DSA, Database System & Operating System — Transaction Processing, Concurrency Control & Recovery, NEC licence examination syllabus (Nepal Engineering Council).
Concurrent Executions
Why running transactions simultaneously is necessary, and the four anomalies it can cause.
🌍 Where this lives: the "lost update" below is the single most common concurrency bug in application code, and it looks nothing like a database problem. You read a value into a variable, compute a new one, write it back — and someone else's write in between vanishes. Every "why did my counter skip numbers" and "two users booked the same seat" bug is this pattern. The fix is never "be more careful"; it is to make the read-modify-write atomic, either with a single UPDATE expression, a lock, or an optimistic version check. Search "read modify write race condition database".
Why concurrency at all
Serial execution — one transaction at a time — is trivially
correct and unusably slow.
THROUGHPUT. A transaction spends most of its life WAITING
for disk. While T1 waits for a page read (~100 µs on SSD),
the CPU is idle. Running T2 during that wait uses the
hardware you have already paid for.
RESPONSE TIME. A short query behind a long report should
not wait for the report to finish. Interleaving lets short
transactions complete quickly.
RESOURCE UTILISATION. Disk, CPU and network are different
devices. Serial execution uses one at a time.
THE COST: interleaving creates the possibility of
interference. Concurrency control exists to get the throughput
of interleaved execution with the correctness of serial
execution.
SCHEDULE — a sequence showing the order in which the
operations of several transactions actually executed.
SERIAL schedule all of T1, then all of T2
CONCURRENT schedule operations interleaved
SERIALIZABLE schedule interleaved, but EQUIVALENT in effect
to some serial schedule
Notation used throughout:
R(X) read item X W(X) write item X
C commit A abort
T1: R(A) W(A) R(B) W(B) C
T2: R(A) W(A) C
→ a schedule is the merged order of these operations
The four anomalies
1. LOST UPDATE (write–write conflict)
Two transactions read the same item, both compute a new
value from what they read, and both write. The first
write is silently overwritten.
T1: R(A)=100 T2: R(A)=100
T1: A := 100+1000 T2: A := 100+500
T2: W(A)=600
T1: W(A)=1100 ← T2's +500 is LOST
final = 1100, should be 1600
2. DIRTY READ (reading uncommitted data)
T2 reads a value T1 wrote but has not committed. If T1
then aborts, T2 acted on data that never existed.
T1: W(A)=500
T2: R(A)=500 ← dirty
T1: ABORT ← A reverts; T2's read was of a
value that was never real
3. NON-REPEATABLE READ (inconsistent read)
T1 reads an item twice and gets different values, because
T2 committed a change in between.
T1: R(A)=100
T2: W(A)=200, COMMIT
T1: R(A)=200 ← same query, different answer
4. PHANTOM READ
T1 runs a range query twice and the second run returns a
row that did not exist before, because T2 INSERTED it.
T1: SELECT COUNT(*) WHERE dept='CS' → 25
T2: INSERT a CS student, COMMIT
T1: SELECT COUNT(*) WHERE dept='CS' → 26 ← phantom
Note this is different from a non-repeatable read: no
EXISTING row changed. Row-level locks cannot prevent it,
because you cannot lock a row that does not exist yet.
Preventing phantoms needs RANGE or PREDICATE locks.
A FIFTH, often omitted: WRITE SKEW
Two transactions read an overlapping set, each writes a
DIFFERENT row, and together they break an invariant that
each individually preserved. See the verified example
below — it is the anomaly that motivates SERIALIZABLE.
Lost update — reproduced and measured
lost_update.sql
-- Two real sessions on PostgreSQL 18, READ COMMITTED.
-- The pattern: read into the application, compute, write back.
-- starting balance = 10000
-- SESSION A SESSION B
BEGIN;
-- read the balance into app memory (simulated with a
-- temp table so the value is captured, as an application
-- variable would be)
CREATE TEMP TABLE tmpa AS
SELECT balance AS b FROM account WHERE id=1; -- 10000-- BEGIN;
-- UPDATE account
-- SET balance =
-- balance + 500
-- WHERE id=1;
-- COMMIT; → 10500UPDATE account
SET balance = (SELECT b FROM tmpa) + 1000
WHERE id = 1; -- writes 10000+1000
COMMIT;
-- MEASURED RESULT:
-- B wrote 10500.00
-- A wrote 11000.00
-- final balance = 11000.00
--
-- EXPECTED (if serialised): 10000 + 500 + 1000 = 11500
-- ACTUAL: 11000
-- B's +500 was LOST. ✔ anomaly reproduced-- ===== THE THREE FIXES =====
-- FIX 1: never read-then-write. Compute IN the UPDATE, so
-- the read and write are one atomic statement.
UPDATE account SET balance = balance + 1000 WHERE id = 1;
-- Row-level locking makes this safe at ANY isolation level:
-- the second UPDATE waits for the first to commit and then
-- re-reads the row.
-- FIX 2: pessimistic locking — take the lock at read time.
BEGIN;
SELECT balance FROM account WHERE id=1 FOR UPDATE;
-- ^ other transactions now BLOCK here until we commit
UPDATE account SET balance = 11000 WHERE id=1;
COMMIT;
-- FIX 3: optimistic locking — a version column.
ALTER TABLE account ADD COLUMN version INT NOT NULL DEFAULT 0;
-- read version 7 along with the balance, then:
UPDATE account
SET balance = 11000, version = version + 1
WHERE id = 1 AND version = 7;
-- If another transaction bumped the version, 0 rows are
-- updated and the application knows to retry. This is what
-- every ORM's @Version annotation does.
The measured numbers are worth restating because they show
the anomaly is real, not theoretical:
starting balance 10,000
B adds 500 → commits 10,500
A adds 1000 → commits 11,000
correct answer 11,500
A read 10,000 BEFORE B committed, held that stale value in
application memory, and wrote 10,000+1000. B's write was
overwritten with no error, no warning, and no lock conflict —
because A never read the row again.
WHY READ COMMITTED DOES NOT PREVENT THIS: it guarantees you
never read UNCOMMITTED data. It says nothing about a value you
read becoming stale afterwards. The window between your read
and your write is entirely unprotected.
WHICH FIX TO USE:
· single-row arithmetic → FIX 1, always. It is free.
· multi-step logic that must see a stable value
→ FIX 2 (FOR UPDATE), simple and
correct, but holds locks
· long user-facing edit ("edit form open for 5 minutes")
→ FIX 3 (optimistic), because you
must not hold a lock across a
user's think time
Fix 1 deserves emphasis: SET balance = balance + 1000 is safe and SET balance = value_I_read_earlier + 1000 is not. The difference is whether the database re-reads the current value at write time. Any time you find yourself putting a database value into an application variable and later writing it back, you have created this bug.
Phantom reads and write skew
write_skew.sql
-- WRITE SKEW: the anomaly that snapshot isolation permits and
-- serializability forbids.
-- Business rule: AT LEAST ONE doctor must remain on call.
CREATE TABLE doctor (name TEXT, on_call BOOLEAN);
INSERT INTO doctor VALUES ('Sharma',true), ('Karki',true);
-- Both doctors decide to go off call at the same moment.
-- Each checks "is someone else still on call?" and sees YES.
-- SESSION 1 SESSION 2
BEGIN ISOLATION LEVEL SERIALIZABLE; -- BEGIN SERIALIZABLE;
SELECT count(*) FROM doctor
WHERE on_call; -- 2 -- SELECT count(*) ... → 2-- both see 2, both
-- conclude it is safe
UPDATE doctor SET on_call=false
WHERE name='Sharma'; -- UPDATE ... WHERE
-- name='Karki';
COMMIT; -- COMMIT;-- MEASURED RESULT — session 2:
-- ERROR: could not serialize access due to read/write
-- dependencies among transactions
-- DETAIL: Reason code: Canceled on identification as a
-- pivot, during write.
-- HINT: The transaction might succeed if retried.
--
-- Final state: Karki | t
-- Sharma | f
-- The invariant HELD, because PostgreSQL aborted one
-- transaction. ✔-- Under REPEATABLE READ (snapshot isolation) BOTH would
-- commit, because neither modified a row the other read —
-- there is no write-write conflict to detect. Both doctors
-- go off call and the invariant is broken.-- THE ESSENTIAL POINT: write skew involves NO write-write
-- conflict. Each transaction writes a row the other never
-- touched. Only tracking READ-WRITE dependencies catches it,
-- which is exactly what SERIALIZABLE (SSI) does and snapshot
-- isolation does not.
-- ===== THE PRACTICAL CONSEQUENCE =====
-- SERIALIZABLE transactions can FAIL and must be RETRIED.
-- Every application using it needs a retry loop:
--
-- for attempt in 1..3:
-- try:
-- run_transaction()
-- break
-- except SerializationFailure:
-- continue # retry with a fresh snapshot
--
-- This is not a defect. It is the price of serializability
-- without long-held locks, and it is why "just use
-- SERIALIZABLE" requires application changes, not only a
-- config change.
The isolation levels and what each permits
The SQL standard defines four levels by which anomalies they
ALLOW:
LEVEL dirty non-repeat phantom write
read read skew
─────────────────────────────────────────────────────────
READ UNCOMMITTED YES YES YES YES
READ COMMITTED no YES YES YES
REPEATABLE READ no no YES* YES
SERIALIZABLE no no no no
* the standard permits phantoms at REPEATABLE READ.
PostgreSQL's implementation (snapshot isolation) does NOT
exhibit them, because a snapshot hides later inserts too.
So PostgreSQL's REPEATABLE READ is STRONGER than the
standard requires — a common source of confusion when
porting from other databases.
WHAT EACH ENGINE ACTUALLY DOES:
PostgreSQL READ UNCOMMITTED behaves as READ COMMITTED
(dirty reads are simply not implementable in
MVCC). Default: READ COMMITTED.
MySQL/InnoDB Default: REPEATABLE READ.
Oracle Supports only READ COMMITTED and SERIALIZABLE.
SQL Server Default: READ COMMITTED, with an optional
snapshot mode.
CHOOSING A LEVEL:
READ COMMITTED the right default for most OLTP. Cheap.
Requires you to avoid read-modify-write in
application code.
REPEATABLE READ when a transaction must see a stable
snapshot — reports, multi-query
consistency checks.
SERIALIZABLE when an invariant spans rows the
transaction only READS. Requires a retry
loop.
SET TRANSACTION ISOLATION LEVEL SERIALIZABLE;
-- or per transaction:
BEGIN ISOLATION LEVEL SERIALIZABLE;
🌍 Go further: the definitive treatment of these anomalies is the 1995 paper "A Critique of ANSI SQL Isolation Levels" by Berenson, Bernstein, Gray and others, which showed the standard's definitions are ambiguous and named the anomalies that the standard missed — including write skew. It introduced snapshot isolation as a distinct level that fits nowhere in the standard's table, which is precisely why PostgreSQL's REPEATABLE READ does not match the standard. Search that paper's title, then "serializable snapshot isolation SSI" for how PostgreSQL 9.1 made true serializability affordable.
💡 Exam angle: name the four anomalies — lost update, dirty read, non-repeatable read, phantom read — and give a two-transaction schedule for each using R(X)/W(X) notation. Reproduce the isolation-level table showing which anomalies each level permits; that table is asked almost verbatim. Explain why a phantom needs range locks rather than row locks. The strongest answer adds write skew and notes that it involves no write-write conflict, which is why snapshot isolation permits it and serializability does not.
Syllabus points
Schedules; benefits/problems of concurrency
Create a free account to tick topics off, take notes as you read, watch the video lessons and get a day-by-day study plan built around your exam date.
Related topics in Transaction Processing, Concurrency Control & Recovery