Delayed-Hits

Artifacts for the "Caching with Delayed Hits" paper as it appears in SIGCOMM '20.

Contents

This repository contains two artifacts:

1. A simulator that models Delayed Hits (in addition to traditional cache hits and misses) for a single-tiered cache hierarchy. We provide implementations of standard caching algorithms (such as Belady, LRU, ARC, and LHD), as well as their Minimum-AggregateDelay (MAD) variants, as described in the paper.
2. The BELATEDLY system, which computes a near-optimal solution to the offline delayed hits caching problem in polynomial time. BELATEDLY consists of two components: (a) A flow network engine that generates, optimizes, and solves a Minimum-Cost Multi-Commodity Flow (MCMCF) problem corresponding to a given instance of the delayed hits problem, and (b) a caching simulator (a simpler version of the one described above) that validates the solution generated by the flow network engine. We use Gurobi C++ as the underlying MCMCF solver.

Minimum Requirements

This code is known to be compatible with Ubuntu 16.04+, GCC 7+, CMake 3.10+, Boost C++ v1.70, and Gurobi v8.1. Note that Gurobi requires a license to use; an academic license is free and can be obtained here. The simulator, unlike BELATEDLY, does not use Gurobi, and can be used even if you don't have access to a license.

Installation (Linux)

Install g++-7+, CMake and make sure their dependencies are met:

sudo apt-get update
sudo apt-get install g++-[7+]
sudo apt-get install cmake

1. Installing Boost

Download Boost C++ (v1.70.0+) here, and extract the archive to a convenient location. In the top-level directory (e.g. ~/libs/boost_1_70_0/), run the bootstrap and installation scripts as follows (program_options is the only separately-compiled library we use):

./bootstrap.sh --with-libraries=program_options
sudo ./b2 -j12 toolset=gcc variant=release threading=multi address-model=64 cxxflags=-std=c++17 install

Ensure that program_options is installed and visible to CMake.

2. Installing Gurobi

As described earlier, Gurobi requires a license to use. If you can't obtain one but would like to run the simulator anyway, skip to Compiling this code without Gurobi. Otherwise, download Gurobi Optimizer v8.1.1 here, and follow the Software Installation Guide. Also set up your Gurobi license. At this point, the environment variables GUROBI_HOME and GRB_LICENSE_FILE should point to Gurobi's top-level (linux64) directory and license file, respectively.

Important: The static library that ships with Gurobi is not compatible with GCC 7+. As such, we need to build it from source. The following snippet recompiles the library using the updated toolchain and drops it in as a replacement for the shipped version:

cd $GUROBI_HOME/src/build
make
cp libgurobi_c++.a ../../lib/

3. Compiling this code

Clone this repository to a convenient location. In the top-level directory for this project, run the following snippet:

mkdir build && cd build
cmake ..
make

If compilation was successful, build/bin/ should contain executables for BELATEDLY (belatedly), as well as each available caching policy (cache_lru, etc).

3.a) Compiling this code without Gurobi

To compile the caching simulator without installing Gurobi, edit CMakeLists.txt in the top-level directory, and comment out the following line: add_subdirectory(belatedly). Now simply follow the steps in Compiling this code as usual.

Using the Simulator and BELATEDLY

To view the available command-line options, run build/bin/cache_{lru,arc,lhd,...} --help and build/bin/belatedly --help. Both the caching simulator and BELATEDLY are trace-driven; an example (anonymized) trace file containing 5K requests is provided in the data/ directory, where each line of the trace has the following format: timestamp;object_id. (Note: The timestamp field is ignored in the current implementation! At the moment, each line of the trace represents one timestep; to encode zero request arrivals on timestep x, simply leave the x'th line of the trace file empty.)

As a starting point, a good sanity check would be to make sure that Belady and BELATEDLY compute the same (optimal) cache schedule for Z=1 (no delayed hits). To verify this, run the following snippet:

build/bin/cache_belady --trace "data/trace.csv" --cscale 5 --zfactor 1
build/bin/belatedly --trace "data/trace.csv" --cscale 5 --zfactor 1

The total latency reported by both algorithms should be identical. Increasing the zfactor parameter demonstrates the effect of delayed hits.

Extending the Simulator

The caching simulator was designed with extensibility in mind, and we hope it enables developers to quickly implement and evaluate their own caching policies. We abstract out the basic caching functionality into two base classes: BaseCache, which represents a generic, single-tiered cache; this is in turn composed of one or more BaseCacheSets, each of which represents a generic, fully- associative cache set. Implementing a caching policy in the simulator entails providing implementations for classes derived from these. For a simple example, please refer to the class definitions for LRUCache and LRUCacheSet in caching/src/cache_lru.cpp.