Data Structures
    Overview
    Number
    String
    Array
    Linked List
    Stack
    Hash
    Tree
    Trie
    Advanced Data Structure
    Probabilistic Data Structures
    Big O

Least Frequently Used (LFU) Cache

Updated: 2021-12-15

Redis: Log counter

log counter: 8-bit counter

uint8_t LFULogIncr(uint8_t counter) {
  if (counter == 255) return 255;
  double r = (double)rand() / RAND_MAX;
  double baseval = counter - LFU_INIT_VAL;
  if (baseval < 0) baseval = 0;
  double p = 1.0 / (baseval * server.lfu_log_factor + 1);
  if (r < p) counter++;
  return counter;
}
  • After 100 hits the value of the counter is 10
  • After 1000 is 18
  • After 100k is 142
  • After 1 million hits it reaches the 255 limit