Snapshot Isolation (SI) is a widely adopted concurrency control mechanism in database systems, which utilizes timestamps to resolve conflicts between transactions. However, centralized allocation of timestamps is a potential bottleneck for parallel transaction management. This bottleneck is becoming increasingly visible with the rapidly growing degree of parallelism of today's computing platforms. This paper introduces Posterior Snapshot Isolation (PostSI), an SI mechanism that allows transactions to determine their timestamps autonomously, without relying on centralized coordination. As such, PostSI can scale well, rendering it suitable for various multi-core and MPP platforms. Extensive experiments are conducted to demonstrate its advantage over existing approaches.
To avoid using a central clock, another viable approach is to use synchronized distributed physical clocks (a.k.a. true time devices). A typical example is Spanner @cite_17 , a distributed database system developed by Google. Spanner utilizes GPS clocks and atomic clocks to constraint the deviation among different physical clocks within a small error bound. It then builds its concurrency control mechanism upon the timestamps generated by the true time devices. However, as GPS clocks and atomic clocks are not common hardware, the approach of Spanner does not seem to be widely applicable. Instead of using hardware of high accuracy, Clock-SI @cite_16 resorts to an algorithmic approach that derives timestamps from loosely synchronized physical clocks. Loose clock synchronization @cite_6 would unavoidably result in skew of time. To deal with time skew, Clock-SI has to let a node falling behind to see only old data snapshots or to force an ahead node to wait for a behind node. This makes Clock-SI unstable, as enlarged clock skew will result in severe performance loss. ViCC chooses not to deal with synchronized physical clocks.
@cite_16 @cite_6 @cite_17
2147806092 2110026634
Clock-SI is a fully distributed protocol that implements snapshot isolation (SI) for partitioned data stores. It derives snapshot and commit timestamps from loosely synchronized clocks, rather than from a centralized timestamp authority as used in current systems. A transaction obtains its snapshot timestamp by reading the clock at its originating partition and Clock-SI provides the corresponding consistent snapshot across all the partitions. In contrast to using a centralized timestamp authority, Clock-SI has availability and performance benefits: It avoids a single point of failure and a potential performance bottleneck, and improves transaction latency and throughput. We develop an analytical model to study the trade-offs introduced by Clock-SI among snapshot age, delay probabilities of transactions, and abort rates of update transactions. We verify the model predictions using a system implementation. Furthermore, we demonstrate the performance benefits of Clock-SI experimentally using a micro-benchmark and an application-level benchmark on a partitioned key-value store. For short read-only transactions, Clock-SI improves latency and throughput by 50 by avoiding communications with a centralized timestamp authority. With a geographically partitioned data store, Clock-SI reduces transaction latency by more than 100 milliseconds. Moreover, the performance benefits of Clock-SI come with higher availability. This paper describes an efficient optimistic concurrency control scheme for use in distributed database systems in which objects are cached and manipulated at client machines while persistent storage and transactional support are provided by servers. The scheme provides both serializability and external consistency for committed transactions; it uses loosely synchronized clocks to achieve global serialization. It stores only a single version of each object, and avoids maintaining any concurrency control information on a per-object basis; instead, it tracks recent invalidations on a per-client basis, an approach that has low in-memory space overhead and no per-object disk overhead. In addition to its low space overheads, the scheme also performs well. The paper presents a simulation study that compares the scheme to adaptive callback locking, the best concurrency control scheme for client-server object-oriented database systems studied to date. The study shows that our scheme outperforms adaptive callback locking for low to moderate contention workloads, and scales better with the number of clients. For high contention workloads, optimism can result in a high abort rate; the scheme presented here is a first step toward a hybrid scheme that we expect to perform well across the full range of workloads.