[Navy BlockCache] Does Hits-Based Reinsertion Policy + FIFO run into a problem if all entries are reinserted?

[dannycho7]

In the docs, a hits-based reinsertion policy is mentioned to "better approximate a LRU than the region-based LRU". I have a few questions regarding this policy:

1. If it is better at approximating LRU for keys, is there a reason why hits-based reinsertion + FIFO this isn't the default policy?
2. What happens if my reinsertion policy is configured such that all entries end up being reinserted? For example, let's say I configure the hitsThreshold to be 1 and my traffic is such that all keys are hit quite frequently. Does the system essentially end up not being able to accept new writes at all?

[jaesoo-fb]

Hi @dannycho7,

The problem with the LRU is that it is a region-based LRU as opposed to per-item LRU. The region-based FIFO with reinsertion will basically work as if it is a per-item second chance algorithm.

is there a reason why hits-based reinsertion + FIFO this isn't the default policy?

The hits-based reinsertion could cause the flash wearing out faster because of the reinsertions. So, there are tradeoffs between the amount of flash writes vs. hit rates, and it would be desirable to be configured per applications' needs.

For FIFO, yeah, I agree FIFO could perform better than LRU in some cases. However, this would also depend on the applications' needs.

Does the system essentially end up not being able to accept new writes at all?

No, it doesn't. Instead, when it run out of free regions, the reinsertions will most likely fail and be silently discarded. When there is a free space in the active region, the writes will keep competing with the reinsertions, so, could be slower.

[dannycho7]

Hi @jaesoo-fb. Thank you for getting back to me.

No, it doesn't. Instead, when it run out of free regions, the reinsertions will most likely fail and be silently discarded. When there is a free space in the active region, the writes will keep competing with the reinsertions, so, could be slower.

Do the writes retry forever or is there a limit to the number of retries? Are there any facilities in place to ensure fairness to allow new writes to come through or are you expecting that reinsertions are probabilistically interleaved with incoming writes? I am imagining the problem where reinsertions are in fact being inserted into free regions (so they are not silently discarded), but end up taking all of them before new writes can.

[jaesoo-fb]

Hi @dannycho7

There is no retry limits for insertion for the allocation failure. The reinsertion will give up immediately if there is no space left in the free region

Are there any facilities in place to ensure fairness to allow new writes to come through or are you expecting that reinsertions are probabilistically interleaved with incoming writes?

The BlockCache does not have any support for the fairness.

[dannycho7]

I see, thanks! Would it be fair to say the write throughput of the system (wrt to writes explicitly requested by the user) is limited under such a scenario? It seems tricky to have to tune for a fixed threshold for hits-based reinsertion because the workload could change over time.

[jaesoo-fb]

@dannycho7 Yeah, I think so.