Re:DragonFlydb: Cache Design
by jandrewrogers on Tuesday August 16, 2022 @03:06PM
(#32487303)
> the most important part in this design is the realization that we do not need a global order in order to choose an entry to evict
This is a key insight many people miss. The optimal eviction is not computable, so any reasonable approximation will likely have a similar outcome. Given this, it makes sense to pick an approximation that facilitates other objectives, like computational performance.
If think the most important part in this design is the realization that we do not need a global order in order to choose an entry to evict: other heuristics like LRU, LFU, frecency - they strive to provide a single number, a metric. Obviously this metric lies because a single number can not represent well both qualities like frequency and recency. DashCache, on the other hand, does not try to do it at all. Instead, it implicitly defines a partial order between entries in the same bucket or segment....