folly/EvictingCacheMap.h

   1 /*
   2  * Copyright 2015 Facebook, Inc.
   3  *
   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
   7  *
   8  *   http://www.apache.org/licenses/LICENSE-2.0
   9  *
  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.
  15  */
  16
  17 #ifndef FOLLY_EVICTINGHASHMAP_H_
  18 #define FOLLY_EVICTINGHASHMAP_H_
  19
  20 #include <algorithm>
  21 #include <exception>
  22 #include <functional>
  23
  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>
  28
  29 namespace folly {
  30
  31 /**
  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.
  40  *
  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.
  43  *
  44  * This is NOT a thread-safe implementation.
  45  *
  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.
  48  *
  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.
  59  *
  60  * +----+     +----+     +----+
  61  * | H1 | <-> | N1 | <-> | N5 |
  62  * +----+     +----+     +----+
  63  *              ^        ^  ^
  64  *              |    ___/    \
  65  *              |   /         \
  66  *              |_ /________   \___
  67  *                /        |       \
  68  *               /         |        \
  69  *              v          v         v
  70  * +----+     +----+     +----+     +----+
  71  * | H2 | <-> | N4 | <-> | N2 | <-> | N6 |
  72  * +----+     +----+     +----+     +----+
  73  *   .          ^          ^
  74  *   .          |          |
  75  *   .          |          |
  76  *   .          |     _____|
  77  *   .          |    /
  78  *              v   v
  79  * +----+     +----+
  80  * | Hi | <-> | N3 |
  81  * +----+     +----+
  82  *
  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
  86  * resizing.
  87  *
  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).
  92  */
  93 template <class TKey, class TValue, class THash = std::hash<TKey> >
  94 class EvictingCacheMap : private boost::noncopyable {
  95
  96  private:
  97   // typedefs for brevity
  98   struct Node;
  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;
 103
 104  public:
 105   typedef std::function<void(TKey, TValue&&)> PruneHookCall;
 106
 107   // iterator base : returns TPair on dereference
 108   template <typename Value, typename TIterator>
 109   class iterator_base
 110     : public boost::iterator_adaptor<iterator_base<Value, TIterator>,
 111                                     TIterator,
 112                                     Value,
 113                                     boost::bidirectional_traversal_tag > {
 114    public:
 115     iterator_base() {
 116     }
 117     explicit iterator_base(TIterator it)
 118         : iterator_base::iterator_adaptor_(it) {
 119     }
 120     Value& dereference() const {
 121       return this->base_reference()->pr;
 122     }
 123   };
 124
 125   // iterators
 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<
 133     const TPair,
 134     typename NodeList::const_reverse_iterator> const_reverse_iterator;
 135
 136   /**
 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.
 142    */
 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_),
 148         maxSize_(maxSize),
 149         clearSize_(clearSize) { }
 150
 151
 152   ~EvictingCacheMap() {
 153     setPruneHook(nullptr);
 154     // ignore any potential exceptions from pruneHook_
 155     pruneWithFailSafeOption(size(), nullptr, true);
 156   }
 157
 158   /**
 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.
 162    *
 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.
 165    *
 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
 168    * reasonable option.
 169    *
 170    * @param maxSize new maximum size of the cache map.
 171    * @param pruneHook callback to use on eviction.
 172    */
 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);
 177     }
 178     maxSize_ = maxSize;
 179   }
 180
 181   size_t getMaxSize() const {
 182     return maxSize_;
 183   }
 184
 185   void setClearSize(size_t clearSize) {
 186     clearSize_ = clearSize;
 187   }
 188
 189   /**
 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
 194    */
 195   bool exists(const TKey& key) const  {
 196     return findInIndex(key) != index_.end();
 197   }
 198
 199   /**
 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
 205    */
 206   TValue& get(const TKey& key) {
 207     auto it = find(key);
 208     if (it == end()) {
 209       throw std::out_of_range("Key does not exist");
 210     }
 211     return it->second;
 212   }
 213
 214   /**
 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
 220    */
 221   iterator find(const TKey& key) {
 222     auto it = findInIndex(key);
 223     if (it == index_.end()) {
 224       return end();
 225     }
 226     lru_.erase(lru_.iterator_to(*it));
 227     lru_.push_front(*it);
 228     return iterator(lru_.iterator_to(*it));
 229   }
 230
 231   /**
 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
 237    */
 238   const TValue& getWithoutPromotion(const TKey& key) const {
 239     auto it = findWithoutPromotion(key);
 240     if (it == end()) {
 241       throw std::out_of_range("Key does not exist");
 242     }
 243     return it->second;
 244   }
 245
 246   TValue& getWithoutPromotion(const TKey& key) {
 247     auto const& cThis = *this;
 248     return const_cast<TValue&>(cThis.getWithoutPromotion(key));
 249   }
 250
 251   /**
 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
 257    */
 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));
 261   }
 262
 263   iterator findWithoutPromotion(const TKey& key) {
 264     auto it = findInIndex(key);
 265     return (it == index_.end()) ? end() : iterator(lru_.iterator_to(*it));
 266   }
 267
 268   /**
 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
 272    */
 273   bool erase(const TKey& key) {
 274     auto it = findInIndex(key);
 275     if (it == index_.end()) {
 276       return false;
 277     }
 278     auto node = &(*it);
 279     std::unique_ptr<Node> nptr(node);
 280     lru_.erase(lru_.iterator_to(*node));
 281     index_.erase(it);
 282     return true;
 283   }
 284
 285   /**
 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).
 293    */
 294   void set(const TKey& key,
 295            TValue value,
 296            bool promote = true,
 297            PruneHookCall pruneHook = nullptr) {
 298     auto it = findInIndex(key);
 299     if (it != index_.end()) {
 300       it->pr.second = std::move(value);
 301       if (promote) {
 302         lru_.erase(lru_.iterator_to(*it));
 303         lru_.push_front(*it);
 304       }
 305     } else {
 306       auto node = new Node(key, std::move(value));
 307       index_.insert(*node);
 308       lru_.push_front(*node);
 309
 310       // no evictions if maxSize_ is 0 i.e. unlimited capacity
 311       if (maxSize_ > 0 && size() > maxSize_) {
 312         prune(clearSize_, pruneHook);
 313       }
 314     }
 315   }
 316
 317   /**
 318    * Get the number of elements in the dictionary
 319    * @return the size of the dictionary
 320    */
 321   std::size_t size() const {
 322     return index_.size();
 323   }
 324
 325   /**
 326    * Typical empty function
 327    * @return true if empty, false otherwise
 328    */
 329   bool empty() const {
 330     return index_.empty();
 331   }
 332
 333   void clear(PruneHookCall pruneHook = nullptr) {
 334     prune(size(), pruneHook);
 335   }
 336
 337   /**
 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
 341    *     be ignored.
 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
 347    */
 348   void setPruneHook(PruneHookCall pruneHook) {
 349     pruneHook_ = pruneHook;
 350   }
 351
 352
 353   /**
 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
 358    */
 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);
 362   }
 363
 364   // Iterators and such
 365   iterator begin() {
 366     return iterator(lru_.begin());
 367   }
 368   iterator end() {
 369     return iterator(lru_.end());
 370   }
 371   const_iterator begin() const {
 372     return const_iterator(lru_.begin());
 373   }
 374   const_iterator end() const {
 375     return const_iterator(lru_.end());
 376   }
 377
 378   const_iterator cbegin() const {
 379     return const_iterator(lru_.cbegin());
 380   }
 381   const_iterator cend() const {
 382     return const_iterator(lru_.cend());
 383   }
 384
 385   reverse_iterator rbegin() {
 386     return reverse_iterator(lru_.rbegin());
 387   }
 388   reverse_iterator rend() {
 389     return reverse_iterator(lru_.rend());
 390   }
 391
 392   const_reverse_iterator rbegin() const {
 393     return const_reverse_iterator(lru_.rbegin());
 394   }
 395   const_reverse_iterator rend() const {
 396     return const_reverse_iterator(lru_.rend());
 397   }
 398
 399   const_reverse_iterator crbegin() const {
 400     return const_reverse_iterator(lru_.crbegin());
 401   }
 402   const_reverse_iterator crend() const {
 403     return const_reverse_iterator(lru_.crend());
 404   }
 405
 406  private:
 407   struct Node
 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))) {
 412     }
 413     TPair pr;
 414     friend bool operator==(const Node& lhs, const Node& rhs) {
 415       return lhs.pr.first == rhs.pr.first;
 416     }
 417     friend std::size_t hash_value(const Node& node) {
 418       return THash()(node.pr.first);
 419     }
 420   };
 421
 422   struct KeyHasher {
 423     std::size_t operator()(const Node& node) {
 424       return THash()(node.pr.first);
 425     }
 426     std::size_t operator()(const TKey& key) {
 427       return THash()(key);
 428     }
 429   };
 430
 431   struct KeyValueEqual {
 432     bool operator()(const TKey& lhs, const Node& rhs) {
 433       return lhs == rhs.pr.first;
 434     }
 435     bool operator()(const Node& lhs, const TKey& rhs) {
 436       return lhs.pr.first == rhs;
 437     }
 438   };
 439
 440   /**
 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
 446    */
 447   typename NodeMap::iterator findInIndex(const TKey& key) {
 448     return index_.find(key, KeyHasher(), KeyValueEqual());
 449   }
 450
 451   typename NodeMap::const_iterator findInIndex(const TKey& key) const {
 452     return index_.find(key, KeyHasher(), KeyValueEqual());
 453   }
 454
 455   /**
 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
 460    */
 461   void pruneWithFailSafeOption(std::size_t pruneSize,
 462     PruneHookCall pruneHook, bool failSafe) {
 463     auto& ph = (nullptr == pruneHook) ? pruneHook_ : pruneHook;
 464
 465     for (std::size_t i = 0; i < pruneSize && !lru_.empty(); i++) {
 466       auto *node = &(*lru_.rbegin());
 467       std::unique_ptr<Node> nptr(node);
 468
 469       lru_.erase(lru_.iterator_to(*node));
 470       index_.erase(index_.iterator_to(*node));
 471       if (ph) {
 472         try {
 473           ph(node->pr.first, std::move(node->pr.second));
 474         } catch (...) {
 475           if (!failSafe) {
 476             throw;
 477           }
 478         }
 479       }
 480     }
 481   }
 482
 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_;
 488   NodeMap index_;
 489   NodeList lru_;
 490   std::size_t maxSize_;
 491   std::size_t clearSize_;
 492 };
 493
 494 } // folly
 495
 496 #endif /* FOLLY_EVICTINGHASHMAP_H_ */