LFU (Least Frequently Used) counter with time-based decay, matching Redis's implementation.
Packed format
The LFU field in each keydir ETS tuple is a single integer packing two values:
- Upper 16 bits:
ldt(last decrement time) — minutes since epoch, wraps at 2^16 (~45 days). - Lower 8 bits:
counter— logarithmic frequency counter (0-255).
Access algorithm
On every key access:
- Decay: elapsed =
now_minutes - ldt. Reduce counter byelapsed / lfu_decay_time. - Increment: probabilistic log increment with probability
1 / (counter * lfu_log_factor + 1). - Update ldt to current minutes.
Configuration
:lfu_decay_time— minutes per decay step (default 1, 0 = no decay):lfu_log_factor— controls increment probability curve (default 10)
New keys start at counter = 5 with the current ldt.
Summary
Functions
Returns the effective (decayed) counter for a packed LFU value.
Returns the effective (decayed) counter using instance ctx.
Computes elapsed minutes between now and ldt, handling 16-bit wraparound.
Initializes persistent_term cache for LFU config values.
Returns the initial packed LFU value for a new key (counter=5, ldt=now).
Returns the initial packed LFU value using instance ctx.
Returns the initial counter value (5).
Returns the current time in minutes, masked to 16 bits.
Packs ldt (16-bit minutes) and counter (8-bit) into a single integer.
Performs an LFU touch: decays the counter, then probabilistically increments it.
Performs an LFU touch using instance ctx for config values.
Unpacks a packed LFU integer into {ldt_minutes, counter}.
Functions
@spec effective_counter(non_neg_integer()) :: non_neg_integer()
Returns the effective (decayed) counter for a packed LFU value.
Applies time-based decay without updating the stored value. Used for eviction comparison and OBJECT FREQ.
@spec effective_counter(FerricStore.Instance.t(), non_neg_integer()) :: non_neg_integer()
Returns the effective (decayed) counter using instance ctx.
@spec elapsed_minutes(non_neg_integer(), non_neg_integer()) :: non_neg_integer()
Computes elapsed minutes between now and ldt, handling 16-bit wraparound.
@spec init_config_cache() :: :ok
Initializes persistent_term cache for LFU config values.
Called once at application startup. Subsequent reads from touch/3 and
effective_counter/1 use :persistent_term.get/1 (~5ns) instead of
Application.get_env/3 (~200-250ns), saving ~400ns per hot GET.
@spec initial() :: non_neg_integer()
Returns the initial packed LFU value for a new key (counter=5, ldt=now).
Uses a per-minute cache in persistent_term to avoid calling
System.os_time/1 on every ETS insert (~50ns/call). The cached value
is refreshed lazily when the current minute changes.
@spec initial(FerricStore.Instance.t()) :: non_neg_integer()
Returns the initial packed LFU value using instance ctx.
@spec initial_counter() :: non_neg_integer()
Returns the initial counter value (5).
@spec now_minutes() :: non_neg_integer()
Returns the current time in minutes, masked to 16 bits.
@spec pack(non_neg_integer(), non_neg_integer()) :: non_neg_integer()
Packs ldt (16-bit minutes) and counter (8-bit) into a single integer.
@spec touch(atom(), binary(), non_neg_integer()) :: :ok
Performs an LFU touch: decays the counter, then probabilistically increments it.
Returns the new packed LFU value. Updates the ETS entry at position 4.
@spec touch(FerricStore.Instance.t(), atom(), binary(), non_neg_integer()) :: :ok
Performs an LFU touch using instance ctx for config values.
@spec unpack(non_neg_integer()) :: {non_neg_integer(), non_neg_integer()}
Unpacks a packed LFU integer into {ldt_minutes, counter}.