LRU Eviction Policy

[CrystSw]

~~In this implementation, when apcu_store, apcu_add (only on successful addition), apcu_fetch, apcu_entry, apcu_inc, apcu_dec, apcu_cas are used, the access history is updated. If the allocation of shared memory fails, the oldest entries in the access history will be deleted. To enable function, specify ./configure --enable-apcu-lru.~~

This is the implementation of the LRU eviction policy. In this implementation, the access history is updated when using apcu_store, apcu_add (only on successful addition), apcu_fetch, apcu_entry, apcu_inc, apcu_dec, and apcu_cas, and when memory allocation fails, the cache entries are evicted in order of the oldest access history. To enable this feature, set the configuration parameter apc.eviction_policy to lru (the default value is default, which is the conventional behavior). Additionally, by setting apc.smart, it is possible to adjust the amount of the cache entries to be evicted (the required size for allocation * apc.smart will be evicted).

[mszabo-wikia]

Interesting! I assume this patch is to make it easier to use APCu as a general purpose in-memory cache. If so, we ended up having to optimize for that case recently, but we ended up taking a slightly different approach—we just tweaked apc_cache_entry_soft_expired such that it would also apply the configured apc.ttl value to entries with an explicit TTL set as well, not just entries without a TTL. The end result is not strictly LRU, but it does accomplish the goal of only keeping hot data in the cache assuming a well-configured apc.ttl, and it does not require any additional bookkeeping beyond the atime tracking that's already implemented. Perhaps this alternative is worth considering?

In either case, from an end-user perspective, I'm not sure if this behavior should be gated behind a config flag—it could create additional complexity as distributions and other packagers would end up making the decision whether to use APCu with LRU functionality or not. I think this is better suited to be an INI flag instead, so that APCU end-users, not distribution package maintainers, can configure how their cache behaves. What do you think?

[CrystSw]

@mszabo-wikia Thanks for your comment!

I think your approach is simple yet effective. However, if all entries are active (not expired) and the shared memory is full, all entries will be deleted due to apc_cache_wlocked_real_expunge(). This could cause issues like Cache Stampede. Therefore, I think it might be good to have an alternative eviction policy.

In this implementation, I used config flag to reduce extra memory consumption on apc_cache_entry_t. (if LRU is not used, hnext and hprev are unnecessary.) However, considering the management cost, it might be better to manage it via INI flag as you suggested. I will rewrite this part.

[LionsAd]

Great idea! I wanted LRU for APCu since quite a long time.

[CrystSw]

I added a new configuration item apc.eviction_policy. The possible values for this setting are either default or lru (The default value is default). To use the conventional eviction policy, specify default. To use the LRU eviction policy, specify lru.

[mszabo-wikia]

That's great, thank you!