Metadata

This paper (SIGMOD '08) proposes a lightweight runtime technique to make Snapshot Isolation (SI) serializable without falling back to locking. The key idea behind Serializable SI (SSI) is to detect potentially dangerous (write-skew) executions at runtime and abort one of the transactions to guarantee serializability (SER). The goal is to offer the strong guarantees of SER without sacrificing SI's high performance and non-blocking reads. But would it make sense to implement SER by layering on MVCC SI instead of implementing it directly? Do you think an SI-based implementation would be more performant than native 2PL-based SER implementations? What about compared to OCC-based SER? The evaluation section gives some answers. The problem and insight Let's back up. Write-skew is the canonical anomaly under SI. And the canonical example for write-skew is the "doctors on-call" scenario. Consider two doctors removing themselves from a duty roster. Each transaction checks ...

ATC and OSDI ran in parallel. As is tradition, OSDI was single-track ; ATC had two parallel tracks . The schedules and papers are online as linked above. USENIX is awesome: it has been open access for its conference proceedings since 2008. So you can access all the paper pdfs through the links above now. I believe the presentation videos will be made available soon as well. Kudos to USENIX! I attended the OSDI opening remarks delivered by the PC chairs, Lidong Zhou (Microsoft) and Yuan Yuan Zhou (UCSD). OSDI saw 339 submissions this year, which is up 20% from last year. Of those, 53 were accepted, for an acceptance rate of 16%. The TPC worked through Christmas to keep the publication machine running. We really are a bunch of workaholics. Who needs family time when you have rebuttals to respond to? OSDI gave two best paper awards: Basilisk: Using Provenance Invariants to Automate Proofs of Undecidable Protocols. Tony Nuda Zhang and Keshav Singh, University of Michigan; Tej Chajed, Unive...

This week I was in Boston for ATC/OSDI’25. Downtown Boston is a unique place where two/three-hundred-year-old homes and cobblestone streets are mixed with sleek buildings and biotech towers. The people here look wicked smart and ambitious (although lacking the optimism/cheer of Bay area people). It’s a sharp contrast from Buffalo, where the ambition is more about not standing out. Boston was burning. 90°F and humid. I made the mistake of booking late, so I got the DoubleTree Boston-Downtown instead of the conference hotel. The mile-long walk to the Sheraton felt like a hike through a sauna. By the time I got there, my undershirt was soaked, and stuck to my back cold under the conference hall’s AC.  Jane Street's fitted t-shirt swag saved the day. The Sheraton looked ragged from the outside, aged on the inside, but it was functional. The conference felt underfilled, with many empty seats. Later, I learned that the total ATC+OSDI attendance was under 500. That's a big drop from e...

Chapter 7 of the Concurrency Control and Recovery in Database Systems book by Bernstein and Hadzilacos (1987) tackles the distributed commit problem: ensuring atomic commit across a set of distributed sites that may fail independently. The chapter covers these concepts: The challenges of transaction processing in distributed database systems (which wasn't around in 1987) Failure models (site and communication) and timeout-based detection The definition and guarantees of Atomic Commitment Protocols (ACPs) The Two-Phase Commit (2PC) protocol (and its cooperative termination variant) The limitations of 2PC (especially blocking) Introduction and advantages of the Three-Phase Commit (3PC) protocol Despite its rigor and methodical development, the chapter feels like a suspense movie today. We, the readers, equipped with modern tools like FLP impossibility result and Paxos protocol watch as the authors try to navigate a minefield, unaware of the lurking impossibility results that were pu...

So it goes: your system is purring like a tiger, devouring requests, until, without warning, it slumps into existential dread. Not a crash. Not a bang. A quiet, self-sustaining collapse. The system doesn’t stop. It just refuses to get better. Metastable failure is what happens when the feedback loops in the system go feral. Retries pile up, queues overflow, recovery stalls. Everything runs but nothing improves. The system is busy and useless. In an earlier post, I reviewed the excellent OSDI ’22 paper on metastable failures , which dissected real-world incidents and laid the theoretical groundwork. If you haven’t read that one, start there. This HotOS ’25 paper picks up the thread. It introduces tooling and a simulation framework to help engineers identify potential metastable failure modes before disaster strikes. It’s early stage work. A short paper. But a promising start. Let’s walk through it. Introduction Like most great tragedies, metastable failure doesn't begin with villain...

With Chapter 6, the Concurrency Control and Recovery in Database Systems book shifts focus from concurrency control to the recovery! This chapter addresses how to preserve the atomicity and durability of transactions in the presence of failures, and how to restore the system to a consistent state afterward. The book offers a remarkably complete foundation for transactional recovery, covering undo/redo logging, checkpointing, and crash recovery. While it doesn't use the phrase "write-ahead logging", the basic concepts are there, including log-before-data and dual-pass recovery. When the book was written, the full WAL abstraction in ARIES was still to come in another five years at 1992 ( see my review here ). I revisit this discussion/comparison at the end of the post. System Model and Architecture In earlier chapters, we had reviewed the architecture: transactions pass through a transaction manager (TM), which sends operations to a scheduler and then to a data manager (DM...

Chapter 5 of Concurrency Control and Recovery in Database Systems (1987) introduces multiversion concurrency control (MVCC), a fundamental advance over single-version techniques. Instead of overwriting data, each write operation creates a new version of the data item. Readers can access older committed versions without blocking concurrent writes or being blocked by concurrent writes. MVCC removes read-write conflicts and increases concurrency significantly. Having multiple versions around gives the scheduler flexibility: if a read arrives "too late" to see the latest write, it can still proceed by accessing an older version. This avoids unnecessary aborts. Writes may still abort due to write-write conflicts, but reads are largely unimpeded. This is especially beneficial in read-heavy workloads. This chapter presents three broad classes of multiversion methods: Multiversion Timestamp Ordering (MVTO), Multiversion Two-Phase Locking (MV2PL), and Multiversion Mixed Methods. For ...

Chapter 4 of the Concurrency Control and Recovery in Database Systems book (1987) opens with a sentence that doesn't quite pass the grammar test: "In this chapter we will examine two scheduling techniques that do not use locks, timestamp ordering (TO) and serialization graph testing (SGT)."  That comma is trying to do the job of a colon and failing at it. Precision matters, more so in technical writing. The writing is otherwise clear and careful. And as par the book, it is ahead of its time. The chapter presents a spectrum of non-locking schedulers, starting from Basic TO, expanding into certifiers (which basically stands for optimistic concurrency control), and ending with modular, composable scheduler designs that separate synchronization concerns cleanly between read-write and write-write synchronization.  Let's dig into the details. Timestamp Ordering (TO) Timestamp Ordering (TO) uses transaction start timestamps to impose a serial order on conflicting operations...

Chapter 3 presents two-phase locking (2PL). Remember I told you in Chapter 2: Serializability Theory that the discussion is very scheduler-centric? Well, this is a deeper dive into the scheduler, using 2PL as the concurrency control mechanism. The chapter examines the design trade-offs in scheduler behavior, proves the correctness of basic 2PL, dissects how deadlocks arise and are handled, and discusses many variations and implementation issues. Here are the section headings in Chapter 3. Aggressive and Conservative Schedulers Basic Two Phase Locking Correctness of Basic Two Phase Locking Deadlocks Variations of Two Phase Locking Implementation Issues The Phantom Problem Locking Additional Operators Multigranularity Locking Distributed Two Phase Locking Distributed Deadlocks Locking Performance Tree Locking Yep, this is a long chapter: 65 pages.  3.1 Aggressive and Conservative Schedulers The chapter opens by asking: how aggressive or conservative should a scheduler be? An aggress...