Serializable Snapshot Isolation in Shared-Nothing, Distributed Database Management Systems

NoSQL data storage systems provide high scalability and availability in exchange for limited transactional guarantees. In many cases, however, an application cannot give up transactional support but still needs the scalability provided by such systems. One approach for overcoming this limitation is to implement Snapshot Isolation (SI) on top of these systems. SI prevents most non-serializable executions and its optimistic concurrency control never delays read-only transactions. Nevertheless SI does not guarantee the serializability that many applications require. For example, the “write anomaly ” is a well-known problem permitted by SI that violates data consistency [4]. This problem occurs when two or more concurrent transactions update a data item that the other reads. To resolve this problem, we present a new commit algorithm to ensure serializable SI in a large-scale distributed system. The algorithm takes a pessimistic approach to detect and avoid non-serializable execution schedules. We also include a performance study that demonstrates both the correctness and scalability of our new algorithm. 1