folly::GenerationalCacheMap

Description

Entries live in one of two generations. A lookup checks the recent generation and then the older one; an insertion goes into the recent one. When the recent generation fills, the generations rotate: the recent one becomes the older one, and the previous older one is discarded. A hit in the older generation is copied back into the recent one, so a key that stays in use survives indefinitely, while one that falls out of use is dropped within two rotations.

Compared with Synchronized<EvictingCacheMap>:

• A lookup takes no lock, and on a hit in the recent generation mutates no shared state. EvictingCacheMap must take a write lock on every hit purely to reorder its intrusive LRU list, which serializes readers against each other.

• Eviction is coarse. Recency is tracked only at the granularity of "which generation", so an entry can be evicted while less recently used entries survive. That imprecision is what buys the point above.

Compared with a fixed-capacity map that never evicts, which would also give lock-free lookups, this tolerates drift: a key set that shifts over time, or a burst of distinct keys early on, cannot permanently fill it and lock out whatever is actually in use later.

The operating point it is built for is a working set comfortably smaller than capacity that drifts slowly, with keys gradually falling out of use as new ones appear, rather than churning wholesale. There, almost every lookup hits the recent generation and mutates nothing shared: no lock, no reference count, no LRU bookkeeping. Insertions, promotions and rotations happen only at the speed of the drift, so throughput scales close to linearly in the number of threads.

Away from that operating point both properties degrade together. A working set larger than capacity means every rotation discards entries that are still in use, so they are inserted again, and every cycle promotes everything that survived: the hit rate falls, and exactly the write traffic that lookups were meant to avoid comes back. Watch rotations() to tell the two regimes apart; see below.

It does not suit callers that need precise eviction, an exact size, or a hard memory bound.

capacity is the approximate number of entries retained. It is approximate in both directions: inserters racing a rotation overshoot the threshold slightly, and a discarded generation is freed asynchronously, so the resident count lags. Overshoot is bounded, since an inserter that finds the map at twice the rotation threshold waits for the rotation rather than adding to it, but it is a bound, not a guarantee of staying near capacity under a heavy enough insert rate.

Value must be copy-constructible, since promotion copies it.