2 * Copyright 2017 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/utility.hpp>
24 #include <boost/intrusive/list.hpp>
25 #include <boost/intrusive/unordered_set.hpp>
26 #include <boost/iterator/iterator_adaptor.hpp>
27 #include <folly/portability/BitsFunctexcept.h>
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 {
96 // typedefs for brevity
98 typedef boost::intrusive::link_mode<boost::intrusive::safe_link> link_mode;
99 typedef boost::intrusive::unordered_set<Node> NodeMap;
100 typedef boost::intrusive::list<Node> NodeList;
101 typedef std::pair<const TKey, TValue> TPair;
104 typedef std::function<void(TKey, TValue&&)> PruneHookCall;
106 // iterator base : returns TPair on dereference
107 template <typename Value, typename TIterator>
109 : public boost::iterator_adaptor<iterator_base<Value, TIterator>,
112 boost::bidirectional_traversal_tag > {
116 explicit iterator_base(TIterator it)
117 : iterator_base::iterator_adaptor_(it) {
119 Value& dereference() const {
120 return this->base_reference()->pr;
125 typedef iterator_base<
126 TPair, typename NodeList::iterator> iterator;
127 typedef iterator_base<
128 const TPair, typename NodeList::const_iterator> const_iterator;
129 typedef iterator_base<
130 TPair, typename NodeList::reverse_iterator> reverse_iterator;
131 typedef iterator_base<
133 typename NodeList::const_reverse_iterator> const_reverse_iterator;
136 * Construct a EvictingCacheMap
137 * @param maxSize maximum size of the cache map. Once the map size exceeds
138 * maxSize, the map will begin to evict.
139 * @param clearSize the number of elements to clear at a time when the
140 * eviction size is reached.
142 explicit EvictingCacheMap(std::size_t maxSize, std::size_t clearSize = 1)
143 : nIndexBuckets_(std::max(maxSize / 2, std::size_t(kMinNumIndexBuckets))),
144 indexBuckets_(new typename NodeMap::bucket_type[nIndexBuckets_]),
145 indexTraits_(indexBuckets_.get(), nIndexBuckets_),
146 index_(indexTraits_),
148 clearSize_(clearSize) { }
150 EvictingCacheMap(const EvictingCacheMap&) = delete;
151 EvictingCacheMap& operator=(const EvictingCacheMap&) = delete;
152 EvictingCacheMap(EvictingCacheMap&&) = default;
153 EvictingCacheMap& operator=(EvictingCacheMap&&) = default;
155 ~EvictingCacheMap() {
156 setPruneHook(nullptr);
157 // ignore any potential exceptions from pruneHook_
158 pruneWithFailSafeOption(size(), nullptr, true);
162 * Adjust the max size of EvictingCacheMap. Note that this does not update
163 * nIndexBuckets_ accordingly. This API can cause performance to get very
164 * bad, e.g., the nIndexBuckets_ is still 100 after maxSize is updated to 1M.
166 * Calling this function with an arugment of 0 removes the limit on the cache
167 * size and elements are not evicted unless clients explictly call prune.
169 * If you intend to resize dynamically using this, then picking an index size
170 * that works well and initializing with corresponding maxSize is the only
173 * @param maxSize new maximum size of the cache map.
174 * @param pruneHook callback to use on eviction.
176 void setMaxSize(size_t maxSize, PruneHookCall pruneHook = nullptr) {
177 if (maxSize != 0 && maxSize < size()) {
178 // Prune the excess elements with our new constraints.
179 prune(std::max(size() - maxSize, clearSize_), pruneHook);
184 size_t getMaxSize() const {
188 void setClearSize(size_t clearSize) {
189 clearSize_ = clearSize;
193 * Check for existence of a specific key in the map. This operation has
194 * no effect on LRU order.
195 * @param key key to search for
196 * @return true if exists, false otherwise
198 bool exists(const TKey& key) const {
199 return findInIndex(key) != index_.end();
203 * Get the value associated with a specific key. This function always
204 * promotes a found value to the head of the LRU.
205 * @param key key associated with the value
206 * @return the value if it exists
207 * @throw std::out_of_range exception of the key does not exist
209 TValue& get(const TKey& key) {
212 std::__throw_out_of_range("Key does not exist");
218 * Get the iterator associated with a specific key. This function always
219 * promotes a found value to the head of the LRU.
220 * @param key key to associate with value
221 * @return the iterator of the object (a std::pair of const TKey, TValue) or
222 * end() if it does not exist
224 iterator find(const TKey& key) {
225 auto it = findInIndex(key);
226 if (it == index_.end()) {
229 lru_.erase(lru_.iterator_to(*it));
230 lru_.push_front(*it);
231 return iterator(lru_.iterator_to(*it));
235 * Get the value associated with a specific key. This function never
236 * promotes a found value to the head of the LRU.
237 * @param key key associated with the value
238 * @return the value if it exists
239 * @throw std::out_of_range exception of the key does not exist
241 const TValue& getWithoutPromotion(const TKey& key) const {
242 auto it = findWithoutPromotion(key);
244 std::__throw_out_of_range("Key does not exist");
249 TValue& getWithoutPromotion(const TKey& key) {
250 auto const& cThis = *this;
251 return const_cast<TValue&>(cThis.getWithoutPromotion(key));
255 * Get the iterator associated with a specific key. This function never
256 * promotes a found value to the head of the LRU.
257 * @param key key to associate with value
258 * @return the iterator of the object (a std::pair of const TKey, TValue) or
259 * end() if it does not exist
261 const_iterator findWithoutPromotion(const TKey& key) const {
262 auto it = findInIndex(key);
263 return (it == index_.end()) ? end() : const_iterator(lru_.iterator_to(*it));
266 iterator findWithoutPromotion(const TKey& key) {
267 auto it = findInIndex(key);
268 return (it == index_.end()) ? end() : iterator(lru_.iterator_to(*it));
272 * Erase the key-value pair associated with key if it exists.
273 * @param key key associated with the value
274 * @return true if the key existed and was erased, else false
276 bool erase(const TKey& key) {
277 auto it = findInIndex(key);
278 if (it == index_.end()) {
282 std::unique_ptr<Node> nptr(node);
283 lru_.erase(lru_.iterator_to(*node));
289 * Set a key-value pair in the dictionary
290 * @param key key to associate with value
291 * @param value value to associate with the key
292 * @param promote boolean flag indicating whether or not to move something
293 * to the front of an LRU. This only really matters if you're setting
294 * a value that already exists.
295 * @param pruneHook callback to use on eviction (if it occurs).
297 void set(const TKey& key,
300 PruneHookCall pruneHook = nullptr) {
301 auto it = findInIndex(key);
302 if (it != index_.end()) {
303 it->pr.second = std::move(value);
305 lru_.erase(lru_.iterator_to(*it));
306 lru_.push_front(*it);
309 auto node = new Node(key, std::move(value));
310 index_.insert(*node);
311 lru_.push_front(*node);
313 // no evictions if maxSize_ is 0 i.e. unlimited capacity
314 if (maxSize_ > 0 && size() > maxSize_) {
315 prune(clearSize_, pruneHook);
321 * Get the number of elements in the dictionary
322 * @return the size of the dictionary
324 std::size_t size() const {
325 return index_.size();
329 * Typical empty function
330 * @return true if empty, false otherwise
333 return index_.empty();
336 void clear(PruneHookCall pruneHook = nullptr) {
337 prune(size(), pruneHook);
341 * Set the prune hook, which is the function invoked on the key and value
342 * on each eviction. Will throw If the pruneHook throws, unless the
343 * EvictingCacheMap object is being destroyed in which case it will
345 * @param pruneHook new callback to use on eviction.
346 * @param promote boolean flag indicating whether or not to move something
347 * to the front of an LRU.
348 * @return the iterator of the object (a std::pair of const TKey, TValue) or
349 * end() if it does not exist
351 void setPruneHook(PruneHookCall pruneHook) {
352 pruneHook_ = pruneHook;
357 * Prune the minimum of pruneSize and size() from the back of the LRU.
358 * Will throw if pruneHook throws.
359 * @param pruneSize minimum number of elements to prune
360 * @param pruneHook a custom pruneHook function
362 void prune(std::size_t pruneSize, PruneHookCall pruneHook = nullptr) {
363 // do not swallow exceptions for prunes not triggered from destructor
364 pruneWithFailSafeOption(pruneSize, pruneHook, false);
367 // Iterators and such
369 return iterator(lru_.begin());
372 return iterator(lru_.end());
374 const_iterator begin() const {
375 return const_iterator(lru_.begin());
377 const_iterator end() const {
378 return const_iterator(lru_.end());
381 const_iterator cbegin() const {
382 return const_iterator(lru_.cbegin());
384 const_iterator cend() const {
385 return const_iterator(lru_.cend());
388 reverse_iterator rbegin() {
389 return reverse_iterator(lru_.rbegin());
391 reverse_iterator rend() {
392 return reverse_iterator(lru_.rend());
395 const_reverse_iterator rbegin() const {
396 return const_reverse_iterator(lru_.rbegin());
398 const_reverse_iterator rend() const {
399 return const_reverse_iterator(lru_.rend());
402 const_reverse_iterator crbegin() const {
403 return const_reverse_iterator(lru_.crbegin());
405 const_reverse_iterator crend() const {
406 return const_reverse_iterator(lru_.crend());
411 : public boost::intrusive::unordered_set_base_hook<link_mode>,
412 public boost::intrusive::list_base_hook<link_mode> {
413 Node(const TKey& key, TValue&& value)
414 : pr(std::make_pair(key, std::move(value))) {
417 friend bool operator==(const Node& lhs, const Node& rhs) {
418 return lhs.pr.first == rhs.pr.first;
420 friend std::size_t hash_value(const Node& node) {
421 return THash()(node.pr.first);
426 std::size_t operator()(const Node& node) {
427 return THash()(node.pr.first);
429 std::size_t operator()(const TKey& key) {
434 struct KeyValueEqual {
435 bool operator()(const TKey& lhs, const Node& rhs) {
436 return lhs == rhs.pr.first;
438 bool operator()(const Node& lhs, const TKey& rhs) {
439 return lhs.pr.first == rhs;
444 * Get the iterator in in the index associated with a specific key. This is
445 * merely a search in the index and does not promote the object.
446 * @param key key to associate with value
447 * @return the NodeMap::iterator to the Node containing the object
448 * (a std::pair of const TKey, TValue) or index_.end() if it does not exist
450 typename NodeMap::iterator findInIndex(const TKey& key) {
451 return index_.find(key, KeyHasher(), KeyValueEqual());
454 typename NodeMap::const_iterator findInIndex(const TKey& key) const {
455 return index_.find(key, KeyHasher(), KeyValueEqual());
459 * Prune the minimum of pruneSize and size() from the back of the LRU.
460 * @param pruneSize minimum number of elements to prune
461 * @param pruneHook a custom pruneHook function
462 * @param failSafe true if exceptions are to ignored, false by default
464 void pruneWithFailSafeOption(std::size_t pruneSize,
465 PruneHookCall pruneHook, bool failSafe) {
466 auto& ph = (nullptr == pruneHook) ? pruneHook_ : pruneHook;
468 for (std::size_t i = 0; i < pruneSize && !lru_.empty(); i++) {
469 auto *node = &(*lru_.rbegin());
470 std::unique_ptr<Node> nptr(node);
472 lru_.erase(lru_.iterator_to(*node));
473 index_.erase(index_.iterator_to(*node));
476 ph(node->pr.first, std::move(node->pr.second));
486 static const std::size_t kMinNumIndexBuckets = 100;
487 PruneHookCall pruneHook_;
488 std::size_t nIndexBuckets_;
489 std::unique_ptr<typename NodeMap::bucket_type[]> indexBuckets_;
490 typename NodeMap::bucket_traits indexTraits_;
493 std::size_t maxSize_;
494 std::size_t clearSize_;