The LRUKeyValue utility is in-memory key-value store which guarantees that its size will never exceed a given budget, and which keeps itself under this maximum size budget using a least-recently used (LRU) eviction policy. It is currently used as the underlying data structure for the classic engine plan cache, the SBE plan cache, and the TelemetryStore.

It is a template class where the keys are of type parameter K and the values of type parameter V. The callers use a pointer type for V (either a shared_ptr or a unique_ptr should work). In the case of the classic and SBE plan caches, K is the plan cache key itself which can be a quite large object.

The problem is that LRUKeyValue actually stores multiple copies of each key object of type K: once in the list of key-value pairs which maintains the least-recently used ordering, and again in the hash table which is used for O(1) lookup by key. This doesn't matter much if the key is a small object like an int, but in practice we are storing multiple copies of a potentially quite large object like the classic or SBE plan cache key. We should improve this to store the key just once.