Transactions, partitions and replicas: what one machine promises

The relational contract: a schema and a unit of work

The slides' example works on one table, Account, with an account number AccNum and a Balance. Before any transaction runs, its schema already promises three things, which p. 144 ("The data schema") lists as three bare words: Typing, Coherence, Uniformity. Fig. 1 shows what each one refuses.

Typing: every column has a type, so a balance of 'ten' is refused. Coherence: integrity constraints — keys, references, conditions — keep the data consistent with itself, so a second account 12202 is refused. Uniformity: every row has the same columns. The slide gives only the three words; these glosses are their standard reading. Note when the checks happen: at write time, before the data is accepted. Lesson 4 is about systems that drop them on purpose.

A transaction is one unit of work

The next slide (p. 145) names three settings where transactions matter: "The relational world", "Multi-user", "Distributed systems". This lesson lives in the first two and ends at the door of the third.

The slides' example (p. 148) moves 10 from account 42177 to account 12202:

-- p. 148: transfer 10 from account 42177 to account 12202
begin transaction;
update Account
  set Balance = Balance + 10 where AccNum = 12202;
update Account
  set Balance = Balance - 10 where AccNum = 42177;
commit work;
end transaction;

Credit 12202, debit 42177, make both permanent. The order of the two updates does not matter; that they happen together or not at all does. The next slide (p. 149) adds a business rule — no overdraft — and lets the program choose how to end:

-- p. 149: commit only if 42177 does not go below zero
begin transaction;
update Account
  set Balance = Balance + 10 where AccNum = 12202;
update Account
  set Balance = Balance - 10 where AccNum = 42177;
select Balance into A from Account
  where AccNum = 42177;
if (A>=0) then commit work
          else rollback work;
end transaction;

After the debit, the program reads the new balance of 42177 into the variable A. If A is at least zero it commits; otherwise it executes rollback work — and the rollback cancels the credit to 12202 as well, although that update ran without error. The unit is the transaction, not the statement.

Well-formed transactions and the path of states

An application program is a sequence of such units (p. 147), and each must be well-formed (p. 150): begin transaction; code for data manipulation (reads and writes); commit work or rollback work; no data manipulation; end transaction. Fig. 2 draws the template twice, once for each outcome.

Under the template, p. 150 draws the transaction as a path of states: \(S_0\) before it, a new state after each write W1, W2, …, and \(S_r\), the result. Only the two ends are meant to be seen from outside. With the hook's balances (the slides give none): \(S_0\) = (100, 25), \(S_1\) = (110, 25) after the credit, \(S_r\) = (110, 15) after the debit.

ACID, one letter at a time

"A transaction is a unit of work enjoying the following properties: Atomicity, Consistency, Isolation, Durability" (p. 188). The slides give each letter its own page (pp. 189–192); here each one meets the transfer.

Atomicity: all or nothing

"A transaction is an atomic transformation from the initial state to the final state" (p. 189). Atomic means indivisible: seen from outside, the database either jumps from \(S_0\) to \(S_r\) or stays in \(S_0\), and \(S_1\) — the money from nowhere — is never where it ends. The slide lists three possible behaviours:

1. "Commit work: SUCCESS" — the database reaches \(S_r\) and stays there.
2. "Rollback work or error prior to commit: UNDO" — every write already made is undone, the newest first, back to \(S_0\).
3. "Fault after commit: REDO" — committed writes that may not have reached the disk are applied again, up to \(S_r\).

Under the chain of states the slide draws UNDO arrows back to \(S_0\) and a REDO arrow forward to \(S_r\). Make them happen.

How does a restarted server know what to undo or redo? The slides only name the mechanisms: "Abort-rollback-restart" under atomicity, "Recovery management" under durability (p. 193). The widget shows the textbook answer, background rather than slide material: a log. Every write is first recorded in a log on stable storage, with the old and the new value, before the changed balance itself may reach the disk; commit work appends a commit record. At restart, a transaction without a commit record is undone with the old values; one with a commit record is redone with the new ones.

Consistency: constraints in, constraints out

"The transaction satisfies the integrity constraints"; consequence: "If the initial state is consistent, Then the final state is also consistent" (p. 190). Only the two ends count. Under a rule "the total of all balances never changes", \(S_1\) would be illegal — 135 instead of 125 — and that is allowed, because \(S_1\) is neither the start nor the end.

Which constraints? Those declared in the schema are checked by the DBMS itself; p. 193 calls it "integrity checking of the DBMS". A rule nobody declared, like "no overdraft" here, is the application's job — the if (A>=0) of p. 149. Had the bank declared "balance at least zero" on the column, the DBMS would have refused the debit with an error, and that error before commit would have triggered the UNDO.

Isolation: no half-finished state on show

"A transaction is not affected by the behavior of other, concurrent transactions"; consequence: "Its intermediate states are not exposed" and “The ‘domino effect’ is avoided” (p. 191, over a picture of falling dominoes). The slide does not spell the dominoes out; Fig. 3 shows their standard reading, a cascade of rollbacks.

Without isolation, an interest transaction T₂ could read 110 from 12202 while the transfer T₁ sits in \(S_1\). If T₁ then rolls back, T₂ has paid interest on money that never existed and must roll back too — and so must T₃, which read T₂'s result. With isolation T₂ reads the committed 100, or waits for T₁ to finish, and the first domino never falls. Isolation does not mean one transaction at a time: they still run concurrently, kept apart by "concurrency control" (p. 193).

Durability: committed means forever

“The effect of a transaction that has successfully committed will last ‘forever’”, "Independently of any system fault" (p. 192). Once commit work has run, no crash may bring back 25 for account 42177. Durability is the promise and REDO is how a restarted server keeps it, which is why p. 193 files it under "recovery management". That slide is the one to learn as a table:

"Commit protocols" sit under atomicity because of the third setting of p. 145: when the two accounts live on two machines, both must commit or both must abort, and a protocol — two-phase commit is the classic one, background here — makes them agree. Lesson 5 shows what keeping machines in agreement costs once the network between them can fail.

Where ACID lives: OLTP, and why relational stayed

The definition slide calls a system that runs transactions "on behalf of multiple, concurrent applications" a Transactional System (OLTP), "As opposed to OLAP" (p. 146). OLTP is the bank counter: many short transactions like the transfer, each touching a few rows of current data. OLAP is the analyst: long read-only queries that scan and aggregate history, such as the average balance per branch over ten years. ACID was built for the first; the data warehouses of lesson 23 serve the second.

This is also the slides' answer to "Why didn't we change Relational?" (p. 205): it is "Consolidated", it is an "Integration platform" — the one database many applications share — and it is "Granting ACID properties!". Nothing in this half of the lesson is broken. What breaks is the size.

How big is big? Scaling up or scaling out

A slide of three lines (p. 158) sets the agenda: "How big is big?", "Not only scaling up", "Elasticity". The answer begins on p. 177 with two bullets in deliberate parallel:

Both degrade as data grows; only the remedy differs. Vertical scaling — scaling up — replaces the machine with a better one. Horizontal scaling — scaling out — adds a machine next to the ones you have. Fig. 4 is the picture to keep.

Vertical scaling has a cost curve (p. 178): cost against data size, rising through "commodity hardware", then "appliance", then "exceptional hardware", each segment steeper than the one before. The slides put numbers on the first two classes:

One appliance rack has 18 to 72 times the cores and 375 to 1,500 times the memory of one commodity server. On the slide's curve each class costs more per terabyte than the one below it, and after "exceptional hardware" there is nothing left to buy: the curve leaves the top of the chart.

Horizontal scaling (p. 181) is one straight line labelled “‘only more’ commodity hardware”: every further slice of data costs about one more cheap machine. The line does not start at zero; the slide leaves the gap unexplained, and the natural reading is the price of having a cluster at all — several machines, a network, the software and the people to run them.

Overlay the two (p. 182) and the chart splits: "Use vertically scalable solutions" on the left, where one machine is cheaper than any cluster; "Use horizontally scalable solutions" on the right, where the staircase has shot past the line. Around the crossing lies “The ‘grey area’” (p. 183), where neither is clearly cheaper and other reasons decide. The last slide of the set is the one to remember: “The ‘grey area’ is time dependent” (p. 184).

Page 184 draws four lines of horizontal scaling, one per generation of distributed platforms. "Hadoop 2.x using clusters on premises (2006)" crosses the staircase near 10 PB, "Hadoop 2.x using cloud-based services (2010)" near 1 PB, "Spark 1.6 using cloud-based service (2013)" near 100 TB, and "Spark on HDInsight (today)?" near 10 TB. Each generation made a cluster cheaper to start and cheaper per terabyte — rented in the cloud instead of bought, with better software on top — so the line sank and the crossing slid left by a factor of ten each time.

"How big is big?" has no fixed answer: big starts where many cheap machines cost less than one good one, and on p. 184 that threshold fell a thousandfold, from about 10 PB to about 10 TB.

"Not only scaling up" also points the other way: what scales out can scale back in. Elasticity — the slide names it without a definition; the meaning comes from cloud computing — is adding machines when the load grows and releasing them when it falls, so that cost follows load. It comes naturally to horizontal scaling, where a machine is a unit you can rent for a month; nobody hands back half an appliance.

Split it, copy it: partitioning and replication

Spreading data over many machines takes two moves, and a section title of the slides names both: partitioning and replication. Both start from "the traditional tabular view of a database" (p. 152), where a table can be cut by columns or by rows.

Vertical partitioning gives each piece a group of columns, with the key AccNum repeated so that rows can be joined back. Horizontal partitioning gives each piece a group of whole rows with the same columns — here the Milano accounts on one node and the Como accounts on the other. A rule decides which row goes where; later lessons call its input the shard key (MongoDB, lesson 16) and the partition key (Cassandra, lesson 21).

Partitioning — "Aim: scalability, distribution." — "splits the data in the database and partitions pieces of it to different storage nodes" (p. 153): one database of three layers A, B, C, an arrow "SPLIT", three separate databases. The same slide adds two sentences that pull in different directions: "Databases can be sharded horizontally (by rows) or vertically (by columns)" and "See also: Sharding (as horizontal partitioning)".

Replication — "Aim: fault-tolerance, backup" (p. 154) — copies instead of splitting: one database, an arrow "COPY", two identical databases. The sentence printed under the aim needs a correction.

"Partitioning + Replication — Possible?" asks p. 155, and its picture answers: copy the A/B/C database into two identical databases, then split each copy into A, B and C — six nodes, every piece on two of them. Splitting first and copying each piece gives the same layout, and real systems describe it that way: a number of shards, each stored a fixed number of times, its replication factor (the term of later lessons, not of these slides). Then the slides weigh the two moves (p. 156):

Every cell has a mechanism behind it. A partitioned node holds and serves only its piece, so the work spreads and each datum is stored once — but a dead node takes its piece with it. A replicated datum can be read from any copy and survives while one copy does — but every write must reach every copy, and \(N\) copies take \(N\) times the space. The sandbox shows both columns at once.

How much safer is "safer"? The slides stop at the table. A back-of-envelope model, not from the slides, gives numbers under one assumption: nodes fail independently, each with probability \(p\).

1. A shard is lost only if all \(N\) of its copies are on failed nodes. With independent failures: \[ P(\text{shard lost}) = p^N . \]

2. So a shard survives with probability \(1 - p^N\), and all \(k\) shards survive together — they sit on different nodes, so their fates are independent too — with \[ (1 - p^N)^k . \]

3. Losing something is the complement: \[ P(\text{data lost}) = 1 - (1 - p^N)^k . \]

4. Partitioning alone, \(N = 1\): \(1 - (1 - p)^k\) grows with \(k\), about \(k\) times \(p\). With \(p = 0.01\) and \(k = 3\) it is 2.97 %: more pieces, more ways to lose one — the table's "potential data loss".

5. Replication alone, \(k = 1\): \(p^N\) collapses, 0.01, then 0.0001, then 0.000001 for \(N\) = 1, 2, 3. Both, \(k = N = 3\): about 3 in a million, for three times the storage.

Independence is the assumption behind Bernoulli trials in statistics, and it is the weak point: a fire or a power cut takes a whole rack down at once. That is why the HDFS slides of lesson 31 put the "Second replica on a remote rack" (p. 857). And one cost is missing from the table altogether: the copies must agree. A write does not reach every copy at the same instant, so for a moment two copies of the same row can differ — remember that for the last section.

Getting data in: ingestion and wrangling

The "Data Architecture Concepts" deck closes its scaling section at the other end of the pipe (pp. 157–160, "Scale and Ingestion"): before data can be split and copied, it has to arrive and become usable. Data ingestion is "The process of importing, transferring and loading data for storage and later use"; "It involves loading data from a variety of sources" and "can involve altering and modification of individual files to fit into a format that optimizes the storage" (p. 159).

The slide's example is pure engineering: "in Big Data small files are concatenated to form files of 100s of MBs and large files are broken down in files of 100s of MB." Hundreds of megabytes is what the distributed file system of lesson 31 wants — "Typically 100MB or more per file", "Millions as opposed to billions of files" (p. 847) — because one server, the NameNode, holds the record of every file: "The entire metadata is in main memory" (p. 855). Around a "bus" that collects the sources, "Integration services" do "Transportation management, message routing, message brokering, transaction management, security, and transformation" — the top band of Fig. 6.

Data wrangling turns what arrived into something worth analysing: “cleansing ‘raw’ data” so that it "can be analysed to generate valid actionable insights", by "understanding, cleansing, augmenting and shaping data", with the result "in the best format (e.g., columnar) for the analysis to perform" (p. 160). The four boxes: understand which types of data there are (qualitative, quantitative, categorical), whether there are outliers, whether data is missing; cleanse — remove outliers, add missing values, transform quantitative values into categorical ones; augment — aggregate data within one source, add data from other sources by exact or fuzzy matches; shape — give the data the best format for the analysis.

If this sounds like the preprocessing done before training a neural network, it is — done once for a whole company and kept running as a pipeline. Lesson 4 places both bands in the architecture of a big-data system; lesson 33 opens the ingestion tools and lessons 35–37 the wrangling.

Back to the missing 10

Now the hook. Who has the extra 10 when the server comes back? Nobody. The power failed before commit work, so the log holds the credit and no commit record: the restart undoes the credit, 12202 is back to 100, and the two accounts hold 125 again. Had the power failed one line after the commit, the restart would redo both writes and the transfer would stand at 110 and 15, whatever had reached the disk. \(S_1\) is never an outcome and never on show — atomicity and isolation — and a committed outcome stays — durability.

Why, then, give up a machine that keeps such promises? Not because of the promises; because of the machine. Its staircase runs out, and the size at which a cluster wins kept falling, from about 10 PB to about 10 TB on p. 184. Beyond it the data is partitioned and replicated — and the hook's question comes back in a new form.

Which copy is right — and when 12202 and 42177 sit on different shards, who makes sure that both writes happen or neither? That is the third setting of p. 145, "Distributed systems". Lesson 5 takes up the first question: the CAP theorem, and the BASE properties that many distributed stores offer instead of ACID.