With the allkeys-lfu maxmemory policy, Redis tracks each key's access frequency in only 8 bits. How can 8 bits represent millions of accesses, and what does the lfu-log-factor setting control?

## Why LFU exists at all LRU answers "who was touched longest ago", which is the wrong question for some caches. A key read once by a nightly report looks as fresh as a key read ten thousand times a second, so a full scan or a burst of one-off requests can evict genuinely hot data. LFU (Redis 4.0, policies `allkeys-lfu` and `volatile-lfu`) ranks by how often a key is used rather than how recently, which is more robust against scan-shaped traffic. ## The bit budget LFU has to fit in the same 24 spare bits of the object header that LRU used, because Redis will not pay extra memory per key. Those bits are split as: - 16 bits: the last decay time, in minutes. - 8 bits: the frequency counter, range 0 to 255. Eight bits obviously cannot count real accesses; a hot key sees millions. The trick is to stop counting exactly. ## The probabilistic (Morris) counter A Morris counter stores the logarithm of a count. Instead of incrementing on every event, it increments with a probability that falls as the stored value rises, so the stored number grows roughly like the logarithm of the true number of events. Redis implements it as follows: - New keys are created with the counter at 5 rather than 0. This is important: a key inserted a moment ago has no access history, and starting at 0 would make it the top eviction candidate immediately, so it would be evicted before it ever had a chance to be used again. - On access, Redis computes `baseval = counter - 5` (floored at 0) and increments the counter with probability `1 / (baseval * lfu_log_factor + 1)`. - The counter saturates at 255. So the first accesses after creation increment almost every time, and by the time the counter is in the hundreds each further increment requires thousands of accesses. With the default factor of 10, a key needs on the order of a million accesses to reach 255; with a much larger factor the same ceiling corresponds to roughly ten million; with a factor of 0 the counter behaves close to a linear count and saturates almost immediately, which destroys any ability to rank popular keys. This is also why the counter is *not* a hit count: an interviewer's favourite trap is asking what `OBJECT FREQ` returns. It returns the logarithmic counter, a rank, not a number of accesses. ## How eviction uses it Eviction machinery is shared with LRU: random sampling into the same bounded candidate pool. Only the score changes - instead of "most idle wins", the candidate with the *lowest* frequency counter wins, so it is scored as the inverse of the counter. Everything else - `maxmemory-samples`, the pool, the split between `allkeys-*` and `volatile-*` candidate sets, eviction happening inline in the command path - is identical. ## Reading and observing it `OBJECT FREQ <key>` is only valid while `maxmemory-policy` is one of the LFU policies, because outside that mode those bits hold the LRU clock instead. Conversely `OBJECT IDLETIME` is rejected under LFU. Sampling `OBJECT FREQ` over a set of interesting keys is the practical way to check whether the tuning actually separates your hot keys from your cold ones: if everything you look at reports 255, the scale is too compressed for your traffic and the log factor should go up; if hot and cold keys both sit near 5, the counter is not climbing and either the factor is too high for your rates or decay is eating the counter. ## What to say in an interview Name the three pieces: eight bits, probabilistic logarithmic increment, an initial value of 5 to protect new keys. Then the tuning consequence: `lfu-log-factor` sets how many real accesses map onto the 0-255 scale, so it decides at what traffic level the counter stops discriminating.