Committing a Dataset to an Object Store Without a Rename

The operation that does not exist

Every data layout that lives on a filesystem relies on one operation for atomic publication: rename. A writer assembles a new directory or file under a temporary name, then renames it into place, and the rename is a single directory-entry update that either happened or did not. Readers see the old name or the new one, never a half-populated directory.

Object stores have no rename, as described in the flat keyspace. Copying a directory-shaped prefix is thousands of independent operations, and no prefix of them constitutes a commit. A dataset that occupies many objects must therefore acquire atomicity from something else, and the only atomic primitive available is the replacement of a single key.

The general shape of the answer is a pointer. Data objects are written under keys that no reader consults: generation numbers, random identifiers, timestamps. Their names are recorded in a small object that does not exist until the write set is complete. Readers read the pointer, learn which data objects constitute the current version, and then read those. The commit is the pointer write, which is atomic, and the reader’s first step determines which version it sees for the entire duration of its read.

Two commit protocols that look different and are not

Delta Lake records the log as a sequence of JSON files named by a zero-padded version number, so a commit is the creation of the next numbered file. Because names sort lexicographically, the numbering makes the sequence enumerable: a reader lists the log prefix, sorts the names, and reads the latest. The create-if-absent precondition on the new file is what serialises concurrent committers, since two writers attempting the same version number cannot both succeed.

Iceberg writes a metadata JSON file per commit and then points a small version-hint or catalog entry at the newest metadata file. The metadata file records the current snapshot, and each snapshot records the manifest list, which records the manifests, which record the data files. The chain is deeper because it is designed so that a reader can prune: a query touching one partition reads only the manifests whose partition ranges overlap, rather than every file in the table.

Both protocols commit by writing one object and both make the committed version immutable. The difference is where the version number lives. Delta’s is in the filename, so the log itself is the index and a listing discovers the latest version. Iceberg’s is in a mutable pointer outside the table’s immutable files, so a listing is not required to find the current state and a reader can be handed the pointer by a catalog. The second arrangement is what makes it possible to commit atomically without relying on listing behaviour, and the first is what makes recovery from a lost pointer possible by scanning the log.

Why immutability is the load-bearing property

If a committed metadata file could be rewritten, a reader that read it at time t and the data files it names at time t+1 could observe a state that never existed as a whole. Immutability removes that possibility: the version named in a metadata file is fixed, so a reader that resolves a snapshot once can read every file it names and see a consistent set.

This is why deletion in these formats is not a delete. Removing rows writes new data files containing the surviving rows and a new snapshot that names them, leaving the old files in place for readers still using the previous snapshot. The old files become unreferenced rather than removed, and reclaiming them is a separate, asynchronous concern.

It also fixes what “concurrent write” means. Two writers that both commit succeed at different version numbers if the protocol permits it, and each commit is a new immutable state derived from the version it read. A writer that commits against a stale version either fails the precondition, because the version it intended to write already exists, or produces a state that omits another writer’s changes. Detecting the second case requires a conflict check against the versions committed since the read, which is why these formats carry an isolation level rather than merely a commit protocol.

Garbage collection is the part with no safe default

Unreferenced data files consume storage indefinitely. Removing them requires knowing that no reader can still reach them, and that is a statement about readers, not about the table. Three mechanisms bound the risk.

The first is a retention interval: files older than some age are eligible for deletion, on the assumption that no reader holds a snapshot older than that. The interval is a guess about the slowest reader, and a query that runs longer than it can fail mid-scan when its files disappear. The failure is not silent, since the read fails on a missing object, but it is indistinguishable from corruption unless the reader records which snapshot it resolved.

The second is an explicit snapshot expiry: the table records which snapshots are retained, and files reachable only from expired snapshots are deleted. This is stronger because it is a statement about the table’s history rather than about elapsed time, and it makes the reader’s obligation explicit: hold a reference to the snapshot, and the files stay.

The third is the object store’s own versioning, which turns an accidental deletion of a data file into a recoverable event as long as the version is retained. The state machine, including the delete marker that a plain delete creates, is described in versioning and delete markers. Versioning does not make garbage collection safe; it makes a mistaken garbage collection reversible within the retention window.

A conservative collector has to reconcile a listing against the set of referenced files, and the reconciliation is where the bugs are:

# store.list(prefix) -> [(key, mtime)]
# store.read_all_referenced(table) -> set of keys named by any retained snapshot

def reclaim(store, table_prefix, referenced, min_age_seconds, now):
    """Delete data files under a prefix that no retained snapshot names."""
    candidates = []
    for key, mtime in store.list(table_prefix + "data/"):
        if key in referenced:
            continue
        if now - mtime < min_age_seconds:
            continue                     # possibly written by an in-flight commit
        candidates.append(key)
    # Re-check after listing: a commit may have landed during the scan.
    referenced = referenced | store.read_all_referenced(table_prefix)
    return [k for k in candidates if k not in referenced]

The second check is not redundant. A commit that landed after the listing began can reference a file the listing saw as unreferenced, and deleting it would corrupt a committed snapshot. Any collector that computes the referenced set before listing is exposed to this race, and the window is the duration of the listing.

Small files, and the cost of the pointer

The pointer design assumes data objects are large enough that one commit’s worth of them is a modest number of writes. A streaming writer that commits every few seconds produces thousands of small files, and each file costs a metadata entry, a request to write, and a request to read at query time. Query planning over a table with a million small files spends its time opening files rather than reading data.

Compaction rewrites small files into larger ones and commits a snapshot that swaps them, which is another commit and another set of unreferenced files for the collector. The size to compact toward is bounded below by the point where per-file overhead dominates and above by the memory a single writer can hold, and the practical target is in the hundreds of megabytes per file. The same arithmetic appears in upload sizing, where the multipart floor and ceiling bound how a single object can be assembled, as covered in multipart upload part sizing.

The pointer itself is small and rewritten on every commit, which makes it the one hot key in the design. It is also the key whose loss is unrecoverable if the pointer is the only record of the current version. Storing the pointer in a service with its own durability and its own conditional-write semantics, rather than as an object alongside the data, is the usual mitigation; where it must be an object, replicating it to a second bucket in another region is the minimum. The consistency of that replication, and the window during which the two regions disagree about the current version, is treated in cross-region replication and its consistency window.