# How to Efficiently Process Very Large Cache Traces (Billions of Requests) with libCacheSim

> Efficiently process billions of requests with libCacheSim. Discover how to manage large cache traces using memory mapping, sampling, and thread pools for constant memory and high CPU use.

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

---

**LibCacheSim processes billion-request workloads using memory-mapped binary traces, configurable request sampling, and GLib thread pools to keep memory usage constant while maximizing CPU utilization.**

Processing cache traces containing billions of requests poses significant memory and throughput challenges for standard analysis tools. The 1a1a11a/libcachesim library is engineered specifically for massive-scale workloads, combining zero-copy file access, statistical sampling, and parallel simulation architectures. This guide explains the specific mechanisms in the source code that enable efficient processing of terabyte-scale trace files on commodity hardware.

## Memory-Mapped Binary Traces for Constant Memory Footprint

### Zero-Copy Access with mmap

In [`libCacheSim/traceReader/reader.c`](https://github.com/1a1a11a/libcachesim/blob/main/libCacheSim/traceReader/reader.c), the `setup_reader()` function (lines 31-39) maps binary trace files directly into the process's virtual address space using `mmap()`. This technique allows the operating system to page data on-demand from disk into RAM, ensuring that **memory-mapped** regions consume only the working set size rather than the full file size.

```c
// From reader.c - setup_reader() maps the file
reader->mapped_file = mmap(NULL, reader->file_size, PROT_READ, 
                           MAP_PRIVATE, reader->fd, 0);

```

By avoiding explicit `read()` syscalls and buffer allocations, libCacheSim achieves **O(1) memory footprint** regardless of trace size. The library supports multiple binary formats—including `oracleGeneralBin`, `vscsi`, and `lcs`—which are parsed via pointer arithmetic directly on the mapped region without temporary string buffers.

### Transparent ZSTD Compression

When `setup_reader()` detects a `.zst` file suffix (lines 53-66), it automatically instantiates a ZSTD decompression stream. This allows analysts to store compressed traces on disk while maintaining the same streaming throughput, as decompression occurs block-by-block during the memory-mapped read.

## Streaming Parsers and Request Sampling

### Incremental Text Trace Handling

For CSV or plain-text traces that cannot be memory-mapped, libCacheSim employs a **streaming** parser in `read_one_req()`. The implementation uses `getline()` to fill a reusable line buffer (`reader->line_buf`) rather than loading the entire file, ensuring that even terabyte-sized ASCII traces are processed with minimal heap allocation.

### Statistical Sampling to Reduce CPU Work

To further accelerate processing, libCacheSim integrates a **sampler** object directly into the read pipeline. In [`reader.c`](https://github.com/1a1a11a/libcachesim/blob/main/reader.c) (lines 11-31), the `read_one_req()` function wraps the read operation in a sampling loop:

```c
// Sampler logic inside read_one_req()
while (!reader->sampler->sample(reader->sampler, req)) {
    // Skip this request, read next
    read_one_req(reader, req);
}

```

Users can configure uniform or weighted sampling ratios (e.g., 0.01 for 1% sampling) to process only a statistical fraction of billions of requests. This reduces CPU cycles and cache pressure while preserving temporal locality patterns, making it ideal for miss-ratio curve estimation on massive datasets.

## Parallel Simulation Architecture

### GLib Thread Pool Implementation

In [`libCacheSim/profiler/simulator.c`](https://github.com/1a1a11a/libcachesim/blob/main/libCacheSim/profiler/simulator.c) (lines 39-68 and 84-106), libCacheSim implements **parallel simulation** using `GThreadPool`. The `_simulate()` worker function clones the original `reader_t` structure for each thread, allowing every core to iterate over the trace independently without file contention.

### Multi-Size and Multi-Algorithm APIs

The library exposes two primary parallel entry points:

- **`simulate_at_multi_sizes()`**: Runs the same cache algorithm across a range of cache sizes (e.g., 1 MiB to 1 GiB) using cloned readers.
- **`simulate_with_multi_caches()`**: Runs different algorithms (e.g., LRU vs. FIFO) concurrently on the same trace.

Because each cloned reader maintains its own file offset (or separate `FILE*` handle for text traces), the underlying trace file is never read twice from disk. Binary traces share the same `mmap` region across threads, while text traces utilize independent stream buffers.

```c
// Example: Parallel simulation entry point from simulator.c
cache_stat_t *simulate_at_multi_sizes(reader_t *reader, cache_t *cache,
                                     uint64_t step_size, void *params,
                                     int warmup_sec, int num_reqs,
                                     int num_threads, bool verbose);

```

## Practical Implementation Examples

### C API: Parallel LRU Simulation

The following example demonstrates opening a binary trace and evaluating LRU across 1024 cache sizes using eight threads:

```c
#include <libCacheSim.h>

int main() {
    // Memory-map the binary trace (auto-detects ZSTD)
    reader_t *reader = open_trace("twitter_cluster52.vscsi", 
                                  VSCSI_TRACE, NULL);
    
    // Create prototype LRU instance
    cache_t *lru = LRU_init((common_cache_params_t){0}, NULL);
    
    // Simulate 1 MiB to 1 GiB in 1 MiB steps using 8 threads
    cache_stat_t *stats = simulate_at_multi_sizes(
        reader, lru, 1ULL << 20, NULL, 0, 0, 8, false
    );
    
    // Access results: stats[i].n_miss / stats[i].n_req
    for (int i = 0; i < 1024; i++) {
        printf("Size: %lu, Miss Ratio: %.4f\n", 
               stats[i].cache_size,
               (double)stats[i].n_miss / stats[i].n_req);
    }
    
    close_reader(reader);
    return 0;
}

```

### Python Bindings for Rapid Prototyping

The `libcachesim` Python package exposes the same parallel backend. The `TraceReader` class wraps `open_trace()`, while `Cache.process_trace()` utilizes the thread pool internally when processing multiple configurations:

```python
from libcachesim import TraceReader, LRU, FIFO

# Open ZSTD-compressed binary trace with 0.5% sampling

reader = TraceReader("cloudPhysicsIO.oracleGeneral.bin.zst",
                     trace_type="oracleGeneral",
                     sampler_params={"sampling_ratio": 0.005})

# Run two algorithms in parallel via the C thread pool

lru = LRU(cache_size=1 << 30)
fifo = FIFO(cache_size=1 << 30)

lru_miss = lru.process_trace(reader)
fifo_miss = fifo.process_trace(reader)

```

### Command-Line Interface

The `cachesim` binary provides direct access to parallel simulation flags:

```bash

# Evaluate LRU across multiple sizes with 12 threads and 10-second warmup

./bin/cachesim trace.vscsi vscsi lru \
    1mb,2mb,4mb,8mb,16mb,32mb,64mb,128mb,256mb,512mb,1gb \
    --num-threads 12 \
    --warmup-sec 10 \
    --num-req 1000000000

```

The `--num-req` flag limits processing to the first N requests for quick validation, while `--num-threads` controls the `GThreadPool` size passed to `simulate_at_multi_sizes()`.

## Summary

- **Memory-mapped I/O** in [`libCacheSim/traceReader/reader.c`](https://github.com/1a1a11a/libcachesim/blob/main/libCacheSim/traceReader/reader.c) uses `mmap()` to provide constant memory access to binary traces of any size.
- **Streaming parsers** with configurable **samplers** allow processing of fractions of billion-request traces without modifying source files.
- **Parallel simulation** via `GThreadPool` in [`libCacheSim/profiler/simulator.c`](https://github.com/1a1a11a/libcachesim/blob/main/libCacheSim/profiler/simulator.c) scales cache size sweeps across CPU cores using cloned readers.
- **ZSTD compression** is handled transparently in the reader pipeline, reducing disk footprint without code changes.
- **Python and CLI interfaces** expose the same C++ parallel backend for both scripting and interactive analysis.

## Frequently Asked Questions

### What trace formats work best for billion-request datasets?

Binary formats (`oracleGeneralBin`, `vscsi`, `lcs`) are optimal because they enable **memory-mapped** access via `mmap()` in [`reader.c`](https://github.com/1a1a11a/libcachesim/blob/main/reader.c), yielding O(1) RAM usage regardless of file size. While CSV traces are supported through streaming `getline()` parsing, they incur higher per-request CPU overhead due to string tokenization.

### How does parallel simulation avoid reading the trace file multiple times from disk?

Each thread created by `simulate_at_multi_sizes()` receives a **cloned reader** that maintains an independent file offset. For binary traces, all clones reference the same memory-mapped region, so the OS pages data once and satisfies all threads from cache. For text traces, each clone opens a separate `FILE*` handle, allowing concurrent streaming without lock contention.

### Can sampling be applied to any trace format?

Yes. The **sampler** logic in `read_one_req()` (lines 11-31 of [`reader.c`](https://github.com/1a1a11a/libcachesim/blob/main/reader.c)) operates after the format-specific parsing stage. Whether the input is binary, CSV, or ZSTD-compressed, the sampler evaluates each request object and either passes it to the cache simulator or discards it before the next read, effectively reducing the sample rate uniformly across the workload.

### What is the memory overhead when processing a billion-request trace?

For binary traces, overhead is effectively constant (megabytes) due to **mmap** demand paging. For text traces, memory scales with the `getline()` buffer size (typically kilobytes) plus any active cache structures. The `--num-threads` flag does not multiply memory usage for binary traces, as all threads share the same mapped pages, making libCacheSim suitable for analyzing billion-request traces on servers with limited RAM.