Evaluate different cache replacement policies for InMemoryCache

[maurolacy]

Currently used LRU is probably not the best choice. For a blockchain, a LFU or some time-aware variant like LRFU (or the next few on the list) could be more appropriate.

As it is much easier to game LRU and flush popular items out of the cache

I don't know a way to simulate it both for efficiency in normal use and stability in face of byzantine actors, but a thought experiment over a few algorithms and searching for ones with good rust implementations should be a good start.

[maurolacy]

List of "popular" (>1000 downloads) cache crates (in decreasing order of popularity):

• lru-cache.
• lru. (O(1)).
• lru_time_cache. (fixed size)
• ttl_cache. (time based)
• associative-cache. (fixed size)
• xlru-cache.
• any-cache.
• clockpro-cache. (clock replacement policy)
• cache_2q. (lru + recent / frequent queues)
• cache.
• arc-cache. (arc replacement policy)
• timed_cache. (time based)
• cart-cache. (cart replacement policy)
• clru (currently used + weighted (0.4.0) version)

Also interesting / relevant:

• wasmer-cache.
• wasmtime-cache.

Documenting this list for when we decide to do this task.

[aumetra]

Another viable caching algorithm would probably be an implementation of the SIEVE algorithm, a refinement of CLOCK IIRC: https://cachemon.github.io/SIEVE-website/