2 * Copyright 2015 Facebook, Inc.
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
8 * http://www.apache.org/licenses/LICENSE-2.0
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
17 #ifndef FOLLY_EVICTINGHASHMAP_H_
18 #define FOLLY_EVICTINGHASHMAP_H_
24 #include <boost/utility.hpp>
25 #include <boost/intrusive/list.hpp>
26 #include <boost/intrusive/unordered_set.hpp>
27 #include <boost/iterator/iterator_adaptor.hpp>
32 * A general purpose LRU evicting cache. Designed to support constant time
33 * set/get operations. It maintains a doubly linked list of items that are
34 * threaded through an index (a hash map). The access ordered is maintained
35 * on the list by moving an element to the front of list on a get. New elements
36 * are added to the front of the list. The index size is set to half the
37 * capacity (setting capacity to 0 is a special case. see notes at the end of
38 * this section). So assuming uniform distribution of keys, set/get are both
39 * constant time operations.
41 * On reaching capacity limit, clearSize_ LRU items are evicted at a time. If
42 * a callback is specified with setPruneHook, it is invoked for each eviction.
44 * This is NOT a thread-safe implementation.
46 * Configurability: capacity of the cache, number of items to evict, eviction
47 * callback and the hasher to hash the keys can all be supplied by the caller.
49 * If at a given state, N1 - N6 are the nodes in MRU to LRU order and hashing
50 * to index keys as {(N1,N5)->H1, (N4,N5,N5)->H2, N3->Hi}, the datastructure
51 * layout is as below. N1 .. N6 is a list threaded through the hash.
52 * Assuming, each the number of nodes hashed to each index key is bounded, the
53 * following operations run in constant time.
54 * i) get computes the index key, walks the list of elements hashed to
55 * the key and moves it to the front of the list, if found.
56 * ii) set inserts a new node into the list and places the same node on to the
57 * list of elements hashing to the corresponding index key.
58 * ii) prune deletes nodes from the end of the list as well from the index.
60 * +----+ +----+ +----+
61 * | H1 | <-> | N1 | <-> | N5 |
62 * +----+ +----+ +----+
70 * +----+ +----+ +----+ +----+
71 * | H2 | <-> | N4 | <-> | N2 | <-> | N6 |
72 * +----+ +----+ +----+ +----+
83 * N.B 1 : Changing the capacity with setMaxSize does not change the index size
84 * and it could end up in too many elements indexed to the same slot in index.
85 * The set/get performance will get worse in this case. So it is best to avoid
88 * N.B 2 : Setting capacity to 0, using setMaxSize or initialization, turns off
89 * evictions based on sizeof the cache making it an INFINITE size cache
90 * unless evictions of LRU items are triggered by calling prune() by clients
91 * (using their own eviction criteria).
93 template <class TKey, class TValue, class THash = std::hash<TKey> >
94 class EvictingCacheMap : private boost::noncopyable {
97 // typedefs for brevity
99 typedef boost::intrusive::link_mode<boost::intrusive::safe_link> link_mode;
100 typedef boost::intrusive::unordered_set<Node> NodeMap;
101 typedef boost::intrusive::list<Node> NodeList;
102 typedef std::pair<const TKey, TValue> TPair;
105 typedef std::function<void(TKey, TValue&&)> PruneHookCall;
107 // iterator base : returns TPair on dereference
108 template <typename Value, typename TIterator>
110 : public boost::iterator_adaptor<iterator_base<Value, TIterator>,
113 boost::bidirectional_traversal_tag > {
117 explicit iterator_base(TIterator it)
118 : iterator_base::iterator_adaptor_(it) {
120 Value& dereference() const {
121 return this->base_reference()->pr;
126 typedef iterator_base<
127 TPair, typename NodeList::iterator> iterator;
128 typedef iterator_base<
129 const TPair, typename NodeList::const_iterator> const_iterator;
130 typedef iterator_base<
131 TPair, typename NodeList::reverse_iterator> reverse_iterator;
132 typedef iterator_base<
134 typename NodeList::const_reverse_iterator> const_reverse_iterator;
137 * Construct a EvictingCacheMap
138 * @param maxSize maximum size of the cache map. Once the map size exceeds
139 * maxSize, the map will begin to evict.
140 * @param clearSize the number of elements to clear at a time when the
141 * eviction size is reached.
143 explicit EvictingCacheMap(std::size_t maxSize, std::size_t clearSize = 1)
144 : nIndexBuckets_(std::max(maxSize / 2, std::size_t(kMinNumIndexBuckets))),
145 indexBuckets_(new typename NodeMap::bucket_type[nIndexBuckets_]),
146 indexTraits_(indexBuckets_.get(), nIndexBuckets_),
147 index_(indexTraits_),
149 clearSize_(clearSize) { }
152 ~EvictingCacheMap() {
153 setPruneHook(nullptr);
154 // ignore any potential exceptions from pruneHook_
155 pruneWithFailSafeOption(size(), nullptr, true);
159 * Adjust the max size of EvictingCacheMap. Note that this does not update
160 * nIndexBuckets_ accordingly. This API can cause performance to get very
161 * bad, e.g., the nIndexBuckets_ is still 100 after maxSize is updated to 1M.
163 * Calling this function with an arugment of 0 removes the limit on the cache
164 * size and elements are not evicted unless clients explictly call prune.
166 * If you intend to resize dynamically using this, then picking an index size
167 * that works well and initializing with corresponding maxSize is the only
170 * @param maxSize new maximum size of the cache map.
171 * @param pruneHook callback to use on eviction.
173 void setMaxSize(size_t maxSize, PruneHookCall pruneHook = nullptr) {
174 if (maxSize != 0 && maxSize < size()) {
175 // Prune the excess elements with our new constraints.
176 prune(std::max(size() - maxSize, clearSize_), pruneHook);
181 size_t getMaxSize() const {
185 void setClearSize(size_t clearSize) {
186 clearSize_ = clearSize;
190 * Check for existence of a specific key in the map. This operation has
191 * no effect on LRU order.
192 * @param key key to search for
193 * @return true if exists, false otherwise
195 bool exists(const TKey& key) const {
196 return findInIndex(key) != index_.end();
200 * Get the value associated with a specific key. This function always
201 * promotes a found value to the head of the LRU.
202 * @param key key associated with the value
203 * @return the value if it exists
204 * @throw std::out_of_range exception of the key does not exist
206 TValue& get(const TKey& key) {
209 throw std::out_of_range("Key does not exist");
215 * Get the iterator associated with a specific key. This function always
216 * promotes a found value to the head of the LRU.
217 * @param key key to associate with value
218 * @return the iterator of the object (a std::pair of const TKey, TValue) or
219 * end() if it does not exist
221 iterator find(const TKey& key) {
222 auto it = findInIndex(key);
223 if (it == index_.end()) {
226 lru_.erase(lru_.iterator_to(*it));
227 lru_.push_front(*it);
228 return iterator(lru_.iterator_to(*it));
232 * Get the value associated with a specific key. This function never
233 * promotes a found value to the head of the LRU.
234 * @param key key associated with the value
235 * @return the value if it exists
236 * @throw std::out_of_range exception of the key does not exist
238 const TValue& getWithoutPromotion(const TKey& key) const {
239 auto it = findWithoutPromotion(key);
241 throw std::out_of_range("Key does not exist");
246 TValue& getWithoutPromotion(const TKey& key) {
247 auto const& cThis = *this;
248 return const_cast<TValue&>(cThis.getWithoutPromotion(key));
252 * Get the iterator associated with a specific key. This function never
253 * promotes a found value to the head of the LRU.
254 * @param key key to associate with value
255 * @return the iterator of the object (a std::pair of const TKey, TValue) or
256 * end() if it does not exist
258 const_iterator findWithoutPromotion(const TKey& key) const {
259 auto it = findInIndex(key);
260 return (it == index_.end()) ? end() : const_iterator(lru_.iterator_to(*it));
263 iterator findWithoutPromotion(const TKey& key) {
264 auto it = findInIndex(key);
265 return (it == index_.end()) ? end() : iterator(lru_.iterator_to(*it));
269 * Erase the key-value pair associated with key if it exists.
270 * @param key key associated with the value
271 * @return true if the key existed and was erased, else false
273 bool erase(const TKey& key) {
274 auto it = findInIndex(key);
275 if (it == index_.end()) {
279 std::unique_ptr<Node> nptr(node);
280 lru_.erase(lru_.iterator_to(*node));
286 * Set a key-value pair in the dictionary
287 * @param key key to associate with value
288 * @param value value to associate with the key
289 * @param promote boolean flag indicating whether or not to move something
290 * to the front of an LRU. This only really matters if you're setting
291 * a value that already exists.
292 * @param pruneHook callback to use on eviction (if it occurs).
294 void set(const TKey& key,
297 PruneHookCall pruneHook = nullptr) {
298 auto it = findInIndex(key);
299 if (it != index_.end()) {
300 it->pr.second = std::move(value);
302 lru_.erase(lru_.iterator_to(*it));
303 lru_.push_front(*it);
306 auto node = new Node(key, std::move(value));
307 index_.insert(*node);
308 lru_.push_front(*node);
310 // no evictions if maxSize_ is 0 i.e. unlimited capacity
311 if (maxSize_ > 0 && size() > maxSize_) {
312 prune(clearSize_, pruneHook);
318 * Get the number of elements in the dictionary
319 * @return the size of the dictionary
321 std::size_t size() const {
322 return index_.size();
326 * Typical empty function
327 * @return true if empty, false otherwise
330 return index_.empty();
333 void clear(PruneHookCall pruneHook = nullptr) {
334 prune(size(), pruneHook);
338 * Set the prune hook, which is the function invoked on the key and value
339 * on each eviction. Will throw If the pruneHook throws, unless the
340 * EvictingCacheMap object is being destroyed in which case it will
342 * @param pruneHook new callback to use on eviction.
343 * @param promote boolean flag indicating whether or not to move something
344 * to the front of an LRU.
345 * @return the iterator of the object (a std::pair of const TKey, TValue) or
346 * end() if it does not exist
348 void setPruneHook(PruneHookCall pruneHook) {
349 pruneHook_ = pruneHook;
354 * Prune the minimum of pruneSize and size() from the back of the LRU.
355 * Will throw if pruneHook throws.
356 * @param pruneSize minimum number of elements to prune
357 * @param pruneHook a custom pruneHook function
359 void prune(std::size_t pruneSize, PruneHookCall pruneHook = nullptr) {
360 // do not swallow exceptions for prunes not triggered from destructor
361 pruneWithFailSafeOption(pruneSize, pruneHook, false);
364 // Iterators and such
366 return iterator(lru_.begin());
369 return iterator(lru_.end());
371 const_iterator begin() const {
372 return const_iterator(lru_.begin());
374 const_iterator end() const {
375 return const_iterator(lru_.end());
378 const_iterator cbegin() const {
379 return const_iterator(lru_.cbegin());
381 const_iterator cend() const {
382 return const_iterator(lru_.cend());
385 reverse_iterator rbegin() {
386 return reverse_iterator(lru_.rbegin());
388 reverse_iterator rend() {
389 return reverse_iterator(lru_.rend());
392 const_reverse_iterator rbegin() const {
393 return const_reverse_iterator(lru_.rbegin());
395 const_reverse_iterator rend() const {
396 return const_reverse_iterator(lru_.rend());
399 const_reverse_iterator crbegin() const {
400 return const_reverse_iterator(lru_.crbegin());
402 const_reverse_iterator crend() const {
403 return const_reverse_iterator(lru_.crend());
408 : public boost::intrusive::unordered_set_base_hook<link_mode>,
409 public boost::intrusive::list_base_hook<link_mode> {
410 Node(const TKey& key, TValue&& value)
411 : pr(std::make_pair(key, std::move(value))) {
414 friend bool operator==(const Node& lhs, const Node& rhs) {
415 return lhs.pr.first == rhs.pr.first;
417 friend std::size_t hash_value(const Node& node) {
418 return THash()(node.pr.first);
423 std::size_t operator()(const Node& node) {
424 return THash()(node.pr.first);
426 std::size_t operator()(const TKey& key) {
431 struct KeyValueEqual {
432 bool operator()(const TKey& lhs, const Node& rhs) {
433 return lhs == rhs.pr.first;
435 bool operator()(const Node& lhs, const TKey& rhs) {
436 return lhs.pr.first == rhs;
441 * Get the iterator in in the index associated with a specific key. This is
442 * merely a search in the index and does not promote the object.
443 * @param key key to associate with value
444 * @return the NodeMap::iterator to the Node containing the object
445 * (a std::pair of const TKey, TValue) or index_.end() if it does not exist
447 typename NodeMap::iterator findInIndex(const TKey& key) {
448 return index_.find(key, KeyHasher(), KeyValueEqual());
451 typename NodeMap::const_iterator findInIndex(const TKey& key) const {
452 return index_.find(key, KeyHasher(), KeyValueEqual());
456 * Prune the minimum of pruneSize and size() from the back of the LRU.
457 * @param pruneSize minimum number of elements to prune
458 * @param pruneHook a custom pruneHook function
459 * @param failSafe true if exceptions are to ignored, false by default
461 void pruneWithFailSafeOption(std::size_t pruneSize,
462 PruneHookCall pruneHook, bool failSafe) {
463 auto& ph = (nullptr == pruneHook) ? pruneHook_ : pruneHook;
465 for (std::size_t i = 0; i < pruneSize && !lru_.empty(); i++) {
466 auto *node = &(*lru_.rbegin());
467 std::unique_ptr<Node> nptr(node);
469 lru_.erase(lru_.iterator_to(*node));
470 index_.erase(index_.iterator_to(*node));
473 ph(node->pr.first, std::move(node->pr.second));
483 static const std::size_t kMinNumIndexBuckets = 100;
484 PruneHookCall pruneHook_;
485 std::size_t nIndexBuckets_;
486 std::unique_ptr<typename NodeMap::bucket_type[]> indexBuckets_;
487 typename NodeMap::bucket_traits indexTraits_;
490 std::size_t maxSize_;
491 std::size_t clearSize_;
496 #endif /* FOLLY_EVICTINGHASHMAP_H_ */