استراترژی های cache eviction متنوع هستند و ما معمولا از ساده ترین و دم دست ترین گزینه که eviction by ttl هست استفاده می کنیم. اما شیوه های مختلفی از eviction وجود داره که میتونه کاربردی باشه. مثلا فرض کنید یه فروشگاه دارید که اطلاعات هر محصول رو کش می کنید با ttl مشخص، احتمالا لود این محصولات یکسان نیست و ممکنه محصولی باشه که خیلی دیده میشه و یک محصولی هست که خیلی دیر به دیر دیده میشه، تو این شرایط بهتره سیاست هوشمندانه تری برای eviction داشته باشیم.


1. Least Recently Used (LRU):
- Evicts the least recently accessed items first.
- Assumes that items accessed recently are more likely to be accessed again soon.
- Implemented using a linked list and a hash map for efficient access and updates.

2. First In, First Out (FIFO):
- Evicts the oldest items in the cache first, regardless of how often or recently they were accessed.
- Implemented using a queue.

3. Least Frequently Used (LFU):
- Evicts the least frequently accessed items first.
- Assumes that items accessed frequently are more likely to be accessed again.
- Can be implemented using a min-heap and a hash map.

4. Most Recently Used (MRU):
- Evicts the most recently accessed items first.
- Useful in scenarios where older items are more likely to be accessed again.
- Implemented using a linked list and a hash map.

5. Random Replacement (RR):
- Evicts a random item from the cache.
- Simple to implement but may not be as efficient in terms of cache performance.

6. Least Recently Used with Time-to-Live (LRU-TTL):
- Combines LRU with a time-to-live (TTL) value for each item.
- Evicts items that have expired (TTL has elapsed) first, then falls back to LRU.

7. Segmented LRU (SLRU):
- Divides the cache into two segments: a probationary segment and a protected segment.
- New items enter the probationary segment and are promoted to the protected segment upon subsequent accesses.
- Evicts items from the probationary segment first.

8. 2Q (Two Queues):
- Uses two queues: one for items accessed once (A1 queue) and one for items accessed multiple times (Am queue).
- Evicts items from the A1 queue first, promoting items to the Am queue upon subsequent accesses.

9. Clock (Second Chance):
- Uses a circular buffer (clock) and a reference bit for each item.
- Evicts items with a reference bit of 0, giving items with a reference bit of 1 a "second chance" by resetting their bit.

10. Adaptive Replacement Cache (ARC):
- Combines LRU and LFU to adaptively balance between recency and frequency.
- Maintains two lists: one for recently accessed items and one for frequently accessed items.
- Adjusts the size of these lists dynamically based on access patterns.

11. Greedy-Dual Size (GDS):
- Evicts items based on a cost-to-size ratio, considering both the cost of fetching the item and its size.
- Useful for caches where items have varying sizes and fetch costs.

12. Time-Aware Least Recently Used (TLRU):
- Extends LRU by considering the time of access and the duration since the last access.
- Evicts items that have not been accessed for the longest time.

13. Write-Once:
- Specifically for write caches, evicts items that have been written once and not read.
- Useful in scenarios where write operations are more frequent than read operations.

14. Not Recently Used (NRU):
- Evicts items that have not been used recently, based on a simple heuristic.
- Often implemented using a single reference bit per item.

15. Low Inter-reference Recency Set (LIRS):
- Focuses on the inter-reference recency, which is the time between consecutive accesses to the same item.
- Evicts items with low inter-reference recency.

این مقاله هم خوبه که مطالعه بشه
https://newsletter.systemdesigncodex.com/p/cache-eviction-strategies



@gocasts

Ai for Software
@aicasts_ir