Dealing With Contention

Solution to make sure the application is race condition safe

Conditional writes

The easiest way to deal with contention is to use Compare And Swap (CAS) with database. For example

UPDATE concerts
SET available_seats = available_seats - 1
WHERE concert_id = 'weeknd_tour'
  AND available_seats > 0;

We only update the seats when there is an available seat. When we do something like this, the database will perform a row lock to make sure that only one operation can change the item at the time.

[!note]
The row lock is only for write operation. For read operation, most database will read a snapshot unless specifically put a lock. To specifically put a lock for read

SELECT * FROM concerts WHERE concert_id = 'weeknd_tour' FOR UPDATE;

Similarly, for a particular seat id, we can do the following

UPDATE tickets
SET status = 'sold', user_id = 'user123'
WHERE concert_id = 'weeknd_tour'
  AND seat_number = 'A15'
  AND status = 'available';

If 2 people book this seat in the same time, the status would not be available anymore and hence failed the WHERE cause.

Pessimistic locking

If we need to lock a range, says if user is picking a range of seats, we need to use pessimistic locking Pessimistic locking. This allow us to acquire the lock upfront

In order to do this, we can use SELECT .. FOR UPDATE. Example

BEGIN TRANSACTION;

-- Lock the open seats in this section while we pick a block
SELECT seat_number FROM seats
WHERE concert_id = 'weeknd_tour'
  AND section = 'floor'
  AND status = 'available'
FOR UPDATE;

-- App scans the result, finds A15-A18 open and adjacent, then claims them
UPDATE seats
SET status = 'sold', user_id = 'user123'
WHERE concert_id = 'weeknd_tour'
  AND seat_number IN ('A15', 'A16', 'A17', 'A18');

COMMIT;

The FOR UPDATE will lock all the rows SELECT returns and no other transaction can claim the seat.

The catch here is you need to lock every seats just to claim 4 seats. In real production, we should only lock the rows that we need and nothing more.

Common problems

1. Locking too much for too long
2. Deadlocks from inconsistent ordering: 2 transactions grab the same rows in opposite order will cause dead lock

[!danger]
When using FOR UPDATE, the database will hold our database connection, this may exhaust the connection pool. If the connection drop, database normally perform a ROLLBACK

Optimistic Concurrency Control (OCC)

See: Optimistic Locking

This is very similar to Conditional Write which assume conflicts are rare and gracefully handle instead of blocking to prevent it

The idea is for each record, we keep a versioning, and when you write, you need to make sure that the versioning is the same as the one we have at read phase

Example: Both Alice and Bob read: 1 seat, version 42

-- Alice writes first:
BEGIN TRANSACTION;
UPDATE concerts
SET available_seats = available_seats - 1, version = version + 1
WHERE concert_id = 'weeknd_tour'
  AND version = 42;  -- the version Alice read

INSERT INTO tickets (user_id, concert_id, seat_number, price, purchase_time)
VALUES ('alice', 'weeknd_tour', 'A15', 750.00, NOW());
COMMIT;
-- Succeeds. seats = 0, version = 43

-- Bob writes against the version he read:
BEGIN TRANSACTION;
UPDATE concerts
SET available_seats = available_seats - 1, version = version + 1
WHERE concert_id = 'weeknd_tour'
  AND version = 42;  -- stale, the row is on 43 now

-- Bob's UPDATE matches 0 rows. Check the count, roll back, skip the insert.
ROLLBACK;

When Bob fail to read, he retries the operation again with the fresh version

[!note]
We use ROLLBACK to indicate the failure here, we technically can use COMMIT as well since there is nothing to commit i.e 0 rows

[!important]
Retries cost more than lock, this is simple but only use when conflict is rare

Isolation level

See also: ISOLATION (ACID)

There could be a scenario where both transaction makes a decision valid on their own, but when combine together it's wrong

Example:

On-call scheduler where at least 1 engineer has to be on call at all time. Right now there are 2: Alice and Bob.

• Alice transaction read the schedule, sees Bob still on-call, and remove herself
• Bob transaction read the schedule, sees Alice still on-call and remove himself

This will cause both the candidates remove them selves and have 0 on call

[!note]
Technically we can still use Pessimistic locking that locked a shared table of who's on call, however if Alice and Bob are in different table or the mapping is complicated, we need to use SERIALIZABLE isolation here

Isolation level control how much one transaction can see another transaction inflight works. Most database offer 4 standard level

READ UNCOMMITTED

One transaction can see another transaction non-commited transaction. For example

Transaction A: UPDATE accounts SET balance = 0;  -- not committed
Transaction B: SELECT balance FROM accounts;

Transaction B would able to see transaction A update already. Some database does not support this e.g Postgres

READ COMMITTED

Default isolation in Postgres, we can only see the committed change. However within a transaction, if we decided to read the data again, it might be different

--Transaction A:
BEGIN;

SELECT balance FROM accounts WHERE id = 'x'; -- Balance 100

-- Transaction B changes balance to 50 and commits here

SELECT balance FROM accounts WHERE id = 'x'; -- Balance 50 (Could change already)

COMMIT;

REPEATABLE READ

Default isolation in MySQL, this make sure the same transaction, reading the same value again stays the same

-- Transaction A
BEGIN TRANSACTION ISOLATION LEVEL REPEATABLE READ;

SELECT balance FROM accounts WHERE id = 'x'; -- 100

-- Transaction B changes balance to 50 and commits here

SELECT balance FROM accounts WHERE id = 'x'; -- still 100

COMMIT;

If we do an update here, transaction A will fail since the value is changed THIS ONLY APPLY FOR REPEATABLE READ

-- Transaction A
BEGIN TRANSACTION ISOLATION LEVEL REPEATABLE READ;

SELECT balance FROM accounts WHERE id = 'x'; -- 100

-- Transaction B changes balance to 50 and commits here

SELECT balance FROM accounts WHERE id = 'x'; -- still 100

-- Transaction A still sees 100
UPDATE accounts SET balance = balance - 10 WHERE id = 'x';

COMMIT;

ERROR: could not serialize access due to concurrent update

Note that this also fail if transaction A set to abitrary value UPDATE accounts SET balance = 999 WHERE id = 'x';

[!danger]
If you use default READ COMMITTED, it will not fail for the UPDATE path

SERIALIZABLE

Related transaction will appear to run one after another, the database will handle all the heavy work for us. The database will handle all the heavy lifting work

BEGIN TRANSACTION ISOLATION LEVEL SERIALIZABLE;

-- Is anyone else on call right now?
SELECT count(*) FROM on_call
WHERE team_id = 'payments'
  AND is_active = true;

-- App sees 2, decides it's safe to step down, then writes:
UPDATE on_call
SET is_active = false
WHERE engineer_id = 'alice';

COMMIT;
-- If Bob's transaction made the same decision concurrently,
-- one of the two commits aborts with a serialization error.

It will auto detect:

• What's the rows/ranges/etc involved here?
• Any other transactions that modifying the row?

In the case it happens, it will either fail our or block the other transaction, the application can then retry to make sure the database stays consistent

Note: SERIALIZABLE isn't free, it makes the database track all the read and writes it need to find these conflict. Any throwaway work need to be retry so very costly.

When possible, consider still use Pessimistic locking or Optimistic Locking for cheaper cost.

[!important]
Isolation is more like a SQL feature only, most NoSQL database dont give you true SERIALIZABLE. When that comes, we need to consider the cheaper ones like Pessimistic locking or Optimistic Locking

Distributed lock

The idea is simply hold a record of who holds the lock that's all. There are multiple way we can do this

Redis with TTL

We can use the SET command with NX (only set if not exists) — NX is very critical here. And a TTL flag.

Problem:

• Using TTL is not air-tight guarantee, if htere is a long operation, slow GC pause, slow network, Redis can hand the lock to the next holder.
  • Solution:
    1. Fencing token:
       • A acquire the lock with token 101, A pauses due to network error and the lock has been expired
       • B acquires the lock with token 102, A resume their work and get rejected because now the token is 102 not 101
    2. Periodic renew lock
       • The lock value is the holder name, the holder can have a background process to periodicly increase the hold time of the lock
• Redis is also single point of failure

Database column

We can simply just use a database column to check who is holding the lock, and when is the expire time

UPDATE seats
SET reserved_by = 'user123', reserved_until = NOW() + INTERVAL '10 minutes'
WHERE seat_id = 'A15'
  AND (reserved_until IS NULL OR reserved_until < NOW());

There is no cleanup job needed since we auto reserve once the reserved_until expires.

Advantage: no additional infrastructure
Disadvantage: slower than cache

Zookeeper / etcd

These provides strong consistency guarantees even during network partitions and leader failure. This is due to Quorum.

This system are designed to handle complex failure scenario that Redis and Database are struggle with. The disadvantage is operational complexity, you need to maintain a separate coordination cluster

Choosing the right approach

These techniques have equivalents outside SQL.

To start with, only keep relevant data in single database first, most of the time it's possible. If the requirement is:

1. Transaction span across multiple service, consider Two Phase Commit, Saga architecture pattern, TCC - Try Confirm Cancel
2. If same record should be able to write at the same time, use Vector Clock, last-write-wins, CRDTs (Conflict-free replicated data types)

[!important]
When in doubt, keep it single database and reach for simplest tool that fits. Starts with conditional write and move to pessimistic locking if needed

When to use in interviews

Don't wait for interviewer to ask about contention. If you see multiple process compete for the same resource, call it out and suggest coordination mechanisms

This typically happen in non-functional requirements where system requires a strong consistency

Recognition signals

1. Multiple users competing limited resource
2. Prevent double-booking / double-charging
3. Ensure data consistency under high concurrency
4. Handle race conditions

When to not overcomplicate

Dont reach for complex coordination mechanisms when simpler solution works!

If Optimistic Locking or Pessimistic locking is sufficient, use it. Don't reach for Redis or Zookeeper etc. Adding new components adds system complexity and introduces new failures mode

1. Low contention scenarios: where conflicts are rare (like updating product descriptions where only admins can edit), we can use basic optimistic concurrency with retry logic. Don't implement locking schemes
2. Single-user operations: if it's just single user like personal todo list, no need to handle race condition here
3. Read-heavy workloads: Since mostly read, a simple OCC Optimistic Locking can do it

Common deep dives

How to prevent deadlocks with pessimistic locking

Consider the following scenario

1. Application A process Alice pays Bob $200 and at the same time, application B process Bob pays Alice $50
   1. Application A locked Alice balance successfully and now process to lock Bob balance
   2. Application B locked Bob balance and now try to lock Alice blance

As you can see, this create a dead lock since application A tries to lock Bob balance — which is held by application B. Application B tries to lock Alice balance which is held by application A.

Solution

When we acquire the lock, regardless of the business logic, always acquire in sorted order. For example, we always acquire per sorted user_id.

In that case, either way of locking for both application it always lock on the same user first before processing on a different user. e.g Alice has a lower userId, so both application will lock on Alice first

How do you handle ABA problem with optimistic concurrency

ABA problems means your application change the field from A -> B and then it changes back to A.

If we use Optimistic Locking or Conditional writes without the verison column the application thought that there has been no change and assume that the record still stay the same

Solution

Use an increment version column to always increase after every change

-- Use a dedicated version column for safety
UPDATE restaurants
SET avg_rating = 4.1, review_count = review_count + 1, version = version + 1
WHERE restaurant_id = 'pizza_palace'
  AND version = 42;  -- Expected current version

If you cant add a version column the safest fall back is to put evevery field into the WHERE clause so that the write matches with what you saw. However it's heavy

Some databases expose a built-in row version, like Postgres xmin column