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 #ifndef ROCKSDB_LITE
7 #ifdef GFLAGS
8 #include "tools/block_cache_analyzer/block_cache_trace_analyzer.h"
9
10 #include <algorithm>
11 #include <cinttypes>
12 #include <cstdio>
13 #include <cstdlib>
14 #include <fstream>
15 #include <iomanip>
16 #include <iostream>
17 #include <memory>
18 #include <random>
19 #include <sstream>
20
21 #include "monitoring/histogram.h"
22 #include "rocksdb/system_clock.h"
23 #include "util/gflags_compat.h"
24 #include "util/string_util.h"
25
26 using GFLAGS_NAMESPACE::ParseCommandLineFlags;
27
28 DEFINE_string(block_cache_trace_path, "", "The trace file path.");
29 DEFINE_bool(is_block_cache_human_readable_trace, false,
30 "Is the trace file provided for analysis generated by running "
31 "block_cache_trace_analyzer with "
32 "FLAGS_human_readable_trace_file_path is specified.");
33 DEFINE_string(
34 block_cache_sim_config_path, "",
35 "The config file path. One cache configuration per line. The format of a "
36 "cache configuration is "
37 "cache_name,num_shard_bits,ghost_capacity,cache_capacity_1,...,cache_"
38 "capacity_N. Supported cache names are lru, lru_priority, lru_hybrid, and "
39 "lru_hybrid_no_insert_on_row_miss. User may also add a prefix 'ghost_' to "
40 "a cache_name to add a ghost cache in front of the real cache. "
41 "ghost_capacity and cache_capacity can be xK, xM or xG where x is a "
42 "positive number.");
43 DEFINE_int32(block_cache_trace_downsample_ratio, 1,
44 "The trace collected accesses on one in every "
45 "block_cache_trace_downsample_ratio blocks. We scale "
46 "down the simulated cache size by this ratio.");
47 DEFINE_bool(print_block_size_stats, false,
48 "Print block size distribution and the distribution break down by "
49 "block type and column family.");
50 DEFINE_bool(print_access_count_stats, false,
51 "Print access count distribution and the distribution break down "
52 "by block type and column family.");
53 DEFINE_bool(print_data_block_access_count_stats, false,
54 "Print data block accesses by user Get and Multi-Get.");
55 DEFINE_int32(cache_sim_warmup_seconds, 0,
56 "The number of seconds to warmup simulated caches. The hit/miss "
57 "counters are reset after the warmup completes.");
58 DEFINE_int32(analyze_bottom_k_access_count_blocks, 0,
59 "Print out detailed access information for blocks with their "
60 "number of accesses are the bottom k among all blocks.");
61 DEFINE_int32(analyze_top_k_access_count_blocks, 0,
62 "Print out detailed access information for blocks with their "
63 "number of accesses are the top k among all blocks.");
64 DEFINE_string(block_cache_analysis_result_dir, "",
65 "The directory that saves block cache analysis results.");
66 DEFINE_string(
67 timeline_labels, "",
68 "Group the number of accesses per block per second using these labels. "
69 "Possible labels are a combination of the following: cf (column family), "
70 "sst, level, bt (block type), caller, block. For example, label \"cf_bt\" "
71 "means the number of access per second is grouped by unique pairs of "
72 "\"cf_bt\". A label \"all\" contains the aggregated number of accesses per "
73 "second across all possible labels.");
74 DEFINE_string(reuse_distance_labels, "",
75 "Group the reuse distance of a block using these labels. Reuse "
76 "distance is defined as the cumulated size of unique blocks read "
77 "between two consecutive accesses on the same block.");
78 DEFINE_string(
79 reuse_distance_buckets, "",
80 "Group blocks by their reuse distances given these buckets. For "
81 "example, if 'reuse_distance_buckets' is '1K,1M,1G', we will "
82 "create four buckets. The first three buckets contain the number of "
83 "blocks with reuse distance less than 1KB, between 1K and 1M, between 1M "
84 "and 1G, respectively. The last bucket contains the number of blocks with "
85 "reuse distance larger than 1G. ");
86 DEFINE_string(
87 reuse_interval_labels, "",
88 "Group the reuse interval of a block using these labels. Reuse "
89 "interval is defined as the time between two consecutive accesses "
90 "on the same block.");
91 DEFINE_string(
92 reuse_interval_buckets, "",
93 "Group blocks by their reuse interval given these buckets. For "
94 "example, if 'reuse_distance_buckets' is '1,10,100', we will "
95 "create four buckets. The first three buckets contain the number of "
96 "blocks with reuse interval less than 1 second, between 1 second and 10 "
97 "seconds, between 10 seconds and 100 seconds, respectively. The last "
98 "bucket contains the number of blocks with reuse interval longer than 100 "
99 "seconds.");
100 DEFINE_string(
101 reuse_lifetime_labels, "",
102 "Group the reuse lifetime of a block using these labels. Reuse "
103 "lifetime is defined as the time interval between the first access on a "
104 "block and the last access on the same block. For blocks that are only "
105 "accessed once, its lifetime is set to kMaxUint64.");
106 DEFINE_string(
107 reuse_lifetime_buckets, "",
108 "Group blocks by their reuse lifetime given these buckets. For "
109 "example, if 'reuse_lifetime_buckets' is '1,10,100', we will "
110 "create four buckets. The first three buckets contain the number of "
111 "blocks with reuse lifetime less than 1 second, between 1 second and 10 "
112 "seconds, between 10 seconds and 100 seconds, respectively. The last "
113 "bucket contains the number of blocks with reuse lifetime longer than 100 "
114 "seconds.");
115 DEFINE_string(
116 analyze_callers, "",
117 "The list of callers to perform a detailed analysis on. If speicfied, the "
118 "analyzer will output a detailed percentage of accesses for each caller "
119 "break down by column family, level, and block type. A list of available "
120 "callers are: Get, MultiGet, Iterator, ApproximateSize, VerifyChecksum, "
121 "SSTDumpTool, ExternalSSTIngestion, Repair, Prefetch, Compaction, "
122 "CompactionRefill, Flush, SSTFileReader, Uncategorized.");
123 DEFINE_string(access_count_buckets, "",
124 "Group number of blocks by their access count given these "
125 "buckets. If specified, the analyzer will output a detailed "
126 "analysis on the number of blocks grouped by their access count "
127 "break down by block type and column family.");
128 DEFINE_int32(analyze_blocks_reuse_k_reuse_window, 0,
129 "Analyze the percentage of blocks that are accessed in the "
130 "[k, 2*k] seconds are accessed again in the next [2*k, 3*k], "
131 "[3*k, 4*k],...,[k*(n-1), k*n] seconds. ");
132 DEFINE_string(analyze_get_spatial_locality_labels, "",
133 "Group data blocks using these labels.");
134 DEFINE_string(analyze_get_spatial_locality_buckets, "",
135 "Group data blocks by their statistics using these buckets.");
136 DEFINE_string(skew_labels, "",
137 "Group the access count of a block using these labels.");
138 DEFINE_string(skew_buckets, "", "Group the skew labels using these buckets.");
139 DEFINE_bool(mrc_only, false,
140 "Evaluate alternative cache policies only. When this flag is true, "
141 "the analyzer does NOT maintain states of each block in memory for "
142 "analysis. It only feeds the accesses into the cache simulators.");
143 DEFINE_string(
144 analyze_correlation_coefficients_labels, "",
145 "Analyze the correlation coefficients of features such as number of past "
146 "accesses with regard to the number of accesses till the next access.");
147 DEFINE_int32(analyze_correlation_coefficients_max_number_of_values, 1000000,
148 "The maximum number of values for a feature. If the number of "
149 "values for a feature is larger than this max, it randomly "
150 "selects 'max' number of values.");
151 DEFINE_string(human_readable_trace_file_path, "",
152 "The filt path that saves human readable access records.");
153
154 namespace ROCKSDB_NAMESPACE {
155 namespace {
156
157 const std::string kMissRatioCurveFileName = "mrc";
158 const std::string kGroupbyBlock = "block";
159 const std::string kGroupbyTable = "table";
160 const std::string kGroupbyColumnFamily = "cf";
161 const std::string kGroupbySSTFile = "sst";
162 const std::string kGroupbyBlockType = "bt";
163 const std::string kGroupbyCaller = "caller";
164 const std::string kGroupbyLevel = "level";
165 const std::string kGroupbyAll = "all";
166 const std::set<std::string> kGroupbyLabels{
167 kGroupbyBlock, kGroupbyColumnFamily, kGroupbySSTFile, kGroupbyLevel,
168 kGroupbyBlockType, kGroupbyCaller, kGroupbyAll};
169 const std::string kSupportedCacheNames =
170 " lru ghost_lru lru_priority ghost_lru_priority lru_hybrid "
171 "ghost_lru_hybrid lru_hybrid_no_insert_on_row_miss "
172 "ghost_lru_hybrid_no_insert_on_row_miss ";
173
174 // The suffix for the generated csv files.
175 const std::string kFileNameSuffixMissRatioTimeline = "miss_ratio_timeline";
176 const std::string kFileNameSuffixMissTimeline = "miss_timeline";
177 const std::string kFileNameSuffixSkew = "skewness";
178 const std::string kFileNameSuffixAccessTimeline = "access_timeline";
179 const std::string kFileNameSuffixCorrelation = "correlation_input";
180 const std::string kFileNameSuffixAvgReuseIntervalNaccesses =
181 "avg_reuse_interval_naccesses";
182 const std::string kFileNameSuffixAvgReuseInterval = "avg_reuse_interval";
183 const std::string kFileNameSuffixReuseInterval = "access_reuse_interval";
184 const std::string kFileNameSuffixReuseLifetime = "reuse_lifetime";
185 const std::string kFileNameSuffixAccessReuseBlocksTimeline =
186 "reuse_blocks_timeline";
187 const std::string kFileNameSuffixPercentOfAccessSummary =
188 "percentage_of_accesses_summary";
189 const std::string kFileNameSuffixPercentRefKeys = "percent_ref_keys";
190 const std::string kFileNameSuffixPercentDataSizeOnRefKeys =
191 "percent_data_size_on_ref_keys";
192 const std::string kFileNameSuffixPercentAccessesOnRefKeys =
193 "percent_accesses_on_ref_keys";
194 const std::string kFileNameSuffixAccessCountSummary = "access_count_summary";
195
block_type_to_string(TraceType type)196 std::string block_type_to_string(TraceType type) {
197 switch (type) {
198 case kBlockTraceFilterBlock:
199 return "Filter";
200 case kBlockTraceDataBlock:
201 return "Data";
202 case kBlockTraceIndexBlock:
203 return "Index";
204 case kBlockTraceRangeDeletionBlock:
205 return "RangeDeletion";
206 case kBlockTraceUncompressionDictBlock:
207 return "UncompressionDict";
208 default:
209 break;
210 }
211 // This cannot happen.
212 return "InvalidType";
213 }
214
caller_to_string(TableReaderCaller caller)215 std::string caller_to_string(TableReaderCaller caller) {
216 switch (caller) {
217 case kUserGet:
218 return "Get";
219 case kUserMultiGet:
220 return "MultiGet";
221 case kUserIterator:
222 return "Iterator";
223 case kUserApproximateSize:
224 return "ApproximateSize";
225 case kUserVerifyChecksum:
226 return "VerifyChecksum";
227 case kSSTDumpTool:
228 return "SSTDumpTool";
229 case kExternalSSTIngestion:
230 return "ExternalSSTIngestion";
231 case kRepair:
232 return "Repair";
233 case kPrefetch:
234 return "Prefetch";
235 case kCompaction:
236 return "Compaction";
237 case kCompactionRefill:
238 return "CompactionRefill";
239 case kFlush:
240 return "Flush";
241 case kSSTFileReader:
242 return "SSTFileReader";
243 case kUncategorized:
244 return "Uncategorized";
245 default:
246 break;
247 }
248 // This cannot happen.
249 return "InvalidCaller";
250 }
251
string_to_caller(std::string caller_str)252 TableReaderCaller string_to_caller(std::string caller_str) {
253 if (caller_str == "Get") {
254 return kUserGet;
255 } else if (caller_str == "MultiGet") {
256 return kUserMultiGet;
257 } else if (caller_str == "Iterator") {
258 return kUserIterator;
259 } else if (caller_str == "ApproximateSize") {
260 return kUserApproximateSize;
261 } else if (caller_str == "VerifyChecksum") {
262 return kUserVerifyChecksum;
263 } else if (caller_str == "SSTDumpTool") {
264 return kSSTDumpTool;
265 } else if (caller_str == "ExternalSSTIngestion") {
266 return kExternalSSTIngestion;
267 } else if (caller_str == "Repair") {
268 return kRepair;
269 } else if (caller_str == "Prefetch") {
270 return kPrefetch;
271 } else if (caller_str == "Compaction") {
272 return kCompaction;
273 } else if (caller_str == "CompactionRefill") {
274 return kCompactionRefill;
275 } else if (caller_str == "Flush") {
276 return kFlush;
277 } else if (caller_str == "SSTFileReader") {
278 return kSSTFileReader;
279 } else if (caller_str == "Uncategorized") {
280 return kUncategorized;
281 }
282 return TableReaderCaller::kMaxBlockCacheLookupCaller;
283 }
284
is_user_access(TableReaderCaller caller)285 bool is_user_access(TableReaderCaller caller) {
286 switch (caller) {
287 case kUserGet:
288 case kUserMultiGet:
289 case kUserIterator:
290 case kUserApproximateSize:
291 case kUserVerifyChecksum:
292 return true;
293 default:
294 break;
295 }
296 return false;
297 }
298
299 const char kBreakLine[] =
300 "***************************************************************\n";
301
print_break_lines(uint32_t num_break_lines)302 void print_break_lines(uint32_t num_break_lines) {
303 for (uint32_t i = 0; i < num_break_lines; i++) {
304 fprintf(stdout, kBreakLine);
305 }
306 }
307
percent(uint64_t numerator,uint64_t denomenator)308 double percent(uint64_t numerator, uint64_t denomenator) {
309 if (denomenator == 0) {
310 return -1;
311 }
312 return static_cast<double>(numerator * 100.0 / denomenator);
313 }
314
adjust_time_unit(const std::map<uint64_t,uint64_t> & time_stats,uint64_t time_unit)315 std::map<uint64_t, uint64_t> adjust_time_unit(
316 const std::map<uint64_t, uint64_t>& time_stats, uint64_t time_unit) {
317 if (time_unit == 1) {
318 return time_stats;
319 }
320 std::map<uint64_t, uint64_t> adjusted_time_stats;
321 for (auto const& time : time_stats) {
322 adjusted_time_stats[static_cast<uint64_t>(time.first / time_unit)] +=
323 time.second;
324 }
325 return adjusted_time_stats;
326 }
327 } // namespace
328
WriteMissRatioCurves() const329 void BlockCacheTraceAnalyzer::WriteMissRatioCurves() const {
330 if (!cache_simulator_) {
331 return;
332 }
333 if (output_dir_.empty()) {
334 return;
335 }
336 uint64_t trace_duration =
337 trace_end_timestamp_in_seconds_ - trace_start_timestamp_in_seconds_;
338 uint64_t total_accesses = access_sequence_number_;
339 const std::string output_miss_ratio_curve_path =
340 output_dir_ + "/" + std::to_string(trace_duration) + "_" +
341 std::to_string(total_accesses) + "_" + kMissRatioCurveFileName;
342 std::ofstream out(output_miss_ratio_curve_path);
343 if (!out.is_open()) {
344 return;
345 }
346 // Write header.
347 const std::string header =
348 "cache_name,num_shard_bits,ghost_capacity,capacity,miss_ratio,total_"
349 "accesses";
350 out << header << std::endl;
351 for (auto const& config_caches : cache_simulator_->sim_caches()) {
352 const CacheConfiguration& config = config_caches.first;
353 for (uint32_t i = 0; i < config.cache_capacities.size(); i++) {
354 double miss_ratio =
355 config_caches.second[i]->miss_ratio_stats().miss_ratio();
356 // Write the body.
357 out << config.cache_name;
358 out << ",";
359 out << config.num_shard_bits;
360 out << ",";
361 out << config.ghost_cache_capacity;
362 out << ",";
363 out << config.cache_capacities[i];
364 out << ",";
365 out << std::fixed << std::setprecision(4) << miss_ratio;
366 out << ",";
367 out << config_caches.second[i]->miss_ratio_stats().total_accesses();
368 out << std::endl;
369 }
370 }
371 out.close();
372 }
373
UpdateFeatureVectors(const std::vector<uint64_t> & access_sequence_number_timeline,const std::vector<uint64_t> & access_timeline,const std::string & label,std::map<std::string,Features> * label_features,std::map<std::string,Predictions> * label_predictions) const374 void BlockCacheTraceAnalyzer::UpdateFeatureVectors(
375 const std::vector<uint64_t>& access_sequence_number_timeline,
376 const std::vector<uint64_t>& access_timeline, const std::string& label,
377 std::map<std::string, Features>* label_features,
378 std::map<std::string, Predictions>* label_predictions) const {
379 if (access_sequence_number_timeline.empty() || access_timeline.empty()) {
380 return;
381 }
382 assert(access_timeline.size() == access_sequence_number_timeline.size());
383 uint64_t prev_access_sequence_number = access_sequence_number_timeline[0];
384 uint64_t prev_access_timestamp = access_timeline[0];
385 for (uint32_t i = 0; i < access_sequence_number_timeline.size(); i++) {
386 uint64_t num_accesses_since_last_access =
387 access_sequence_number_timeline[i] - prev_access_sequence_number;
388 uint64_t elapsed_time_since_last_access =
389 access_timeline[i] - prev_access_timestamp;
390 prev_access_sequence_number = access_sequence_number_timeline[i];
391 prev_access_timestamp = access_timeline[i];
392 if (i < access_sequence_number_timeline.size() - 1) {
393 (*label_features)[label].num_accesses_since_last_access.push_back(
394 num_accesses_since_last_access);
395 (*label_features)[label].num_past_accesses.push_back(i);
396 (*label_features)[label].elapsed_time_since_last_access.push_back(
397 elapsed_time_since_last_access);
398 }
399 if (i >= 1) {
400 (*label_predictions)[label].num_accesses_till_next_access.push_back(
401 num_accesses_since_last_access);
402 (*label_predictions)[label].elapsed_time_till_next_access.push_back(
403 elapsed_time_since_last_access);
404 }
405 }
406 }
407
WriteMissRatioTimeline(uint64_t time_unit) const408 void BlockCacheTraceAnalyzer::WriteMissRatioTimeline(uint64_t time_unit) const {
409 if (!cache_simulator_ || output_dir_.empty()) {
410 return;
411 }
412 std::map<uint64_t, std::map<std::string, std::map<uint64_t, double>>>
413 cs_name_timeline;
414 uint64_t start_time = port::kMaxUint64;
415 uint64_t end_time = 0;
416 const std::map<uint64_t, uint64_t>& trace_num_misses =
417 adjust_time_unit(miss_ratio_stats_.num_misses_timeline(), time_unit);
418 const std::map<uint64_t, uint64_t>& trace_num_accesses =
419 adjust_time_unit(miss_ratio_stats_.num_accesses_timeline(), time_unit);
420 assert(trace_num_misses.size() == trace_num_accesses.size());
421 for (auto const& num_miss : trace_num_misses) {
422 uint64_t time = num_miss.first;
423 start_time = std::min(start_time, time);
424 end_time = std::max(end_time, time);
425 uint64_t miss = num_miss.second;
426 auto it = trace_num_accesses.find(time);
427 assert(it != trace_num_accesses.end());
428 uint64_t access = it->second;
429 cs_name_timeline[port::kMaxUint64]["trace"][time] = percent(miss, access);
430 }
431 for (auto const& config_caches : cache_simulator_->sim_caches()) {
432 const CacheConfiguration& config = config_caches.first;
433 std::string cache_label = config.cache_name + "-" +
434 std::to_string(config.num_shard_bits) + "-" +
435 std::to_string(config.ghost_cache_capacity);
436 for (uint32_t i = 0; i < config.cache_capacities.size(); i++) {
437 const std::map<uint64_t, uint64_t>& num_misses = adjust_time_unit(
438 config_caches.second[i]->miss_ratio_stats().num_misses_timeline(),
439 time_unit);
440 const std::map<uint64_t, uint64_t>& num_accesses = adjust_time_unit(
441 config_caches.second[i]->miss_ratio_stats().num_accesses_timeline(),
442 time_unit);
443 assert(num_misses.size() == num_accesses.size());
444 for (auto const& num_miss : num_misses) {
445 uint64_t time = num_miss.first;
446 start_time = std::min(start_time, time);
447 end_time = std::max(end_time, time);
448 uint64_t miss = num_miss.second;
449 auto it = num_accesses.find(time);
450 assert(it != num_accesses.end());
451 uint64_t access = it->second;
452 cs_name_timeline[config.cache_capacities[i]][cache_label][time] =
453 percent(miss, access);
454 }
455 }
456 }
457 for (auto const& it : cs_name_timeline) {
458 const std::string output_miss_ratio_timeline_path =
459 output_dir_ + "/" + std::to_string(it.first) + "_" +
460 std::to_string(time_unit) + "_" + kFileNameSuffixMissRatioTimeline;
461 std::ofstream out(output_miss_ratio_timeline_path);
462 if (!out.is_open()) {
463 return;
464 }
465 std::string header("time");
466 for (uint64_t now = start_time; now <= end_time; now++) {
467 header += ",";
468 header += std::to_string(now);
469 }
470 out << header << std::endl;
471 for (auto const& label : it.second) {
472 std::string row(label.first);
473 for (uint64_t now = start_time; now <= end_time; now++) {
474 auto misses = label.second.find(now);
475 row += ",";
476 if (misses != label.second.end()) {
477 row += std::to_string(misses->second);
478 } else {
479 row += "0";
480 }
481 }
482 out << row << std::endl;
483 }
484 out.close();
485 }
486 }
487
WriteMissTimeline(uint64_t time_unit) const488 void BlockCacheTraceAnalyzer::WriteMissTimeline(uint64_t time_unit) const {
489 if (!cache_simulator_ || output_dir_.empty()) {
490 return;
491 }
492 std::map<uint64_t, std::map<std::string, std::map<uint64_t, uint64_t>>>
493 cs_name_timeline;
494 uint64_t start_time = port::kMaxUint64;
495 uint64_t end_time = 0;
496 const std::map<uint64_t, uint64_t>& trace_num_misses =
497 adjust_time_unit(miss_ratio_stats_.num_misses_timeline(), time_unit);
498 for (auto const& num_miss : trace_num_misses) {
499 uint64_t time = num_miss.first;
500 start_time = std::min(start_time, time);
501 end_time = std::max(end_time, time);
502 uint64_t miss = num_miss.second;
503 cs_name_timeline[port::kMaxUint64]["trace"][time] = miss;
504 }
505 for (auto const& config_caches : cache_simulator_->sim_caches()) {
506 const CacheConfiguration& config = config_caches.first;
507 std::string cache_label = config.cache_name + "-" +
508 std::to_string(config.num_shard_bits) + "-" +
509 std::to_string(config.ghost_cache_capacity);
510 for (uint32_t i = 0; i < config.cache_capacities.size(); i++) {
511 const std::map<uint64_t, uint64_t>& num_misses = adjust_time_unit(
512 config_caches.second[i]->miss_ratio_stats().num_misses_timeline(),
513 time_unit);
514 for (auto const& num_miss : num_misses) {
515 uint64_t time = num_miss.first;
516 start_time = std::min(start_time, time);
517 end_time = std::max(end_time, time);
518 uint64_t miss = num_miss.second;
519 cs_name_timeline[config.cache_capacities[i]][cache_label][time] = miss;
520 }
521 }
522 }
523 for (auto const& it : cs_name_timeline) {
524 const std::string output_miss_ratio_timeline_path =
525 output_dir_ + "/" + std::to_string(it.first) + "_" +
526 std::to_string(time_unit) + "_" + kFileNameSuffixMissTimeline;
527 std::ofstream out(output_miss_ratio_timeline_path);
528 if (!out.is_open()) {
529 return;
530 }
531 std::string header("time");
532 for (uint64_t now = start_time; now <= end_time; now++) {
533 header += ",";
534 header += std::to_string(now);
535 }
536 out << header << std::endl;
537 for (auto const& label : it.second) {
538 std::string row(label.first);
539 for (uint64_t now = start_time; now <= end_time; now++) {
540 auto misses = label.second.find(now);
541 row += ",";
542 if (misses != label.second.end()) {
543 row += std::to_string(misses->second);
544 } else {
545 row += "0";
546 }
547 }
548 out << row << std::endl;
549 }
550 out.close();
551 }
552 }
553
WriteSkewness(const std::string & label_str,const std::vector<uint64_t> & percent_buckets,TraceType target_block_type) const554 void BlockCacheTraceAnalyzer::WriteSkewness(
555 const std::string& label_str, const std::vector<uint64_t>& percent_buckets,
556 TraceType target_block_type) const {
557 std::set<std::string> labels = ParseLabelStr(label_str);
558 std::map<std::string, uint64_t> label_naccesses;
559 uint64_t total_naccesses = 0;
560 auto block_callback = [&](const std::string& cf_name, uint64_t fd,
561 uint32_t level, TraceType type,
562 const std::string& /*block_key*/, uint64_t block_id,
563 const BlockAccessInfo& block) {
564 if (target_block_type != TraceType::kTraceMax &&
565 target_block_type != type) {
566 return;
567 }
568 const std::string label = BuildLabel(
569 labels, cf_name, fd, level, type,
570 TableReaderCaller::kMaxBlockCacheLookupCaller, block_id, block);
571 label_naccesses[label] += block.num_accesses;
572 total_naccesses += block.num_accesses;
573 };
574 TraverseBlocks(block_callback, &labels);
575 std::map<std::string, std::map<uint64_t, uint64_t>> label_bucket_naccesses;
576 std::vector<std::pair<std::string, uint64_t>> pairs;
577 for (auto const& itr : label_naccesses) {
578 pairs.push_back(itr);
579 }
580 // Sort in descending order.
581 sort(pairs.begin(), pairs.end(),
582 [](const std::pair<std::string, uint64_t>& a,
583 const std::pair<std::string, uint64_t>& b) {
584 return b.second < a.second;
585 });
586
587 size_t prev_start_index = 0;
588 for (auto const& percent : percent_buckets) {
589 label_bucket_naccesses[label_str][percent] = 0;
590 size_t end_index = 0;
591 if (percent == port::kMaxUint64) {
592 end_index = label_naccesses.size();
593 } else {
594 end_index = percent * label_naccesses.size() / 100;
595 }
596 for (size_t i = prev_start_index; i < end_index; i++) {
597 label_bucket_naccesses[label_str][percent] += pairs[i].second;
598 }
599 prev_start_index = end_index;
600 }
601 std::string filename_suffix;
602 if (target_block_type != TraceType::kTraceMax) {
603 filename_suffix = block_type_to_string(target_block_type);
604 filename_suffix += "_";
605 }
606 filename_suffix += kFileNameSuffixSkew;
607 WriteStatsToFile(label_str, percent_buckets, filename_suffix,
608 label_bucket_naccesses, total_naccesses);
609 }
610
WriteCorrelationFeatures(const std::string & label_str,uint32_t max_number_of_values) const611 void BlockCacheTraceAnalyzer::WriteCorrelationFeatures(
612 const std::string& label_str, uint32_t max_number_of_values) const {
613 std::set<std::string> labels = ParseLabelStr(label_str);
614 std::map<std::string, Features> label_features;
615 std::map<std::string, Predictions> label_predictions;
616 auto block_callback =
617 [&](const std::string& cf_name, uint64_t fd, uint32_t level,
618 TraceType block_type, const std::string& /*block_key*/,
619 uint64_t /*block_key_id*/, const BlockAccessInfo& block) {
620 if (block.table_id == 0 && labels.find(kGroupbyTable) != labels.end()) {
621 // We only know table id information for get requests.
622 return;
623 }
624 if (labels.find(kGroupbyCaller) != labels.end()) {
625 // Group by caller.
626 for (auto const& caller_map : block.caller_access_timeline) {
627 const std::string label =
628 BuildLabel(labels, cf_name, fd, level, block_type,
629 caller_map.first, /*block_id=*/0, block);
630 auto it = block.caller_access_sequence__number_timeline.find(
631 caller_map.first);
632 assert(it != block.caller_access_sequence__number_timeline.end());
633 UpdateFeatureVectors(it->second, caller_map.second, label,
634 &label_features, &label_predictions);
635 }
636 return;
637 }
638 const std::string label =
639 BuildLabel(labels, cf_name, fd, level, block_type,
640 TableReaderCaller::kMaxBlockCacheLookupCaller,
641 /*block_id=*/0, block);
642 UpdateFeatureVectors(block.access_sequence_number_timeline,
643 block.access_timeline, label, &label_features,
644 &label_predictions);
645 };
646 TraverseBlocks(block_callback, &labels);
647 WriteCorrelationFeaturesToFile(label_str, label_features, label_predictions,
648 max_number_of_values);
649 }
650
WriteCorrelationFeaturesToFile(const std::string & label,const std::map<std::string,Features> & label_features,const std::map<std::string,Predictions> & label_predictions,uint32_t max_number_of_values) const651 void BlockCacheTraceAnalyzer::WriteCorrelationFeaturesToFile(
652 const std::string& label,
653 const std::map<std::string, Features>& label_features,
654 const std::map<std::string, Predictions>& label_predictions,
655 uint32_t max_number_of_values) const {
656 for (auto const& label_feature_vectors : label_features) {
657 const Features& past = label_feature_vectors.second;
658 auto it = label_predictions.find(label_feature_vectors.first);
659 assert(it != label_predictions.end());
660 const Predictions& future = it->second;
661 const std::string output_path = output_dir_ + "/" + label + "_" +
662 label_feature_vectors.first + "_" +
663 kFileNameSuffixCorrelation;
664 std::ofstream out(output_path);
665 if (!out.is_open()) {
666 return;
667 }
668 std::string header(
669 "num_accesses_since_last_access,elapsed_time_since_last_access,num_"
670 "past_accesses,num_accesses_till_next_access,elapsed_time_till_next_"
671 "access");
672 out << header << std::endl;
673 std::vector<uint32_t> indexes;
674 for (uint32_t i = 0; i < past.num_accesses_since_last_access.size(); i++) {
675 indexes.push_back(i);
676 }
677 RandomShuffle(indexes.begin(), indexes.end());
678 for (uint32_t i = 0; i < max_number_of_values && i < indexes.size(); i++) {
679 uint32_t rand_index = indexes[i];
680 out << std::to_string(past.num_accesses_since_last_access[rand_index])
681 << ",";
682 out << std::to_string(past.elapsed_time_since_last_access[rand_index])
683 << ",";
684 out << std::to_string(past.num_past_accesses[rand_index]) << ",";
685 out << std::to_string(future.num_accesses_till_next_access[rand_index])
686 << ",";
687 out << std::to_string(future.elapsed_time_till_next_access[rand_index])
688 << std::endl;
689 }
690 out.close();
691 }
692 }
693
WriteCorrelationFeaturesForGet(uint32_t max_number_of_values) const694 void BlockCacheTraceAnalyzer::WriteCorrelationFeaturesForGet(
695 uint32_t max_number_of_values) const {
696 std::string label = "GetKeyInfo";
697 std::map<std::string, Features> label_features;
698 std::map<std::string, Predictions> label_predictions;
699 for (auto const& get_info : get_key_info_map_) {
700 const GetKeyInfo& info = get_info.second;
701 UpdateFeatureVectors(info.access_sequence_number_timeline,
702 info.access_timeline, label, &label_features,
703 &label_predictions);
704 }
705 WriteCorrelationFeaturesToFile(label, label_features, label_predictions,
706 max_number_of_values);
707 }
708
ParseLabelStr(const std::string & label_str) const709 std::set<std::string> BlockCacheTraceAnalyzer::ParseLabelStr(
710 const std::string& label_str) const {
711 std::stringstream ss(label_str);
712 std::set<std::string> labels;
713 // label_str is in the form of "label1_label2_label3", e.g., cf_bt.
714 while (ss.good()) {
715 std::string label_name;
716 getline(ss, label_name, '_');
717 if (kGroupbyLabels.find(label_name) == kGroupbyLabels.end()) {
718 // Unknown label name.
719 fprintf(stderr, "Unknown label name %s, label string %s\n",
720 label_name.c_str(), label_str.c_str());
721 return {};
722 }
723 labels.insert(label_name);
724 }
725 return labels;
726 }
727
BuildLabel(const std::set<std::string> & labels,const std::string & cf_name,uint64_t fd,uint32_t level,TraceType type,TableReaderCaller caller,uint64_t block_key,const BlockAccessInfo & block) const728 std::string BlockCacheTraceAnalyzer::BuildLabel(
729 const std::set<std::string>& labels, const std::string& cf_name,
730 uint64_t fd, uint32_t level, TraceType type, TableReaderCaller caller,
731 uint64_t block_key, const BlockAccessInfo& block) const {
732 std::map<std::string, std::string> label_value_map;
733 label_value_map[kGroupbyAll] = kGroupbyAll;
734 label_value_map[kGroupbyLevel] = std::to_string(level);
735 label_value_map[kGroupbyCaller] = caller_to_string(caller);
736 label_value_map[kGroupbySSTFile] = std::to_string(fd);
737 label_value_map[kGroupbyBlockType] = block_type_to_string(type);
738 label_value_map[kGroupbyColumnFamily] = cf_name;
739 label_value_map[kGroupbyBlock] = std::to_string(block_key);
740 label_value_map[kGroupbyTable] = std::to_string(block.table_id);
741 // Concatenate the label values.
742 std::string label;
743 for (auto const& l : labels) {
744 label += label_value_map[l];
745 label += "-";
746 }
747 if (!label.empty()) {
748 label.pop_back();
749 }
750 return label;
751 }
752
TraverseBlocks(std::function<void (const std::string &,uint64_t,uint32_t,TraceType,const std::string &,uint64_t,const BlockAccessInfo &)> block_callback,std::set<std::string> * labels) const753 void BlockCacheTraceAnalyzer::TraverseBlocks(
754 std::function<void(const std::string& /*cf_name*/, uint64_t /*fd*/,
755 uint32_t /*level*/, TraceType /*block_type*/,
756 const std::string& /*block_key*/,
757 uint64_t /*block_key_id*/,
758 const BlockAccessInfo& /*block_access_info*/)>
759 block_callback,
760 std::set<std::string>* labels) const {
761 for (auto const& cf_aggregates : cf_aggregates_map_) {
762 // Stats per column family.
763 const std::string& cf_name = cf_aggregates.first;
764 for (auto const& file_aggregates : cf_aggregates.second.fd_aggregates_map) {
765 // Stats per SST file.
766 const uint64_t fd = file_aggregates.first;
767 const uint32_t level = file_aggregates.second.level;
768 for (auto const& block_type_aggregates :
769 file_aggregates.second.block_type_aggregates_map) {
770 // Stats per block type.
771 const TraceType type = block_type_aggregates.first;
772 for (auto const& block_access_info :
773 block_type_aggregates.second.block_access_info_map) {
774 // Stats per block.
775 if (labels && block_access_info.second.table_id == 0 &&
776 labels->find(kGroupbyTable) != labels->end()) {
777 // We only know table id information for get requests.
778 return;
779 }
780 block_callback(cf_name, fd, level, type, block_access_info.first,
781 block_access_info.second.block_id,
782 block_access_info.second);
783 }
784 }
785 }
786 }
787 }
788
WriteGetSpatialLocality(const std::string & label_str,const std::vector<uint64_t> & percent_buckets) const789 void BlockCacheTraceAnalyzer::WriteGetSpatialLocality(
790 const std::string& label_str,
791 const std::vector<uint64_t>& percent_buckets) const {
792 std::set<std::string> labels = ParseLabelStr(label_str);
793 std::map<std::string, std::map<uint64_t, uint64_t>> label_pnrefkeys_nblocks;
794 std::map<std::string, std::map<uint64_t, uint64_t>> label_pnrefs_nblocks;
795 std::map<std::string, std::map<uint64_t, uint64_t>> label_pndatasize_nblocks;
796 uint64_t nblocks = 0;
797 auto block_callback = [&](const std::string& cf_name, uint64_t fd,
798 uint32_t level, TraceType /*block_type*/,
799 const std::string& /*block_key*/,
800 uint64_t /*block_key_id*/,
801 const BlockAccessInfo& block) {
802 if (block.num_keys == 0) {
803 return;
804 }
805 uint64_t naccesses = 0;
806 for (auto const& key_access : block.key_num_access_map) {
807 for (auto const& caller_access : key_access.second) {
808 if (caller_access.first == TableReaderCaller::kUserGet) {
809 naccesses += caller_access.second;
810 }
811 }
812 }
813 const std::string label =
814 BuildLabel(labels, cf_name, fd, level, TraceType::kBlockTraceDataBlock,
815 TableReaderCaller::kUserGet, /*block_id=*/0, block);
816
817 const uint64_t percent_referenced_for_existing_keys =
818 static_cast<uint64_t>(std::max(
819 percent(block.key_num_access_map.size(), block.num_keys), 0.0));
820 const uint64_t percent_accesses_for_existing_keys =
821 static_cast<uint64_t>(std::max(
822 percent(block.num_referenced_key_exist_in_block, naccesses), 0.0));
823 const uint64_t percent_referenced_data_size = static_cast<uint64_t>(
824 std::max(percent(block.referenced_data_size, block.block_size), 0.0));
825 if (label_pnrefkeys_nblocks.find(label) == label_pnrefkeys_nblocks.end()) {
826 for (auto const& percent_bucket : percent_buckets) {
827 label_pnrefkeys_nblocks[label][percent_bucket] = 0;
828 label_pnrefs_nblocks[label][percent_bucket] = 0;
829 label_pndatasize_nblocks[label][percent_bucket] = 0;
830 }
831 }
832 label_pnrefkeys_nblocks[label]
833 .upper_bound(percent_referenced_for_existing_keys)
834 ->second += 1;
835 label_pnrefs_nblocks[label]
836 .upper_bound(percent_accesses_for_existing_keys)
837 ->second += 1;
838 label_pndatasize_nblocks[label]
839 .upper_bound(percent_referenced_data_size)
840 ->second += 1;
841 nblocks += 1;
842 };
843 TraverseBlocks(block_callback, &labels);
844 WriteStatsToFile(label_str, percent_buckets, kFileNameSuffixPercentRefKeys,
845 label_pnrefkeys_nblocks, nblocks);
846 WriteStatsToFile(label_str, percent_buckets,
847 kFileNameSuffixPercentAccessesOnRefKeys,
848 label_pnrefs_nblocks, nblocks);
849 WriteStatsToFile(label_str, percent_buckets,
850 kFileNameSuffixPercentDataSizeOnRefKeys,
851 label_pndatasize_nblocks, nblocks);
852 }
853
WriteAccessTimeline(const std::string & label_str,uint64_t time_unit,bool user_access_only) const854 void BlockCacheTraceAnalyzer::WriteAccessTimeline(const std::string& label_str,
855 uint64_t time_unit,
856 bool user_access_only) const {
857 std::set<std::string> labels = ParseLabelStr(label_str);
858 uint64_t start_time = port::kMaxUint64;
859 uint64_t end_time = 0;
860 std::map<std::string, std::map<uint64_t, uint64_t>> label_access_timeline;
861 std::map<uint64_t, std::vector<std::string>> access_count_block_id_map;
862
863 auto block_callback = [&](const std::string& cf_name, uint64_t fd,
864 uint32_t level, TraceType type,
865 const std::string& /*block_key*/, uint64_t block_id,
866 const BlockAccessInfo& block) {
867 uint64_t naccesses = 0;
868 for (auto const& timeline : block.caller_num_accesses_timeline) {
869 const TableReaderCaller caller = timeline.first;
870 if (user_access_only && !is_user_access(caller)) {
871 continue;
872 }
873 const std::string label =
874 BuildLabel(labels, cf_name, fd, level, type, caller, block_id, block);
875 for (auto const& naccess : timeline.second) {
876 const uint64_t timestamp = naccess.first / time_unit;
877 const uint64_t num = naccess.second;
878 label_access_timeline[label][timestamp] += num;
879 start_time = std::min(start_time, timestamp);
880 end_time = std::max(end_time, timestamp);
881 naccesses += num;
882 }
883 }
884 if (naccesses > 0) {
885 access_count_block_id_map[naccesses].push_back(std::to_string(block_id));
886 }
887 };
888 TraverseBlocks(block_callback, &labels);
889
890 // We have label_access_timeline now. Write them into a file.
891 const std::string user_access_prefix =
892 user_access_only ? "user_access_only_" : "all_access_";
893 const std::string output_path = output_dir_ + "/" + user_access_prefix +
894 label_str + "_" + std::to_string(time_unit) +
895 "_" + kFileNameSuffixAccessTimeline;
896 std::ofstream out(output_path);
897 if (!out.is_open()) {
898 return;
899 }
900 std::string header("time");
901 if (labels.find("block") != labels.end()) {
902 for (uint64_t now = start_time; now <= end_time; now++) {
903 header += ",";
904 header += std::to_string(now);
905 }
906 out << header << std::endl;
907 // Write the most frequently accessed blocks first.
908 for (auto naccess_it = access_count_block_id_map.rbegin();
909 naccess_it != access_count_block_id_map.rend(); naccess_it++) {
910 for (auto& block_id_it : naccess_it->second) {
911 std::string row(block_id_it);
912 for (uint64_t now = start_time; now <= end_time; now++) {
913 auto it = label_access_timeline[block_id_it].find(now);
914 row += ",";
915 if (it != label_access_timeline[block_id_it].end()) {
916 row += std::to_string(it->second);
917 } else {
918 row += "0";
919 }
920 }
921 out << row << std::endl;
922 }
923 }
924 out.close();
925 return;
926 }
927 for (uint64_t now = start_time; now <= end_time; now++) {
928 header += ",";
929 header += std::to_string(now);
930 }
931 out << header << std::endl;
932 for (auto const& label : label_access_timeline) {
933 std::string row(label.first);
934 for (uint64_t now = start_time; now <= end_time; now++) {
935 auto it = label.second.find(now);
936 row += ",";
937 if (it != label.second.end()) {
938 row += std::to_string(it->second);
939 } else {
940 row += "0";
941 }
942 }
943 out << row << std::endl;
944 }
945
946 out.close();
947 }
948
WriteReuseDistance(const std::string & label_str,const std::vector<uint64_t> & distance_buckets) const949 void BlockCacheTraceAnalyzer::WriteReuseDistance(
950 const std::string& label_str,
951 const std::vector<uint64_t>& distance_buckets) const {
952 std::set<std::string> labels = ParseLabelStr(label_str);
953 std::map<std::string, std::map<uint64_t, uint64_t>> label_distance_num_reuses;
954 uint64_t total_num_reuses = 0;
955 auto block_callback = [&](const std::string& cf_name, uint64_t fd,
956 uint32_t level, TraceType type,
957 const std::string& /*block_key*/, uint64_t block_id,
958 const BlockAccessInfo& block) {
959 const std::string label = BuildLabel(
960 labels, cf_name, fd, level, type,
961 TableReaderCaller::kMaxBlockCacheLookupCaller, block_id, block);
962 if (label_distance_num_reuses.find(label) ==
963 label_distance_num_reuses.end()) {
964 // The first time we encounter this label.
965 for (auto const& distance_bucket : distance_buckets) {
966 label_distance_num_reuses[label][distance_bucket] = 0;
967 }
968 }
969 for (auto const& reuse_distance : block.reuse_distance_count) {
970 label_distance_num_reuses[label]
971 .upper_bound(reuse_distance.first)
972 ->second += reuse_distance.second;
973 total_num_reuses += reuse_distance.second;
974 }
975 };
976 TraverseBlocks(block_callback, &labels);
977 // We have label_naccesses and label_distance_num_reuses now. Write them into
978 // a file.
979 const std::string output_path =
980 output_dir_ + "/" + label_str + "_reuse_distance";
981 std::ofstream out(output_path);
982 if (!out.is_open()) {
983 return;
984 }
985 std::string header("bucket");
986 for (auto const& label_it : label_distance_num_reuses) {
987 header += ",";
988 header += label_it.first;
989 }
990 out << header << std::endl;
991 for (auto const& bucket : distance_buckets) {
992 std::string row(std::to_string(bucket));
993 for (auto const& label_it : label_distance_num_reuses) {
994 auto const& it = label_it.second.find(bucket);
995 assert(it != label_it.second.end());
996 row += ",";
997 row += std::to_string(percent(it->second, total_num_reuses));
998 }
999 out << row << std::endl;
1000 }
1001 out.close();
1002 }
1003
UpdateReuseIntervalStats(const std::string & label,const std::vector<uint64_t> & time_buckets,const std::map<uint64_t,uint64_t> timeline,std::map<std::string,std::map<uint64_t,uint64_t>> * label_time_num_reuses,uint64_t * total_num_reuses) const1004 void BlockCacheTraceAnalyzer::UpdateReuseIntervalStats(
1005 const std::string& label, const std::vector<uint64_t>& time_buckets,
1006 const std::map<uint64_t, uint64_t> timeline,
1007 std::map<std::string, std::map<uint64_t, uint64_t>>* label_time_num_reuses,
1008 uint64_t* total_num_reuses) const {
1009 assert(label_time_num_reuses);
1010 assert(total_num_reuses);
1011 if (label_time_num_reuses->find(label) == label_time_num_reuses->end()) {
1012 // The first time we encounter this label.
1013 for (auto const& time_bucket : time_buckets) {
1014 (*label_time_num_reuses)[label][time_bucket] = 0;
1015 }
1016 }
1017 auto it = timeline.begin();
1018 uint64_t prev_timestamp = it->first;
1019 const uint64_t prev_num = it->second;
1020 it++;
1021 // Reused within one second.
1022 if (prev_num > 1) {
1023 (*label_time_num_reuses)[label].upper_bound(0)->second += prev_num - 1;
1024 *total_num_reuses += prev_num - 1;
1025 }
1026 while (it != timeline.end()) {
1027 const uint64_t timestamp = it->first;
1028 const uint64_t num = it->second;
1029 const uint64_t reuse_interval = timestamp - prev_timestamp;
1030 (*label_time_num_reuses)[label].upper_bound(reuse_interval)->second += 1;
1031 if (num > 1) {
1032 (*label_time_num_reuses)[label].upper_bound(0)->second += num - 1;
1033 }
1034 prev_timestamp = timestamp;
1035 *total_num_reuses += num;
1036 it++;
1037 }
1038 }
1039
WriteStatsToFile(const std::string & label_str,const std::vector<uint64_t> & time_buckets,const std::string & filename_suffix,const std::map<std::string,std::map<uint64_t,uint64_t>> & label_data,uint64_t ntotal) const1040 void BlockCacheTraceAnalyzer::WriteStatsToFile(
1041 const std::string& label_str, const std::vector<uint64_t>& time_buckets,
1042 const std::string& filename_suffix,
1043 const std::map<std::string, std::map<uint64_t, uint64_t>>& label_data,
1044 uint64_t ntotal) const {
1045 const std::string output_path =
1046 output_dir_ + "/" + label_str + "_" + filename_suffix;
1047 std::ofstream out(output_path);
1048 if (!out.is_open()) {
1049 return;
1050 }
1051 std::string header("bucket");
1052 for (auto const& label_it : label_data) {
1053 header += ",";
1054 header += label_it.first;
1055 }
1056 out << header << std::endl;
1057 for (auto const& bucket : time_buckets) {
1058 std::string row(std::to_string(bucket));
1059 for (auto const& label_it : label_data) {
1060 auto const& it = label_it.second.find(bucket);
1061 assert(it != label_it.second.end());
1062 row += ",";
1063 row += std::to_string(percent(it->second, ntotal));
1064 }
1065 out << row << std::endl;
1066 }
1067 out.close();
1068 }
1069
WriteReuseInterval(const std::string & label_str,const std::vector<uint64_t> & time_buckets) const1070 void BlockCacheTraceAnalyzer::WriteReuseInterval(
1071 const std::string& label_str,
1072 const std::vector<uint64_t>& time_buckets) const {
1073 std::set<std::string> labels = ParseLabelStr(label_str);
1074 std::map<std::string, std::map<uint64_t, uint64_t>> label_time_num_reuses;
1075 std::map<std::string, std::map<uint64_t, uint64_t>> label_avg_reuse_nblocks;
1076 std::map<std::string, std::map<uint64_t, uint64_t>> label_avg_reuse_naccesses;
1077
1078 uint64_t total_num_reuses = 0;
1079 uint64_t total_nblocks = 0;
1080 uint64_t total_accesses = 0;
1081 auto block_callback = [&](const std::string& cf_name, uint64_t fd,
1082 uint32_t level, TraceType type,
1083 const std::string& /*block_key*/, uint64_t block_id,
1084 const BlockAccessInfo& block) {
1085 total_nblocks++;
1086 total_accesses += block.num_accesses;
1087 uint64_t avg_reuse_interval = 0;
1088 if (block.num_accesses > 1) {
1089 avg_reuse_interval = ((block.last_access_time - block.first_access_time) /
1090 kMicrosInSecond) /
1091 block.num_accesses;
1092 } else {
1093 avg_reuse_interval = port::kMaxUint64 - 1;
1094 }
1095 if (labels.find(kGroupbyCaller) != labels.end()) {
1096 for (auto const& timeline : block.caller_num_accesses_timeline) {
1097 const TableReaderCaller caller = timeline.first;
1098 const std::string label = BuildLabel(labels, cf_name, fd, level, type,
1099 caller, block_id, block);
1100 UpdateReuseIntervalStats(label, time_buckets, timeline.second,
1101 &label_time_num_reuses, &total_num_reuses);
1102 }
1103 return;
1104 }
1105 // Does not group by caller so we need to flatten the access timeline.
1106 const std::string label = BuildLabel(
1107 labels, cf_name, fd, level, type,
1108 TableReaderCaller::kMaxBlockCacheLookupCaller, block_id, block);
1109 std::map<uint64_t, uint64_t> timeline;
1110 for (auto const& caller_timeline : block.caller_num_accesses_timeline) {
1111 for (auto const& time_naccess : caller_timeline.second) {
1112 timeline[time_naccess.first] += time_naccess.second;
1113 }
1114 }
1115 UpdateReuseIntervalStats(label, time_buckets, timeline,
1116 &label_time_num_reuses, &total_num_reuses);
1117 if (label_avg_reuse_nblocks.find(label) == label_avg_reuse_nblocks.end()) {
1118 for (auto const& time_bucket : time_buckets) {
1119 label_avg_reuse_nblocks[label][time_bucket] = 0;
1120 label_avg_reuse_naccesses[label][time_bucket] = 0;
1121 }
1122 }
1123 label_avg_reuse_nblocks[label].upper_bound(avg_reuse_interval)->second += 1;
1124 label_avg_reuse_naccesses[label].upper_bound(avg_reuse_interval)->second +=
1125 block.num_accesses;
1126 };
1127 TraverseBlocks(block_callback, &labels);
1128
1129 // Write the stats into files.
1130 WriteStatsToFile(label_str, time_buckets, kFileNameSuffixReuseInterval,
1131 label_time_num_reuses, total_num_reuses);
1132 WriteStatsToFile(label_str, time_buckets, kFileNameSuffixAvgReuseInterval,
1133 label_avg_reuse_nblocks, total_nblocks);
1134 WriteStatsToFile(label_str, time_buckets,
1135 kFileNameSuffixAvgReuseIntervalNaccesses,
1136 label_avg_reuse_naccesses, total_accesses);
1137 }
1138
WriteReuseLifetime(const std::string & label_str,const std::vector<uint64_t> & time_buckets) const1139 void BlockCacheTraceAnalyzer::WriteReuseLifetime(
1140 const std::string& label_str,
1141 const std::vector<uint64_t>& time_buckets) const {
1142 std::set<std::string> labels = ParseLabelStr(label_str);
1143 std::map<std::string, std::map<uint64_t, uint64_t>> label_lifetime_nblocks;
1144 uint64_t total_nblocks = 0;
1145 auto block_callback = [&](const std::string& cf_name, uint64_t fd,
1146 uint32_t level, TraceType type,
1147 const std::string& /*block_key*/, uint64_t block_id,
1148 const BlockAccessInfo& block) {
1149 uint64_t lifetime = 0;
1150 if (block.num_accesses > 1) {
1151 lifetime =
1152 (block.last_access_time - block.first_access_time) / kMicrosInSecond;
1153 } else {
1154 lifetime = port::kMaxUint64 - 1;
1155 }
1156 const std::string label = BuildLabel(
1157 labels, cf_name, fd, level, type,
1158 TableReaderCaller::kMaxBlockCacheLookupCaller, block_id, block);
1159
1160 if (label_lifetime_nblocks.find(label) == label_lifetime_nblocks.end()) {
1161 // The first time we encounter this label.
1162 for (auto const& time_bucket : time_buckets) {
1163 label_lifetime_nblocks[label][time_bucket] = 0;
1164 }
1165 }
1166 label_lifetime_nblocks[label].upper_bound(lifetime)->second += 1;
1167 total_nblocks += 1;
1168 };
1169 TraverseBlocks(block_callback, &labels);
1170 WriteStatsToFile(label_str, time_buckets, kFileNameSuffixReuseLifetime,
1171 label_lifetime_nblocks, total_nblocks);
1172 }
1173
WriteBlockReuseTimeline(const uint64_t reuse_window,bool user_access_only,TraceType block_type) const1174 void BlockCacheTraceAnalyzer::WriteBlockReuseTimeline(
1175 const uint64_t reuse_window, bool user_access_only, TraceType block_type) const {
1176 // A map from block key to an array of bools that states whether a block is
1177 // accessed in a time window.
1178 std::map<uint64_t, std::vector<bool>> block_accessed;
1179 const uint64_t trace_duration =
1180 trace_end_timestamp_in_seconds_ - trace_start_timestamp_in_seconds_;
1181 const uint64_t reuse_vector_size = (trace_duration / reuse_window);
1182 if (reuse_vector_size < 2) {
1183 // The reuse window is less than 2. We cannot calculate the reused
1184 // percentage of blocks.
1185 return;
1186 }
1187 auto block_callback = [&](const std::string& /*cf_name*/, uint64_t /*fd*/,
1188 uint32_t /*level*/, TraceType /*type*/,
1189 const std::string& /*block_key*/, uint64_t block_id,
1190 const BlockAccessInfo& block) {
1191 if (block_accessed.find(block_id) == block_accessed.end()) {
1192 block_accessed[block_id].resize(reuse_vector_size);
1193 for (uint64_t i = 0; i < reuse_vector_size; i++) {
1194 block_accessed[block_id][i] = false;
1195 }
1196 }
1197 for (auto const& caller_num : block.caller_num_accesses_timeline) {
1198 const TableReaderCaller caller = caller_num.first;
1199 for (auto const& timeline : caller_num.second) {
1200 const uint64_t timestamp = timeline.first;
1201 const uint64_t elapsed_time =
1202 timestamp - trace_start_timestamp_in_seconds_;
1203 if (!user_access_only || is_user_access(caller)) {
1204 uint64_t index =
1205 std::min(elapsed_time / reuse_window, reuse_vector_size - 1);
1206 block_accessed[block_id][index] = true;
1207 }
1208 }
1209 }
1210 };
1211 TraverseBlocks(block_callback);
1212
1213 // A cell is the number of blocks accessed in a reuse window.
1214 std::unique_ptr<uint64_t[]> reuse_table(new uint64_t[reuse_vector_size * reuse_vector_size]);
1215 for (uint64_t start_time = 0; start_time < reuse_vector_size; start_time++) {
1216 // Initialize the reuse_table.
1217 for (uint64_t i = 0; i < reuse_vector_size; i++) {
1218 reuse_table[start_time * reuse_vector_size + i] = 0;
1219 }
1220 // Examine all blocks.
1221 for (auto const& block : block_accessed) {
1222 for (uint64_t i = start_time; i < reuse_vector_size; i++) {
1223 if (block.second[start_time] && block.second[i]) {
1224 // This block is accessed at start time and at the current time. We
1225 // increment reuse_table[start_time][i] since it is reused at the ith
1226 // window.
1227 reuse_table[start_time * reuse_vector_size + i]++;
1228 }
1229 }
1230 }
1231 }
1232 const std::string user_access_prefix =
1233 user_access_only ? "_user_access_only_" : "_all_access_";
1234 const std::string output_path =
1235 output_dir_ + "/" + block_type_to_string(block_type) +
1236 user_access_prefix + std::to_string(reuse_window) + "_" +
1237 kFileNameSuffixAccessReuseBlocksTimeline;
1238 std::ofstream out(output_path);
1239 if (!out.is_open()) {
1240 return;
1241 }
1242 std::string header("start_time");
1243 for (uint64_t start_time = 0; start_time < reuse_vector_size; start_time++) {
1244 header += ",";
1245 header += std::to_string(start_time);
1246 }
1247 out << header << std::endl;
1248 for (uint64_t start_time = 0; start_time < reuse_vector_size; start_time++) {
1249 std::string row(std::to_string(start_time * reuse_window));
1250 for (uint64_t j = 0; j < reuse_vector_size; j++) {
1251 row += ",";
1252 if (j < start_time) {
1253 row += "100.0";
1254 } else {
1255 row += std::to_string(percent(reuse_table[start_time * reuse_vector_size + j],
1256 reuse_table[start_time * reuse_vector_size + start_time]));
1257 }
1258 }
1259 out << row << std::endl;
1260 }
1261 out.close();
1262 }
1263
OutputPercentAccessStats(uint64_t total_accesses,const std::map<std::string,uint64_t> & cf_access_count) const1264 std::string BlockCacheTraceAnalyzer::OutputPercentAccessStats(
1265 uint64_t total_accesses,
1266 const std::map<std::string, uint64_t>& cf_access_count) const {
1267 std::string row;
1268 for (auto const& cf_aggregates : cf_aggregates_map_) {
1269 const std::string& cf_name = cf_aggregates.first;
1270 const auto& naccess = cf_access_count.find(cf_name);
1271 row += ",";
1272 if (naccess != cf_access_count.end()) {
1273 row += std::to_string(percent(naccess->second, total_accesses));
1274 } else {
1275 row += "0";
1276 }
1277 }
1278 return row;
1279 }
1280
WritePercentAccessSummaryStats() const1281 void BlockCacheTraceAnalyzer::WritePercentAccessSummaryStats() const {
1282 std::map<TableReaderCaller, std::map<std::string, uint64_t>>
1283 caller_cf_accesses;
1284 uint64_t total_accesses = 0;
1285 auto block_callback =
1286 [&](const std::string& cf_name, uint64_t /*fd*/, uint32_t /*level*/,
1287 TraceType /*type*/, const std::string& /*block_key*/,
1288 uint64_t /*block_id*/, const BlockAccessInfo& block) {
1289 for (auto const& caller_num : block.caller_num_access_map) {
1290 const TableReaderCaller caller = caller_num.first;
1291 const uint64_t naccess = caller_num.second;
1292 caller_cf_accesses[caller][cf_name] += naccess;
1293 total_accesses += naccess;
1294 }
1295 };
1296 TraverseBlocks(block_callback);
1297
1298 const std::string output_path =
1299 output_dir_ + "/" + kFileNameSuffixPercentOfAccessSummary;
1300 std::ofstream out(output_path);
1301 if (!out.is_open()) {
1302 return;
1303 }
1304 std::string header("caller");
1305 for (auto const& cf_name : cf_aggregates_map_) {
1306 header += ",";
1307 header += cf_name.first;
1308 }
1309 out << header << std::endl;
1310 for (auto const& cf_naccess_it : caller_cf_accesses) {
1311 const TableReaderCaller caller = cf_naccess_it.first;
1312 std::string row;
1313 row += caller_to_string(caller);
1314 row += OutputPercentAccessStats(total_accesses, cf_naccess_it.second);
1315 out << row << std::endl;
1316 }
1317 out.close();
1318 }
1319
WriteDetailedPercentAccessSummaryStats(TableReaderCaller analyzing_caller) const1320 void BlockCacheTraceAnalyzer::WriteDetailedPercentAccessSummaryStats(
1321 TableReaderCaller analyzing_caller) const {
1322 std::map<uint32_t, std::map<std::string, uint64_t>> level_cf_accesses;
1323 std::map<TraceType, std::map<std::string, uint64_t>> bt_cf_accesses;
1324 uint64_t total_accesses = 0;
1325 auto block_callback =
1326 [&](const std::string& cf_name, uint64_t /*fd*/, uint32_t level,
1327 TraceType type, const std::string& /*block_key*/,
1328 uint64_t /*block_id*/, const BlockAccessInfo& block) {
1329 for (auto const& caller_num : block.caller_num_access_map) {
1330 const TableReaderCaller caller = caller_num.first;
1331 if (caller == analyzing_caller) {
1332 const uint64_t naccess = caller_num.second;
1333 level_cf_accesses[level][cf_name] += naccess;
1334 bt_cf_accesses[type][cf_name] += naccess;
1335 total_accesses += naccess;
1336 }
1337 }
1338 };
1339 TraverseBlocks(block_callback);
1340 {
1341 const std::string output_path =
1342 output_dir_ + "/" + caller_to_string(analyzing_caller) + "_level_" +
1343 kFileNameSuffixPercentOfAccessSummary;
1344 std::ofstream out(output_path);
1345 if (!out.is_open()) {
1346 return;
1347 }
1348 std::string header("level");
1349 for (auto const& cf_name : cf_aggregates_map_) {
1350 header += ",";
1351 header += cf_name.first;
1352 }
1353 out << header << std::endl;
1354 for (auto const& level_naccess_it : level_cf_accesses) {
1355 const uint32_t level = level_naccess_it.first;
1356 std::string row;
1357 row += std::to_string(level);
1358 row += OutputPercentAccessStats(total_accesses, level_naccess_it.second);
1359 out << row << std::endl;
1360 }
1361 out.close();
1362 }
1363 {
1364 const std::string output_path =
1365 output_dir_ + "/" + caller_to_string(analyzing_caller) + "_bt_" +
1366 kFileNameSuffixPercentOfAccessSummary;
1367 std::ofstream out(output_path);
1368 if (!out.is_open()) {
1369 return;
1370 }
1371 std::string header("bt");
1372 for (auto const& cf_name : cf_aggregates_map_) {
1373 header += ",";
1374 header += cf_name.first;
1375 }
1376 out << header << std::endl;
1377 for (auto const& bt_naccess_it : bt_cf_accesses) {
1378 const TraceType bt = bt_naccess_it.first;
1379 std::string row;
1380 row += block_type_to_string(bt);
1381 row += OutputPercentAccessStats(total_accesses, bt_naccess_it.second);
1382 out << row << std::endl;
1383 }
1384 out.close();
1385 }
1386 }
1387
WriteAccessCountSummaryStats(const std::vector<uint64_t> & access_count_buckets,bool user_access_only) const1388 void BlockCacheTraceAnalyzer::WriteAccessCountSummaryStats(
1389 const std::vector<uint64_t>& access_count_buckets,
1390 bool user_access_only) const {
1391 // x: buckets.
1392 // y: # of accesses.
1393 std::map<std::string, std::map<uint64_t, uint64_t>> bt_access_nblocks;
1394 std::map<std::string, std::map<uint64_t, uint64_t>> cf_access_nblocks;
1395 uint64_t total_nblocks = 0;
1396 auto block_callback =
1397 [&](const std::string& cf_name, uint64_t /*fd*/, uint32_t /*level*/,
1398 TraceType type, const std::string& /*block_key*/,
1399 uint64_t /*block_id*/, const BlockAccessInfo& block) {
1400 const std::string type_str = block_type_to_string(type);
1401 if (cf_access_nblocks.find(cf_name) == cf_access_nblocks.end()) {
1402 // initialize.
1403 for (auto& access : access_count_buckets) {
1404 cf_access_nblocks[cf_name][access] = 0;
1405 }
1406 }
1407 if (bt_access_nblocks.find(type_str) == bt_access_nblocks.end()) {
1408 // initialize.
1409 for (auto& access : access_count_buckets) {
1410 bt_access_nblocks[type_str][access] = 0;
1411 }
1412 }
1413 uint64_t naccesses = 0;
1414 for (auto const& caller_access : block.caller_num_access_map) {
1415 if (!user_access_only || is_user_access(caller_access.first)) {
1416 naccesses += caller_access.second;
1417 }
1418 }
1419 if (naccesses == 0) {
1420 return;
1421 }
1422 total_nblocks += 1;
1423 bt_access_nblocks[type_str].upper_bound(naccesses)->second += 1;
1424 cf_access_nblocks[cf_name].upper_bound(naccesses)->second += 1;
1425 };
1426 TraverseBlocks(block_callback);
1427 const std::string user_access_prefix =
1428 user_access_only ? "user_access_only_" : "all_access_";
1429 WriteStatsToFile("cf", access_count_buckets,
1430 user_access_prefix + kFileNameSuffixAccessCountSummary,
1431 cf_access_nblocks, total_nblocks);
1432 WriteStatsToFile("bt", access_count_buckets,
1433 user_access_prefix + kFileNameSuffixAccessCountSummary,
1434 bt_access_nblocks, total_nblocks);
1435 }
1436
BlockCacheTraceAnalyzer(const std::string & trace_file_path,const std::string & output_dir,const std::string & human_readable_trace_file_path,bool compute_reuse_distance,bool mrc_only,bool is_human_readable_trace_file,std::unique_ptr<BlockCacheTraceSimulator> && cache_simulator)1437 BlockCacheTraceAnalyzer::BlockCacheTraceAnalyzer(
1438 const std::string& trace_file_path, const std::string& output_dir,
1439 const std::string& human_readable_trace_file_path,
1440 bool compute_reuse_distance, bool mrc_only,
1441 bool is_human_readable_trace_file,
1442 std::unique_ptr<BlockCacheTraceSimulator>&& cache_simulator)
1443 : env_(ROCKSDB_NAMESPACE::Env::Default()),
1444 trace_file_path_(trace_file_path),
1445 output_dir_(output_dir),
1446 human_readable_trace_file_path_(human_readable_trace_file_path),
1447 compute_reuse_distance_(compute_reuse_distance),
1448 mrc_only_(mrc_only),
1449 is_human_readable_trace_file_(is_human_readable_trace_file),
1450 cache_simulator_(std::move(cache_simulator)) {}
1451
ComputeReuseDistance(BlockAccessInfo * info) const1452 void BlockCacheTraceAnalyzer::ComputeReuseDistance(
1453 BlockAccessInfo* info) const {
1454 assert(info);
1455 if (info->num_accesses == 0) {
1456 return;
1457 }
1458 uint64_t reuse_distance = 0;
1459 for (auto const& block_key : info->unique_blocks_since_last_access) {
1460 auto const& it = block_info_map_.find(block_key);
1461 // This block must exist.
1462 assert(it != block_info_map_.end());
1463 reuse_distance += it->second->block_size;
1464 }
1465 info->reuse_distance_count[reuse_distance] += 1;
1466 // We clear this hash set since this is the second access on this block.
1467 info->unique_blocks_since_last_access.clear();
1468 }
1469
RecordAccess(const BlockCacheTraceRecord & access)1470 Status BlockCacheTraceAnalyzer::RecordAccess(
1471 const BlockCacheTraceRecord& access) {
1472 ColumnFamilyAccessInfoAggregate& cf_aggr = cf_aggregates_map_[access.cf_name];
1473 SSTFileAccessInfoAggregate& file_aggr =
1474 cf_aggr.fd_aggregates_map[access.sst_fd_number];
1475 file_aggr.level = access.level;
1476 BlockTypeAccessInfoAggregate& block_type_aggr =
1477 file_aggr.block_type_aggregates_map[access.block_type];
1478 if (block_type_aggr.block_access_info_map.find(access.block_key) ==
1479 block_type_aggr.block_access_info_map.end()) {
1480 block_type_aggr.block_access_info_map[access.block_key].block_id =
1481 unique_block_id_;
1482 unique_block_id_++;
1483 }
1484 BlockAccessInfo& block_access_info =
1485 block_type_aggr.block_access_info_map[access.block_key];
1486 if (compute_reuse_distance_) {
1487 ComputeReuseDistance(&block_access_info);
1488 }
1489 block_access_info.AddAccess(access, access_sequence_number_);
1490 block_info_map_[access.block_key] = &block_access_info;
1491 uint64_t get_key_id = 0;
1492 if (access.caller == TableReaderCaller::kUserGet &&
1493 access.get_id != BlockCacheTraceHelper::kReservedGetId) {
1494 std::string user_key = ExtractUserKey(access.referenced_key).ToString();
1495 if (get_key_info_map_.find(user_key) == get_key_info_map_.end()) {
1496 get_key_info_map_[user_key].key_id = unique_get_key_id_;
1497 unique_get_key_id_++;
1498 }
1499 get_key_id = get_key_info_map_[user_key].key_id;
1500 get_key_info_map_[user_key].AddAccess(access, access_sequence_number_);
1501 }
1502
1503 if (compute_reuse_distance_) {
1504 // Add this block to all existing blocks.
1505 for (auto& cf_aggregates : cf_aggregates_map_) {
1506 for (auto& file_aggregates : cf_aggregates.second.fd_aggregates_map) {
1507 for (auto& block_type_aggregates :
1508 file_aggregates.second.block_type_aggregates_map) {
1509 for (auto& existing_block :
1510 block_type_aggregates.second.block_access_info_map) {
1511 existing_block.second.unique_blocks_since_last_access.insert(
1512 access.block_key);
1513 }
1514 }
1515 }
1516 }
1517 }
1518 return human_readable_trace_writer_.WriteHumanReadableTraceRecord(
1519 access, block_access_info.block_id, get_key_id);
1520 }
1521
Analyze()1522 Status BlockCacheTraceAnalyzer::Analyze() {
1523 SystemClock* clock = env_->GetSystemClock().get();
1524 std::unique_ptr<BlockCacheTraceReader> reader;
1525 Status s = Status::OK();
1526 if (is_human_readable_trace_file_) {
1527 reader.reset(new BlockCacheHumanReadableTraceReader(trace_file_path_));
1528 } else {
1529 std::unique_ptr<TraceReader> trace_reader;
1530 s = NewFileTraceReader(env_, EnvOptions(), trace_file_path_, &trace_reader);
1531 if (!s.ok()) {
1532 return s;
1533 }
1534 reader.reset(new BlockCacheTraceReader(std::move(trace_reader)));
1535 s = reader->ReadHeader(&header_);
1536 if (!s.ok()) {
1537 return s;
1538 }
1539 }
1540 if (!human_readable_trace_file_path_.empty()) {
1541 s = human_readable_trace_writer_.NewWritableFile(
1542 human_readable_trace_file_path_, env_);
1543 if (!s.ok()) {
1544 return s;
1545 }
1546 }
1547 uint64_t start = clock->NowMicros();
1548 uint64_t time_interval = 0;
1549 while (s.ok()) {
1550 BlockCacheTraceRecord access;
1551 s = reader->ReadAccess(&access);
1552 if (!s.ok()) {
1553 break;
1554 }
1555 if (!mrc_only_) {
1556 s = RecordAccess(access);
1557 if (!s.ok()) {
1558 break;
1559 }
1560 }
1561 if (trace_start_timestamp_in_seconds_ == 0) {
1562 trace_start_timestamp_in_seconds_ =
1563 access.access_timestamp / kMicrosInSecond;
1564 }
1565 trace_end_timestamp_in_seconds_ = access.access_timestamp / kMicrosInSecond;
1566 miss_ratio_stats_.UpdateMetrics(access.access_timestamp,
1567 is_user_access(access.caller),
1568 access.is_cache_hit == Boolean::kFalse);
1569 if (cache_simulator_) {
1570 cache_simulator_->Access(access);
1571 }
1572 access_sequence_number_++;
1573 uint64_t now = clock->NowMicros();
1574 uint64_t duration = (now - start) / kMicrosInSecond;
1575 if (duration > 10 * time_interval) {
1576 uint64_t trace_duration =
1577 trace_end_timestamp_in_seconds_ - trace_start_timestamp_in_seconds_;
1578 fprintf(stdout,
1579 "Running for %" PRIu64 " seconds: Processed %" PRIu64
1580 " records/second. Trace duration %" PRIu64
1581 " seconds. Observed miss ratio %.2f\n",
1582 duration, duration > 0 ? access_sequence_number_ / duration : 0,
1583 trace_duration, miss_ratio_stats_.miss_ratio());
1584 time_interval++;
1585 }
1586 }
1587 uint64_t now = clock->NowMicros();
1588 uint64_t duration = (now - start) / kMicrosInSecond;
1589 uint64_t trace_duration =
1590 trace_end_timestamp_in_seconds_ - trace_start_timestamp_in_seconds_;
1591 fprintf(stdout,
1592 "Running for %" PRIu64 " seconds: Processed %" PRIu64
1593 " records/second. Trace duration %" PRIu64
1594 " seconds. Observed miss ratio %.2f\n",
1595 duration, duration > 0 ? access_sequence_number_ / duration : 0,
1596 trace_duration, miss_ratio_stats_.miss_ratio());
1597 return s;
1598 }
1599
PrintBlockSizeStats() const1600 void BlockCacheTraceAnalyzer::PrintBlockSizeStats() const {
1601 HistogramStat bs_stats;
1602 std::map<TraceType, HistogramStat> bt_stats_map;
1603 std::map<std::string, std::map<TraceType, HistogramStat>> cf_bt_stats_map;
1604 auto block_callback =
1605 [&](const std::string& cf_name, uint64_t /*fd*/, uint32_t /*level*/,
1606 TraceType type, const std::string& /*block_key*/,
1607 uint64_t /*block_id*/, const BlockAccessInfo& block) {
1608 if (block.block_size == 0) {
1609 // Block size may be 0 when 1) compaction observes a cache miss and
1610 // does not insert the missing block into the cache again. 2)
1611 // fetching filter blocks in SST files at the last level.
1612 return;
1613 }
1614 bs_stats.Add(block.block_size);
1615 bt_stats_map[type].Add(block.block_size);
1616 cf_bt_stats_map[cf_name][type].Add(block.block_size);
1617 };
1618 TraverseBlocks(block_callback);
1619 fprintf(stdout, "Block size stats: \n%s", bs_stats.ToString().c_str());
1620 for (auto const& bt_stats : bt_stats_map) {
1621 print_break_lines(/*num_break_lines=*/1);
1622 fprintf(stdout, "Block size stats for block type %s: \n%s",
1623 block_type_to_string(bt_stats.first).c_str(),
1624 bt_stats.second.ToString().c_str());
1625 }
1626 for (auto const& cf_bt_stats : cf_bt_stats_map) {
1627 const std::string& cf_name = cf_bt_stats.first;
1628 for (auto const& bt_stats : cf_bt_stats.second) {
1629 print_break_lines(/*num_break_lines=*/1);
1630 fprintf(stdout,
1631 "Block size stats for column family %s and block type %s: \n%s",
1632 cf_name.c_str(), block_type_to_string(bt_stats.first).c_str(),
1633 bt_stats.second.ToString().c_str());
1634 }
1635 }
1636 }
1637
PrintAccessCountStats(bool user_access_only,uint32_t bottom_k,uint32_t top_k) const1638 void BlockCacheTraceAnalyzer::PrintAccessCountStats(bool user_access_only,
1639 uint32_t bottom_k,
1640 uint32_t top_k) const {
1641 HistogramStat access_stats;
1642 std::map<TraceType, HistogramStat> bt_stats_map;
1643 std::map<std::string, std::map<TraceType, HistogramStat>> cf_bt_stats_map;
1644 std::map<uint64_t, std::vector<std::string>> access_count_blocks;
1645 auto block_callback = [&](const std::string& cf_name, uint64_t /*fd*/,
1646 uint32_t /*level*/, TraceType type,
1647 const std::string& block_key, uint64_t /*block_id*/,
1648 const BlockAccessInfo& block) {
1649 uint64_t naccesses = 0;
1650 for (auto const& caller_access : block.caller_num_access_map) {
1651 if (!user_access_only || is_user_access(caller_access.first)) {
1652 naccesses += caller_access.second;
1653 }
1654 }
1655 if (naccesses == 0) {
1656 return;
1657 }
1658 if (type == TraceType::kBlockTraceDataBlock) {
1659 access_count_blocks[naccesses].push_back(block_key);
1660 }
1661 access_stats.Add(naccesses);
1662 bt_stats_map[type].Add(naccesses);
1663 cf_bt_stats_map[cf_name][type].Add(naccesses);
1664 };
1665 TraverseBlocks(block_callback);
1666 fprintf(stdout,
1667 "Block access count stats: The number of accesses per block. %s\n%s",
1668 user_access_only ? "User accesses only" : "All accesses",
1669 access_stats.ToString().c_str());
1670 uint32_t bottom_k_index = 0;
1671 for (auto naccess_it = access_count_blocks.begin();
1672 naccess_it != access_count_blocks.end(); naccess_it++) {
1673 bottom_k_index++;
1674 if (bottom_k_index >= bottom_k) {
1675 break;
1676 }
1677 std::map<TableReaderCaller, uint64_t> caller_naccesses;
1678 uint64_t naccesses = 0;
1679 for (auto const& block_id : naccess_it->second) {
1680 BlockAccessInfo* block = block_info_map_.find(block_id)->second;
1681 for (auto const& caller_access : block->caller_num_access_map) {
1682 if (!user_access_only || is_user_access(caller_access.first)) {
1683 caller_naccesses[caller_access.first] += caller_access.second;
1684 naccesses += caller_access.second;
1685 }
1686 }
1687 }
1688 std::string statistics("Caller:");
1689 for (auto const& caller_naccessess_it : caller_naccesses) {
1690 statistics += caller_to_string(caller_naccessess_it.first);
1691 statistics += ":";
1692 statistics +=
1693 std::to_string(percent(caller_naccessess_it.second, naccesses));
1694 statistics += ",";
1695 }
1696 fprintf(stdout,
1697 "Bottom %" PRIu32 " access count. Access count=%" PRIu64
1698 " nblocks=%" ROCKSDB_PRIszt " %s\n",
1699 bottom_k, naccess_it->first, naccess_it->second.size(),
1700 statistics.c_str());
1701 }
1702
1703 uint32_t top_k_index = 0;
1704 for (auto naccess_it = access_count_blocks.rbegin();
1705 naccess_it != access_count_blocks.rend(); naccess_it++) {
1706 top_k_index++;
1707 if (top_k_index >= top_k) {
1708 break;
1709 }
1710 for (auto const& block_id : naccess_it->second) {
1711 BlockAccessInfo* block = block_info_map_.find(block_id)->second;
1712 std::string statistics("Caller:");
1713 uint64_t naccesses = 0;
1714 for (auto const& caller_access : block->caller_num_access_map) {
1715 if (!user_access_only || is_user_access(caller_access.first)) {
1716 naccesses += caller_access.second;
1717 }
1718 }
1719 assert(naccesses > 0);
1720 for (auto const& caller_access : block->caller_num_access_map) {
1721 if (!user_access_only || is_user_access(caller_access.first)) {
1722 statistics += ",";
1723 statistics += caller_to_string(caller_access.first);
1724 statistics += ":";
1725 statistics +=
1726 std::to_string(percent(caller_access.second, naccesses));
1727 }
1728 }
1729 uint64_t ref_keys_accesses = 0;
1730 uint64_t ref_keys_does_not_exist_accesses = 0;
1731 for (auto const& ref_key_caller_access : block->key_num_access_map) {
1732 for (auto const& caller_access : ref_key_caller_access.second) {
1733 if (!user_access_only || is_user_access(caller_access.first)) {
1734 ref_keys_accesses += caller_access.second;
1735 }
1736 }
1737 }
1738 for (auto const& ref_key_caller_access :
1739 block->non_exist_key_num_access_map) {
1740 for (auto const& caller_access : ref_key_caller_access.second) {
1741 if (!user_access_only || is_user_access(caller_access.first)) {
1742 ref_keys_does_not_exist_accesses += caller_access.second;
1743 }
1744 }
1745 }
1746 statistics += ",nkeys=";
1747 statistics += std::to_string(block->num_keys);
1748 statistics += ",block_size=";
1749 statistics += std::to_string(block->block_size);
1750 statistics += ",num_ref_keys=";
1751 statistics += std::to_string(block->key_num_access_map.size());
1752 statistics += ",percent_access_ref_keys=";
1753 statistics += std::to_string(percent(ref_keys_accesses, naccesses));
1754 statistics += ",num_ref_keys_does_not_exist=";
1755 statistics += std::to_string(block->non_exist_key_num_access_map.size());
1756 statistics += ",percent_access_ref_keys_does_not_exist=";
1757 statistics +=
1758 std::to_string(percent(ref_keys_does_not_exist_accesses, naccesses));
1759 statistics += ",ref_data_size=";
1760 statistics += std::to_string(block->referenced_data_size);
1761 fprintf(stdout,
1762 "Top %" PRIu32 " access count blocks access_count=%" PRIu64
1763 " %s\n",
1764 top_k, naccess_it->first, statistics.c_str());
1765 }
1766 }
1767
1768 for (auto const& bt_stats : bt_stats_map) {
1769 print_break_lines(/*num_break_lines=*/1);
1770 fprintf(stdout, "Break down by block type %s: \n%s",
1771 block_type_to_string(bt_stats.first).c_str(),
1772 bt_stats.second.ToString().c_str());
1773 }
1774 for (auto const& cf_bt_stats : cf_bt_stats_map) {
1775 const std::string& cf_name = cf_bt_stats.first;
1776 for (auto const& bt_stats : cf_bt_stats.second) {
1777 print_break_lines(/*num_break_lines=*/1);
1778 fprintf(stdout,
1779 "Break down by column family %s and block type "
1780 "%s: \n%s",
1781 cf_name.c_str(), block_type_to_string(bt_stats.first).c_str(),
1782 bt_stats.second.ToString().c_str());
1783 }
1784 }
1785 }
1786
PrintDataBlockAccessStats() const1787 void BlockCacheTraceAnalyzer::PrintDataBlockAccessStats() const {
1788 HistogramStat existing_keys_stats;
1789 std::map<std::string, HistogramStat> cf_existing_keys_stats_map;
1790 HistogramStat non_existing_keys_stats;
1791 std::map<std::string, HistogramStat> cf_non_existing_keys_stats_map;
1792 HistogramStat block_access_stats;
1793 std::map<std::string, HistogramStat> cf_block_access_info;
1794 HistogramStat percent_referenced_bytes;
1795 std::map<std::string, HistogramStat> cf_percent_referenced_bytes;
1796 // Total number of accesses in a data block / number of keys in a data block.
1797 HistogramStat avg_naccesses_per_key_in_a_data_block;
1798 std::map<std::string, HistogramStat> cf_avg_naccesses_per_key_in_a_data_block;
1799 // The standard deviation on the number of accesses of a key in a data block.
1800 HistogramStat stdev_naccesses_per_key_in_a_data_block;
1801 std::map<std::string, HistogramStat>
1802 cf_stdev_naccesses_per_key_in_a_data_block;
1803 auto block_callback =
1804 [&](const std::string& cf_name, uint64_t /*fd*/, uint32_t /*level*/,
1805 TraceType /*type*/, const std::string& /*block_key*/,
1806 uint64_t /*block_id*/, const BlockAccessInfo& block) {
1807 if (block.num_keys == 0) {
1808 return;
1809 }
1810 // Use four decimal points.
1811 uint64_t percent_referenced_for_existing_keys = (uint64_t)(
1812 ((double)block.key_num_access_map.size() / (double)block.num_keys) *
1813 10000.0);
1814 uint64_t percent_referenced_for_non_existing_keys =
1815 (uint64_t)(((double)block.non_exist_key_num_access_map.size() /
1816 (double)block.num_keys) *
1817 10000.0);
1818 uint64_t percent_accesses_for_existing_keys =
1819 (uint64_t)(((double)block.num_referenced_key_exist_in_block /
1820 (double)block.num_accesses) *
1821 10000.0);
1822
1823 HistogramStat hist_naccess_per_key;
1824 for (auto const& key_access : block.key_num_access_map) {
1825 for (auto const& caller_access : key_access.second) {
1826 hist_naccess_per_key.Add(caller_access.second);
1827 }
1828 }
1829 uint64_t avg_accesses =
1830 static_cast<uint64_t>(hist_naccess_per_key.Average());
1831 uint64_t stdev_accesses =
1832 static_cast<uint64_t>(hist_naccess_per_key.StandardDeviation());
1833 avg_naccesses_per_key_in_a_data_block.Add(avg_accesses);
1834 cf_avg_naccesses_per_key_in_a_data_block[cf_name].Add(avg_accesses);
1835 stdev_naccesses_per_key_in_a_data_block.Add(stdev_accesses);
1836 cf_stdev_naccesses_per_key_in_a_data_block[cf_name].Add(stdev_accesses);
1837
1838 existing_keys_stats.Add(percent_referenced_for_existing_keys);
1839 cf_existing_keys_stats_map[cf_name].Add(
1840 percent_referenced_for_existing_keys);
1841 non_existing_keys_stats.Add(percent_referenced_for_non_existing_keys);
1842 cf_non_existing_keys_stats_map[cf_name].Add(
1843 percent_referenced_for_non_existing_keys);
1844 block_access_stats.Add(percent_accesses_for_existing_keys);
1845 cf_block_access_info[cf_name].Add(percent_accesses_for_existing_keys);
1846 };
1847 TraverseBlocks(block_callback);
1848 fprintf(stdout,
1849 "Histogram on the number of referenced keys existing in a block over "
1850 "the total number of keys in a block: \n%s",
1851 existing_keys_stats.ToString().c_str());
1852 for (auto const& cf_stats : cf_existing_keys_stats_map) {
1853 print_break_lines(/*num_break_lines=*/1);
1854 fprintf(stdout, "Break down by column family %s: \n%s",
1855 cf_stats.first.c_str(), cf_stats.second.ToString().c_str());
1856 }
1857 print_break_lines(/*num_break_lines=*/1);
1858 fprintf(
1859 stdout,
1860 "Histogram on the number of referenced keys DO NOT exist in a block over "
1861 "the total number of keys in a block: \n%s",
1862 non_existing_keys_stats.ToString().c_str());
1863 for (auto const& cf_stats : cf_non_existing_keys_stats_map) {
1864 print_break_lines(/*num_break_lines=*/1);
1865 fprintf(stdout, "Break down by column family %s: \n%s",
1866 cf_stats.first.c_str(), cf_stats.second.ToString().c_str());
1867 }
1868 print_break_lines(/*num_break_lines=*/1);
1869 fprintf(stdout,
1870 "Histogram on the number of accesses on keys exist in a block over "
1871 "the total number of accesses in a block: \n%s",
1872 block_access_stats.ToString().c_str());
1873 for (auto const& cf_stats : cf_block_access_info) {
1874 print_break_lines(/*num_break_lines=*/1);
1875 fprintf(stdout, "Break down by column family %s: \n%s",
1876 cf_stats.first.c_str(), cf_stats.second.ToString().c_str());
1877 }
1878 print_break_lines(/*num_break_lines=*/1);
1879 fprintf(
1880 stdout,
1881 "Histogram on the average number of accesses per key in a block: \n%s",
1882 avg_naccesses_per_key_in_a_data_block.ToString().c_str());
1883 for (auto const& cf_stats : cf_avg_naccesses_per_key_in_a_data_block) {
1884 fprintf(stdout, "Break down by column family %s: \n%s",
1885 cf_stats.first.c_str(), cf_stats.second.ToString().c_str());
1886 }
1887 print_break_lines(/*num_break_lines=*/1);
1888 fprintf(stdout,
1889 "Histogram on the standard deviation of the number of accesses per "
1890 "key in a block: \n%s",
1891 stdev_naccesses_per_key_in_a_data_block.ToString().c_str());
1892 for (auto const& cf_stats : cf_stdev_naccesses_per_key_in_a_data_block) {
1893 fprintf(stdout, "Break down by column family %s: \n%s",
1894 cf_stats.first.c_str(), cf_stats.second.ToString().c_str());
1895 }
1896 }
1897
PrintStatsSummary() const1898 void BlockCacheTraceAnalyzer::PrintStatsSummary() const {
1899 uint64_t total_num_files = 0;
1900 uint64_t total_num_blocks = 0;
1901 uint64_t total_num_accesses = 0;
1902 std::map<TraceType, uint64_t> bt_num_blocks_map;
1903 std::map<TableReaderCaller, uint64_t> caller_num_access_map;
1904 std::map<TableReaderCaller, std::map<TraceType, uint64_t>>
1905 caller_bt_num_access_map;
1906 std::map<TableReaderCaller, std::map<uint32_t, uint64_t>>
1907 caller_level_num_access_map;
1908 for (auto const& cf_aggregates : cf_aggregates_map_) {
1909 // Stats per column family.
1910 const std::string& cf_name = cf_aggregates.first;
1911 uint64_t cf_num_files = 0;
1912 uint64_t cf_num_blocks = 0;
1913 std::map<TraceType, uint64_t> cf_bt_blocks;
1914 uint64_t cf_num_accesses = 0;
1915 std::map<TableReaderCaller, uint64_t> cf_caller_num_accesses_map;
1916 std::map<TableReaderCaller, std::map<uint64_t, uint64_t>>
1917 cf_caller_level_num_accesses_map;
1918 std::map<TableReaderCaller, std::map<uint64_t, uint64_t>>
1919 cf_caller_file_num_accesses_map;
1920 std::map<TableReaderCaller, std::map<TraceType, uint64_t>>
1921 cf_caller_bt_num_accesses_map;
1922 total_num_files += cf_aggregates.second.fd_aggregates_map.size();
1923 for (auto const& file_aggregates : cf_aggregates.second.fd_aggregates_map) {
1924 // Stats per SST file.
1925 const uint64_t fd = file_aggregates.first;
1926 const uint32_t level = file_aggregates.second.level;
1927 cf_num_files++;
1928 for (auto const& block_type_aggregates :
1929 file_aggregates.second.block_type_aggregates_map) {
1930 // Stats per block type.
1931 const TraceType type = block_type_aggregates.first;
1932 cf_bt_blocks[type] +=
1933 block_type_aggregates.second.block_access_info_map.size();
1934 total_num_blocks +=
1935 block_type_aggregates.second.block_access_info_map.size();
1936 bt_num_blocks_map[type] +=
1937 block_type_aggregates.second.block_access_info_map.size();
1938 for (auto const& block_access_info :
1939 block_type_aggregates.second.block_access_info_map) {
1940 // Stats per block.
1941 cf_num_blocks++;
1942 for (auto const& stats :
1943 block_access_info.second.caller_num_access_map) {
1944 // Stats per caller.
1945 const TableReaderCaller caller = stats.first;
1946 const uint64_t num_accesses = stats.second;
1947 // Overall stats.
1948 total_num_accesses += num_accesses;
1949 caller_num_access_map[caller] += num_accesses;
1950 caller_bt_num_access_map[caller][type] += num_accesses;
1951 caller_level_num_access_map[caller][level] += num_accesses;
1952 // Column Family stats.
1953 cf_num_accesses += num_accesses;
1954 cf_caller_num_accesses_map[caller] += num_accesses;
1955 cf_caller_level_num_accesses_map[caller][level] += num_accesses;
1956 cf_caller_file_num_accesses_map[caller][fd] += num_accesses;
1957 cf_caller_bt_num_accesses_map[caller][type] += num_accesses;
1958 }
1959 }
1960 }
1961 }
1962
1963 // Print stats.
1964 print_break_lines(/*num_break_lines=*/3);
1965 fprintf(stdout, "Statistics for column family %s:\n", cf_name.c_str());
1966 fprintf(stdout,
1967 " Number of files:%" PRIu64 " Number of blocks: %" PRIu64
1968 " Number of accesses: %" PRIu64 "\n",
1969 cf_num_files, cf_num_blocks, cf_num_accesses);
1970 for (auto block_type : cf_bt_blocks) {
1971 fprintf(stdout, "Number of %s blocks: %" PRIu64 " Percent: %.2f\n",
1972 block_type_to_string(block_type.first).c_str(), block_type.second,
1973 percent(block_type.second, cf_num_blocks));
1974 }
1975 for (auto caller : cf_caller_num_accesses_map) {
1976 const uint64_t naccesses = caller.second;
1977 print_break_lines(/*num_break_lines=*/1);
1978 fprintf(stdout,
1979 "Caller %s: Number of accesses %" PRIu64 " Percent: %.2f\n",
1980 caller_to_string(caller.first).c_str(), naccesses,
1981 percent(naccesses, cf_num_accesses));
1982 fprintf(stdout, "Caller %s: Number of accesses per level break down\n",
1983 caller_to_string(caller.first).c_str());
1984 for (auto naccess_level :
1985 cf_caller_level_num_accesses_map[caller.first]) {
1986 fprintf(stdout,
1987 "\t Level %" PRIu64 ": Number of accesses: %" PRIu64
1988 " Percent: %.2f\n",
1989 naccess_level.first, naccess_level.second,
1990 percent(naccess_level.second, naccesses));
1991 }
1992 fprintf(stdout, "Caller %s: Number of accesses per file break down\n",
1993 caller_to_string(caller.first).c_str());
1994 for (auto naccess_file : cf_caller_file_num_accesses_map[caller.first]) {
1995 fprintf(stdout,
1996 "\t File %" PRIu64 ": Number of accesses: %" PRIu64
1997 " Percent: %.2f\n",
1998 naccess_file.first, naccess_file.second,
1999 percent(naccess_file.second, naccesses));
2000 }
2001 fprintf(stdout,
2002 "Caller %s: Number of accesses per block type break down\n",
2003 caller_to_string(caller.first).c_str());
2004 for (auto naccess_type : cf_caller_bt_num_accesses_map[caller.first]) {
2005 fprintf(stdout,
2006 "\t Block Type %s: Number of accesses: %" PRIu64
2007 " Percent: %.2f\n",
2008 block_type_to_string(naccess_type.first).c_str(),
2009 naccess_type.second, percent(naccess_type.second, naccesses));
2010 }
2011 }
2012 }
2013 print_break_lines(/*num_break_lines=*/3);
2014 fprintf(stdout, "Overall statistics:\n");
2015 fprintf(stdout,
2016 "Number of files: %" PRIu64 " Number of blocks: %" PRIu64
2017 " Number of accesses: %" PRIu64 "\n",
2018 total_num_files, total_num_blocks, total_num_accesses);
2019 for (auto block_type : bt_num_blocks_map) {
2020 fprintf(stdout, "Number of %s blocks: %" PRIu64 " Percent: %.2f\n",
2021 block_type_to_string(block_type.first).c_str(), block_type.second,
2022 percent(block_type.second, total_num_blocks));
2023 }
2024 for (auto caller : caller_num_access_map) {
2025 print_break_lines(/*num_break_lines=*/1);
2026 uint64_t naccesses = caller.second;
2027 fprintf(stdout, "Caller %s: Number of accesses %" PRIu64 " Percent: %.2f\n",
2028 caller_to_string(caller.first).c_str(), naccesses,
2029 percent(naccesses, total_num_accesses));
2030 fprintf(stdout, "Caller %s: Number of accesses per level break down\n",
2031 caller_to_string(caller.first).c_str());
2032 for (auto naccess_level : caller_level_num_access_map[caller.first]) {
2033 fprintf(stdout,
2034 "\t Level %d: Number of accesses: %" PRIu64 " Percent: %.2f\n",
2035 naccess_level.first, naccess_level.second,
2036 percent(naccess_level.second, naccesses));
2037 }
2038 fprintf(stdout, "Caller %s: Number of accesses per block type break down\n",
2039 caller_to_string(caller.first).c_str());
2040 for (auto naccess_type : caller_bt_num_access_map[caller.first]) {
2041 fprintf(stdout,
2042 "\t Block Type %s: Number of accesses: %" PRIu64
2043 " Percent: %.2f\n",
2044 block_type_to_string(naccess_type.first).c_str(),
2045 naccess_type.second, percent(naccess_type.second, naccesses));
2046 }
2047 }
2048 }
2049
parse_cache_config_file(const std::string & config_path)2050 std::vector<CacheConfiguration> parse_cache_config_file(
2051 const std::string& config_path) {
2052 std::ifstream file(config_path);
2053 if (!file.is_open()) {
2054 return {};
2055 }
2056 std::vector<CacheConfiguration> configs;
2057 std::string line;
2058 while (getline(file, line)) {
2059 CacheConfiguration cache_config;
2060 std::stringstream ss(line);
2061 std::vector<std::string> config_strs;
2062 while (ss.good()) {
2063 std::string substr;
2064 getline(ss, substr, ',');
2065 config_strs.push_back(substr);
2066 }
2067 // Sanity checks.
2068 if (config_strs.size() < 4) {
2069 fprintf(stderr, "Invalid cache simulator configuration %s\n",
2070 line.c_str());
2071 exit(1);
2072 }
2073 if (kSupportedCacheNames.find(" " + config_strs[0] + " ") ==
2074 std::string::npos) {
2075 fprintf(stderr, "Invalid cache name %s. Supported cache names are %s\n",
2076 line.c_str(), kSupportedCacheNames.c_str());
2077 exit(1);
2078 }
2079 cache_config.cache_name = config_strs[0];
2080 cache_config.num_shard_bits = ParseUint32(config_strs[1]);
2081 cache_config.ghost_cache_capacity = ParseUint64(config_strs[2]);
2082 for (uint32_t i = 3; i < config_strs.size(); i++) {
2083 uint64_t capacity = ParseUint64(config_strs[i]);
2084 if (capacity == 0) {
2085 fprintf(stderr, "Invalid cache capacity %s, %s\n",
2086 config_strs[i].c_str(), line.c_str());
2087 exit(1);
2088 }
2089 cache_config.cache_capacities.push_back(capacity);
2090 }
2091 configs.push_back(cache_config);
2092 }
2093 file.close();
2094 return configs;
2095 }
2096
parse_buckets(const std::string & bucket_str)2097 std::vector<uint64_t> parse_buckets(const std::string& bucket_str) {
2098 std::vector<uint64_t> buckets;
2099 std::stringstream ss(bucket_str);
2100 while (ss.good()) {
2101 std::string bucket;
2102 getline(ss, bucket, ',');
2103 buckets.push_back(ParseUint64(bucket));
2104 }
2105 buckets.push_back(port::kMaxUint64);
2106 return buckets;
2107 }
2108
block_cache_trace_analyzer_tool(int argc,char ** argv)2109 int block_cache_trace_analyzer_tool(int argc, char** argv) {
2110 ParseCommandLineFlags(&argc, &argv, true);
2111 if (FLAGS_block_cache_trace_path.empty()) {
2112 fprintf(stderr, "block cache trace path is empty\n");
2113 exit(1);
2114 }
2115 uint64_t warmup_seconds =
2116 FLAGS_cache_sim_warmup_seconds > 0 ? FLAGS_cache_sim_warmup_seconds : 0;
2117 uint32_t downsample_ratio = FLAGS_block_cache_trace_downsample_ratio > 0
2118 ? FLAGS_block_cache_trace_downsample_ratio
2119 : 0;
2120 std::vector<CacheConfiguration> cache_configs =
2121 parse_cache_config_file(FLAGS_block_cache_sim_config_path);
2122 std::unique_ptr<BlockCacheTraceSimulator> cache_simulator;
2123 if (!cache_configs.empty()) {
2124 cache_simulator.reset(new BlockCacheTraceSimulator(
2125 warmup_seconds, downsample_ratio, cache_configs));
2126 Status s = cache_simulator->InitializeCaches();
2127 if (!s.ok()) {
2128 fprintf(stderr, "Cannot initialize cache simulators %s\n",
2129 s.ToString().c_str());
2130 exit(1);
2131 }
2132 }
2133 BlockCacheTraceAnalyzer analyzer(
2134 FLAGS_block_cache_trace_path, FLAGS_block_cache_analysis_result_dir,
2135 FLAGS_human_readable_trace_file_path,
2136 !FLAGS_reuse_distance_labels.empty(), FLAGS_mrc_only,
2137 FLAGS_is_block_cache_human_readable_trace, std::move(cache_simulator));
2138 Status s = analyzer.Analyze();
2139 if (!s.IsIncomplete() && !s.ok()) {
2140 // Read all traces.
2141 fprintf(stderr, "Cannot process the trace %s\n", s.ToString().c_str());
2142 exit(1);
2143 }
2144 fprintf(stdout, "Status: %s\n", s.ToString().c_str());
2145 analyzer.WriteMissRatioCurves();
2146 analyzer.WriteMissRatioTimeline(1);
2147 analyzer.WriteMissRatioTimeline(kSecondInMinute);
2148 analyzer.WriteMissRatioTimeline(kSecondInHour);
2149 analyzer.WriteMissTimeline(1);
2150 analyzer.WriteMissTimeline(kSecondInMinute);
2151 analyzer.WriteMissTimeline(kSecondInHour);
2152
2153 if (FLAGS_mrc_only) {
2154 fprintf(stdout,
2155 "Skipping the analysis statistics since the user wants to compute "
2156 "MRC only");
2157 return 0;
2158 }
2159
2160 analyzer.PrintStatsSummary();
2161 if (FLAGS_print_access_count_stats) {
2162 print_break_lines(/*num_break_lines=*/3);
2163 analyzer.PrintAccessCountStats(
2164 /*user_access_only=*/false, FLAGS_analyze_bottom_k_access_count_blocks,
2165 FLAGS_analyze_top_k_access_count_blocks);
2166 print_break_lines(/*num_break_lines=*/3);
2167 analyzer.PrintAccessCountStats(
2168 /*user_access_only=*/true, FLAGS_analyze_bottom_k_access_count_blocks,
2169 FLAGS_analyze_top_k_access_count_blocks);
2170 }
2171 if (FLAGS_print_block_size_stats) {
2172 print_break_lines(/*num_break_lines=*/3);
2173 analyzer.PrintBlockSizeStats();
2174 }
2175 if (FLAGS_print_data_block_access_count_stats) {
2176 print_break_lines(/*num_break_lines=*/3);
2177 analyzer.PrintDataBlockAccessStats();
2178 }
2179 print_break_lines(/*num_break_lines=*/3);
2180
2181 if (!FLAGS_timeline_labels.empty()) {
2182 std::stringstream ss(FLAGS_timeline_labels);
2183 while (ss.good()) {
2184 std::string label;
2185 getline(ss, label, ',');
2186 if (label.find("block") != std::string::npos) {
2187 analyzer.WriteAccessTimeline(label, kSecondInMinute, true);
2188 analyzer.WriteAccessTimeline(label, kSecondInMinute, false);
2189 analyzer.WriteAccessTimeline(label, kSecondInHour, true);
2190 analyzer.WriteAccessTimeline(label, kSecondInHour, false);
2191 } else {
2192 analyzer.WriteAccessTimeline(label, kSecondInMinute, false);
2193 analyzer.WriteAccessTimeline(label, kSecondInHour, false);
2194 }
2195 }
2196 }
2197
2198 if (!FLAGS_analyze_callers.empty()) {
2199 analyzer.WritePercentAccessSummaryStats();
2200 std::stringstream ss(FLAGS_analyze_callers);
2201 while (ss.good()) {
2202 std::string caller;
2203 getline(ss, caller, ',');
2204 analyzer.WriteDetailedPercentAccessSummaryStats(string_to_caller(caller));
2205 }
2206 }
2207
2208 if (!FLAGS_access_count_buckets.empty()) {
2209 std::vector<uint64_t> buckets = parse_buckets(FLAGS_access_count_buckets);
2210 analyzer.WriteAccessCountSummaryStats(buckets, /*user_access_only=*/true);
2211 analyzer.WriteAccessCountSummaryStats(buckets, /*user_access_only=*/false);
2212 }
2213
2214 if (!FLAGS_reuse_distance_labels.empty() &&
2215 !FLAGS_reuse_distance_buckets.empty()) {
2216 std::vector<uint64_t> buckets = parse_buckets(FLAGS_reuse_distance_buckets);
2217 std::stringstream ss(FLAGS_reuse_distance_labels);
2218 while (ss.good()) {
2219 std::string label;
2220 getline(ss, label, ',');
2221 analyzer.WriteReuseDistance(label, buckets);
2222 }
2223 }
2224
2225 if (!FLAGS_reuse_interval_labels.empty() &&
2226 !FLAGS_reuse_interval_buckets.empty()) {
2227 std::vector<uint64_t> buckets = parse_buckets(FLAGS_reuse_interval_buckets);
2228 std::stringstream ss(FLAGS_reuse_interval_labels);
2229 while (ss.good()) {
2230 std::string label;
2231 getline(ss, label, ',');
2232 analyzer.WriteReuseInterval(label, buckets);
2233 }
2234 }
2235
2236 if (!FLAGS_reuse_lifetime_labels.empty() &&
2237 !FLAGS_reuse_lifetime_buckets.empty()) {
2238 std::vector<uint64_t> buckets = parse_buckets(FLAGS_reuse_lifetime_buckets);
2239 std::stringstream ss(FLAGS_reuse_lifetime_labels);
2240 while (ss.good()) {
2241 std::string label;
2242 getline(ss, label, ',');
2243 analyzer.WriteReuseLifetime(label, buckets);
2244 }
2245 }
2246
2247 if (FLAGS_analyze_blocks_reuse_k_reuse_window != 0) {
2248 std::vector<TraceType> block_types{TraceType::kBlockTraceIndexBlock,
2249 TraceType::kBlockTraceDataBlock,
2250 TraceType::kBlockTraceFilterBlock};
2251 for (auto block_type : block_types) {
2252 analyzer.WriteBlockReuseTimeline(
2253 FLAGS_analyze_blocks_reuse_k_reuse_window,
2254 /*user_access_only=*/true, block_type);
2255 analyzer.WriteBlockReuseTimeline(
2256 FLAGS_analyze_blocks_reuse_k_reuse_window,
2257 /*user_access_only=*/false, block_type);
2258 }
2259 }
2260
2261 if (!FLAGS_analyze_get_spatial_locality_labels.empty() &&
2262 !FLAGS_analyze_get_spatial_locality_buckets.empty()) {
2263 std::vector<uint64_t> buckets =
2264 parse_buckets(FLAGS_analyze_get_spatial_locality_buckets);
2265 std::stringstream ss(FLAGS_analyze_get_spatial_locality_labels);
2266 while (ss.good()) {
2267 std::string label;
2268 getline(ss, label, ',');
2269 analyzer.WriteGetSpatialLocality(label, buckets);
2270 }
2271 }
2272
2273 if (!FLAGS_analyze_correlation_coefficients_labels.empty()) {
2274 std::stringstream ss(FLAGS_analyze_correlation_coefficients_labels);
2275 while (ss.good()) {
2276 std::string label;
2277 getline(ss, label, ',');
2278 analyzer.WriteCorrelationFeatures(
2279 label, FLAGS_analyze_correlation_coefficients_max_number_of_values);
2280 }
2281 analyzer.WriteCorrelationFeaturesForGet(
2282 FLAGS_analyze_correlation_coefficients_max_number_of_values);
2283 }
2284
2285 if (!FLAGS_skew_labels.empty() && !FLAGS_skew_buckets.empty()) {
2286 std::vector<uint64_t> buckets = parse_buckets(FLAGS_skew_buckets);
2287 std::stringstream ss(FLAGS_skew_labels);
2288 while (ss.good()) {
2289 std::string label;
2290 getline(ss, label, ',');
2291 if (label.find("block") != std::string::npos) {
2292 analyzer.WriteSkewness(label, buckets,
2293 TraceType::kBlockTraceIndexBlock);
2294 analyzer.WriteSkewness(label, buckets,
2295 TraceType::kBlockTraceFilterBlock);
2296 analyzer.WriteSkewness(label, buckets, TraceType::kBlockTraceDataBlock);
2297 analyzer.WriteSkewness(label, buckets, TraceType::kTraceMax);
2298 } else {
2299 analyzer.WriteSkewness(label, buckets, TraceType::kTraceMax);
2300 }
2301 }
2302 }
2303 return 0;
2304 }
2305
2306 } // namespace ROCKSDB_NAMESPACE
2307
2308 #endif // GFLAGS
2309 #endif // ROCKSDB_LITE
2310