folly/EvictingCacheMap.h

   1 /*
   2  * Copyright 2016 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
  28 namespace folly {
  29
  30 /**
  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.
  39  *
  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.
  42  *
  43  * This is NOT a thread-safe implementation.
  44  *
  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.
  47  *
  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.
  58  *
  59  * +----+     +----+     +----+
  60  * | H1 | <-> | N1 | <-> | N5 |
  61  * +----+     +----+     +----+
  62  *              ^        ^  ^
  63  *              |    ___/    \
  64  *              |   /         \
  65  *              |_ /________   \___
  66  *                /        |       \
  67  *               /         |        \
  68  *              v          v         v
  69  * +----+     +----+     +----+     +----+
  70  * | H2 | <-> | N4 | <-> | N2 | <-> | N6 |
  71  * +----+     +----+     +----+     +----+
  72  *   .          ^          ^
  73  *   .          |          |
  74  *   .          |          |
  75  *   .          |     _____|
  76  *   .          |    /
  77  *              v   v
  78  * +----+     +----+
  79  * | Hi | <-> | N3 |
  80  * +----+     +----+
  81  *
  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
  85  * resizing.
  86  *
  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).
  91  */
  92 template <class TKey, class TValue, class THash = std::hash<TKey> >
  93 class EvictingCacheMap : private boost::noncopyable {
  94
  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
 151   ~EvictingCacheMap() {
 152     setPruneHook(nullptr);
 153     // ignore any potential exceptions from pruneHook_
 154     pruneWithFailSafeOption(size(), nullptr, true);
 155   }
 156
 157   /**
 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.
 161    *
 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.
 164    *
 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
 167    * reasonable option.
 168    *
 169    * @param maxSize new maximum size of the cache map.
 170    * @param pruneHook callback to use on eviction.
 171    */
 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);
 176     }
 177     maxSize_ = maxSize;
 178   }
 179
 180   size_t getMaxSize() const {
 181     return maxSize_;
 182   }
 183
 184   void setClearSize(size_t clearSize) {
 185     clearSize_ = clearSize;
 186   }
 187
 188   /**
 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
 193    */
 194   bool exists(const TKey& key) const  {
 195     return findInIndex(key) != index_.end();
 196   }
 197
 198   /**
 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
 204    */
 205   TValue& get(const TKey& key) {
 206     auto it = find(key);
 207     if (it == end()) {
 208       throw std::out_of_range("Key does not exist");
 209     }
 210     return it->second;
 211   }
 212
 213   /**
 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
 219    */
 220   iterator find(const TKey& key) {
 221     auto it = findInIndex(key);
 222     if (it == index_.end()) {
 223       return end();
 224     }
 225     lru_.erase(lru_.iterator_to(*it));
 226     lru_.push_front(*it);
 227     return iterator(lru_.iterator_to(*it));
 228   }
 229
 230   /**
 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
 236    */
 237   const TValue& getWithoutPromotion(const TKey& key) const {
 238     auto it = findWithoutPromotion(key);
 239     if (it == end()) {
 240       throw std::out_of_range("Key does not exist");
 241     }
 242     return it->second;
 243   }
 244
 245   TValue& getWithoutPromotion(const TKey& key) {
 246     auto const& cThis = *this;
 247     return const_cast<TValue&>(cThis.getWithoutPromotion(key));
 248   }
 249
 250   /**
 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
 256    */
 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));
 260   }
 261
 262   iterator findWithoutPromotion(const TKey& key) {
 263     auto it = findInIndex(key);
 264     return (it == index_.end()) ? end() : iterator(lru_.iterator_to(*it));
 265   }
 266
 267   /**
 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
 271    */
 272   bool erase(const TKey& key) {
 273     auto it = findInIndex(key);
 274     if (it == index_.end()) {
 275       return false;
 276     }
 277     auto node = &(*it);
 278     std::unique_ptr<Node> nptr(node);
 279     lru_.erase(lru_.iterator_to(*node));
 280     index_.erase(it);
 281     return true;
 282   }
 283
 284   /**
 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).
 292    */
 293   void set(const TKey& key,
 294            TValue value,
 295            bool promote = true,
 296            PruneHookCall pruneHook = nullptr) {
 297     auto it = findInIndex(key);
 298     if (it != index_.end()) {
 299       it->pr.second = std::move(value);
 300       if (promote) {
 301         lru_.erase(lru_.iterator_to(*it));
 302         lru_.push_front(*it);
 303       }
 304     } else {
 305       auto node = new Node(key, std::move(value));
 306       index_.insert(*node);
 307       lru_.push_front(*node);
 308
 309       // no evictions if maxSize_ is 0 i.e. unlimited capacity
 310       if (maxSize_ > 0 && size() > maxSize_) {
 311         prune(clearSize_, pruneHook);
 312       }
 313     }
 314   }
 315
 316   /**
 317    * Get the number of elements in the dictionary
 318    * @return the size of the dictionary
 319    */
 320   std::size_t size() const {
 321     return index_.size();
 322   }
 323
 324   /**
 325    * Typical empty function
 326    * @return true if empty, false otherwise
 327    */
 328   bool empty() const {
 329     return index_.empty();
 330   }
 331
 332   void clear(PruneHookCall pruneHook = nullptr) {
 333     prune(size(), pruneHook);
 334   }
 335
 336   /**
 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
 340    *     be ignored.
 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
 346    */
 347   void setPruneHook(PruneHookCall pruneHook) {
 348     pruneHook_ = pruneHook;
 349   }
 350
 351
 352   /**
 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
 357    */
 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);
 361   }
 362
 363   // Iterators and such
 364   iterator begin() {
 365     return iterator(lru_.begin());
 366   }
 367   iterator end() {
 368     return iterator(lru_.end());
 369   }
 370   const_iterator begin() const {
 371     return const_iterator(lru_.begin());
 372   }
 373   const_iterator end() const {
 374     return const_iterator(lru_.end());
 375   }
 376
 377   const_iterator cbegin() const {
 378     return const_iterator(lru_.cbegin());
 379   }
 380   const_iterator cend() const {
 381     return const_iterator(lru_.cend());
 382   }
 383
 384   reverse_iterator rbegin() {
 385     return reverse_iterator(lru_.rbegin());
 386   }
 387   reverse_iterator rend() {
 388     return reverse_iterator(lru_.rend());
 389   }
 390
 391   const_reverse_iterator rbegin() const {
 392     return const_reverse_iterator(lru_.rbegin());
 393   }
 394   const_reverse_iterator rend() const {
 395     return const_reverse_iterator(lru_.rend());
 396   }
 397
 398   const_reverse_iterator crbegin() const {
 399     return const_reverse_iterator(lru_.crbegin());
 400   }
 401   const_reverse_iterator crend() const {
 402     return const_reverse_iterator(lru_.crend());
 403   }
 404
 405  private:
 406   struct Node
 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))) {
 411     }
 412     TPair pr;
 413     friend bool operator==(const Node& lhs, const Node& rhs) {
 414       return lhs.pr.first == rhs.pr.first;
 415     }
 416     friend std::size_t hash_value(const Node& node) {
 417       return THash()(node.pr.first);
 418     }
 419   };
 420
 421   struct KeyHasher {
 422     std::size_t operator()(const Node& node) {
 423       return THash()(node.pr.first);
 424     }
 425     std::size_t operator()(const TKey& key) {
 426       return THash()(key);
 427     }
 428   };
 429
 430   struct KeyValueEqual {
 431     bool operator()(const TKey& lhs, const Node& rhs) {
 432       return lhs == rhs.pr.first;
 433     }
 434     bool operator()(const Node& lhs, const TKey& rhs) {
 435       return lhs.pr.first == rhs;
 436     }
 437   };
 438
 439   /**
 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
 445    */
 446   typename NodeMap::iterator findInIndex(const TKey& key) {
 447     return index_.find(key, KeyHasher(), KeyValueEqual());
 448   }
 449
 450   typename NodeMap::const_iterator findInIndex(const TKey& key) const {
 451     return index_.find(key, KeyHasher(), KeyValueEqual());
 452   }
 453
 454   /**
 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
 459    */
 460   void pruneWithFailSafeOption(std::size_t pruneSize,
 461     PruneHookCall pruneHook, bool failSafe) {
 462     auto& ph = (nullptr == pruneHook) ? pruneHook_ : pruneHook;
 463
 464     for (std::size_t i = 0; i < pruneSize && !lru_.empty(); i++) {
 465       auto *node = &(*lru_.rbegin());
 466       std::unique_ptr<Node> nptr(node);
 467
 468       lru_.erase(lru_.iterator_to(*node));
 469       index_.erase(index_.iterator_to(*node));
 470       if (ph) {
 471         try {
 472           ph(node->pr.first, std::move(node->pr.second));
 473         } catch (...) {
 474           if (!failSafe) {
 475             throw;
 476           }
 477         }
 478       }
 479     }
 480   }
 481
 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_;
 487   NodeMap index_;
 488   NodeList lru_;
 489   std::size_t maxSize_;
 490   std::size_t clearSize_;
 491 };
 492
 493 } // folly