作者:尚卓燃(PsiACE)
澳门科技大学在读硕士,Databend 研发工程师实习生
Apache OpenDAL(Incubating) Committer
论文原文:
GL-Cache: Group-level learning for efficient and high-performance caching | FAST '23
源码 地址:
https://github.com/Thesys-lab/fast23-GLCache
论文贡献:
提出 Group-level Learning ,利用多对象组的特征来适应工作负荷和缓存大小,通过分组来积累更强的学习信号,学习成本均摊到对象级别。GL-Cache 不仅提供高效益的学习型缓存,还能够保证缓存系统的高吞吐量。
网络应用程序在很大程度上依赖于软件缓存来实现低延迟、高吞吐的服务。为了适应不断变化的工作负载,近年来设计出一些学习型缓存(学习型缓存替换策略,特别是逐出策略),大致可以分为三种:对象级别学习、从分布中学习和从简单专家(策略集)中学习。本论文认为现有方法的学习粒度要么太细(对象级别),导致计算和存储成本过大,要么太粗(工作负载或专家策略级),无法捕捉对象之间的差异,留下了相当大的效益差距。(这里的效益主要是由 hits/miss ratio 进行评估)
在本论文中,作者针对缓存设计了一种新的学习方法——组级别学习。该方法将相似的对象聚类成组,并按照组进行学习和逐出操作。组级学习可以积累更多的信号,能够利用更多具有自适应权重的特征,并将成本分摊到对象上,从而实现高效益和高吞吐量。
作者使用 GL-Cache 在生产环境下演示了组级别学习,并对 118 个生产块 I/O 和 CDN 缓存跟踪进行评估。结果显示 GL-Cache 比最先进设计具有更高命中率和更高吞吐量。与 LRB (对象级别)相比,GL-Cache 平均提升 228 倍吞吐量和 7% 命中率;对于 CDN 缓存跟踪 P90 的情况下,GL-Cache 比 LRB 提供了25% 的命中率提升;与所有其他类型最好表现者相比较,在平均值方面 GL-Cache 提升64% 吞吐量、3% 命中率,在 P90 方面提升13% 命中率。
在正式讨论 GL-Cache 之前,让我们先来看一下缓存和学习型缓存相关的一些内容。
上图反映了计算机体系中的存储层次结构,可以看到明显的趋势是速度越大,容量越小。图中的缓存位于 CPU 内部,用于协调 CPU 运行速度和内存读取速度。
一般而言,缓存是位于速度相差较大的两种存储之间,用于协调两者数据传输速度差异的结构。无论是哪一层次的缓存都面临一个同样的问题:当容量有限的缓存的空闲空间全部用完后,又有新的内容需要添加进缓存时,如何挑选并舍弃原有的部分内容,从而腾出空间放入这些新的内容。
本论文讨论的是位于内存/磁盘之间的缓存而不是芯片上的缓存。
本文主要选用以下两个方面的评价标准。
本论文工作属于学习型策略,但得益于设计实现上的一些决策,在效益和性能上都取得了比较好的收益。
前面介绍了学习型缓存,这是一类结合机器学习来改善缓存适应性的方法,根据本论文的分类,大致可以分成以下几种:
机器学习经常用于改进决策过程。将缓存管理和机器学习相结合的主要考虑因素是提高性能,包括如何增加吞吐量以及如何提高命中率。
为什么要使用 机器学习
为什么不使用 机器学习
前面花了大量的篇幅介绍缓存和机器学习在缓存中的应用,接下来让我们将目光转向本文的主角 GL-Cache 。
GL-Cache 采用组级学习的思想,将对象分组,并按组聚集特征。
GL-Cache 将对象划分成若干组,定期跟踪每个对象组的特征,进行采样并形成特征快照,对每个特征快照计算效用并用于模型的训练,然后利用训练得到的模型进行预测并作出逐出决策。
GL-Cache 选择了基于插入时间的分组策略,简单且有效。主要是以下几点:
当然,也可以根据实际需要设计不同的分组策略,进一步适应工作负载。
效用,用来度量逐出或保留对象组的后续影响。根据设计,效用较低的对象组更应该被逐出。
对象和对象之间的比较非常容易,但是对于组与组之间,尚且缺乏有效的衡量方法。论文设计了一个新的效用函数来量化对象组的效用。
在设计效用时主要的决策如下:
上图第一个式子展示了对于单个对象的效用函数计算,T(o)(t) 表示下一次请求的时间,而 S(o) 表示对象的大小。而组的效用可以用对象效用的累加来计算。
GL-Cache 选用了 7 种特征进行学习,并且进行了分类。
动态特征,也就是在访问请求时需要更新的特征:
静态特征,不需要实时更新,只需要计算一次:
其中,静态特征的前三个又被称为 上下文特征 ,能够反映工作负载的变化情况。比如在数据备份时,可能会观测到写速率、未命中率和请求速率都在增加。
模型比较简单,利用梯度提升树设计回归算法作为目标函数。感兴趣的话可以阅读 xgboost 相关论文和本论文相关源码,这里就不进行赘述。
GL-Cache 使用训练得到的模型来对对象组进行排序,并且预测其效用,并选择效用最低的组进行逐出。
但是,GL-Cache 的逐出并不是直接删除对应的组,而是采用了合并逐出(Merge Evict)的思想:
由于选择插入时间接近的几个相邻组作为合并对象,逐出后形成的新组仍然可以保证组内对象特征的相似性。
让我们略过评估相关的实验设计和结果细节,只是简单看一下基于组级学习的算法在潜在效益(命中率)和性能(吞吐量)象限上所处的位置。
本论文提出了一种名为 “组级学习(Group-level Learning)” 的新方法,利用机器学习提高缓存效益。组级学习利用多个对象组特征预测和清除效用最低的对象组,在适应工作负载和缓存大小的同时,积累更强的信号进行学习,并将学习成本分摊到对象上。因此,它可以用极小的成本做出更好的逐出决策。作者在生产级缓存中构建 GL-Cache 来展示组级学习,并在 118 个生产块 I/O 和 CDN 跟踪数据上进行评估。与所有其他已知缓存相比,GL-Cache 实现了显著更高的吞吐量,同时保持较高的命中率。因此,GL-Cache 为在生产系统中采用学习型缓存铺平了道路。
|