Cache: Implement the frequency sketch #442
Description
As discussed in #127
When the new cache was originally designed, it was built on top of the older imprecise keys, and was largely implemented in Python. Now that it's based on exact keys and mostly implemented in C, a frequency sketch to make the eviction policy more optimal seems feasible.
Because of the nature of the keys and usage patterns, it will still take some thought.