userver: userver/cache/nway_lru_cache.hpp Source File
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages Concepts
nway_lru_cache.hpp
1#pragma once
2
3#include <functional>
4#include <optional>
5#include <vector>
6
7#include <boost/container_hash/hash.hpp>
8
9#include <userver/cache/lru_map.hpp>
10#include <userver/dump/dumper.hpp>
11#include <userver/dump/operations.hpp>
12#include <userver/engine/mutex.hpp>
13
14USERVER_NAMESPACE_BEGIN
15
16namespace cache {
17
18/// @ingroup userver_containers
19template <typename T, typename U, typename Hash = std::hash<T>, typename Equal = std::equal_to<T>>
20class NWayLRU final {
21public:
22 /// @param ways is the number of ways (a.k.a. shards, internal hash-maps),
23 /// into which elements are distributed based on their hash. Each shard is
24 /// protected by an individual mutex. Larger `ways` means more internal
25 /// hash-map instances and more memory usage, but less contention. A good
26 /// starting point is `ways=16`. If you encounter contention, you can increase
27 /// `ways` to something on the order of `256` or whatever your RAM constraints
28 /// allow.
29 ///
30 /// @param way_size is the maximum allowed amount of elements per way. When
31 /// the size of a way reaches this number, existing elements are deleted
32 /// according to the LRU policy.
33 ///
34 /// @param hash is the instance of `Hash` function to use, in case of a custom stateful `Hash`.
35 /// @param equal is the instance of `Equal` function to use, in case of a custom stateful `Equal`.
36 ///
37 /// The maximum total number of elements is `ways * way_size`.
38 NWayLRU(size_t ways, size_t way_size, const Hash& hash = Hash(), const Equal& equal = Equal());
39
40 void Put(const T& key, U value);
41
42 template <typename Validator>
43 std::optional<U> Get(const T& key, Validator validator);
44
45 std::optional<U> Get(const T& key) {
46 return Get(key, [](const U&) { return true; });
47 }
48
49 U GetOr(const T& key, const U& default_value);
50
51 void Invalidate();
52
53 void InvalidateByKey(const T& key);
54
55 /// Iterates over all items. May be slow for big caches.
56 template <typename Function>
57 void VisitAll(Function func) const;
58
59 size_t GetSize() const;
60
61 /// For the description of `way_size`,
62 /// see the cache::NWayLRU::NWayLRU constructor.
63 void UpdateWaySize(size_t way_size);
64
65 void Write(dump::Writer& writer) const;
66 void Read(dump::Reader& reader);
67
68 /// The dump::Dumper will be notified of any cache updates. This method is not
69 /// thread-safe.
70 void SetDumper(std::shared_ptr<dump::Dumper> dumper);
71
72private:
73 struct Way {
74 Way(Way&& other) noexcept : cache(std::move(other.cache)) {}
75
76 // max_size is not used, will be reset by Resize() in NWayLRU::NWayLRU
77 Way(const Hash& hash, const Equal& equal) : cache(1, hash, equal) {}
78
79 mutable engine::Mutex mutex;
80 LruMap<T, U, Hash, Equal> cache;
81 };
82
83 Way& GetWay(const T& key);
84
85 void NotifyDumper();
86
87 std::vector<Way> caches_;
88 Hash hash_fn_;
89 std::shared_ptr<dump::Dumper> dumper_{nullptr};
90};
91
92template <typename T, typename U, typename Hash, typename Eq>
93NWayLRU<T, U, Hash, Eq>::NWayLRU(size_t ways, size_t way_size, const Hash& hash, const Eq& equal)
94 : caches_(), hash_fn_(hash) {
95 caches_.reserve(ways);
96 for (size_t i = 0; i < ways; ++i) caches_.emplace_back(hash, equal);
97 if (ways == 0) throw std::logic_error("Ways must be positive");
98
99 for (auto& way : caches_) way.cache.SetMaxSize(way_size);
100}
101
102template <typename T, typename U, typename Hash, typename Eq>
103void NWayLRU<T, U, Hash, Eq>::Put(const T& key, U value) {
104 auto& way = GetWay(key);
105 {
106 std::unique_lock<engine::Mutex> lock(way.mutex);
107 way.cache.Put(key, std::move(value));
108 }
109 NotifyDumper();
110}
111
112template <typename T, typename U, typename Hash, typename Eq>
113template <typename Validator>
114std::optional<U> NWayLRU<T, U, Hash, Eq>::Get(const T& key, Validator validator) {
115 auto& way = GetWay(key);
116 std::unique_lock<engine::Mutex> lock(way.mutex);
117 auto* value = way.cache.Get(key);
118
119 if (value) {
120 if (validator(*value)) return *value;
121 way.cache.Erase(key);
122 }
123
124 return std::nullopt;
125}
126
127template <typename T, typename U, typename Hash, typename Eq>
128void NWayLRU<T, U, Hash, Eq>::InvalidateByKey(const T& key) {
129 auto& way = GetWay(key);
130 {
131 std::unique_lock<engine::Mutex> lock(way.mutex);
132 way.cache.Erase(key);
133 }
134 NotifyDumper();
135}
136
137template <typename T, typename U, typename Hash, typename Eq>
138U NWayLRU<T, U, Hash, Eq>::GetOr(const T& key, const U& default_value) {
139 auto& way = GetWay(key);
140 std::unique_lock<engine::Mutex> lock(way.mutex);
141 return way.cache.GetOr(key, default_value);
142}
143
144template <typename T, typename U, typename Hash, typename Eq>
145void NWayLRU<T, U, Hash, Eq>::Invalidate() {
146 for (auto& way : caches_) {
147 std::unique_lock<engine::Mutex> lock(way.mutex);
148 way.cache.Clear();
149 }
150 NotifyDumper();
151}
152
153template <typename T, typename U, typename Hash, typename Eq>
154template <typename Function>
155void NWayLRU<T, U, Hash, Eq>::VisitAll(Function func) const {
156 for (const auto& way : caches_) {
157 std::unique_lock<engine::Mutex> lock(way.mutex);
158 way.cache.VisitAll(func);
159 }
160}
161
162template <typename T, typename U, typename Hash, typename Eq>
163size_t NWayLRU<T, U, Hash, Eq>::GetSize() const {
164 size_t size{0};
165 for (const auto& way : caches_) {
166 std::unique_lock<engine::Mutex> lock(way.mutex);
167 size += way.cache.GetSize();
168 }
169 return size;
170}
171
172template <typename T, typename U, typename Hash, typename Eq>
173void NWayLRU<T, U, Hash, Eq>::UpdateWaySize(size_t way_size) {
174 for (auto& way : caches_) {
175 std::unique_lock<engine::Mutex> lock(way.mutex);
176 way.cache.SetMaxSize(way_size);
177 }
178}
179
180template <typename T, typename U, typename Hash, typename Eq>
181typename NWayLRU<T, U, Hash, Eq>::Way& NWayLRU<T, U, Hash, Eq>::GetWay(const T& key) {
182 /// It is needed to twist hash because there is hash map in LruMap. Otherwise
183 /// nodes will fall into one bucket. According to
184 /// https://www.boost.org/doc/libs/1_83_0/libs/container_hash/doc/html/hash.html#notes_hash_combine
185 /// hash_combine can be treated as hash itself
186 auto seed = hash_fn_(key);
187 boost::hash_combine(seed, 0);
188 auto n = seed % caches_.size();
189 return caches_[n];
190}
191
192template <typename T, typename U, typename Hash, typename Equal>
193void NWayLRU<T, U, Hash, Equal>::Write(dump::Writer& writer) const {
194 writer.Write(caches_.size());
195
196 for (const Way& way : caches_) {
197 std::unique_lock<engine::Mutex> lock(way.mutex);
198
199 writer.Write(way.cache.GetSize());
200
201 way.cache.VisitAll([&writer](const T& key, const U& value) {
202 writer.Write(key);
203 writer.Write(value);
204 });
205 }
206}
207
208template <typename T, typename U, typename Hash, typename Equal>
209void NWayLRU<T, U, Hash, Equal>::Read(dump::Reader& reader) {
210 Invalidate();
211
212 const auto ways = reader.Read<std::size_t>();
213 for (std::size_t i = 0; i < ways; ++i) {
214 const auto elements_in_way = reader.Read<std::size_t>();
215 for (std::size_t j = 0; j < elements_in_way; ++j) {
216 auto key = reader.Read<T>();
217 auto value = reader.Read<U>();
218 Put(std::move(key), std::move(value));
219 }
220 }
221}
222
223template <typename T, typename U, typename Hash, typename Equal>
224void NWayLRU<T, U, Hash, Equal>::NotifyDumper() {
225 if (dumper_ != nullptr) {
226 dumper_->OnUpdateCompleted();
227 }
228}
229
230template <typename T, typename U, typename Hash, typename Equal>
231void NWayLRU<T, U, Hash, Equal>::SetDumper(std::shared_ptr<dump::Dumper> dumper) {
232 dumper_ = std::move(dumper);
233}
234
235} // namespace cache
236
237USERVER_NAMESPACE_END