Where's the Next 100x?
Concept. Choose the next optimization by measuring contention, I/O, and coordination costs. Finer-grained locks, LSM storage, and timestamp ordering address different costs. They can be combined; none guarantees a fixed speedup.
Intuition. Updates to separate fields may benefit from smaller locks. A stream of listening events benefits from batching writes. Transactions that conflict still need a concurrency-control rule.
Figure: Where could the next 100× come from?Three separately revealed design choices. Performance depends on the workload; no fixed speedup is guaranteed.
Figure 1. Choose the change that addresses the measured bottleneck. Improving Strict 2PL and choosing another protocol are both options.
The Opportunity Space
Strict 2PL accepts a subset of conflict-serializable schedules, which are a subset of serializable schedules. Other protocols can admit different schedules, but the larger set alone does not tell us the performance gain.
Figure: Nested hierarchy: every S2PL schedule is a 2PL schedule, every 2PL schedule is conflict-serializable, every conflict-serializable schedule is serializableNested hierarchy: every S2PL schedule is a 2PL schedule, every 2PL schedule is conflict-serializable, every conflict-serializable schedule is serializable
Figure 2. Serializability is the correctness target. A scheduling rule may be more restrictive to make correctness practical to enforce.
Match the Protocol to the Workload
Figure: Match the workload to the mechanismThree neutral rows compare finer-grained locks, LSM storage and timestamp ordering. Violet identifies the approach. These are mechanisms that can be combined, not interchangeable guarantees.
Figure 3. These mechanisms solve different problems. LSM storage does not replace transaction concurrency control.
-
Many users update independent fields. Smaller locks can reduce unnecessary blocking. Updates to the same counter still serialize; changing the lock size does not remove that conflict.
-
A song receives 10M plays in an hour. An LSM tree buffers events, flushes sorted files, and compacts them later. The trade-off is extra work during reads and compaction, not necessarily delayed visibility. Transactional updates still need coordination.
-
Transactions must respect a timestamp order. A basic timestamp-ordering protocol rejects operations that violate the order. Retrying aborted transactions is part of the cost.
Real systems combine mechanisms. RocksDB supports both optimistic and pessimistic transactions; Spanner combines timestamps with concurrency control.
The Next Machine
Figure: Scale the workload. Preserve correctness.Three separately revealed design choices. Performance depends on the workload; no fixed speedup is guaranteed.
Figure 4. Distributed systems add communication and partial failures to the same correctness and performance questions.