How Logical Undo Logging and Constant-Time Recovery Transform Modern Databases

Logical Undo Logging Overview

Logical Undo Logging was introduced to address the problems caused by early lock release, where a transaction may need to roll back after its lock has been acquired by another transaction, leading to cascading rollbacks and performance degradation.

The core idea of Logical Undo Logging is to undo the logical effect of an operation during rollback rather than the physical data change; for example, undoing an insert becomes a delete, and undoing an increment becomes a decrement.

Operation Logging extends this concept by recording special logs for transaction operations. When an operation begins, a log entry <T_i, O_j, operation-begin> is written, where O_j is a unique operation ID. Normal physical redo/undo logs are recorded during the operation, and when the operation ends, a log <T_i, O_j, operation-end, U> is written, where U describes the logical undo actions for the whole operation.

Example: inserting a key‑value pair (K5, RID7) into leaf node I9 generates a begin log <T1, O1, operation-begin>, normal physical logs for the update, and an end log <T1, O1, operation-end, (delete I9, K5, RID7)>. During rollback, the system can simply delete K5 and RID7 from the index instead of physically undoing each page modification.

All redo operations remain physical because implementing logical redo is complex and requires ordering decisions.

SQL Server – Constant Time Recovery (CTR)

Most commercial DBMSs, such as SQL Server, use the ARIES recovery algorithm, where undo work is proportional to the amount of work a transaction performed. This can be unacceptable for cloud services that demand high availability.

CTR combines ARIES with multi‑version concurrency control to achieve fixed‑time recovery. By leveraging versioned data, the system can restore the database to a correct state within a deterministic time bound, regardless of the number of uncommitted updates.

MS‑SQL Concurrency Control : Since 2005, SQL Server supports snapshot isolation using a version store that records old tuple versions in an append‑only table. Each record points to its previous version, forming a version chain. Garbage collection removes obsolete versions once they are no longer needed.

CTR extends the version store with a persistent version store, increasing its size and introducing two storage strategies: In‑Row Versioning (small delta values stored with the record) and Off‑Row Versioning (large updates stored in a separate system table).

Silo – Force Recovery

Silo is a high‑performance in‑memory database prototype from Harvard and MIT. It uses optimistic concurrency control, where transactions assume no conflicts and validate only at commit time.

To avoid the bottleneck of a global transaction ID, Silo introduces epochs (40 ms intervals) and group commit. All transactions in an epoch are committed together, eliminating per‑transaction ID allocation. Each transaction is identified by a Sequence Number and an Epoch Number, which together form a 64‑bit transaction ID.

Transaction commit proceeds in three phases:

Acquire locks for all records in the local write‑set using atomic compare‑and‑swap.

Read the current epoch and validate the read‑set; if any record’s TID changed, the transaction aborts.

Generate a new TID (combining sequence and epoch) and finalize the commit.

SiloR, the recovery subsystem of Silo, uses physical logging and checkpoints with parallel recovery. A dedicated log thread manages a pool of log buffers; worker threads request buffers, write logs, and return them. Every 100 epochs a new log file is created, and each log entry records the transaction ID and the set of record updates ( Table, Key, Old Value → New Value).

In‑Memory Checkpoints

In‑memory databases require only redo logging; indexes can be rebuilt from memory after a crash. Checkpoints are classified as:

Consistent Checkpoints : contain only committed transactions.

Fuzzy Checkpoints : may include uncommitted transactions, which are discarded during recovery.

Checkpoint mechanisms include:

Database‑level implementations (e.g., snapshotting via version stores).

OS‑level fork‑based copying of the process memory.

Checkpoint frequency can be time‑based, log‑size‑based, or forced (e.g., during shutdown).

Conclusion

The article surveyed recovery subsystems in modern database systems, covering physical logging with ARIES, logical undo logging, SQL Server’s constant‑time recovery, and Silo’s force recovery. The next installment will explore concurrency control techniques.