userver: userver/cache/expirable_lru_cache.hpp Source File
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages Concepts
expirable_lru_cache.hpp
Go to the documentation of this file.
1#pragma once
2
3/// @file userver/cache/expirable_lru_cache.hpp
4/// @brief @copybrief cache::ExpirableLruCache
5
6#include <atomic>
7#include <chrono>
8#include <optional>
9
10#include <userver/cache/lru_cache_config.hpp>
11#include <userver/cache/lru_cache_statistics.hpp>
12#include <userver/cache/nway_lru_cache.hpp>
13#include <userver/concurrent/mutex_set.hpp>
14#include <userver/dump/common.hpp>
15#include <userver/dump/dumper.hpp>
16#include <userver/engine/async.hpp>
17#include <userver/utils/datetime.hpp>
18#include <userver/utils/impl/cached_time.hpp>
19#include <userver/utils/impl/wait_token_storage.hpp>
20#include <userver/utils/statistics/writer.hpp>
21
22USERVER_NAMESPACE_BEGIN
23
24namespace cache {
25
26namespace impl {
27
28template <typename Value>
29struct ExpirableValue final {
30 Value value;
31 std::chrono::steady_clock::time_point update_time;
32};
33
34template <typename Value>
35void Write(dump::Writer& writer, const impl::ExpirableValue<Value>& value) {
36 const auto [now, steady_now] = utils::impl::GetGlobalTime();
37 writer.Write(value.value);
38 writer.Write(value.update_time - steady_now + now);
39}
40
41template <typename Value>
42impl::ExpirableValue<Value> Read(dump::Reader& reader, dump::To<impl::ExpirableValue<Value>>) {
43 const auto [now, steady_now] = utils::impl::GetGlobalTime();
44 // Evaluation order of arguments is guaranteed in brace-initialization.
45 return impl::ExpirableValue<Value>{
46 reader.Read<Value>(), reader.Read<std::chrono::system_clock::time_point>() - now + steady_now};
47}
48
49} // namespace impl
50
51/// @ingroup userver_containers
52/// @brief Class for expirable LRU cache. Use cache::LruMap for not expirable
53/// LRU Cache.
54///
55/// Example usage:
56///
57/// @snippet cache/expirable_lru_cache_test.cpp Sample ExpirableLruCache
58template <typename Key, typename Value, typename Hash = std::hash<Key>, typename Equal = std::equal_to<Key>>
59class ExpirableLruCache final {
60public:
61 using UpdateValueFunc = std::function<Value(const Key&)>;
62
63 /// Cache read mode
64 enum class ReadMode {
65 kSkipCache, ///< Do not cache value got from update function
66 kUseCache, ///< Cache value got from update function
67 };
68
69 /// For the description of `ways` and `way_size`,
70 /// see the cache::NWayLRU::NWayLRU constructor.
71 ExpirableLruCache(size_t ways, size_t way_size, const Hash& hash = Hash(), const Equal& equal = Equal());
72
73 ~ExpirableLruCache();
74
75 /// For the description of `way_size`,
76 /// see the cache::NWayLRU::NWayLRU constructor.
77 void SetWaySize(size_t way_size);
78
79 std::chrono::milliseconds GetMaxLifetime() const noexcept;
80
81 void SetMaxLifetime(std::chrono::milliseconds max_lifetime);
82
83 /**
84 * Sets background update mode. If "background_update" mode is kDisabled,
85 * expiring values are not updated in background (asynchronously) or are
86 * updated if "background_update" is kEnabled.
87 */
88 void SetBackgroundUpdate(BackgroundUpdateMode background_update);
89
90 /**
91 * @returns GetOptional("key", update_func) if it is not std::nullopt.
92 * Otherwise the result of update_func(key) is returned, and additionally
93 * stored in cache if "read_mode" is kUseCache.
94 */
95 Value Get(const Key& key, const UpdateValueFunc& update_func, ReadMode read_mode = ReadMode::kUseCache);
96
97 /**
98 * Update value in cache by "update_func" if background update mode is
99 * kEnabled and "key" is in cache and not expired but its lifetime ends soon.
100 * @returns value by key if key is in cache and not expired, or std::nullopt
101 * otherwise
102 */
103 std::optional<Value> GetOptional(const Key& key, const UpdateValueFunc& update_func);
104
105 /**
106 * GetOptional, but without expiry checks and value updates.
107 *
108 * Used during fallback in FallbackELruCache.
109 */
110 std::optional<Value> GetOptionalUnexpirable(const Key& key);
111
112 /**
113 * GetOptional, but without expiry check.
114 *
115 * Used during fallback in FallbackELruCache.
116 */
117 std::optional<Value> GetOptionalUnexpirableWithUpdate(const Key& key, const UpdateValueFunc& update_func);
118
119 /**
120 * GetOptional, but without value updates.
121 */
122 std::optional<Value> GetOptionalNoUpdate(const Key& key);
123
124 void Put(const Key& key, const Value& value);
125
126 void Put(const Key& key, Value&& value);
127
128 const impl::ExpirableLruCacheStatistics& GetStatistics() const;
129
130 size_t GetSizeApproximate() const;
131
132 /// Clear cache
134
135 /// Erase key from cache
136 void InvalidateByKey(const Key& key);
137
138 /// Erase key from cache conditionally
139 template <typename Predicate>
140 void InvalidateByKeyIf(const Key& key, Predicate pred);
141
142 /// Add async task for updating value by update_func(key)
143 void UpdateInBackground(const Key& key, UpdateValueFunc update_func);
144
145 void Write(dump::Writer& writer) const;
146
147 void Read(dump::Reader& reader);
148
149 /// The dump::Dumper will be notified of any cache updates. This method is not
150 /// thread-safe.
151 void SetDumper(std::shared_ptr<dump::Dumper> dumper);
152
153private:
154 bool IsExpired(std::chrono::steady_clock::time_point update_time, std::chrono::steady_clock::time_point now) const;
155
156 bool ShouldUpdate(std::chrono::steady_clock::time_point update_time, std::chrono::steady_clock::time_point now)
157 const;
158
159 cache::NWayLRU<Key, impl::ExpirableValue<Value>, Hash, Equal> lru_;
160 std::atomic<std::chrono::milliseconds> max_lifetime_{std::chrono::milliseconds(0)};
161 std::atomic<BackgroundUpdateMode> background_update_mode_{BackgroundUpdateMode::kDisabled};
162 impl::ExpirableLruCacheStatistics stats_;
163 concurrent::MutexSet<Key, Hash, Equal> mutex_set_;
164 utils::impl::WaitTokenStorage wait_token_storage_;
165};
166
167template <typename Key, typename Value, typename Hash, typename Equal>
168ExpirableLruCache<Key, Value, Hash, Equal>::ExpirableLruCache(
169 size_t ways,
170 size_t way_size,
171 const Hash& hash,
172 const Equal& equal
173)
174 : lru_(ways, way_size, hash, equal), mutex_set_{ways, way_size, hash, equal} {}
175
176template <typename Key, typename Value, typename Hash, typename Equal>
177ExpirableLruCache<Key, Value, Hash, Equal>::~ExpirableLruCache() {
178 wait_token_storage_.WaitForAllTokens();
179}
180
181template <typename Key, typename Value, typename Hash, typename Equal>
182void ExpirableLruCache<Key, Value, Hash, Equal>::SetWaySize(size_t way_size) {
183 lru_.UpdateWaySize(way_size);
184}
185
186template <typename Key, typename Value, typename Hash, typename Equal>
187std::chrono::milliseconds ExpirableLruCache<Key, Value, Hash, Equal>::GetMaxLifetime() const noexcept {
188 return max_lifetime_.load();
189}
190
191template <typename Key, typename Value, typename Hash, typename Equal>
192void ExpirableLruCache<Key, Value, Hash, Equal>::SetMaxLifetime(std::chrono::milliseconds max_lifetime) {
193 max_lifetime_ = max_lifetime;
194}
195
196template <typename Key, typename Value, typename Hash, typename Equal>
197void ExpirableLruCache<Key, Value, Hash, Equal>::SetBackgroundUpdate(BackgroundUpdateMode background_update) {
198 background_update_mode_ = background_update;
199}
200
201template <typename Key, typename Value, typename Hash, typename Equal>
202Value ExpirableLruCache<Key, Value, Hash, Equal>::Get(
203 const Key& key,
204 const UpdateValueFunc& update_func,
205 ReadMode read_mode
206) {
208 auto opt_old_value = GetOptional(key, update_func);
209 if (opt_old_value) {
210 return std::move(*opt_old_value);
211 }
212
213 auto mutex = mutex_set_.GetMutexForKey(key);
214 std::lock_guard lock(mutex);
215 // Test one more time - concurrent ExpirableLruCache::Get()
216 // might have put the value
217 auto old_value = lru_.Get(key);
218 if (old_value && !IsExpired(old_value->update_time, now)) {
219 return std::move(old_value->value);
220 }
221
222 auto value = update_func(key);
223 if (read_mode == ReadMode::kUseCache) {
224 lru_.Put(key, {value, now});
225 }
226 return value;
227}
228
229template <typename Key, typename Value, typename Hash, typename Equal>
230std::optional<Value>
231ExpirableLruCache<Key, Value, Hash, Equal>::GetOptional(const Key& key, const UpdateValueFunc& update_func) {
233 auto old_value = lru_.Get(key);
234
235 if (old_value) {
236 if (!IsExpired(old_value->update_time, now)) {
237 impl::CacheHit(stats_);
238
239 if (ShouldUpdate(old_value->update_time, now)) {
240 UpdateInBackground(key, update_func);
241 }
242
243 return std::move(old_value->value);
244 } else {
245 impl::CacheStale(stats_);
246 }
247 }
248 impl::CacheMiss(stats_);
249
250 return std::nullopt;
251}
252
253template <typename Key, typename Value, typename Hash, typename Equal>
254std::optional<Value> ExpirableLruCache<Key, Value, Hash, Equal>::GetOptionalUnexpirable(const Key& key) {
255 auto old_value = lru_.Get(key);
256
257 if (old_value) {
258 impl::CacheHit(stats_);
259 return old_value->value;
260 }
261 impl::CacheMiss(stats_);
262
263 return std::nullopt;
264}
265
266template <typename Key, typename Value, typename Hash, typename Equal>
267std::optional<Value> ExpirableLruCache<Key, Value, Hash, Equal>::GetOptionalUnexpirableWithUpdate(
268 const Key& key,
269 const UpdateValueFunc& update_func
270) {
272 auto old_value = lru_.Get(key);
273
274 if (old_value) {
275 impl::CacheHit(stats_);
276
277 if (ShouldUpdate(old_value->update_time, now)) {
278 UpdateInBackground(key, update_func);
279 }
280
281 return old_value->value;
282 }
283 impl::CacheMiss(stats_);
284
285 return std::nullopt;
286}
287
288template <typename Key, typename Value, typename Hash, typename Equal>
289std::optional<Value> ExpirableLruCache<Key, Value, Hash, Equal>::GetOptionalNoUpdate(const Key& key) {
291 auto old_value = lru_.Get(key);
292
293 if (old_value) {
294 if (!IsExpired(old_value->update_time, now)) {
295 impl::CacheHit(stats_);
296
297 return old_value->value;
298 } else {
299 impl::CacheStale(stats_);
300 }
301 }
302 impl::CacheMiss(stats_);
303
304 return std::nullopt;
305}
306
307template <typename Key, typename Value, typename Hash, typename Equal>
308void ExpirableLruCache<Key, Value, Hash, Equal>::Put(const Key& key, const Value& value) {
309 lru_.Put(key, {value, utils::datetime::SteadyNow()});
310}
311
312template <typename Key, typename Value, typename Hash, typename Equal>
313void ExpirableLruCache<Key, Value, Hash, Equal>::Put(const Key& key, Value&& value) {
314 lru_.Put(key, {std::move(value), utils::datetime::SteadyNow()});
315}
316
317template <typename Key, typename Value, typename Hash, typename Equal>
318const impl::ExpirableLruCacheStatistics& ExpirableLruCache<Key, Value, Hash, Equal>::GetStatistics() const {
319 return stats_;
320}
321
322template <typename Key, typename Value, typename Hash, typename Equal>
323size_t ExpirableLruCache<Key, Value, Hash, Equal>::GetSizeApproximate() const {
324 return lru_.GetSize();
325}
326
327template <typename Key, typename Value, typename Hash, typename Equal>
328void ExpirableLruCache<Key, Value, Hash, Equal>::Invalidate() {
329 lru_.Invalidate();
330}
331
332template <typename Key, typename Value, typename Hash, typename Equal>
333void ExpirableLruCache<Key, Value, Hash, Equal>::InvalidateByKey(const Key& key) {
334 lru_.InvalidateByKey(key);
335}
336
337template <typename Key, typename Value, typename Hash, typename Equal>
338template <typename Predicate>
339void ExpirableLruCache<Key, Value, Hash, Equal>::InvalidateByKeyIf(const Key& key, Predicate pred) {
341
342 auto mutex = mutex_set_.GetMutexForKey(key);
343 std::lock_guard lock(mutex);
344 const auto cur_value = lru_.Get(key);
345
346 if (cur_value.has_value() && !IsExpired(cur_value->update_time, now) && pred(cur_value->value)) {
348 }
349}
350
351template <typename Key, typename Value, typename Hash, typename Equal>
352void ExpirableLruCache<Key, Value, Hash, Equal>::UpdateInBackground(const Key& key, UpdateValueFunc update_func) {
353 impl::CacheBackgroundUpdate(stats_);
354
355 // cache will wait for all detached tasks in ~ExpirableLruCache()
356 engine::AsyncNoSpan([token = wait_token_storage_.GetToken(), this, key, update_func = std::move(update_func)] {
357 auto mutex = mutex_set_.GetMutexForKey(key);
358 std::unique_lock lock(mutex, std::try_to_lock);
359 if (!lock) {
360 // someone is updating the key right now
361 return;
362 }
363
365 auto value = update_func(key);
366 lru_.Put(key, {value, now});
367 }).Detach();
368}
369
370template <typename Key, typename Value, typename Hash, typename Equal>
371bool ExpirableLruCache<Key, Value, Hash, Equal>::IsExpired(
372 std::chrono::steady_clock::time_point update_time,
373 std::chrono::steady_clock::time_point now
374) const {
375 auto max_lifetime = max_lifetime_.load();
376 return max_lifetime.count() != 0 && update_time + max_lifetime < now;
377}
378
379template <typename Key, typename Value, typename Hash, typename Equal>
380bool ExpirableLruCache<Key, Value, Hash, Equal>::ShouldUpdate(
381 std::chrono::steady_clock::time_point update_time,
382 std::chrono::steady_clock::time_point now
383) const {
384 auto max_lifetime = max_lifetime_.load();
385 return (background_update_mode_.load() == BackgroundUpdateMode::kEnabled) && max_lifetime.count() != 0 &&
386 update_time + max_lifetime / 2 < now;
387}
388
389template <typename Key, typename Value, typename Hash = std::hash<Key>, typename Equal = std::equal_to<Key>>
390class LruCacheWrapper final {
391public:
392 using Cache = ExpirableLruCache<Key, Value, Hash, Equal>;
393 using ReadMode = typename Cache::ReadMode;
394
395 LruCacheWrapper(std::shared_ptr<Cache> cache, typename Cache::UpdateValueFunc update_func)
396 : cache_(std::move(cache)), update_func_(std::move(update_func)) {}
397
398 /// Get cached value or evaluates if "key" is missing in cache
399 Value Get(const Key& key, ReadMode read_mode = ReadMode::kUseCache) {
400 return cache_->Get(key, update_func_, read_mode);
401 }
402
403 /// Get cached value or "nullopt" if "key" is missing in cache
404 std::optional<Value> GetOptional(const Key& key) { return cache_->GetOptional(key, update_func_); }
405
406 void InvalidateByKey(const Key& key) { cache_->InvalidateByKey(key); }
407
408 template <typename Predicate>
409 void InvalidateByKeyIf(const Key& key, Predicate pred) {
410 cache_->InvalidateByKeyIf(key, pred);
411 }
412
413 /// Update cached value in background
414 void UpdateInBackground(const Key& key) { cache_->UpdateInBackground(key, update_func_); }
415
416 /// Get raw cache. For internal use.
417 std::shared_ptr<Cache> GetCache() { return cache_; }
418
419private:
420 std::shared_ptr<Cache> cache_;
421 typename Cache::UpdateValueFunc update_func_;
422};
423
424template <typename Key, typename Value, typename Hash, typename Equal>
425void ExpirableLruCache<Key, Value, Hash, Equal>::Write(dump::Writer& writer) const {
426 utils::impl::UpdateGlobalTime();
427 lru_.Write(writer);
428}
429
430template <typename Key, typename Value, typename Hash, typename Equal>
431void ExpirableLruCache<Key, Value, Hash, Equal>::Read(dump::Reader& reader) {
432 utils::impl::UpdateGlobalTime();
433 lru_.Read(reader);
434}
435
436template <typename Key, typename Value, typename Hash, typename Equal>
437void ExpirableLruCache<Key, Value, Hash, Equal>::SetDumper(std::shared_ptr<dump::Dumper> dumper) {
438 lru_.SetDumper(std::move(dumper));
439}
440
441template <typename Key, typename Value, typename Hash, typename Equal>
442void DumpMetric(utils::statistics::Writer& writer, const ExpirableLruCache<Key, Value, Hash, Equal>& cache) {
443 writer["current-documents-count"] = cache.GetSizeApproximate();
444 writer = cache.GetStatistics();
445}
446
447} // namespace cache
448
449USERVER_NAMESPACE_END