📚 Database Recovery Deep Dive

Brief Overview
This note covers database recovery and was
created from an 43-page PDF. It gives a thorough
walk‑through of recovery techniques in DBMS,
including logical undo, concurrency concerns, and the
ARIES algorithm, as well as considerations for
main‑memory and NVRAM systems.
Key Points
Overview of logical undo and its role in crash
recovery
How concurrency issues affect logical undo
and mitigation strategies
Detailed breakdown of the ARIES recovery
method and its four key differences from
simpler schemes
Concepts for recovery in main‑memory
databases and NVRAM environments
Summary of recovery terminology, data
structures, and checkpointing strategies
19.8.3 Transaction Rollback with Logical Undo 🚦
Process Overview
The log is scanned backwards to locate
records of transaction Ti.
1. Physical log records are handled as in earlier
recovery, except those that will be skipped
(see step b). Incomplete logical operations are
undone using their physical log records.
2. Completed logical operations are identified
by an operation‑end record :
The operation is rolled back using the
undo information U.
Updates performed during this rollback
are logged like normal updates.
After the rollback, a operation‑abort
record is generated (instead of another
operation‑end).
The backward scan then skips all
subsequent log records of Ti until it finds
the matching , after which normal
processing resumes.
3. If an operation‑abort record is encountered,
the scan skips all preceding records (including
the operation‑end) until the matching is found.
 This prevents multiple rollbacks of a
non‑idempotent logical operation after a
crash during a previous rollback.
4. When the record is reached, the rollback is
complete and a record is appended to the log.
Definition: Logical undo – undo of a logical
operation using the information stored in the
operation’s own log records rather than by
re‑applying physical updates.
Example Log Sequence
Log Record Meaning
Physical update of C
(old = 700, new = 600)
Physical update of C by
T1
Physical update of C by
T0
Update of B by T0
Start of T0
… …
 T0 abort record
T1 commit record
Physical update of B
(old = 2000, new = 2050)
Begin logical operation
O1
Begin logical operation
O2
O1 aborted (skip to its
begin)
O2 completed, adds 200
to C
O1 completed, adds 100
to C
Figure 19.7 – Illustrates how logical undo and
operation‑abort records guide the backward scan.

19.8.4 Concurrency Issues in Logical Undo 🔒

Lower‑level locks obtained during an
operation must also protect the subsequent
 logical undo; otherwise, a concurrent operation
may corrupt the undo.
Example conflict: operation O1 of T1 and
concurrent operation O2 of T2 both
manipulate the same data item. If O1 finishes
while O2 is still in progress and the system
crashes, physical undo of O2 may overwrite
the logical undo of O1.
The problem disappears when O1 holds all
necessary lower‑level locks, preventing O2
from accessing the same items.
Physiological operations (single‑page
logical‑plus‑physical actions) naturally satisfy
the lock requirement.
For more complex operations (e.g., B⁺‑tree
updates), appropriate short‑term locks (e.g., on
the tree root) must be acquired to secure the
logical undo.
19.9 ARIES Recovery Method 🌟
Four Major Differences from the Simplified
Scheme
1. Log Sequence Number (LSN) – uniquely
identifies each log record; stored in pages as
 PageLSN to know which updates have already
been applied.
2. Physiological redo – combines physical page
identification with logical semantics (e.g.,
record deletion with shifting). Results in smaller
log records.
3. Dirty Page Table (DPT) – tracks pages
modified in memory but not yet flushed,
minimizing unnecessary redos.
4. Fuzzy checkpointing – records only dirty‑page
information; dirty pages are flushed
continuously, not during checkpoint creation.
Data Structures 📊
Structure Key Fields Purpose
Log Record LSN, PrevLSN, Sequential
data, (for CLRs) identification;
UndoNextLSN backward
navigation;
undo chaining
PageLSN – Indicates the
LSN of the
latest update
 reflected on the
page
PrevLSN – LSN of previous
log record of
the same
transaction
CLR LSN, PrevLSN, Redo‑only
(Compensation UndoNextLSN, record
Log Record) undo data generated
during rollback;
skips already
undone records
Dirty Page PageID → Lists pages
Table (PageLSN, dirty in the
RecLSN) buffer; RecLSN
marks the
earliest LSN
needed for redo
Checkpoint DPT, list of Persists
Record active recovery state;
transactions + provides
LastLSN starting point
 for analysis
pass
Definition: RecLSN – the LSN of the earliest log
record that might need to be redone for a dirty
page.

19.9.2 ARIES Recovery Algorithm 📈

1. Analysis Pass
Locate the last complete checkpoint and load
its Dirty Page Table.
Compute RedoLSN = minimum RecLSN among
pages in DPT (or checkpoint LSN if DPT
empty).
Scan forward from the checkpoint:
Add new transactions to undo‑list.
Remove transactions that encounter an
end record.
Update DPT entries for pages updated
by log records (add page with RecLSN =
record’s LSN if not present).
Record the last LSN for each transaction in the
undo‑list (used later).
2. Redo Pass
Start scanning from RedoLSN.
For each update log record:
1. Skip if the page is not in DPT or the
record’s LSN < page’s RecLSN.
2. Otherwise, fetch the page; if PageLSN <
record’s LSN, redo the operation.
This ensures only actions not already reflected
on disk are reapplied.
3. Undo Pass
Perform a single backward scan over the log,
processing only transactions in the undo‑list.
For each update record of such a transaction:
Generate a CLR containing the
physiological undo action.
Set UndoNextLSN of the CLR to the
record’s PrevLSN.
When a CLR is encountered, its UndoNextLSN
tells the next record to undo for that
transaction.
Continue until the record is found; then write .
Figure 19.10 – Shows analysis, redo, and undo
actions on an example log (LSNs 7563‑7571).
19.9.3 Additional ARIES Features 🛠️
Nested top actions – operations that must not
be undone (e.g., page allocation). Implemented
via dummy CLRs whose UndoNextLSN skips
the operation’s log records.
Recovery independence – pages can be
recovered independently, allowing transaction
processing on unaffected pages to continue.
Savepoints – allow partial rollback to a named
point within a transaction, useful for deadlock
handling and error recovery.
Fine‑grained locking – supports tuple‑level
locks on indexes, improving concurrency over
page‑level locking.
Recovery optimizations – DPT can be used
for prefetching pages; out‑of‑order redo
permits postponing redo until a page is
fetched, while processing other log records.
19.10 Recovery in Main‑Memory Databases 🖥️
Main‑memory databases keep the active data
in RAM; recovery still requires logging to
stable storage.
 Redo logging may be omitted for index
updates because indices can be rebuilt quickly
after loading the base relations.
Undo logging remains necessary for
transaction aborts; undo records can stay in
volatile memory if the system guarantees they
are flushed before a crash.
Checkpoints are used to bound the amount of
log replay; some systems ensure uncommitted
data are not written to disk.
Parallel recovery – log and data are
partitioned; each core recovers its own
partition, dramatically reducing recovery time.
Non‑Volatile RAM (NVRAM) Note ⚡
NVRAM (or Storage Class Memory) provides
byte‑addressable, persistent storage with
latency comparable to RAM.
Recovery techniques can skip redo logging
because the memory survives power failures;
however, undo logging may still be required
for aborts.
Atomic update mechanisms must be designed
to maintain consistency on NVRAM.
Summary of Recovery Concepts 📚
Failures (disk crash, power loss, software
errors) can corrupt volatile data; stable
storage (mirrored disks, RAID) preserves logs.
Atomicity and durability are enforced by a
log‑based recovery scheme.
Log records contain both old values (for
undo) and new values (for redo); in
deferred‑modification, only new values are
needed.
Checkpoints reduce the amount of log that
must be scanned during recovery.
Modern algorithms (ARIES) use
repeat‑history: redo all actions up to the
crash, then undo incomplete transactions.
Compensation Log Records (CLRs) enable
safe rollback while preserving idempotence.
Dirty Page Table, LSNs, and fuzzy
checkpointing together minimize recovery
time and logging overhead.
Logical undo is required when lower‑level
locks are released early; proper locking
prevents concurrency conflicts during undo.
19.10 Recovery Concepts & Terminology 🌐
Failure Classification
Failure Type Description
Transaction failure A single transaction
aborts (e.g., user
request).
Logical error Incorrect application
logic leads to wrong
results.
System error Software or hardware
malfunction (e.g., OS
crash).
System crash Complete loss of volatile
memory; requires full
recovery.
Data‑transfer failure I/O error while moving
data between storage
levels.
Definition: Fail‑stop assumption – the system
stops executing further operations after a failure is
detected.
Storage Types
Type Characteristics I/O Cost
Volatile RAM; lost on Fast, but not
storage power failure. durable.
Non‑volatile NVRAM, SSDs; Moderate
storage retain data after latency, survives
power loss. crashes.
Stable storage Mirrored disks, Higher latency,
RAID; used for guarantees
log persistence. durability.
Blocks & Buffers
Entity Purpose
Physical block Unit read/written to
disk.
Buffer block In‑memory copy of a
physical block; resides in
the buffer pool.
Disk buffer Intermediate cache
managed by the
OS/device.
 Definition: Force‑output – the operation that
forces a buffer’s contents to be written to stable
storage.
Log‑Based Recovery Essentials
Log – sequential record of all updates; stored
on stable storage.
Log record – contains enough information to
undo (old value) and redo (new value) an
update.
Update log record – captures a single
data‑item modification.
Deferred modification – updates are applied
to the database only at commit; log stores only
new values.
Immediate modification – updates are
applied as they occur; log stores both old and
new values.
Uncommitted modifications – changes made
by a transaction that has not yet committed;
must be undone on abort.
Checkpoint – a saved state of the system
(DPT, active transactions) that bounds the
 portion of the log to be scanned during
recovery.
Restart recovery – the three‑phase process
(analysis, redo, undo) that restores the
database after a crash.
Physical undo – uses old values from log
records to revert updates.
Logical undo – reverts a logical operation
using its own undo information (as described in
earlier sections).
Write‑Ahead Logging (WAL) & Log Force
WAL rule – before a dirty page is written to
disk, its log record must be flushed to stable
storage.
Log force – explicitly forces the log buffer to
be written out (e.g., at transaction commit or
checkpoint).
Buffer Management & Latches
Component Role
Buffer pool Holds in‑memory copies
of disk pages for
read/write.
 Log‑record buffering Temporarily stores log
records before they are
forced to stable storage.
Latches Short‑duration locks
(often implemented with
atomic instructions) that
protect in‑memory
structures during
updates.
Definition: Latch – a lightweight lock used to
ensure mutual exclusion while accessing shared
data structures in memory.
High Availability & Remote Backup
Primary site – the main operational location
where transactions are processed.
Remote backup site – a secondary location
that receives periodic dumps of the database
(e.g., nightly archival dump) to protect against
loss of non‑volatile storage.
Secondary site – may serve read‑only queries
while the primary site recovers.
20 Database‑System Architectures 🏗️
20.1 Overview
Database architecture is shaped by the underlying
hardware (processor, memory, network) and by the
need for parallelism and distribution. Early systems
ran on a single machine; modern designs span many
nodes to support web‑scale workloads.
20.2 Centralized Database Systems
Single‑user systems – run on personal devices
(phones, laptops). Typically a single processor
(or few cores) and one/two disks. Concurrency
control is simple; recovery may be minimal.
Multi‑user server systems – multiple CPUs,
large memory, many disks. Serve thousands of
concurrent users. Provide full transactional
features (SQL, concurrency control, crash
recovery).
Definition: Embedded database – a database
linked to a single application, often lacking full SQL
support and providing only a simple API.
20.3 Server System Architectures 🔧
Server systems fall into two major categories:
Category Description
Transaction‑server Clients submit complete
transactions; the server
executes them and
returns results.
Data‑server Clients read/write
lower‑level data units
(files, pages, objects).
Provides indexing and
transaction support for
these units.
20.3.1 Transaction‑Server Architecture
A typical transaction‑server comprises several
cooperating processes that share a common memory
region:
The image shows a calm sea with sailboats,
symbolizing the orderly coordination of multiple
processes in a server environment.
Server processes – receive, execute, and
return query results. May be one process per
session or a multithreaded process handling
many sessions.
Lock manager process – grants, releases, and
deadlock‑detects locks.
Database writer process(es) – continuously
flush dirty buffers to disk.
Log writer process – forces log records from
the log buffer to stable storage.
Checkpoint process – periodically creates
fuzzy checkpoints (writes DPT and
 active‑transaction info).
Process monitor – detects failed processes
and initiates abort/restart actions.
All processes access shared structures stored in
shared memory, such as:
Shared Structure Purpose
Buffer pool Holds cached
pages/blocks.
Lock table Tracks granted locks.
Log buffer Holds pending log
records before force.
Query‑plan cache Reuses compiled query
plans.
Mutual exclusion for these structures is achieved with
semaphores or atomic instructions (see Note 20.1).
20.3.2 Atomic Instructions for Mutual Exclusion
Two widely supported hardware primitives:
1. Test‑and‑set (M) – atomically reads a memory
location M and sets it to 1.
 Returns the original value; a return of 0
means the lock was acquired.
2. Compare‑and‑swap (M, V₀, Vₙ) – atomically
compares M with V₀; if equal, replaces it with
Vₙ and reports success.
These primitives are used to implement latches,
which protect short‑duration critical sections (e.g.,
updating the lock table). While they provide
exclusive locking, they do not directly support shared
locks; higher‑level lock managers build on them.
Definition: Latch – a short‑lived lock implemented
with atomic instructions to ensure safe concurrent
access to in‑memory data structures.

20.4 Summary of Core Concepts (Link to Earlier

Sections)
ARIES (Advanced
Recovery Information System — see §19.9)
employs LSNs, physiological redo, CLRs, and a
Dirty Page Table to achieve efficient recovery.
Logical undo (discussed in §19.8.3) requires
retaining higher‑level locks so that concurrent
 transactions cannot invalidate the undo
information.
Checkpointing (both fuzzy and full) bounds
the amount of log that must be scanned;
frequent checkpoints reduce crash‑recovery
time but increase normal‑operation overhead.
Write‑Ahead Logging guarantees that the log
is persisted before any dirty page reaches
stable storage, preserving atomicity and
durability.
These principles together enable modern database
systems—whether centralized, parallel, or distributed
—to provide high availability, concurrency, and
robust recovery.
20.3.1 Lock‑Table Concurrency in
Transaction‑Server Architectures 🔐
Mutual‑Exclusion Protocol
1. Acquire a mutex (latch) on the lock table using
test‑and‑set or compare‑and‑swap on a
dedicated memory location.
2. Check whether the requested lock can be
granted (see § 18.1.4).
 If grantable → update the lock table to
reflect allocation.
If not → queue the request in the
lock‑table entry.
3. Release the mutex.

Lock Release Procedure

1. Acquire the mutex on the lock table.
2. Remove the entry for the released lock.
3. Examine the queue; allocate pending requests
that now satisfy the lock‑granting rules
(§ 18.1.4) and update the table accordingly.
4. Release the mutex.

Busy‑Waiting Avoidance
Transactions that cannot obtain a lock
immediately may periodically poll the lock
table (busy waiting).
A more efficient alternative uses
operating‑system semaphores:
Lock‑request code waits on a
semaphore until a grant notification is
received.
Lock‑release code signals the
semaphore to wake waiting transactions.
 Definition: Latch – a short‑lived lock implemented
with atomic instructions (test‑and‑set or
compare‑and‑swap) to protect shared in‑memory
structures such as the lock table.
Even with shared‑memory lock handling, a
dedicated lock‑manager process performs
deadlock detection.
20.3.2 Data Servers and Data‑Storage Systems 📦
Purpose and Evolution
Originated for object‑oriented databases
where clients manipulate persistent objects
(e.g., CAD models).
Computation‑intensive tasks are performed on
client machines, while the data server only
stores and retrieves data items.
Data Item Model
Term Description
Data item Tuple, object
(JSON/XML), file, or
document.
 Data server System that stores and
communicates whole
data items (or parts
thereof).
Modern systems expose APIs (rather than
SQL) for store / retrieve / update operations
on data items.
For very large items, servers may allow partial
transfer (e.g., specific blocks) instead of
moving the whole item.
Historical Note
Earlier generations used page shipping
(communication unit = database page
containing multiple items).
Today, the underlying storage layout is hidden
from clients; page shipping is obsolete.
20.3.3 Caching at Clients 🚀
Why Cache?
Network latency (≈ 1 ms) dwarfs local
memory access (< 100 ns).
 Reducing round‑trip messages is critical for
both client‑server and parallel‑database
workloads.
Optimization Strategies
Strategy Mechanism Typical Benefit
Prefetching When an item is Hides latency
requested, also for subsequent
send items accesses.
likely needed
soon.
Data caching Keep received Eliminates
items in a repeated
client‑side fetches; must
cache verify freshness.
(transaction‑scoped
or longer).
Lock caching Store acquired Allows
locks locally lock‑protected
when usage is operations
partitioned without
among clients. contacting the
server; requires
 server‑side
tracking and
possible
callbacks.
Adaptive lock Switch between Reduces
granularity fine‑grained number of lock
(item) and requests; may
coarse‑grained involve lock
(page) locks de‑escalation
based on (coarse → fine).
contention.
Cache Coherency
Clients must validate cached data (e.g., via a
server check) before use, unless stale data are
acceptable.
New inserts that were not present during
caching also require a server round‑trip.
Lock De‑escalation Workflow
1. Server requests the client to downgrade a
coarse lock.
2. Client acquires finer‑grained locks for needed
items and releases the coarse lock.
 3. Items without current locks may be evicted
from the cache instead of re‑locking.
20.4 Parallel Systems 🌐
Core Idea
Parallelism exploits multiple
processors/computers to accelerate I/O and
computation.
Two categories:
Coarse‑grain – few powerful CPUs
(each with many cores).
Massively parallel (fine‑grain) –
thousands of modest nodes, each with
private memory and disks.
Architecture Elements
Element Role
Node Independent machine
with its own CPU,
memory, and storage.
Data center Facility housing many
nodes; provides
 high‑speed internal
networking.
Inter‑node network Connects nodes; crucial
for data movement and
coordination.
Motivation for Parallel Databases 📈
Web‑scale applications generate petabytes
of data and thousands of transactions per
second.
Single‑node systems cannot meet the required
throughput or response time.
Parallel query processing leverages the
set‑oriented nature of SQL operations.
Performance Measures
1. Throughput – number of tasks completed per
unit time.
2. Response time – duration from task
submission to completion.
Speedup & Scaleup
Speedup = T /T (time on small system ÷
S ​

L ​

time on larger system).

 Linear speedup: speedup = N when
resources increase N ‑fold.
Sublinear speedup: speedup < N .
Superlinear speedup (rare) occurs when
larger resources allow data to fit in
memory or cache, eliminating disk I/O.
Scaleup evaluates handling of larger tasks
with proportionally more resources.
Batch scaleup: database size grows;
tasks (e.g., full table scans) scale with
data volume.
Transaction scaleup: transaction rate
and database size grow together; each
transaction remains short, making
parallel execution natural.
Definition: Speedup – the factor by which
execution time is reduced when increasing parallel
resources.
Definition: Scaleup – the ability of a system to
maintain performance when both problem size and
resources are increased proportionally.
Types of Scaleup
 Type Scenario
Batch scaleup Large analytical jobs
(e.g., scans) on
ever‑growing databases;
also used in scientific
simulations with finer
resolution.
Transaction scaleup High‑rate transaction
processing (e.g.,
banking) where the
number of accounts and
transaction volume rise
together.
In practice, transaction scaleup is often the
more critical metric for parallel database
systems, as it reflects the system’s ability to
keep up with growing user demand while
preserving low response times.