Everything is a Transaction: Unifying Logical Concurrency Control and Physical Data Structure Maintenance in Database Management Systems

This paper from CIDR'21 introduces the Deferred Action Framework (DAF). This framework aims to unify transaction control and data structure maintenance under multi-version concurrency control (MVCC) database systems, particularly for complex maintenance tasks like garbage collection and index cleanup.

In MVCC systems, transactions and data maintenance tasks (like garbage collection) often interfere, requiring complex coordination. This can lead to issues in system performance and code maintainability, as physical structures (e.g., B+ trees) aren't inherently designed to handle multi-versioning.

The paper proposes DAF to handle deferred actions—maintenance tasks that are queued to execute only when they no longer interfere with active transactions. DAF relies on timestamp-based ordering and executes tasks only when their actions won’t affect concurrent transactions. DAF guarantees to process actions deferred at some timestamp t only after all transactions started before t have exited. This provides *epoch protection* to transactions and maintenance tasks, without requiring a separate mechanism for refreshing and advancing epochs. Using a global epoch counter might have been simpler, but it would disallow the complex, multi-deferral-based ordering of actions needed for DAF’s broader applications like schema changes and index maintenance.

DAF is implemented in NoisePage (notice Pavlo's patented database naming scheme in action). The implementation chains deferrals to handle dependencies (e.g., an index cleanup must happen before a table deletion). DAF uses a single-action queue with timestamp tags, and processes tasks sequentially ensuring no conflicts arise. DAF supports multi-threaded processing, with both cooperative and dedicated action processing threads for high concurrency.

As Figure 1 shows, DAF uses a single action queue with a dedicated execution thread. DAF's transaction management process follows a specific sequence. First, a transaction worker gets an "observable" timestamp by incrementing the global counter. It then tags its deferred actions with this timestamp and adds them to the queue. When the transaction begins, the worker increments the global counter again. The action thread processes queue items by comparing queue item timestamps against the oldest active transaction timestamp. It executes items when their timestamp is smaller or when no active transactions exist, blocks when this condition isn't met, and waits when the queue is empty.

For complex operations like table deletion under snapshot isolation, DAF uses chained deferrals. For example, when transaction T1 drops a table, it defers action T1-A1, which when executed defers the actual deletion T1-A2. This ensures T1-A2 executes after all concurrent operations (like T2's inserts) complete. This approach solves ordering issues in concurrent scenarios while maintaining memory safety.

Experiments show DAF’s performance is on par with or exceeds specialized implementations, particularly in high-throughput scenarios like TPC-C benchmarks.

Beyond garbage collection, DAF can support latch-free block transformations and non-blocking schema changes. While simple schema changes (like renaming tables) can proceed without blocking transactions, complex changes that require table rewrites typically block all queries. Supporting true non-blocking schema changes requires managing multiple concurrent schema versions, which complicates transaction visibility and query planning due to the need for multiple plan cache entries.