[CODE] W-LFU eviction - Githubissues

carrotdata / carrot-cache

In-Out-Process Java cache (L1/L2 off-heap, scalable, ZeroGC) with full SSD support

Other

3 stars 0 forks source link

[CODE] W-LFU eviction #9

Open VladRodionov opened 2 years ago

VladRodionov commented 2 years ago

Implement window-LFU eviction algorithm.

VladRodionov commented 1 year ago

Evicted items can go to a history store, which is MemoryIndex and be kept there for some time (after expiration they get removed completely from the system) - NO

VladRodionov commented 1 year ago

Idea was borrowed from rate limiter implementation:

Keep two counters (previous period of time and current period of time
Probabilistic counters a.k.a Morris with a twist (lower half is used for exact count)
Roll counters when new period starts
Calculate frequency using portion of both counters: see Sliding window counter algorithm

By using probabilistic counters we could fit everything into 2 bytes (1 byte per time interval)