1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 package org.apache.hadoop.hbase.regionserver;
20
21 import org.apache.commons.logging.Log;
22 import org.apache.commons.logging.LogFactory;
23 import org.apache.hadoop.hbase.classification.InterfaceAudience;
24 import org.apache.hadoop.hbase.io.HeapSize;
25 import org.apache.hadoop.hbase.util.Bytes;
26 import org.apache.hadoop.hbase.util.ClassSize;
27
28 import java.util.ArrayList;
29 import java.util.Collection;
30 import java.util.HashSet;
31 import java.util.List;
32 import java.util.Map;
33 import java.util.Set;
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51 @InterfaceAudience.Private
52 public class LruHashMap<K extends HeapSize, V extends HeapSize>
53 implements HeapSize, Map<K,V> {
54
55 static final Log LOG = LogFactory.getLog(LruHashMap.class);
56
57
58 private static final long DEFAULT_MAX_MEM_USAGE = 50000;
59
60 private static final int DEFAULT_INITIAL_CAPACITY = 16;
61
62 private static final int MAXIMUM_CAPACITY = 1 << 30;
63
64 private static final float DEFAULT_LOAD_FACTOR = 0.75f;
65
66
67 private static final int OVERHEAD = 5 * Bytes.SIZEOF_LONG +
68 2 * Bytes.SIZEOF_INT + 2 * Bytes.SIZEOF_FLOAT + 3 * ClassSize.REFERENCE +
69 1 * ClassSize.ARRAY;
70
71
72 private final float loadFactor;
73
74 private int size;
75
76 private int threshold;
77
78 private Entry [] entries;
79
80
81 private Entry<K,V> headPtr;
82
83 private Entry<K,V> tailPtr;
84
85
86 private long memTotal = 0;
87
88 private long memFree = 0;
89
90
91 private long hitCount = 0;
92
93 private long missCount = 0;
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109 public LruHashMap(int initialCapacity, float loadFactor,
110 long maxMemUsage) {
111 if (initialCapacity < 1) {
112 throw new IllegalArgumentException("Initial capacity must be > 0");
113 }
114 if (initialCapacity > MAXIMUM_CAPACITY) {
115 throw new IllegalArgumentException("Initial capacity is too large");
116 }
117 if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
118 throw new IllegalArgumentException("Load factor must be > 0");
119 }
120 if (maxMemUsage <= (OVERHEAD + initialCapacity * ClassSize.REFERENCE)) {
121 throw new IllegalArgumentException("Max memory usage too small to " +
122 "support base overhead");
123 }
124
125
126 int capacity = calculateCapacity(initialCapacity);
127 this.loadFactor = loadFactor;
128 this.threshold = calculateThreshold(capacity,loadFactor);
129 this.entries = new Entry[capacity];
130 this.memFree = maxMemUsage;
131 this.memTotal = maxMemUsage;
132 init();
133 }
134
135
136
137
138
139
140
141
142
143
144
145
146 public LruHashMap(int initialCapacity, float loadFactor) {
147 this(initialCapacity, loadFactor, DEFAULT_MAX_MEM_USAGE);
148 }
149
150
151
152
153
154
155
156
157
158
159 public LruHashMap(int initialCapacity) {
160 this(initialCapacity, DEFAULT_LOAD_FACTOR, DEFAULT_MAX_MEM_USAGE);
161 }
162
163
164
165
166
167
168
169
170
171 public LruHashMap(long maxMemUsage) {
172 this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR,
173 maxMemUsage);
174 }
175
176
177
178
179
180 public LruHashMap() {
181 this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR,
182 DEFAULT_MAX_MEM_USAGE);
183 }
184
185
186
187
188
189
190
191
192 public long getMemFree() {
193 return memFree;
194 }
195
196
197
198
199
200
201 public long getMemMax() {
202 return memTotal;
203 }
204
205
206
207
208
209
210 public long getMemUsed() {
211 return (memTotal - memFree);
212 }
213
214
215
216
217
218
219
220 public long getHitCount() {
221 return hitCount;
222 }
223
224
225
226
227
228
229
230 public long getMissCount() {
231 return missCount;
232 }
233
234
235
236
237
238
239
240 public double getHitRatio() {
241 return (double)((double)hitCount/
242 ((double)(hitCount+missCount)));
243 }
244
245
246
247
248
249
250
251
252
253
254
255 public synchronized long freeMemory(long requestedAmount) throws Exception {
256 if(requestedAmount > (getMemUsed() - getMinimumUsage())) {
257 return clearAll();
258 }
259 long freedMemory = 0;
260 while(freedMemory < requestedAmount) {
261 freedMemory += evictFromLru();
262 }
263 return freedMemory;
264 }
265
266
267
268
269
270
271 public long heapSize() {
272 return (memTotal - memFree);
273 }
274
275
276
277
278
279
280
281
282
283
284
285
286 public synchronized V get(Object key) {
287 checkKey((K)key);
288 int hash = hash(key);
289 int i = hashIndex(hash, entries.length);
290 Entry<K,V> e = entries[i];
291 while (true) {
292 if (e == null) {
293 missCount++;
294 return null;
295 }
296 if (e.hash == hash && isEqual(key, e.key)) {
297
298 hitCount++;
299 updateLru(e);
300 return e.value;
301 }
302 e = e.next;
303 }
304 }
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321 public synchronized V put(K key, V value) {
322 checkKey(key);
323 checkValue(value);
324 int hash = hash(key);
325 int i = hashIndex(hash, entries.length);
326
327
328 for (Entry<K,V> e = entries[i]; e != null; e = e.next) {
329 if (e.hash == hash && isEqual(key, e.key)) {
330 V oldValue = e.value;
331 long memChange = e.replaceValue(value);
332 checkAndFreeMemory(memChange);
333
334 updateLru(e);
335 return oldValue;
336 }
337 }
338 long memChange = addEntry(hash, key, value, i);
339 checkAndFreeMemory(memChange);
340 return null;
341 }
342
343
344
345
346
347
348
349
350 public synchronized V remove(Object key) {
351 Entry<K,V> e = removeEntryForKey((K)key);
352 if(e == null) return null;
353
354 memFree += e.heapSize();
355 return e.value;
356 }
357
358
359
360
361
362
363 public int size() {
364 return size;
365 }
366
367
368
369
370
371
372 public boolean isEmpty() {
373 return size == 0;
374 }
375
376
377
378
379
380
381
382 public synchronized void clear() {
383 memFree += clearAll();
384 }
385
386
387
388
389
390
391
392
393
394
395
396 public synchronized boolean containsKey(Object key) {
397 checkKey((K)key);
398 int hash = hash(key);
399 int i = hashIndex(hash, entries.length);
400 Entry e = entries[i];
401 while (e != null) {
402 if (e.hash == hash && isEqual(key, e.key))
403 return true;
404 e = e.next;
405 }
406 return false;
407 }
408
409
410
411
412
413
414
415
416
417
418
419 public synchronized boolean containsValue(Object value) {
420 checkValue((V)value);
421 Entry[] tab = entries;
422 for (int i = 0; i < tab.length ; i++)
423 for (Entry e = tab[i] ; e != null ; e = e.next)
424 if (value.equals(e.value))
425 return true;
426 return false;
427 }
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442 private void checkKey(K key) {
443 if(key == null) {
444 throw new NullPointerException("null keys are not allowed");
445 }
446 }
447
448
449
450
451
452
453
454
455
456
457
458
459
460 private void checkValue(V value) {
461 if(value == null) {
462 throw new NullPointerException("null values are not allowed");
463 }
464 }
465
466
467
468
469
470
471 private long getMinimumUsage() {
472 return OVERHEAD + (entries.length * ClassSize.REFERENCE);
473 }
474
475
476
477
478
479
480
481
482 private void checkAndFreeMemory(long memNeeded) {
483 while(memFree < memNeeded) {
484 evictFromLru();
485 }
486 memFree -= memNeeded;
487 }
488
489
490
491
492
493
494
495 private long evictFromLru() {
496 long freed = headPtr.heapSize();
497 memFree += freed;
498 removeEntry(headPtr);
499 return freed;
500 }
501
502
503
504
505
506
507
508 private void updateLru(Entry<K,V> e) {
509 Entry<K,V> prev = e.getPrevPtr();
510 Entry<K,V> next = e.getNextPtr();
511 if(next != null) {
512 if(prev != null) {
513 prev.setNextPtr(next);
514 next.setPrevPtr(prev);
515 } else {
516 headPtr = next;
517 headPtr.setPrevPtr(null);
518 }
519 e.setNextPtr(null);
520 e.setPrevPtr(tailPtr);
521 tailPtr.setNextPtr(e);
522 tailPtr = e;
523 }
524 }
525
526
527
528
529
530
531 private void removeEntry(Entry<K,V> entry) {
532 K k = entry.key;
533 int hash = entry.hash;
534 int i = hashIndex(hash, entries.length);
535 Entry<K,V> prev = entries[i];
536 Entry<K,V> e = prev;
537
538 while (e != null) {
539 Entry<K,V> next = e.next;
540 if (e.hash == hash && isEqual(k, e.key)) {
541 size--;
542 if (prev == e) {
543 entries[i] = next;
544 } else {
545 prev.next = next;
546 }
547
548 Entry<K,V> prevPtr = e.getPrevPtr();
549 Entry<K,V> nextPtr = e.getNextPtr();
550
551 if(prevPtr != null && nextPtr != null) {
552 prevPtr.setNextPtr(nextPtr);
553 nextPtr.setPrevPtr(prevPtr);
554 } else if(prevPtr != null) {
555 tailPtr = prevPtr;
556 prevPtr.setNextPtr(null);
557 } else if(nextPtr != null) {
558 headPtr = nextPtr;
559 nextPtr.setPrevPtr(null);
560 }
561
562 return;
563 }
564 prev = e;
565 e = next;
566 }
567 }
568
569
570
571
572
573
574
575
576 private Entry<K,V> removeEntryForKey(K key) {
577 int hash = hash(key);
578 int i = hashIndex(hash, entries.length);
579 Entry<K,V> prev = entries[i];
580 Entry<K,V> e = prev;
581
582 while (e != null) {
583 Entry<K,V> next = e.next;
584 if (e.hash == hash && isEqual(key, e.key)) {
585 size--;
586 if (prev == e) {
587 entries[i] = next;
588 } else {
589 prev.next = next;
590 }
591
592
593 Entry<K,V> prevPtr = e.getPrevPtr();
594 Entry<K,V> nextPtr = e.getNextPtr();
595 if(prevPtr != null && nextPtr != null) {
596 prevPtr.setNextPtr(nextPtr);
597 nextPtr.setPrevPtr(prevPtr);
598 } else if(prevPtr != null) {
599 tailPtr = prevPtr;
600 prevPtr.setNextPtr(null);
601 } else if(nextPtr != null) {
602 headPtr = nextPtr;
603 nextPtr.setPrevPtr(null);
604 }
605
606 return e;
607 }
608 prev = e;
609 e = next;
610 }
611
612 return e;
613 }
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628 private long addEntry(int hash, K key, V value, int bucketIndex) {
629 Entry<K,V> e = entries[bucketIndex];
630 Entry<K,V> newE = new Entry<K,V>(hash, key, value, e, tailPtr);
631 entries[bucketIndex] = newE;
632
633 if (size == 0) {
634 headPtr = newE;
635 tailPtr = newE;
636 } else {
637 newE.setPrevPtr(tailPtr);
638 tailPtr.setNextPtr(newE);
639 tailPtr = newE;
640 }
641
642 if (size++ >= threshold) {
643 growTable(2 * entries.length);
644 }
645 return newE.heapSize();
646 }
647
648
649
650
651
652
653
654
655
656 private long clearAll() {
657 Entry cur;
658 long freedMemory = 0;
659 for(int i=0; i<entries.length; i++) {
660 cur = entries[i];
661 while(cur != null) {
662 freedMemory += cur.heapSize();
663 cur = cur.next;
664 }
665 entries[i] = null;
666 }
667 headPtr = null;
668 tailPtr = null;
669 size = 0;
670 return freedMemory;
671 }
672
673
674
675
676
677
678
679
680
681 private void growTable(int newCapacity) {
682 Entry [] oldTable = entries;
683 int oldCapacity = oldTable.length;
684
685
686 if (oldCapacity == MAXIMUM_CAPACITY) {
687 threshold = Integer.MAX_VALUE;
688 return;
689 }
690
691
692 long requiredSpace = (newCapacity - oldCapacity) * ClassSize.REFERENCE;
693
694
695 checkAndFreeMemory(requiredSpace);
696
697 Entry [] newTable = new Entry[newCapacity];
698
699
700 for(int i=0; i < oldCapacity; i++) {
701 Entry<K,V> entry = oldTable[i];
702 if(entry != null) {
703
704 oldTable[i] = null;
705 do {
706 Entry<K,V> next = entry.next;
707 int idx = hashIndex(entry.hash, newCapacity);
708 entry.next = newTable[idx];
709 newTable[idx] = entry;
710 entry = next;
711 } while(entry != null);
712 }
713 }
714
715 entries = newTable;
716 threshold = (int)(newCapacity * loadFactor);
717 }
718
719
720
721
722
723
724
725
726
727 private int hash(Object key) {
728 int h = key.hashCode();
729 h += ~(h << 9);
730 h ^= (h >>> 14);
731 h += (h << 4);
732 h ^= (h >>> 10);
733 return h;
734 }
735
736
737
738
739
740
741
742
743
744 private boolean isEqual(Object x, Object y) {
745 return (x == y || x.equals(y));
746 }
747
748
749
750
751
752
753
754
755
756 private int hashIndex(int hashValue, int length) {
757 return hashValue & (length - 1);
758 }
759
760
761
762
763
764
765
766
767
768 private int calculateCapacity(int proposedCapacity) {
769 int newCapacity = 1;
770 if(proposedCapacity > MAXIMUM_CAPACITY) {
771 newCapacity = MAXIMUM_CAPACITY;
772 } else {
773 while(newCapacity < proposedCapacity) {
774 newCapacity <<= 1;
775 }
776 if(newCapacity > MAXIMUM_CAPACITY) {
777 newCapacity = MAXIMUM_CAPACITY;
778 }
779 }
780 return newCapacity;
781 }
782
783
784
785
786
787
788
789
790
791 private int calculateThreshold(int capacity, float factor) {
792 return (int)(capacity * factor);
793 }
794
795
796
797
798
799 private void init() {
800 memFree -= OVERHEAD;
801 memFree -= (entries.length * ClassSize.REFERENCE);
802 }
803
804
805
806
807
808
809
810
811
812 public List<Entry<K,V>> entryLruList() {
813 List<Entry<K,V>> entryList = new ArrayList<Entry<K,V>>();
814 Entry<K,V> entry = headPtr;
815 while(entry != null) {
816 entryList.add(entry);
817 entry = entry.getNextPtr();
818 }
819 return entryList;
820 }
821
822
823
824
825
826
827 public Set<Entry<K,V>> entryTableSet() {
828 Set<Entry<K,V>> entrySet = new HashSet<Entry<K,V>>();
829 Entry [] table = entries;
830 for(int i=0;i<table.length;i++) {
831 for(Entry e = table[i]; e != null; e = e.next) {
832 entrySet.add(e);
833 }
834 }
835 return entrySet;
836 }
837
838
839
840
841
842
843 public Entry getHeadPtr() {
844 return headPtr;
845 }
846
847
848
849
850
851
852 public Entry getTailPtr() {
853 return tailPtr;
854 }
855
856
857
858
859
860
861
862
863
864
865
866
867
868 public Set<Map.Entry<K,V>> entrySet() {
869 throw new UnsupportedOperationException(
870 "entrySet() is intentionally unimplemented");
871 }
872
873
874
875
876 public boolean equals(Object o) {
877 throw new UnsupportedOperationException(
878 "equals(Object) is intentionally unimplemented");
879 }
880
881
882
883
884 public int hashCode() {
885 throw new UnsupportedOperationException(
886 "hashCode(Object) is intentionally unimplemented");
887 }
888
889
890
891
892 public Set<K> keySet() {
893 throw new UnsupportedOperationException(
894 "keySet() is intentionally unimplemented");
895 }
896
897
898
899
900 public void putAll(Map<? extends K, ? extends V> m) {
901 throw new UnsupportedOperationException(
902 "putAll() is intentionally unimplemented");
903 }
904
905
906
907
908 public Collection<V> values() {
909 throw new UnsupportedOperationException(
910 "values() is intentionally unimplemented");
911 }
912
913
914
915
916
917
918
919
920
921
922
923 protected static class Entry<K extends HeapSize, V extends HeapSize>
924 implements Map.Entry<K,V>, HeapSize {
925
926 static final int OVERHEAD = 1 * Bytes.SIZEOF_LONG +
927 5 * ClassSize.REFERENCE + 2 * Bytes.SIZEOF_INT;
928
929
930 protected final K key;
931
932 protected V value;
933
934 protected final int hash;
935
936 protected Entry<K,V> next;
937
938
939 protected Entry<K,V> prevPtr;
940
941 protected Entry<K,V> nextPtr;
942
943
944 protected long heapSize;
945
946
947
948
949
950
951
952
953
954
955 Entry(int h, K k, V v, Entry<K,V> nextChainPtr, Entry<K,V> prevLruPtr) {
956 value = v;
957 next = nextChainPtr;
958 key = k;
959 hash = h;
960 prevPtr = prevLruPtr;
961 nextPtr = null;
962
963 heapSize = OVERHEAD + k.heapSize() + v.heapSize();
964 }
965
966
967
968
969
970
971 public K getKey() {
972 return key;
973 }
974
975
976
977
978
979
980 public V getValue() {
981 return value;
982 }
983
984
985
986
987
988
989
990
991
992
993
994 public V setValue(V newValue) {
995 V oldValue = value;
996 value = newValue;
997 return oldValue;
998 }
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009 protected long replaceValue(V newValue) {
1010 long sizeDiff = newValue.heapSize() - value.heapSize();
1011 value = newValue;
1012 heapSize += sizeDiff;
1013 return sizeDiff;
1014 }
1015
1016
1017
1018
1019
1020
1021
1022
1023 public boolean equals(Object o) {
1024 if (!(o instanceof Map.Entry))
1025 return false;
1026 Map.Entry e = (Map.Entry)o;
1027 Object k1 = getKey();
1028 Object k2 = e.getKey();
1029 if (k1 == k2 || (k1 != null && k1.equals(k2))) {
1030 Object v1 = getValue();
1031 Object v2 = e.getValue();
1032 if (v1 == v2 || (v1 != null && v1.equals(v2)))
1033 return true;
1034 }
1035 return false;
1036 }
1037
1038
1039
1040
1041
1042
1043
1044 public int hashCode() {
1045 return (key.hashCode() ^ value.hashCode());
1046 }
1047
1048
1049
1050
1051
1052
1053 public String toString() {
1054 return getKey() + "=" + getValue();
1055 }
1056
1057
1058
1059
1060
1061
1062 protected void setPrevPtr(Entry<K,V> prevPtr){
1063 this.prevPtr = prevPtr;
1064 }
1065
1066
1067
1068
1069
1070 protected Entry<K,V> getPrevPtr(){
1071 return prevPtr;
1072 }
1073
1074
1075
1076
1077
1078 protected void setNextPtr(Entry<K,V> nextPtr){
1079 this.nextPtr = nextPtr;
1080 }
1081
1082
1083
1084
1085
1086 protected Entry<K,V> getNextPtr(){
1087 return nextPtr;
1088 }
1089
1090
1091
1092
1093
1094 public long heapSize() {
1095 return heapSize;
1096 }
1097 }
1098 }
1099
1100