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

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, 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.

// 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 (lines 11-31), the read_one_req() function wraps the read operation in a sampling loop:

// 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 (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.

// 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:

#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:

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:

# 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 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 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, 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) 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.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}