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