[hknmtt]

>On a cache hit, SIEVE marks the object as visited. On a cache miss, SIEVE checks the object pointed to by the hand. If the object has been visited, its visited bit is reset, and the hand moves to the next position, keeping the retained object in its original position in the queue. This continues until an unvisited object is found and evicted. After eviction, the hand moves to the next position.

Dude, what?

[vidarh]

Look at the animation. The description is confusing.

It uses a list that's treated as a ring buffer to keep track of keys currently in the cache.

The "hand" is a pointer that points to a given node in that ring buffer.

When the cache is full and a space is needed, the "hand" moves through that buffer (possibly wrapping around). Whenever it points at a node that hasn't been touched since the last time it was seen, that node is evicted and you're done for this time, otherwise it clears the visited bit for that node and keeps going.

(You're always guaranteed to find a node to evict, because worst case you scan through the entire set of nodes, and find the first node you cleared the visited bit of)

[Epa095]

Maybe it's a bit odd that it resets the 'visited' bit on non-related objects (why are they suddenly not visited)?

For me it helped to rather think about 'visited' as a special case of a counter called 'valuation' (or something like that). New objects come in with valuation 1, on cache hits a objects valuation is set to 2, and when the hand moves left it decreases objects valuations until it reaches one that gets valuation 0, then it's evicted immediately. One could easily imagine a modified algorithm where 'valuation' could be increased further than 2 if an object got visited many times (but then eviction would be much slower in some cases).

Then this is all optimized by using a bool instead of an int since we truncate 'valuation' at max 2.

Idk why they choose to call it 'visited' though.

[vidarh]

What "visited" really denotes is "accessed since the last time the hand reached this node".

[toast0]

Yahoo has (or had) a very similar 'cache' for tracking abuse (ydod). As I recall it was patented, but I can't find the patent to confirm it has expired.

Really handy for tracking potentially abusive ips, if your table is big enough; on a request, check if it's in the table - if so increase the count and if it's above the theshold mark it. If it's not in the list, decrement the current item and move current to the next item.

An agressive user will clear out a slot for itself, and rapidly hit the threshold. Other users will come and go. You can iterate through and try to always clear a spot for a new entry, but it might not be necessary, depending on what you're caching.

[echelon]

The hand is a pointer on the queue to the current cache item being inspected. The cache miss eviction behavior depends on if the pointed to element is marked as visited.

If you're familiar with LRU/LFU, ring buffers (though this isn't such), and data structures this will probably make a lot more sense.

A rigorous course in data structures is fantastic for any engineer. Everything is data structures and algorithms at the end of the day.