1 /** 2 * Copyright 2022 Huawei Technologies Co., Ltd 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 MINDSPORE_CCSRC_DISTRIBUTED_EMBEDDING_CACHE_CACHE_STRATEGY_LRU_CHCHE_H_ 18 #define MINDSPORE_CCSRC_DISTRIBUTED_EMBEDDING_CACHE_CACHE_STRATEGY_LRU_CHCHE_H_ 19 20 #include <list> 21 #include <vector> 22 #include <utility> 23 #include <functional> 24 25 #include "distributed/embedding_cache/cache_strategy/cache.h" 26 #include "utils/hash_map.h" 27 #include "utils/log_adapter.h" 28 29 namespace mindspore { 30 namespace distributed { 31 // This class implements a common LRU (least recently used) caching strategy, with the idea that "if data has been 32 // accessed recently, it is more likely to be accessed in the future." 33 // The LRUCache implementation uses a linked list to hold elements and a hash table to quickly find the location of an 34 // element in linked list. 35 template <typename KeyType, typename ValueType, typename Hash = std::hash<KeyType>, 36 typename KeyEqual = std::equal_to<KeyType>> 37 class LRUCache : public Cache<KeyType, ValueType> { 38 public: 39 // The elements in cache are stored as key-value pairs. 40 using Element = typename Cache<KeyType, ValueType>::Element; 41 // The Iter type is the iterator type of the linked list. 42 using Iter = typename std::list<Element>::iterator; 43 LRUCache(size_t capacity)44 explicit LRUCache(size_t capacity) : Cache<KeyType, ValueType>(capacity) {} 45 ~LRUCache()46 ~LRUCache() override { 47 elements_.clear(); 48 element_keys_to_iters_.clear(); 49 } 50 51 // Insert an element (key-value pair) into the lru cache. 52 // The newly inserted element is considered hot data and will be placed at the head of the linked list, because this 53 // element may have been replaced from a higher level cache. Put(const KeyType & key,const ValueType & value)54 void Put(const KeyType &key, const ValueType &value) override { 55 const auto &iter = element_keys_to_iters_.find(key); 56 // The key exist in lru cache, move this element to the head of list. 57 if (iter != element_keys_to_iters_.end()) { 58 elements_.splice(elements_.begin(), elements_, iter->second); 59 // Update value. 60 elements_.begin()->second = value; 61 return; 62 } 63 64 if (IsFull()) { 65 MS_LOG(EXCEPTION) << "There is no space in lru cache."; 66 } 67 68 // The key does not exist in lru cache, insert this new element at the head of list. 69 elements_.emplace_front(key, value); 70 (void)element_keys_to_iters_.emplace(key, elements_.begin()); 71 } 72 73 // Query the corresponding Value from the cache according to the Key. If the element exists, the corresponding Value 74 // is assigned to parameter value and return true. If the element does not exist, return false. 75 // The newly accessed element is moved to the head of the list, indicating that it was recently accessed. Get(const KeyType & key,ValueType * value)76 bool Get(const KeyType &key, ValueType *value) override { 77 const auto &iter = element_keys_to_iters_.find(key); 78 if (iter != element_keys_to_iters_.end()) { 79 // For performance, no element was constructed or destroyed. 80 elements_.splice(elements_.begin(), elements_, iter->second); 81 MS_EXCEPTION_IF_NULL(value); 82 *value = iter->second->second; 83 return true; 84 } 85 return false; 86 } 87 88 // Get the most recently used element. Front()89 const Element &Front() const override { 90 if (elements_.empty()) { 91 MS_LOG(EXCEPTION) << "There is no element in lru cache."; 92 } 93 return elements_.front(); 94 } 95 96 // Get the least recently used element. Back()97 const Element &Back() const override { 98 if (elements_.empty()) { 99 MS_LOG(EXCEPTION) << "There is no element in lru cache."; 100 } 101 return elements_.back(); 102 } 103 104 // Query whether the element corresponding to a particular key exists in the cache. Exists(const KeyType & key)105 bool Exists(const KeyType &key) const override { 106 return element_keys_to_iters_.find(key) != element_keys_to_iters_.end(); 107 } 108 109 // When the size of the cache is close to capacity, you can use this interface to evict some non-hot data to reserve 110 // space for new elements to be inserted into the cache. If the current cache has enough free space, this function 111 // does nothing. 112 // The input parameter 'reserve_size' indicates the number of element slots that are expected to be reserved. If the 113 // reserve_size is less than or equal to the number of slots remaining in the cache, the function does nothing. 114 // The output parameter 'evicted_elements' is used to hold the evicted element. TryEvict(size_t reserve_size,std::vector<Element> * evicted_elements)115 void TryEvict(size_t reserve_size, std::vector<Element> *evicted_elements) override { 116 MS_EXCEPTION_IF_NULL(evicted_elements); 117 const auto &capacity = Cache<KeyType, ValueType>::capacity(); 118 if (reserve_size > capacity) { 119 MS_LOG(EXCEPTION) << "The evict number must be less or equal to lru cache capacity: " << capacity 120 << ", but got: " << reserve_size; 121 } 122 123 while (size() > capacity - reserve_size) { 124 const auto &back_element = elements_.back(); 125 evicted_elements->emplace_back(back_element.first, back_element.second); 126 (void)element_keys_to_iters_.erase(back_element.first); 127 elements_.pop_back(); 128 } 129 } 130 131 // Check whether the number of elements in cache reaches capacity. IsFull()132 bool IsFull() const override { return size() >= Cache<KeyType, ValueType>::capacity(); } 133 134 // Get the current number of elements in the cache. size()135 size_t size() const override { return element_keys_to_iters_.size(); } 136 137 // Dump all elements in the lru cache. Export()138 const std::list<Element> &Export() const override { return elements_; } 139 140 private: 141 // The linked list used to hold elements. 142 std::list<Element> elements_; 143 144 // The hash table used to quickly find the location of an element in linked list. 145 mindspore::HashMap<KeyType, Iter, Hash, KeyEqual> element_keys_to_iters_; 146 }; 147 } // namespace distributed 148 } // namespace mindspore 149 #endif // MINDSPORE_CCSRC_DISTRIBUTED_EMBEDDING_CACHE_CACHE_STRATEGY_LRU_CHCHE_H_ 150