Chapter 5: Transaction Processing and Recovery

Welcome to Last Minute Lecture.

This free chapter overview is designed to help students review and understand key concepts.

These summaries supplement not replaced the original textbook and may not be redistributed or resold.

For complete coverage, always consult the official text.

Welcome back to the Deep Dive.

We've spent our previous dives really building the physical foundation of our data prep systems.

You know, the files, the pages, how data actually lands on the lowest level.

Exactly.

But today we are making a massive shift.

We're moving up from those raw storage structures to the high level components that truly make a database reliable, trustworthy, and actually capable of handling complex work.

That's a great way to put it.

If the storage layer is the physical foundation, today we're building the operational headquarters.

We're moving into this realm of complex coordination where transactions, the fundamental units of work are managed, tracked,

and most importantly, guaranteed.

Guaranteed.

Yeah.

Without the systems we're covering today, things like buffer management, sophisticated recovery logs, and concurrency control, modern high -throughput database operations just,

they simply wouldn't be possible.

So our mission today for you is to demystify this incredible complexity that's hiding behind just a single database operation.

I mean, when thousands of users are hitting the database simultaneously, how does the system make sure those concurrent operations appear perfectly sequential and isolated?

And crucially, how does it guarantee persistence even if someone literally yanks the power cord out mid -write?

Right.

We're focusing on the local components, the managers and caches that govern this fundamental contract, all modern databases promise.

And that contract is universally known as ACID.

Atomicity, Consistency, Isolation, and Durability.

This is the bedrock of database trust and is what defines a transaction, an indivisible logical unit of work, even if it's made up of multiple steps like a read followed by three writes.

Okay.

So let's unpack that contract, starting with the guarantee that feels the most, I guess, definitive.

The A, atomicity.

Atomicity is the all -or -nothing principle.

It's completely rigid.

A transaction, no matter how complex, must either succeed completely, and that's what we call a commit, or none of its effects are applied at all.

That's an abort or a rollback.

So there's no partial success.

None.

Zero.

If you start a transaction, the transfer money from account A to account B, and the debit from A works, but the system crashes or hits an error before the credit to B, the system must automatically roll back that debit.

It has to restore the original state of account A.

It's binary,

full application, or total erasure.

Okay.

That's clear.

Next to C, consistency.

Now, this is the one that always requires a second look.

The source material even notes this is the most weakly defined property, and it's the only one that is actually user -controlled or application -controlled.

So if a database is supposed to enforce integrity, why is consistency kind of outsourced?

That is a fantastic question that gets right to the heart of what a database system can and cannot guarantee.

You see, consistency means the transaction moves the database from one valid state to another valid state.

The database itself, it enforces constraints like unique keys or foreign key relationships.

Those are technical invariants.

Right.

The hard rules.

Borders rules.

But if you, the user or the application designer, have a business rule, let's say the inventory count must never go below zero or the sum of all balances must equal the system's total, the database can't read your mind.

It relies completely on the logic within your transaction to make sure that when it starts, all your defined invariants hold true, and when it ends, they still hold true.

I see.

So the database is providing the scaffolding.

It ensures atomicity, isolation, and durability, but it basically trusts your code to uphold the business logic of consistency.

Precisely.

It gives you a safe environment to execute your logic, but the logic itself is on you.

That brings us to what feels like the most complex and, frankly, contested property.

I for isolation.

The ideal definition sounds perfect.

Concurrent transactions run without interfering with one another, as if they were executed one after the other.

The ideal theoretical isolation is called serializability.

But here's the reality check.

Enforcing perfect serializability for every single operation, every single time, is often just prohibitively expensive.

It can destroy your performance and throughput.

So we compromise.

We do.

And that's why we have to talk about isolation levels.

These are basically deliberate weakenings of the isolation guarantee to improve speed.

We'll dive into the specific anomalies that weaker levels permit later.

But for now, just remember that isolation is all about controlling when and what changes become visible to other simultaneous transactions.

And finally, the foundational guarantee that lets us all sleep at night.

D's for durability.

Durability is the simple promise.

Once the database tells you a transaction has committed, those modifications must be safe on persistent storage.

Usually disk or non -volatile memory.

They have to survive any physical failure.

A crash, a reboot, a power outage.

So when the system comes back online, that committed data is guaranteed to be there.

This property is enforced by this beautiful coordination between the page cache and the write -ahead log, which we'll get into in detail.

And that right there is the entire non -negotiable transactional contract.

So if ACID is the contract, we need to meet the internal team.

The four local components that are operating inside a single database node, enforcing these rules in real time.

You could think of them as the command crew of the system.

I like that.

They're constantly communicating and coordinating access to data pages.

Okay.

First up, the captain of the ship, the transaction manager.

This is the orchestrator.

It manages the entire life cycle of a transaction.

It assigns it an ID.

It tracks its current state.

Is it running, committing a boarding?

And ultimately it coordinates the lock manager and the log manager to make sure that the

rollback succeeds atomically.

Right.

Then second, we have the gatekeeper,

the lock manager.

The lock manager guards access to data resources.

Before any transaction can read or write a piece of data, it has to ask the lock manager for permission.

This manager keeps track of which resources are currently held and in what mode.

It could be a shared mode where multiple readers are allowed or an exclusive mode where there's only one writer allowed and is blocking everyone else.

This control is absolutely essential for isolation.

Got it.

Third, the system's working memory,

the page cache, or as some call it, the buffer pool.

This is the high speed intermediary.

It's where data pages live temporarily sitting between the really slow disk and the ultra fast CPU.

It's essentially a staging area for any data that needs to be read or modified.

And fourth, the memory keeper,

the log manager.

This component is responsible for holding the history of operations.

It writes these things log entries that detail every single change made to a page in the cache.

The log manager is the key to both atomicity for doing rollbacks and durability for crash recovery.

Okay.

Let's dive straight into that engine room and focus entirely on buffer management and that critical component, the page cache.

The whole reason we even need a page cache is because of the memory hierarchy, this vast performance gap between persistent storage like a disk and main memory or RAM.

Oh, the gap is astronomical.

I mean, disk latency can be measured in milliseconds while RAM access is in nanoseconds.

It's a difference of several orders of magnitude.

The page cache exists purely to cache pages read from disk into RAM to minimize those incredibly expensive IO operations.

Ideally, when the storage engine requests a page, it should always be returned instantly from the cache.

I noticed the sources we're using consistently use the term page cache over the more traditional buffer pool.

Is that just semantics or does it imply a specific function?

It's a bit more than just semantics.

It really emphasizes the function.

While buffer pool kind of implies you're just allocating memory slots buffers, the term page cache highlights that its primary role is to cache the contents of pages read from disk, which allows for reuse.

It's acting as this transparent layer, often thought of as a virtual extension of the disk, but operating at RAM speed.

Okay.

So let's get the vocabulary for that cache management down.

If a page isn't in RAM, loading it is called paging in.

Correct.

And once it's in memory and a transaction modifies it, we flip a switch and label it a dirty page.

This flag is hugely important because it means the version of the page in RAM is now the authoritative source of truth, and it's now inconsistent with the old persistent copy on disk.

And those changes must be synchronized eventually.

Exactly.

Durability demands it.

And inevitably RAM fills up.

So when the cache hits capacity and it needs to make room for a new page, that process is eviction.

And this decision, what to sacrifice, that's where the real complexity begins.

It is the buffer manager's hardest job.

Because if you make the wrong choice, you can cause a massive dip in performance.

The system starts churning, just repeatedly loading and evicting necessary pages.

It's called thrashing.

So figure five one in the text gives us a great illustration of this.

It shows a B -tree structure and it's logically mapping to these page cache slots, which then in turn map to physical pages on the disk.

What should we be taking away from that visual relationship?

The key takeaway is the detachment.

The logical B -tree structure is nice and orderly, but the physical reality,

how those pages are actually stored on disk,

might be completely scattered.

The page cache abstracts all of that away.

The buffer pool slots, they just hold the base purely on the cache's management rules, not the logical structure of the B -tree or the physical layout of the disk.

So it decouples the application's view of the data from the underlying I -O mechanisms.

Properly said.

Okay.

Based on that, we can summarize the page cache's primary functions as first, caching the page contents.

Second, buffering modifications with that dirty flag.

Third, handling those page and requests when it has to.

And fourth, performing intelligent eviction and flushing when it runs out of space.

And that control over I -O is so crucial.

The database is actively trying to decide when the right operation physically happens, rather than just letting the operating system decide on its own schedule.

Which of course leads us to the infamous kernel page cache debate.

Why do these highly -tuned, high -performance database systems so often try to bypass the operating system's built -in page cache?

They use flags like Odirect.

They want absolute, total control over the memory hierarchy.

The kernel's page cache is a generalist.

It's designed to work well for everything from video files to executable code.

A database, though, has this highly specialized knowledge.

What kind of knowledge?

It knows exactly which pages are the B -tree root, which are needed constantly.

It knows which pages are part of a massive, one -time sequential scan, which will only be needed once.

And it knows which pages are already protected by the write -ahead log.

By using Odirect, the database takes over buffer management and avoids this redundancy and potential conflict of having the data cached in two different places, in the kernel's cache and in its own page cache.

But the sources did note that kernel developers, people like Linus Torvalds, have historically been pretty critical of the way Odirect is used.

What was the central complaint there?

The complaint was that Odirect, as it was implemented, often wasn't truly asynchronous.

And it didn't offer good mechanisms for dividing hints to the kernel about access patterns, like prefetching data.

It was a bit of a blunt instrument.

And while we can use other tools like Fidvise to influence the kernel's eviction policy, that's just a hint.

It's not a guarantee.

And databases need guarantees.

Databases absolutely require guarantees for durability, which is why owning the cache management, despite the criticism, remains a standard practice for so many high -performance systems.

Let's talk about the internal controls the database uses then.

How does it manage the pages it owns?

You mentioned a page being referenced.

Right.

Reference just means the storage engine is actively using the data buffer, maybe reading from it or modifying it.

The engine has to signal when it's done by dereferencing it.

But even stronger than a reference is pinning.

Pinning literally locks a page in the cache.

It makes it immune to eviction, even if the buffer manager is desperate for space.

And when is pinning most critical?

Think of the highest levels of a B -tree.

The root page is accessed on virtually every single lookup.

If that root page were ever evicted, the system would immediately have to pay a massive IO cost to page it back in.

So pinning those high -level critical pages ensures they never leave RAM, guaranteeing maximum IO efficiency for lookups.

Okay.

And we already established the dirty flag as the signal for synchronization needed for durability.

This brings us right back to that inherent conflict.

Cache eviction and durability trade -offs.

This is the eternal struggle.

It truly is.

We need to evict pages to make space.

But if a page is dirty, we absolutely must flush it to disk first.

Flushing means IO, which means latency.

We have to coordinate the flushing of those dirty pages with the checkpoint process and the write -ahead log.

Explain that crucial coordination point.

What's that link?

Okay.

So the checkpoint process is what links the cache and the log.

The database cannot safely discard log records from the wall until it is certain that all the changes described by those records, the changes in the corresponding dirty pages have been safely flushed to persistent disk.

If you evict a dirty page without logging its changes, you've broken the durability promise.

If you truncate the log before the dirty page is flushed, you can't recover from a crash.

It's an incredibly tight coupling.

So the buffer manager is constantly balancing performance against safety.

What are the competing trade -offs it's juggling?

Well, there are a few.

One,

you can delay flushes as long as possible to reduce IO, which helps performance.

Two, you can preemptively flush dirty pages in the background, like PostgreSQL's separate flush writer does, just so they can be evicted quickly later on.

That's a preparedness strategy.

And three, you have to choose the optimal sequence for eviction and flushing to stay within your memory limits while minimizing the performance hit of those mandatory disk writes.

It's a really complex optimization problem.

We mentioned pinning as a great optimization.

What about handling massive one -time data accesses, like a huge table scan?

You certainly don't want those millions of pages to pollute your cash.

Precisely.

That's where techniques like immediate eviction come in.

For large sequential scans, some systems use a dedicated circular buffer, or even a simple first -in, first -out, or FIFO policy just for those pages.

They're read once and then immediately marked as evictable.

This prevents them from displacing the highly valuable, frequently accessed Btree nodes that are so critical for your day -to -day OLTP performance.

That makes the shift to our next topic completely logical.

Page replacement policies.

When we absolutely must evict something, how do we decide which page is the sacrificial lamb?

The goal, ideally, is to have a crystal ball algorithm that can perfectly estimate which page is least likely to be accessed again soon.

But of course, that prediction is never perfect.

And this is where we run headlong into Bellotti's Anomaly.

Could you explain why just increasing your cache size doesn't necessarily guarantee a performance improvement if your algorithm is poor?

Right.

Bellotti's Anomaly is this counterintuitive finding that warns us that our intuition can fail us.

You might think, I'll just add more memory.

So you increase your cache from 1 GB to 2 GB.

But if your replacement algorithm is terrible, that new larger memory space might allow pages to stay in memory just long enough to interfere with each other's access patterns.

You could potentially increase the rate of evictions or thrashing where the system is just constantly loading and unloading pages.

So the algorithm matters more than the raw capacity.

Way more.

It's a stark warning about that.

So starting with the algorithms, let's revisit that naive approach you mentioned.

FIFO.

First in, first out.

FIFO is simple.

The oldest page gets evicted.

For general systems, this is bad enough.

But for structured databases using B -trees, it's truly terrible.

As we discussed, the root page of a B -tree is usually paged in first, which makes it the oldest resident.

Under FIFO, you would constantly be evicting and then reloading the B -tree root, which would make lookups impossibly slow.

Okay, so that's out.

Which brings us to the gold standard of recency, LRU.

Least recently used.

LRU is a significant improvement.

It operates on the assumption that if a page was accessed recently, it will probably be accessed again soon.

Any access moves that page to the newest spot in a queue.

This is excellent for keeping hot data in memory.

The major drawback, though, is the high cost of maintaining this in a highly concurrent environment.

How so?

Every single access requires a complex update.

You have to relink pointers in this queue structure, which must be protected by synchronization primitives like locks or latches.

And that leads to contention.

It slows things down.

That complexity leads to variants like LRUK, which tracks the last k accesses, or 2Q, which separates pages based on initial versus frequent access.

But when systems prioritize efficiency and concurrency over perfect statistical precision, they often turn to the CLOCK sweep algorithm.

Ah, CLOCK sweep.

It's an engineering marvel of compromise.

It trades the absolute precision of LRU for far greater efficiency, especially with concurrent use.

It uses a simple circular buffer structure, which is easy to implement, and a single access bit on each page slot.

So walk us through the CLOCK process.

Let's visualize figure 5 -2 with the clock hand sweeping around the buffer.

Okay.

Imagine this clock hand moving around the circular buffer whenever the system needs a free page.

Every out of a page is accessed.

Its access bit is set to one.

Now, when the clock hand lands on a page, it follows a very simple decision loop.

What's the loop?

First, if the bit is one, it means the page was recently referenced.

So the hand resets the bit to zero, giving the page a sort of second chance, and then it just moves to the next slot.

Second, if the bit is zero, that means the page hasn't been accessed since the last time the hand swept past it.

This page is now a prime candidate for eviction.

And what if the page is Right, that's the third case.

If the page is currently pinned or referenced by a storage operation, the bit stays at one, and the page is entirely protected.

The clock hand just skips it.

And the efficiency comes from the fact that we don't need all that complex pointer relinking like in LRU.

Exactly.

Since it's a circular array, updating the clock hand pointer and changing the access bits can often be done using simple, low -contention atomic operations like compare swap.

This makes it fantastic for concurrent access management compared to maintaining a complicated LRU list.

Now, what if we want to factor in access frequency rather than just recency?

I mean, recency can be fooled by a single massive sequential scan, which could push out truly frequently used pages.

That brings us to LFU, least frequently used.

Right.

LFU tries to track a page's lifetime access frequency.

The engineering challenge here is managing that history.

You can't track every single access forever.

It's impossible.

This is why modern implementations like TinyLFU, which is used in the Java caching library Caffeine, use some really clever data structures.

TinyLFU uses a frequency histogram to keep a compact history, and it divides the cache into several queues, which we see laid out in Figure 5 .3.

How do elements flow through the system?

TinyLFU is essentially a multi -level cache that uses frequency as its promotion mechanism.

New elements start in the admission queue, which behaves like a simple LRU.

When the admission queue gets full, the system doesn't just evict the LRU candidate.

It first compares that candidate's frequency score, which it gets from the compact histogram,

against the frequency of the candidate that's ready for eviction for the next level, the probation queue.

So it's frequency -based promotion, not just eviction, a sort of contest.

Exactly.

It's a contest.

An item is only admitted or promoted if its frequency score is higher than the item currently sitting at the eviction end of that probation queue.

If it succeeds, it lands in probation.

If it continues to be accessed frequently, it can then move up to the protected queue, which has the highest retention.

Then the benefit.

This provides high retention for truly hot items while very quickly filtering out the one -hit wonder items, even if they were recent.

It's a very sophisticated way to achieve high hit rates without the massive overhead of tracking full LRU or full frequency histories.

So the choice of replacement strategy dramatically impacts everything.

Latency, IO, and throughput.

But none of that performance matters if the database can't keep its promises.

Which is why we now have to transition to the systems that enforce the durability component of ACID, even in the face of absolute failure.

Okay.

Transitioning to recovery mechanisms.

We are now addressing the inevitability of crashes.

A database system absolutely must be able to return to a consistent state and honor all of its committed transactions.

This is where the Right Ahead Log, or WALL, steps in as the system's insurance policy.

The WALL is non -negotiable.

It is an append -only disk resident structure, and its fundamental purpose is to record the history of operations before those operations are ever applied to the data pages in the volatile page cache.

This enforces the Right Ahead Rule, log first, modify later.

What are the three key functions the WALL fulfills by sticking to that rule?

Okay.

So first, it allows the page cache to buffer updates in fast RAM while still guaranteeing durability.

We get to decouple the speedy transaction commit from the slow disk write.

Second, it maintains a persistent history of operations until the associated data pages are synchronized to disk.

And third, and this is the most dramatic one, it allows the system to reconstruct any lost in -memory state after a crash.

The WALL must be immutable and totally ordered.

How does the database manage writes to ensure this order?

Every single record written to the log is assigned a unique, monotonically increasing log sequence number, or LSN.

These records are first cached in a log buffer in memory, and then they must be flushed to disk via force operation, always in strict LSN order.

The good news is that sequential disk writes are very fast, which is critical for minimizing commit latency.

And this LSN order is the very foundation of the durability guarantee.

Absolutely.

A transaction is only considered committed when its final commit record and all preceding log records have been forced to persistent disk.

If the server loses power one microsecond before that force operation completes, that transaction is considered aborted and will be rolled back upon restart.

You mentioned compensation log records, or CLRs, earlier.

Why are they necessary during a rollback?

This is a really robust feature designed for resiliency during the recovery itself.

When a transaction needs to be undone, the system performs the undo operation.

But what if the system crashes while performing that undo?

You have a messy situation.

The CLR logs the action of the undo operation itself.

So if the system restarts again, the CLR tells the recovery manager, hey, I was in the middle of undoing this transaction, and here's the LSN where it stopped.

So it prevents double undoing.

Exactly.

It prevents the system from re -undoing work that has already been reversed, which could lead to further data corruption.

It's a metal log for the recovery process.

Let's pause for a moment to reflect on just how complex this implementation can be.

The source material has this great, or maybe terrifying, anecdote about a post -gresql sync issue.

Why does one small kernel interaction highlight the fragility of the entire recovery system?

Oh, it's terrifying, actually.

The issue came from the think system call, which is the command that tells the OS to synchronize dirty pages to disk.

In certain OS configurations,

think might return an error, but the kernel might still clear the dirty flag on those pages in its own cache.

Ouch.

Yeah.

So if the database's checkpoint process, which isn't constantly pulling the kernel for every little thing, missed that error notification, it would just assume the written.

It might then proceed with very dangerous steps, like prematurely trimming the wall.

If a crash happened after that, the database would wake up and realize the committed data was never actually written, and worse, the log records it needed for recovery were gone.

Catastrophic data loss.

Total data loss.

It illustrates that guaranteeing durability requires painstaking, low -level coordination between the application and the operating system.

Even a small assumption about an OS call can break the whole promise.

That makes the work of the checkpoint process even more critical.

Since the wall log grows continuously, we have to be able to trim it at some point.

Checkpoints are the mechanism for establishing a safe, known starting point for recovery.

And by doing that, they allow the system to discard older log records.

If we kept the full history forever, recovery after a crash could take hours.

The simplest idea is the sync checkpoint.

Which is completely impractical because it requires pausing all ongoing operations while you flush every single dirty page simultaneously.

Right.

High concurrency demands a less intrusive method, which is why most modern databases use the fuzzy checkpoint.

A fuzzy checkpoint begins by logging the begin checkpoint record, and it ends with an end checkpoint record that summarizes the state so, the list of dirty pages and running transactions at that moment.

The actual flushing of the dirty pages happens asynchronously in the background.

And when is the checkpoint actually considered valid and usable?

The checkpoint is only considered complete, and the log header's last checkpoint pointer is only updated once all the pages that were referenced in that end checkpoint record have finished flushing to disk.

This gives the recovery process a reliable, recent starting LSN, which drastically reduces the amount of work it needs to do during a restart.

Okay, let's refine our understanding of what actually goes into the log.

We can log state changes either by image or by operation.

How do the physical log and the logical log differ in this regard?

A physical log is very granular.

It stores complete before -image and after -image snapshots of the page, or maybe just bytewise changes.

This is primarily useful for redo operations because you can rapidly restore the exact physical state of the page.

A logical log, on the other hand, stores high -level operations like update account x balance by $10 or insert this record.

It also stores the corresponding high -level undo operation, like remove this record.

And why is the logical log often preferred for undo operations?

Logical undo operations can often be applied independently, and they don't require deep knowledge of the physical page structure.

They tend to improve concurrency during the execution phase.

The source notes that a common, highly efficient mix, used notably by the Arei's algorithm, is to use logical undo

So you get the best of both worlds.

You do.

You leverage the raw speed of physical redo during crash recovery, while using the flexibility of logical undo to maintain good concurrency during normal execution.

We've established the components.

Now we need to look at the engineering decisions that determine how severe a crash is.

These are the steel and force policies, which dictate the interaction between the volatile page cache and the persistent log.

Right.

This is a spectrum of safety versus performance.

These four policies really define whether you're going to rely more heavily on undoing changes or redoing changes after a failure.

Let's start with the steal policy.

The steal policy allows the buffer manager to flush a dirty page that was modified by a transaction before that transaction is actually committed.

It steals the cache space by pushing uncommuted changes out to disk.

What's the massive implication for recovery if you allow that kind of stealing?

If the system crashes,

you might find uncommitted partial changes written on the disk.

To guarantee atomicity, you must be able to remove those changes.

Therefore, a steal policy absolutely requires undo logs for recovery.

If you adopt a no -steal policy, you prevent any uncommitted changes from ever hitting the disk, which makes recovery much simpler.

You only need redo logs.

Okay, now for the commit timing.

The force policy.

The force policy is the safest, but also the slowest.

It requires that all pages modified by a transaction be flushed to disk before the transaction is allowed to commit.

The result is that durability is guaranteed on disk the instant you acknowledge the commit.

And the high -performance inverse.

That would be the no -force policy.

This allows the transaction to commit even if the modified data pages are still dirty and sitting in the page cache.

This allows for extremely fast commit times because you only have to incur the fast sequential write to the wall.

However, this means that if you crash after committing, but before those pages flush, you must rely on the log to restore the data.

So no force requires redo logs for recovery.

So if the engineering goal is maximum possible performance, the combination you'd choose is steal no force.

This speeds up both caching by stealing space and the commit time by not forcing writes.

And this brings us directly to ARIES.

That's the algorithm for recovery and isolation and exploiting semantics.

ARIES is a prime example of a robust production grade steal no force algorithm.

It combines logical undo, physical redo, and fuzzy checkpointing.

It's really the gold standard for crash recovery.

Let's walk through the three dramatic phases of ARIES recovery when the system restarts after a failure.

Phase one, analysis.

Right.

The database is essentially trying to figure out what was I doing when I died?

It starts reading the log forward from the last checkpoint LSN.

The goal is to identify two crucial sets of information.

The dirty pages, which pages were modified but not yet flushed, and the set of in -progress transactions.

The ones that had not committed when the crash happened.

This phase just establishes the boundaries for all the work to come.

Phase two, the redo phase, the repeating history phase.

This is where we restore the world exactly as it was at the moment of the crash.

ARIES re -applies every single operation, starting from the earliest LSN associated with the dirty page it found in the analysis phase.

This includes changes from transactions that successfully committed, which fixes the no force problem, and changes from transactions that were incomplete to restore the physical state needed for undoing them later.

We are physically replaying history up to the point of failure.

And phase three, the undo phase, the cleanup.

Now that the physical state is restored, we have to ensure atomicity.

We take that list of in -progress transactions we identified back in the analysis phase, and we roll them back using logical undo operations.

This is done in reverse chronological LSN order.

And this is where those compensation log records, the CLRs, are logged.

They serve as markers, so that if the system crashes during the rollback itself, the next recovery attempt knows exactly which undo operations already succeeded and where to resume.

Wow.

The ARIES algorithm really demonstrates the immense internal complexity required just to honor the A and D in ACID.

It's the ultimate example of a database having to perfectly remember its own history, even after a near -death experience.

We've ensured durability and recovery.

Now we tackle the real -time, minute -by -minute challenge of concurrency control.

This is how we allow thousands of transactions to run at the exact same moment without seeing each other's half -finished work.

Concurrency control is all about managing resource interactions to maintain that isolation property.

And we generally group the techniques into three philosophical approaches.

Okay, first up,

optimistic concurrency control, or OCC.

The optimistic approach basically says, conflicts are probably rare, so let's just run and we'll deal with the fallout later.

Transactions execute freely and only check for conflicts right before they try to commit.

If there's a conflict, the system aborts one of them and retries.

This maximizes parallelism when contention is low.

Second, multi -version concurrency control,

MVCC uses time as a coordinator.

It maintains multiple, time -stamped versions of records.

This allows readers to access a consistent snapshot of the data from the moment they started, completely without blocking writers, which is a massive performance win.

And third, pessimistic concurrency control, PCC.

The pessimistic approach is more conservative.

It says, conflicts are lively, so we must block execution early.

This includes traditional lock -based systems, like where transactions acquire locks and force others to wait, or even non -locking time stamp ordering approaches.

Before we discuss the mechanisms, we need the technical gold standard for correctness, serializability.

Every transaction creates an interleaved schedule of operations.

Right, a schedule is just a precise sequence of reads, writes, commits, or aborts from all running transactions.

A serial schedule is where T1 runs to completion, then T2, then T3, one after another.

This is obviously correct, but the throughput is terrible.

So serializability is the concept that the concurrent execution schedule must produce the exact same final result as if the transactions had been executed serially in some order.

Figure 5 -4 illustrates this with three transactions, T1, T2, and P3.

If they run concurrently, the result has to be equivalent to one of the six possible sequential orderings of those three transactions.

That equivalence is the guarantee of isolation.

The database guarantees the correct final state without forcing the transactions to wait sequentially.

The whole trick is achieving this speed while preserving that correctness.

And if the isolation property is weakened for performance, we introduce read and write anomalies.

Let's review the three read anomalies from the SQL standard, starting with the simplest, the dirty read.

A dirty read is when one transaction, T1, reads data that was modified by another transaction, T2, and T2 has not yet committed.

If T2 later aborts, T1 has acted on phantom data that never officially existed.

This is the least safe type of read you can do.

Moving up in safety, we have the non -repeatable read or a fuzzy read.

This is when T1 reads a specific row.

Before T1 finishes, T2 comes along, modifies that same row, and commits.

Then T1 reads the row a second time and gets a different, newer result.

The data is committed, so it's not dirty, but T1's view of the world is unstable because the content of a single row changed mid -transaction.

And finally, the phantom read.

This applies to sets of data.

T1 runs a query looking for, say, all accounts with a balance over $100.

Then T2 inserts a brand new account that fits that criterion and commits.

T1 reruns the same query and suddenly sees a different set of rows.

That new row is the phantom.

Okay, now for the more insidious write anomalies.

First, the lost update.

This happens in concurrent read -modify -write scenarios.

T1 reads a value, let's call it V.

Then T2 reads the same value V.

T1 calculates a change, writes a new value V, and commits.

Then T2, which is still working with the original V, calculates its change, writes V, and commits, completely overwriting and losing T1's update.

Then the dirty write.

A dirty write is when T1 modifies a value, and T2 comes along and modifies that same value before T1 even commits.

This is highly problematic because if T1 then aborts, its rollback might incorrectly overwrite T2's, potentially still running modification.

Most concurrency control schemes work very hard to prevent dirty writes immediately.

And the most subtle one that often slips through weakened isolation levels, write skew.

Let's use that dual account withdrawal example again.

We have A1 with $100 and A2 with $150.

And the business rule, the invariant, is A1 plus A2 must be greater than or equal to $0.

This is the perfect illustration of why simple row level locking isn't enough.

So T1 starts, checks.

Is A1 plus A2, which is $250, positive?

Yes.

So T1 proceeds to withdraw $200 from A1, making A1's balance made to $100.

Concurrently, T2 checks its own copy of the data.

Is A1 plus A2 $250 positive?

Yes.

So T2 proceeds to withdraw $200 from A2, making A2's balance make it $50.

Both transactions committed, having followed their local rules perfectly.

But the global system is now A1 plus A2 equals $150,

which violates the global invariant.

Wow.

Write skew happens because the transactions didn't realize they were relying on the same piece of information, the combined balance, to make independent updates to separate accounts.

It perfectly shows the failure of isolation short of true serializability.

Which is exactly why we use a hierarchy of isolation levels, which is clearly shown in Figure 5 -5.

It's all about trading that correctness for OK, we start at the bottom with read uncommitted, the weakest level.

This allows dirty reads, and by extension all the other anomalies, it's primarily useful for very high speed statistical reads where absolute precision isn't required.

Next up, read committed.

This avoids dirty reads by making sure you only read committed data, but it still allows non -repeatable and phantom reads.

This is the default in many popular databases because it provides a pretty good balance between safety and concurrency.

Repeatable read.

This avoids both dirty reads and non -repeatable reads.

If you query the same row twice, you're guaranteed to get the same result.

Crucially, though, it still permits phantom reads when you're dealing with range inserts or deletes.

And serializable is the peak, avoiding all three.

Serializable ensures the execution is equivalent to a serial run, guaranteeing freedom from all these read anomalies.

It provides the strongest guarantee, but often at the cost of the lowest throughput due to all the required locking.

And where does snapshot isolation, or SI, which is so commonly used in modern systems, fit into this hierarchy?

Snapshot isolation is positioned just above repeatable read, but slightly below full serializable.

It guarantees that a transaction executes against a static, committed view, a snapshot, of the database that was taken at its start time.

It successfully prevents lost update anomalies by checking for concurrent writes upon commit.

But.

But, as we just saw with our A1A2 example, because it allows transactions to read from their old, consistent snapshot and then write repeatedly,

it still permits the subtle write skew anomaly.

Okay, let's look closer at the implementation techniques, starting with optimistic concurrency control, OCC.

Since it assumes conflicts are rare, it avoids that heavy -handed approach of using locks.

OCC is fantastic for systems with many reads and few writes, or where the data sets being modified are largely independent.

It uses a three -phase approach, treating the entire transaction as a kind of speculative execution.

Phase one, the read phase.

The transaction runs privately, reading values and performing all its logic in isolation.

Crucially, it records two things.

It's read set, which is all the data it looked at, and it's write set, which is all the modifications it intends to make.

No actual database modifications are made yet.

Phase two, the validation phase.

This is the bottleneck, but it's designed to be fast.

The system checks if the transaction's read set or write set conflicts with any transactions that have already committed or are currently in the validation phase themselves.

If the data T1 read was modified by T2, and T2 committed while T1 was running, then T1's read set is stale, and it fails validation.

And if it fail?

It's immediately aborted and restarted from scratch.

What's the difference between the two validation styles So backward -oriented validation checks T1 against a history of transactions that have already committed while T1 was running.

Forward -oriented validation checks T1 against other transactions that are currently in the validation phase.

If two transactions are trying to validate at the same time, the system has to have a rule to decide which one wins.

And finally, phase three, the write phase.

If validation succeeds,

the transaction's write set is atomically applied to the database state.

This critical section, the validation and writing, must be extremely short and protected to maintain serializability.

The performance of OCC hinges entirely on keeping that conflict rate low.

If you have too many aborts, the overhead of restarting transactions completely negates the benefit of avoiding locks in the first place.

Alright, now let's move to pessimistic concurrency control,

PCC.

You mentioned it could be lock -free using something called timestamp ordering.

Right, timestamp ordering is another way to enforce serializability without traditional two -phase locking.

Every transaction gets a unique, globally consistent timestamp when it starts.

The system then maintains two timestamps for every piece of data, a max -read timestamp and a max -write timestamp.

How did those timestamps enforce the transaction order?

The rules are very strict.

For a read operation by T1, if T1's timestamp is lower than the data's max -write timestamp, meaning a newer transaction has already committed a write to the people, the value T1 must abort.

Because T1 is trying to read a value that should have been invisible to it based on the timeline.

It's from the future, so to speak.

And for a write operation by T1, if T1's timestamp is lower than the data's max -read timestamp, meaning a newer transaction has already read the old value T1 must also abort,

T1's outdated write would confuse that reader.

But there's an optimization that saves some unnecessary abortions, the Thomas write rule.

This is a classic efficiency trick.

If T1 tries to write a value, but its timestamp is lower than the current max -write timestamp, we know that T1's write is already obsolete.

A newer, legitimate transaction has already overwritten it.

So instead of aborting T1, the Thomas write rule simply discards T1's write operation and lets T1 continue.

It prevents an abort for a write that was doomed to be overwritten anyway.

Okay.

And finally, the traditional PCC mechanism, lock -based concurrency control, specifically two -phase locking, or 2PL.

2PL uses explicit shared and exclusive locks on data items to enforce serializability.

It's defined by two strict, non -overlapping phases, ensuring that once a transaction starts releasing its safety mechanisms, it cannot acquire any new ones.

Phase one, the growing phase.

The transaction acquires all the necessary locks it needs to read and write.

The critical rule is that no locks can be released during this time.

The transaction just accumulates its resources.

And phase two,

the shrinking phase.

Once the transaction releases its very first lock, it enters the shrinking phase.

It can then release the remaining locks, but the new rule is that no new locks can be acquired.

This strict discipline is what guarantees serializability.

The resources required for correctness are held until the transaction is absolutely sure it doesn't need to change its mind.

And as noted, we have to be absolutely clear.

This is two -phase locking, a local concurrency control mechanism, and it is fundamentally different from the two -phase commit protocol.

Completely different.

They share the name two -phase, but they solve entirely distinct problems.

One is about local concurrency.

The other is about distributed agreement.

The moment you introduce waiting mechanisms like 2PL, you introduce the risk of deadlocks.

A deadlock is the nightmare scenario where transactions are indefinitely stalled, waiting for resources held by each other.

Figure five, six illustrates the problem perfectly.

T1 holds lock L1 and is waiting for L2, but at the same time T2 holds L2 and is waiting for L1.

Neither one can proceed.

They're stuck forever.

How does the system manage deadlocks beyond just, you know, timing out a transaction?

We use methods for either detection or avoidance.

Detection involves the transaction manager constantly monitoring the system by maintaining a wasteful graph.

This graph literally maps which transaction is waiting for which lock and who currently holds it.

And a cycle in that graph means?

Instant deadlock.

If T1 waits for T2 and T2 waits for T3 and T3 waits back for T1, you have a cycle.

This system has to select a victim, usually a transaction that has done the least amount of work or acquired its lock most recently, and just abort it to break the cycle.

Then we have avoidance protocols, which use the transaction's timestamp or priority to prevent the cycle from ever forming in the first place.

Right.

These protocols ensure that any waiting relationship always flows in one direction, usually from lower priority transactions to higher priority transactions.

Protocol one, wait die.

In wait die, if the transaction trying to acquire the lock, let's call it T1, has higher priority, a lower timestamp than the transaction holding the lock, T2, then T1 is allowed to wait and block.

But if T1 has lower priority, it must abort and retry later.

It has to die.

Only higher priority transactions are allowed to wait for lower priority ones.

And protocol two, wound wait.

This is the inverse.

If the transaction trying to acquire the lock, T1, has higher priority, it wounds T2, meaning it forces T2 to abort and restart immediately.

But if T1 has lower priority, T1 must wait for T2 to finish.

The rule here is that higher priority transactions force lower priority ones out of the way.

These protocols are vital because they provide these strict rules that prevent the circular waiting patterns that define a deadlock.

They ensure that if a transaction is forced to wait, it can only be for a transaction that is older or higher in the predetermined hierarchy, which guarantees eventual progress for everyone.

Now, for a critical distinction that I think confuses many engineers, especially those crossing over from general programming,

locks versus latches.

This distinction is so crucial in database internals.

Locks are high -level.

They guard logical data integrity and transaction correctness, the ACD properties.

They operate on high -level resources like a key, a row, or a whole table, and they are held for the entire duration of the transaction.

They're what prevent anomalies like lost updates.

Latches, on the other hand, are the low -level physical guards.

Exactly.

Latches are short -term synchronization primitives.

They guard physical data integrity, like the actual contents of a page buffer in memory or the structural pointers inside an index node.

They are held only for the smallest possible duration, just long enough for a thread to read or modify a pointer or a few bytes on a page, and then they're immediately released.

They ensure concurrent threads don't corrupt the in -memory data structures.

And since multiple threads might need to read the same page simultaneously, we need more flexible latches than just simple exclusive access.

That's why the Reader's Writer Lock, or RW Lock, is standard.

It permits multiple concurrent readers to hold the latch in shared mode.

This drastically improves read throughput.

However, any writer must acquire the latch in exclusive mode, which then blocks all other readers and writers until its update is complete.

Figure 5 -7 confirms the compatibility here.

Only shared access between readers is allowed.

Any other combination requires exclusivity.

To maximize concurrency, we have to minimize the time a latch is held.

That is the goal of the key optimization for B -tree indexes.

Latch -crabbing or Latch -coupling?

Latch -crabbing is an optimistic strategy designed for traversals.

If you were to hold a latch on the root while traversing the entire tree, you would create a massive bottleneck.

The goal of crabbing is to release the parent latch as soon as you have safely acquired the child latch.

What determines that safety, particularly during an insert operation?

Well, for a simple read, safety is easy.

You acquire the child's shared latch, then you can release the parent's shared latch.

For an insert requiring a right latch, as shown in Figure 5 -9, the check is focused on structural change propagation.

You acquire the right latch on the root and descend, acquiring the right latch on the child.

Now, the critical point.

If that child node is not full, you are guaranteed that the insert will not cause a split that needs to propagate back up to the parent.

And because the insertion is self -contained?

You immediately release the parent latch.

You don't need it anymore.

So, we only hold the parent latch if we are pessimistic about the child.

If we think we're about to perform a structural change, like a split or a merge, that's going to need to modify the parent's pointer.

It's highly efficient because statistically, most operations do not cause splits.

By only holding that parent lock for that very short window of potential structural change, we drastically minimize the contention on those higher, more frequently accessed nodes in the tree.

Another technique mentioned is latch upgrading.

Right.

Instead of grabbing an expensive exclusive latch immediately, the traversal acquires cheap shared latches all the way down the search path.

Only when the thread reaches the leaf page and determines it actually needs to write, potentially causing a split or merge, does it then attempt to upgrade that shared latch to an exclusive latch on the required nodes, climbing back up the tree only if absolutely necessary.

Again, this optimizes for the common case, which is non -modifying reads.

And finally, we have the highly advanced blink trees, or B -link trees, which take concurrency control for indexes even further.

What structural additions do they make?

Blink trees, which derive from B -star trees, add two crucial features, high keys and sibling

subtree.

The sibling link is a pointer that links every node to its immediate right sibling on the same level of the tree.

What performance benefit does that sibling link provide, especially during a structural change like a split?

It allows for massively reduced contention during splits.

A split involves creating a new node,

adding it via the sibling link, and then later updating the parent node to point to this new node.

This allows the system to enter a temporary half -split state.

So if a reader is traversing the tree, and it hits a node whose high key is smaller than the key it's searching for, it realizes the structure has changed concurrently.

But instead of aborting and restarting the whole search, it just follows the link.

It just follows the sibling link pointer to the next node and continues its traversal.

That's a really powerful idea.

It allows the complex parent pointer update to happen lazily without blocking concurrent readers, ensuring that readers can self -correct their path, even if a writer is in the middle of a structural modification.

It effectively decouples the structural change from the read operation.

This prevents the reader from needing to acquire or hold ancestor latches for long periods, which significantly boosts overall system throughput.

We've covered the internal mechanics that transition a simple set of files into a robust transactional database system.

If we zoom out, we can clearly see the two main system -level problems this chapter really solves.

First, there's the coordination challenge.

How do you align the volatile page cache with the persistent write -ahead log to honor the ACD contract?

That's all dictated by those crucial steel and force policies, and that governs both durability and your recovery speed.

And second, the resource contention challenge.

How do you maintain the appearance of sequential isolate execution while maximizing concurrency?

This is the domain of all those concurrency strategies, OCC, PCC, MVCC, and their underlying physical mechanisms like latch grabbing and blink trees.

It's all about engineering trade -offs.

Every single decision, from choosing the CLSK algorithm over LRU to selecting snapshot isolation over full serializability, involves this delicate balance between performance, speed, and safety.

Which leaves us with the inherent and I think provocative conflict at the very heart of database design.

We established that the theoretical gold standard is serializable, isolation, perfect correctness, and integrity.

But we also know that strict locking to achieve that standard fundamentally chokes system throughput.

It can bring things to a crawl.

So the engineering effort we've spent this time analyzing, whether it's using snapshot isolation to incorporate time through timestamped versions or utilizing structures like blink trees to leverage structural optimism with sibling pointers, instead of just relying solely on heavy locks, it's all aimed at one goal.

It is the relentless, ingenious effort to find ways to cheat that fundamental conflict between speed and perfect correctness.

It's about making the database appear sequential and safe to you, the user, while it's secretly executing thousands of interleaved operations in parallel underneath.

That tension is what drives all the innovation in database systems today.

And that is a truly deep dive into the engines of persistence.

Thank you for guiding us through the mechanical heart of transactions and recovery.

My pleasure.

It's really critical knowledge for anyone who wants to understand what makes these systems truly tick.

And thank you for joining us.

We hope you feel far more well informed about the complex promises your database system is making, and more importantly, how it keeps them.

We'll catch you next time.