Supporting LIRS replacement algorithm in CacheLib #98

We has implemented the LIRS replacement in the cachelib source code and use cachebench to read the traces and generate the results.

The traces in the test are from CloudPhysics and were collected in caching analytics service in production VMware environments (As the trace files only contain block number, we set enableLookaside to true, and the value size is fixed at 1KB). Some trace files can be downloaded at here

Attached are LIRS's miss ratio curves in comparison with replacement algorithms currently in the cachelib, including LRU, LRU2Q, and TinyLFU (All algorithms simply adopt their default settings).

The results are very encouraging: where cachelib's existing algorithms don't perform well as expected (miss ratio curve don't decrease with increase of cache size), LIRS mostly fixes the performance issue. Some of the results are attached. Please take a look.

cachelib_results.pdf

The LIRS's source code for cachelib can be found at https://github.com/hansonzhao007/CacheLib, (in branch 'LIRS". Current implementation is a prototype, so it may not pass the unit-test in multithreading tests.)

To reproduce the results, you may follow these steps:

git clone --recurse-submodules https://github.com/hansonzhao007/CacheLib.git
cd CacheLib
git checkout LIRS
# external lib branch when testing
# fbthrift: 0b008a959
# fizz: b5cd3b59
# fmt: 094b66e8
# folly: c4d6fcdde
# gflags: e171aa2
# glog: 8f9ccfe
# googletest: 1b18723e
# sparsemap: 1186290
# wangle: 9f706148
# zstd: a488ba11
./contrib/build.sh -j
cp cachelib/cachebench/config.json ./build-cachelib/cachebench
cp cachelib/cachebench/run.py ./build-cachelib/cachebench
cd build-cachelib/cachebench
# before running the script, please modify the `trace_path` parameter in `run.py`
python3 run.py

We intend to contribute to the cachelib community by hopefully merging lirs into cachelib. To this end, we may continue to improve the lirs implementation by hearing from you and the rest of the community.