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