4 ms·

I feel like a simple improvement to LRU is to not promote on every fetch. This adds some frequency bias into the mix and reduces the need to synchronize between

by latch 3y ago

I feel like a simple improvement to LRU is to not promote on every fetch. This adds some frequency bias into the mix and reduces the need to synchronize between threads. Is this a known/used technique?

NovaX 3y ago
Yes, basically you sample requests to improve concurrency and rely on the hottest entries to be more frequently observed in the sample. Memcached uses 60s intervals between promotions and a try-lock guard. A small variation is to do this probabilistically using a thread-local random. Caffeine (BP-Wrapper) decouples the event from the policy by recording into an array of ring buffers hashed to by the thread id. This serves to spread out contention and drains them under a try-lock to update the eviction policy. When the buffers fill up to quickly then it will drop events instead of blocking. This allows the cache to shed load by reducing the sample quality if a burst of activity. Sieve is a very slight modification to the classic Clock algorithm (1969, Multics) which is a well known and commonly used pseudo LRU. The clock hand is a cursor to scan from and to insert behind, where instead they separated it to maintain FIFO insertion order. Clock and its variations are probably the most commonly used caches, e.g. Linux's page cache and Postgres' buffer pool. Sieve decoupling the hand from the insertion point so that new arrivals are evicted sooner, so the benefit is very workload dependent. Sampled policies are another common policy type, e.g. where the timestamp is updated on access. Then on eviction a random subset is chosen and a utility function discards the least valuable. Since there are no promotions it is nice for simple concurrent caches and mimics a classic lru or lfu policy. In short, a concurrent cache will not promote synchronously on every access event. That is only done as a strawman comparison for a simple baseline, though its actually good enough for many simple use-cases. It would be very misleading if researchers pretended that is how concurrent LRU-style caches are implemented.
- quangtung 3y ago
  Do you mention the old version of memcached? Newer versions seem doesn't need that 60s anymore. The architecture feels similar to BP-Wrapper. Ref: https://memcached.org/blog/modern-lru/ https://memcached.org/blog/modern-lru/
  - NovaX 3y ago
    Oh, thank you! I didn't realize that LRU Maintainer Thread was more than an expiration reaper. When it was first being introduced that was its first responsibility as lazy expiration removal by size eviction meant dead entries wasted capacity. It was all work in progress when I had read about it [1] and talked to dormando, so it got fuzzy. The compat code [2, 3] might have also thrown me off if I only looked at the setting and not the usage. Its a neat variant to all of these ideas. [1] https://github.com/memcached/memcached/pull/97 https://github.com/memcached/memcached/pull/97 [2] https://github.com/memcached/memcached/blob/9723c0ea8ec1237b8364410ba982af8ea020a2b6/memcached.h#L103-L108 https://github.com/memcached/memcached/blob/9723c0ea8ec1237b... [3] https://github.com/memcached/memcached/blob/9723c0ea8ec1237b8364410ba982af8ea020a2b6/items.c#L562-L589 https://github.com/memcached/memcached/blob/9723c0ea8ec1237b...

by latch 3y ago

NovaX 3y ago

Yes, basically you sample requests to improve concurrency and rely on the hottest entries to be more frequently observed in the sample. Memcached uses 60s intervals between promotions and a try-lock guard. A small variation is to do this probabilistically using a thread-local random. Caffeine (BP-Wrapper) decouples the event from the policy by recording into an array of ring buffers hashed to by the thread id. This serves to spread out contention and drains them under a try-lock to update the eviction policy. When the buffers fill up to quickly then it will drop events instead of blocking. This allows the cache to shed load by reducing the sample quality if a burst of activity. Sieve is a very slight modification to the classic Clock algorithm (1969, Multics) which is a well known and commonly used pseudo LRU. The clock hand is a cursor to scan from and to insert behind, where instead they separated it to maintain FIFO insertion order. Clock and its variations are probably the most commonly used caches, e.g. Linux's page cache and Postgres' buffer pool. Sieve decoupling the hand from the insertion point so that new arrivals are evicted sooner, so the benefit is very workload dependent. Sampled policies are another common policy type, e.g. where the timestamp is updated on access. Then on eviction a random subset is chosen and a utility function discards the least valuable. Since there are no promotions it is nice for simple concurrent caches and mimics a classic lru or lfu policy. In short, a concurrent cache will not promote synchronously on every access event. That is only done as a strawman comparison for a simple baseline, though its actually good enough for many simple use-cases. It would be very misleading if researchers pretended that is how concurrent LRU-style caches are implemented.

quangtung 3y ago
Do you mention the old version of memcached? Newer versions seem doesn't need that 60s anymore. The architecture feels similar to BP-Wrapper. Ref: https://memcached.org/blog/modern-lru/ https://memcached.org/blog/modern-lru/
- NovaX 3y ago
  Oh, thank you! I didn't realize that LRU Maintainer Thread was more than an expiration reaper. When it was first being introduced that was its first responsibility as lazy expiration removal by size eviction meant dead entries wasted capacity. It was all work in progress when I had read about it [1] and talked to dormando, so it got fuzzy. The compat code [2, 3] might have also thrown me off if I only looked at the setting and not the usage. Its a neat variant to all of these ideas. [1] https://github.com/memcached/memcached/pull/97 https://github.com/memcached/memcached/pull/97 [2] https://github.com/memcached/memcached/blob/9723c0ea8ec1237b8364410ba982af8ea020a2b6/memcached.h#L103-L108 https://github.com/memcached/memcached/blob/9723c0ea8ec1237b... [3] https://github.com/memcached/memcached/blob/9723c0ea8ec1237b8364410ba982af8ea020a2b6/items.c#L562-L589 https://github.com/memcached/memcached/blob/9723c0ea8ec1237b...