How Redis Uses 24‑Bit Counters for Efficient LRU Caching

In programming, counters are a fundamental yet powerful tool for tracking and managing data and resources. This article delves into various counter applications, from Redis’s LRU (Least Recently Used) cache eviction algorithm to memory‑constrained environments and clever uses of ordinary counters.

1. Redis LRU Implementation

Redis, a high‑performance key‑value store, uses an LRU algorithm to decide which data to evict and free memory. To save memory, Redis does not store full timestamps; instead it employs a clever approach:

Timestamp precision simplification : Redis reduces precision by dividing the timestamp by a fixed resolution (e.g., 1000 ms).

Bit‑length limitation : It stores the reduced timestamps in a fixed number of bits (e.g., 24 bits).

Bitwise AND operation : A bitwise AND ensures the counter automatically wraps to zero after reaching its maximum, preventing overflow.

This method balances memory usage and timestamp update efficiency, making the LRU implementation both fast and space‑saving.

#define LRU_BITS 24
#define LRU_CLOCK_MAX ((1<<LRU_BITS)-1) /* Max value of obj->lru */
#define LRU_CLOCK_RESOLUTION 1000

unsigned int getLRUClock(void) {
    return (mstime()/LRU_CLOCK_RESOLUTION) & LRU_CLOCK_MAX;
}

Using a 24‑bit timestamp means the maximum representable value is (2^24‑1) = 16,777,215. Redis treats the timestamp as seconds, so the maximum span is 16,777,215 seconds, which equals roughly 194 days (≈ 4,655 hours). After this period the timestamp wraps to zero, but the LRU algorithm only cares about relative recency, not absolute time.

2. Memory Efficiency and Approximate Timestamps

Fixed‑bit counters are useful in many scenarios where memory efficiency is critical.

2.1 Memory‑Efficiency Example

Consider a high‑performance logging system that tracks millions of log entries. Storing a full 64‑bit millisecond timestamp consumes 8 bytes per entry. By using a 24‑bit timestamp (≈ 3 bytes) the memory footprint drops dramatically while still providing sufficient granularity for most analyses.

64‑bit timestamps: 1,000,000 events × 8 bytes = 8 MB.

24‑bit timestamps: 1,000,000 events × 3 bytes = 3 MB (≈ 4.77 MB saved).

2.2 Approximate Timestamp Example

For a website cache, recording the last access time with a 10‑minute granularity reduces storage needs. A full 32‑bit Unix timestamp (seconds) might be 1617181723, while a 20‑bit approximate timestamp representing 10‑minute intervals could be a value like 99,000.

Full precision: seconds resolution.

Approximate precision: 10‑minute resolution, sufficient for cache eviction decisions.

3. Practical Use of Cyclic Counters

Fixed‑bit counters combined with a bitwise AND provide an elegant way to implement automatic wrap‑around without extra checks.

Implementation steps :

Determine the required bit width.

Compute the mask value (2^N‑1).

Apply the mask with a bitwise AND after each increment.

Example with a 16‑bit counter:

#include <stdio.h>
#define COUNTER_BITS 16
#define COUNTER_MAX ((1 << COUNTER_BITS) - 1)

int main() {
    unsigned int counter = 0;
    for (int i = 0; i < 70000; i++) {
        counter = (counter + 1) & COUNTER_MAX; // automatic wrap‑around
    }
    printf("Final counter value: %u
", counter);
    return 0;
}

After 65,535 increments the counter wraps to zero, making it ideal for cache eviction, timestamps, or state tracking in resource‑constrained environments.

4. Efficient Storage of Fixed‑Bit Values

Typical integer types occupy 4 bytes (32 bits). To store values that need only 3 bytes, several techniques exist:

Bit‑field structs (C/C++) :

struct Timestamp {
    unsigned int time : 24;
};

Byte arrays :

uint8_t timestamp[3];
// Set value
timestamp[0] = (value >> 16) & 0xFF; // high byte
timestamp[1] = (value >> 8) & 0xFF;  // middle byte
timestamp[2] = value & 0xFF;         // low byte
// Recover value
uint32_t recovered = (timestamp[0] << 16) | (timestamp[1] << 8) | timestamp[2];

Using standard 4‑byte types is often acceptable when extreme memory savings are not required, offering simplicity and portability.

Choosing the appropriate method depends on the trade‑off between memory efficiency and code complexity.

Conclusion

Fixed‑bit counters with bitwise AND operations provide a resource‑saving, error‑reducing, and efficient solution for cyclic counting, especially in memory‑limited contexts. By leveraging simple bit manipulations, developers can achieve automatic wrap‑around, compact storage, and robust code.