on S3-FIFO being problematic, have you looked into TinyUFO? (part of cloudflare/pingora)
replies(1):
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.