search

tannal / ohmywork

0 stars 0 forks source link

Optimal Probabilistic Cache Stampede Prevention #53

Open tannal opened 5 months ago

tannal commented 5 months ago

https://www.vldb.org/pvldb/vol8/p886-vattani.pdf

https://sources.debian.org/src/firefox-esr/115.9.1esr-1/third_party/python/diskcache/diskcache/recipes.py/?hl=334#L334

tannal commented 1 month ago

缓存雪崩 Cache Stampede

外部重新计算:使用单独的后台进程定期重新生成缓存项 锁定机制:获得锁的请求负责重新生成缓存项 概率性提前过期:每个请求独立做出概率决策是否提前重新生成缓存项

tannal commented 1 month ago

论文提出使用指数分布来优化概率性提前过期方法:

使用Exp(λ)分布来决定提前过期的时间 证明这种方法在减少雪崩规模和控制提前过期时间上是最优的 参数λ不需要依赖请求率就能有效减少雪崩

tannal commented 1 month ago

论文建立了数学模型来分析雪崩规模和提前过期时间:

定义了进程到达模型、间隔分布等概念 证明了指数分布的效果优于均匀分布 给出了指数分布方法的理论上界

实验表明指数分布方法(XFetch)在各种情况下都优于其他方法: 显著减少了雪崩规模 保持了较小的提前过期时间 对不同的请求率都有良好的适应性