001/*
002 * Licensed to the Apache Software Foundation (ASF) under one
003 * or more contributor license agreements.  See the NOTICE file
004 * distributed with this work for additional information
005 * regarding copyright ownership.  The ASF licenses this file
006 * to you under the Apache License, Version 2.0 (the
007 * "License"); you may not use this file except in compliance
008 * with the License.  You may obtain a copy of the License at
009 *
010 *     http://www.apache.org/licenses/LICENSE-2.0
011 *
012 * Unless required by applicable law or agreed to in writing, software
013 * distributed under the License is distributed on an "AS IS" BASIS,
014 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
015 * See the License for the specific language governing permissions and
016 * limitations under the License.
017 */
018package org.apache.hadoop.hbase.io.util;
019
020import java.nio.ByteBuffer;
021import java.util.HashMap;
022import org.apache.hadoop.hbase.util.ByteBufferUtils;
023import org.apache.hadoop.hbase.util.Bytes;
024import org.apache.yetus.audience.InterfaceAudience;
025
026import org.apache.hbase.thirdparty.com.google.common.base.Preconditions;
027
028/**
029 * WALDictionary using an LRU eviction algorithm. Uses a linked list running through a hashtable.
030 * Currently has max of 2^15 entries. Will start evicting if exceeds this number The maximum memory
031 * we expect this dictionary to take in the worst case is about:
032 * <code>(2 ^ 15) * 5 (Regionname, Row key, CF, Column qual, table) * 100 bytes
033 * (these are some big names) = ~16MB</code>. If you want to get silly, even at 1kb entries, it
034 * maxes out at 160 megabytes.
035 */
036@InterfaceAudience.Private
037public class LRUDictionary implements Dictionary {
038
039  BidirectionalLRUMap backingStore;
040
041  @Override
042  public byte[] getEntry(short idx) {
043    return backingStore.get(idx);
044  }
045
046  @Override
047  public void init(int initialSize) {
048    backingStore = new BidirectionalLRUMap(initialSize);
049  }
050
051  @Override
052  public short findEntry(byte[] data, int offset, int length) {
053    short ret = backingStore.findIdx(data, offset, length);
054    if (ret == NOT_IN_DICTIONARY) {
055      addEntry(data, offset, length);
056    }
057    return ret;
058  }
059
060  @Override
061  public short addEntry(byte[] data, int offset, int length) {
062    return addEntryInternal(data, offset, length, true);
063  }
064
065  private short addEntryInternal(byte[] data, int offset, int length, boolean copy) {
066    if (length <= 0) return NOT_IN_DICTIONARY;
067    return backingStore.put(data, offset, length, copy);
068  }
069
070  @Override
071  public void clear() {
072    backingStore.clear();
073  }
074
075  /*
076   * Internal class used to implement LRU eviction and dual lookup (by key and value). This is not
077   * thread safe. Don't use in multi-threaded applications.
078   */
079  static class BidirectionalLRUMap {
080    private int currSize = 0;
081
082    // Head and tail of the LRU list.
083    private Node head;
084    private Node tail;
085
086    private HashMap<Node, Short> nodeToIndex = new HashMap<>();
087    private Node[] indexToNode;
088    private int initSize = 0;
089
090    public BidirectionalLRUMap(int initialSize) {
091      initSize = initialSize;
092      indexToNode = new Node[initialSize];
093    }
094
095    private short put(byte[] array, int offset, int length, boolean copy) {
096      if (copy) {
097        // We copy the bytes we want, otherwise we might be holding references to
098        // massive arrays in our dictionary (or those arrays might change)
099        byte[] stored = new byte[length];
100        Bytes.putBytes(stored, 0, array, offset, length);
101        return putInternal(stored);
102      } else {
103        return putInternal(array);
104      }
105    }
106
107    private short putInternal(byte[] stored) {
108      if (currSize < initSize) {
109        // There is space to add without evicting.
110        if (indexToNode[currSize] == null) {
111          indexToNode[currSize] = new ByteArrayBackedNode();
112        }
113        indexToNode[currSize].setContents(stored, 0, stored.length);
114        setHead(indexToNode[currSize]);
115        short ret = (short) currSize++;
116        nodeToIndex.put(indexToNode[ret], ret);
117        return ret;
118      } else {
119        short s = nodeToIndex.remove(tail);
120        tail.setContents(stored, 0, stored.length);
121        // we need to rehash this.
122        nodeToIndex.put(tail, s);
123        moveToHead(tail);
124        return s;
125      }
126    }
127
128    private short findIdx(byte[] array, int offset, int length) {
129      Short s;
130      final Node comparisonNode = new ByteArrayBackedNode();
131      comparisonNode.setContents(array, offset, length);
132      if ((s = nodeToIndex.get(comparisonNode)) != null) {
133        moveToHead(indexToNode[s]);
134        return s;
135      } else {
136        return -1;
137      }
138    }
139
140    private short findIdx(ByteBuffer buf, int offset, int length) {
141      Short s;
142      final ByteBufferBackedNode comparisonNode = new ByteBufferBackedNode();
143      comparisonNode.setContents(buf, offset, length);
144      if ((s = nodeToIndex.get(comparisonNode)) != null) {
145        moveToHead(indexToNode[s]);
146        return s;
147      } else {
148        return -1;
149      }
150    }
151
152    private byte[] get(short idx) {
153      Preconditions.checkElementIndex(idx, currSize);
154      moveToHead(indexToNode[idx]);
155      return indexToNode[idx].getContents();
156    }
157
158    private void moveToHead(Node n) {
159      if (head == n) {
160        // no-op -- it's already the head.
161        return;
162      }
163      // At this point we definitely have prev, since it's not the head.
164      assert n.prev != null;
165      // Unlink prev.
166      n.prev.next = n.next;
167
168      // Unlink next
169      if (n.next != null) {
170        n.next.prev = n.prev;
171      } else {
172        assert n == tail;
173        tail = n.prev;
174      }
175      // Node is now removed from the list. Re-add it at the head.
176      setHead(n);
177    }
178
179    private void setHead(Node n) {
180      // assume it's already unlinked from the list at this point.
181      n.prev = null;
182      n.next = head;
183      if (head != null) {
184        assert head.prev == null;
185        head.prev = n;
186      }
187
188      head = n;
189
190      // First entry
191      if (tail == null) {
192        tail = n;
193      }
194    }
195
196    private void clear() {
197      for (int i = 0; i < currSize; i++) {
198        indexToNode[i].next = null;
199        indexToNode[i].prev = null;
200        indexToNode[i].resetContents();
201      }
202      currSize = 0;
203      nodeToIndex.clear();
204      tail = null;
205      head = null;
206    }
207
208    private static abstract class Node {
209      int offset;
210      int length;
211      Node next; // link towards the tail
212      Node prev; // link towards the head
213
214      abstract void setContents(byte[] container, int offset, int length);
215
216      abstract byte[] getContents();
217
218      abstract void resetContents();
219    }
220
221    // The actual contents of the LRUDictionary are of ByteArrayBackedNode type
222    private static class ByteArrayBackedNode extends Node {
223      private byte[] container;
224
225      @Override
226      void setContents(byte[] container, int offset, int length) {
227        this.container = container;
228        this.offset = offset;
229        this.length = length;
230      }
231
232      @Override
233      byte[] getContents() {
234        return this.container;
235      }
236
237      @Override
238      public int hashCode() {
239        return Bytes.hashCode(container, offset, length);
240      }
241
242      @Override
243      void resetContents() {
244        this.container = null;
245      }
246
247      @Override
248      public boolean equals(Object other) {
249        if (!(other instanceof Node)) {
250          return false;
251        }
252
253        Node casted = (Node) other;
254        return Bytes.equals(container, offset, length, casted.getContents(), casted.offset,
255          casted.length);
256      }
257    }
258
259    // Currently only used for finding the index and hence this node acts
260    // as a temporary holder to look up in the indexToNode map
261    // which is formed by ByteArrayBackedNode
262    private static class ByteBufferBackedNode extends Node {
263      private ByteBuffer container;
264
265      public ByteBufferBackedNode() {
266      }
267
268      @Override
269      void setContents(byte[] container, int offset, int length) {
270        this.container = ByteBuffer.wrap(container);
271        this.offset = offset;
272        this.length = length;
273      }
274
275      void setContents(ByteBuffer container, int offset, int length) {
276        this.container = container;
277        this.offset = offset;
278        this.length = length;
279      }
280
281      @Override
282      void resetContents() {
283        this.container = null;
284      }
285
286      @Override
287      byte[] getContents() {
288        // This ideally should not be called
289        byte[] copy = new byte[this.length];
290        ByteBufferUtils.copyFromBufferToArray(copy, (ByteBuffer) this.container, this.offset, 0,
291          length);
292        return copy;
293      }
294
295      @Override
296      public int hashCode() {
297        return ByteBufferUtils.hashCode(container, offset, length);
298      }
299
300      @Override
301      public boolean equals(Object other) {
302        if (!(other instanceof Node)) {
303          return false;
304        }
305        // This was done to avoid findbugs comment
306        Node casted = (Node) other;
307        // The other side should be a byte array backed node only as we add only
308        // ByteArrayBackedNode to the indexToNode map.
309        return ByteBufferUtils.equals(this.container, offset, length, casted.getContents(),
310          casted.offset, casted.length);
311      }
312    }
313  }
314
315  @Override
316  public short findEntry(ByteBuffer data, int offset, int length) {
317    short ret = backingStore.findIdx(data, offset, length);
318    if (ret == NOT_IN_DICTIONARY) {
319      byte[] copy = new byte[length];
320      ByteBufferUtils.copyFromBufferToArray(copy, data, offset, 0, length);
321      addEntryInternal(copy, 0, length, false);
322    }
323    return ret;
324  }
325}