libCacheSim - building and running cache simulations

• libCacheSim - building and running cache simulations
• News
• What is libCacheSim
• libCacheSim features
• Supported algorithms
  • Eviction algorithms
  • Admission algorithms
  • Prefetching algorithms
• Build and Install libCacheSim
  • One-line install
  • Install dependency
  • Build libCacheSim
  • Developer Setup
  • Pre-commit Hooks
• Usage
  • cachesim (a high-performance cache simulator)
  • basic usage
  • Run a single cache simulation
  • Run multiple cache simulations with different cache sizes
  • Debug cachesim
  • Plot miss ratio curve
  • Trace analysis
  • Miss ratio curves profiling
  • Using libCacheSim as a library
  • Extending libCacheSim (new algorithms and trace types)
• Open source cache traces
• Contributions
• Reference
• License
• Related

News

• 2024 Oct: S3-FIFO gets an upgrade! Please try out the new version (the old is now renamed to S3-FIFOv0).
• 2023 June: QDLP is available now, see our paper for details.
• 2023 Oct: S3-FIFO and SIEVE(https://sievecache.com) are available! These are very simple algorithms that are very effective in reducing cache misses. Try them out in libCacheSim and your production!
• 2024 Jan: We compiled a list of open-source cache datasets at the bottom of this page

---

What is libCacheSim

• a high-performance cache simulator for running cache simulations.
• a high-performance and versatile trace analyzer for analyzing different cache traces.
• a high-performance library for building cache simulators.

---

libCacheSim features

• High performance - over 20M requests/sec for a realistic trace replay.
• High memory efficiency - predictable and small memory footprint.
• State-of-the-art algorithms - eviction algorithms, admission algorithms, prefetching algorithms, sampling techniques, approximate miss ratio computation, see here.
• Parallelism out-of-the-box - uses the many CPU cores to speed up trace analysis and cache simulations.
• The ONLY feature-rich trace analyzer - all types of trace analysis you need, see here.
• Simple API - easy to build cache clusters, multi-layer caching, etc.; see here.
• Extensible - easy to support new trace types or eviction algorithms; see here.
• Efficient Miss Ratio Curve profiler - quickly build highly accurate miss ratio curves on large-scale workloads; see here.

---

Supported algorithms

cachesim supports the following algorithms:

Eviction algorithms

• FIFO, LRU, Clock, SLRU
• LFU, LFU with dynamic aging
• ARC, TwoQ, CLOCK-PRO
• Belady, BeladySize
• GDSF
• Hyperbolic
• LeCaR
• Cacheus
• LHD
• LRB
• GLCache
• WTinyLFU
• 3LCache
• QD-LP
• S3-FIFO
• Sieve

Admission algorithms

• Adaptsize
• Bloomfilter
• Prob
• Size

Prefetching algorithms

• OBL
• Mithril
• PG

---

Build and Install libCacheSim

One-line install

We provide some scripts for quick installation of libCacheSim.

cd scripts && bash install_dependency.sh && bash install_libcachesim.sh

If this does not work, please 1. let us know what system you are using and what error you get 2. read the following sections for self-installation.

Install dependency

libCacheSim uses cmake build system and has a few dependencies: glib, tcmalloc, zstd. Please see install.md for instructions on how to install the dependencies.

Build libCacheSim

cmake recommends out-of-source build, so we do it in a new directory:

git clone https://github.com/1a1a11a/libCacheSim
pushd libCacheSim
mkdir _build && cd _build
cmake .. && make -j
[sudo] make install
popd

Developer Setup

For developers, we provide tools to ensure code quality and consistent formatting:

Pre-commit Hooks

We provide a git pre-commit hook that runs linting checks before each commit, helping catch issues early:

# Install the pre-commit hook
bash scripts/setup-hooks.sh

The pre-commit hook: - Checks formatting with clang-format (if available) - Runs clang-tidy static analysis in parallel - Compiles modified files with strict compiler warnings enabled - Prevents committing code with formatting, static analysis, or compiler issues - Logs are preserved for debugging in .lint-logs/ directory

---

Usage

cachesim (a high-performance cache simulator)

After building and installing libCacheSim, cachesim should be in the _build/bin/ directory.

basic usage

./bin/cachesim trace_path trace_type eviction_algo cache_size [OPTION...]

use ./bin/cachesim --help to get more information.

Run a single cache simulation

Run the example traces using the LRU eviction algorithm and a 1 GB cache size.

# Note that no space between the cache size and the unit, and the unit is not case-sensitive
./bin/cachesim ../data/trace.vscsi vscsi lru 1gb 

Run multiple cache simulations with different cache sizes

# Note that there is no space between the cache sizes
./bin/cachesim ../data/trace.vscsi vscsi lru 1mb,16mb,256mb,8gb

# Besides absolute cache size, you can also use a fraction of the working set size
./bin/cachesim ../data/trace.vscsi vscsi lru 0.001,0.01,0.1,0.2

# besides using byte as the unit, you can also treat all objects having the same size, and the size is the number of objects
./bin/cachesim ../data/trace.vscsi vscsi lru 1000,16000 --ignore-obj-size 1

# use a csv trace, note the quotation marks when you have multiple options
./bin/cachesim ../data/trace.csv csv lru 1gb -t "time-col=2, obj-id-col=5, obj-size-col=4"

# use a csv trace with more options
./bin/cachesim ../data/trace.csv csv lru 1gb -t "time-col=2, obj-id-col=5, obj-size-col=4, delimiter=,, has-header=true"

See quick start cachesim for more usages.

Debug cachesim

We provide a debug script to help you debug cachesim with GDB. For detailed usage instructions, see debug guide.

# Basic usage
./scripts/debug.sh

# Debug with program arguments
./scripts/debug.sh -- data/cloudPhysicsIO.vscsi vscsi lru,s3fifo 100mb,1gb

Plot miss ratio curve

You can plot miss ratios of different algorithms and sizes, and plot the miss ratios over time.

# plot miss ratio over size
cd scripts
python3 plot_mrc_size.py --tracepath ../data/twitter_cluster52.csv --trace-format csv --trace-format-params="time-col=1,obj-id-col=2,obj-size-col=3,delimiter=," --algos=fifo,lru,lecar,s3fifo --sizes=0.001,0.002,0.005,0.01,0.02,0.05,0.1,0.2,0.3,0.4

# plot miss ratio over time
python3 plot_mrc_time.py --tracepath ../data/twitter_cluster52.csv --trace-format csv --trace-format-params="time-col=1, obj-id-col=2, obj-size-col=3, delimiter=,," --algos=fifo,lru,lecar,s3fifo --report-interval=30 --miss-ratio-type="accu"

# plot miss ratio over size using SHARDS
python3 plot_appr_mrc.py SHARDS ../data/twitter_cluster52.vscsi vscsi 0.01

# plot miss ratio over size using Miniature Simulations
python3 plot_appr_mrc.py MINI ../data/twitter_cluster52.vscsi vscsi s3fifo "0.0001,0.0002,0.0004,0.0008,0.001,0.002,0.004,0.008,0.01,0.02,0.04,0.08,0.1,0.2,0.4,0.8" 0.001,0.01,0.1,1 --extra_args "--ignore-obj-size 1" 

---

Trace analysis

libCacheSim also has a trace analyzer that provides a lot of useful information about the trace. And it is very fast, designed to work with billions of requests. It also comes with a set of scripts to help you analyze the trace. See trace analysis for more details.

---

Miss ratio curves profiling

Constructing fine-grained miss ratio curves for large-scale workloads is very demanding on CPU and memory resources. libCacheSim provides advanced miss ratio curves profiling tools to help you quickly build miss ratio curves for large-scale workloads. See mrcProfiler for more details.

---

Using libCacheSim as a library

libCacheSim can be used as a library for building cache simulators. For example, you can build a cache cluster with consistent hashing or a multi-layer cache simulator.

Here is a simplified example showing the basic APIs.

#include <libCacheSim.h>

/* open trace, see quickstart_lib.md for opening csv and binary trace */
reader_t *reader = open_trace("../data/trace.vscsi", VSCSI_TRACE, NULL);

/* create a container for reading from trace */
request_t *req = new_request();

/* create a LRU cache */
common_cache_params_t cc_params = {.cache_size=1024*1024U}; 
cache_t *cache = LRU_init(cc_params, NULL); 

/* counters */
uint64_t n_req = 0, n_miss = 0;

/* loop through the trace */
while (read_one_req(reader, req) == 0) {
    if (!cache->get(cache, req)) {
        n_miss++;
    }
    n_req++;
}

printf("miss ratio: %.4lf\n", (double)n_miss / n_req);

/* cleaning */
close_trace(reader);
free_request(req);
cache->cache_free(cache);

Save this to test.c and compile it with the below command. For libCacheSim.h to work correctly, we need the following libs to be installed first: glib and zstd. Please refer to the previous section, Installation.

gcc test.c $(pkg-config --cflags --libs libCacheSim glib-2.0) -o test.out -lm -lzstd

To run the executable,

./test.out

See here for more details, and see example folder for examples on how to use libCacheSim, such as building a cache cluster with consistent hashing, multi-layer cache simulators.

---

Extending libCacheSim (new algorithms and trace types)

libCacheSim supports txt, csv, and binary traces. We prefer binary traces because they allow libCacheSim to run faster, and the traces are more compact.

We also support zstd compressed binary traces without decompression. This allows you to store the traces with less space.

If you need to add a new trace type or a new algorithm, please see here for details.

We encourage the users to check deepWiki for a more detailed documentation.

---

Open source cach