Sparse File LRU Cache

Source: Hacker News

Sparse Files Overview

An interesting file‑system feature that I came across a few years ago is sparse files. In short, many file systems allow you to create a logical file with “empty” (fully zeroed) blocks that are not physically backed until they get written to.

The file starts at 0 physical bytes on disk despite being logically 512 MB. After writing some non‑zero bytes at a 16 MB offset, it physically allocates a single block (4 KB). The file system maintains metadata on which blocks of the file are physically represented on disk and which ones are not. To normal readers the sparsity is transparent – it is managed completely by the file system.

Use Case at Amplitude

At Amplitude, all data is stored durably in cold storage (Amazon S3) in a columnar data format used for analytics queries. Fetching data from S3 for every query is inefficient and costly, so the data is cached on local NVMe SSDs (e.g., from the r7gd instance class).

These local SSDs are more than ten times as expensive as cold storage, so a good caching strategy is essential.

Why Columnar Formats Matter

Analytics queries typically touch only a small subset of columns (5–10 out of potentially thousands). Because each column is stored as a contiguous range inside the file, reads are fast. The contiguous ranges also align well with our local caching approach—we are not trying to pick out tiny pieces scattered across the file.

Traditional Caching Approaches

1. Cache entire files – Simple and requires minimal metadata, but wastes a lot of SSD space on columns that are rarely or never used.
2. Cache each column as a separate file – Reduces wasted space but explodes the number of files, increasing file‑system metadata overhead. Small columns are rounded up to the file‑system block size, and with hundreds of thousands of customers the vast majority of files/columns are small (Pareto principle).

Sparse Files as a Middle Ground

Sparse files let us cache entire files while only the logical blocks that contain the needed columns are physically present. This approach:

• Keeps the consumer‑side read logic simple (still a single file).
• Reduces disk usage because unused columns remain unallocated.
• Lowers file‑system metadata overhead.
• Consolidates small columns into shared file‑system blocks, reducing the number of S3 GET requests.

Consumers must declare the columns they need to the cache before reading them.

Managing Sparse File Metadata

We store metadata about which columns are cached in a local RocksDB instance. Specifically, we track logical blocks of the sparse files:

• Which blocks are present locally.
• When each block was last read.

Using this information we approximate an LRU policy to evict data when the SSD fills up.

Block Layout

Logical blocks are variable‑sized:

• A few smaller blocks at the head (still larger than the file‑system block size) to hold the file‑format metadata header (similar to Parquet).
• Larger blocks for the rest of the data.

This layout exploits the fact that the header must always be read to interpret column locations.

Benefits of the Sparse File LRU Cache

• Fewer S3 GETs – Only the needed columns are fetched.
• Reduced file‑system metadata – Fewer individual files and less block allocation overhead.
• Lower block overhead – Small columns share blocks, minimizing wasted space.
• Fewer IOPS – Less frequent cache management operations.

The sparse file LRU cache improved many aspects of the query system simultaneously, demonstrating how a low‑level file‑system feature can have a prominent impact on overall system design.