2 * Copyright 2016 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>
31 * A general purpose LRU evicting cache. Designed to support constant time
32 * set/get operations. It maintains a doubly linked list of items that are
33 * threaded through an index (a hash map). The access ordered is maintained
34 * on the list by moving an element to the front of list on a get. New elements
35 * are added to the front of the list. The index size is set to half the
36 * capacity (setting capacity to 0 is a special case. see notes at the end of
37 * this section). So assuming uniform distribution of keys, set/get are both
38 * constant time operations.
40 * On reaching capacity limit, clearSize_ LRU items are evicted at a time. If
41 * a callback is specified with setPruneHook, it is invoked for each eviction.
43 * This is NOT a thread-safe implementation.
45 * Configurability: capacity of the cache, number of items to evict, eviction
46 * callback and the hasher to hash the keys can all be supplied by the caller.
48 * If at a given state, N1 - N6 are the nodes in MRU to LRU order and hashing
49 * to index keys as {(N1,N5)->H1, (N4,N5,N5)->H2, N3->Hi}, the datastructure
50 * layout is as below. N1 .. N6 is a list threaded through the hash.
51 * Assuming, each the number of nodes hashed to each index key is bounded, the
52 * following operations run in constant time.
53 * i) get computes the index key, walks the list of elements hashed to
54 * the key and moves it to the front of the list, if found.
55 * ii) set inserts a new node into the list and places the same node on to the
56 * list of elements hashing to the corresponding index key.
57 * ii) prune deletes nodes from the end of the list as well from the index.
59 * +----+ +----+ +----+
60 * | H1 | <-> | N1 | <-> | N5 |
61 * +----+ +----+ +----+
69 * +----+ +----+ +----+ +----+
70 * | H2 | <-> | N4 | <-> | N2 | <-> | N6 |
71 * +----+ +----+ +----+ +----+
82 * N.B 1 : Changing the capacity with setMaxSize does not change the index size
83 * and it could end up in too many elements indexed to the same slot in index.
84 * The set/get performance will get worse in this case. So it is best to avoid
87 * N.B 2 : Setting capacity to 0, using setMaxSize or initialization, turns off
88 * evictions based on sizeof the cache making it an INFINITE size cache
89 * unless evictions of LRU items are triggered by calling prune() by clients
90 * (using their own eviction criteria).
92 template <class TKey, class TValue, class THash = std::hash<TKey> >
93 class EvictingCacheMap : private boost::noncopyable {
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) { }
151 ~EvictingCacheMap() {
152 setPruneHook(nullptr);
153 // ignore any potential exceptions from pruneHook_
154 pruneWithFailSafeOption(size(), nullptr, true);
158 * Adjust the max size of EvictingCacheMap. Note that this does not update
159 * nIndexBuckets_ accordingly. This API can cause performance to get very
160 * bad, e.g., the nIndexBuckets_ is still 100 after maxSize is updated to 1M.
162 * Calling this function with an arugment of 0 removes the limit on the cache
163 * size and elements are not evicted unless clients explictly call prune.
165 * If you intend to resize dynamically using this, then picking an index size
166 * that works well and initializing with corresponding maxSize is the only
169 * @param maxSize new maximum size of the cache map.
170 * @param pruneHook callback to use on eviction.
172 void setMaxSize(size_t maxSize, PruneHookCall pruneHook = nullptr) {
173 if (maxSize != 0 && maxSize < size()) {
174 // Prune the excess elements with our new constraints.
175 prune(std::max(size() - maxSize, clearSize_), pruneHook);
180 size_t getMaxSize() const {
184 void setClearSize(size_t clearSize) {
185 clearSize_ = clearSize;
189 * Check for existence of a specific key in the map. This operation has
190 * no effect on LRU order.
191 * @param key key to search for
192 * @return true if exists, false otherwise
194 bool exists(const TKey& key) const {
195 return findInIndex(key) != index_.end();
199 * Get the value associated with a specific key. This function always
200 * promotes a found value to the head of the LRU.
201 * @param key key associated with the value
202 * @return the value if it exists
203 * @throw std::out_of_range exception of the key does not exist
205 TValue& get(const TKey& key) {
208 throw std::out_of_range("Key does not exist");
214 * Get the iterator associated with a specific key. This function always
215 * promotes a found value to the head of the LRU.
216 * @param key key to associate with value
217 * @return the iterator of the object (a std::pair of const TKey, TValue) or
218 * end() if it does not exist
220 iterator find(const TKey& key) {
221 auto it = findInIndex(key);
222 if (it == index_.end()) {
225 lru_.erase(lru_.iterator_to(*it));
226 lru_.push_front(*it);
227 return iterator(lru_.iterator_to(*it));
231 * Get the value associated with a specific key. This function never
232 * promotes a found value to the head of the LRU.
233 * @param key key associated with the value
234 * @return the value if it exists
235 * @throw std::out_of_range exception of the key does not exist
237 const TValue& getWithoutPromotion(const TKey& key) const {
238 auto it = findWithoutPromotion(key);
240 throw std::out_of_range("Key does not exist");
245 TValue& getWithoutPromotion(const TKey& key) {
246 auto const& cThis = *this;
247 return const_cast<TValue&>(cThis.getWithoutPromotion(key));
251 * Get the iterator associated with a specific key. This function never
252 * promotes a found value to the head of the LRU.
253 * @param key key to associate with value
254 * @return the iterator of the object (a std::pair of const TKey, TValue) or
255 * end() if it does not exist
257 const_iterator findWithoutPromotion(const TKey& key) const {
258 auto it = findInIndex(key);
259 return (it == index_.end()) ? end() : const_iterator(lru_.iterator_to(*it));
262 iterator findWithoutPromotion(const TKey& key) {
263 auto it = findInIndex(key);
264 return (it == index_.end()) ? end() : iterator(lru_.iterator_to(*it));
268 * Erase the key-value pair associated with key if it exists.
269 * @param key key associated with the value
270 * @return true if the key existed and was erased, else false
272 bool erase(const TKey& key) {
273 auto it = findInIndex(key);
274 if (it == index_.end()) {
278 std::unique_ptr<Node> nptr(node);
279 lru_.erase(lru_.iterator_to(*node));
285 * Set a key-value pair in the dictionary
286 * @param key key to associate with value
287 * @param value value to associate with the key
288 * @param promote boolean flag indicating whether or not to move something
289 * to the front of an LRU. This only really matters if you're setting
290 * a value that already exists.
291 * @param pruneHook callback to use on eviction (if it occurs).
293 void set(const TKey& key,
296 PruneHookCall pruneHook = nullptr) {
297 auto it = findInIndex(key);
298 if (it != index_.end()) {
299 it->pr.second = std::move(value);
301 lru_.erase(lru_.iterator_to(*it));
302 lru_.push_front(*it);
305 auto node = new Node(key, std::move(value));
306 index_.insert(*node);
307 lru_.push_front(*node);
309 // no evictions if maxSize_ is 0 i.e. unlimited capacity
310 if (maxSize_ > 0 && size() > maxSize_) {
311 prune(clearSize_, pruneHook);
317 * Get the number of elements in the dictionary
318 * @return the size of the dictionary
320 std::size_t size() const {
321 return index_.size();
325 * Typical empty function
326 * @return true if empty, false otherwise
329 return index_.empty();
332 void clear(PruneHookCall pruneHook = nullptr) {
333 prune(size(), pruneHook);
337 * Set the prune hook, which is the function invoked on the key and value
338 * on each eviction. Will throw If the pruneHook throws, unless the
339 * EvictingCacheMap object is being destroyed in which case it will
341 * @param pruneHook new callback to use on eviction.
342 * @param promote boolean flag indicating whether or not to move something
343 * to the front of an LRU.
344 * @return the iterator of the object (a std::pair of const TKey, TValue) or
345 * end() if it does not exist
347 void setPruneHook(PruneHookCall pruneHook) {
348 pruneHook_ = pruneHook;
353 * Prune the minimum of pruneSize and size() from the back of the LRU.
354 * Will throw if pruneHook throws.
355 * @param pruneSize minimum number of elements to prune
356 * @param pruneHook a custom pruneHook function
358 void prune(std::size_t pruneSize, PruneHookCall pruneHook = nullptr) {
359 // do not swallow exceptions for prunes not triggered from destructor
360 pruneWithFailSafeOption(pruneSize, pruneHook, false);
363 // Iterators and such
365 return iterator(lru_.begin());
368 return iterator(lru_.end());
370 const_iterator begin() const {
371 return const_iterator(lru_.begin());
373 const_iterator end() const {
374 return const_iterator(lru_.end());
377 const_iterator cbegin() const {
378 return const_iterator(lru_.cbegin());
380 const_iterator cend() const {
381 return const_iterator(lru_.cend());
384 reverse_iterator rbegin() {
385 return reverse_iterator(lru_.rbegin());
387 reverse_iterator rend() {
388 return reverse_iterator(lru_.rend());
391 const_reverse_iterator rbegin() const {
392 return const_reverse_iterator(lru_.rbegin());
394 const_reverse_iterator rend() const {
395 return const_reverse_iterator(lru_.rend());
398 const_reverse_iterator crbegin() const {
399 return const_reverse_iterator(lru_.crbegin());
401 const_reverse_iterator crend() const {
402 return const_reverse_iterator(lru_.crend());
407 : public boost::intrusive::unordered_set_base_hook<link_mode>,
408 public boost::intrusive::list_base_hook<link_mode> {
409 Node(const TKey& key, TValue&& value)
410 : pr(std::make_pair(key, std::move(value))) {
413 friend bool operator==(const Node& lhs, const Node& rhs) {
414 return lhs.pr.first == rhs.pr.first;
416 friend std::size_t hash_value(const Node& node) {
417 return THash()(node.pr.first);
422 std::size_t operator()(const Node& node) {
423 return THash()(node.pr.first);
425 std::size_t operator()(const TKey& key) {
430 struct KeyValueEqual {
431 bool operator()(const TKey& lhs, const Node& rhs) {
432 return lhs == rhs.pr.first;
434 bool operator()(const Node& lhs, const TKey& rhs) {
435 return lhs.pr.first == rhs;
440 * Get the iterator in in the index associated with a specific key. This is
441 * merely a search in the index and does not promote the object.
442 * @param key key to associate with value
443 * @return the NodeMap::iterator to the Node containing the object
444 * (a std::pair of const TKey, TValue) or index_.end() if it does not exist
446 typename NodeMap::iterator findInIndex(const TKey& key) {
447 return index_.find(key, KeyHasher(), KeyValueEqual());
450 typename NodeMap::const_iterator findInIndex(const TKey& key) const {
451 return index_.find(key, KeyHasher(), KeyValueEqual());
455 * Prune the minimum of pruneSize and size() from the back of the LRU.
456 * @param pruneSize minimum number of elements to prune
457 * @param pruneHook a custom pruneHook function
458 * @param failSafe true if exceptions are to ignored, false by default
460 void pruneWithFailSafeOption(std::size_t pruneSize,
461 PruneHookCall pruneHook, bool failSafe) {
462 auto& ph = (nullptr == pruneHook) ? pruneHook_ : pruneHook;
464 for (std::size_t i = 0; i < pruneSize && !lru_.empty(); i++) {
465 auto *node = &(*lru_.rbegin());
466 std::unique_ptr<Node> nptr(node);
468 lru_.erase(lru_.iterator_to(*node));
469 index_.erase(index_.iterator_to(*node));
472 ph(node->pr.first, std::move(node->pr.second));
482 static const std::size_t kMinNumIndexBuckets = 100;
483 PruneHookCall pruneHook_;
484 std::size_t nIndexBuckets_;
485 std::unique_ptr<typename NodeMap::bucket_type[]> indexBuckets_;
486 typename NodeMap::bucket_traits indexTraits_;
489 std::size_t maxSize_;
490 std::size_t clearSize_;