userver: userver/cache/expirable_lru_cache.hpp Source File
Loading...
Searching...
No Matches
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