MyDistributed.Systems

Amazon DynamoDB uses a lightweight transaction protocol via timestamp ordering. Although both Spanner and DynamoDB use timestamps in their transaction protocol, DynamoDB seems significantly simpler than Spanner; while Spanner uses 2PL and MVCC and needs TrueTime, DynamoDB only relies on timestamp ordering and does not use any locking or MVCC scheme. In this post, we want to review the DynamoDB transaction protocol and compare it with Google Spanner. 

As we covered in this earlier post , serializability means that the database should appear to run transactions in some sequential order. In other words, although we might run transactions concurrently, to the clients, it should appear we are running transactions one-at-a-time. This definition seems clear, but how can we precisely prove that a given transactional system is serializable? The problem is the word "appear" in this definition; what do we formally mean by that? In this post, we see how we can prove the serializability of a transactional system. After covering some definitions, we will see how we can prove serializability of one of the transactional databases that we covered in this blog--  FoundationDB .  Serializability, Conflict-serializability, and Precedence Graph The following definitions and theorems are from [1-2].  Definition 1 (Schedule): a sequence of (important) steps taken by one or more transactions.  In concurrency control, the important ste...

Calvin is a transaction scheduling and replication protocol that provides distributed ACID transactions for partitioned and replicated systems. In its heart, Calvin relies on a locking mechanism that unlike 2PL is deterministic. This determinism removes the need for an atomic commit protocol (e.g. 2PC) which leads to a significantly smaller contention footprint of distributed transactions.

FoundationDB is an open-source database that provides distributed ACID transactions. In this post, we will see how FoundationDB uses optimistic and multi-version concurrency control techniques to provide strictly serializable distributed transactions. 

Spanner provides strictly serializable distributed transactions on a global scale. Spanner was introduced in 2012, and today, it is available as a managed service called Cloud Spanner via Google Cloud Platform. CockroachDB and YugaByteDB are two open-source products based on Spanner. In this post, we see how Spanner provides strictly serializable distributed transactions while being a replicated and partitioned database.  

Serializability is the strongest isolation level that a transactional system can offer. This level of isolation removes all possible anomalies due to concurrently running transactions. It provides a powerful abstraction for application developers. The letter "I" in ACID, stands for isolation, and when people talk about ACID transactions, they most likely mean serializable transactions. However, note that many systems that claim to provide ACID transactions, in reality, provide weaker isolation levels. In this post, we want to review serializability and see how a database system can provide serializability for single-node and distributed transactions.