The concurrent hash map implementation built by CacheBuilder. This implementation is heavily derived from revision 1.96 of ConcurrentHashMap.java . @author Charles Fry @author Bob Lee (com.google.common.collect.MapMaker) @author
| 94 | * @author Doug Lea ({@code ConcurrentHashMap}) |
| 95 | */ |
| 96 | @GwtCompatible(emulated = true) |
| 97 | class LocalCache<K, V> extends AbstractMap<K, V> implements ConcurrentMap<K, V> { |
| 98 | |
| 99 | /* |
| 100 | * The basic strategy is to subdivide the table among Segments, each of which itself is a |
| 101 | * concurrently readable hash table. The map supports non-blocking reads and concurrent writes |
| 102 | * across different segments. |
| 103 | * |
| 104 | * If a maximum size is specified, a best-effort bounding is performed per segment, using a |
| 105 | * page-replacement algorithm to determine which entries to evict when the capacity has been |
| 106 | * exceeded. |
| 107 | * |
| 108 | * The page replacement algorithm's data structures are kept casually consistent with the map. The |
| 109 | * ordering of writes to a segment is sequentially consistent. An update to the map and recording |
| 110 | * of reads may not be immediately reflected on the algorithm's data structures. These structures |
| 111 | * are guarded by a lock and operations are applied in batches to avoid lock contention. The |
| 112 | * penalty of applying the batches is spread across threads so that the amortized cost is slightly |
| 113 | * higher than performing just the operation without enforcing the capacity constraint. |
| 114 | * |
| 115 | * This implementation uses a per-segment queue to record a memento of the additions, removals, |
| 116 | * and accesses that were performed on the map. The queue is drained on writes and when it exceeds |
| 117 | * its capacity threshold. |
| 118 | * |
| 119 | * The Least Recently Used page replacement algorithm was chosen due to its simplicity, high hit |
| 120 | * rate, and ability to be implemented with O(1) time complexity. The initial LRU implementation |
| 121 | * operates per-segment rather than globally for increased implementation simplicity. We expect |
| 122 | * the cache hit rate to be similar to that of a global LRU algorithm. |
| 123 | */ |
| 124 | |
| 125 | // Constants |
| 126 | |
| 127 | /** |
| 128 | * The maximum capacity, used if a higher value is implicitly specified by either of the |
| 129 | * constructors with arguments. MUST be a power of two <= 1<<30 to ensure that entries are |
| 130 | * indexable using ints. |
| 131 | */ |
| 132 | static final int MAXIMUM_CAPACITY = 1 << 30; |
| 133 | |
| 134 | /** The maximum number of segments to allow; used to bound constructor arguments. */ |
| 135 | static final int MAX_SEGMENTS = 1 << 16; // slightly conservative |
| 136 | |
| 137 | /** Number of (unsynchronized) retries in the containsValue method. */ |
| 138 | static final int CONTAINS_VALUE_RETRIES = 3; |
| 139 | |
| 140 | /** |
| 141 | * Number of cache access operations that can be buffered per segment before the cache's recency |
| 142 | * ordering information is updated. This is used to avoid lock contention by recording a memento |
| 143 | * of reads and delaying a lock acquisition until the threshold is crossed or a mutation occurs. |
| 144 | * |
| 145 | * <p>This must be a (2^n)-1 as it is used as a mask. |
| 146 | */ |
| 147 | static final int DRAIN_THRESHOLD = 0x3F; |
| 148 | |
| 149 | /** |
| 150 | * Maximum number of entries to be drained in a single cleanup run. This applies independently to |
| 151 | * the cleanup queue and both reference queues. |
| 152 | */ |
| 153 | // TODO(fry): empirically optimize this |