LRU and Clock Algorithms — Buffer Management in… | OneNoughtOne

0/131

Database Management SystemsBuffer Management

Buffer Management in Database Systems

LevelIntermediate

Duration60 mins

TopicBuffer Management

5 / 5

LRU and Clock Algorithms

The Workhorses of Page Replacement

Of all the page replacement algorithms developed over decades of computer science research, two have emerged as the dominant choices in production database systems: Least Recently Used (LRU) and Clock . LRU provides optimal recency-based replacement when overhead is acceptable. Clock approximates LRU with dramatically lower cost. Together, they form the foundation of page replacement in systems ranging from tiny embedded databases to planet-scale distributed systems. Understanding their implementation details, variations, and trade-offs is essential for anyone working with database internals.

What You Will Learn

By the end of this page, you will master the implementation details of LRU and Clock algorithms, understand the production variations used in real databases like PostgreSQL and MySQL, and know how to tune these algorithms for different workload characteristics.

LRU Implementation Strategies

Implementing LRU efficiently requires careful data structure design. The core challenge is supporting two operations efficiently: Record access: Move page to "most recently used" position — must be O(1) Find victim: Return the "least recently used" page — must be O(1) Several implementation strategies achieve these requirements:

Strategy 1: Doubly-Linked List + Hash Map The classic implementation uses two data structures in tandem: A doubly-linked list maintains pages in recency order (head = MRU, tail = LRU) A hash map provides O(1) lookup from page ID to list node This achieves O(1) for both operations: access moves a node (O(1) with direct pointer), and victim selection returns the tail (O(1)).

lru_classic.cpp
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
// Classic LRU with doubly-linked list + hash map
 
class LRUList {
    struct Node {
        FrameId frame_id;
        Node* prev;
        Node* next;
    };
    
    Node* head;  // Most recently used
    Node* tail;  // Least recently used
    unordered_map<FrameId, Node*> node_map;
    size_t size;
    mutex latch;
    
public:
    LRUList() : head(nullptr), tail(nullptr), size(0) {}
    
    // Move or add frame to MRU position (head)
    void touch(FrameId frame_id) {
        lock_guard<mutex> guard(latch);
        
        auto it = node_map.find(frame_id);
        if (it != node_map.end()) {
            // Already in list - move to head
            Node* node = it->second;
            removeFromList(node);
            addToHead(node);
        } else {
            // New frame - create node and add to head
            Node* node = new Node{frame_id, nullptr, nullptr};
            node_map[frame_id] = node;
            addToHead(node);
            size++;
        }
    }
    
    // Get LRU frame (don't remove - caller decides)
    FrameId getLRU() {
        lock_guard<mutex> guard(latch);
        return (tail != nullptr) ? tail->frame_id : INVALID_FRAME_ID;
    }
    
    // Remove a specific frame (when pinned or evicted)
    void remove(FrameId frame_id) {
        lock_guard<mutex> guard(latch);
        
        auto it = node_map.find(frame_id);
        if (it != node_map.end()) {
            Node* node = it->second;
            removeFromList(node);
            node_map.erase(it);
            delete node;
            size--;
        }
    }
    
private:
    void addToHead(Node* node) {
        node->prev = nullptr;
        node->next = head;
        if (head) head->prev = node;
        head = node;
        if (!tail) tail = node;
    }
    
    void removeFromList(Node* node) {
        if (node->prev) node->prev->next = node->next;
        else head = node->next;
        
        if (node->next) node->next->prev = node->prev;
        else tail = node->prev;
    }
};

Strategy 2: Timestamp-Based LRU Instead of maintaining explicit ordering, each frame stores a timestamp of its last access. Victim selection scans for the frame with the oldest timestamp. Access: O(1) — just update the timestamp Victim selection: O(n) — must scan all frames This trades faster access tracking for slower victim selection. It's useful when accesses vastly outnumber evictions.

LRU Implementation Trade-offs
Strategy	Access Cost	Victim Cost	Memory Overhead	Contention
List + HashMap	O(1)	O(1)	~24 bytes/frame	High (list manipulation)
Timestamp	O(1)	O(n)	8 bytes/frame	Low (atomic timestamp)
Approximate (sampling)	O(1)	O(k) samples	8 bytes/frame	Very low

LRU Concurrency Challenges

Pure LRU becomes a significant bottleneck in multi-core systems. Every page access requires updating the LRU list, and this update must be synchronized across threads. With dozens or hundreds of cores, the LRU list's mutex becomes a severe contention point.

The concurrency problem: Thread A accesses page P1 \to tries to move P1 to head \to acquires LRU mutex Threads B, C, D also access pages \to all wait for mutex Under high concurrency, threads spend more time waiting for the mutex than doing useful work Solutions to LRU concurrency:

Concurrency Solutions

•Multiple LRU Lists (Partitioning) — Divide the buffer pool into partitions, each with its own LRU list. Access only contends within partition.
•Batched Updates — Threads record accesses in thread-local buffers; background thread periodically applies batched updates to LRU list.
•Lock-Free Data Structures — Use compare-and-swap operations instead of mutexes; complex to implement correctly.
•Approximate LRU (Switch to Clock) — Accept lower precision for dramatically lower overhead; this is the most common solution.

partitioned_lru.cpp
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
// Partitioned LRU to reduce contention
 
class PartitionedLRU {
    static const size_t NUM_PARTITIONS = 64;  // Often matches core count
    LRUList partitions[NUM_PARTITIONS];
    
    size_t getPartition(FrameId frame_id) {
        // Simple hash-based partitioning
        return frame_id % NUM_PARTITIONS;
    }
    
public:
    void touch(FrameId frame_id) {
        size_t p = getPartition(frame_id);
        partitions[p].touch(frame_id);
        // Only contends with accesses to same partition
    }
    
    FrameId getVictim() {
        // Try each partition until we find a victim
        // More sophisticated: select partition with oldest LRU
        for (size_t i = 0; i < NUM_PARTITIONS; i++) {
            FrameId victim = partitions[i].getLRU();
            if (victim != INVALID_FRAME_ID) {
                return victim;
            }
        }
        return INVALID_FRAME_ID;
    }
    
    void remove(FrameId frame_id) {
        size_t p = getPartition(frame_id);
        partitions[p].remove(frame_id);
    }
};

Why Exact LRU Is Rare in Production

The overhead of maintaining exact LRU order is rarely justified. Modern databases almost universally use Clock or LRU approximations. The hit rate difference is typically 1-5%, but the throughput difference under concurrency can be 10x or more.

Clock Algorithm Deep Dive

The Clock algorithm (also called Second-Chance or Not Recently Used) is the dominant replacement algorithm in production databases due to its excellent performance-to-overhead ratio. Let's examine it in detail.

The fundamental insight: Clock replaces the expensive "move to head" operation with a cheap "set bit" operation. Instead of tracking exact recency order, it only distinguishes between "recently used" and "not recently used." This binary distinction, surprisingly, captures most of LRU's benefit. How Clock maintains state: Each frame has a reference bit (1 bit) A clock hand (integer) points to the current position Frames are conceptually arranged in a circle

clock_detailed.cpp
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
// Detailed Clock algorithm implementation
 
class ClockReplacer {
private:
    struct FrameState {
        bool in_pool;     // Is this frame in the replacement pool?
        bool ref_bit;     // Has this frame been accessed recently?
    };
    
    vector<FrameState> frames;
    size_t capacity;
    atomic<size_t> clock_hand;  // Atomic for better concurrency
    size_t num_in_pool;        // Count of replaceable frames
    mutex latch;               // Protects in_pool and num_in_pool
    
public:
    ClockReplacer(size_t capacity) 
        : frames(capacity), capacity(capacity), 
          clock_hand(0), num_in_pool(0) {
        for (auto& f : frames) {
            f.in_pool = false;
            f.ref_bit = false;
        }
    }
    
    // Called when a frame is accessed
    // Note: This can be lockless! Just an atomic store.
    void recordAccess(FrameId frame_id) {
        // Simple atomic store - no locking required
        frames[frame_id].ref_bit = true;
    }
    
    // Find a victim for eviction
    FrameId selectVictim() {
        lock_guard<mutex> guard(latch);
        
        if (num_in_pool == 0) {
            return INVALID_FRAME_ID;
        }
        
        // Scan until we find a victim
        // Worst case: 2 full rotations (first clears all ref bits)
        size_t scanned = 0;
        size_t max_scans = 2 * capacity;
        
        while (scanned < max_scans) {
            size_t hand = clock_hand.load();
            FrameState& frame = frames[hand];
            
            // Advance clock hand first (for next iteration)
            clock_hand.store((hand + 1) % capacity);
            
            if (!frame.in_pool) {
                // Frame is pinned - skip it
                scanned++;
                continue;
            }
            
            if (frame.ref_bit) {
                // Recently used - give it a second chance
                frame.ref_bit = false;
                scanned++;
                continue;
            }
            
            // Found victim: in_pool == true && ref_bit == false
            frame.in_pool = false;
            num_in_pool--;
            return hand;
        }
        
        // Shouldn't happen if num_in_pool > 0
        return INVALID_FRAME_ID;
    }
    
    // Add frame to replacement pool (when unpinned)
    void unpin(FrameId frame_id) {
        lock_guard<mutex> guard(latch);
        if (!frames[frame_id].in_pool) {
            frames[frame_id].in_pool = true;
            num_in_pool++;
            // Note: ref_bit is NOT set here
            // It will be set on next access
        }
    }
    
    // Remove from replacement pool (when pinned)
    void pin(FrameId frame_id) {
        lock_guard<mutex> guard(latch);
        if (frames[frame_id].in_pool) {
            frames[frame_id].in_pool = false;
            num_in_pool--;
        }
    }
};

Clock's efficiency advantages: Access recording is lockless: Setting ref_bit is an atomic operation—no mutex required No list manipulation: No pointer updates on every access Cache-friendly: Frame states are contiguous in memory Bounded scan time: At most 2N frames scanned (one to clear bits, one to find victim) Low memory overhead: 2 bits per frame (vs. ~24 bytes for LRU list nodes)

Why 'Second Chance'?

The name 'Second Chance' comes from the algorithm's behavior: a frame with ref_bit=1 isn't evicted immediately. Instead, its bit is cleared and the clock moves on. The frame gets a 'second chance' to be accessed before the clock returns. Only frames not accessed during a full rotation are evicted.

Clock Variants and Enhancements

Production databases often use enhanced variants of the basic Clock algorithm to address specific workload characteristics:

Enhanced Clock (Two-handed Clock): Uses two clock hands instead of one: Leading hand: Clears reference bits as it sweeps Trailing hand: (Following at distance D) Evicts frames with cleared bits This provides more time for pages to prove their worth, reducing the chance of evicting truly hot pages.

Clock with Priority Classes: Different pages get different treatment: Hot pages (frequently accessed): Require multiple passes to clear all priority bits Cold pages (infrequently accessed): Evicted after a single pass This is often implemented using multiple reference bits or a reference counter instead of a single bit.

enhanced_clock.cpp
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
// Enhanced Clock with reference counter
 
class EnhancedClockReplacer {
    struct FrameState {
        bool in_pool;
        uint8_t ref_count;  // 0-3 instead of single bit
    };
    
    static const uint8_t MAX_REF_COUNT = 3;
    vector<FrameState> frames;
    size_t clock_hand;
    
public:
    // Increment reference count (capped at MAX)
    void recordAccess(FrameId frame_id) {
        auto& ref = frames[frame_id].ref_count;
        if (ref < MAX_REF_COUNT) {
            ref++;  // Atomic increment if needed
        }
    }
    
    FrameId selectVictim() {
        while (true) {
            FrameState& frame = frames[clock_hand];
            
            if (frame.in_pool) {
                if (frame.ref_count == 0) {
                    // Found victim
                    frame.in_pool = false;
                    return clock_hand;
                } else {
                    // Decrement and continue
                    frame.ref_count--;
                }
            }
            
            clock_hand = (clock_hand + 1) % frames.size();
        }
    }
};
 
// Clock with scan resistance (MySQL InnoDB-inspired)
class ScanResistantClock {
    struct FrameState {
        bool in_pool;
        bool ref_bit;
        bool is_young;       // In the "hot" section
        Timestamp last_access;
    };
    
    Duration young_threshold = 1s;  // innodb_old_blocks_time
    
public:
    void recordAccess(FrameId frame_id, bool is_new_page) {
        auto& frame = frames[frame_id];
        frame.ref_bit = true;
        
        Timestamp now = getCurrentTime();
        
        if (is_new_page) {
            // New pages start as "old" - not immediately promoted
            frame.is_young = false;
            frame.last_access = now;
        } else if (!frame.is_young) {
            // Page in "old" section - check if it should be promoted
            if (now - frame.last_access > young_threshold) {
                // Accessed again after threshold - promote to young
                frame.is_young = true;
            }
            frame.last_access = now;
        }
        // Pages already young just update ref_bit
    }
    
    FrameId selectVictim() {
        // First try to evict from "old" pages
        // Only evict "young" pages if no old pages available
        // This protects hot data from sequential scans
        
        // Implementation: scan old pages first, then young
        // Or: maintain separate lists for young/old
    }
};

Clock Variants Comparison
Variant	Key Feature	Use Case
Basic Clock	Single ref bit	Simple systems, low contention
Two-handed Clock	Leading/trailing hands	Better approximation of LRU
Multi-bit Clock	Reference counter	Distinguishing hot from warm pages
Scan-resistant Clock	Young/old sections	Mixed OLTP/scan workloads

PostgreSQL's Clock Implementation

PostgreSQL uses a Clock-based replacement algorithm with several interesting refinements. Understanding its implementation provides insight into production-grade buffer management.

PostgreSQL's buffer management architecture: Buffer pool is stored in shared memory (shared_buffers) Each buffer has a buf_hdr containing state (including a usage_count) Uses a usage count (0-5) instead of a single reference bit The Clock algorithm is called the "buffer replacement strategy"

postgresql_clock.c
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
// PostgreSQL-style Clock implementation (simplified)
 
#define BM_MAX_USAGE_COUNT 5
 
typedef struct BufferDesc {
    int32 buf_id;
    uint32 state;           // Includes usage_count, refcount, flags
    pg_atomic_uint32 state_spinlock;
    
    // usage_count is stored in state bits
    // Extract: (state >> BUF_USAGE_COUNT_SHIFT) & BUF_USAGE_COUNT_MASK
} BufferDesc;
 
// Called when buffer is accessed
void PinBuffer_common(BufferDesc *buf) {
    for (;;) {
        uint32 old_state = pg_atomic_read_u32(&buf->state);
        uint32 new_state = old_state;
        
        // Increment refcount
        new_state += BUF_REFCOUNT_ONE;
        
        // Increment usage_count if not at max
        if (BUF_STATE_GET_USAGECOUNT(new_state) < BM_MAX_USAGE_COUNT) {
            new_state += BUF_USAGECOUNT_ONE;
        }
        
        // Atomic compare-and-swap
        if (pg_atomic_compare_exchange_u32(&buf->state, 
                                           &old_state, new_state)) {
            break;
        }
        // Retry if state changed
    }
}
 
// Find a buffer to evict (ClockSweep)
BufferDesc* StrategyGetBuffer(BufferStrategyControl *strategy) {
    // Try freelist first
    if (strategy->firstFreeBuffer >= 0) {
        return GetBufferFromFreeList(strategy);
    }
    
    // Clock sweep
    int tries = NBuffers * 2;  // Avoid infinite loop
    
    while (tries > 0) {
        BufferDesc *buf = GetBufferDescriptor(strategy->nextVictimBuffer);
        
        // Advance clock hand
        strategy->nextVictimBuffer = 
            (strategy->nextVictimBuffer + 1) % NBuffers;
        
        // Try to victimize this buffer
        uint32 state = LockBufHdr(buf);
        
        // Skip if pinned
        if (BUF_STATE_GET_REFCOUNT(state) > 0) {
            UnlockBufHdr(buf, state);
            tries--;
            continue;
        }
        
        // Check usage count
        uint32 usage_count = BUF_STATE_GET_USAGECOUNT(state);
        
        if (usage_count > 0) {
            // Decrement and continue searching
            state -= BUF_USAGECOUNT_ONE;
            UnlockBufHdr(buf, state);
            tries--;
            continue;
        }
        
        // Found victim: refcount == 0 && usage_count == 0
        return buf;
    }
    
    // No victim found - all buffers pinned
    elog(ERROR, "no unpinned buffers available");
    return NULL;
}

PostgreSQL's Usage Count

PostgreSQL's usage_count (0-5) provides more granularity than a single bit. A page that's accessed repeatedly accumulates a higher usage_count, requiring multiple Clock passes to evict. This approximates LRU-K behavior without the complexity of tracking access timestamps.

MySQL InnoDB's LRU Implementation

MySQL InnoDB uses a modified LRU algorithm with explicit protections against scan pollution. Its implementation is more complex than PostgreSQL's Clock but provides better scan resistance.

InnoDB's LRU structure: The LRU list is a doubly-linked list of buffer pages Divided into two sublists: young (head, ~5/8) and old (tail, ~3/8) New pages enter at the old/young boundary (3/8 from tail) Pages must be accessed again after innodb_old_blocks_time to move to young The key insight: Sequential scan pages enter the old sublist. If the scan continues without re-accessing pages, they remain in old and get evicted first. Hot OLTP data in the young sublist is protected.

innodb_lru.cpp
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
// InnoDB-style LRU with young/old sublists (conceptual)
 
class InnoDBLRU {
    struct BufferPage {
        PageId page_id;
        BufferPage* prev;
        BufferPage* next;
        Timestamp access_time;
        bool is_young;  // In young sublist
    };
    
    BufferPage* lru_head;  // Head = most recently used in young
    BufferPage* old_head;  // Start of old sublist
    BufferPage* lru_tail;  // Tail = least recently used in old
    
    Duration old_blocks_time;  // innodb_old_blocks_time (default 1000ms)
    double old_ratio = 0.375;  // 3/8 for old sublist
    
public:
    // Insert new page at old/young boundary
    void insertNewPage(BufferPage* page) {
        page->is_young = false;
        page->access_time = currentTime();
        
        // Insert just before old_head (at boundary)
        insertBefore(old_head, page);
    }
    
    // Handle page access
    void accessPage(BufferPage* page) {
        Timestamp now = currentTime();
        
        if (page->is_young) {
            // Already in young sublist - move to head if not already there
            if (page != lru_head) {
                removeFromList(page);
                insertAtHead(page);
            }
            page->access_time = now;
            
        } else {
            // In old sublist - check if should promote
            Duration time_since_first = now - page->access_time;
            
            if (time_since_first > old_blocks_time) {
                // Accessed again after threshold - promote to young
                removeFromList(page);
                page->is_young = true;
                insertAtHead(page);
            }
            // If accessed within old_blocks_time, don't promote
            // This prevents read-ahead and scans from polluting young
            
            page->access_time = now;
        }
    }
    
    // Get victim for eviction (from tail of old sublist)
    BufferPage* getVictim() {
        // Scan from tail looking for unpinned page
        BufferPage* candidate = lru_tail;
        
        while (candidate != nullptr) {
            if (!candidate->isPinned()) {
                return candidate;
            }
            candidate = candidate->prev;
            
            // Prefer victims from old sublist
            if (candidate == old_head) {
                // Reached young sublist - ideally don't evict from here
                // But may need to if old is all pinned
            }
        }
        
        return nullptr;  // All pages pinned
    }
    
    // Adjust sublist sizes after operations
    void rebalance() {
        // Ensure old sublist maintains target ratio
        size_t total = getTotalPageCount();
        size_t target_old = total * old_ratio;
        size_t current_old = getOldSublistCount();
        
        while (current_old < target_old && lru_head != old_head) {
            // Move pages from young to old
            moveLastYoungToOld();
            current_old++;
        }
    }
};

InnoDB Buffer Pool Configuration Parameters
Parameter	Default	Description
innodb_buffer_pool_size	128MB	Total buffer pool memory
innodb_buffer_pool_instances	8 (if > 1GB)	Number of buffer pool partitions
innodb_old_blocks_pct	37 (3/8)	Percentage for old sublist
innodb_old_blocks_time	1000 (ms)	Time before promoting to young
innodb_lru_scan_depth	1024	Pages scanned for flushing per second

Tuning LRU and Clock Algorithms

While LRU and Clock algorithms are largely self-tuning, understanding key tuning parameters helps optimize performance for specific workloads.

Key Tuning Considerations

•Buffer pool size — The most impactful setting. Larger pools cache more data, reducing I/O. Size to fit the working set if possible.
•Buffer pool instances (MySQL) — More instances reduce contention but add overhead. Match to core count for high-concurrency systems.
•Old blocks time (MySQL) — Higher values protect against scan pollution more aggressively but may delay promotion of legitimately hot pages.
•Usage count max (PostgreSQL concept) — Higher values require more passes to evict, favoring very hot pages. Default of 5 is usually appropriate.
•Background flusher settings — Affect how aggressively dirty pages are written, which impacts eviction efficiency.

Workload-specific tuning: For OLTP workloads: Maximize buffer pool size (often 70-80% of RAM) Keep old_blocks_time at default or higher to protect against occasional scans Use multiple buffer pool instances for concurrency For analytical/scan workloads: Buffer pool may not help if data doesn't repeat Consider reducing old_blocks_time to allow scan pages to age out faster Sequential read optimizations (prefetching) matter more than replacement For mixed workloads: Default settings usually work well Monitor hit ratios for both OLTP and analytical queries Consider separate buffer pools for different tables if system supports it

Monitoring for Tuning Decisions

Before tuning, gather metrics: buffer pool hit ratio, pages read/written per second, evictions from young vs. old sublists. In MySQL, SHOW ENGINE INNODB STATUS provides buffer pool statistics. In PostgreSQL, enable pg_stat_statements and monitor pg_statio_user_tables .

Database Management SystemsBuffer Management

Buffer Management in Database Systems

LevelIntermediate

Duration60 mins

TopicBuffer Management

5 / 5

LRU and Clock Algorithms

The Workhorses of Page Replacement

Of all the page replacement algorithms developed over decades of computer science research, two have emerged as the dominant choices in production database systems: Least Recently Used (LRU) and Clock . LRU provides optimal recency-based replacement when overhead is acceptable. Clock approximates LRU with dramatically lower cost. Together, they form the foundation of page replacement in systems ranging from tiny embedded databases to planet-scale distributed systems. Understanding their implementation details, variations, and trade-offs is essential for anyone working with database internals.

What You Will Learn

By the end of this page, you will master the implementation details of LRU and Clock algorithms, understand the production variations used in real databases like PostgreSQL and MySQL, and know how to tune these algorithms for different workload characteristics.

LRU Implementation Strategies

Implementing LRU efficiently requires careful data structure design. The core challenge is supporting two operations efficiently: Record access: Move page to "most recently used" position — must be O(1) Find victim: Return the "least recently used" page — must be O(1) Several implementation strategies achieve these requirements:

Strategy 1: Doubly-Linked List + Hash Map The classic implementation uses two data structures in tandem: A doubly-linked list maintains pages in recency order (head = MRU, tail = LRU) A hash map provides O(1) lookup from page ID to list node This achieves O(1) for both operations: access moves a node (O(1) with direct pointer), and victim selection returns the tail (O(1)).

lru_classic.cpp
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
// Classic LRU with doubly-linked list + hash map
 
class LRUList {
    struct Node {
        FrameId frame_id;
        Node* prev;
        Node* next;
    };
    
    Node* head;  // Most recently used
    Node* tail;  // Least recently used
    unordered_map<FrameId, Node*> node_map;
    size_t size;
    mutex latch;
    
public:
    LRUList() : head(nullptr), tail(nullptr), size(0) {}
    
    // Move or add frame to MRU position (head)
    void touch(FrameId frame_id) {
        lock_guard<mutex> guard(latch);
        
        auto it = node_map.find(frame_id);
        if (it != node_map.end()) {
            // Already in list - move to head
            Node* node = it->second;
            removeFromList(node);
            addToHead(node);
        } else {
            // New frame - create node and add to head
            Node* node = new Node{frame_id, nullptr, nullptr};
            node_map[frame_id] = node;
            addToHead(node);
            size++;
        }
    }
    
    // Get LRU frame (don't remove - caller decides)
    FrameId getLRU() {
        lock_guard<mutex> guard(latch);
        return (tail != nullptr) ? tail->frame_id : INVALID_FRAME_ID;
    }
    
    // Remove a specific frame (when pinned or evicted)
    void remove(FrameId frame_id) {
        lock_guard<mutex> guard(latch);
        
        auto it = node_map.find(frame_id);
        if (it != node_map.end()) {
            Node* node = it->second;
            removeFromList(node);
            node_map.erase(it);
            delete node;
            size--;
        }
    }
    
private:
    void addToHead(Node* node) {
        node->prev = nullptr;
        node->next = head;
        if (head) head->prev = node;
        head = node;
        if (!tail) tail = node;
    }
    
    void removeFromList(Node* node) {
        if (node->prev) node->prev->next = node->next;
        else head = node->next;
        
        if (node->next) node->next->prev = node->prev;
        else tail = node->prev;
    }
};

Strategy 2: Timestamp-Based LRU Instead of maintaining explicit ordering, each frame stores a timestamp of its last access. Victim selection scans for the frame with the oldest timestamp. Access: O(1) — just update the timestamp Victim selection: O(n) — must scan all frames This trades faster access tracking for slower victim selection. It's useful when accesses vastly outnumber evictions.

LRU Implementation Trade-offs
Strategy	Access Cost	Victim Cost	Memory Overhead	Contention
List + HashMap	O(1)	O(1)	~24 bytes/frame	High (list manipulation)
Timestamp	O(1)	O(n)	8 bytes/frame	Low (atomic timestamp)
Approximate (sampling)	O(1)	O(k) samples	8 bytes/frame	Very low

LRU Concurrency Challenges

Pure LRU becomes a significant bottleneck in multi-core systems. Every page access requires updating the LRU list, and this update must be synchronized across threads. With dozens or hundreds of cores, the LRU list's mutex becomes a severe contention point.

The concurrency problem: Thread A accesses page P1 \to tries to move P1 to head \to acquires LRU mutex Threads B, C, D also access pages \to all wait for mutex Under high concurrency, threads spend more time waiting for the mutex than doing useful work Solutions to LRU concurrency:

Concurrency Solutions

•Multiple LRU Lists (Partitioning) — Divide the buffer pool into partitions, each with its own LRU list. Access only contends within partition.
•Batched Updates — Threads record accesses in thread-local buffers; background thread periodically applies batched updates to LRU list.
•Lock-Free Data Structures — Use compare-and-swap operations instead of mutexes; complex to implement correctly.
•Approximate LRU (Switch to Clock) — Accept lower precision for dramatically lower overhead; this is the most common solution.

partitioned_lru.cpp
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
// Partitioned LRU to reduce contention
 
class PartitionedLRU {
    static const size_t NUM_PARTITIONS = 64;  // Often matches core count
    LRUList partitions[NUM_PARTITIONS];
    
    size_t getPartition(FrameId frame_id) {
        // Simple hash-based partitioning
        return frame_id % NUM_PARTITIONS;
    }
    
public:
    void touch(FrameId frame_id) {
        size_t p = getPartition(frame_id);
        partitions[p].touch(frame_id);
        // Only contends with accesses to same partition
    }
    
    FrameId getVictim() {
        // Try each partition until we find a victim
        // More sophisticated: select partition with oldest LRU
        for (size_t i = 0; i < NUM_PARTITIONS; i++) {
            FrameId victim = partitions[i].getLRU();
            if (victim != INVALID_FRAME_ID) {
                return victim;
            }
        }
        return INVALID_FRAME_ID;
    }
    
    void remove(FrameId frame_id) {
        size_t p = getPartition(frame_id);
        partitions[p].remove(frame_id);
    }
};

Why Exact LRU Is Rare in Production

The overhead of maintaining exact LRU order is rarely justified. Modern databases almost universally use Clock or LRU approximations. The hit rate difference is typically 1-5%, but the throughput difference under concurrency can be 10x or more.

Clock Algorithm Deep Dive

The Clock algorithm (also called Second-Chance or Not Recently Used) is the dominant replacement algorithm in production databases due to its excellent performance-to-overhead ratio. Let's examine it in detail.

The fundamental insight: Clock replaces the expensive "move to head" operation with a cheap "set bit" operation. Instead of tracking exact recency order, it only distinguishes between "recently used" and "not recently used." This binary distinction, surprisingly, captures most of LRU's benefit. How Clock maintains state: Each frame has a reference bit (1 bit) A clock hand (integer) points to the current position Frames are conceptually arranged in a circle

clock_detailed.cpp
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
// Detailed Clock algorithm implementation
 
class ClockReplacer {
private:
    struct FrameState {
        bool in_pool;     // Is this frame in the replacement pool?
        bool ref_bit;     // Has this frame been accessed recently?
    };
    
    vector<FrameState> frames;
    size_t capacity;
    atomic<size_t> clock_hand;  // Atomic for better concurrency
    size_t num_in_pool;        // Count of replaceable frames
    mutex latch;               // Protects in_pool and num_in_pool
    
public:
    ClockReplacer(size_t capacity) 
        : frames(capacity), capacity(capacity), 
          clock_hand(0), num_in_pool(0) {
        for (auto& f : frames) {
            f.in_pool = false;
            f.ref_bit = false;
        }
    }
    
    // Called when a frame is accessed
    // Note: This can be lockless! Just an atomic store.
    void recordAccess(FrameId frame_id) {
        // Simple atomic store - no locking required
        frames[frame_id].ref_bit = true;
    }
    
    // Find a victim for eviction
    FrameId selectVictim() {
        lock_guard<mutex> guard(latch);
        
        if (num_in_pool == 0) {
            return INVALID_FRAME_ID;
        }
        
        // Scan until we find a victim
        // Worst case: 2 full rotations (first clears all ref bits)
        size_t scanned = 0;
        size_t max_scans = 2 * capacity;
        
        while (scanned < max_scans) {
            size_t hand = clock_hand.load();
            FrameState& frame = frames[hand];
            
            // Advance clock hand first (for next iteration)
            clock_hand.store((hand + 1) % capacity);
            
            if (!frame.in_pool) {
                // Frame is pinned - skip it
                scanned++;
                continue;
            }
            
            if (frame.ref_bit) {
                // Recently used - give it a second chance
                frame.ref_bit = false;
                scanned++;
                continue;
            }
            
            // Found victim: in_pool == true && ref_bit == false
            frame.in_pool = false;
            num_in_pool--;
            return hand;
        }
        
        // Shouldn't happen if num_in_pool > 0
        return INVALID_FRAME_ID;
    }
    
    // Add frame to replacement pool (when unpinned)
    void unpin(FrameId frame_id) {
        lock_guard<mutex> guard(latch);
        if (!frames[frame_id].in_pool) {
            frames[frame_id].in_pool = true;
            num_in_pool++;
            // Note: ref_bit is NOT set here
            // It will be set on next access
        }
    }
    
    // Remove from replacement pool (when pinned)
    void pin(FrameId frame_id) {
        lock_guard<mutex> guard(latch);
        if (frames[frame_id].in_pool) {
            frames[frame_id].in_pool = false;
            num_in_pool--;
        }
    }
};

Clock's efficiency advantages: Access recording is lockless: Setting ref_bit is an atomic operation—no mutex required No list manipulation: No pointer updates on every access Cache-friendly: Frame states are contiguous in memory Bounded scan time: At most 2N frames scanned (one to clear bits, one to find victim) Low memory overhead: 2 bits per frame (vs. ~24 bytes for LRU list nodes)

Why 'Second Chance'?

The name 'Second Chance' comes from the algorithm's behavior: a frame with ref_bit=1 isn't evicted immediately. Instead, its bit is cleared and the clock moves on. The frame gets a 'second chance' to be accessed before the clock returns. Only frames not accessed during a full rotation are evicted.

Clock Variants and Enhancements

Production databases often use enhanced variants of the basic Clock algorithm to address specific workload characteristics:

Enhanced Clock (Two-handed Clock): Uses two clock hands instead of one: Leading hand: Clears reference bits as it sweeps Trailing hand: (Following at distance D) Evicts frames with cleared bits This provides more time for pages to prove their worth, reducing the chance of evicting truly hot pages.

Clock with Priority Classes: Different pages get different treatment: Hot pages (frequently accessed): Require multiple passes to clear all priority bits Cold pages (infrequently accessed): Evicted after a single pass This is often implemented using multiple reference bits or a reference counter instead of a single bit.

enhanced_clock.cpp
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
// Enhanced Clock with reference counter
 
class EnhancedClockReplacer {
    struct FrameState {
        bool in_pool;
        uint8_t ref_count;  // 0-3 instead of single bit
    };
    
    static const uint8_t MAX_REF_COUNT = 3;
    vector<FrameState> frames;
    size_t clock_hand;
    
public:
    // Increment reference count (capped at MAX)
    void recordAccess(FrameId frame_id) {
        auto& ref = frames[frame_id].ref_count;
        if (ref < MAX_REF_COUNT) {
            ref++;  // Atomic increment if needed
        }
    }
    
    FrameId selectVictim() {
        while (true) {
            FrameState& frame = frames[clock_hand];
            
            if (frame.in_pool) {
                if (frame.ref_count == 0) {
                    // Found victim
                    frame.in_pool = false;
                    return clock_hand;
                } else {
                    // Decrement and continue
                    frame.ref_count--;
                }
            }
            
            clock_hand = (clock_hand + 1) % frames.size();
        }
    }
};
 
// Clock with scan resistance (MySQL InnoDB-inspired)
class ScanResistantClock {
    struct FrameState {
        bool in_pool;
        bool ref_bit;
        bool is_young;       // In the "hot" section
        Timestamp last_access;
    };
    
    Duration young_threshold = 1s;  // innodb_old_blocks_time
    
public:
    void recordAccess(FrameId frame_id, bool is_new_page) {
        auto& frame = frames[frame_id];
        frame.ref_bit = true;
        
        Timestamp now = getCurrentTime();
        
        if (is_new_page) {
            // New pages start as "old" - not immediately promoted
            frame.is_young = false;
            frame.last_access = now;
        } else if (!frame.is_young) {
            // Page in "old" section - check if it should be promoted
            if (now - frame.last_access > young_threshold) {
                // Accessed again after threshold - promote to young
                frame.is_young = true;
            }
            frame.last_access = now;
        }
        // Pages already young just update ref_bit
    }
    
    FrameId selectVictim() {
        // First try to evict from "old" pages
        // Only evict "young" pages if no old pages available
        // This protects hot data from sequential scans
        
        // Implementation: scan old pages first, then young
        // Or: maintain separate lists for young/old
    }
};

Clock Variants Comparison
Variant	Key Feature	Use Case
Basic Clock	Single ref bit	Simple systems, low contention
Two-handed Clock	Leading/trailing hands	Better approximation of LRU
Multi-bit Clock	Reference counter	Distinguishing hot from warm pages
Scan-resistant Clock	Young/old sections	Mixed OLTP/scan workloads

PostgreSQL's Clock Implementation

PostgreSQL uses a Clock-based replacement algorithm with several interesting refinements. Understanding its implementation provides insight into production-grade buffer management.

PostgreSQL's buffer management architecture: Buffer pool is stored in shared memory (shared_buffers) Each buffer has a buf_hdr containing state (including a usage_count) Uses a usage count (0-5) instead of a single reference bit The Clock algorithm is called the "buffer replacement strategy"

postgresql_clock.c
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
// PostgreSQL-style Clock implementation (simplified)
 
#define BM_MAX_USAGE_COUNT 5
 
typedef struct BufferDesc {
    int32 buf_id;
    uint32 state;           // Includes usage_count, refcount, flags
    pg_atomic_uint32 state_spinlock;
    
    // usage_count is stored in state bits
    // Extract: (state >> BUF_USAGE_COUNT_SHIFT) & BUF_USAGE_COUNT_MASK
} BufferDesc;
 
// Called when buffer is accessed
void PinBuffer_common(BufferDesc *buf) {
    for (;;) {
        uint32 old_state = pg_atomic_read_u32(&buf->state);
        uint32 new_state = old_state;
        
        // Increment refcount
        new_state += BUF_REFCOUNT_ONE;
        
        // Increment usage_count if not at max
        if (BUF_STATE_GET_USAGECOUNT(new_state) < BM_MAX_USAGE_COUNT) {
            new_state += BUF_USAGECOUNT_ONE;
        }
        
        // Atomic compare-and-swap
        if (pg_atomic_compare_exchange_u32(&buf->state, 
                                           &old_state, new_state)) {
            break;
        }
        // Retry if state changed
    }
}
 
// Find a buffer to evict (ClockSweep)
BufferDesc* StrategyGetBuffer(BufferStrategyControl *strategy) {
    // Try freelist first
    if (strategy->firstFreeBuffer >= 0) {
        return GetBufferFromFreeList(strategy);
    }
    
    // Clock sweep
    int tries = NBuffers * 2;  // Avoid infinite loop
    
    while (tries > 0) {
        BufferDesc *buf = GetBufferDescriptor(strategy->nextVictimBuffer);
        
        // Advance clock hand
        strategy->nextVictimBuffer = 
            (strategy->nextVictimBuffer + 1) % NBuffers;
        
        // Try to victimize this buffer
        uint32 state = LockBufHdr(buf);
        
        // Skip if pinned
        if (BUF_STATE_GET_REFCOUNT(state) > 0) {
            UnlockBufHdr(buf, state);
            tries--;
            continue;
        }
        
        // Check usage count
        uint32 usage_count = BUF_STATE_GET_USAGECOUNT(state);
        
        if (usage_count > 0) {
            // Decrement and continue searching
            state -= BUF_USAGECOUNT_ONE;
            UnlockBufHdr(buf, state);
            tries--;
            continue;
        }
        
        // Found victim: refcount == 0 && usage_count == 0
        return buf;
    }
    
    // No victim found - all buffers pinned
    elog(ERROR, "no unpinned buffers available");
    return NULL;
}

PostgreSQL's Usage Count

PostgreSQL's usage_count (0-5) provides more granularity than a single bit. A page that's accessed repeatedly accumulates a higher usage_count, requiring multiple Clock passes to evict. This approximates LRU-K behavior without the complexity of tracking access timestamps.

MySQL InnoDB's LRU Implementation

MySQL InnoDB uses a modified LRU algorithm with explicit protections against scan pollution. Its implementation is more complex than PostgreSQL's Clock but provides better scan resistance.

InnoDB's LRU structure: The LRU list is a doubly-linked list of buffer pages Divided into two sublists: young (head, ~5/8) and old (tail, ~3/8) New pages enter at the old/young boundary (3/8 from tail) Pages must be accessed again after innodb_old_blocks_time to move to young The key insight: Sequential scan pages enter the old sublist. If the scan continues without re-accessing pages, they remain in old and get evicted first. Hot OLTP data in the young sublist is protected.

innodb_lru.cpp
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
// InnoDB-style LRU with young/old sublists (conceptual)
 
class InnoDBLRU {
    struct BufferPage {
        PageId page_id;
        BufferPage* prev;
        BufferPage* next;
        Timestamp access_time;
        bool is_young;  // In young sublist
    };
    
    BufferPage* lru_head;  // Head = most recently used in young
    BufferPage* old_head;  // Start of old sublist
    BufferPage* lru_tail;  // Tail = least recently used in old
    
    Duration old_blocks_time;  // innodb_old_blocks_time (default 1000ms)
    double old_ratio = 0.375;  // 3/8 for old sublist
    
public:
    // Insert new page at old/young boundary
    void insertNewPage(BufferPage* page) {
        page->is_young = false;
        page->access_time = currentTime();
        
        // Insert just before old_head (at boundary)
        insertBefore(old_head, page);
    }
    
    // Handle page access
    void accessPage(BufferPage* page) {
        Timestamp now = currentTime();
        
        if (page->is_young) {
            // Already in young sublist - move to head if not already there
            if (page != lru_head) {
                removeFromList(page);
                insertAtHead(page);
            }
            page->access_time = now;
            
        } else {
            // In old sublist - check if should promote
            Duration time_since_first = now - page->access_time;
            
            if (time_since_first > old_blocks_time) {
                // Accessed again after threshold - promote to young
                removeFromList(page);
                page->is_young = true;
                insertAtHead(page);
            }
            // If accessed within old_blocks_time, don't promote
            // This prevents read-ahead and scans from polluting young
            
            page->access_time = now;
        }
    }
    
    // Get victim for eviction (from tail of old sublist)
    BufferPage* getVictim() {
        // Scan from tail looking for unpinned page
        BufferPage* candidate = lru_tail;
        
        while (candidate != nullptr) {
            if (!candidate->isPinned()) {
                return candidate;
            }
            candidate = candidate->prev;
            
            // Prefer victims from old sublist
            if (candidate == old_head) {
                // Reached young sublist - ideally don't evict from here
                // But may need to if old is all pinned
            }
        }
        
        return nullptr;  // All pages pinned
    }
    
    // Adjust sublist sizes after operations
    void rebalance() {
        // Ensure old sublist maintains target ratio
        size_t total = getTotalPageCount();
        size_t target_old = total * old_ratio;
        size_t current_old = getOldSublistCount();
        
        while (current_old < target_old && lru_head != old_head) {
            // Move pages from young to old
            moveLastYoungToOld();
            current_old++;
        }
    }
};

InnoDB Buffer Pool Configuration Parameters
Parameter	Default	Description
innodb_buffer_pool_size	128MB	Total buffer pool memory
innodb_buffer_pool_instances	8 (if > 1GB)	Number of buffer pool partitions
innodb_old_blocks_pct	37 (3/8)	Percentage for old sublist
innodb_old_blocks_time	1000 (ms)	Time before promoting to young
innodb_lru_scan_depth	1024	Pages scanned for flushing per second

Tuning LRU and Clock Algorithms

While LRU and Clock algorithms are largely self-tuning, understanding key tuning parameters helps optimize performance for specific workloads.

Key Tuning Considerations

•Buffer pool size — The most impactful setting. Larger pools cache more data, reducing I/O. Size to fit the working set if possible.
•Buffer pool instances (MySQL) — More instances reduce contention but add overhead. Match to core count for high-concurrency systems.
•Old blocks time (MySQL) — Higher values protect against scan pollution more aggressively but may delay promotion of legitimately hot pages.
•Usage count max (PostgreSQL concept) — Higher values require more passes to evict, favoring very hot pages. Default of 5 is usually appropriate.
•Background flusher settings — Affect how aggressively dirty pages are written, which impacts eviction efficiency.

Workload-specific tuning: For OLTP workloads: Maximize buffer pool size (often 70-80% of RAM) Keep old_blocks_time at default or higher to protect against occasional scans Use multiple buffer pool instances for concurrency For analytical/scan workloads: Buffer pool may not help if data doesn't repeat Consider reducing old_blocks_time to allow scan pages to age out faster Sequential read optimizations (prefetching) matter more than replacement For mixed workloads: Default settings usually work well Monitor hit ratios for both OLTP and analytical queries Consider separate buffer pools for different tables if system supports it

Monitoring for Tuning Decisions

Before tuning, gather metrics: buffer pool hit ratio, pages read/written per second, evictions from young vs. old sublists. In MySQL, SHOW ENGINE INNODB STATUS provides buffer pool statistics. In PostgreSQL, enable pg_stat_statements and monitor pg_statio_user_tables .

LRU and Clock Algorithms

The Workhorses of Page Replacement

LRU Implementation Strategies

LRU Concurrency Challenges

Clock Algorithm Deep Dive

Clock Variants and Enhancements

PostgreSQL's Clock Implementation

MySQL InnoDB's LRU Implementation

Tuning LRU and Clock Algorithms

There’s more to understand.

LRU and Clock Algorithms

The Workhorses of Page Replacement

LRU Implementation Strategies

LRU Concurrency Challenges

Clock Algorithm Deep Dive

Clock Variants and Enhancements

PostgreSQL's Clock Implementation

MySQL InnoDB's LRU Implementation

Tuning LRU and Clock Algorithms

There’s more to understand.