Least Frequently Used (LFU) Cache

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