on S3-FIFO being problematic, have you looked into TinyUFO? (part of cloudflare/pingora)

No, I haven't looked into it, but the combination of "lock-free" and "S3-FIFO" raises some red flags for me :)

I don't quite understand the specific rationale for replacing segmented LRU with S3-FIFO. If I remember correctly, even the original authors stated it doesn't provide significant benefits [1].

Regarding TinyUFO - are you using lock-free queues? Has the algorithmic complexity of TinyLFU changed? (In the base version, S3-FIFO is O(n)). How easy is it to add new features? With lock-free queues, even implementing a decent expiration policy becomes a major challenge.

[1]: https://github.com/Yiling-J/theine/issues/21