2 * Copyright 2014 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 void setMaxSize(size_t maxSize) {
171 if (maxSize != 0 && maxSize < size()) {
172 // Prune the excess elements with our new constraints.
173 prune(std::max(size() - maxSize, clearSize_));
178 size_t getMaxSize() const {
182 void setClearSize(size_t clearSize) {
183 clearSize_ = clearSize;
187 * Check for existence of a specific key in the map. This operation has
188 * no effect on LRU order.
189 * @param key key to search for
190 * @return true if exists, false otherwise
192 bool exists(const TKey& key) const {
193 return findInIndex(key) != index_.end();
197 * Get the value associated with a specific key. This function always
198 * promotes a found value to the head of the LRU.
199 * @param key key associated with the value
200 * @return the value if it exists
201 * @throw std::out_of_range exception of the key does not exist
203 TValue& get(const TKey& key) {
206 throw std::out_of_range("Key does not exist");
212 * Get the iterator associated with a specific key. This function always
213 * promotes a found value to the head of the LRU.
214 * @param key key to associate with value
215 * @return the iterator of the object (a std::pair of const TKey, TValue) or
216 * end() if it does not exist
218 iterator find(const TKey& key) {
219 auto it = findInIndex(key);
220 if (it == index_.end()) {
223 lru_.erase(lru_.iterator_to(*it));
224 lru_.push_front(*it);
225 return iterator(lru_.iterator_to(*it));
229 * Get the value associated with a specific key. This function never
230 * promotes a found value to the head of the LRU.
231 * @param key key associated with the value
232 * @return the value if it exists
233 * @throw std::out_of_range exception of the key does not exist
235 const TValue& getWithoutPromotion(const TKey& key) const {
236 auto it = findWithoutPromotion(key);
238 throw std::out_of_range("Key does not exist");
243 TValue& getWithoutPromotion(const TKey& key) {
244 auto const& cThis = *this;
245 return const_cast<TValue&>(cThis.getWithoutPromotion(key));
249 * Get the iterator associated with a specific key. This function never
250 * promotes a found value to the head of the LRU.
251 * @param key key to associate with value
252 * @return the iterator of the object (a std::pair of const TKey, TValue) or
253 * end() if it does not exist
255 const_iterator findWithoutPromotion(const TKey& key) const {
256 auto it = findInIndex(key);
257 return (it == index_.end()) ? end() : const_iterator(lru_.iterator_to(*it));
260 iterator findWithoutPromotion(const TKey& key) {
261 auto it = findInIndex(key);
262 return (it == index_.end()) ? end() : iterator(lru_.iterator_to(*it));
266 * Erase the key-value pair associated with key if it exists.
267 * @param key key associated with the value
268 * @return true if the key existed and was erased, else false
270 bool erase(const TKey& key) {
271 auto it = findInIndex(key);
272 if (it == index_.end()) {
276 std::unique_ptr<Node> nptr(node);
277 lru_.erase(lru_.iterator_to(*node));
283 * Set a key-value pair in the dictionary
284 * @param key key to associate with value
285 * @param value value to associate with the key
286 * @param promote boolean flag indicating whether or not to move something
287 * to the front of an LRU. This only really matters if you're setting
288 * a value that already exists.
290 void set(const TKey& key, TValue value, bool promote = true) {
291 auto it = findInIndex(key);
292 if (it != index_.end()) {
293 it->pr.second = std::move(value);
295 lru_.erase(lru_.iterator_to(*it));
296 lru_.push_front(*it);
299 auto node = new Node(key, std::move(value));
300 index_.insert(*node);
301 lru_.push_front(*node);
303 // no evictions if maxSize_ is 0 i.e. unlimited capacity
304 if (maxSize_ > 0 && size() > maxSize_) {
311 * Get the number of elements in the dictionary
312 * @return the size of the dictionary
314 std::size_t size() const {
315 return index_.size();
319 * Typical empty function
320 * @return true if empty, false otherwise
323 return index_.empty();
331 * Set the prune hook, which is the function invoked on the key and value
332 * on each eviction. Will throw If the pruneHook throws, unless the
333 * EvictingCacheMap object is being destroyed in which case it will
335 * @param pruneHook new callback to use on eviction.
336 * @param promote boolean flag indicating whether or not to move something
337 * to the front of an LRU.
338 * @return the iterator of the object (a std::pair of const TKey, TValue) or
339 * end() if it does not exist
341 void setPruneHook(PruneHookCall pruneHook) {
342 pruneHook_ = pruneHook;
347 * Prune the minimum of pruneSize and size() from the back of the LRU.
348 * Will throw if pruneHook throws.
349 * @param pruneSize minimum number of elements to prune
350 * @param pruneHook a custom pruneHook function
352 void prune(std::size_t pruneSize, PruneHookCall pruneHook = nullptr) {
353 // do not swallow exceptions for prunes not triggered from destructor
354 pruneWithFailSafeOption(pruneSize, pruneHook, false);
357 // Iterators and such
359 return iterator(lru_.begin());
362 return iterator(lru_.end());
364 const_iterator begin() const {
365 return const_iterator(lru_.begin());
367 const_iterator end() const {
368 return const_iterator(lru_.end());
371 const_iterator cbegin() const {
372 return const_iterator(lru_.cbegin());
374 const_iterator cend() const {
375 return const_iterator(lru_.cend());
378 reverse_iterator rbegin() {
379 return reverse_iterator(lru_.rbegin());
381 reverse_iterator rend() {
382 return reverse_iterator(lru_.rend());
385 const_reverse_iterator rbegin() const {
386 return const_reverse_iterator(lru_.rbegin());
388 const_reverse_iterator rend() const {
389 return const_reverse_iterator(lru_.rend());
392 const_reverse_iterator crbegin() const {
393 return const_reverse_iterator(lru_.crbegin());
395 const_reverse_iterator crend() const {
396 return const_reverse_iterator(lru_.crend());
401 : public boost::intrusive::unordered_set_base_hook<link_mode>,
402 public boost::intrusive::list_base_hook<link_mode> {
403 Node(const TKey& key, TValue&& value)
404 : pr(std::make_pair(key, std::move(value))) {
407 friend bool operator==(const Node& lhs, const Node& rhs) {
408 return lhs.pr.first == rhs.pr.first;
410 friend std::size_t hash_value(const Node& node) {
411 return THash()(node.pr.first);
416 std::size_t operator()(const Node& node) {
417 return THash()(node.pr.first);
419 std::size_t operator()(const TKey& key) {
424 struct KeyValueEqual {
425 bool operator()(const TKey& lhs, const Node& rhs) {
426 return lhs == rhs.pr.first;
428 bool operator()(const Node& lhs, const TKey& rhs) {
429 return lhs.pr.first == rhs;
434 * Get the iterator in in the index associated with a specific key. This is
435 * merely a search in the index and does not promote the object.
436 * @param key key to associate with value
437 * @return the NodeMap::iterator to the Node containing the object
438 * (a std::pair of const TKey, TValue) or index_.end() if it does not exist
440 typename NodeMap::iterator findInIndex(const TKey& key) {
441 return index_.find(key, KeyHasher(), KeyValueEqual());
444 typename NodeMap::const_iterator findInIndex(const TKey& key) const {
445 return index_.find(key, KeyHasher(), KeyValueEqual());
449 * Prune the minimum of pruneSize and size() from the back of the LRU.
450 * @param pruneSize minimum number of elements to prune
451 * @param pruneHook a custom pruneHook function
452 * @param failSafe true if exceptions are to ignored, false by default
454 void pruneWithFailSafeOption(std::size_t pruneSize,
455 PruneHookCall pruneHook, bool failSafe) {
456 auto& ph = (nullptr == pruneHook) ? pruneHook_ : pruneHook;
458 for (std::size_t i = 0; i < pruneSize && !lru_.empty(); i++) {
459 auto *node = &(*lru_.rbegin());
460 std::unique_ptr<Node> nptr(node);
462 lru_.erase(lru_.iterator_to(*node));
463 index_.erase(index_.iterator_to(*node));
466 ph(node->pr.first, std::move(node->pr.second));
476 static const std::size_t kMinNumIndexBuckets = 100;
477 PruneHookCall pruneHook_;
478 std::size_t nIndexBuckets_;
479 std::unique_ptr<typename NodeMap::bucket_type[]> indexBuckets_;
480 typename NodeMap::bucket_traits indexTraits_;
483 std::size_t maxSize_;
484 std::size_t clearSize_;
489 #endif /* FOLLY_EVICTINGHASHMAP_H_ */