Transactions on immutable storage

How can a store that only ever writes whole files support a transaction that can be rolled back?

An object store will accept a whole object and give it a name. It will not let you edit ten bytes in the middle of one, and it will certainly not let you replace four objects together in a single indivisible step. There is no lock manager, no write-ahead log, no notion of a transaction anywhere in the interface.

Yet data lakes built on exactly that substrate offer atomic commits, isolated readers, and rollback to last Tuesday. Something has to be giving. Either the storage is doing more than it admits, or the transaction is being constructed out of parts we have not yet noticed.

Ask first what a transaction actually requires. Not durability — the object store already gives us that. We need a set of changes to become visible all at once, and until then, readers to see the previous state cleanly. Two properties: atomicity of the switch, and a stable view for anyone mid-read.

Now ask what the substrate does give us. One thing is genuinely atomic: writing a single object either happens or it does not, and no half-written object is visible to a reader. So we have exactly one atomic operation, on one object at a time.

Can one atomic single-object write produce an atomic multi-file change? It can, if the multi-file change is described by that one object rather than performed by it. Here is the move: separate the data from the statement of what the table is. Data files are immutable and inert — bytes in the store, and nothing about their presence makes them part of the table. Membership is decided by a metadata object listing which files constitute the table right now. Write ten data files and nothing has changed, because nothing points at them. Write one metadata object listing them, switch to it atomically, and all ten arrive together.

Sit with the consequence, because it is the whole design. The expensive work — writing gigabytes — happens entirely outside the transaction, with no lock held and no reader affected. The transaction is the swap of one pointer. Atomicity was never bought by making many writes indivisible; it was bought by making them not count until a single small one said they did.

Where does the pointer live? This is where the object store's limitations bite, and the formats answer differently. Apache Iceberg keeps the current metadata location in a catalog and swaps it by compare-and-swap: change it from the value I read to this new one, and fail if someone moved it first. Delta Lake instead writes an ordered sequence of numbered log files, and a commit is the creation of the next number — atomic provided the store refuses to create an object that already exists. Until object stores offered such conditional writes, deployments needed an external service for that mutual exclusion, a reminder that the primitive relied on here is real and specific.

Now the second property, the stable view. A reader resolves the pointer once and reads exactly the files that metadata object lists. A writer committing mid-read has created new files and a new metadata object, but the reader holds the old one, and nothing it named was modified or deleted. So isolation is free, needing no locks and no coordination: readers cannot be disturbed because there is nothing to disturb.

And rollback? The old metadata object still exists; it still lists a complete, coherent set of files; those files were never touched. So rollback is nothing more than making the pointer name that older object again, and reading the table as of last Tuesday is the same operation with a different target. Neither undoes anything, because nothing was ever done to the old state.

Two writers at once, then? Both stage their files, both attempt the swap, and exactly one wins. The loser has corrupted nothing — its data files are simply unreferenced — so it re-reads the new current state and tries again. This is optimistic concurrency: no locks, conflicts detected at commit, work redone when detection says so. It performs beautifully when writers rarely collide and badly when they constantly do, which is why these formats prefer few large commits over many small ones.

Three refinements.

The first corrects the natural misreading that immutability means the data never changes. It means individual files never change. The table changes constantly, by gaining a new definition of which files it consists of. Updating one row means writing a new file holding the corrected version, plus a metadata object that includes it and excludes the old one. Hence these systems are far better at bulk changes than single-row updates: the unit of rewriting is a file, not a row.

The second: everything else is arranged to keep the swapped object small. Regenerating full metadata per commit would make large tables slow to commit, so the formats layer it — a top object referring to manifests, manifests listing files — and a commit rewrites only the top of that tree.

The third, an honest scope limit: this gives you atomic commits, snapshot isolation and time travel over one table. Committing across several tables at once needs the pointer swaps to be coordinated by something above them, and support for that is uneven across catalogs. It is a genuine limitation, not an oversight.

• How manifest layering keeps commit cost roughly constant as a table grows to millions of files.
• What orphan-file cleanup must prove before deleting anything, given that a reader may still hold an old pointer.

Every term the collection defines is gathered in the glossary.