SIEVE: efficient cache eviction
Jun. 14th, 2024 03:05 pmData structure. SIEVE requires only one FIFO list and one pointer called a “hand”. The list maintains the insertion order between objects. Each object in the list uses one bit to track the visited status. The hand points to the next eviction candidate in the cache and moves from the tail to the head of the list. Note that unlike some existing algorithms, e.g., LRU, FIFO, and CLOCK, in which the eviction candidate is always the tail object, the eviction candidate in SIEVE is an object that can be in the middle of the list.
SIEVE operations. A cache hit in SIEVE sets the visited bit of the accessed object to true. For a popular object whose visited bit is already set, cache hits do not perform any metadata update. During a cache miss, SIEVE examines the object pointed by the hand. If it has been visited, the visited bit is reset, and the hand moves to the next position (the retained object stays in the original position of the list). It continues this process until it encounters an object that has not been visited, and it evicts the object. After the eviction, the hand points to the previous object in the list. While an evicted object is in the middle of the queue most of the time, a new object is always inserted into the head of the queue. In other words, the new objects and the retained objects are not mixed together.