Some questions about S3-FIFO

[maypok86]

Hi, I'm currently writing a cache library based on S3-FIFO and intermediately got good results with this eviction policy but I have some questions about this algorithm:

1. What is the correct way to remove a random element from this policy, since many caches need this?
2. My impression is that such good hit ratios are only due to the fact that S3-FIFO uses about twice as many elements as W-TinyLFU. Since in the article the weights of key-value pairs were always equal to 1, and main and ghost had an actual size of 90% of the declared cache capacity, the total size of the cache was not capacity but small capacity + main capacity + ghost capacity = (0.1 + 0.9 + 0.9) * capacity = 1.9 capacity. Is this true or have I misunderstood something?

[1a1a11a]

Hi @maypok86, awesome work!

1. can you elaborate more on the challenge of removing an element? It may depend on how the cache is implemented, log-structured, external managed or slab-based allocation.

2. This is not true. The elements in the ghost queue do not store data, it only keeps the metadata. So the total size of the cache is not 1.9x. If each element is 4K and metadata is 8 byte, then S3-FIFO uses (1+8/4096)x space. Moreover, the ghost queue is often implemented together with the indexing structure to leverage the over-provisioning (see paper https://dl.acm.org/doi/10.1145/3600006.3613147). When comparing it with W-TinyLFU, the latter uses a count-min sketch which stores the frequency of many more objects (>2x).

Does this make sense? If you need help, I am happy to jump on a call. :)

[maypok86]

1. Otter currently stores key-value pairs in structures that are stored in a separate hash table:

type Entry struct {
    key keyType
    value valueType
    frequency uint
    isSmall bool
    isMain bool
    isGhost bool
}

The simplest working way to remove random elements from the queue is to store two more pointers to the previous and next elements in the queue inside this structure. As a result, you can delete elements the same way you would in a doubly-linked list. But I asked this question because it puts additional pressure on GC, and in general it works slower than a queue based on a ring buffer, and ideally I would like to have a solution that requires fewer pointers to the object. But in principle it is not very important.

2. And this is much more important. Actually, I wasn't referring specifically to the memory cost of maintaining a ghost queue but to the fact that a ghost queue seems to require holding items in a hash table. As a cache developer, I don't really care that W-TinyLFU stores frequencies for a large number of items because it doesn't prohibit removing key-value pairs from the main hash table. As a result, the main hash table (and RAM too) will store about capacity of items. But the ghost queue in S3-FIFO seems to require storing items in the hash table (at least that's how it's done in all the implementations I've seen) because of which the hash table will store 1.9 times more items. Also, if we use the advice from the paper and just store the time of inserting an item into the ghost queue and evict items only after a hash collision with another item, then there will be even more items in the hash table since hash collisions are not very frequent events. And since the main hash table using S3-FIFO contains a much larger number of items than the hash table using W-TinyLFU, the hit ratio of such a cache will be higher, but the memory usage will also be higher.

And in current implementations, I don't see preempting items that are in the ghost queue

In py-cacheMon we just overwrite the value with None and then based on the information in the node a decision is made to insert into the main queue instead of the small one. here.

In its implementation, redpanda completely ignores the strict limitation of the ghost queue (just like in the paper about using the time of insertion into the ghost queue).

As a result, I don't really like the use of leaving the key-value pair (which is in the ghost queue) in the main hash table.

It seems that since the ghost queue is only needed to choose whether to insert into the small or main queue, you can only store hashes in a special hash set and a ring queue (since the insertion time can overflow and the size in this case will not be strictly limited). And also remove items from the main hash table when moving from small to ghost queue

I hope I've written something clear at least 😥

[1a1a11a]

This is very clear!

1. there are two options, one is to use pointers, while the other is to leave a tombstone (and waste the space). From my experience, most workloads do not have a lot of delete, and when they have delete, they mostly happen soon after insertion (happening in the small queue, and since the small queue recycles much faster, this makes ring buffer more suitable). So I think the ring buffer approach is better.
2. I see the confusion now. This happens because you store data in the hash table. I think you can store the ghost queue in a separate data structure. For example, you can use a ring buffer and hash set to implement it. Or you can just use a new (and small) hash table that just stores the ghost entries (fingerprint + timestamp). Does this make sense?

If this is not clear, I am happy to jump on a call. :)

[maypok86]

Okay, thank you very much, I think I have a much better idea of what I should do next.

P.S. I apologize for such a long delay in replying to you, work/study overlap ate up all my time.😩

[1a1a11a]

Awesome, let me know if I can help others :)