Concurrency control strategies

• Each buyer computes the new value from an old read.
• No error is raised. The stock count is simply wrong.
• Every strategy on this sheet closes the gap between the read and the write.

If two clients read, decide and then write, the second write silently replaces the first.

• Waiting costs latency, but no work is lost.
• Retrying wastes work, and the waste grows with contention.
• Skipping needs many rows that are equal, such as jobs or units.

Every strategy decides one thing: does the losing writer wait, retry, skip, or queue?

On a hot key I use a conditional update or a single writer. Optimistic locking and SERIALIZABLE are for keys that rarely collide.

32 clients, 3 s per run, Postgres 16.14, 16 CPU threads. Each take decrements a counter that must stay at or above zero. Repeated runs differ by up to 2 times, so read these as orders of magnitude.

With one hot key the strategies differ by almost 100 times. With 1,000 keys they are all within a few times of each other.

With a conditional update, the second buyer waits for the first, then sees qty 0 and gets sold out.

• All 200 buyers start at once.
• Every strategy sells exactly 50 units.
• The CHECK constraint never fires in the other strategies. It stays as a backstop.

I prove a strategy under load: the units sold must equal the stock, with no errors.

Postgres gives me row locks, a re-check after a lock wait, constraints, SKIP LOCKED and serializable isolation. The service adds a single writer when one key is hot.

pessimistic(item):
  BEGIN
    qty = read qty FOR UPDATE           // others wait here1
    IF qty == 0: ROLLBACK; RETURN sold out
    qty = qty - 1
  COMMIT

conditional(item):
  rows = set qty = qty - 1 WHERE qty > 02  // check and write, one statement
  RETURN rows == 13 ? taken : sold out

constraint(item):
  set qty = qty - 1                     // no check in the code4
  ON error 23514: RETURN sold out

-- Pessimistic: lock the row. Other buyers of this item wait here.
SELECT qty FROM stock WHERE item_id = $1 FOR UPDATE;

UPDATE stock SET qty = qty - 1 WHERE item_id = $1;

-- Check and write in one statement. The row count says if it worked.
UPDATE stock SET qty = qty - 1
WHERE item_id = $1 AND qty > 0;

-- One row per item. The CHECK refuses stock below zero, whatever the code does.
CREATE TABLE stock (
  item_id bigint PRIMARY KEY,
  qty     int    NOT NULL CHECK (qty >= 0),
  version bigint NOT NULL DEFAULT 0
);

A conditional update is the check and the write in one statement. The row count tells me if it worked.

take(item):
  LOOP:
    read qty, version                   // no lock1
    IF qty == 0: RETURN sold out
    rows = set qty = qty - 1, version = version + 1
           WHERE version = the version you read2
    IF rows == 1: RETURN taken
    // 0 rows: another buyer wrote first; read again3

var qty int
var version int64
if err := db.QueryRow(ctx, q["read"], item).Scan(&qty, &version); err != nil {
  return Result{}, fmt.Errorf("optimistic read: %w", err)
}
if qty == 0 {
  return res, nil // sold out
}
tag, err := db.Exec(ctx, q["cas"], item, qty-1, version)
if err != nil {
  return Result{}, fmt.Errorf("optimistic write: %w", err)
}
if tag.RowsAffected() == 1 {
  res.Taken = true
  return res, nil
}
res.Retries++ // another buyer changed the row first: read again

SELECT qty, version FROM stock WHERE item_id = $1;

-- Optimistic: write only if nobody changed the row since we read it.
UPDATE stock SET qty = $2, version = version + 1
WHERE item_id = $1 AND version = $3;

• Use it for edits that a person makes, where a lock would be held too long.
• An HTTP ETag with If-Match is the same idea at the API.

I read the version, then write only if the version has not changed. A miss means someone else won, so I read again.

take(item):
  LOOP:
    BEGIN ISOLATION LEVEL SERIALIZABLE1
      qty = read qty
      IF qty == 0: COMMIT; RETURN sold out
      write qty - 1
    COMMIT
    ON error 400012: ROLLBACK, run the whole transaction again3
    RETURN taken

taken := false
err := pgx.BeginTxFunc(ctx, db, pgx.TxOptions{IsoLevel: pgx.Serializable}, func(tx pgx.Tx) error {
  var qty int
  var version int64
  if err := tx.QueryRow(ctx, q["read"], item).Scan(&qty, &version); err != nil {
    return fmt.Errorf("read: %w", err)
  }
  if qty == 0 {
    return nil
  }
  if _, err := tx.Exec(ctx, q["write_qty"], item, qty-1); err != nil {
    return fmt.Errorf("write: %w", err)
  }
  taken = true
  return nil
})
if IsCode(err, CodeSerialization) || IsCode(err, CodeDeadlock) {
  res.Retries++ // Postgres found a conflict: run the whole transaction again
  continue
}

• It also stops write skew, which row locks on one row cannot see.
• A read by full table scan marks the whole table. On small tables, almost every pair of transactions conflicts.

SERIALIZABLE lets me write plain reads and writes, but I must retry the whole transaction on error 40001.

claim(worker):                     // one statement
  job = oldest queued job
        that no other transaction holds1   // FOR UPDATE SKIP LOCKED
  IF none: RETURN nothing to do
  mark job running2 by worker; COMMIT
  RETURN job

-- A worker takes the oldest queued job that no other worker holds.
UPDATE jobs SET status = 'running', worker = $1
WHERE id = (
  SELECT id FROM jobs
  WHERE status = 'queued'
  ORDER BY id
  LIMIT 1
  FOR UPDATE SKIP LOCKED
)
RETURNING id;

Workers claim jobs with FOR UPDATE SKIP LOCKED, so each job goes to one worker and no worker waits.

route(take(item)):
  queue[item mod 81].push(request)        // no lock anywhere

writer(queue):                           // ONE writer per queue2
  LOOP:
    batch = wait for 1 request, then take up to 256 more
    BEGIN
      FOR EACH item IN batch:
        n = requests for item
        granted = set qty = qty - min(qty, n)3, RETURN min(qty, n)
    COMMIT                               // one commit for the batch4
    reply taken to the first granted requests, sold out to the rest

  batch := []request{first}
drain:
  for len(batch) < MaxBatch {
    select {
    case r := <-ch:
      batch = append(batch, r)
    default:
      break drain
    }
  }
  byItem := map[int64][]request{}
  var order []int64
  for _, r := range batch {
    if _, ok := byItem[r.item]; !ok {
      order = append(order, r.item)
    }
    byItem[r.item] = append(byItem[r.item], r)
  }
  granted := map[int64]int{}
  err := pgx.BeginFunc(ctx, w.db, func(tx pgx.Tx) error { // one commit for the whole batch
    for _, item := range order {
      var n int
      if err := tx.QueryRow(ctx, q["take_batch"], item, len(byItem[item])).Scan(&n); err != nil {
        return fmt.Errorf("take item %d: %w", item, err)
      }
      granted[item] = n
    }
    return nil
  })
  for _, item := range order {
    for i, r := range byItem[item] { // reply only after the commit
      r.reply <- Reply{Taken: err == nil && i < granted[item], Err: err}
    }
  }

-- Single writer: grant up to $2 requests in one statement. No other writer touches this item.
WITH cur AS (SELECT qty FROM stock WHERE item_id = $1)
UPDATE stock SET qty = stock.qty - LEAST(cur.qty, $2)
FROM cur
WHERE stock.item_id = $1
RETURNING LEAST(cur.qty, $2);

For one very hot key I route every request for that key to one writer. It applies a batch in one transaction, so there is no lock and one commit.

Demand example: 100,000 buyers want one item within 60 seconds, so 100,000 / 60 = 1,667 takes a second. The single writer bar is drawn in the Postgres colour because its writes land in Postgres.

I start with a conditional update. I split a hot row or add a single writer only when one key needs more than its row can commit.