cachesim replays a trace (a recorded list of requests) through a simulated cache and tells you how often the cache missed. Use it to answer questions like "how big does my cache need to be?" or "would S3-FIFO beat LRU on this workload?" without writing any code.
It knows dozens of eviction algorithms, reads many trace formats, and runs several simulations in parallel.
Build libCacheSim first. cachesim ends up in _build/bin/.
Every command on this page is run from the build directory, _build/, so the sample traces in data/ are at ../data/:
cd _buildWarning
The sample traces are tiny. They are good for trying commands, but far too small to compare algorithms. See cache_dataset for real ones.
./bin/cachesim ../data/cloudPhysicsIO.vscsi vscsi lru 1gbThe four arguments are always in this order:
| Argument | Example | Meaning |
|---|---|---|
| trace path | ../data/cloudPhysicsIO.vscsi |
the trace file, optionally zstd-compressed (.zst) |
| trace type | vscsi |
the file format, see Using your own trace |
| algorithm | lru |
the eviction algorithm, case-insensitive |
| cache size | 1gb |
how big the cache is |
After a few log lines, you get the result:
../data/cloudPhysicsIO.vscsi LRU cache size 1GiB, 113872 req, miss ratio 0.6297, byte miss ratio 0.7274, throughput 4.62 MQPS
- miss ratio is the fraction of requests that missed the cache.
- byte miss ratio is the same thing weighted by object size, which is what matters if you care about bandwidth.
- throughput is how fast the simulator ran, in millions of requests per second.
Results are also appended to result/<trace name>.cachesim in the current directory. Use -o to pick another path.
Run ./bin/cachesim --help to see every option.
Write sizes with a unit and no space: 1gb, 256mb, 100m. Units are not case-sensitive.
Give several sizes, separated by commas, and they run in parallel:
./bin/cachesim ../data/cloudPhysicsIO.vscsi vscsi lru 1mb,16mb,256mb,8gb
# spaces are fine if you quote the list
./bin/cachesim ../data/cloudPhysicsIO.vscsi vscsi lru "1mb, 16mb, 256mb, 8gb"You often don't know what sizes make sense for a new trace. Two options help:
Use a fraction of the working set. The working set size is the total size of all distinct objects in the trace. A number between 0 and 1 means "this fraction of the working set":
./bin/cachesim ../data/cloudPhysicsIO.vscsi vscsi lru 0.001,0.01,0.1,0.2Let cachesim pick. With auto (or 0), cachesim measures the working set and simulates at 0.1%, 0.3%, 1%, 3%, 10%, 20%, 40% and 80% of it. Sizes that would hold fewer than 100 objects are skipped.
./bin/cachesim ../data/cloudPhysicsIO.vscsi vscsi lru autoCount objects instead of bytes. With --ignore-obj-size 1, every object has size 1, so the cache size becomes a number of objects:
./bin/cachesim ../data/cloudPhysicsIO.vscsi vscsi lru 1000,16000 --ignore-obj-size 1List several algorithms, separated by commas. cachesim runs every algorithm at every size, in parallel:
# 4 algorithms at one size
./bin/cachesim ../data/cloudPhysicsIO.vscsi vscsi fifo,lru,arc,qdlp 0.01 --ignore-obj-size 1
# 4 algorithms x 4 sizes = 16 simulations
./bin/cachesim ../data/cloudPhysicsIO.vscsi vscsi fifo,lru,arc,qdlp 0.01,0.05,0.1,0.2 --ignore-obj-size 1At most --num-thread simulations run at once. The default is the number of CPU cores.
A few more examples:
./bin/cachesim ../data/cloudPhysicsIO.vscsi vscsi s3fifo auto
./bin/cachesim ../data/cloudPhysicsIO.vscsi vscsi sieve auto
./bin/cachesim ../data/cloudPhysicsIO.vscsi vscsi lecar auto
./bin/cachesim ../data/cloudPhysicsIO.vscsi vscsi lhd autoThe README lists every algorithm and the exact name to pass here. A few (GLCache, LRB, 3LCache, S4-FIFO) need an optional build flag. If you ask for one that wasn't compiled in, cachesim stops with do not support algorithm <name>.
belady, beladySize and beladyCompute cheat: they look into the future to decide what to evict. That makes them a useful lower bound, but they need a trace that records when each object is requested next. In practice that means an oracleGeneral trace:
./bin/cachesim ../data/cloudPhysicsIO.oracleGeneral.bin oracleGeneral beladySize autoUse beladySize when objects have different sizes, and belady with --ignore-obj-size 1. You can make an oracle trace from any other trace with traceConv. If your oracle trace contains zero-size requests, read oracle traces and zero-size requests first.
cachesim reads these trace types:
| Type | What it is |
|---|---|
csv |
a text file with one request per line and comma- (or other) separated columns |
txt |
a text file with one object id per line, nothing else |
binary |
any fixed-size binary record, described with a format string |
oracleGeneral |
libCacheSim's compact binary format, which includes next-access times |
lcs |
libCacheSim's own binary format, with a header that stores trace statistics |
vscsi, twr |
two specific binary formats used by the sample traces |
syn |
no file at all: a generated uniform or Zipf workload, see synthetic traces |
lcp |
LLM prefix-cache traces, see the lcp format |
Any of them can be zstd-compressed (.zst); cachesim reads them without decompressing first.
Tell cachesim which column holds what with -t (--trace-type-params). Columns are numbered from 1. The sample cloudPhysicsIO.csv has the header version,time,op,size,lbn, so:
./bin/cachesim ../data/cloudPhysicsIO.csv csv lru 1gb \
-t "time-col=2, obj-id-col=5, obj-size-col=4, obj-id-is-num=true"The settings you will use most:
| Key | Meaning |
|---|---|
obj-id-col |
column with the object id (required) |
time-col |
column with the timestamp, in seconds |
obj-size-col |
column with the object size, in bytes |
obj-id-is-num |
true if the ids are numbers |
delimiter |
the separator, e.g. delimiter=, or delimiter=\t |
has-header |
true if the first line is a header |
Time and size are optional, but many algorithms behave differently without them, so include them if your trace has them.
cachesim guesses the delimiter and whether there is a header. If it guesses wrong, set them yourself. Note the doubled comma in delimiter=,,: the first comma is the value, the second separates it from the next key.
./bin/cachesim ../data/cloudPhysicsIO.csv csv lru 1gb \
-t "time-col=2, obj-id-col=5, obj-size-col=4, obj-id-is-num=true, delimiter=,, has-header=true"About obj-id-is-num. By default cachesim treats ids as strings and hashes them. If the id column holds numbers, set obj-id-is-num=true, which is faster and uses less memory. cachesim notices numeric ids and refuses to guess:
[ERROR] csv.c: detect obj_id is numeric, please specify -t 'obj-id-is-num=1'
csv files must be plain ASCII; UTF-8 is not supported.
# txt: one object id per line
./bin/cachesim ../data/cloudPhysicsIO.txt txt lru 1gb
# binary: describe each record with a Python struct-style format string,
# then say which field (counting from 1) is the id and which is the size
./bin/cachesim ../data/cloudPhysicsIO.vscsi binary lru 1gb \
-t "format=<IIIHHQQ,obj-id-col=6,obj-size-col=2"
# oracleGeneral: time, id, size, and next access time
./bin/cachesim ../data/cloudPhysicsIO.oracleGeneral.bin oracleGeneral lru 1gbThe format string follows Python's struct module: < means little-endian, I is a 4-byte unsigned int, H 2 bytes, Q 8 bytes.
Tip
Binary traces are several times faster to replay than csv and use less memory. If you will run a trace more than once, convert it to oracleGeneral with traceConv first.
Many algorithms have parameters. Pass them with -e (--eviction-params) as key=value pairs separated by commas:
# SLRU with 4 segments
./bin/cachesim ../data/cloudPhysicsIO.vscsi vscsi slru 1gb -e n-seg=4To see what an algorithm accepts and its defaults, pass -e print:
./bin/cachesim ../data/cloudPhysicsIO.vscsi vscsi slru 1gb -e print
# current parameters: n-seg=4,seg-size=25:25:25:25An admission policy decides whether a missed object is worth inserting at all. Add one with -a:
# skip objects the first time they are seen, using a Bloom filter
./bin/cachesim ../data/cloudPhysicsIO.vscsi vscsi lru 1gb -a bloomFilterAvailable: bloomFilter, prob (admit with a fixed probability), size (reject large objects), sizeProbabilistic, and adaptSize. Pass their parameters with --admission-params, for example --admission-params="prob=0.8".
A prefetching policy loads objects before they are requested. Add one with -p:
# Mithril learns which objects tend to be accessed together
./bin/cachesim ../data/cloudPhysicsIO.vscsi vscsi lru 1gb -p MithrilAvailable: Mithril, OBL, and PG. Pass their parameters with --prefetch-params.
| Option | What it does |
|---|---|
--num-thread=4 |
run at most 4 simulations at once |
--num-req=1000000 |
stop after this many requests, handy for quick tests |
--warmup-sec=3600 |
use the first hour to warm the cache and leave it out of the results |
--ignore-obj-size=true |
treat every object as size 1 |
--consider-obj-metadata=true |
count each algorithm's per-object metadata against the cache size |
--use-ttl=false |
ignore TTLs in the trace (only matters in a -DSUPPORT_TTL=ON build, see below) |
--hashpower=16 |
size of the internal hash table, as a power of 2 (default 24, about 16M entries) |
--print-head-req=false |
don't print the first few requests at start-up |
-o my-output |
write results to my-output instead of result/<trace>.cachesim |
--verbose=0 |
print only the results, no log lines |
A few of these deserve a closer look.
Warmup. --warmup-sec is measured in trace time, so it has to be shorter than the trace. The sample trace covers two hours, so --warmup-sec=86400 (one day) uses up the whole trace and reports 0 req.
TTLs. A build configured with -DSUPPORT_TTL=ON honors the TTLs in the trace by default, and --use-ttl=false replays the trace as if it had none. A normal build ignores TTLs and rejects --use-ttl=true.
Hash table size. The default --hashpower=24 reserves room for about 16 million objects up front. On a small trace, lowering it saves a lot of memory. Replaying the sample trace drops from about 106 MB to 8 MB at --hashpower=16.
Note
Sampling-based algorithms such as RandomLRU and hyperbolic draw eviction candidates from the hash table, so their miss ratios shift slightly with --hashpower. Keep it fixed when you compare results.
- Analyze a trace to understand why algorithms behave the way they do.
- Build miss ratio curves quickly on very large traces.
- Try your own algorithm without changing libCacheSim, or add one to the library.