The CLOCK cache algorithm is quite easy to implement with a reference array recording whether an item has been reference or not, and this is an example. However, it seems that the time complexity of this solution is O(N) (N is the capacity of the cache), since we need to iterate the reference array to find a victim whose reference bit is 0. Is there any more efficient solution?
Another question is how to support del operation efficiently for CLOCK algorithm? There're many resources on how to do get and set operations. But nothing mentioned about del operation. If some items are deleted, e.g. either explicitly deleted or expired with a TTL, there will be some holes in the reference array.
In this case, when we need to find a victim, the following solution should work:
- Element in reference array has 3 state: hole, referenced, not referenced.
- if cache is not full, iterate reference array to find a hole, and use that hole as victim. No item will be evicted. In this case, we don't move the clock hand, and untouched the state of other elements.
- if cache is full, iterate the array with moving the clock hand, to find a victim. Also modify states of elements we passed by from referenced to not referenced.
Again, this also has O(N) complexity. Is there any way to optimize it?