Concurrency Control

Concurrency control is the mechanism by which databases manage multiple transactions accessing the same data simultaneously, ensuring data consistency and transaction isolation.

Concurrency Control Methods

┌─────────────────────────────────────────────────────────┐
│              Concurrency Control                        │
├─────────────────────────────────────────────────────────┤
│                                                         │
│  ┌──────────────┐  ┌──────────────┐  ┌──────────────┐  │
│  │  Lock-Based  │  │     MVCC     │  │  Optimistic  │  │
│  │ (Pessimistic)│  │(Multi-Version)│ │  (Optimistic)│  │
│  └──────────────┘  └──────────────┘  └──────────────┘  │
│                                                         │
└─────────────────────────────────────────────────────────┘

Lock-Based Concurrency Control

Lock Types

Lock Type	Abbrev	Compatibility	Purpose
Shared Lock	S	S compatible, X exclusive	Read operations
Exclusive Lock	X	Exclusive with all	Write operations
Intent Shared	IS	Table-level, indicates S lock needed	Table locking
Intent Exclusive	IX	Table-level, indicates X lock needed	Table locking

Lock Compatibility Matrix

        │  S   │  X   │  IS  │  IX
────────┼──────┼──────┼──────┼──────
   S    │  ✓   │  ✗   │  ✓   │  ✗
   X    │  ✗   │  ✗   │  ✗   │  ✗
   IS   │  ✓   │  ✗   │  ✓   │  ✓
   IX   │  ✗   │  ✗   │  ✓   │  ✓

✓ = Compatible (can hold simultaneously)
✗ = Conflict (must wait)

Lock Granularity

Table Lock:
┌─────────────────────────────────────────────────────────┐
│ Locks the entire table                                  │
│ Pros: Low overhead, avoids deadlocks                    │
│ Cons: Poor concurrency                                  │
└─────────────────────────────────────────────────────────┘

Row Lock:
┌─────────────────────────────────────────────────────────┐
│ Locks only specific rows                                │
│ Pros: Good concurrency                                  │
│ Cons: Higher overhead, deadlock possible                │
└─────────────────────────────────────────────────────────┘

Page Lock:
┌─────────────────────────────────────────────────────────┐
│ Locks data pages (typically 8KB-16KB)                   │
│ Between table and row lock granularity                  │
└─────────────────────────────────────────────────────────┘

SQL Lock Statements

-- PostgreSQL row locks
SELECT * FROM accounts WHERE id = 1 FOR UPDATE;         -- Exclusive lock
SELECT * FROM accounts WHERE id = 1 FOR SHARE;          -- Shared lock
SELECT * FROM accounts WHERE id = 1 FOR UPDATE NOWAIT;  -- No wait
SELECT * FROM accounts WHERE id = 1 FOR UPDATE SKIP LOCKED;  -- Skip locked

-- PostgreSQL table locks
LOCK TABLE accounts IN SHARE MODE;           -- Shared lock
LOCK TABLE accounts IN EXCLUSIVE MODE;       -- Exclusive lock
LOCK TABLE accounts IN ACCESS EXCLUSIVE MODE;  -- Full exclusive

-- MySQL row locks
SELECT * FROM accounts WHERE id = 1 FOR UPDATE;
SELECT * FROM accounts WHERE id = 1 FOR SHARE;  -- MySQL 8.0+
SELECT * FROM accounts WHERE id = 1 LOCK IN SHARE MODE;  -- MySQL 5.7

MVCC (Multi-Version Concurrency Control)

MVCC maintains multiple versions of data to allow reads and writes without blocking each other.

How It Works

Transaction T1 (xid=100)         Transaction T2 (xid=101)
─────────────────────────────────────────────────────
BEGIN;                           BEGIN;

                                 UPDATE accounts
                                 SET balance = 900
                                 WHERE id = 1;

SELECT balance FROM accounts     -- T2 creates new version
WHERE id = 1;
-- Returns 1000 (T1 sees old version)
                                 COMMIT;

SELECT balance FROM accounts
WHERE id = 1;
-- Read Committed: Returns 900
-- Repeatable Read: Returns 1000

PostgreSQL MVCC Implementation

Each row contains system columns:
┌─────────────────────────────────────────────────────────┐
│ xmin: Transaction ID that created this version          │
│ xmax: Transaction ID that deleted/updated (0 = active)  │
│ ctid: Physical location (points to new version)         │
└─────────────────────────────────────────────────────────┘

Row version chain:
┌───────────────────┐    ┌───────────────────┐
│ version 1         │    │ version 2         │
│ balance = 1000    │───▶│ balance = 900     │
│ xmin = 100        │    │ xmin = 101        │
│ xmax = 101        │    │ xmax = 0          │
└───────────────────┘    └───────────────────┘

Visibility rules:
- xmin committed AND xmax not committed → Visible
- xmin not committed → Not visible
- xmax committed → Not visible (deleted/updated)

MySQL InnoDB MVCC Implementation

Undo Log stores historical versions:
┌─────────────────────────────────────────────────────────┐
│ Current data row:                                       │
│ ├── DATA: balance = 900                                 │
│ ├── DB_TRX_ID: 101 (last modifying transaction ID)      │
│ └── DB_ROLL_PTR: → undo log                            │
│                                                         │
│ Undo Log:                                               │
│ └── balance = 1000 (previous version)                   │
└─────────────────────────────────────────────────────────┘

Read View (consistent snapshot):
┌─────────────────────────────────────────────────────────┐
│ creator_trx_id: Current transaction ID                  │
│ trx_ids: Active transaction list when view created      │
│ low_limit_id: Next transaction ID to be assigned        │
│ up_limit_id: Smallest ID among active transactions      │
└─────────────────────────────────────────────────────────┘

MVCC Benefits and Costs

Benefits	Costs
Reads don't block writes	Extra storage (multiple versions)
Writes don't block reads	Requires version cleanup (VACUUM)
Consistent snapshot reads	Long transactions cause bloat
No read lock overhead	Visibility checks have CPU cost

Deadlock

Deadlock occurs when two or more transactions are waiting for each other to release locks.

Deadlock Example

Transaction A                    Transaction B
─────────────────────────────────────────────────────
BEGIN;                           BEGIN;

-- A locks row 1
UPDATE accounts
SET balance = balance - 100
WHERE id = 1;
                                 -- B locks row 2
                                 UPDATE accounts
                                 SET balance = balance - 50
                                 WHERE id = 2;

-- A waits for B to release row 2
UPDATE accounts
SET balance = balance + 100
WHERE id = 2;
-- WAITING...
                                 -- B waits for A to release row 1
                                 UPDATE accounts
                                 SET balance = balance + 50
                                 WHERE id = 1;
                                 -- WAITING...

-- Deadlock! Both are waiting

Deadlock Detection and Handling

-- PostgreSQL deadlock detection
-- Enabled by default, deadlock_timeout = 1s
SHOW deadlock_timeout;

-- When deadlock detected, automatically rolls back one transaction
-- ERROR: deadlock detected
-- DETAIL: Process 1234 waits for ShareLock on transaction 5678;
--         blocked by process 5678.
--         Process 5678 waits for ShareLock on transaction 1234;
--         blocked by process 1234.

-- MySQL deadlock information
SHOW ENGINE INNODB STATUS;
-- Check the LATEST DETECTED DEADLOCK section

Deadlock Prevention Strategies

-- 1. Access resources in fixed order
-- Bad: Random order
UPDATE accounts SET ... WHERE id = 2;
UPDATE accounts SET ... WHERE id = 1;

-- Good: By ID order
UPDATE accounts SET ... WHERE id = 1;
UPDATE accounts SET ... WHERE id = 2;

-- 2. Use lock timeout
SET lock_timeout = '5s';  -- PostgreSQL
SET innodb_lock_wait_timeout = 5;  -- MySQL

-- 3. Reduce lock hold time
BEGIN;
-- Do calculations first
PREPARE calculation;
-- Lock and update last
UPDATE accounts SET ...;
COMMIT;

-- 4. Use NOWAIT or SKIP LOCKED
SELECT * FROM accounts WHERE id = 1 FOR UPDATE NOWAIT;
-- Fail immediately instead of waiting

SELECT * FROM tasks WHERE status = 'pending'
FOR UPDATE SKIP LOCKED LIMIT 1;
-- Skip locked rows (queue scenario)

Optimistic Concurrency Control

Optimistic concurrency control assumes conflicts are rare and detects them at commit time.

Version Number Implementation

-- Table structure
CREATE TABLE products (
    id SERIAL PRIMARY KEY,
    name VARCHAR(100),
    price DECIMAL(10,2),
    stock INT,
    version INT DEFAULT 1
);

-- Read
SELECT id, name, price, stock, version
FROM products WHERE id = 1;
-- Returns: version = 5

-- Check version when updating
UPDATE products
SET stock = stock - 1,
    version = version + 1
WHERE id = 1 AND version = 5;

-- Check if update succeeded
-- If affected_rows = 0, conflict occurred, retry needed

Timestamp Implementation

CREATE TABLE documents (
    id SERIAL PRIMARY KEY,
    content TEXT,
    updated_at TIMESTAMP WITH TIME ZONE DEFAULT CURRENT_TIMESTAMP
);

-- Check timestamp when updating
UPDATE documents
SET content = 'new content',
    updated_at = CURRENT_TIMESTAMP
WHERE id = 1 AND updated_at = '2024-06-01 10:00:00+00';

Application Layer Implementation

def update_with_optimistic_lock(product_id, new_stock):
    max_retries = 3
    for attempt in range(max_retries):
        # Read current version
        product = db.query(
            "SELECT id, stock, version FROM products WHERE id = %s",
            product_id
        )

        # Business logic
        if product.stock < new_stock:
            raise InsufficientStockError()

        # Check version when updating
        result = db.execute(
            """UPDATE products
               SET stock = %s, version = version + 1
               WHERE id = %s AND version = %s""",
            new_stock, product_id, product.version
        )

        if result.rowcount > 0:
            return True  # Success

        # Version conflict, retry
        time.sleep(0.1 * (attempt + 1))  # Exponential backoff

    raise ConcurrencyError("Max retries exceeded")

Comparison

Feature	Pessimistic Lock	Optimistic Lock	MVCC
Conflict assumption	Frequent	Rare	Moderate
Lock timing	At read	At commit	No explicit lock
Blocking	Read-write mutual	No blocking	Read-write independent
Use case	High conflict	Low conflict	General scenarios
Implementation	Database	App/Database	Database

Best Practices

Short transactions: Minimize transaction duration to reduce lock hold time
Fixed order: Access resources in fixed order to prevent deadlocks
Choose appropriate strategy: Pessimistic for high conflict, optimistic for low
Monitor: Track lock waits and deadlock frequency
Index optimization: Ensure WHERE conditions have indexes to reduce lock scope
Batch operations: Consider batch processing for large updates
Timeout settings: Set reasonable lock timeout values

Concurrency Control

On this page