Alice and Bob want to go to the cinema together and sit next to each other. However, each will book their seat. Will they be able to book two adjacent seats?
Let's run that in two Distributed SQL databases:
- PostgreSQL-compatible behavior (YugabyteDB)
- Optimistic Concurrency Control (Aurora DSQL)
I created the following table to book seats, identified by the row and seat number:
create table seats (
seat_row char, -- row of the seat in the theater
seat_number int, -- number of the seat in the row
booked_by text, -- null if seat is free, or the name if booked
primary key (seat_row, seat_number),
unique (booked_by)
);
Carol, Carlos, Charlie, and Oscar are already booked, but seats A-2, A-4, and A-5 remain available:
insert into seats (seat_row, seat_number, booked_by) values
('A', 1, 'Carol' ),
('A', 2, null ),
('A', 3, 'Oscar' ),
('A', 4, null ),
('A', 5, null ),
('A', 6, 'Carlos' ),
('A', 7, 'Charlie')
;
Here are fully reproducible tests that I've run on YugabyteDB (open-source multi-cloud distributed SQL) and Aurora DSQL (AWS serverless distributed SQL in preview) on the same multi-region configuration.
PostgreSQL-compatible on YugabyteDB
Here is the initial state:
yugabyte=# select * from seats order by seat_row, seat_number
;
seat_row | seat_number | booked_by
----------+-------------+-----------
A | 1 | Carol
A | 2 |
A | 3 | Oscar
A | 4 |
A | 5 |
A | 6 | Carlos
A | 7 | Charlie
(7 rows)
Bob starts a transaction:
yugabyte=# begin transaction;
BEGIN
Bob checks for two adjacent seats that are free:
yugabyte=*# select seat_row, seat_number, next_seat_number
from (
select seat_row, seat_number, booked_by
, lead(seat_number) over row_seats as next_seat_number
, lead(booked_by ) over row_seats as next_booked_by
from seats
window row_seats as (partition by seat_row order by seat_number)
) seats_with_next
where booked_by is null and next_booked_by is null
;
seat_row | seat_number | next_seat_number
----------+-------------+------------------
A | 4 | 5
(1 row)
Bob is happy. He verifies that his seat is still free, intending to reserve it if Alice can book the other seat. A SELECT FOR UPDATE declares to the database the intent to update:
yugabyte=*# select * from seats
where (seat_row, seat_number)=('A', 4)
for update
;
seat_row | seat_number | booked_by
----------+-------------+-----------
A | 4 |
(1 row)
Bob calls Alice and tells her to book seat A-5.
Alice starts a transaction:
yugabyte=# begin transaction;
BEGIN
Alice verifies that the seat is still free, intending to reserve it:
yugabyte=*# select * from seats
where (seat_row, seat_number)=('A', 5)
for update
;
seat_row | seat_number | booked_by
----------+-------------+-----------
A | 5 |
(1 row)
Great, the seat is still free. Alice confirms to Bob that she can reserve it. She declared the intent with a SELECT FOR UPDATE.
During this time, other people may try to book a seat. Mallory checks for available seats, and because the others have not committed yet, he sees three available seats:
yugabyte=# select * from seats where booked_by is null;
;
seat_row | seat_number | booked_by
----------+-------------+-----------
A | 2 |
A | 4 |
A | 5 |
(3 rows)
Mallory picks one of those seats, A-4, and tries to book it:
yugabyte=# update seats set booked_by='Mallory'
where (seat_row, seat_number)=('A', 4)
and booked_by is null
;
...
Mallory is waiting because a SELECT FOR UPDATE needs to acquire a row lock, and this intent conflicts with the same intent from Bob. He cannot progress until the outcome of the other transaction is known.
Bob and Alice were unaware of this and just continued. As long as their transaction does not time out, what they have read with SELECT FOR UPDATE remains valid, and they can perform the update.
Bob books his seat:
yugabyte=*# update seats set booked_by='Bob'
where (seat_row, seat_number)=('A', 4)
and booked_by is null
;
UPDATE 1
Alice books her seat:
yugabyte=*# update seats set booked_by='Alice'
where (seat_row, seat_number)=('A', 5)
and booked_by is null
;
UPDATE 1
What Alice and Bob did is similar to the the first phase of a Two-Phase Commit. They prepared their booking, checking that everything looked good. They found two free seats near each other and were able to book them. They can COMMIT.
Alice commits:
yugabyte=*# commit;
COMMIT
Bob commits:
yugabyte=*# commit;
COMMIT
In the meantime, if Mallory's session doesn't time out, it will continue automatically, as Bob's commit has released the lock.
Mallory is informed that he wasn't able to book the seat because it didn't verify booked_by is null, and by consequence, no rows were updated:
yugabyte=# update seats set booked_by='Mallory'
where (seat_row, seat_number)=('A', 4)
and booked_by is null
;
UPDATE 0
All transactions are completed, and here is the final state:
yugabyte=# select * from seats order by seat_row, seat_number
;
seat_row | seat_number | booked_by
----------+-------------+-----------
A | 1 | Carol
A | 2 |
A | 3 | Oscar
A | 4 | Bob
A | 5 | Alice
A | 6 | Carlos
A | 7 | Charlie
(7 rows)
Alice and Bob will go to the movies, and they can sit together. Mallory will be able to book another seat.
Pessimistic Concurrency Control makes everyone happy and limited the frustration.
Optimistic Concurrency Control on Aurora DSQL
There are not many SQL databases using Optimistic Concurrency Control, but the latest AWS announcement includes one of them: Aurora DSQL.
This database is designed for use cases with minimal conflicts. Contrary to other databases that try to detect errors beforehand and make the commit fast with a high probability of success, Optimistic Concurrency Control defers all ACID enforcement to the COMMIT command and returns an OC000 error (with error code 40001 Serialization Failure) if any previous operation in the transaction is not compatible with the current state of the database.
Here is the initial state:
dsql=> select * from seats order by seat_row, seat_number
;
seat_row | seat_number | booked_by
----------+-------------+-----------
A | 1 | Carol
A | 2 |
A | 3 | Oscar
A | 4 |
A | 5 |
A | 6 | Carlos
A | 7 | Charlie
(7 rows)
Bob starts a transaction:
dsql=> begin transaction;
BEGIN
Bob checks for two available adjacent seats
dsql=*> select seat_row, seat_number, next_seat_number
from (
select seat_row, seat_number, booked_by
, lead(seat_number) over row_seats as next_seat_number
, lead(booked_by ) over row_seats as next_booked_by
from seats
window row_seats as (partition by seat_row order by seat_number)
) seats_with_next
where booked_by is null and next_booked_by is null
;
seat_row | seat_number | next_seat_number
----------+-------------+------------------
A | 4 | 5
(1 row)
Bob is happy and verifies that his seat is still free, intending to reserve it if Alice is available to book the other seat:
dsql=*> select * from seats
where (seat_row, seat_number)=('A', 4)
for update
;
seat_row | seat_number | booked_by
----------+-------------+-----------
A | 4 |
(1 row)
Bob calls Alice and tells her to book seat A-5.
Alice starts a transaction:
dsql=> begin transaction;
BEGIN
Alice verifies that the seat is still free, with the intention to reserve it:
dsql=*> select * from seats
where (seat_row, seat_number)=('A', 5)
for update
;
seat_row | seat_number | booked_by
----------+-------------+-----------
A | 5 |
(1 row)
The seat is still free. Alice confirms to Bob that she can reserve it.
During this time, Mallory checks for available seats, and because the others have not committed yet, he sees three free seats:
dsql=> select * from seats where booked_by is null
;
seat_row | seat_number | booked_by
----------+-------------+-----------
A | 2 |
A | 4 |
A | 5 |
(3 rows)
Mallory picks one of them, A-4, and tries to book it:
dsql=> update seats set booked_by='Mallory'
where (seat_row, seat_number)=('A', 4)
and booked_by is null
;
UPDATE 1
Mallory did not have to wait, and his transaction was successful. Because the database is in Optimistic Concurrency Control mode, he ignored others' intents and was able to book it. Aurora DSQL doesn't synchronize with others before committing and reads from a stale state (snapshot isolation defined at the beginning of the transaction).
This provides good performance for reads, but application developers must understand its consequences: what you have read is valid only if your transaction can commit, and any decision that depends on what you have read must be reverted if the commit fails. This includes the SQL commands, part of the rollback, and any non-transaction action the application did (write to a file, send to queue, increment a counter).
Mallory's transaction is committed. I've run it in auto-commit here to keep it simple, as it is a single-statement transaction.
Bob and Alice were not aware of this. Their transaction runs in Repeatable Read, so they can query again and will always see the same result with 3 free seats. They did a SELECT FOR UPDATE, which in other databases declares the intent to update and reserves the row for it. This is not true with Optimistic Concurrency Control.
Bob books his seat:
dsql=*> update seats set booked_by='Bob'
where (seat_row, seat_number)=('A', 4)
and booked_by is null
;
UPDATE 1
Alice books her seat:
dsql=*> update seats set booked_by='Alice'
where (seat_row, seat_number)=('A', 5)
and booked_by is null
;
UPDATE 1
Alice and Bob prepared their bookings, checking everything to ensure they had two seats near each other. If anything was incorrect, they could cancel their transaction, but from what they saw, it all looked good so that they could commit.
Alice commits:
dsql=*> commit;
COMMIT
Bob commits:
dsql=*> commit;
ERROR: change conflicts with another transaction, please retry: (OC000)
Bob gets an optimistic concurrency control error, which tells him everything he has read is a phantom state that isn't true. The seat he selected is not free, and he cannot book it. His transaction is canceled.
He checks the status of the bookings:
dsql=> select * from seats order by seat_row, seat_number
;
seat_row | seat_number | booked_by
----------+-------------+-----------
A | 1 | Carol
A | 2 |
A | 3 | Oscar
A | 4 | Mallory
A | 5 | Alice
A | 6 | Carlos
A | 7 | Charlie
(7 rows)
Alice will sit with Mallory, not Bob. They tried to synchronize their booking, but the database was designed to avoid such synchronization.
This illustrates what happens with Optimistic Concurrency Control: the application developer must understand and code around it, and the tests must include race conditions to validate the behavior.
This behavior is different from that of PostgreSQL and PostgreSQL-compatible databases. Aurora DSQL made this trade-off to improve performance. YugabyteDB distributes the transaction intents like the committed data (each tablet has an IntentsDB and a RegularDB, which are maintained strongly consistent across zones or regions with a Raft consensus) with additional synchronization during the transaction (read Write Buffering to Reduce Raft Consensus Latency in YugabyteDB to know when). Aurora DSQL does not synchronize the transaction intents for ongoing transactions to synchronize only once at COMMIT time. The application developer familiar with PostgreSQL must keep this in mind and adapt his code.
Top comments (0)