Clock Cache Replacement Algorithm: Complete Implementation Guide

Introduction and Core Concepts

The clock cache replacement algorithm, often called the Clock algorithm or second-chance algorithm, is one of the most elegant and widely deployed approximations of the Least Recently Used (LRU) policy. It was designed to deliver nearly the same hit rate as LRU while eliminating the expensive linked-list manipulations and locking overhead that make true LRU impractical at scale. For any system where memory is finite and access latency matters, understanding the clock cache replacement algorithm is essential to building fast, predictable caching layers.

At its core, the clock cache replacement algorithm organizes cached entries in a circular buffer that resembles the face of a clock. A single pointer, called the clock hand, sweeps continuously around the circle. Each cached page or object has an associated reference bit, sometimes called a use bit or accessed bit. When an item is accessed, its reference bit is set to 1, giving it a second chance to remain in cache. When eviction is necessary, the hand scans for an entry whose reference bit is 0, which indicates it has not been recently used and is therefore a good candidate for replacement.

Why does this matter? Modern software systems live and die by cache efficiency. A CPU cache miss can cost 100x more cycles than a hit, a database buffer pool miss can trigger a disk seek, and a web cache miss can add hundreds of milliseconds of network latency. True LRU requires moving nodes to the head of a doubly linked list on every single hit, which creates contention in multi-threaded environments and pollutes cache lines. The clock cache replacement algorithm achieves O(1) amortized operations with minimal metadata — just one bit per entry and a single integer pointer — making it ideal for operating system page replacement, database buffer managers, and high-throughput application caches.

The Problem Clock Solves

Consider a fixed-size cache that can hold N items. When the cache is full and a new item arrives, which item should be evicted? First-In-First-Out (FIFO) is cheap but evicts frequently used items simply because they are old. Least Frequently Used (LFU) requires counters and ages poorly. True LRU is optimal for recency-based workloads but is expensive to maintain precisely. The clock cache replacement algorithm strikes a balance: it approximates LRU behavior by observing recent usage through reference bits without maintaining a strict total ordering of all entries.

The key insight is that perfect recency ordering is not necessary. It is enough to distinguish between hot items that have been touched in the recent sweep of the clock hand and cold items that have not. This coarse-grained distinction is sufficient to achieve hit ratios within a few percent of LRU for most real workloads, particularly those exhibiting temporal locality, where recently accessed items are likely to be accessed again soon.

How It Works

The mechanism of the clock cache replacement algorithm can be understood as a circular array with three components: the storage array that holds the cached keys and values, a parallel array of reference bits, and the clock hand index. The hand always points to the next candidate for eviction, not the most recently inserted item. This subtle detail is what makes the algorithm fair and prevents pathological eviction patterns.

On a cache hit, the operation is trivial. The algorithm locates the entry, returns its value, and sets its reference bit to 1. No movement, no reordering, and no pointer updates are required beyond flipping a single bit. This is the primary source of the algorithm's efficiency compared to LRU, where a hit requires unlinking and relinking list nodes.

On a cache miss when there is still free space, the algorithm inserts the new entry at the position indicated by the clock hand, sets its reference bit to 1, and advances the hand to the next slot. The hand advancement ensures that the next insertion will use the following slot, distributing entries evenly around the circle.

The Eviction Scan

The most interesting behavior occurs on a cache miss when the cache is full. The algorithm enters its eviction scan loop. It examines the entry currently under the clock hand. If that entry's reference bit is 0, it has not been accessed since the last time the hand visited it, so it is evicted immediately and replaced with the new entry. Its reference bit is set to 1 for the newcomer, and the hand advances one position past the victim.

If the reference bit is 1, the entry is given a second chance. The algorithm clears the bit to 0, advances the hand to the next position, and repeats the check. This process continues, potentially wrapping around the entire circle, until a victim with a 0 bit is found. In the worst case where every entry has its bit set to 1, the hand will make a full revolution, clearing all bits to 0, and then evict the starting entry on the second pass. This guarantees progress and ensures that no entry is permanently pinned.

This scan is why the algorithm is called Clock. Visualizing the hand moving clockwise around a dial, flipping bits as it goes, makes the behavior intuitive. The reference bits act as a form of decaying memory: an item touched recently survives one full sweep, but if it remains untouched for an entire revolution, it becomes eligible for eviction.

Hardware and Software Support

In operating systems, the reference bit is often maintained directly by the memory management unit (MMU). The hardware sets the bit whenever a page is accessed, and the OS clears it during its clock scan. In user-space application caches, the software explicitly sets the bit in its get() method. This duality makes the clock cache replacement algorithm uniquely portable across kernel and user-space implementations.

Implementation

Implementing the clock cache replacement algorithm in Python requires careful handling of the circular buffer, the hand pointer, and the bidirectional mapping between keys and indices. The implementation below prioritizes clarity and correctness while maintaining O(1) average-case performance for hits and inserts.

Basic Clock Cache Structure

This first implementation provides a complete, production-ready Clock cache with get and put operations, proper hand management, and explicit reference bit handling.

class ClockCache:
    def __init__(self, capacity):
        if capacity <= 0:
            raise ValueError("capacity must be > 0")
        self.capacity = capacity
        self.cache = [None] * capacity      # stores (key, value) tuples
        self.ref_bits = [0] * capacity      # reference / use bits
        self.hand = 0                       # clock hand pointer
        self.key_to_index = {}              # key -> index for O(1) lookup
        self.index_to_key = {}              # index -> key for eviction

    def get(self, key):
        """Return value if present and set reference bit, else -1."""
        if key not in self.key_to_index:
            return -1
        idx = self.key_to_index[key]
        self.ref_bits[idx] = 1              # give second chance on hit
        return self.cache[idx][1]

    def put(self, key, value):
        """Insert or update key-value pair using clock eviction."""
        # Update existing entry
        if key in self.key_to_index:
            idx = self.key_to_index[key]
            self.cache[idx] = (key, value)
            self.ref_bits[idx] = 1
            return

        # Insert into free slot if cache not full
        if len(self.key_to_index) < self.capacity:
            while self.cache[self.hand] is not None:
                self.hand = (self.hand + 1) % self.capacity
            self.cache[self.hand] = (key, value)
            self.ref_bits[self.hand] = 1
            self.key_to_index[key] = self.hand
            self.index_to_key[self.hand] = key
            self.hand = (self.hand + 1) % self.capacity
            return

        # Cache full: evict via clock scan
        self._evict_and_insert(key, value)

    def _evict_and_insert(self, key, value):
        """Scan for victim with ref_bit == 0 and replace it."""
        while True:
            if self.ref_bits[self.hand] == 0:
                # Evict victim at hand
                old_key = self.index_to_key.pop(self.hand, None)
                if old_key is not None:
                    del self.key_to_index[old_key]
                self.cache[self.hand] = (key, value)
                self.ref_bits[self.hand] = 1
                self.key_to_index[key] = self.hand
                self.index_to_key[self.hand] = key
                self.hand = (self.hand + 1) % self.capacity
                break
            else:
                # Give second chance: clear bit and advance
                self.ref_bits[self.hand] = 0
                self.hand = (self.hand + 1) % self.capacity

Handling Edge Cases and State Inspection

A robust implementation should expose debugging helpers and correctly handle duplicate puts, capacity boundaries, and hand wrap-around. The following extension adds utility methods that are invaluable for testing and monitoring.

class InstrumentedClockCache(ClockCache):
    def display(self):
        """Print current clock state for debugging."""
        print(f"Hand -> {self.hand}")
        for i in range(self.capacity):
            entry = self.cache[i]
            bit = self.ref_bits[i]
            marker = "<-- hand" if i == self.hand else ""
            if entry is None:
                print(f"  [{i}] empty | ref={bit} {marker}")
            else:
                print(f"  [{i}] {entry[0]}:{entry[1]} | ref={bit} {marker}")

    def contains(self, key):
        return key in self.key_to_index

    def stats(self):
        """Return occupancy and hand position."""
        return {
            "capacity": self.capacity,
            "size": len(self.key_to_index),
            "hand": self.hand,
            "ref_bits": list(self.ref_bits)
        }

# Example usage
cache = InstrumentedClockCache(3)
cache.put("A", 1)
cache.put("B", 2)
cache.put("C", 3)
cache.display()
# Access A to set its ref bit
cache.get("A")
print("After get(A):", cache.stats())
# Next insert will trigger eviction scan
cache.put("D", 4)
cache.display()

Thread-Safe Variant for Concurrent Workloads

In multi-threaded web servers or database buffer pools, the clock hand is a shared mutable pointer. A naive implementation would race. The following variant uses a lock to protect hand movement and bit updates while keeping the critical section minimal.

import threading

class ConcurrentClockCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = [None] * capacity
        self.ref_bits = [0] * capacity
        self.hand = 0
        self.key_to_index = {}
        self.index_to_key = {}
        self.lock = threading.Lock()

    def get(self, key):
        with self.lock:
            if key not in self.key_to_index:
                return -1
            idx = self.key_to_index[key]
            self.ref_bits[idx] = 1
            return self.cache[idx][1]

    def put(self, key, value):
        with self.lock:
            if key in self.key_to_index:
                idx = self.key_to_index[key]
                self.cache[idx] = (key, value)
                self.ref_bits[idx] = 1
                return
            if len(self.key_to_index) < self.capacity:
                while self.cache[self.hand] is not None:
                    self.hand = (self.hand + 1) % self.capacity
                self.cache[self.hand] = (key, value)
                self.ref_bits[self.hand] = 1
                self.key_to_index[key] = self.hand
                self.index_to_key[self.hand] = key
                self.hand = (self.hand + 1) % self.capacity
                return
            # Full eviction scan under lock
            scans = 0
            while True:
                scans += 1
                if scans > self.capacity * 2:
                    raise RuntimeError("Clock scan failed to find victim")
                if self.ref_bits[self.hand] == 0:
                    old_key = self.index_to_key.pop(self.hand, None)
                    if old_key is not None:
                        del self.key_to_index[old_key]
                    self.cache[self.hand] = (key, value)
                    self.ref_bits[self.hand] = 1
                    self.key_to_index[key] = self.hand
                    self.index_to_key[self.hand] = key
                    self.hand = (self.hand + 1) % self.capacity
                    break
                else:
                    self.ref_bits[self.hand] = 0
                    self.hand = (self.hand + 1) % self.capacity

Generalized Clock (GCLOCK) with Counter

The classic Clock uses a single bit, but the Generalized Clock replaces the bit with a small counter that is incremented on hits and decremented on scans. This better approximates LFU for skewed workloads while retaining Clock's simplicity.

class GClockCache:
    def __init__(self, capacity, max_count=3):
        self.capacity = capacity
        self.max_count = max_count
        self.cache = [None] * capacity
        self.counters = [0] * capacity
        self.hand = 0
        self.key_to_index = {}
        self.index_to_key = {}

    def get(self, key):
        if key not in self.key_to_index:
            return -1
        idx = self.key_to_index[key]
        # Increment counter up to max, simulating frequency
        if self.counters[idx] < self.max_count:
            self.counters[idx] += 1
        return self.cache[idx][1]

    def put(self, key, value):
        if key in self.key_to_index:
            idx = self.key_to_index[key]
            self.cache[idx] = (key, value)
            if self.counters[idx] < self.max_count:
                self.counters[idx] += 1
            return
        if len(self.key_to_index) < self.capacity:
            while self.cache[self.hand] is not None:
                self.hand = (self.hand + 1) % self.capacity
            self.cache[self.hand] = (key, value)
            self.counters[self.hand] = 1
            self.key_to_index[key] = self.hand
            self.index_to_key[self.hand] = key
            self.hand = (self.hand + 1) % self.capacity
            return
        # Eviction: decrement counters until zero found
        while True:
            if self.counters[self.hand] == 0:
                old_key = self.index_to_key.pop(self.hand, None)
                if old_key is not None:
                    del self.key_to_index[old_key]
                self.cache[self.hand] = (key, value)
                self.counters[self.hand] = 1
                self.key_to_index[key] = self.hand
                self.index_to_key[self.hand] = key
                self.hand = (self.hand + 1) % self.capacity
                break
            else:
                self.counters[self.hand] -= 1
                self.hand = (self.hand + 1) % self.capacity

Step-by-Step Example

To make the clock cache replacement algorithm concrete, let us walk through a cache with capacity 3. We will track the cache array, reference bits, hand position, and the action taken for each operation. The hand is shown as an arrow pointing to the next slot to examine.

Initially the cache is empty: [ -, -, - ], ref bits [0,0,0], hand = 0. Operations proceed sequentially. This example demonstrates hits giving second chances, the hand wrapping around, and the worst-case full scan.

Pay close attention to how a get() operation that sets a reference bit can save an entry from eviction even if it is the oldest entry in the buffer. This is the essence of the second-chance behavior that allows Clock to outperform FIFO.

The previous row oversimplifies the scan for clarity. Let us detail step 5 precisely. At the moment before put(D), bits are [1,1,1] and hand=0. The scan examines index 0: bit is 1, so it clears it to 0 and advances to 1. Index 1: bit is 1, clear to 0, advance to 2. Index 2: bit is 1, clear to 0, advance to 0 (wrap). Now index 0 has bit 0, so A is evicted and replaced by D with bit 1. Final state after step 5 is [D, B, C] with bits [1,0,0] and hand=1. This full revolution illustrates the worst-case scan cost.

Continuing, suppose we now do get(B). Bits become [1,1,0] and hand stays at 1. Next put(E) will scan at hand=1: bit is 1, so clear to 0 and advance to 2. At hand=2, bit is 0, so C is evicted. Result is [D, B, E] with bits [1,0,1] and hand=0 (wrapped from 2 to 0 after eviction at 2, then advanced). Notice B survived because its recent get() gave it a second chance, while C, untouched since insertion, was evicted despite being newer than B. This demonstrates how Clock respects recency over insertion order.

Key Observations from the Walkthrough

First, the hand never moves backward and only advances forward, guaranteeing fairness. Second, a single hit can delay eviction by up to one full revolution, which is approximately N misses. Third, the algorithm requires no global timestamp or ordering, only local bit manipulation. These properties make the walkthrough representative of real system behavior under both sequential and random access patterns.

Complexity Analysis

The efficiency of the clock cache replacement algorithm is its primary selling point. Unlike LRU, which requires pointer manipulation on every access, Clock performs only constant-time bit operations on hits and an amortized constant-time scan on misses. Understanding the precise complexity helps in capacity planning and latency budgeting.

For a cache of capacity N, a hit operation is strictly O(1). It involves a hash table lookup to find the index and setting a single reference bit. No scan is performed, no hand movement occurs, and no other entries are touched. This makes hits extremely cheap and cache-friendly, as the bit array is often contiguous in memory.

Insertion into a non-full cache is also O(1) average case, though it may need to skip over occupied slots if the hand has advanced past free slots. In practice, the while loop to find a free slot executes at most once or twice because free slots are plentiful early on.

Eviction is where complexity becomes interesting. In the best case, the entry under the hand already has a 0 bit, so eviction is O(1). In the average case, assuming reference bits are randomly distributed with probability p of being 1, the expected number of steps is 1/(1-p), which is constant. In the worst case where all N bits are 1, the algorithm must scan N entries, clear them, and then scan one more to evict, resulting in O(N) time. However, this worst case is amortized: each entry's bit can be cleared at most once per eviction, so over a sequence of M operations, the total work is O(M), yielding O(1) amortized cost per operation.

Space complexity is O(N) for the cache entries plus O(N) bits for reference bits and O(N) for the hash maps. If the cache stores keys and values directly in the circular array, the overhead is essentially one bit plus two hash entries per slot, which is significantly less than LRU's two pointers per entry.

Amortized vs. Worst-Case Latency

For latency-sensitive systems, the worst-case O(N) scan can be a concern. A request that triggers a full revolution will experience higher tail latency. This is why some implementations bound the scan to a fixed number of steps or use concurrent background hand advancement. For most workloads, however, the amortized O(1) guarantee holds, and the 99th percentile latency remains close to the average.

Memory overhead is another consideration. Storing reference bits as a Python list of integers is wasteful; in C or Java, a bitset or byte array is used. For a cache of 1 million entries, the bit array consumes only 125 KB, negligible compared to the cached data itself.

Variations and Optimizations

The basic Clock algorithm has spawned numerous variants that address its limitations, such as poor handling of scans, inability to distinguish frequency from recency, and sensitivity to large sequential scans that wash out the cache.

Clock with Adaptive Replacement (CAR) and Clock-Pro

CAR maintains two Clock lists: one for recently accessed pages (T1) and one for frequently accessed pages (T2), plus ghost lists that remember evicted keys. It dynamically adjusts the target size of T1 vs T2 based on workload, achieving hit rates comparable to ARC while retaining Clock's low overhead. Clock-Pro extends this idea by tracking cold, hot, and non-resident information to better handle looping and scanning workloads where basic Clock performs poorly.

WSClock (Working Set Clock)

WSClock, used in operating system virtual memory, augments each entry with a timestamp of last use. During the scan, if the reference bit is 1, it is cleared and the timestamp updated. If the bit is 0, the algorithm checks the age: if the entry is older than a working-set window tau, it is evicted; otherwise it is kept and the hand advances. This combines Clock's efficiency with working-set theory to avoid evicting pages that are part of the current working set, even if their bit happens to be 0 at scan time.

Generalized Clock (GCLOCK) and Multi-Bit Clock

GCLOCK replaces the single bit with a counter, as shown in the implementation above. Hits increment the counter, misses decrement it during scans. A 2-bit or 3-bit counter can distinguish between items accessed once, a few times, and many times, providing a spectrum between LRU and LFU. This is particularly effective for database buffer pools where some pages are hot and others are scanned once and never revisited.

Optimizations for Modern Hardware

Several low-level optimizations improve Clock performance. Using a power-of-two capacity allows hand advancement via bitmask instead of modulo. Storing reference bits in a separate bitset improves cache locality. Batching hand advancement or using a free-list for empty slots avoids scanning for free space. For highly concurrent caches, sharding the Clock into per-core sub-clocks with occasional rebalancing reduces contention on the global hand.

Another practical optimization is the use of a dirty bit alongside the reference bit. In write-back caches, clean pages are cheaper to evict than dirty pages that require writeback. The hand can prioritize clean victims by checking both bits, effectively implementing a Clock variant of the enhanced second-chance algorithm used in many OS kernels.

Real-World Applications

The clock cache replacement algorithm is not an academic curiosity; it is the backbone of many production systems where predictability and low overhead are non-negotiable.

In operating systems, Clock is the default page replacement algorithm in FreeBSD, Linux (as an approximation via the active/inactive lists), and Windows. The MMU sets accessed bits, and the kernel's page daemon sweeps the clock hand to reclaim frames. The simplicity of the scan allows it to run in interrupt context with minimal locking.

Database systems rely heavily on Clock variants. PostgreSQL's buffer manager uses a Clock sweep to choose victim buffers. Oracle and MySQL's InnoDB use modified Clock or LRU approximations that are essentially Clock with additional frequency tracking. The ability to handle large buffer pools (hundreds of gigabytes) with O(1) operations is critical when every microsecond of buffer lookup matters.

Web caches and CDNs use Clock for in-memory object caches. Varnish, Nginx, and custom edge caches often implement Clock because it avoids the lock contention that true LRU would create under thousands of concurrent requests. The second-chance property naturally keeps popular objects (like trending images or API responses) hot while allowing one-hit wonders to be evicted quickly.

When Not to Use Clock

Clock is less suitable when strict recency ordering is required for correctness, such as in some transactional systems, or when access patterns are highly frequency-biased and LFU would perform significantly better. For small caches (under 100 entries) where LRU overhead is negligible, the simplicity of a doubly linked list may outweigh Clock's benefits.

Comparison with Alternatives

Choosing a cache replacement policy requires understanding trade-offs in hit ratio, overhead, and implementation complexity. The clock cache replacement algorithm occupies a sweet spot, but it is important to compare it directly with other common policies.

FIFO is the simplest policy but blind to recency, leading to poor hit rates for looping workloads. LRU offers excellent hit rates but at the cost of per-hit pointer updates and poor concurrency. LFU captures frequency but requires aging and can retain stale popular items. Random eviction is surprisingly competitive and trivial to implement, but its hit rate variance is high. Clock provides near-LRU hit rates with near-FIFO overhead, which is why it is often the default choice.

The table highlights why Clock is favored for large, concurrent caches. Its metadata is minimal, its hit path is lock-light, and its hit ratio is close to LRU. The primary weakness is scan resistance, which is addressed by GCLOCK or Clock-Pro variants. For workloads dominated by sequential scans, such as full table scans in databases, a plain Clock can be polluted, evicting hot pages. In those cases, augmenting Clock with ghost lists or counters is recommended.

Common Mistakes and Best Practices

Even though the clock cache replacement algorithm is conceptually simple, implementation pitfalls can lead to subtle bugs, performance degradation, or incorrect eviction behavior.

A frequent mistake is forgetting to advance the hand after insertion or eviction. If the hand is not advanced, the same slot will be examined repeatedly, causing unfair eviction and potentially infinite loops. Always advance the hand modulo capacity immediately after placing a new entry.

Another common error is mishandling the reference bit on updates. When an existing key is updated via put(), its reference bit must be set to 1, just as on a get(). Failing to do so makes recently updated items artificially cold and likely to be evicted prematurely. Similarly, some implementations clear the bit on every get() instead of setting it, inverting the intended semantics.

Concurrency bugs are prevalent. The hand and reference bits must be protected by a lock or atomic operations. A race where two threads simultaneously scan and evict can corrupt the key-to-index maps. Use a single lock for the entire scan, or shard the cache if contention becomes a bottleneck. Avoid fine-grained per-slot locks, which add complexity without measurable benefit for Clock's simple scan.

Capacity and modulo errors also cause issues. Using Python's % operator with a non-power-of-two capacity is correct but slower; ensure hand wrap uses modulo capacity consistently. Off-by-one errors when checking len(map) < capacity versus <= capacity can cause the cache to overfill or underutilize one slot.

Best Practices

• Initialize reference bits to 0 and set to 1 on both get() and successful put(). Treat updates as hits for recency purposes.
• Keep the clock array and bit array as contiguous Python lists or arrays for cache locality; avoid linked structures.
• Add a bounded scan guard (e.g., 2 * capacity iterations) to detect logic errors that prevent finding a victim and to avoid infinite loops if bits are mishandled.
• Instrument the cache with hit/miss counters and average scan length metrics. A rising average scan length indicates that many entries are hot and capacity may be too small.
• For write-back caches, maintain a dirty bit alongside the reference bit and preferentially evict clean pages to reduce I/O.
• Test with deterministic sequences, including the worst-case scenario where all bits are 1, to verify that the hand makes a full revolution correctly.
• Consider GCLOCK counters (2-3 bits) if your workload includes both hot and scan-once data; the extra bits dramatically improve hit ratio with minimal cost.

Finally, document the eviction policy clearly for users of the cache. Unlike LRU, Clock's behavior is not strictly deterministic from the user's perspective due to the hand position. Providing visibility into the algorithm helps in debugging performance anomalies.

Interview Questions

Interviewers frequently probe understanding of the clock cache replacement algorithm because it tests knowledge of systems design, complexity analysis, and trade-offs. Below are common questions with guidance on strong answers.

Q1: How does Clock approximate LRU and why is it more efficient?

A strong answer explains that Clock uses a single reference bit per entry and a circular hand to approximate recency without maintaining a total order. On hits, LRU must move a node to the head of a doubly linked list, requiring multiple pointer updates and often a global lock. Clock only sets a bit to 1, which is O(1) and lock-light. Eviction scans for a 0 bit, giving entries with 1 a second chance. This yields hit ratios within a few percent of LRU for workloads with temporal locality while reducing per-operation overhead and improving concurrency.

Q2: What is the worst-case time complexity of Clock eviction and how is it amortized?

Answer: Worst-case eviction is O(N) when all N reference bits are 1, requiring a full revolution to clear bits and a second pass to find a victim. However, each bit is cleared at most once per eviction, so over M operations total work is O(M). Thus amortized cost is O(1) per operation. Mention that this amortized guarantee assumes the hand only moves forward and bits are only set on hits, and note the impact on tail latency for latency-sensitive systems.

Q3: How would you handle a sequential scan that pollutes a Clock cache?

Discuss scan resistance. Plain Clock will evict hot pages when a large sequential scan sets bits for many cold pages. Solutions include GCLOCK with counters so scan-once pages have low counts and are quickly evicted, Clock-Pro or CAR with ghost lists to remember evicted hot pages, or adding a separate scan-resistant area. Also mention WSClock's time window or simply bypassing the cache for known large scans.

Q4: Implement Clock's put() method and explain hand management.

Interviewers expect code that handles three cases: update existing key (set bit, no hand move), insert into free slot (place at hand, set bit, advance hand), and evict when full (loop: if bit 0 evict and advance, else clear bit and advance). Emphasize modulo arithmetic for hand wrap, maintaining both key_to_index and index_to_key maps, and advancing the hand after every insertion/eviction to ensure fairness. Be prepared to walk through an example with capacity 3.

Q5: Compare Clock, LRU, and Random replacement for a highly concurrent web cache.

Explain that LRU has high lock contention due to list manipulation on every hit, limiting throughput. Random has no contention and is simple but has lower and less predictable hit rates. Clock offers the best balance: near-LRU hit rate with O(1) bit updates and a single hand pointer that can be protected by a lightweight lock or sharded. For a web cache with Zipf-distributed requests and thousands of concurrent threads, Clock (or its GCLOCK variant) typically maximizes both hit ratio and request throughput.

Mastering these questions demonstrates not just memorization of the algorithm but deep understanding of when and why the clock cache replacement algorithm is the right tool for building high-performance caching systems.