LRU cache on a single machine which is multi threaded - how does the LRU part work?


#1

In this section, it goes over how to implement the concurrent hashmap but I don’t understand what happened to the LRU part - how does the eviction happen? I get putting values on a per row linked list, but with the classic LRU implementation, items gets moved around and aged out in the doubly linked list implementation. In this part, I am not seeing how items are aged out. Can someone explain what is going on here or does the LRU concept not play a part here?


#2

This is my interpretation of how to solve the question you are posing. Given we use the design suggested in the problem (hashmap with hashed request keys for keys and linked lists for values) we could define a maximum capacity for the linked list. Since, theoretically, new write requests should be evenly distributed by the hashing function, each linked list should receive new write requests at about the same rate. Then if a hashmap row is full, the last value of that row would be rejected when a new write request comes in. Assuming a linked list length of 100 nodes, this would mean that the bottom 1% of cached values could be rejected. Realistically, this also means that values can be rejected from the cache before the cache is actually completely full. This would need to be taken into consideration when sizing the system.