4 ms·

FIFO queues are all you need for cache eviction

38 points by azeemba 3y ago

avidiax 3y ago
> Can we tune the adaptive algorithms to work better? > We have also experimented with using an adaptive algorithm to change the size of FIFO queues in S3-FIFO. The results show that using an adaptive algorithm can improve the tail performance, but degrade overall performance. We find that tuning the adaptive algorithm is very challenging. > In fact, adaptive algorithms all have many parameters. For example, queue resizing requires several parameters, e.g., the frequency of resizing, the amount of space moved each time, the lower bound of queue sizes, and the threshold for trigger resizing. > Besides the many hard-to-tune parameters, adaptive algorithms adapt based on observation of the past. However, the past may not predict the future. We find that small perturbations in the workload can cause the adaptive algorithm to overreact. It is unclear how to balance between under-reaction and overreaction without introducing more parameters. Moreover, some adaptive algorithms implicitly assume that the miss ratio curve is convex because following the gradient direction leads to the global optimum. However, the miss ratio curves of scan-heavy workloads are often not convex. Maybe this is where further research should go. * Can we reduce the dimensionality of the parameters for more complicated algorithms? That would mean taking n parameters and mapping them to 1 or 2 metaparameters that are imperfect, but maintain a continuous and near linear performance tradeoff throughout their range. Then adaptive algorithms are easier to reason about. * Knowledge of the past is both a shortcoming and potential strength for adaptation. Ex: what if we can learn a weight for every hour of the day, every day of the week, every day of the month, the name of every job, etc.? This gives you fast reaction based on history, and gradient ascent can handle the rest.
withinboredom 3y ago
This is quite brilliant and it was interesting to see some similarities to FASTER which uses a similar-ish method for a WAL.
colonelxc 3y ago
From the website (https://s3fifo.com/ https://s3fifo.com/), it claims that it needs no locking (backing scalability claims). This seems like an important part of their work too, unless I've missed some obvious trick that everyone uses. Naively, I would think that you can't update a hash table (to find the cache items efficiently?) and the queues at the same time without a lock. They surely aren't doing a linear search through the queue looking for a match
- deleted 3y ago
  [deleted]
- kccqzy 3y ago
  You don't have to atomically update a hash table and the queue. You can first insert into the queue, then update the hash table. The article does seem to make assumptions that there is a lockless hash table and a lockless queue. It clarified that the lockless queue need not support removal from the middle.
kccqzy 3y ago
This reminds me of generational garbage collectors. They typically have a nursery where new objects are allocated in, and a small number of generations, whereby every object that survives a garbage collection is promoted to an older generation. Here we also have essentially two queues for that.

38 points by azeemba 3y ago

> Can we tune the adaptive algorithms to work better? > We have also experimented with using an adaptive algorithm to change the size of FIFO queues in S3-FIFO. The results show that using an adaptive algorithm can improve the tail performance, but degrade overall performance. We find that tuning the adaptive algorithm is very challenging. > In fact, adaptive algorithms all have many parameters. For example, queue resizing requires several parameters, e.g., the frequency of resizing, the amount of space moved each time, the lower bound of queue sizes, and the threshold for trigger resizing. > Besides the many hard-to-tune parameters, adaptive algorithms adapt based on observation of the past. However, the past may not predict the future. We find that small perturbations in the workload can cause the adaptive algorithm to overreact. It is unclear how to balance between under-reaction and overreaction without introducing more parameters. Moreover, some adaptive algorithms implicitly assume that the miss ratio curve is convex because following the gradient direction leads to the global optimum. However, the miss ratio curves of scan-heavy workloads are often not convex. Maybe this is where further research should go. * Can we reduce the dimensionality of the parameters for more complicated algorithms? That would mean taking n parameters and mapping them to 1 or 2 metaparameters that are imperfect, but maintain a continuous and near linear performance tradeoff throughout their range. Then adaptive algorithms are easier to reason about. * Knowledge of the past is both a shortcoming and potential strength for adaptation. Ex: what if we can learn a weight for every hour of the day, every day of the week, every day of the month, the name of every job, etc.? This gives you fast reaction based on history, and gradient ascent can handle the rest.

withinboredom 3y ago

This is quite brilliant and it was interesting to see some similarities to FASTER which uses a similar-ish method for a WAL.

colonelxc 3y ago

From the website (https://s3fifo.com/ https://s3fifo.com/), it claims that it needs no locking (backing scalability claims). This seems like an important part of their work too, unless I've missed some obvious trick that everyone uses. Naively, I would think that you can't update a hash table (to find the cache items efficiently?) and the queues at the same time without a lock. They surely aren't doing a linear search through the queue looking for a match

deleted 3y ago
[deleted]
kccqzy 3y ago
You don't have to atomically update a hash table and the queue. You can first insert into the queue, then update the hash table. The article does seem to make assumptions that there is a lockless hash table and a lockless queue. It clarified that the lockless queue need not support removal from the middle.

kccqzy 3y ago

This reminds me of generational garbage collectors. They typically have a nursery where new objects are allocated in, and a small number of generations, whereby every object that survives a garbage collection is promoted to an older generation. Here we also have essentially two queues for that.