K2: On Optimizing Distributed Transactions in a Multi-region Data Store with True-time Clocks

Download PDF

Abstract

TrueTime clocks (TTCs) that offer accurate and reliable time within limited uncertainty bounds have been increasingly implemented in many clouds. Multi-region data stores that seek decentralized synchronization for high performance represent an ideal application of TTC. However, the co-designs between the two often failed to realize their full potential. This paper proposes K2, a multi-region data store that explores the opportunity of using TTC for distributed transactions. Compared to its pioneer, Google Spanner, K2 augments TTC’s semantics in three core design pillars. First, K2 carries a new timestamp-generating scheme that is capable of providing a small time uncertainty bound at scale. Second, K2 revitalizes existing multi-version timestamp-ordered concurrency control to realize multi-version properties for read-write transactions. Third, K2 introduces a new TTC-based visibility control protocol that provides efficient reads at replicas. Our evaluation shows that, K2 achieves an order of magnitude higher transaction throughput relative to other geo-distributed transaction protocols while ensuring a lower visibility delay at asynchronous replicas.