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