Quick Start

db_bench supports tracing block cache accesses. This section demonstrates how to trace accesses when running db_bench. It also shows how to analyze and evaluate caching policies using the generated trace file.

Create a database:

To trace block cache accesses when running benchmark:

  1. ./db_bench --benchmarks="readrandom" --use_existing_db --duration=60 \
  2. --key_size=20 --prefix_size=20 --keys_per_prefix=0 --value_size=100 \
  3. --cache_index_and_filter_blocks --cache_size=1048576 \
  4. --disable_auto_compactions=1 --disable_wal=1 --compression_type=none \
  5. --min_level_to_compress=-1 --compression_ratio=1 --num=10000000 \
  6. --threads=16 \
  7. -block_cache_trace_file="/tmp/binary_trace_test_example" \
  8. -block_cache_trace_max_trace_file_size_in_bytes=1073741824 \
  9. -block_cache_trace_sampling_frequency=1

Convert the trace file to human readable format:

  1. ./block_cache_trace_analyzer \
  2. -block_cache_trace_path=/tmp/binary_trace_test_example \
  3. -human_readable_trace_file_path=/tmp/human_readable_block_trace_test_example

Evaluate alternative caching policies:

  1. bash block_cache_pysim.sh /tmp/human_readable_block_trace_test_example /tmp/sim_results/bench 1 0 30

Plot graphs:

  1. python block_cache_trace_analyzer_plot.py /tmp/sim_results /tmp/sim_results_graphs

Tracing Block Cache Accesses

A trace option contains max_trace_file_size and sampling_frequency.

  • max_trace_file_size specifies the maximum size of the trace file. The tracing stops when the trace file size exceeds the specified max_trace_file_size.
  • sampling_frequency determines how frequent should RocksDB trace an access. RocksDB uses spatial downsampling such that it traces all accesses to sampled blocks. A sampling_frequency of 1 means tracing all block cache accesses. A sampling_frequency of 100 means tracing all accesses on ~1% blocks.

An example to start tracing block cache accesses:

Trace Format

We can convert the generated binary trace file into human readable trace file in csv format. It contains the following columns:

Cache Simulations

We support running cache simulators using both RocksDB built-in caches and caching policies written in python. The cache simulator replays the trace and reports the miss ratio given a cache capacity and a caching policy.

To replay the trace and evaluate alternative policies, we first need to provide a cache configuration file. An example file contains the following content:

  1. lru,0,0,16M,256M,1G,2G,4G,8G,12G,16G,1T

Cache configuration file format:

Next, we can start simulating caches.

  1. ./block_cache_trace_analyzer -mrc_only=true \
  2. -block_cache_trace_downsample_ratio=100 \
  3. -block_cache_trace_path=/tmp/binary_trace_test_example \
  4. -block_cache_sim_config_path=/tmp/cache_config \
  5. -block_cache_analysis_result_dir=/tmp/binary_trace_test_example_results \
  6. -cache_sim_warmup_seconds=3600

It contains two important parameters:

block_cache_trace_downsample_ratio: The sampling frequency used to collect the trace. The simulator scales down the given cache size by this factor. For example, with downsample_ratio of 100, the cache simulator creates a 1 GB cache to simulate a 100 GB cache.

cache_sim_warmup_seconds: The number of seconds used for warmup. The reported miss ratio does NOT include the number of misses/accesses during the warmup.

The analyzer outputs a few files:

  • A miss ratio curve file: {trace_duration_in_seconds}_{total_accesses}_mrc.
  • Three miss ratio timeline files per second (1), per minute (60), and per hour (3600).
  • Three number of misses timeline files per second (1), per minute (60), and per hour (3600).

Python Cache Simulations

We also support a more diverse set of caching policies written in python. In addition to LRU, it provides replacement policies using reinforcement learning, cost class, and more. To use the python cache simulator, we need to first convert the binary trace file into human readable trace file.

  1. ./block_cache_trace_analyzer \
  2. -block_cache_trace_path=/tmp/binary_trace_test_example \
  3. -human_readable_trace_file_path=/tmp/human_readable_block_trace_test_example

block_cache_pysim.py options:

  1. 1) Cache type (ts, linucb, arc, lru, opt, pylru, pymru, pylfu, pyhb, gdsize, trace). 
  2. One may evaluate the hybrid row_block cache by appending '_hybrid' to a cache_type, e.g., ts_hybrid. 
  3. Note that hybrid is not supported with opt and trace. 
  4. 2) Cache size (xM, xG, xT).
  5. 3) The sampling frequency used to collect the trace. 
  6. (The simulation scales down the cache size by the sampling frequency).
  7. 4) Warmup seconds (The number of seconds used for warmup).
  8. 5) Trace file path.
  9. 6) Result directory (A directory that saves generated results)
  10. 7) Max number of accesses to process. (Replay the entire trace if set to -1.)
  11. 8) The target column family. (The simulation will only run accesses on the target column family.

We also provide a bash script to simulate a batch of cache configurations:

  1. Usage: ./block_cache_pysim.sh trace_file_path result_dir downsample_size warmup_seconds max_jobs
  3. -max_jobs: The maximum number of simulators to run at a time.

One example:

  1. bash block_cache_pysim.sh /tmp/human_readable_block_trace_test_example /tmp/sim_results/bench 1 0 30

block_cache_pysim.py output the following files:

  • A miss ratio curve file: data-ml-mrc-{cache_type}-{cache_size}-{target_cf_name}.
  • Two files on the timeline of miss ratios per minute (60), and per hour (3600).
  • Two files on the timeline of number of misses per second (1), per minute (60), and per hour (3600). For ts and linucb, it also outputs the following files:
  • Two files on the timeline of percentage of times a policy is selected: per minute (60) and per hour (3600).
  • Two files on the timeline of number of times a policy is selected: per minute (60) and per hour (3600).

block_cache_pysim.sh combines the outputs of block_cache_pysim.py into following files:

  • One miss ratio curve file per target column family: ml_{target_cf_name}_mrc
  • One files on the timeline of number of misses per {target_cf_name}{capacity}{time_unit}: ml_{target_cf_name}{capacity}{time_unit}miss_timeline
  • One files on the timeline of miss ratios per {target_cf_name}{capacity}{time_unit}:
  • One files on the timeline of number of times a policy is selected per {target_cf_name}{capacity}{time_unit}: ml_{target_cf_name}{capacity}{time_unit}policy_timeline
  • One files on the timeline of percentage of times a policy is selected per {target_cf_name}{capacity}{time_unit}: ml_{target_cf_name}{capacity}{time_unit}policy_ratio_timeline

Supported Cache Simulators

py* caches use random sampling at eviction time. It samples 64 random entries in the cache, sorts these entries based on a priority function, e.g., LRU, and evicts from the lowest priority entry until the cache has enough capacity to insert the new entry.

pycc* caches group cached entries by a cost class. The cache maintains aggregated statistics for each cost class such as number of hits, total size. A cached entry is also tagged with one cost class. At eviction time, the cache samples 64 random entries and group them by their cost class. It then evicts entries based on their cost class’s statistics.

ts and linucb are two caches using reinforcement learning. The cache is configured with N policies, e.g., LRU, MRU, LFU, etc. The cache learns which policy is the best overtime and selects the best policy for eviction. The cache rewards the selected policy if the policy has not evicted the missing key before. ts does not use any feature of a block while linucb uses three features: a block’s level, column family, and block type.

trace reports the misses observed in the collected trace.

Analyzing Block Cache Traces

The block_cache_trace_analyzer analyzes a trace file and outputs useful statistics of the access pattern. It provides insights into how to tune and improve a caching policy.

The block_cache_trace_analyzer may output statistics into multiple csv files saved in a result directory. We can plot graphs on these statistics using block_cache_trace_analyzer_plot.py.

Analyzer options:

  1.  -access_count_buckets (Group number of blocks by their access count given
  2.   these buckets. If specified, the analyzer will output a detailed analysis
  3.   on the number of blocks grouped by their access count break down by block
  4.   type and column family.) type: string default: ""
  5. -analyze_blocks_reuse_k_reuse_window (Analyze the percentage of blocks that
  6.   are accessed in the [k, 2*k] seconds are accessed again in the next [2*k,
  7.   3*k], [3*k, 4*k],...,[k*(n-1), k*n] seconds. ) type: int32 default: 0
  8. -analyze_bottom_k_access_count_blocks (Print out detailed access
  9.   information for blocks with their number of accesses are the bottom k
  10.   among all blocks.) type: int32 default: 0
  11. -analyze_callers (The list of callers to perform a detailed analysis on. If
  12.   speicfied, the analyzer will output a detailed percentage of accesses for
  13.   each caller break down by column family, level, and block type. A list of
  14.   available callers are: Get, MultiGet, Iterator, ApproximateSize,
  15.   VerifyChecksum, SSTDumpTool, ExternalSSTIngestion, Repair, Prefetch,
  16.   Compaction, CompactionRefill, Flush, SSTFileReader, Uncategorized.)
  17.   type: string default: ""
  18. -analyze_correlation_coefficients_labels (Analyze the correlation
  19.   coefficients of features such as number of past accesses with regard to
  20.   the number of accesses till the next access.) type: string default: ""
  21. -analyze_correlation_coefficients_max_number_of_values (The maximum number
  22.   of values for a feature. If the number of values for a feature is larger
  23.   than this max, it randomly selects 'max' number of values.) type: int32
  24.   default: 1000000
  25. -analyze_get_spatial_locality_buckets (Group data blocks by their
  26.   statistics using these buckets.) type: string default: ""
  27. -analyze_get_spatial_locality_labels (Group data blocks using these
  28.   labels.) type: string default: ""
  29. -analyze_top_k_access_count_blocks (Print out detailed access information
  30.   for blocks with their number of accesses are the top k among all blocks.)
  31.   type: int32 default: 0
  32. -block_cache_analysis_result_dir (The directory that saves block cache
  33.   analysis results.) type: string default: ""
  34. -block_cache_sim_config_path (The config file path. One cache configuration
  35.   per line. The format of a cache configuration is
  36.   cache_name,num_shard_bits,ghost_capacity,cache_capacity_1,...,cache_capacity_N. 
  37.   Supported cache names are lru, lru_priority, lru_hybrid. User may also add 
  38.   a prefix 'ghost_' to a cache_name to add a ghost cache in front of the real 
  39.   cache. ghost_capacity and cache_capacity can be xK, xM or xG where 
  40.   x is a positive number.)
  41.   type: string default: ""
  42. -block_cache_trace_downsample_ratio (The trace collected accesses on one in
  43.   every block_cache_trace_downsample_ratio blocks. We scale down the
  44.   simulated cache size by this ratio.) type: int32 default: 1
  45. -block_cache_trace_path (The trace file path.) type: string default: ""
  46.   caches. The hit/miss counters are reset after the warmup completes.)
  47.   type: int32 default: 0
  48. -human_readable_trace_file_path (The filt path that saves human readable
  49.   access records.) type: string default: ""
  50. -mrc_only (Evaluate alternative cache policies only. When this flag is
  51.   true, the analyzer does NOT maintain states of each block in memory for
  52.   analysis. It only feeds the accesses into the cache simulators.)
  53.   type: bool default: false
  54. -print_access_count_stats (Print access count distribution and the
  55.   distribution break down by block type and column family.) type: bool
  56.   default: false
  57. -print_block_size_stats (Print block size distribution and the distribution
  58.   break down by block type and column family.) type: bool default: false
  59. -print_data_block_access_count_stats (Print data block accesses by user Get
  60.   and Multi-Get.) type: bool default: false
  61. -reuse_distance_buckets (Group blocks by their reuse distances given these
  62.   buckets. For example, if 'reuse_distance_buckets' is '1K,1M,1G', we will
  63.   create four buckets. The first three buckets contain the number of blocks
  64.   with reuse distance less than 1KB, between 1K and 1M, between 1M and 1G,
  65.   respectively. The last bucket contains the number of blocks with reuse
  66.   distance larger than 1G. ) type: string default: ""
  67. -reuse_distance_labels (Group the reuse distance of a block using these
  68.   labels. Reuse distance is defined as the cumulated size of unique blocks
  69.   read between two consecutive accesses on the same block.) type: string
  70.   default: ""
  71. -reuse_interval_buckets (Group blocks by their reuse interval given these
  72.   buckets. For example, if 'reuse_distance_buckets' is '1,10,100', we will
  73.   create four buckets. The first three buckets contain the number of blocks
  74.   with reuse interval less than 1 second, between 1 second and 10 seconds,
  75.   between 10 seconds and 100 seconds, respectively. The last bucket
  76.   contains the number of blocks with reuse interval longer than 100
  77.   seconds.) type: string default: ""
  78. -reuse_interval_labels (Group the reuse interval of a block using these
  79.   labels. Reuse interval is defined as the time between two consecutive
  80.   accesses on the same block.) type: string default: ""
  81. -reuse_lifetime_buckets (Group blocks by their reuse lifetime given these
  82.   buckets. For example, if 'reuse_lifetime_buckets' is '1,10,100', we will
  83.   create four buckets. The first three buckets contain the number of blocks
  84.   with reuse lifetime less than 1 second, between 1 second and 10 seconds,
  85.   between 10 seconds and 100 seconds, respectively. The last bucket
  86.   contains the number of blocks with reuse lifetime longer than 100
  87.   seconds.) type: string default: ""
  88. -reuse_lifetime_labels (Group the reuse lifetime of a block using these
  89.   labels. Reuse lifetime is defined as the time interval between the first
  90.   access on a block and the last access on the same block. For blocks that
  91.   are only accessed once, its lifetime is set to kMaxUint64.) type: string
  92.   default: ""
  93. -skew_buckets (Group the skew labels using these buckets.) type: string
  94.   default: ""
  95. -skew_labels (Group the access count of a block using these labels.)
  96.   type: string default: ""
  97. -timeline_labels (Group the number of accesses per block per second using
  98.   these labels. Possible labels are a combination of the following: cf
  99.   (column family), sst, level, bt (block type), caller, block. For example,
  100.   label "cf_bt" means the number of acccess per second is grouped by unique
  101.   pairs of "cf_bt". A label "all" contains the aggregated number of
  102.   accesses per second across all possible labels.) type: string default: ""

An example that outputs a statistics summary of the access pattern:

  1. ./block_cache_trace_analyzer -block_cache_trace_path=/tmp/test_trace_file_path

Another example:

  1. python block_cache_trace_analyzer_plot.py /tmp/sim_results /tmp/sim_results_graphs