SIEVE: efficient cache eviction

https://www.usenix.org/publications/loginonline/sieve-cache-eviction-can-be-simple-effective-and-scalable

Data structure. SIEVE requires only one FIFO list and one pointer called a “hand”. The list maintains the insertion order between objects. Each object in the list uses one bit to track the visited status. The hand points to the next eviction candidate in the cache and moves from the tail to the head of the list. Note that unlike some existing algorithms, e.g., LRU, FIFO, and CLOCK, in which the eviction candidate is always the tail object, the eviction candidate in SIEVE is an object that can be in the middle of the list. 

SIEVE operations. A cache hit in SIEVE sets the visited bit of the accessed object to true. For a popular object whose visited bit is already set, cache hits do not perform any metadata update. During a cache miss, SIEVE examines the object pointed by the hand. If it has been visited, the visited bit is reset, and the hand moves to the next position (the retained object stays in the original position of the list). It continues this process until it encounters an object that has not been visited, and it evicts the object. After the eviction, the hand points to the previous object in the list. While an evicted object is in the middle of the queue most of the time, a new object is always inserted into the head of the queue. In other words, the new objects and the retained objects are not mixed together.

dybr

 A weird day.

First, the "pr from bot", which I had fixed two days ago, and which the bitch (Sam) rolled back, because I did not follow her unwritten rules, was revived again, and I was again supposed to go ahead and fix it. I just wrote that there is a pr with a fix, and feel free to revive it and merge - or at least review. 

Second, the "remove persistence module" pr, that I sent yesterday, got interesting comments from Brad: we cannot remove the module, because some deployment scripts may feel bad about missing module, so he suggested that I move the kafka sinks, to another module (which I did), but keep this module running empty (that is, no endpoints, just a server waiting for a call from above.) I believe they will want to have "health" endpoint at least, but let them ask for it first. Ok, whatever, I promised to restore that "empty server" - but not right away. Monday.

Third, Bermi kind of agreed that his formatter slightly misbehaves, but he suggested that it's the endpoint call format that is not good enough. Well, whatever. I can always fork it, and do with it whatever I choose; Jeremey already said that this could be a good idea.

But anyway, ok, I improved this and that, and the docs started looking better (and stabler, not including values of x-request-id into README). And I would have sent Bermi a pr - but the problem is, one test fails. How come? FIIK. I stashed the changes - that test still fails. I switched the branch to 'main' that test still fails. I rolled back to something before I even touched that project - tons of tests started failing. So, fuck (but not fork) it, I got back to my latest version, and started experimenting. Ok, one of the reasons was that port forwarding was expired. That part is manageable... still failures. So I spent the rest of the day looking deeper into his weird shell scripts, weird Makefile, trying to catch all those problems that are usually not reported, but just hidden, returning '1' instead. Shell programmers. They think they can. 

Oh, btw, but at least the "project under documenting" can be sent for review, that part looks better now.