Why this algorithm doesn't degrade?

[funny-falcon]

Looking at the SIEVE's code, I don't get why it doesn't degrade to single item?

I mean, since "hand" always move to the head, it will eventually point at the element at the head. And with great probability, every new access will be to different element, head element will always be evicted, and head's access mark will never be updated.

This history sequence generates patological sequence which is different from raw seqscan (every element is accessed 5 times), but still has hit ratio decreasing to zero with grow of N:

def history(N):
    for i in range(10, N, 2):
        for j in range(-10, -1):
            yield i+j
        yield i
        yield i+1

Here's output of python implementation from https://cachemon.github.io/SIEVE-website/blog/2023/12/17/sieve-is-simpler-than-lru/#appendix for this sequence with N=1000:

999 (Visited: False) -> 998 (Visited: False) -> 10 (Visited: True) -> 8 (Visited: True) -> 7 (Visited: True) -> 6 (Visited: True) -> 5 (Visited: True) -> 4 (Visited: True) -> 3 (Visited: False) -> 2 (Visited: False)

As you see, SIEVE remembers only first 8 elements. Other accesses don't propagate to history part of a cache and so accesses to them are always "misses".

I've instrumented implementation with more logging: https://gist.github.com/funny-falcon/5e7fdd2d2dfc4136d133facc3af763a9
It clearly shows, every access aside first few is miss.

[funny-falcon]

As a relatively dumb fix I suggest kind of "fuse": early restart if there too many "immediate evictions without any hit":

 class SieveCache:
   def __init__(self, capacity):
...
     self._hit = 0
     self._evi = 0
...
   def _evict(self):
     if not self.hand:
       obj = self.tail
       self._evi = 0
     else:
       obj = self.hand
       if obj and not obj.visited:
         self._evi += 1
         if self._evi > self._hit:
           # the fuse is blown
           self._evi = 0
           self._hit = 0
           obj = self.tail
     while obj and obj.visited:
       if self._evi > 0:
         self._evi -= 1
...
   def access(self, x):
     if x in self.cache:
       self._hit += 1
...

It at least partially solves patological case above: raises hit ratio to 0.39 . It is still lesser than simplest Clock (0.725), but greater than zero.

Certainly, I don't claim it is best "fuse" ever. And I didn't test it on other workloads/traces. I believe, you'll find some better kind of safety valve than this one.

[1a1a11a]

Hi @funny-falcon Great observation! Yes, it is easy to create an adversary workload for SIEVE. Just like you can create adversarial workloads to make a cache useless. However, in today's world, with a large cache serving a large number of tenants, the workload tends to follow Zipf's law, which is where SIEVE excels. I like your idea of handling the pathological case, do you plan to use it in a product or research project?

[funny-falcon]

I'm looking for a better replacement algorithm for PostgreSQL's shared buffers for proprietary fork.

I’m fear a bit of this weakness of SIEVE, so I doubt it will be used. And other man will do actual experiments, so I can’t promise anything about measurements.

If you find my idea worthy, I will give it away.

[1a1a11a]

For PostgreSQL, I would not recommend SIEVE, take a look at S3-FIFO. :)

[funny-falcon]

Yes, S3-FIFO looks more promising ))

In fact, GClock is implemented in very scalable way in Pg. It would be hard to replace it.