[colonelxc]

From the website (https://s3fifo.com/), it claims that it needs no locking (backing scalability claims). This seems like an important part of their work too, unless I've missed some obvious trick that everyone uses. Naively, I would think that you can't update a hash table (to find the cache items efficiently?) and the queues at the same time without a lock. They surely aren't doing a linear search through the queue looking for a match

[kccqzy]

You don't have to atomically update a hash table and the queue. You can first insert into the queue, then update the hash table.

The article does seem to make assumptions that there is a lockless hash table and a lockless queue. It clarified that the lockless queue need not support removal from the middle.