LFU: Frequency Buckets

The Idea

Least-frequently-used eviction has to find the lowest count fast, and scanning every key is O(n). So keep one bucket per count, each an ordered list, plus a note of the lowest non-empty count. A hit moves its key from bucket c to bucket c+1; an eviction pops the front of the lowest bucket — least used, and oldest among those. The lowest count only ever rises when a promotion empties its bucket.

Real-World Example

A CDN edge node deciding what to drop when disk fills up. Files sit on shelves by how often they have been served. The shelf nobody touches is emptied first, and the file that has sat there longest goes first.

The Code

def touch(count, buckets, least, key):
    c = count[key]
    buckets[c].remove(key)
    if not buckets[c]:
        del buckets[c]
        if least == c:
            least = c + 1          # the only way the floor ever rises
    count[key] = c + 1
    buckets.setdefault(c + 1, []).append(key)
    return least

def evict(count, buckets, least):
    key = buckets[least].pop(0)    # least used, and oldest among those
    del count[key]
    return key

count, buckets = {"a": 1, "b": 1}, {1: ["a", "b"]}
print(touch(count, buckets, 1, "a"), buckets)   # 1 {1: ['b'], 2: ['a']}

count, buckets = {"a": 1, "b": 1}, {1: ["a", "b"]}
least = touch(count, buckets, 1, "a")
print(least, evict(count, buckets, least))