# Approximate Miss Ratio Computation Using Sampling in libCacheSim: SHARDS and MINISIM Explained

> Discover how libCacheSim computes approximate miss ratios using SHARDS and MINISIM sampling profilers. Estimate miss-ratio curves from trace samples with high accuracy.

- Repository: [Juncheng Yang/libcachesim](https://github.com/1a1a11a/libcachesim)
- Tags: deep-dive
- Published: 2026-02-23

---

**Yes, libCacheSim performs approximate miss ratio computation using sampling through two built-in profilers—SHARDS and MINISIM—that estimate miss-ratio curves from trace samples with configurable rates as low as 1% while maintaining error margins below 0.1%.**

libCacheSim is a high-performance caching simulation framework designed for analyzing massive storage workloads. When evaluating **cache performance** across billions of requests, exhaustive simulation becomes prohibitively expensive. By leveraging **sampling-based approximate miss ratio computation**, the library enables rapid **miss-ratio curve (MRC)** generation without replaying every request, significantly reducing both computation time and memory overhead.

## Sampling-Based MRC Profilers in libCacheSim

libCacheSim implements two distinct sampling strategies within the `mrcProfiler` module, each optimized for different eviction algorithms and accuracy requirements. Both profilers are exposed through the command-line `mrcProfiler` tool and the C++ API defined in [`libCacheSim/mrcProfiler/mrcProfiler.h`](https://github.com/1a1a11a/libcachesim/blob/main/libCacheSim/mrcProfiler/mrcProfiler.h).

### SHARDS Profiler (Fixed-Rate and Fixed-Size Sampling)

The **SHARDS** profiler implements the Simple Hash-based Approximate Reuse Distance Sampling algorithm, specifically optimized for **LRU** cache analysis. It operates in two modes:

- **Fixed-rate sampling**: Processes a configurable percentage of requests (e.g., 1%) selected via hash-based filtering
- **Fixed-size sampling**: Maintains a bounded set of unique objects using reservoir-style sampling to limit memory consumption

The core logic resides in [`libCacheSim/mrcProfiler/mrcProfiler.cpp`](https://github.com/1a1a11a/libcachesim/blob/main/libCacheSim/mrcProfiler/mrcProfiler.cpp), with `MRCProfilerSHARDS::fixed_sample_rate_run()` handling percentage-based sampling (lines 92–170) and `MRCProfilerSHARDS::fixed_sample_size_run()` managing bounded unique-object sampling (lines 171–250). Both methods rely on exact LRU stack distances computed via a **SplayTree** (`rd_tree`) to estimate reuse distances for the sampled subset.

### MINISIM Profiler (Spatial Sampling)

The **MINISIM** profiler provides **spatial sampling** capabilities that work with any eviction algorithm supported by libCacheSim plug-ins, including LFU, FIFO, ARC, and S3FIFO. Unlike SHARDS, which approximates stack distances analytically, MINISIM replays the down-sampled trace through an actual cache simulator and rescales the results.

The sampling object is created via `create_spatial_sampler()` (lines 67–90), while the simulation and scaling logic execute within `MRCProfilerMINISIM::run()` (lines 165–227). After simulation, miss counts are multiplied by the inverse sampling ratio (`reader_->sampler->sampling_ratio_inv`) to project full-trace statistics.

## Internal Sampling Mechanisms

Understanding the hash-based selection and weighting systems is essential for configuring accurate approximate miss ratio computation.

### Hash-Based Request Selection

Both profilers use deterministic hash functions to select representative samples without bias. Each request’s object ID is hashed with a user-supplied salt via `get_hash_value_int_64_with_salt()` (defined in [`mrcProfiler.h`](https://github.com/1a1a11a/libcachesim/blob/main/mrcProfiler.h), lines 29–42).

- **Fixed-rate mode**: Requests are retained when the hash value falls below a threshold (`sample_max`) proportional to the desired sampling rate
- **Fixed-size mode**: The system tracks the smallest *N* hash values using a `MinValueMap` data structure, ensuring bounded memory usage regardless of trace length

This approach guarantees that sampling is both reproducible (given constant salt values) and spatially uniform across the workload.

### Online Stack-Distance Tracking

For SHARDS sampling, the profiler maintains a **SplayTree** instance (`rd_tree`) that stores the most recent access timestamps and object sizes for sampled requests. When a sampled object is accessed, `rd_tree.getDistance()` calculates the stack distance to the previous occurrence, which maps directly to an MRC bucket index.

You can see the tree manipulation logic in `fixed_sample_rate_run()` (lines 105–138) and `fixed_sample_size_run()` (lines 200–236), where distances are computed and recorded in histogram bins corresponding to cache sizes.

### Statistical Weighting and Scaling

Because only a fraction of requests are examined, the system applies inverse probability weighting to maintain unbiased estimates:

- Each sampled hit is up-scaled by `1 / sample_rate` 
- The first MRC bucket (representing compulsory misses at cache size zero) receives the un-sampled portion calculated as `n_req_ - sampled_cnt` for request counts and `sum_obj_size_req - sampled_size` for byte volumes

This weighting logic appears in lines 152–158 (fixed-rate) and 251–257 (fixed-size) of [`mrcProfiler.cpp`](https://github.com/1a1a11a/libcachesim/blob/main/mrcProfiler.cpp). For MINISIM, the scaling occurs post-simulation by dividing miss counts by the spatial sampling ratio.

## Practical Implementation Examples

libCacheSim provides both command-line tools and programmatic APIs for integrating sampling-based MRC analysis into evaluation pipelines.

### Command-Line Usage

The `mrcProfiler` binary accepts sampling parameters through the `--profiler-params` flag, supporting both SHARDS and MINISIM modes:

```bash

# LRU miss-ratio curve via SHARDS, 1% fixed-rate sampling with salt 42

./mrcProfiler data/cloudPhysicsIO.vscsi vscsi \
    --algo=LRU --profiler=SHARDS \
    --profiler-params=FIX_RATE,0.01,42 \
    --size=100MB,1GB,10

```

```bash

# FIFO miss-ratio curve via MINISIM, 1% spatial sampling, 8 threads

./mrcProfiler data/cloudPhysicsIO.vscsi vscsi \
    --algo=FIFO --profiler=MINISIM \
    --profiler-params=FIX_RATE,0.01,8 \
    --size=10MB,100MB,10

```

The quick-start guide in [`doc/quickstart_mrcProfiler.md`](https://github.com/1a1a11a/libcachesim/blob/main/doc/quickstart_mrcProfiler.md) documents all available options and performance benchmarks for various sampling configurations.

### C++ API Integration

For embedded applications, instantiate profilers directly using the C++ API:

```cpp
#include "libCacheSim/mrcProfiler/mrcProfiler.h"
#include "libCacheSim/reader.h"

int main() {
    // Open trace reader (vscsi format in this example)
    reader_t *reader = create_reader("data/cloudPhysicsIO.vscsi", "vscsi");

    // Configure SHARDS parameters for 1% fixed-rate sampling
    mrc_profiler_params_t params{};
    params.shards_params.enable_fix_size = false;
    params.shards_params.sample_rate = 0.01;
    params.shards_params.salt = 42;
    params.cache_algorithm_str = "LRU";
    params.profile_size = {100<<20, 200<<20, 400<<20, 800<<20, 1<<30};

    // Create and execute profiler
    MRCProfilerBase *prof = create_mrc_profiler(
        mrc_profiler_e::SHARDS_PROFILER,
        reader, "mrc_output.txt", params
    );
    
    prof->run();
    prof->print();

    delete prof;
    free_reader(reader);
}

```

The repository includes comprehensive unit tests in [`test/test_mrcProfiler.cpp`](https://github.com/1a1a11a/libcachesim/blob/main/test/test_mrcProfiler.cpp) demonstrating both sampling modes and validation against exact simulations.

## Summary

- **libCacheSim supports two sampling methodologies**: SHARDS for LRU-specific stack-distance approximation and MINISIM for general-purpose spatial sampling compatible with any eviction algorithm.
- **Hash-based selection ensures unbiased sampling**: Using `get_hash_value_int_64_with_salt()` with configurable salts provides reproducible sample selection across fixed-rate and fixed-size modes.
- **Statistical weighting maintains accuracy**: Inverse scaling (`1/sample_rate`) and explicit handling of un-sampled portions keep MRC error below 0.1% even at 1% sampling rates.
- **Multiple interfaces available**: Both the `mrcProfiler` CLI tool and the C++ API in [`mrcProfiler.h`](https://github.com/1a1a11a/libcachesim/blob/main/mrcProfiler.h) expose these capabilities for integration into automated evaluation pipelines.

## Frequently Asked Questions

### What sampling rates does libCacheSim support for approximate miss ratio computation?

libCacheSim supports sampling rates as low as **0.01 (1%)** while maintaining MRC error margins below 0.1% for billion-request traces. The `sample_rate` parameter accepts float values between 0 and 1, though rates below 0.001 are not recommended due to increased variance in the estimates.

### Which caching algorithms work with sampling-based MRC profilers?

**SHARDS** supports **LRU only**, as the algorithm relies on exact LRU stack distances computed via the SplayTree (`rd_tree`). **MINISIM** supports **any eviction algorithm** available in libCacheSim plug-ins, including LFU, FIFO, ARC, S3FIFO, and custom implementations, because it executes actual cache simulations on the sampled subset.

### How does libCacheSim ensure sampling accuracy with variable object sizes?

The system tracks both request counts and byte volumes separately. In `fixed_sample_rate_run()` and `fixed_sample_size_run()`, the code adjusts the first MRC bucket (size=0) using `sum_obj_size_req - sampled_size` to account for un-sampled object sizes, while hits are weighted by the inverse sampling probability. This dual-tracking ensures accurate byte-hit ratio estimation alongside request-based metrics.

### Can I combine spatial sampling with multi-threaded cache simulation?

Yes. The MINISIM profiler supports parallel execution through the thread parameter in `--profiler-params`. When using `create_spatial_sampler()`, you can specify the number of threads (e.g., 8) to process the down-sampled trace concurrently, with the scaling factor `sampling_ratio_inv` applied to the aggregated results in `MRCProfilerMINISIM::run()`.