Lightweight Locking for Main Memory Database Systems
📜 Abstract
Locking is widely used as a concurrency control mechanism in database systems. As more OLTP databases are stored mostly or entirely in memory, transactional throughput is less and less limited by disk IO, and lock managers increasingly become performance bottlenecks. In this paper, we introduce very lightweight locking (VLL), an alternative approach to pessimistic concurrency control for main-memory database systems that avoids almost all overhead associated with traditional lock manager operations. We also propose a protocol called selective contention analysis (SCA), which enables systems implementing VLL to achieve high transactional throughput under high contention workloads. We implement these protocols both in a traditional single-machine multi-core database server setting and in a distributed database where data is partitioned across many commodity machines in a shared-nothing cluster. Our experiments show that VLL dramatically reduces locking overhead and thereby increases transactional throughput in both settings.
✨ Summary
Main contribution
The paper proposes very lightweight locking (VLL) for main-memory database systems. Instead of maintaining a centralized hash table containing per-record lock queues, VLL stores two counters with each record: one for exclusive-lock requests and one for shared-lock requests. Transactions request their complete read and write sets atomically, and a partition-local transaction queue determines execution order and prevents deadlock.
VLL substantially reduces lock-management work by avoiding linked-list operations, lock-table lookups, and much of the associated latching and cache-miss overhead. Its principal limitation is that the compact counters do not preserve enough dependency information to identify every transaction that could safely run. Selective contention analysis (SCA) addresses this limitation by reconstructing relevant conflicts only when the system would otherwise be idle or unable to make progress.
The evaluation reports approximately 2% locking overhead for VLL versus approximately 21% for traditional two-phase locking at low contention. Isolated per-transaction locking costs were reported as 20.13 microseconds for traditional 2PL, 20.16 microseconds for deterministic Calvin locking, 1.8 microseconds for multi-threaded VLL, and 0.71 microseconds for single-threaded VLL. Under workloads permitting deadlocks, VLL with SCA exceeded traditional 2PL by at least 163% in most tested cases and by as much as 18× at extreme contention. In distributed experiments, VLL with SCA achieved similar scalability to Calvin, outperformed Calvin by up to 33% in some low-contention configurations, and substantially outperformed serial H-Store-style execution as multi-partition transactions increased.
Subsequent influence
The work was extended into a 2015 VLDB Journal article, which generalized VLL and SCA to range locking through the VLLR design. (vldb.org) A later 2021 study on dependence-cognizant locking explicitly builds on VLL and SCA, implements its alternative locking design in Calvin, and evaluates it against VLL/SCA in multicore and shared-nothing database settings. (onlinelibrary.wiley.com) The available evidence indicates continued academic follow-up and algorithmic extensions; the search did not identify a clearly documented commercial database product adoption of VLL itself.