Experiment | Recovery

Here are the chapters of Experiments and Recovery.
Lecture_5

Experimental Design

Do-it-yourself recap

The below (Lecture 3 and Lecture 4) is all about achieving isolation, I in ACID.

Objectives Today

—> Focus on the atomicity and durability

Techniques to Evaluate Performance

Three main techniques for performance measurement and modeling.

Do-it-yourself Recap - Virtual Memory With Paging

Analytical Modeling

So, according to the previous example, we can introduce a new kind of question. Given such a system, and discuss its performance. The previous example is about latency.

Simulation

We want to obtain the HitRatio by measuring it. So we will simulate a particular component of the system, maybe the virtual memory with paging component and you will estimate certain known parameters like latency of the main memory and the latency of the disk. Those are easier to get out from other specifications than the HitRatio which is certainly workloads specific. Then, we try different workloads to measure the HitRatio on our partial implementation that focuses on this particular aspect of the system. That’s a simulation.

Pros & Cons of Simulation

Why do we consider such things? It’s a way to estimate difficult parameters, and it may be easier to do this rather than performing a full-blown implementation of the entire system and measuring the actual HitRatio. => If you want to implement the whole system and measure the actual value, that is the so-called Experiment.

Numbers Everyone Should Know

image-20230105162342099

And remember, do not switch them even though they do stay roughly the same. The main thing is they are relative to how they compare the world.

Choosing Workloads & Datasets

This is how we can estimate parameters. How can we choose workloads?

And this method is maybe the usual technique in the practice.

Experimentation

Simple Factor Experimentation

How to set up certain experiments?

In Practice: Many Factors

image-20230105170239576

How to pick up the parameters to run the experiments is very difficult, and there should already be with some hypothesis to help us.

Benchmarking

Designing a Micro-Benchmark => Not Understand

Hint: Think about your measurement program!

for (i=0; i<file.len; i++)
  read(f, i)

We already came up with very simple experiment with three different programs, reading forwards, reading backwards from the end, and random points. We can vary the file size. We can measure different things below. We have some multi-dimensional thing so maybe that reading left right works best. And that’s what we try to measure those experiments.

What would we measure?

Necessary Care with Executing Experiments

When executing the experiments, select your data carefully, workloads carefully. For example, when you are comes counting things, be careful what you’re counting. Be careful to not introduce overhead by running the experiments. That’s can also lead you to wrong improvements obviously.

Think how you measure things. For example, sampling you run a system and periodically at different time points you take measurements or you let the system log certain things with a monitor. And what it logs. Be careful always some interpreting statistics when you look at other people and they tell you the conclusions they drawn from statistics. Don't be tricked by one arguments.

Comparing Alternatives

Two systems, with throughput-oriented measurements $R_2$ and $R_1$

Speedup

Relative change

Example statements

Recovery: Basic Concepts

The next topic is about the ACID properties and here are different notions of atomicity that we have discussed before. In lecture 3 and lecture 4 about Concurrency Control, we are talking about Before-or-after atomicity (== Isolation). But right now, about recovery, we are focused on All-or-nothing atomicity (== A: Atomicity + D: Durability).

This is what we want to achieve. And what would be the problems?

Implementing All-or-Nothing Atomicity

This is something that could happen. $T1$, $T2$, and $T3$ can successfully commit, so these transactions definitely have been executed. $T4$ and $T5$ still running at this point when a crash happened. And that even though they might have already performed certain WRITEs on the database. They modified the state of the database, these transactions should be undone and we don’t want to see any effects or any modifications performed by these transactions in our database. Hence, the transactions that were running at the moment of the crash should be aborted.

Official Statement:

Assumptions

What are our assumptions?

The failures are always considered to be fail-stop and this means that some part of the system completely breaks. It’s not like one bit was flipped, we will not consider such kinds of variables rather the entire system stopped or maybe needs to restart. So all the information that was stored in the system maybe is gone. And then, we are gonna talk about which parts are gone.

Volatile vs. Nonvolatile vs. Stable Storage

To talk about which parts disappear after a crash and which parts survive, we are going to talk about the different kinds of storage that we have in such a system.

Surviving Crashes: How to handle the Buffer Pool?

Now the central question is when we have such a crash, where the volatile memory is lost?

And the question is, how can we restore it or restore the information that we need to be stored there?

And the two basic strategies are called force and steal.

image-20230105224632537

Force

Force means that everything that is written to this buffer also gets written to the disk, and the downside is of course maybe we need to wait for the WRITEs as we already remarked when we are discussing the two-level virtual memory abstraction. But on the other side, we can survive with respect to crashes due to the durability because everything is written on the disk.

However, because we don’t want to wait for every WRITE been propagated to the disk (i.e., As 2 level memory abstraction, we want the performance => latency to be close to the RAM, so we should use No Force), we want to lean to the No Force side.

Steal

And now, given that, there will be a quite lot of contention on the memory because everybody will want to write to the fast medium and things then will live in memory.

The different transactions compete for space in the Buffer-Pool. And the question is if there is too little space, what should happen? A transaction that wants to write something, can it steal a frame or page from another transaction that may be not even committed yet?

So if we don’t steal pages, this means our memories are the critical region. Then the transactions will block if they want to access a page but they cannot get a page from the memory. This will impact our throughput and this means that we want to lean on the stealing side where our transaction is allowed to steal a page that belongs to a potential uncommitted transaction.

If in the corner of “No Steal” and “Force”, it can ensure atomicity and durability. However, if in the “Desired” corner, both questions become open.

Fill in the matrix

When do you need to UNDO changes? => STEAL

So for this problem, we need to consider what happens to the disk.

If we steal, for example, frames or pages, we might end up with pages of uncommitted transactions written to the disk. And there is a certain danger always that the transaction gets aborted. For example, if a crash occurs, so we might need UNDO. So, on the Steal side of things, we need UNDO.

When do you need to REDO changes?

When we don’t write things into the disk, you might have committed transactions that don’t write immediately to the disk. => We might have committed transactions whose modifications only live in memory. And if at that point, a crash occurs, we need to first see how we can redo the actions but we need to REDO them because the things that changed in this memory will be lost. So whenever we don’t force things, we need REDO things.

More on Steal and Force

STEAL is essentially the justification why enforcing atomicity is hard.

Suppose the frame or the page that we are about to steal is already written to the disk and particular some transaction holds the lock on this page. Now we need to consider what happens if this transaction aborts.

We need to remember the old value that was stored on this page at the moment of the steal to UNDO the write that we just performed to this disk.

I think this is just the same case as what we have mentioned when talking about filling in the matrix. And this is all to enforce that we cannot have partially executed transactions and then see the effects on the memory.

NO FORCE (Why enforcing Durability is hard) => We are not necessarily writing modifications by committed transactions immediately to disk.

UNDO/REDO vs. FORCE/STEAL

image-20230106000931305

In the case of NO FORCE, we need to REDO things. In the case of STEAL, we need to UNDO things. And how do we support the hardest corner that we desired?

Basic Idea: Logging

To approach this corner, we can use logging and log all the operations that we do on the database. So there will be record information that this relevant for both REDOing and UNDOing actions for every update.

We store these in the so-called log. We write sequentially to the logs, that's the order of things determined there. We have S2PL so the actions are ordered somehow.

We also put it maybe on a separate disk, hopefully on stable storage when we don’t want to lose the log.

We try to write some minimal information that is required to perform our changes. We do not want to duplicate the database in the log. But in particular, we compress things so that multiple updates fit in a single log page. So whenever we write to the log, we are performing effectively many more writes than when we actually write data to disk.

Record REDO and UNDO information, for every update, in a log.

Thus, what is a log?

Log can be thought of abstraction of the sequence of REDO and UNDO actions. There are different ways of logging standard approaches, they are Logical and Physical Logging. Example physical log record contains:

\[<XID, pageID, offset, length, old \ data, new \ data>\]

And there are also compromises where for certain parts, you do physical data use or both the old and the new value. For other parts of other types of database, we store some logical orientation of difference that you can then both REDO and UNDO. => Good compromise is physiological logging.

But for simplicity, we only consider physical logging. => And UNDO is just write the old data, REDO is just write new data.

Write-Ahead Logging (WAL)

The fundamental principle that makes it work is called Write-Ahead Logging.

Golden Rule: The idea is that you never modify the only copy of your data. Kind of always have a log and you modify the log before you actually modify the data.

WAL consists of two principles,

Exactly how is logging (and recovery!) done? We will study the ARIES algorithms.

Recovery Equations

What is stored and how far do we need to go back when we recover? Below is lost one data structure which is volatile (buffer pool)

image-20230106005651216

When we have a crash recovery, we lose the volatile memory that does not show here. What we want to do is to recover the state from the current state of the database plus the log that we have here.

Final Summary