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}