tl;dr

Corollary to compaction maps. No code, yet.

Old snapshots in table formats are immutable, referencing the same objects they were derived from until they’re deleted. However, given a compaction map, we can peel back versions to invert delta commits between compactions. By rewriting snapshots to reference later compactions, we can reclaim storage by garbage-collecting the old layouts they pin, and improve cache efficacy by leaving fewer distinct objects to cache, without changing the versions we can address.

Compaction maps tl;dr

A compaction rewrites a table’s data files into a more efficient layout without changing what the table contains. Compactions are logical noops; they only conflict with concurrent transactions because they change the layout of the data. Transactions need to know where their input rows were moved in the new layout to repair the layout conflict.

A compaction map effects that translation. For each run of rows the compaction relocated, it records the source file and offset, the target file and offset, and the length. Repairing a conflict is then arithmetic over the position delete vectors- tgt_start + (pos - src_start)- instead of re-execution. The previous post uses this to make compactions commute with concurrent transactions.

Rewriting Snapshots

Compaction maps rebase transactions that commit concurrently with a compaction, but the same translation works in reverse: rewriting snapshots that already committed so they refer to the subsequent compaction, rather than the layout of the snapshot they were prepared against.

A typical history is on the top of the figure. When \(C_B\) compacts the state and commits, the compacted objects are unaddressable by future delta updates: \(T_\alpha\) and \(T_\beta\) can be read, but not referenced by subsequent transactions.

This creates a new possibility: rewriting these old snapshots to refer to the new layout. The snapshot written by \(T_\beta\) is redundant as soon as \(C_B\) commits, but more interesting is its inverse, which we can use to derive its predecessor \(T_\alpha\). The compaction map rewrites \(T_\beta\)’s inserts to position delete vectors in \(T_\beta^{-1}\) against \(C_B\). The position delete vector for \(T_\beta\) looks up what it deleted to create inserts for \(T_\beta^{-1}\). This creates the state of \(T_\beta\)’s predecessor \(T_\alpha\), but against \(C_B\) instead of \(C_A\).

However, the compaction map alone is not sufficient to rewrite \(T_\alpha\)’s inserts. \(T_\beta\) deleted d, one of \(T_\alpha\)’s inserts, so d doesn’t survive into \(C_B\) and the compaction map has no information to recover it. But recall that to generate \(T_\beta^{-1}\), the rewrite had to resolve the rows that \(T_\beta\) deleted, including d. It must know the position of d in \(T_\beta^{-1}\) and the object/transaction that needs the reference (\(T_\beta^{-1}:2\) in the figure, for \(T_\alpha^{-1}\)). The insert of c in \(T_\alpha^{-1}\) is recovered from \(C_A\) by resolving the position delete.

Rolling backward, either inserted rows survived to \(C_B\) and they’re in the compaction map, or they were deleted by a transaction that committed between compactions, in which case they were recovered during the rewrite of that transaction’s inverse.

When this reaches \(C_A\), we can reclaim not only the snapshots made redundant by the compactions, but also old compactions without losing snapshot states.

OK. Why?

Beyond reclaiming old compactions, two immediate benefits come to mind. First, if a snapshot is insert-only and all its data survives, then this process can compress that snapshot to a position delete vector using only the compaction map. Even if only most data survives, this reduces the space required to store the interstitial snapshots and improves the efficacy of caching the target snapshot. Second, GDPR and other “right to be forgotten” regulations require that data be deleted from a table, but it remains available in older, immutable snapshots. As part of the rewrite, purged data can be removed from the transactions that inserted it.

If the layout conflicts introduced by compactions are trivially repaired, then extending the compaction’s runtime by including these rewrites imposes few costs on workloads. Old layouts can’t be immediately reclaimed without causing running transactions to fail, but GC is already asynchronous and separate from compaction. The cases where a rewrite of a particular snapshot is less efficient (or difficult) can leave the old layout undisturbed.

Breaking Changes

Rewrites preserve the sequence of states, but many services downstream of table formats- replication, change data capture (CDC), audit- depend on the original layout because the encoding captures its provenance: data dependencies that reconstruct the table following the same sequence of incremental changes. Returning to the running example, the snapshot written by \(T_\alpha\) was not derived from its successor \(C_B\), but that’s what the new layout describes¹. While recoverable, the rewrite scrambles exactly what the original layout captured: change logs.

The value of table provenance usually decays quickly. Transactions don’t validate against historical snapshots (and only care that some transaction conflicted), async audit/replication consumes changes in minutes, and historical audits can afford to reconstruct the original layout. Still, practical implementations would probably need to avoid rewriting recent snapshots so these services have a chance to run before the layout is rewritten.

Conclusion

Compaction maps were a narrow solution to a specific problem, but tracking layout lineage in table formats seems to enable a broader set of repairs and optimizations. A real implementation would also grapple with schema changes, partitioning, equality deletes, etc. I’d love to hear why this doesn’t work. Email me.