View Javadoc

1   /**
2    * Licensed to the Apache Software Foundation (ASF) under one
3    * or more contributor license agreements.  See the NOTICE file
4    * distributed with this work for additional information
5    * regarding copyright ownership.  The ASF licenses this file
6    * to you under the Apache License, Version 2.0 (the
7    * "License"); you may not use this file except in compliance
8    * with the License.  You may obtain a copy of the License at
9    *
10   *     http://www.apache.org/licenses/LICENSE-2.0
11   *
12   * Unless required by applicable law or agreed to in writing, software
13   * distributed under the License is distributed on an "AS IS" BASIS,
14   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15   * See the License for the specific language governing permissions and
16   * limitations under the License.
17   */
18  
19  package org.apache.hadoop.hbase.io.util;
20  
21  import java.util.HashMap;
22  
23  import org.apache.hadoop.classification.InterfaceAudience;
24  import org.apache.hadoop.hbase.util.Bytes;
25  
26  import com.google.common.base.Preconditions;
27  
28  /**
29   * WALDictionary using an LRU eviction algorithm. Uses a linked list running
30   * through a hashtable.  Currently has max of 2^15 entries.  Will start
31   * evicting if exceeds this number  The maximum memory we expect this dictionary
32   * to take in the worst case is about:
33   * <code>(2 ^ 15) * 5 (Regionname, Row key, CF, Column qual, table) * 100 bytes 
34   * (these are some big names) = ~16MB</code>.
35   * If you want to get silly, even at 1kb entries, it maxes out at 160 megabytes.
36   */
37  @InterfaceAudience.Private
38  public class LRUDictionary implements Dictionary {
39  
40    BidirectionalLRUMap backingStore;
41    @Override
42    public byte[] getEntry(short idx) {
43      return backingStore.get(idx);
44    }
45  
46    @Override
47    public void init(int initialSize) {
48      backingStore = new BidirectionalLRUMap(initialSize);
49    }
50    @Override
51    public short findEntry(byte[] data, int offset, int length) {
52      short ret = backingStore.findIdx(data, offset, length);
53      if (ret == NOT_IN_DICTIONARY) {
54        addEntry(data, offset, length);
55      }
56      return ret;
57    }
58  
59    @Override
60    public short addEntry(byte[] data, int offset, int length) {
61      if (length <= 0) return NOT_IN_DICTIONARY;
62      return backingStore.put(data, offset, length);
63    }
64  
65    @Override
66    public void clear() {
67      backingStore.clear();
68    }
69  
70    /*
71     * Internal class used to implement LRU eviction and dual lookup (by key and
72     * value).
73     * 
74     * This is not thread safe. Don't use in multi-threaded applications.
75     */
76    static class BidirectionalLRUMap {
77      private int currSize = 0;
78  
79      // Head and tail of the LRU list.
80      private Node head;
81      private Node tail;
82  
83      private HashMap<Node, Short> nodeToIndex = new HashMap<Node, Short>();
84      private Node[] indexToNode;
85      private int initSize = 0;
86  
87      public BidirectionalLRUMap(int initialSize) {
88        initSize = initialSize;
89        indexToNode = new Node[initialSize];
90      }
91  
92      private short put(byte[] array, int offset, int length) {
93        // We copy the bytes we want, otherwise we might be holding references to
94        // massive arrays in our dictionary (or those arrays might change)
95        byte[] stored = new byte[length];
96        Bytes.putBytes(stored, 0, array, offset, length);
97  
98        if (currSize < initSize) {
99          // There is space to add without evicting.
100         if (indexToNode[currSize] == null) {
101           indexToNode[currSize] = new Node();
102         }
103         indexToNode[currSize].setContents(stored, 0, stored.length);
104         setHead(indexToNode[currSize]);
105         short ret = (short) currSize++;
106         nodeToIndex.put(indexToNode[ret], ret);
107         return ret;
108       } else {
109         short s = nodeToIndex.remove(tail);
110         tail.setContents(stored, 0, stored.length);
111         // we need to rehash this.
112         nodeToIndex.put(tail, s);
113         moveToHead(tail);
114         return s;
115       }
116     }
117 
118     private short findIdx(byte[] array, int offset, int length) {
119       Short s;
120       final Node comparisonNode = new Node();
121       comparisonNode.setContents(array, offset, length);
122       if ((s = nodeToIndex.get(comparisonNode)) != null) {
123         moveToHead(indexToNode[s]);
124         return s;
125       } else {
126         return -1;
127       }
128     }
129 
130     private byte[] get(short idx) {
131       Preconditions.checkElementIndex(idx, currSize);
132       moveToHead(indexToNode[idx]);
133       return indexToNode[idx].container;
134     }
135 
136     private void moveToHead(Node n) {
137       if (head == n) {
138         // no-op -- it's already the head.
139         return;
140       }
141       // At this point we definitely have prev, since it's not the head.
142       assert n.prev != null;
143       // Unlink prev.
144       n.prev.next = n.next;
145 
146       // Unlink next
147       if (n.next != null) {
148         n.next.prev = n.prev;
149       } else {
150         assert n == tail;
151         tail = n.prev;
152       }
153       // Node is now removed from the list. Re-add it at the head.
154       setHead(n);
155     }
156     
157     private void setHead(Node n) {
158       // assume it's already unlinked from the list at this point.
159       n.prev = null;
160       n.next = head;
161       if (head != null) {
162         assert head.prev == null;
163         head.prev = n;
164       }
165 
166       head = n;
167 
168       // First entry
169       if (tail == null) {
170         tail = n;
171       }
172     }
173 
174     private void clear() {
175       for (int i = 0; i < currSize; i++) {
176         indexToNode[i].next = null;
177         indexToNode[i].prev = null;
178         indexToNode[i].container = null;
179       }
180       currSize = 0;
181       nodeToIndex.clear();
182       tail = null;
183       head = null;
184     }
185 
186     private static class Node {
187       byte[] container;
188       int offset;
189       int length;
190       Node next; // link towards the tail
191       Node prev; // link towards the head
192 
193       public Node() {
194       }
195 
196       private void setContents(byte[] container, int offset, int length) {
197         this.container = container;
198         this.offset = offset;
199         this.length = length;
200       }
201 
202       @Override
203       public int hashCode() {
204         return Bytes.hashCode(container, offset, length);
205       }
206 
207       @Override
208       public boolean equals(Object other) {
209         if (!(other instanceof Node)) {
210           return false;
211         }
212 
213         Node casted = (Node) other;
214         return Bytes.equals(container, offset, length, casted.container,
215             casted.offset, casted.length);
216       }
217     }
218   }
219 }