S3 Cache Built From Holes Speeds Up Berserk Queries

Diagram of an S3 cache built from sparse files with punched holes

Berserk, a database for observability data such as logs, metrics, traces and evals, has built an S3 cache that is deliberately full of holes. The engineers use sparse files and punch out space as cached pieces fall out of use, which keeps queries fast and disk usage low.

The design, and the race condition it creates, shows how much careful coordination a plain Linux S3 cache needs.

What a sparse file is

A sparse file looks large but occupies little disk space. Parts of it are simply never allocated, and reading them returns zeros. You create one by opening a file, seeking to any position and writing. The file system tracks the allocated blocks, typically 4 KB each, and the gaps between them are the holes.

The trick is old. Unix tools such as GNU tar added a sparse-file option in the early 1990s so that backups wouldn’t write gaps out as zeros. Early files used the idea too: a login record file could place each user’s entry at a position computed from the numeric user ID, leaving unused slots as holes.

Linux now has direct tools. Calls to lseek with SEEK_DATA and SEEK_HOLE locate data and holes, and fallocate with FALLOC_FL_PUNCH_HOLE releases disk space inside a file while leaving its length alone. POSIX standardized finding holes in 2024, while creating them still depends on platform-specific APIs.

How the cache server works

When a query needs data from S3, Berserk’s coordinator splits the work among workers. Each query node runs one cache server, and its workers share the cache kept on that machine’s disk. A worker pulls cached data directly off disk and, for anything absent, requests a download from the local server.

Berserk stores batches of rows on S3 as segments, files that hold rows plus indexes and can grow to several gigabytes. The cache server fetches missing data with range requests aligned to 4 MiB blocks, and one request can cover several adjacent blocks. Each cached S3 object becomes a local sparse file, with every block written at the same offset it had in the original segment.

Workers talk to the server over Unix domain sockets, which can pass shared memory handles between processes. Among the shared memory is a bitmap that marks, for each 4 MiB block, whether it is cached. Before a direct read, the worker checks the bitmap. If the blocks are present, it reads the file. If not, it asks the server to download the range and tries again.

It works much like the operating system’s page cache, except the host-local cache server tracks what sits on local SSD. This leaves much of the bookkeeping to the operating system, and everything runs on a standard Linux file system.

Evicting data without serving zeros

The trouble starts when the cache fills. The server prefers to evict blocks used less recently or less often. First it resets their flags in the shared bitmap, then it calls fallocate to punch holes and return the space.

Checking the bitmap and reading the file are two steps, and the server is a different process. A client might see a block flagged as cached, the server might evict it in that gap, and the client would end up reading zeros where the data used to be. Updating the bitmap afterward can’t undo the earlier check.

Berserk’s fix is a shared counter. The server bumps it for a file just ahead of any hole punch. Before reading, the client confirms every block it needs is flagged and no write is queued. It records the counter value, reads, and records it again, using memory fences around the read. A different value means a punch was announced during the read. In that case the client attempts to validate the data while holding a lock over the range, and falls back to asking the cache server if that fails.

Reusing the disk contents after a restart

Blocks left on disk can be reused once the service restarts, as long as the cache can prove the bytes are unchanged. It stores a checksum per 4 MiB block. The first design had the server read and verify a whole block when a query first hit it post-restart, even for a handful of bytes. Queries slowed down while the cache rechecked data it already held.

The team dropped that step because segment files already carry a checksum per chunk. A chunk can sit inside one block or span several. The query worker verifies each chunk it reads, and if a check fails, it asks the cache server to refetch the affected blocks from S3.

Balancing downloads and eviction

When blocks are missing, the cache keeps several S3 requests in flight and reads ahead when it expects the next blocks to be needed. How many requests to run at once depends on the object store’s latency and bandwidth. The cache tunes this itself and slows down if the store begins throttling. Downloads also need disk space, so under sustained load eviction has to free it fast enough to keep them moving.

Releasing disk space is simple. Stopping a query from consuming data out of a block that has just vanished is where the difficulty lies.

What this means for engineers building caches

Berserk’s cache punches holes to evict single blocks while preserving original S3 offsets. Workers read cached blocks directly using the shared bitmap and detect a hole punch mid-read through the eviction counter. After restarts, the segment format’s own checksums let workers verify only the chunks they read.

The same file serves local reads, fills missing ranges from S3 and hands disk space back as queries move on. Teams building their own S3 cache on Linux can borrow the pattern, but they will need the same discipline around cross-process checks.

Source: Berserk

Written by

Saksham Bhargava

Saksham Bhargava runs Alteroid and has been writing about consumer technology for over five years, covering iPhone, Android, Windows, AI tools and gaming. With an MCA and six years of hands-on web development experience, he tests the features he writes about on his own devices and focuses on clear, practical guides that solve real problems. Away from the screen, he enjoys travelling to places most tourists skip.