Impossible read and write isolation phenomena with Cloud Spanner

Introduction

Cloud Spanner offers the strictest concurrency-control with external consistency. This guarantees for multiple transactions to run concurrently without the possibility of inconsistencies.

In this article, I’m going to demonstrate how the following 6 transaction isolation phenomenon aren’t allowed in Cloud Spanner.

  1. Dirty Reads
  2. Lost Updates
  3. Non-repeatable Reads
  4. Phantom Reads
  5. Read Skew
  6. Write Skew

Testing tool

We’re going to use the interactive CLI tool called spanner-cli to run multiple transactions. With spanner-cli we can interactively run arbitrary SQL statements similar to using the mysql command.

You can find the source code on GitHub at https://github.com/yfuruyama/spanner-cli

  1. Preparing the database for our tests:
$ spanner-cli -p $PROJECT -i $INSTANCE -d $DATABASE

2. Copying and pasting the following DML and DDL on your CLI session.

CREATE TABLE Accounts (
UserId INT64 NOT NULL,
Balance INT64 NOT NULL,
Type STRING(16) NOT NULL
) PRIMARY KEY (UserId);

CREATE TABLE Counters (
Id INT64 NOT NULL,
Value Int64 NOT NULL
) PRIMARY KEY (Id);

INSERT INTO Accounts (UserId, Balance, Type) VALUES (1, 1000, 'Checking'), (2, 1000, 'Checking'), (3, 1000, 'Checking');
INSERT INTO Counters (Id, Value) VALUES (1, 0);

Let’s open two terminal consoles and connect to our Cloud Spanner database with spanner-cli.

1. Dirty Reads

First we are going to demonstrate that dirty reads aren’t allowed in Cloud Spanner. Dirty reads happen in a situation where one transaction can read uncommitted records which are being modified by another transaction. This could happen in relational databases that permit the READ UNCOMMITTED isolation level.

In the following example, we show while tx1 is changing the Balance to 2000, tx2 can only read the original value, 1000, until tx1 commits.

https://gist.github.com/yfuruyama/1d24d503ab0dfa1f16e0c2e62a479c4e

In Cloud Spanner, all mutations performed using DML (INSERT / UPDATE / DELETE) statements are buffered on the server-side, and those mutations aren’t applied to the records unless they are committed.

2. Lost Updates

Lost Update describes the situation where a modification in one transaction is overwritten by another transaction, which results in the original modification to disappear.

Let’s take incrementing a counter as an example.

  1. Getting the current_value of the counter
  2. Updating the counter with current_value + 1

If two transactions execute the above operations after each other, we expect the final result to be old_counter_value+2. However if operation #1 happens simultaneously in both transactions, and both transactions commit successfully the final result would be old_counter_value+1 because the last transaction committed wins.

Let’s check that lost updates don’t happen in Cloud Spanner.

https://gist.github.com/yfuruyama/a2fef5cfabf7f94b8c4869943783242d

You can see that tx1 was able to commit successfully, but tx2 was aborted at the commit. This is because the deadlock prevention mechanism called wound-wait has been invoked at that moment which aborts the younger transaction and lets the older transaction succeed.

During read-write transactions, Cloud Spanner tries to acquire a shared read lock on the record to be read and tries to acquire an exclusive lock on the record during the update (write). To acquire an exclusive lock on the record, no shared lock is allowed to be held by any other transaction. If one transaction has already acquired a shared lock on the record and another transaction needs an exclusive lock on the same record, Cloud Spanner compares the transaction timestamps and aborts the younger transaction to grant the exclusive lock to the older transaction.

In the above example, although both tx1 and tx2 have a shared lock on the record, since tx1 has run the SELECT statement earlier (at that time transaction age timestamp is acquired), Cloud Spanner aborts tx2 to get the exclusive lock for tx1.

In some RDBMS, such as MySQL, it’s common to prevent lost updates by explicitly locking records with Locking Reads (SELECT FOR UPDATE).

Note: Aborted transactions are automatically retried in all Google maintained client libraries (ex. Go client). If you’re doing non-Spanner operations in Cloud Spanner transactions, it’s a good practice to make entire function idempotent to ensure side effects won’t appear.

3. Non-repeatable Reads

Non-repeatable Reads happen where repeated reads on the same record in one transaction result in different returned values from the database. This could happen in relational databases that permit the READ COMMITTED isolation level.

Let’s check that non-repeatable reads don’t happen in Cloud Spanner. In this demonstration tx1 is trying to read a record multiple times and tx2 writes the record with new value during the multiple reads.

https://gist.github.com/yfuruyama/3a5668cc1322dc5ed2f1ee5f59d07dcd

In the above scenario, since tx1 has acquired a shared lock on the record before tx2 acquires the exclusive lock, tx2 has to wait to get the exclusive lock until tx1 releases the shared lock. Therefore, tx2 has been blocked until tx1 commits or aborts the transaction.

This is where read-only transactions come into play. In read-only transactions only SELECT statements are allowed which do not block read-write transactions because they do not acquire any locks.

Let’s look at what happens if tx1 uses a read-only transaction. You can run read-only transactions in spanner-cli by using the BEGIN RO statement.

https://gist.github.com/yfuruyama/2ec4e05c7ed54aae787cbbc52fdd8271

As you can see, tx1 has read the same value both before and after tx2 updates the record. Non-repeatable reads have not occurred.

Read-only transactions get a consistent view of the database with the execution timestamp of the first SELECT statement. All subsequent queries will read data at the transaction timestamp. This is made possible by TrueTime and Cloud Spanner using append-only storage which allows for consistent view of the past.

4. Phantom Reads

Phantom reads describe the situation where result sets of repeated reads in a transaction change when another transaction inserts a new record that qualifies for the read query.

Let’s say, there are three records (UserID=1~3) and a transaction is executing the query SELECT * FROM Accounts WHERE UserId >=1 && UserId <= 10 repeatedly. In that situation, if another transaction inserts a new record (UserId=4), it causes the first transaction to read a new phantom record.

Lets see how Cloud Spanner doesn’t allow phantom reads. First, let’s look at what happens if we use read-write transactions.

https://gist.github.com/yfuruyama/cba2b942c89fc00d228511a01d3336d1

Similar to the case of non-repeatable reads, tx2 blocks at the commit. This shows that not only the records between UserID=1~3 which meet the WHERE condition, but also the records between UserId=4~10 are included in the shared lock. This is similar to the Gap Lock mechanism in MySQL.

If tx1 uses a read-only transaction tx2 can commit successfully and no phantom reads happen in tx1.

https://gist.github.com/yfuruyama/3ac84e0c5d2a3a7a02cf8738b24e35ca

5. Read Skew

Read Skew is situation where one transaction is reading multiple records, and at the same time another transaction updates one of the records, which results in non-serializable transactions since the 2nd transaction is interleaved in the first transaction.

This is similar to non-repeatable reads, but in contrast read skew refers to the conflict of interleaving multiple transactions when reading multiple different records.

Let’s imagine the following scenario. We have two accounts and both accounts have a balance of 1000. There are two transactions running, one of the transactions reads the balance of both accounts and the other transaction updates them in an interleaved way. In this scenario, if the transaction performing SELECT statements gets the Balance=1000 for the first account and gets the Balance=1500 for 2nd account, it is considered an inconsistent read.

Let’s check read skew doesn’t happen in Cloud Spanner. The following example shows the situation where tx1 reads records of UserId=1 and UserId=2, while tx2 updates both records.

https://gist.github.com/yfuruyama/68b8f166ffba273c665482832cf9fc2e

As you can see, tx1 got consistent reads without being affected by tx2. Note that tx1 used a read-only transaction to not block updates in tx2.

6. Write Skew

Write skew happens where two transactions are running concurrently and trying to update different records upon reading the same records, which results in inconsistent writes.

For example, given that there is a certain rule on the Accounts table: At most only one record has Type=Saving. With that rule, if two transactions execute following operations concurrently,

  1. Check the current number of saving accounts by SELECT COUNT(*) FROM Accounts WHERE type = “Saving”;
  2. If the number of saving accounts is zero, change one of the records to the saving account.

then it could be possible for both transactions to be executed simultaneously, as a result two accounts are changed to saving accounts. This breaks the rule.

Let’s check write skew doesn’t happen in Cloud Spanner for the above scenario.

https://gist.github.com/yfuruyama/4516fe4c9b94c1ceae34f8332dc4f5cd

As you can see, while tx1 succeeded to commit, tx2 was aborted at commit phase. The reason for this is that tx1 tried to acquire the exclusive lock, but the shared lock for the record has been acquired by tx2, so Cloud Spanner aborted tx2 to acquire the exclusive lock for tx1. As a result, only one transactions could commit successfully.

Summary

As seen, Cloud Spanner doesn’t allow any of the above isolation phenomena by providing only the highest level of transaction isolation with external consistency.

  • Thank you to @hostirosti for helping me write this article!