folly/EvictingCacheMap.h

   1 /*
   2  * Copyright 2014 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   void setMaxSize(size_t maxSize) {
 171     if (maxSize != 0 && maxSize < size()) {
 172       // Prune the excess elements with our new constraints.
 173       prune(std::max(size() - maxSize, clearSize_));
 174     }
 175     maxSize_ = maxSize;
 176   }
 177
 178   size_t getMaxSize() const {
 179     return maxSize_;
 180   }
 181
 182   void setClearSize(size_t clearSize) {
 183     clearSize_ = clearSize;
 184   }
 185
 186   /**
 187    * Check for existence of a specific key in the map.  This operation has
 188    *     no effect on LRU order.
 189    * @param key key to search for
 190    * @return true if exists, false otherwise
 191    */
 192   bool exists(const TKey& key) const  {
 193     return findInIndex(key) != index_.end();
 194   }
 195
 196   /**
 197    * Get the value associated with a specific key.  This function always
 198    *     promotes a found value to the head of the LRU.
 199    * @param key key associated with the value
 200    * @return the value if it exists
 201    * @throw std::out_of_range exception of the key does not exist
 202    */
 203   TValue& get(const TKey& key) {
 204     auto it = find(key);
 205     if (it == end()) {
 206       throw std::out_of_range("Key does not exist");
 207     }
 208     return it->second;
 209   }
 210
 211   /**
 212    * Get the iterator associated with a specific key.  This function always
 213    *     promotes a found value to the head of the LRU.
 214    * @param key key to associate with value
 215    * @return the iterator of the object (a std::pair of const TKey, TValue) or
 216    *     end() if it does not exist
 217    */
 218   iterator find(const TKey& key) {
 219     auto it = findInIndex(key);
 220     if (it == index_.end()) {
 221       return end();
 222     }
 223     lru_.erase(lru_.iterator_to(*it));
 224     lru_.push_front(*it);
 225     return iterator(lru_.iterator_to(*it));
 226   }
 227
 228   /**
 229    * Get the value associated with a specific key.  This function never
 230    *     promotes a found value to the head of the LRU.
 231    * @param key key associated with the value
 232    * @return the value if it exists
 233    * @throw std::out_of_range exception of the key does not exist
 234    */
 235   const TValue& getWithoutPromotion(const TKey& key) const {
 236     auto it = findWithoutPromotion(key);
 237     if (it == end()) {
 238       throw std::out_of_range("Key does not exist");
 239     }
 240     return it->second;
 241   }
 242
 243   TValue& getWithoutPromotion(const TKey& key) {
 244     auto const& cThis = *this;
 245     return const_cast<TValue&>(cThis.getWithoutPromotion(key));
 246   }
 247
 248   /**
 249    * Get the iterator associated with a specific key.  This function never
 250    *     promotes a found value to the head of the LRU.
 251    * @param key key to associate with value
 252    * @return the iterator of the object (a std::pair of const TKey, TValue) or
 253    *     end() if it does not exist
 254    */
 255   const_iterator findWithoutPromotion(const TKey& key) const {
 256     auto it = findInIndex(key);
 257     return (it == index_.end()) ? end() : const_iterator(lru_.iterator_to(*it));
 258   }
 259
 260   iterator findWithoutPromotion(const TKey& key) {
 261     auto it = findInIndex(key);
 262     return (it == index_.end()) ? end() : iterator(lru_.iterator_to(*it));
 263   }
 264
 265   /**
 266    * Erase the key-value pair associated with key if it exists.
 267    * @param key key associated with the value
 268    * @return true if the key existed and was erased, else false
 269    */
 270   bool erase(const TKey& key) {
 271     auto it = findInIndex(key);
 272     if (it == index_.end()) {
 273       return false;
 274     }
 275     auto node = &(*it);
 276     std::unique_ptr<Node> nptr(node);
 277     lru_.erase(lru_.iterator_to(*node));
 278     index_.erase(it);
 279     return true;
 280   }
 281
 282   /**
 283    * Set a key-value pair in the dictionary
 284    * @param key key to associate with value
 285    * @param value value to associate with the key
 286    * @param promote boolean flag indicating whether or not to move something
 287    *     to the front of an LRU.  This only really matters if you're setting
 288    *     a value that already exists.
 289    */
 290   void set(const TKey& key, TValue value, bool promote = true) {
 291     auto it = findInIndex(key);
 292     if (it != index_.end()) {
 293       it->pr.second = std::move(value);
 294       if (promote) {
 295         lru_.erase(lru_.iterator_to(*it));
 296         lru_.push_front(*it);
 297       }
 298     } else {
 299       auto node = new Node(key, std::move(value));
 300       index_.insert(*node);
 301       lru_.push_front(*node);
 302
 303       // no evictions if maxSize_ is 0 i.e. unlimited capacity
 304       if (maxSize_ > 0 && size() > maxSize_) {
 305         prune(clearSize_);
 306       }
 307     }
 308   }
 309
 310   /**
 311    * Get the number of elements in the dictionary
 312    * @return the size of the dictionary
 313    */
 314   std::size_t size() const {
 315     return index_.size();
 316   }
 317
 318   /**
 319    * Typical empty function
 320    * @return true if empty, false otherwise
 321    */
 322   bool empty() const {
 323     return index_.empty();
 324   }
 325
 326   void clear() {
 327     prune(size());
 328   }
 329
 330   /**
 331    * Set the prune hook, which is the function invoked on the key and value
 332    *     on each eviction.  Will throw If the pruneHook throws, unless the
 333    *     EvictingCacheMap object is being destroyed in which case it will
 334    *     be ignored.
 335    * @param pruneHook new callback to use on eviction.
 336    * @param promote boolean flag indicating whether or not to move something
 337    *     to the front of an LRU.
 338    * @return the iterator of the object (a std::pair of const TKey, TValue) or
 339    *     end() if it does not exist
 340    */
 341   void setPruneHook(PruneHookCall pruneHook) {
 342     pruneHook_ = pruneHook;
 343   }
 344
 345
 346   /**
 347    * Prune the minimum of pruneSize and size() from the back of the LRU.
 348    * Will throw if pruneHook throws.
 349    * @param pruneSize minimum number of elements to prune
 350    * @param pruneHook a custom pruneHook function
 351    */
 352   void prune(std::size_t pruneSize, PruneHookCall pruneHook = nullptr) {
 353     // do not swallow exceptions for prunes not triggered from destructor
 354     pruneWithFailSafeOption(pruneSize, pruneHook, false);
 355   }
 356
 357   // Iterators and such
 358   iterator begin() {
 359     return iterator(lru_.begin());
 360   }
 361   iterator end() {
 362     return iterator(lru_.end());
 363   }
 364   const_iterator begin() const {
 365     return const_iterator(lru_.begin());
 366   }
 367   const_iterator end() const {
 368     return const_iterator(lru_.end());
 369   }
 370
 371   const_iterator cbegin() const {
 372     return const_iterator(lru_.cbegin());
 373   }
 374   const_iterator cend() const {
 375     return const_iterator(lru_.cend());
 376   }
 377
 378   reverse_iterator rbegin() {
 379     return reverse_iterator(lru_.rbegin());
 380   }
 381   reverse_iterator rend() {
 382     return reverse_iterator(lru_.rend());
 383   }
 384
 385   const_reverse_iterator rbegin() const {
 386     return const_reverse_iterator(lru_.rbegin());
 387   }
 388   const_reverse_iterator rend() const {
 389     return const_reverse_iterator(lru_.rend());
 390   }
 391
 392   const_reverse_iterator crbegin() const {
 393     return const_reverse_iterator(lru_.crbegin());
 394   }
 395   const_reverse_iterator crend() const {
 396     return const_reverse_iterator(lru_.crend());
 397   }
 398
 399  private:
 400   struct Node
 401     : public boost::intrusive::unordered_set_base_hook<link_mode>,
 402       public boost::intrusive::list_base_hook<link_mode> {
 403     Node(const TKey& key, TValue&& value)
 404         : pr(std::make_pair(key, std::move(value))) {
 405     }
 406     TPair pr;
 407     friend bool operator==(const Node& lhs, const Node& rhs) {
 408       return lhs.pr.first == rhs.pr.first;
 409     }
 410     friend std::size_t hash_value(const Node& node) {
 411       return THash()(node.pr.first);
 412     }
 413   };
 414
 415   struct KeyHasher {
 416     std::size_t operator()(const Node& node) {
 417       return THash()(node.pr.first);
 418     }
 419     std::size_t operator()(const TKey& key) {
 420       return THash()(key);
 421     }
 422   };
 423
 424   struct KeyValueEqual {
 425     bool operator()(const TKey& lhs, const Node& rhs) {
 426       return lhs == rhs.pr.first;
 427     }
 428     bool operator()(const Node& lhs, const TKey& rhs) {
 429       return lhs.pr.first == rhs;
 430     }
 431   };
 432
 433   /**
 434    * Get the iterator in in the index associated with a specific key. This is
 435    * merely a search in the index and does not promote the object.
 436    * @param key key to associate with value
 437    * @return the NodeMap::iterator to the Node containing the object
 438    *    (a std::pair of const TKey, TValue) or index_.end() if it does not exist
 439    */
 440   typename NodeMap::iterator findInIndex(const TKey& key) {
 441     return index_.find(key, KeyHasher(), KeyValueEqual());
 442   }
 443
 444   typename NodeMap::const_iterator findInIndex(const TKey& key) const {
 445     return index_.find(key, KeyHasher(), KeyValueEqual());
 446   }
 447
 448   /**
 449    * Prune the minimum of pruneSize and size() from the back of the LRU.
 450    * @param pruneSize minimum number of elements to prune
 451    * @param pruneHook a custom pruneHook function
 452    * @param failSafe true if exceptions are to ignored, false by default
 453    */
 454   void pruneWithFailSafeOption(std::size_t pruneSize,
 455     PruneHookCall pruneHook, bool failSafe) {
 456     auto& ph = (nullptr == pruneHook) ? pruneHook_ : pruneHook;
 457
 458     for (std::size_t i = 0; i < pruneSize && !lru_.empty(); i++) {
 459       auto *node = &(*lru_.rbegin());
 460       std::unique_ptr<Node> nptr(node);
 461
 462       lru_.erase(lru_.iterator_to(*node));
 463       index_.erase(index_.iterator_to(*node));
 464       if (ph) {
 465         try {
 466           ph(node->pr.first, std::move(node->pr.second));
 467         } catch (...) {
 468           if (!failSafe) {
 469             throw;
 470           }
 471         }
 472       }
 473     }
 474   }
 475
 476   static const std::size_t kMinNumIndexBuckets = 100;
 477   PruneHookCall pruneHook_;
 478   std::size_t nIndexBuckets_;
 479   std::unique_ptr<typename NodeMap::bucket_type[]> indexBuckets_;
 480   typename NodeMap::bucket_traits indexTraits_;
 481   NodeMap index_;
 482   NodeList lru_;
 483   std::size_t maxSize_;
 484   std::size_t clearSize_;
 485 };
 486
 487 } // folly
 488
 489 #endif /* FOLLY_EVICTINGHASHMAP_H_ */