CSE Roadmap

Core tier · about 3 hours · 6 parts

Part 3 of 6 · 5 min read

ACID, letter by letter

The four promises, and the honest meaning of each.

Think of four clauses in a contract for a delivery company: nothing is delivered half done, the goods match the order, other deliveries do not mix with yours, and once delivered the goods stay delivered. Each clause is a different promise.

The safety guarantees of transactions are described by the acronym ACID: atomicity, consistency, isolation, durability. It was coined in 1983 by Theo Härder and Andreas Reuter to give precise names to fault-tolerance mechanisms. The book warns that in practice one database's ACID is not another's. There is a lot of ambiguity, especially about isolation. "ACID compliant" has become mostly a marketing term. Systems that do not meet ACID are sometimes called BASE (basically available, soft state, eventual consistency), which the book calls even vaguer: the only sensible reading is "not ACID".

A: Atomicity. In multi-threaded programming, an atomic operation cannot be seen half done by another thread. In ACID, atomicity means something else. It is not about concurrency (that is isolation). It describes what happens if a client makes several writes and a fault strikes after some of them: a crash, a broken connection, a full disk, a violated constraint. The transaction aborts and the database discards every write it made so far. The application can be sure that nothing changed, so it can safely retry.

Atomicity (ACID)

Atomicity means all-or-nothing: if a transaction cannot complete, all of its writes are undone. The book suggests "abortability" would have been a better name.

Example: a transaction inserts an email and increases an unread counter. If the counter update fails, the inserted email is removed too.

C: Consistency. The word has at least four meanings in this book alone: replica consistency (eventual consistency, Level 4), consistent hashing (an approach to rebalancing), consistency in the CAP theorem (which means linearizability, module 6) and ACID consistency. In ACID it means that certain statements about your data, called invariants, are always true. In an accounting system, credits and debits across all accounts must balance. If a transaction starts from a valid state and keeps the invariants, the state is valid after. But the invariants are the application's. The database can check some, such as foreign keys and uniqueness, but it cannot know that "debits equal credits". The book concludes that atomicity, isolation and durability are properties of the database, while consistency is a property of the application, so the C does not really belong in ACID. It remarks that the C was "tossed in to make the acronym work".

Invariant

An invariant is a statement about the data that must always be true.

Example: the balances of all accounts add up to the total money in the bank. Or: no two bookings for one room overlap.

I: Isolation. Most databases have many clients at once. If they touch different data there is no problem. If they touch the same records, race conditions appear. The book's example: two clients increase a counter from 42. Each reads 42, adds 1 and writes 43. The result is 43, not 44. Isolation means concurrent transactions cannot step on each other. The textbook ideal is serializability: each transaction can pretend it is the only one running, and the result is the same as if they ran one after another. In practice that costs performance, and it is rarely used. Some databases do not provide it at all: the book notes that in Oracle 11g the level called "serializable" is actually snapshot isolation, which is weaker. Modules 2 and 3 cover this in detail.

D: Durability. Once a transaction commits, its data is not forgotten, even if hardware fails or the database crashes. On one node it usually means data written to non-volatile storage (a disk or SSD), normally with a write-ahead log for recovery (Level 2, module 4). In a replicated database it may mean the data reached some number of nodes, so the database must wait for that before reporting success.

The book is blunt that perfect durability does not exist. If all disks and all backups are destroyed together, nothing helps. Each technique has holes:

  • Writing to one disk: if the machine dies, data is safe but unreachable until the machine is fixed. Replicas stay available.
  • Replication: a fault that hits all replicas at once, such as a power failure or a bug triggered by one input, can lose data held only in memory.
  • Asynchronous replication: recent writes can be lost when the leader fails (Level 4, module 1).
  • SSDs can break their promises when power is cut, and even fsync is not always reliable. Disk firmware has bugs. Interactions between the storage engine and the file system can corrupt files after a crash.
  • Data can silently go bad on disk, and replicas and recent backups may carry the damage.
  • One study found 30 to 80 percent of SSDs develop at least one bad block in four years. A disconnected SSD can start to lose data within weeks.

The conclusion is that no single technique gives absolute guarantees. There are only risk-reduction techniques: write to disk, replicate to remote machines and keep backups, used together.

Letter Whose property Plain promise
Atomicity Database All of the writes happen or none
Consistency Application Invariants hold if the transaction keeps them
Isolation Database Concurrent transactions do not see each other's half-done work
Durability Database (with limits) Committed data survives crashes, to a degree

Check yourself:

  • Which letter of ACID is really a property of the application?
  • Why does atomicity in ACID differ from atomic in multi-threaded code?