Starvation - Learning Module

Loading content...

0/252

Fairness in Lock Management

The Price of Order

A courtroom operates on a simple principle: justice delayed is justice denied. No matter how efficient the court system becomes at processing cases, if certain plaintiffs systematically wait decades while others are heard immediately, the system has failed—even if total cases processed per year reaches record highs.

Database lock managers face an analogous challenge. A system might achieve maximum throughput—transactions completing at unprecedented rates—while systematically disadvantaging certain transaction types. From a pure performance standpoint, such a system appears optimal. From a fairness standpoint, it is fundamentally broken.

Fairness in database concurrency control is the property that ensures all transactions receive equitable access to shared resources. It is the antidote to starvation, transforming a lock manager from a performance optimizer into a guardian of transactional rights.

What You Will Learn

This page explores fairness in depth: its formal definitions, the hierarchy of fairness guarantees, implementation techniques, and the critical tradeoffs between fairness and throughput. You will learn to reason about fairness properties and evaluate whether a given lock management policy satisfies specific fairness criteria.

Formal Definition of Fairness

Fairness is a property of scheduling algorithms that guarantees equitable treatment of competing requests. In the context of lock management, fairness ensures that every transaction requesting a lock will eventually acquire it.

Formal Definition:

A lock manager L is said to be fair if for every transaction T and every lock request r made by T:

If T requests lock r at time t₀, then there exists a finite time t₁ > t₀ at which T is granted r, provided:

T does not voluntarily withdraw the request

T does not abort due to deadlock resolution

The resource remains in a lockable state

This definition establishes the minimum requirement for fairness: eventual progress. However, as we'll see, different levels of fairness impose stronger or weaker constraints on how soon this progress must occur.

Components of a Fairness Definition
Component	Description	Why It Matters
Eventual Granting	Every valid request is eventually satisfied	Prevents indefinite waiting (starvation)
Request Ordering	Defines how requests are sequenced for service	Determines who gets access when resources free
Bounded Waiting	Specifies maximum wait time or bypasses	Distinguishes weak from strong fairness
Priority Handling	Defines interaction between fairness and priorities	Balances urgency against equity
Exception Cases	What conditions exempt fairness guarantees	Covers deadlock victims, timeouts, aborts

Fairness Is Not Equality

Fairness does not mean all transactions wait the same amount of time. A transaction requesting an exclusive lock on a highly contended resource will naturally wait longer than one requesting a shared lock on a rarely-accessed item. Fairness means that given the same request on the same resource, transactions are treated equitably—not that all transactions have identical experiences.

The Fairness Hierarchy

Computer scientists have identified a hierarchy of fairness guarantees, each progressively stronger than the last. Understanding this hierarchy is crucial for analyzing and designing lock management systems.

Fairness Guarantee Levels

•No Fairness Guarantee — The scheduler makes no promises about eventual service. Transactions may wait indefinitely. This is the default for many simple lock implementations.
•Eventual Fairness (Starvation-Freedom) — Every transaction will eventually get service, but no bound is specified. A transaction might wait microseconds or millennia.
•Weak Fairness — If a request is continuously enabled (could be granted), it will eventually be granted. This prevents starvation for requests that could always proceed.
•Strong Fairness — If a request is infinitely often enabled (could be granted infinitely often), it will eventually be granted. Handles intermittently available resources.
•Bounded Fairness — Every request will be granted within a specified bound: either a maximum wait time or a maximum number of bypasses by later requests.
•First-Come-First-Served (FCFS) — Requests are granted in exact arrival order. Zero bypasses. The gold standard for fairness, but potentially suboptimal for throughput.

Converting Mermaid diagram...

Detailed Analysis of Each Level:

1. No Fairness Guarantee The simplest lock managers offer no fairness at all. When a lock is released, any waiting transaction might be selected—or none might be. In practice, this often devolves into LIFO (last-in-first-out) behavior due to stack-based implementations.

2. Eventual Fairness (Starvation-Freedom) The minimum acceptable standard. Every transaction will eventually proceed. However, the time to proceed is unbounded. Useful for systems where some delay is tolerable but permanent blocking is not.

3. Weak Fairness Formal definition: If a request r is continuously enabled from some time t onward, then r will eventually be granted.

"Continuously enabled" means: at every moment from t forward, granting r would not violate consistency.
This handles the case where a lock becomes and stays free.

4. Strong Fairness Formal definition: If a request r is infinitely often enabled, then r will eventually be granted.

Handles intermittent availability: a resource keeps becoming free and getting taken by others.
Stronger than weak fairness because it doesn't require continuous availability.

5. Bounded Fairness Adds quantitative guarantees:

Time-bounded: Wait time ≤ T milliseconds
Bypass-bounded: At most N later requests can be granted before this one
Critical for SLA-sensitive applications where latency guarantees matter.

6. FCFS Fairness The strictest form: requests are processed in exact arrival order. If request A arrives before request B, then A is granted before B (assuming both are for the same or conflicting resources).

Guarantees zero bypasses
May reduce throughput due to inefficient batching
Often approximated rather than strictly implemented

FCFS: The Gold Standard

First-Come-First-Served (FCFS) ordering is the most intuitive fairness policy. Like a queue at a coffee shop, requests are served in the order they arrive. This simple principle provides the strongest fairness guarantees but comes with important implications for system performance.

How FCFS Works in Lock Management:

When a transaction requests a lock, it receives a ticket number (monotonically increasing)
When a lock becomes available, the transaction with the lowest ticket number among compatible waiters is granted the lock
No transaction with a higher ticket number can be granted while a lower-numbered transaction is waiting for a conflicting lock

fcfs_lock_manager.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class FCFSLockManager:
    ticket_counter = 0
    lock_queues = {}  # resource -> priority queue ordered by ticket
    
    def request_lock(transaction, resource, lock_type):
        ticket = atomic_increment(ticket_counter)
        
        request = LockRequest(
            transaction=transaction,
            resource=resource,
            type=lock_type,
            ticket=ticket,
            timestamp=now()
        )
        
        lock_queues[resource].enqueue(request)
        
        while not can_grant(request):
            wait()
        
        grant_lock(request)
    
    def can_grant(request):
        # Find all requests with lower ticket numbers
        earlier_requests = [r for r in lock_queues[request.resource] 
                          if r.ticket < request.ticket]
        
        # Check for conflicts with earlier requests
        for earlier in earlier_requests:
            if conflicts(earlier.type, request.type):
                return False
        
        # Check for conflicts with currently held locks
        for holder in current_holders[request.resource]:
            if conflicts(holder.type, request.type):
                return False
        
        return True

FCFS Guarantees:

Property	Guarantee
Starvation-freedom	✓ Absolute
Bounded waiting	✓ Bounded by queue length × max hold time
Bypass count	0 (strictly enforced)
Predictability	High (wait time correlates with queue position)

The Convoy Problem:

FCFS fairness comes with a significant performance cost: the convoy effect. When:

A slow transaction acquires a frequently-accessed lock
Fast transactions queue behind it
The slow transaction completes, releasing the lock
Fast transactions quickly complete and queue again
A new slow transaction arrives and acquires the lock
The convoy of fast transactions queues again

The result: fast transactions are forced to proceed at the pace of slow transactions, reducing overall throughput. This is the fundamental fairness-throughput tradeoff.

FCFS Is Rarely Strictly Implemented

Due to the convoy problem, production databases often use approximate FCFS: requests are mostly ordered by arrival, but optimizations like lock batching, priority shortcuts for short transactions, and read-write request merging may reorder some requests. The key is that bypasses are bounded, not eliminated.

Bypass Bounds and SLA Guarantees

Bounded fairness allows some deviation from strict FCFS ordering while still preventing starvation. The key mechanism is the bypass bound: a limit on how many later requests can be granted before an earlier request.

Bypass Bound Definition:

A lock manager satisfies a bypass bound of k if, for any request R:

At most k requests arriving after R can be granted before R is granted
Once k bypasses occur, R must be granted before any additional requests

Example (k = 2):

Request order: R1, R2, R3, R4, R5 (all for same resource)
Allowed: Grant R3, then R2, then R1, then R4, then R5
        (R1 was bypassed 2 times: by R2 and R3)
Not allowed: Grant R4 before R1
             (R1 would be bypassed 3 times)

Bypass Bound Tradeoffs
Bypass Bound (k)	Fairness Level	Throughput Impact	Use Case
k = 0	Strict FCFS	May cause convoy effect	Critical systems requiring predictable latency
k = 1-5	Near-FCFS	Minor optimization possible	General-purpose databases
k = 10-50	Bounded	Moderate batching benefits	OLTP with read-heavy workloads
k = ∞	No bound (starvation possible)	Maximum throughput	Only with additional safeguards

SLA-Driven Fairness:

Modern database systems often express fairness in terms of Service Level Agreements (SLAs):

p99 Latency Bound: 99% of transactions complete within X milliseconds
Maximum Lock Wait: No transaction waits more than Y seconds for a lock
Fairness Index Threshold: Jain's Fairness Index ≥ 0.9 across transaction classes

These SLAs can be translated into bypass bounds:

If max allowed wait = T seconds
And average lock hold time = H seconds
Then bypass bound k ≤ T / H

For example, if transactions must acquire locks within 5 seconds, and average lock hold time is 50ms, then k ≤ 100 bypasses.

Dynamic Bypass Adjustment:

Sophisticated systems dynamically adjust bypass bounds:

Low contention: Relax bypass bounds for throughput
High contention: Tighten bypass bounds to maintain SLAs
Per-transaction type: Different bypass bounds for different workload classes

Bypass Counting Requires Careful Bookkeeping

Implementing bypass bounds requires tracking how many times each waiting request has been bypassed. This adds overhead: each lock grant must update bypass counters for all waiting transactions on that resource. Systems balance this overhead against the fairness benefits.

Fairness in Reader-Writer Locks

The reader-writer lock problem exemplifies the tension between efficiency and fairness. Three primary strategies exist, each with distinct fairness implications:

Reader Preference (Also: Read-Biased)

Policy: When readers are active, new readers are immediately granted access. Writers must wait until all readers complete.

Algorithm:

Reader enters:
  if no writer holding or waiting:
    grant immediately
  else:
    wait for writer to complete
    
Writer enters:
  wait for all readers to complete
  acquire exclusive lock

Pros:

Maximum read concurrency
Simple implementation
Optimal for read-heavy workloads

Cons:

Writers starve — Continuous reader arrivals block writers indefinitely
Unsuitable for mixed workloads

Use when: Reads vastly outnumber writes and write latency is unimportant (e.g., read-only replicas).

Converting Mermaid diagram...

Measuring Fairness: Jain's Index

How do we quantitatively measure whether a system is fair? Jain's Fairness Index is a widely-used metric that provides a single number between 0 and 1 representing the fairness of resource allocation.

Definition:

For n users (transactions) each receiving allocation xᵢ:

              (Σxᵢ)²
J(x) = ─────────────────
         n × Σ(xᵢ²)

Properties:

J(x) = 1: Perfect fairness (all allocations equal)
J(x) = 1/n: Complete unfairness (one user gets everything)
Higher values indicate more equitable distribution

Jain's Fairness Index Examples
Scenario	Allocations	Index	Interpretation
Perfect fairness	[100, 100, 100, 100]	1.0	All transactions served equally
Good fairness	[90, 100, 110, 100]	0.998	Minor variations, acceptable
Moderate fairness	[50, 100, 100, 150]	0.94	Noticeable disparity
Poor fairness	[10, 100, 100, 190]	0.79	Significant starvation risk
Severe unfairness	[0, 100, 200, 100]	0.75	One transaction completely starved

Applying Jain's Index to Lock Management:

In a database context, xᵢ might represent:

Number of lock grants per transaction class
Inverse of wait time (1/wait_time)
Throughput of each transaction type

Example Calculation:

Consider three transaction types with measured wait times:

Type A: 10ms average wait
Type B: 15ms average wait
Type C: 500ms average wait

Using inverse wait times (higher = better allocation):

x₁ = 100, x₂ = 67, x₃ = 2

J = (100 + 67 + 2)² / (3 × (100² + 67² + 2²))
J = (169)² / (3 × (10000 + 4489 + 4))
J = 28561 / (3 × 14493)
J = 28561 / 43479
J ≈ 0.66

A fairness index of 0.66 indicates significant unfairness—Type C is being starved.

Target Thresholds for Fairness Index

Production databases typically target J ≥ 0.9 for acceptable fairness. Values below 0.8 usually trigger investigation for starvation issues. The index is especially useful for monitoring: a declining fairness index over time signals emerging starvation conditions.

Implementation Techniques for Fairness

Implementing fairness in a high-performance lock manager requires careful design. Here are the primary techniques used in production systems:

Fairness Implementation Strategies

•Ticket-Based Queuing — Each request receives a monotonically increasing ticket. Grants are issued in ticket order. Simple, effective, but strict FCFS may cause convoy effects.
•Priority Aging — Waiting transactions gradually increase in priority. Eventually, even low-priority transactions become high-priority and must be serviced. Prevents indefinite starvation of low-priority work.
•Wait-Time Thresholds — After waiting beyond a threshold, a transaction is moved to an expedited queue or given priority. Combines performance optimization with starvation prevention.
•Round-Robin by Transaction Class — Alternate between transaction types (e.g., readers, writers, different application modules). Ensures no class is systematically disadvantaged.
•Weighted Fair Queuing — Assign weights to transaction classes. Each class receives a fraction of lock grants proportional to its weight. Provides tunable fairness.
•Epoch-Based Batching — Process all requests from one time epoch before moving to the next. Provides bounded waiting while allowing batching within epochs.

priority_aging.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class PriorityAgingLockManager:
    BASE_PRIORITY_BOOST = 1
    AGING_INTERVAL_MS = 100
    MAX_WAIT_BEFORE_URGENT = 5000
    
    def aging_thread():
        """Background thread that ages waiting requests"""
        while running:
            sleep(AGING_INTERVAL_MS)
            
            for resource, queue in lock_queues.items():
                for request in queue:
                    wait_time = now() - request.start_time
                    
                    # Calculate dynamic priority boost
                    age_factor = wait_time / MAX_WAIT_BEFORE_URGENT
                    boost = BASE_PRIORITY_BOOST * (1 + age_factor^2)
                    
                    request.effective_priority = request.base_priority + boost
                    
                    # Urgent promotion if near timeout
                    if wait_time > MAX_WAIT_BEFORE_URGENT * 0.8:
                        request.effective_priority = URGENT_PRIORITY
                
                # Re-sort queue by effective priority
                queue.reheapify()
    
    def grant_next(resource):
        """Grant lock to highest effective priority requestor"""
        queue = lock_queues[resource]
        
        for request in queue.sorted_by_effective_priority():
            if is_compatible(request, current_holders[resource]):
                grant(request)
                queue.remove(request)
                return

Aging Prevents Priority Inversion

Priority aging addresses not just starvation but also priority inversion—where a high-priority transaction waits for a lower-priority one. By continuously boosting the priority of waiting transactions, the system naturally resolves inversions over time.

The Fairness-Performance Tradeoff

Fairness and throughput exist in tension. Optimizing for one often degrades the other. Understanding this tradeoff is essential for making informed design decisions.

Why the Tradeoff Exists:

Fairness Requires

•Processing requests in order (limits batching)
•Blocking new readers for waiting writers
•Tracking wait times and priority queues
•Potentially suboptimal lock sequences
•CPU overhead for queue management

Throughput Requires

•Batching compatible requests (improve cache locality)
•Maximizing reader concurrency
•Minimal bookkeeping overhead
•Opportunistic lock granting
•Simple data structures for speed

Fairness-Throughput Tradeoff Matrix
Policy	Fairness	Throughput	Best For
Strict FCFS	★★★★★	★★☆☆☆	Latency-critical, predictable workloads
Bounded bypass (k=10)	★★★★☆	★★★☆☆	General-purpose databases
Reader-preference	★★☆☆☆	★★★★★ (reads)	Read-heavy, write-tolerant
Priority with aging	★★★★☆	★★★★☆	Mixed workloads with priorities
Weighted fair queuing	★★★★☆	★★★★☆	Multi-tenant systems

Finding the Right Balance:

Characterize your workload: Read/write ratio, transaction duration distribution, criticality requirements
Define fairness SLAs: What latency bounds are acceptable? What fairness index is required?
Measure baseline: Test with different policies and measure both throughput and fairness metrics
Tune iteratively: Start with stricter fairness and relax only as throughput requirements demand
Monitor continuously: Fairness conditions change as workloads evolve; what works today may not work next month

The ideal policy is workload-dependent. A financial trading system might require near-perfect fairness at the cost of throughput, while a social media feed generator might tolerate unfairness for maximum read performance.

Summary: Fairness in Lock Management

We've explored fairness as the antidote to starvation—the property that ensures every transaction eventually receives the resources it needs. Let's consolidate the key concepts:

Key Takeaways

•Fairness guarantees eventual progress — Every valid lock request will be granted in finite time, preventing starvation.
•A hierarchy of fairness exists — From no guarantee, through eventual fairness, weak/strong fairness, bounded fairness, to strict FCFS.
•FCFS is the gold standard — Zero bypasses, perfect fairness, but may cause convoy effects that reduce throughput.
•Bypass bounds provide practical fairness — Allowing limited reordering balances fairness with performance optimization.
•Reader-writer policies must choose a bias — Reader-preference starves writers; writer-preference starves readers; fair locks balance both.
•Jain's Fairness Index quantifies equity — Values above 0.9 indicate acceptable fairness; declining values signal emerging starvation.
•Implementation techniques include aging and weighting — Priority aging ensures no request waits forever; weighted queuing allows tunable fairness.
•Fairness and throughput trade off — Stricter fairness typically reduces throughput; the right balance depends on workload characteristics.

What's Next:

With a solid understanding of fairness, we're ready to examine priority schemes—mechanisms that allow important transactions to receive preferential treatment while still maintaining fairness guarantees. We'll explore how priority can coexist with fairness through techniques like aging and bounded priority boosts.

Page Complete

You now understand fairness as a formal property of lock management systems—its definition, hierarchy, measurement, and implementation. This foundation prepares you to evaluate and design fair lock management policies for production database systems.

Fairness in Lock Management

The Price of Order

What You Will Learn

Formal Definition of Fairness

Formal Definition:

A lock manager L is said to be fair if for every transaction T and every lock request r made by T:

If T requests lock r at time t₀, then there exists a finite time t₁ > t₀ at which T is granted r, provided:

T does not voluntarily withdraw the request

T does not abort due to deadlock resolution

The resource remains in a lockable state

Components of a Fairness Definition
Component	Description	Why It Matters
Eventual Granting	Every valid request is eventually satisfied	Prevents indefinite waiting (starvation)
Request Ordering	Defines how requests are sequenced for service	Determines who gets access when resources free
Bounded Waiting	Specifies maximum wait time or bypasses	Distinguishes weak from strong fairness
Priority Handling	Defines interaction between fairness and priorities	Balances urgency against equity
Exception Cases	What conditions exempt fairness guarantees	Covers deadlock victims, timeouts, aborts

Fairness Is Not Equality

The Fairness Hierarchy

Fairness Guarantee Levels

•No Fairness Guarantee — The scheduler makes no promises about eventual service. Transactions may wait indefinitely. This is the default for many simple lock implementations.
•Eventual Fairness (Starvation-Freedom) — Every transaction will eventually get service, but no bound is specified. A transaction might wait microseconds or millennia.
•Weak Fairness — If a request is continuously enabled (could be granted), it will eventually be granted. This prevents starvation for requests that could always proceed.
•Strong Fairness — If a request is infinitely often enabled (could be granted infinitely often), it will eventually be granted. Handles intermittently available resources.
•Bounded Fairness — Every request will be granted within a specified bound: either a maximum wait time or a maximum number of bypasses by later requests.
•First-Come-First-Served (FCFS) — Requests are granted in exact arrival order. Zero bypasses. The gold standard for fairness, but potentially suboptimal for throughput.

Converting Mermaid diagram...

Detailed Analysis of Each Level:

3. Weak Fairness Formal definition: If a request r is continuously enabled from some time t onward, then r will eventually be granted.

"Continuously enabled" means: at every moment from t forward, granting r would not violate consistency.
This handles the case where a lock becomes and stays free.

4. Strong Fairness Formal definition: If a request r is infinitely often enabled, then r will eventually be granted.

Handles intermittent availability: a resource keeps becoming free and getting taken by others.
Stronger than weak fairness because it doesn't require continuous availability.

5. Bounded Fairness Adds quantitative guarantees:

Time-bounded: Wait time ≤ T milliseconds
Bypass-bounded: At most N later requests can be granted before this one
Critical for SLA-sensitive applications where latency guarantees matter.

Guarantees zero bypasses
May reduce throughput due to inefficient batching
Often approximated rather than strictly implemented

FCFS: The Gold Standard

How FCFS Works in Lock Management:

When a transaction requests a lock, it receives a ticket number (monotonically increasing)
When a lock becomes available, the transaction with the lowest ticket number among compatible waiters is granted the lock
No transaction with a higher ticket number can be granted while a lower-numbered transaction is waiting for a conflicting lock

fcfs_lock_manager.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class FCFSLockManager:
    ticket_counter = 0
    lock_queues = {}  # resource -> priority queue ordered by ticket
    
    def request_lock(transaction, resource, lock_type):
        ticket = atomic_increment(ticket_counter)
        
        request = LockRequest(
            transaction=transaction,
            resource=resource,
            type=lock_type,
            ticket=ticket,
            timestamp=now()
        )
        
        lock_queues[resource].enqueue(request)
        
        while not can_grant(request):
            wait()
        
        grant_lock(request)
    
    def can_grant(request):
        # Find all requests with lower ticket numbers
        earlier_requests = [r for r in lock_queues[request.resource] 
                          if r.ticket < request.ticket]
        
        # Check for conflicts with earlier requests
        for earlier in earlier_requests:
            if conflicts(earlier.type, request.type):
                return False
        
        # Check for conflicts with currently held locks
        for holder in current_holders[request.resource]:
            if conflicts(holder.type, request.type):
                return False
        
        return True

FCFS Guarantees:

Property	Guarantee
Starvation-freedom	✓ Absolute
Bounded waiting	✓ Bounded by queue length × max hold time
Bypass count	0 (strictly enforced)
Predictability	High (wait time correlates with queue position)

The Convoy Problem:

FCFS fairness comes with a significant performance cost: the convoy effect. When:

A slow transaction acquires a frequently-accessed lock
Fast transactions queue behind it
The slow transaction completes, releasing the lock
Fast transactions quickly complete and queue again
A new slow transaction arrives and acquires the lock
The convoy of fast transactions queues again

The result: fast transactions are forced to proceed at the pace of slow transactions, reducing overall throughput. This is the fundamental fairness-throughput tradeoff.

FCFS Is Rarely Strictly Implemented

Bypass Bounds and SLA Guarantees

Bypass Bound Definition:

A lock manager satisfies a bypass bound of k if, for any request R:

At most k requests arriving after R can be granted before R is granted
Once k bypasses occur, R must be granted before any additional requests

Example (k = 2):

Request order: R1, R2, R3, R4, R5 (all for same resource)
Allowed: Grant R3, then R2, then R1, then R4, then R5
        (R1 was bypassed 2 times: by R2 and R3)
Not allowed: Grant R4 before R1
             (R1 would be bypassed 3 times)

Bypass Bound Tradeoffs
Bypass Bound (k)	Fairness Level	Throughput Impact	Use Case
k = 0	Strict FCFS	May cause convoy effect	Critical systems requiring predictable latency
k = 1-5	Near-FCFS	Minor optimization possible	General-purpose databases
k = 10-50	Bounded	Moderate batching benefits	OLTP with read-heavy workloads
k = ∞	No bound (starvation possible)	Maximum throughput	Only with additional safeguards

SLA-Driven Fairness:

Modern database systems often express fairness in terms of Service Level Agreements (SLAs):

p99 Latency Bound: 99% of transactions complete within X milliseconds
Maximum Lock Wait: No transaction waits more than Y seconds for a lock
Fairness Index Threshold: Jain's Fairness Index ≥ 0.9 across transaction classes

These SLAs can be translated into bypass bounds:

If max allowed wait = T seconds
And average lock hold time = H seconds
Then bypass bound k ≤ T / H

For example, if transactions must acquire locks within 5 seconds, and average lock hold time is 50ms, then k ≤ 100 bypasses.

Dynamic Bypass Adjustment:

Sophisticated systems dynamically adjust bypass bounds:

Low contention: Relax bypass bounds for throughput
High contention: Tighten bypass bounds to maintain SLAs
Per-transaction type: Different bypass bounds for different workload classes

Bypass Counting Requires Careful Bookkeeping

Fairness in Reader-Writer Locks

The reader-writer lock problem exemplifies the tension between efficiency and fairness. Three primary strategies exist, each with distinct fairness implications:

Reader Preference (Also: Read-Biased)

Policy: When readers are active, new readers are immediately granted access. Writers must wait until all readers complete.

Algorithm:

Reader enters:
  if no writer holding or waiting:
    grant immediately
  else:
    wait for writer to complete
    
Writer enters:
  wait for all readers to complete
  acquire exclusive lock

Pros:

Maximum read concurrency
Simple implementation
Optimal for read-heavy workloads

Cons:

Writers starve — Continuous reader arrivals block writers indefinitely
Unsuitable for mixed workloads

Use when: Reads vastly outnumber writes and write latency is unimportant (e.g., read-only replicas).

Converting Mermaid diagram...

Measuring Fairness: Jain's Index

Definition:

For n users (transactions) each receiving allocation xᵢ:

              (Σxᵢ)²
J(x) = ─────────────────
         n × Σ(xᵢ²)

Properties:

J(x) = 1: Perfect fairness (all allocations equal)
J(x) = 1/n: Complete unfairness (one user gets everything)
Higher values indicate more equitable distribution

Jain's Fairness Index Examples
Scenario	Allocations	Index	Interpretation
Perfect fairness	[100, 100, 100, 100]	1.0	All transactions served equally
Good fairness	[90, 100, 110, 100]	0.998	Minor variations, acceptable
Moderate fairness	[50, 100, 100, 150]	0.94	Noticeable disparity
Poor fairness	[10, 100, 100, 190]	0.79	Significant starvation risk
Severe unfairness	[0, 100, 200, 100]	0.75	One transaction completely starved

Applying Jain's Index to Lock Management:

In a database context, xᵢ might represent:

Number of lock grants per transaction class
Inverse of wait time (1/wait_time)
Throughput of each transaction type

Example Calculation:

Consider three transaction types with measured wait times:

Type A: 10ms average wait
Type B: 15ms average wait
Type C: 500ms average wait

Using inverse wait times (higher = better allocation):

x₁ = 100, x₂ = 67, x₃ = 2

J = (100 + 67 + 2)² / (3 × (100² + 67² + 2²))
J = (169)² / (3 × (10000 + 4489 + 4))
J = 28561 / (3 × 14493)
J = 28561 / 43479
J ≈ 0.66

A fairness index of 0.66 indicates significant unfairness—Type C is being starved.

Target Thresholds for Fairness Index

Implementation Techniques for Fairness

Implementing fairness in a high-performance lock manager requires careful design. Here are the primary techniques used in production systems:

Fairness Implementation Strategies

•Ticket-Based Queuing — Each request receives a monotonically increasing ticket. Grants are issued in ticket order. Simple, effective, but strict FCFS may cause convoy effects.
•Priority Aging — Waiting transactions gradually increase in priority. Eventually, even low-priority transactions become high-priority and must be serviced. Prevents indefinite starvation of low-priority work.
•Wait-Time Thresholds — After waiting beyond a threshold, a transaction is moved to an expedited queue or given priority. Combines performance optimization with starvation prevention.
•Round-Robin by Transaction Class — Alternate between transaction types (e.g., readers, writers, different application modules). Ensures no class is systematically disadvantaged.
•Weighted Fair Queuing — Assign weights to transaction classes. Each class receives a fraction of lock grants proportional to its weight. Provides tunable fairness.
•Epoch-Based Batching — Process all requests from one time epoch before moving to the next. Provides bounded waiting while allowing batching within epochs.

priority_aging.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class PriorityAgingLockManager:
    BASE_PRIORITY_BOOST = 1
    AGING_INTERVAL_MS = 100
    MAX_WAIT_BEFORE_URGENT = 5000
    
    def aging_thread():
        """Background thread that ages waiting requests"""
        while running:
            sleep(AGING_INTERVAL_MS)
            
            for resource, queue in lock_queues.items():
                for request in queue:
                    wait_time = now() - request.start_time
                    
                    # Calculate dynamic priority boost
                    age_factor = wait_time / MAX_WAIT_BEFORE_URGENT
                    boost = BASE_PRIORITY_BOOST * (1 + age_factor^2)
                    
                    request.effective_priority = request.base_priority + boost
                    
                    # Urgent promotion if near timeout
                    if wait_time > MAX_WAIT_BEFORE_URGENT * 0.8:
                        request.effective_priority = URGENT_PRIORITY
                
                # Re-sort queue by effective priority
                queue.reheapify()
    
    def grant_next(resource):
        """Grant lock to highest effective priority requestor"""
        queue = lock_queues[resource]
        
        for request in queue.sorted_by_effective_priority():
            if is_compatible(request, current_holders[resource]):
                grant(request)
                queue.remove(request)
                return

Aging Prevents Priority Inversion

The Fairness-Performance Tradeoff

Fairness and throughput exist in tension. Optimizing for one often degrades the other. Understanding this tradeoff is essential for making informed design decisions.

Why the Tradeoff Exists:

Fairness Requires

•Processing requests in order (limits batching)
•Blocking new readers for waiting writers
•Tracking wait times and priority queues
•Potentially suboptimal lock sequences
•CPU overhead for queue management

Throughput Requires

•Batching compatible requests (improve cache locality)
•Maximizing reader concurrency
•Minimal bookkeeping overhead
•Opportunistic lock granting
•Simple data structures for speed

Fairness-Throughput Tradeoff Matrix
Policy	Fairness	Throughput	Best For
Strict FCFS	★★★★★	★★☆☆☆	Latency-critical, predictable workloads
Bounded bypass (k=10)	★★★★☆	★★★☆☆	General-purpose databases
Reader-preference	★★☆☆☆	★★★★★ (reads)	Read-heavy, write-tolerant
Priority with aging	★★★★☆	★★★★☆	Mixed workloads with priorities
Weighted fair queuing	★★★★☆	★★★★☆	Multi-tenant systems

Finding the Right Balance:

Characterize your workload: Read/write ratio, transaction duration distribution, criticality requirements
Define fairness SLAs: What latency bounds are acceptable? What fairness index is required?
Measure baseline: Test with different policies and measure both throughput and fairness metrics
Tune iteratively: Start with stricter fairness and relax only as throughput requirements demand
Monitor continuously: Fairness conditions change as workloads evolve; what works today may not work next month

Summary: Fairness in Lock Management

We've explored fairness as the antidote to starvation—the property that ensures every transaction eventually receives the resources it needs. Let's consolidate the key concepts:

Key Takeaways

•Fairness guarantees eventual progress — Every valid lock request will be granted in finite time, preventing starvation.
•A hierarchy of fairness exists — From no guarantee, through eventual fairness, weak/strong fairness, bounded fairness, to strict FCFS.
•FCFS is the gold standard — Zero bypasses, perfect fairness, but may cause convoy effects that reduce throughput.
•Bypass bounds provide practical fairness — Allowing limited reordering balances fairness with performance optimization.
•Reader-writer policies must choose a bias — Reader-preference starves writers; writer-preference starves readers; fair locks balance both.
•Jain's Fairness Index quantifies equity — Values above 0.9 indicate acceptable fairness; declining values signal emerging starvation.
•Implementation techniques include aging and weighting — Priority aging ensures no request waits forever; weighted queuing allows tunable fairness.
•Fairness and throughput trade off — Stricter fairness typically reduces throughput; the right balance depends on workload characteristics.

What's Next:

Page Complete