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/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>
  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 {
  95  private:
  96   // typedefs for brevity
  97   struct Node;
  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;
 102
 103  public:
 104   typedef std::function<void(TKey, TValue&&)> PruneHookCall;
 105
 106   // iterator base : returns TPair on dereference
 107   template <typename Value, typename TIterator>
 108   class iterator_base
 109     : public boost::iterator_adaptor<iterator_base<Value, TIterator>,
 110                                     TIterator,
 111                                     Value,
 112                                     boost::bidirectional_traversal_tag > {
 113    public:
 114     iterator_base() {
 115     }
 116     explicit iterator_base(TIterator it)
 117         : iterator_base::iterator_adaptor_(it) {
 118     }
 119     Value& dereference() const {
 120       return this->base_reference()->pr;
 121     }
 122   };
 123
 124   // iterators
 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<
 132     const TPair,
 133     typename NodeList::const_reverse_iterator> const_reverse_iterator;
 134
 135   /**
 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.
 141    */
 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_),
 147         maxSize_(maxSize),
 148         clearSize_(clearSize) { }
 149
 150   EvictingCacheMap(const EvictingCacheMap&) = delete;
 151   EvictingCacheMap& operator=(const EvictingCacheMap&) = delete;
 152   EvictingCacheMap(EvictingCacheMap&&) = default;
 153   EvictingCacheMap& operator=(EvictingCacheMap&&) = default;
 154
 155   ~EvictingCacheMap() {
 156     setPruneHook(nullptr);
 157     // ignore any potential exceptions from pruneHook_
 158     pruneWithFailSafeOption(size(), nullptr, true);
 159   }
 160
 161   /**
 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.
 165    *
 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.
 168    *
 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
 171    * reasonable option.
 172    *
 173    * @param maxSize new maximum size of the cache map.
 174    * @param pruneHook callback to use on eviction.
 175    */
 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);
 180     }
 181     maxSize_ = maxSize;
 182   }
 183
 184   size_t getMaxSize() const {
 185     return maxSize_;
 186   }
 187
 188   void setClearSize(size_t clearSize) {
 189     clearSize_ = clearSize;
 190   }
 191
 192   /**
 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
 197    */
 198   bool exists(const TKey& key) const  {
 199     return findInIndex(key) != index_.end();
 200   }
 201
 202   /**
 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
 208    */
 209   TValue& get(const TKey& key) {
 210     auto it = find(key);
 211     if (it == end()) {
 212       std::__throw_out_of_range("Key does not exist");
 213     }
 214     return it->second;
 215   }
 216
 217   /**
 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
 223    */
 224   iterator find(const TKey& key) {
 225     auto it = findInIndex(key);
 226     if (it == index_.end()) {
 227       return end();
 228     }
 229     lru_.erase(lru_.iterator_to(*it));
 230     lru_.push_front(*it);
 231     return iterator(lru_.iterator_to(*it));
 232   }
 233
 234   /**
 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
 240    */
 241   const TValue& getWithoutPromotion(const TKey& key) const {
 242     auto it = findWithoutPromotion(key);
 243     if (it == end()) {
 244       std::__throw_out_of_range("Key does not exist");
 245     }
 246     return it->second;
 247   }
 248
 249   TValue& getWithoutPromotion(const TKey& key) {
 250     auto const& cThis = *this;
 251     return const_cast<TValue&>(cThis.getWithoutPromotion(key));
 252   }
 253
 254   /**
 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
 260    */
 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));
 264   }
 265
 266   iterator findWithoutPromotion(const TKey& key) {
 267     auto it = findInIndex(key);
 268     return (it == index_.end()) ? end() : iterator(lru_.iterator_to(*it));
 269   }
 270
 271   /**
 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
 275    */
 276   bool erase(const TKey& key) {
 277     auto it = findInIndex(key);
 278     if (it == index_.end()) {
 279       return false;
 280     }
 281     auto node = &(*it);
 282     std::unique_ptr<Node> nptr(node);
 283     lru_.erase(lru_.iterator_to(*node));
 284     index_.erase(it);
 285     return true;
 286   }
 287
 288   /**
 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).
 296    */
 297   void set(const TKey& key,
 298            TValue value,
 299            bool promote = true,
 300            PruneHookCall pruneHook = nullptr) {
 301     auto it = findInIndex(key);
 302     if (it != index_.end()) {
 303       it->pr.second = std::move(value);
 304       if (promote) {
 305         lru_.erase(lru_.iterator_to(*it));
 306         lru_.push_front(*it);
 307       }
 308     } else {
 309       auto node = new Node(key, std::move(value));
 310       index_.insert(*node);
 311       lru_.push_front(*node);
 312
 313       // no evictions if maxSize_ is 0 i.e. unlimited capacity
 314       if (maxSize_ > 0 && size() > maxSize_) {
 315         prune(clearSize_, pruneHook);
 316       }
 317     }
 318   }
 319
 320   /**
 321    * Get the number of elements in the dictionary
 322    * @return the size of the dictionary
 323    */
 324   std::size_t size() const {
 325     return index_.size();
 326   }
 327
 328   /**
 329    * Typical empty function
 330    * @return true if empty, false otherwise
 331    */
 332   bool empty() const {
 333     return index_.empty();
 334   }
 335
 336   void clear(PruneHookCall pruneHook = nullptr) {
 337     prune(size(), pruneHook);
 338   }
 339
 340   /**
 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
 344    *     be ignored.
 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
 350    */
 351   void setPruneHook(PruneHookCall pruneHook) {
 352     pruneHook_ = pruneHook;
 353   }
 354
 355
 356   /**
 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
 361    */
 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);
 365   }
 366
 367   // Iterators and such
 368   iterator begin() {
 369     return iterator(lru_.begin());
 370   }
 371   iterator end() {
 372     return iterator(lru_.end());
 373   }
 374   const_iterator begin() const {
 375     return const_iterator(lru_.begin());
 376   }
 377   const_iterator end() const {
 378     return const_iterator(lru_.end());
 379   }
 380
 381   const_iterator cbegin() const {
 382     return const_iterator(lru_.cbegin());
 383   }
 384   const_iterator cend() const {
 385     return const_iterator(lru_.cend());
 386   }
 387
 388   reverse_iterator rbegin() {
 389     return reverse_iterator(lru_.rbegin());
 390   }
 391   reverse_iterator rend() {
 392     return reverse_iterator(lru_.rend());
 393   }
 394
 395   const_reverse_iterator rbegin() const {
 396     return const_reverse_iterator(lru_.rbegin());
 397   }
 398   const_reverse_iterator rend() const {
 399     return const_reverse_iterator(lru_.rend());
 400   }
 401
 402   const_reverse_iterator crbegin() const {
 403     return const_reverse_iterator(lru_.crbegin());
 404   }
 405   const_reverse_iterator crend() const {
 406     return const_reverse_iterator(lru_.crend());
 407   }
 408
 409  private:
 410   struct Node
 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))) {
 415     }
 416     TPair pr;
 417     friend bool operator==(const Node& lhs, const Node& rhs) {
 418       return lhs.pr.first == rhs.pr.first;
 419     }
 420     friend std::size_t hash_value(const Node& node) {
 421       return THash()(node.pr.first);
 422     }
 423   };
 424
 425   struct KeyHasher {
 426     std::size_t operator()(const Node& node) {
 427       return THash()(node.pr.first);
 428     }
 429     std::size_t operator()(const TKey& key) {
 430       return THash()(key);
 431     }
 432   };
 433
 434   struct KeyValueEqual {
 435     bool operator()(const TKey& lhs, const Node& rhs) {
 436       return lhs == rhs.pr.first;
 437     }
 438     bool operator()(const Node& lhs, const TKey& rhs) {
 439       return lhs.pr.first == rhs;
 440     }
 441   };
 442
 443   /**
 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
 449    */
 450   typename NodeMap::iterator findInIndex(const TKey& key) {
 451     return index_.find(key, KeyHasher(), KeyValueEqual());
 452   }
 453
 454   typename NodeMap::const_iterator findInIndex(const TKey& key) const {
 455     return index_.find(key, KeyHasher(), KeyValueEqual());
 456   }
 457
 458   /**
 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
 463    */
 464   void pruneWithFailSafeOption(std::size_t pruneSize,
 465     PruneHookCall pruneHook, bool failSafe) {
 466     auto& ph = (nullptr == pruneHook) ? pruneHook_ : pruneHook;
 467
 468     for (std::size_t i = 0; i < pruneSize && !lru_.empty(); i++) {
 469       auto *node = &(*lru_.rbegin());
 470       std::unique_ptr<Node> nptr(node);
 471
 472       lru_.erase(lru_.iterator_to(*node));
 473       index_.erase(index_.iterator_to(*node));
 474       if (ph) {
 475         try {
 476           ph(node->pr.first, std::move(node->pr.second));
 477         } catch (...) {
 478           if (!failSafe) {
 479             throw;
 480           }
 481         }
 482       }
 483     }
 484   }
 485
 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_;
 491   NodeMap index_;
 492   NodeList lru_;
 493   std::size_t maxSize_;
 494   std::size_t clearSize_;
 495 };
 496
 497 } // folly