A Center for Sustainable Cloud Computing

Partitioning is the primary technique to deal with large data sets. Besides allowing for larger data sizes, partitioned systems improve latency and throughput by allowing concurrent access to data in different partitions. With current large main memory sizes, partitioning also makes it possible to keep all data in memory, further improving performance.

Snapshot isolation is a multi-version concurrency control scheme widely used by both commercial and open-source database systems, including Oracle RDBMS, Microsoft SQL Server, and PostgreSQL. Clock-SI provides attractive performance for read-heavy transactional workloads since, in contrast to several locking schemes (such as two-phase locking) read operations do not need to acquire locks, and therefore do not block writers or wait behind write locks.

Clock-SI is a new protocol for implementing snapshot isolation (SI) on partitioned data sets. In contrast to previous work, there is no centralized timestamp authority. Instead, snapshot and commit timestamps are derived from loosely synchronized physical clocks. In particular, snapshot timestamps are always assigned locally on the transaction’s originating partition.

By eliminating the centralized timestamp authority, Clock-SI avoids a single point of failure, and improves latency and throughput. These advantages come, however, with a challenge: a straightforward assignment of the current local clock value as a transaction’s snapshot timestamp may give that transaction a snapshot that is not yet fully available, for instance due to clock skew among machines. In such cases, an access to an unavailable part of the snapshot must be delayed. In order to

reduce this probability, the Clock-SI protocol allows the assignment of snapshot timestamps slightly older than the current clock value, trading freshness for improved latency.