The assumption being dropped
- Previous lectures on B+ trees, hash tables, skip lists, inverted indexes, vector indexes and Bloom filters assumed the data structure was single-threaded, purely to simplify the discussion
3:35. - Real systems need multiple workers (threads or processes) mutating the structure simultaneously without breaking it
4:08. - Motivation: exploit many-core CPUs, and when one thread stalls on disk or network, let others keep running to hide the stall
4:36.
The counter-argument: don't do any of this
- There's a class of systems that skips latching entirely, on the argument that latching protocols only add overhead and running one thread at a time gets you bare-metal speed
4:585:19. - Examples given:
- Redis — single process, single thread; only one query can touch the database at a time, so no latches are needed
5:19. - VoltDB — takes it to the extreme; based on H-Store, which the lecturer helped build
5:46. - kdb (KX) — ubiquitous on Wall Street, uses its own K language rather than SQL; core engine is single-threaded
5:46.
- Redis — single process, single thread; only one query can touch the database at a time, so no latches are needed
Concurrency control protocol
- Think of it as the traffic cop inside the DBMS: it decides which worker may read which data, when, and in what way, to protect a shared object
6:26.
Two notions of correctness
| Notion | Question it answers | Covered where |
|---|---|---|
| Logical correctness | Can my thread see the data it is supposed to see? (e.g. I inserted key 5 — will my read find it, or did someone delete it first?) | After the midterm, with transactions 6:44 |
| Physical correctness | Is the internal representation sound? Does a page pointer lead somewhere real? | This lecture 7:15 |