182
Scalable Replacement Policy
An LRU cache is traditionally implemented as a doubly linked list. When an item is
retrieved from this list, it gets moved from the middle to the front of the list, so it is not
evicted. In a multithreaded environment, multiple threads may contend with the front
element, all trying to move elements being retrieved to the front. Therefore, the front
element is always locked (along with other locks) before moving the element being
retrieved, which results in lock contention. This method is not scalable and is inefficient.
A buffer-based LRU policy creates a scalable and efficient replacement policy. A nonblocking ring buffer is placed in front of the LRU linked list to track the elements being
retrieved. When an element is retrieved, it is added to this buffer, and only when the
buffer is full (or the element is being evicted), the linked list is locked, and the elements
in that buffer are processed and moved to the front of the list. This method preserves the
LRU policy and provides a scalable LRU mechanism with minimal performance impact.
Figure 10-7 shows a ring buffer-based design for the LRU algorithm.
Figure 10-7. A ring buffer-based LRU design
Chapter 10 Volatile Use of persistent MeMory
Scalable Replacement Policy
An LRU cache is traditionally implemented as a doubly linked list. When an item is
retrieved from this list, it gets moved from the middle to the front of the list, so it is not
evicted. In a multithreaded environment, multiple threads may contend with the front
element, all trying to move elements being retrieved to the front. Therefore, the front
element is always locked (along with other locks) before moving the element being
retrieved, which results in lock contention. This method is not scalable and is inefficient.
A buffer-based LRU policy creates a scalable and efficient replacement policy. A nonblocking ring buffer is placed in front of the LRU linked list to track the elements being
retrieved. When an element is retrieved, it is added to this buffer, and only when the
buffer is full (or the element is being evicted), the linked list is locked, and the elements
in that buffer are processed and moved to the front of the list. This method preserves the
LRU policy and provides a scalable LRU mechanism with minimal performance impact.
Figure 10-7 shows a ring buffer-based design for the LRU algorithm.
Figure 10-7. A ring buffer-based LRU design
Chapter 10 Volatile Use of persistent MeMory