folly/EvictingCacheMap.h

   1 /*
   2  * Copyright 2017 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 #pragma once
  18
  19 #include <algorithm>
  20 #include <exception>
  21 #include <functional>
  22
  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>
  27
  28 #include <folly/portability/BitsFunctexcept.h>
  29
  30 namespace folly {
  31
  32 /**
  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.
  41  *
  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.
  44  *
  45  * This is NOT a thread-safe implementation.
  46  *
  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.
  49  *
  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.
  60  *
  61  * +----+     +----+     +----+
  62  * | H1 | <-> | N1 | <-> | N5 |
  63  * +----+     +----+     +----+
  64  *              ^        ^  ^
  65  *              |    ___/    \
  66  *              |   /         \
  67  *              |_ /________   \___
  68  *                /        |       \
  69  *               /         |        \
  70  *              v          v         v
  71  * +----+     +----+     +----+     +----+
  72  * | H2 | <-> | N4 | <-> | N2 | <-> | N6 |
  73  * +----+     +----+     +----+     +----+
  74  *   .          ^          ^
  75  *   .          |          |
  76  *   .          |          |
  77  *   .          |     _____|
  78  *   .          |    /
  79  *              v   v
  80  * +----+     +----+
  81  * | Hi | <-> | N3 |
  82  * +----+     +----+
  83  *
  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
  87  * resizing.
  88  *
  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).
  93  */
  94 template <class TKey, class TValue, class THash = std::hash<TKey>>
  95 class EvictingCacheMap {
  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   EvictingCacheMap(const EvictingCacheMap&) = delete;
 152   EvictingCacheMap& operator=(const EvictingCacheMap&) = delete;
 153   EvictingCacheMap(EvictingCacheMap&&) = default;
 154   EvictingCacheMap& operator=(EvictingCacheMap&&) = default;
 155
 156   ~EvictingCacheMap() {
 157     setPruneHook(nullptr);
 158     // ignore any potential exceptions from pruneHook_
 159     pruneWithFailSafeOption(size(), nullptr, true);
 160   }
 161
 162   /**
 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.
 166    *
 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.
 169    *
 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
 172    * reasonable option.
 173    *
 174    * @param maxSize new maximum size of the cache map.
 175    * @param pruneHook callback to use on eviction.
 176    */
 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);
 181     }
 182     maxSize_ = maxSize;
 183   }
 184
 185   size_t getMaxSize() const {
 186     return maxSize_;
 187   }
 188
 189   void setClearSize(size_t clearSize) {
 190     clearSize_ = clearSize;
 191   }
 192
 193   /**
 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
 198    */
 199   bool exists(const TKey& key) const  {
 200     return findInIndex(key) != index_.end();
 201   }
 202
 203   /**
 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
 209    */
 210   TValue& get(const TKey& key) {
 211     auto it = find(key);
 212     if (it == end()) {
 213       std::__throw_out_of_range("Key does not exist");
 214     }
 215     return it->second;
 216   }
 217
 218   /**
 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
 224    */
 225   iterator find(const TKey& key) {
 226     auto it = findInIndex(key);
 227     if (it == index_.end()) {
 228       return end();
 229     }
 230     lru_.erase(lru_.iterator_to(*it));
 231     lru_.push_front(*it);
 232     return iterator(lru_.iterator_to(*it));
 233   }
 234
 235   /**
 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
 241    */
 242   const TValue& getWithoutPromotion(const TKey& key) const {
 243     auto it = findWithoutPromotion(key);
 244     if (it == end()) {
 245       std::__throw_out_of_range("Key does not exist");
 246     }
 247     return it->second;
 248   }
 249
 250   TValue& getWithoutPromotion(const TKey& key) {
 251     auto const& cThis = *this;
 252     return const_cast<TValue&>(cThis.getWithoutPromotion(key));
 253   }
 254
 255   /**
 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
 261    */
 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));
 265   }
 266
 267   iterator findWithoutPromotion(const TKey& key) {
 268     auto it = findInIndex(key);
 269     return (it == index_.end()) ? end() : iterator(lru_.iterator_to(*it));
 270   }
 271
 272   /**
 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
 276    */
 277   bool erase(const TKey& key) {
 278     auto it = findInIndex(key);
 279     if (it == index_.end()) {
 280       return false;
 281     }
 282     auto node = &(*it);
 283     std::unique_ptr<Node> nptr(node);
 284     lru_.erase(lru_.iterator_to(*node));
 285     index_.erase(it);
 286     return true;
 287   }
 288
 289   /**
 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).
 297    */
 298   void set(const TKey& key,
 299            TValue value,
 300            bool promote = true,
 301            PruneHookCall pruneHook = nullptr) {
 302     auto it = findInIndex(key);
 303     if (it != index_.end()) {
 304       it->pr.second = std::move(value);
 305       if (promote) {
 306         lru_.erase(lru_.iterator_to(*it));
 307         lru_.push_front(*it);
 308       }
 309     } else {
 310       auto node = new Node(key, std::move(value));
 311       index_.insert(*node);
 312       lru_.push_front(*node);
 313
 314       // no evictions if maxSize_ is 0 i.e. unlimited capacity
 315       if (maxSize_ > 0 && size() > maxSize_) {
 316         prune(clearSize_, pruneHook);
 317       }
 318     }
 319   }
 320
 321   /**
 322    * Get the number of elements in the dictionary
 323    * @return the size of the dictionary
 324    */
 325   std::size_t size() const {
 326     return index_.size();
 327   }
 328
 329   /**
 330    * Typical empty function
 331    * @return true if empty, false otherwise
 332    */
 333   bool empty() const {
 334     return index_.empty();
 335   }
 336
 337   void clear(PruneHookCall pruneHook = nullptr) {
 338     prune(size(), pruneHook);
 339   }
 340
 341   /**
 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
 345    *     be ignored.
 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
 351    */
 352   void setPruneHook(PruneHookCall pruneHook) {
 353     pruneHook_ = pruneHook;
 354   }
 355
 356
 357   /**
 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
 362    */
 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);
 366   }
 367
 368   // Iterators and such
 369   iterator begin() {
 370     return iterator(lru_.begin());
 371   }
 372   iterator end() {
 373     return iterator(lru_.end());
 374   }
 375   const_iterator begin() const {
 376     return const_iterator(lru_.begin());
 377   }
 378   const_iterator end() const {
 379     return const_iterator(lru_.end());
 380   }
 381
 382   const_iterator cbegin() const {
 383     return const_iterator(lru_.cbegin());
 384   }
 385   const_iterator cend() const {
 386     return const_iterator(lru_.cend());
 387   }
 388
 389   reverse_iterator rbegin() {
 390     return reverse_iterator(lru_.rbegin());
 391   }
 392   reverse_iterator rend() {
 393     return reverse_iterator(lru_.rend());
 394   }
 395
 396   const_reverse_iterator rbegin() const {
 397     return const_reverse_iterator(lru_.rbegin());
 398   }
 399   const_reverse_iterator rend() const {
 400     return const_reverse_iterator(lru_.rend());
 401   }
 402
 403   const_reverse_iterator crbegin() const {
 404     return const_reverse_iterator(lru_.crbegin());
 405   }
 406   const_reverse_iterator crend() const {
 407     return const_reverse_iterator(lru_.crend());
 408   }
 409
 410  private:
 411   struct Node
 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))) {
 416     }
 417     TPair pr;
 418     friend bool operator==(const Node& lhs, const Node& rhs) {
 419       return lhs.pr.first == rhs.pr.first;
 420     }
 421     friend std::size_t hash_value(const Node& node) {
 422       return THash()(node.pr.first);
 423     }
 424   };
 425
 426   struct KeyHasher {
 427     std::size_t operator()(const Node& node) {
 428       return THash()(node.pr.first);
 429     }
 430     std::size_t operator()(const TKey& key) {
 431       return THash()(key);
 432     }
 433   };
 434
 435   struct KeyValueEqual {
 436     bool operator()(const TKey& lhs, const Node& rhs) {
 437       return lhs == rhs.pr.first;
 438     }
 439     bool operator()(const Node& lhs, const TKey& rhs) {
 440       return lhs.pr.first == rhs;
 441     }
 442   };
 443
 444   /**
 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
 450    */
 451   typename NodeMap::iterator findInIndex(const TKey& key) {
 452     return index_.find(key, KeyHasher(), KeyValueEqual());
 453   }
 454
 455   typename NodeMap::const_iterator findInIndex(const TKey& key) const {
 456     return index_.find(key, KeyHasher(), KeyValueEqual());
 457   }
 458
 459   /**
 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
 464    */
 465   void pruneWithFailSafeOption(std::size_t pruneSize,
 466     PruneHookCall pruneHook, bool failSafe) {
 467     auto& ph = (nullptr == pruneHook) ? pruneHook_ : pruneHook;
 468
 469     for (std::size_t i = 0; i < pruneSize && !lru_.empty(); i++) {
 470       auto *node = &(*lru_.rbegin());
 471       std::unique_ptr<Node> nptr(node);
 472
 473       lru_.erase(lru_.iterator_to(*node));
 474       index_.erase(index_.iterator_to(*node));
 475       if (ph) {
 476         try {
 477           ph(node->pr.first, std::move(node->pr.second));
 478         } catch (...) {
 479           if (!failSafe) {
 480             throw;
 481           }
 482         }
 483       }
 484     }
 485   }
 486
 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_;
 492   NodeMap index_;
 493   NodeList lru_;
 494   std::size_t maxSize_;
 495   std::size_t clearSize_;
 496 };
 497
 498 } // namespace folly