2 * Copyright 2014-present 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.
23 #include <boost/intrusive/list.hpp>
24 #include <boost/intrusive/unordered_set.hpp>
25 #include <boost/iterator/iterator_adaptor.hpp>
26 #include <boost/utility.hpp>
28 #include <folly/portability/BitsFunctexcept.h>
33 * A general purpose LRU evicting cache. Designed to support constant time
34 * set/get operations. It maintains a doubly linked list of items that are
35 * threaded through an index (a hash map). The access ordered is maintained
36 * on the list by moving an element to the front of list on a get. New elements
37 * are added to the front of the list. The index size is set to half the
38 * capacity (setting capacity to 0 is a special case. see notes at the end of
39 * this section). So assuming uniform distribution of keys, set/get are both
40 * constant time operations.
42 * On reaching capacity limit, clearSize_ LRU items are evicted at a time. If
43 * a callback is specified with setPruneHook, it is invoked for each eviction.
45 * This is NOT a thread-safe implementation.
47 * Configurability: capacity of the cache, number of items to evict, eviction
48 * callback and the hasher to hash the keys can all be supplied by the caller.
50 * If at a given state, N1 - N6 are the nodes in MRU to LRU order and hashing
51 * to index keys as {(N1,N5)->H1, (N4,N5,N5)->H2, N3->Hi}, the datastructure
52 * layout is as below. N1 .. N6 is a list threaded through the hash.
53 * Assuming, each the number of nodes hashed to each index key is bounded, the
54 * following operations run in constant time.
55 * i) get computes the index key, walks the list of elements hashed to
56 * the key and moves it to the front of the list, if found.
57 * ii) set inserts a new node into the list and places the same node on to the
58 * list of elements hashing to the corresponding index key.
59 * ii) prune deletes nodes from the end of the list as well from the index.
61 * +----+ +----+ +----+
62 * | H1 | <-> | N1 | <-> | N5 |
63 * +----+ +----+ +----+
71 * +----+ +----+ +----+ +----+
72 * | H2 | <-> | N4 | <-> | N2 | <-> | N6 |
73 * +----+ +----+ +----+ +----+
84 * N.B 1 : Changing the capacity with setMaxSize does not change the index size
85 * and it could end up in too many elements indexed to the same slot in index.
86 * The set/get performance will get worse in this case. So it is best to avoid
89 * N.B 2 : Setting capacity to 0, using setMaxSize or initialization, turns off
90 * evictions based on sizeof the cache making it an INFINITE size cache
91 * unless evictions of LRU items are triggered by calling prune() by clients
92 * (using their own eviction criteria).
94 template <class TKey, class TValue, class THash = std::hash<TKey>>
95 class EvictingCacheMap {
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) { }
151 EvictingCacheMap(const EvictingCacheMap&) = delete;
152 EvictingCacheMap& operator=(const EvictingCacheMap&) = delete;
153 EvictingCacheMap(EvictingCacheMap&&) = default;
154 EvictingCacheMap& operator=(EvictingCacheMap&&) = default;
156 ~EvictingCacheMap() {
157 setPruneHook(nullptr);
158 // ignore any potential exceptions from pruneHook_
159 pruneWithFailSafeOption(size(), nullptr, true);
163 * Adjust the max size of EvictingCacheMap. Note that this does not update
164 * nIndexBuckets_ accordingly. This API can cause performance to get very
165 * bad, e.g., the nIndexBuckets_ is still 100 after maxSize is updated to 1M.
167 * Calling this function with an arugment of 0 removes the limit on the cache
168 * size and elements are not evicted unless clients explictly call prune.
170 * If you intend to resize dynamically using this, then picking an index size
171 * that works well and initializing with corresponding maxSize is the only
174 * @param maxSize new maximum size of the cache map.
175 * @param pruneHook callback to use on eviction.
177 void setMaxSize(size_t maxSize, PruneHookCall pruneHook = nullptr) {
178 if (maxSize != 0 && maxSize < size()) {
179 // Prune the excess elements with our new constraints.
180 prune(std::max(size() - maxSize, clearSize_), pruneHook);
185 size_t getMaxSize() const {
189 void setClearSize(size_t clearSize) {
190 clearSize_ = clearSize;
194 * Check for existence of a specific key in the map. This operation has
195 * no effect on LRU order.
196 * @param key key to search for
197 * @return true if exists, false otherwise
199 bool exists(const TKey& key) const {
200 return findInIndex(key) != index_.end();
204 * Get the value associated with a specific key. This function always
205 * promotes a found value to the head of the LRU.
206 * @param key key associated with the value
207 * @return the value if it exists
208 * @throw std::out_of_range exception of the key does not exist
210 TValue& get(const TKey& key) {
213 std::__throw_out_of_range("Key does not exist");
219 * Get the iterator associated with a specific key. This function always
220 * promotes a found value to the head of the LRU.
221 * @param key key to associate with value
222 * @return the iterator of the object (a std::pair of const TKey, TValue) or
223 * end() if it does not exist
225 iterator find(const TKey& key) {
226 auto it = findInIndex(key);
227 if (it == index_.end()) {
230 lru_.erase(lru_.iterator_to(*it));
231 lru_.push_front(*it);
232 return iterator(lru_.iterator_to(*it));
236 * Get the value associated with a specific key. This function never
237 * promotes a found value to the head of the LRU.
238 * @param key key associated with the value
239 * @return the value if it exists
240 * @throw std::out_of_range exception of the key does not exist
242 const TValue& getWithoutPromotion(const TKey& key) const {
243 auto it = findWithoutPromotion(key);
245 std::__throw_out_of_range("Key does not exist");
250 TValue& getWithoutPromotion(const TKey& key) {
251 auto const& cThis = *this;
252 return const_cast<TValue&>(cThis.getWithoutPromotion(key));
256 * Get the iterator associated with a specific key. This function never
257 * promotes a found value to the head of the LRU.
258 * @param key key to associate with value
259 * @return the iterator of the object (a std::pair of const TKey, TValue) or
260 * end() if it does not exist
262 const_iterator findWithoutPromotion(const TKey& key) const {
263 auto it = findInIndex(key);
264 return (it == index_.end()) ? end() : const_iterator(lru_.iterator_to(*it));
267 iterator findWithoutPromotion(const TKey& key) {
268 auto it = findInIndex(key);
269 return (it == index_.end()) ? end() : iterator(lru_.iterator_to(*it));
273 * Erase the key-value pair associated with key if it exists.
274 * @param key key associated with the value
275 * @return true if the key existed and was erased, else false
277 bool erase(const TKey& key) {
278 auto it = findInIndex(key);
279 if (it == index_.end()) {
283 std::unique_ptr<Node> nptr(node);
284 lru_.erase(lru_.iterator_to(*node));
290 * Set a key-value pair in the dictionary
291 * @param key key to associate with value
292 * @param value value to associate with the key
293 * @param promote boolean flag indicating whether or not to move something
294 * to the front of an LRU. This only really matters if you're setting
295 * a value that already exists.
296 * @param pruneHook callback to use on eviction (if it occurs).
298 void set(const TKey& key,
301 PruneHookCall pruneHook = nullptr) {
302 auto it = findInIndex(key);
303 if (it != index_.end()) {
304 it->pr.second = std::move(value);
306 lru_.erase(lru_.iterator_to(*it));
307 lru_.push_front(*it);
310 auto node = new Node(key, std::move(value));
311 index_.insert(*node);
312 lru_.push_front(*node);
314 // no evictions if maxSize_ is 0 i.e. unlimited capacity
315 if (maxSize_ > 0 && size() > maxSize_) {
316 prune(clearSize_, pruneHook);
322 * Get the number of elements in the dictionary
323 * @return the size of the dictionary
325 std::size_t size() const {
326 return index_.size();
330 * Typical empty function
331 * @return true if empty, false otherwise
334 return index_.empty();
337 void clear(PruneHookCall pruneHook = nullptr) {
338 prune(size(), pruneHook);
342 * Set the prune hook, which is the function invoked on the key and value
343 * on each eviction. Will throw If the pruneHook throws, unless the
344 * EvictingCacheMap object is being destroyed in which case it will
346 * @param pruneHook new callback to use on eviction.
347 * @param promote boolean flag indicating whether or not to move something
348 * to the front of an LRU.
349 * @return the iterator of the object (a std::pair of const TKey, TValue) or
350 * end() if it does not exist
352 void setPruneHook(PruneHookCall pruneHook) {
353 pruneHook_ = pruneHook;
358 * Prune the minimum of pruneSize and size() from the back of the LRU.
359 * Will throw if pruneHook throws.
360 * @param pruneSize minimum number of elements to prune
361 * @param pruneHook a custom pruneHook function
363 void prune(std::size_t pruneSize, PruneHookCall pruneHook = nullptr) {
364 // do not swallow exceptions for prunes not triggered from destructor
365 pruneWithFailSafeOption(pruneSize, pruneHook, false);
368 // Iterators and such
370 return iterator(lru_.begin());
373 return iterator(lru_.end());
375 const_iterator begin() const {
376 return const_iterator(lru_.begin());
378 const_iterator end() const {
379 return const_iterator(lru_.end());
382 const_iterator cbegin() const {
383 return const_iterator(lru_.cbegin());
385 const_iterator cend() const {
386 return const_iterator(lru_.cend());
389 reverse_iterator rbegin() {
390 return reverse_iterator(lru_.rbegin());
392 reverse_iterator rend() {
393 return reverse_iterator(lru_.rend());
396 const_reverse_iterator rbegin() const {
397 return const_reverse_iterator(lru_.rbegin());
399 const_reverse_iterator rend() const {
400 return const_reverse_iterator(lru_.rend());
403 const_reverse_iterator crbegin() const {
404 return const_reverse_iterator(lru_.crbegin());
406 const_reverse_iterator crend() const {
407 return const_reverse_iterator(lru_.crend());
412 : public boost::intrusive::unordered_set_base_hook<link_mode>,
413 public boost::intrusive::list_base_hook<link_mode> {
414 Node(const TKey& key, TValue&& value)
415 : pr(std::make_pair(key, std::move(value))) {
418 friend bool operator==(const Node& lhs, const Node& rhs) {
419 return lhs.pr.first == rhs.pr.first;
421 friend std::size_t hash_value(const Node& node) {
422 return THash()(node.pr.first);
427 std::size_t operator()(const Node& node) {
428 return THash()(node.pr.first);
430 std::size_t operator()(const TKey& key) {
435 struct KeyValueEqual {
436 bool operator()(const TKey& lhs, const Node& rhs) {
437 return lhs == rhs.pr.first;
439 bool operator()(const Node& lhs, const TKey& rhs) {
440 return lhs.pr.first == rhs;
445 * Get the iterator in in the index associated with a specific key. This is
446 * merely a search in the index and does not promote the object.
447 * @param key key to associate with value
448 * @return the NodeMap::iterator to the Node containing the object
449 * (a std::pair of const TKey, TValue) or index_.end() if it does not exist
451 typename NodeMap::iterator findInIndex(const TKey& key) {
452 return index_.find(key, KeyHasher(), KeyValueEqual());
455 typename NodeMap::const_iterator findInIndex(const TKey& key) const {
456 return index_.find(key, KeyHasher(), KeyValueEqual());
460 * Prune the minimum of pruneSize and size() from the back of the LRU.
461 * @param pruneSize minimum number of elements to prune
462 * @param pruneHook a custom pruneHook function
463 * @param failSafe true if exceptions are to ignored, false by default
465 void pruneWithFailSafeOption(std::size_t pruneSize,
466 PruneHookCall pruneHook, bool failSafe) {
467 auto& ph = (nullptr == pruneHook) ? pruneHook_ : pruneHook;
469 for (std::size_t i = 0; i < pruneSize && !lru_.empty(); i++) {
470 auto *node = &(*lru_.rbegin());
471 std::unique_ptr<Node> nptr(node);
473 lru_.erase(lru_.iterator_to(*node));
474 index_.erase(index_.iterator_to(*node));
477 ph(node->pr.first, std::move(node->pr.second));
487 static const std::size_t kMinNumIndexBuckets = 100;
488 PruneHookCall pruneHook_;
489 std::size_t nIndexBuckets_;
490 std::unique_ptr<typename NodeMap::bucket_type[]> indexBuckets_;
491 typename NodeMap::bucket_traits indexTraits_;
494 std::size_t maxSize_;
495 std::size_t clearSize_;