1 // Copyright (c) 2011-present, Facebook, Inc. All rights reserved.
2 // This source code is licensed under both the GPLv2 (found in the
3 // COPYING file in the root directory) and Apache 2.0 License
4 // (found in the LICENSE.Apache file in the root directory).
5
6 #include "utilities/simulator_cache/cache_simulator.h"
7 #include <algorithm>
8 #include "db/dbformat.h"
9
10 namespace ROCKSDB_NAMESPACE {
11
12 namespace {
13 const std::string kGhostCachePrefix = "ghost_";
14 } // namespace
15
GhostCache(std::shared_ptr<Cache> sim_cache)16 GhostCache::GhostCache(std::shared_ptr<Cache> sim_cache)
17 : sim_cache_(sim_cache) {}
18
Admit(const Slice & lookup_key)19 bool GhostCache::Admit(const Slice& lookup_key) {
20 auto handle = sim_cache_->Lookup(lookup_key);
21 if (handle != nullptr) {
22 sim_cache_->Release(handle);
23 return true;
24 }
25 sim_cache_->Insert(lookup_key, /*value=*/nullptr, lookup_key.size(),
26 /*deleter=*/nullptr);
27 return false;
28 }
29
CacheSimulator(std::unique_ptr<GhostCache> && ghost_cache,std::shared_ptr<Cache> sim_cache)30 CacheSimulator::CacheSimulator(std::unique_ptr<GhostCache>&& ghost_cache,
31 std::shared_ptr<Cache> sim_cache)
32 : ghost_cache_(std::move(ghost_cache)), sim_cache_(sim_cache) {}
33
Access(const BlockCacheTraceRecord & access)34 void CacheSimulator::Access(const BlockCacheTraceRecord& access) {
35 bool admit = true;
36 const bool is_user_access =
37 BlockCacheTraceHelper::IsUserAccess(access.caller);
38 bool is_cache_miss = true;
39 if (ghost_cache_ && access.no_insert == Boolean::kFalse) {
40 admit = ghost_cache_->Admit(access.block_key);
41 }
42 auto handle = sim_cache_->Lookup(access.block_key);
43 if (handle != nullptr) {
44 sim_cache_->Release(handle);
45 is_cache_miss = false;
46 } else {
47 if (access.no_insert == Boolean::kFalse && admit && access.block_size > 0) {
48 sim_cache_->Insert(access.block_key, /*value=*/nullptr, access.block_size,
49 /*deleter=*/nullptr);
50 }
51 }
52 miss_ratio_stats_.UpdateMetrics(access.access_timestamp, is_user_access,
53 is_cache_miss);
54 }
55
UpdateMetrics(uint64_t timestamp_in_ms,bool is_user_access,bool is_cache_miss)56 void MissRatioStats::UpdateMetrics(uint64_t timestamp_in_ms,
57 bool is_user_access, bool is_cache_miss) {
58 uint64_t timestamp_in_seconds = timestamp_in_ms / kMicrosInSecond;
59 num_accesses_timeline_[timestamp_in_seconds] += 1;
60 num_accesses_ += 1;
61 if (num_misses_timeline_.find(timestamp_in_seconds) ==
62 num_misses_timeline_.end()) {
63 num_misses_timeline_[timestamp_in_seconds] = 0;
64 }
65 if (is_cache_miss) {
66 num_misses_ += 1;
67 num_misses_timeline_[timestamp_in_seconds] += 1;
68 }
69 if (is_user_access) {
70 user_accesses_ += 1;
71 if (is_cache_miss) {
72 user_misses_ += 1;
73 }
74 }
75 }
76
ComputeBlockPriority(const BlockCacheTraceRecord & access) const77 Cache::Priority PrioritizedCacheSimulator::ComputeBlockPriority(
78 const BlockCacheTraceRecord& access) const {
79 if (access.block_type == TraceType::kBlockTraceFilterBlock ||
80 access.block_type == TraceType::kBlockTraceIndexBlock ||
81 access.block_type == TraceType::kBlockTraceUncompressionDictBlock) {
82 return Cache::Priority::HIGH;
83 }
84 return Cache::Priority::LOW;
85 }
86
AccessKVPair(const Slice & key,uint64_t value_size,Cache::Priority priority,const BlockCacheTraceRecord & access,bool no_insert,bool is_user_access,bool * is_cache_miss,bool * admitted,bool update_metrics)87 void PrioritizedCacheSimulator::AccessKVPair(
88 const Slice& key, uint64_t value_size, Cache::Priority priority,
89 const BlockCacheTraceRecord& access, bool no_insert, bool is_user_access,
90 bool* is_cache_miss, bool* admitted, bool update_metrics) {
91 assert(is_cache_miss);
92 assert(admitted);
93 *is_cache_miss = true;
94 *admitted = true;
95 if (ghost_cache_ && !no_insert) {
96 *admitted = ghost_cache_->Admit(key);
97 }
98 auto handle = sim_cache_->Lookup(key);
99 if (handle != nullptr) {
100 sim_cache_->Release(handle);
101 *is_cache_miss = false;
102 } else if (!no_insert && *admitted && value_size > 0) {
103 sim_cache_->Insert(key, /*value=*/nullptr, value_size, /*deleter=*/nullptr,
104 /*handle=*/nullptr, priority);
105 }
106 if (update_metrics) {
107 miss_ratio_stats_.UpdateMetrics(access.access_timestamp, is_user_access,
108 *is_cache_miss);
109 }
110 }
111
Access(const BlockCacheTraceRecord & access)112 void PrioritizedCacheSimulator::Access(const BlockCacheTraceRecord& access) {
113 bool is_cache_miss = true;
114 bool admitted = true;
115 AccessKVPair(access.block_key, access.block_size,
116 ComputeBlockPriority(access), access, access.no_insert,
117 BlockCacheTraceHelper::IsUserAccess(access.caller),
118 &is_cache_miss, &admitted, /*update_metrics=*/true);
119 }
120
Access(const BlockCacheTraceRecord & access)121 void HybridRowBlockCacheSimulator::Access(const BlockCacheTraceRecord& access) {
122 // TODO (haoyu): We only support Get for now. We need to extend the tracing
123 // for MultiGet, i.e., non-data block accesses must log all keys in a
124 // MultiGet.
125 bool is_cache_miss = true;
126 bool admitted = false;
127 if (access.caller == TableReaderCaller::kUserGet &&
128 access.get_id != BlockCacheTraceHelper::kReservedGetId) {
129 // This is a Get request.
130 const std::string& row_key = BlockCacheTraceHelper::ComputeRowKey(access);
131 GetRequestStatus& status = getid_status_map_[access.get_id];
132 if (status.is_complete) {
133 // This Get request completes.
134 // Skip future accesses to its index/filter/data
135 // blocks. These block lookups are unnecessary if we observe a hit for the
136 // referenced key-value pair already. Thus, we treat these lookups as
137 // hits. This is also to ensure the total number of accesses are the same
138 // when comparing to other policies.
139 miss_ratio_stats_.UpdateMetrics(access.access_timestamp,
140 /*is_user_access=*/true,
141 /*is_cache_miss=*/false);
142 return;
143 }
144 if (status.row_key_status.find(row_key) == status.row_key_status.end()) {
145 // This is the first time that this key is accessed. Look up the key-value
146 // pair first. Do not update the miss/accesses metrics here since it will
147 // be updated later.
148 AccessKVPair(row_key, access.referenced_data_size, Cache::Priority::HIGH,
149 access,
150 /*no_insert=*/false,
151 /*is_user_access=*/true, &is_cache_miss, &admitted,
152 /*update_metrics=*/false);
153 InsertResult result = InsertResult::NO_INSERT;
154 if (admitted && access.referenced_data_size > 0) {
155 result = InsertResult::INSERTED;
156 } else if (admitted) {
157 result = InsertResult::ADMITTED;
158 }
159 status.row_key_status[row_key] = result;
160 }
161 if (!is_cache_miss) {
162 // A cache hit.
163 status.is_complete = true;
164 miss_ratio_stats_.UpdateMetrics(access.access_timestamp,
165 /*is_user_access=*/true,
166 /*is_cache_miss=*/false);
167 return;
168 }
169 // The row key-value pair observes a cache miss. We need to access its
170 // index/filter/data blocks.
171 InsertResult inserted = status.row_key_status[row_key];
172 AccessKVPair(
173 access.block_key, access.block_size, ComputeBlockPriority(access),
174 access,
175 /*no_insert=*/!insert_blocks_upon_row_kvpair_miss_ || access.no_insert,
176 /*is_user_access=*/true, &is_cache_miss, &admitted,
177 /*update_metrics=*/true);
178 if (access.referenced_data_size > 0 && inserted == InsertResult::ADMITTED) {
179 sim_cache_->Insert(row_key, /*value=*/nullptr,
180 access.referenced_data_size, /*deleter=*/nullptr,
181 /*handle=*/nullptr, Cache::Priority::HIGH);
182 status.row_key_status[row_key] = InsertResult::INSERTED;
183 }
184 return;
185 }
186 AccessKVPair(access.block_key, access.block_size,
187 ComputeBlockPriority(access), access, access.no_insert,
188 BlockCacheTraceHelper::IsUserAccess(access.caller),
189 &is_cache_miss, &admitted, /*update_metrics=*/true);
190 }
191
BlockCacheTraceSimulator(uint64_t warmup_seconds,uint32_t downsample_ratio,const std::vector<CacheConfiguration> & cache_configurations)192 BlockCacheTraceSimulator::BlockCacheTraceSimulator(
193 uint64_t warmup_seconds, uint32_t downsample_ratio,
194 const std::vector<CacheConfiguration>& cache_configurations)
195 : warmup_seconds_(warmup_seconds),
196 downsample_ratio_(downsample_ratio),
197 cache_configurations_(cache_configurations) {}
198
InitializeCaches()199 Status BlockCacheTraceSimulator::InitializeCaches() {
200 for (auto const& config : cache_configurations_) {
201 for (auto cache_capacity : config.cache_capacities) {
202 // Scale down the cache capacity since the trace contains accesses on
203 // 1/'downsample_ratio' blocks.
204 uint64_t simulate_cache_capacity = cache_capacity / downsample_ratio_;
205 std::shared_ptr<CacheSimulator> sim_cache;
206 std::unique_ptr<GhostCache> ghost_cache;
207 std::string cache_name = config.cache_name;
208 if (cache_name.find(kGhostCachePrefix) != std::string::npos) {
209 ghost_cache.reset(new GhostCache(
210 NewLRUCache(config.ghost_cache_capacity, /*num_shard_bits=*/1,
211 /*strict_capacity_limit=*/false,
212 /*high_pri_pool_ratio=*/0)));
213 cache_name = cache_name.substr(kGhostCachePrefix.size());
214 }
215 if (cache_name == "lru") {
216 sim_cache = std::make_shared<CacheSimulator>(
217 std::move(ghost_cache),
218 NewLRUCache(simulate_cache_capacity, config.num_shard_bits,
219 /*strict_capacity_limit=*/false,
220 /*high_pri_pool_ratio=*/0));
221 } else if (cache_name == "lru_priority") {
222 sim_cache = std::make_shared<PrioritizedCacheSimulator>(
223 std::move(ghost_cache),
224 NewLRUCache(simulate_cache_capacity, config.num_shard_bits,
225 /*strict_capacity_limit=*/false,
226 /*high_pri_pool_ratio=*/0.5));
227 } else if (cache_name == "lru_hybrid") {
228 sim_cache = std::make_shared<HybridRowBlockCacheSimulator>(
229 std::move(ghost_cache),
230 NewLRUCache(simulate_cache_capacity, config.num_shard_bits,
231 /*strict_capacity_limit=*/false,
232 /*high_pri_pool_ratio=*/0.5),
233 /*insert_blocks_upon_row_kvpair_miss=*/true);
234 } else if (cache_name == "lru_hybrid_no_insert_on_row_miss") {
235 sim_cache = std::make_shared<HybridRowBlockCacheSimulator>(
236 std::move(ghost_cache),
237 NewLRUCache(simulate_cache_capacity, config.num_shard_bits,
238 /*strict_capacity_limit=*/false,
239 /*high_pri_pool_ratio=*/0.5),
240 /*insert_blocks_upon_row_kvpair_miss=*/false);
241 } else {
242 // Not supported.
243 return Status::InvalidArgument("Unknown cache name " +
244 config.cache_name);
245 }
246 sim_caches_[config].push_back(sim_cache);
247 }
248 }
249 return Status::OK();
250 }
251
Access(const BlockCacheTraceRecord & access)252 void BlockCacheTraceSimulator::Access(const BlockCacheTraceRecord& access) {
253 if (trace_start_time_ == 0) {
254 trace_start_time_ = access.access_timestamp;
255 }
256 // access.access_timestamp is in microseconds.
257 if (!warmup_complete_ &&
258 trace_start_time_ + warmup_seconds_ * kMicrosInSecond <=
259 access.access_timestamp) {
260 for (auto& config_caches : sim_caches_) {
261 for (auto& sim_cache : config_caches.second) {
262 sim_cache->reset_counter();
263 }
264 }
265 warmup_complete_ = true;
266 }
267 for (auto& config_caches : sim_caches_) {
268 for (auto& sim_cache : config_caches.second) {
269 sim_cache->Access(access);
270 }
271 }
272 }
273
274 } // namespace ROCKSDB_NAMESPACE
275