⾯向现代分层存储的 Caching 技术漫谈｜Data Infra 研究社第十九期（含资料发布）

2024-07-18
北京
本文字数：7051 字
阅读完需：约 23 分钟

大家好，我是 Databend 研发工程师尚卓燃，很长时间没有在 Data Infra 和大家见面了，今天给大家带来的分享是《面向现代分层存储的 Caching 技术漫谈》。 Caching 其实就是缓存，在像 Databend 这样的大数据处理系统中是非常常见的一项技术。但在最近几年的研究中，出现了一些新的 Caching 设计趋势，包括一些和机器学习结合的方案，本次分享会围绕一些相关论文进行展开。

Part 1 Caching vs. Tiering

在复杂的分层存储模型中，不同层级的存储设备（如内存、闪存、机械硬盘、远程存储、磁带机等）共同构成一个金字塔式结构。每一层的设计和算法需要考虑不同层级带来的性能影响和数据移动策略。为了简化讨论，我们可以将分层存储模型抽象为两层：

容量层：容量大、速度慢、价格低廉，适用于大量数据的存储。
性能层：容量小、速度快、价格高，适用于存放热数据来优化数据访问路径的性能。分层存储的目标可以看成是通过少量的高性能存储设备提升整体性能，并且控制存储系统的整体拥有成本。

缓存（Caching）和分层（Tiering）是两种优化数据存储和访问性能的重要技术，在过去几十年来被广泛应用在各种数据处理系统之中，它们都需要在高性能存储设备上保存高频访问的数据，以提高系统的整体性能。Caching 是将数据从容量层复制到性能层，并逐出最不常用的对象。数据移动粒度较细，在性能层保留热数据的副本。Tiering 将数据从容量层移动到性能层，通常以较长周期运作，数据移动粒度较粗。容量层和性能层共同组成完整的数据集。那缓存和分层到底有哪些区别？

数据移动方式：

缓存：数据从容量层复制到性能层，容量层保留完整的数据副本。
分层存储：数据从容量层移动到性能层，容量层加性能层共同构成完整的数据集。

数据移动频率：

缓存：数据移动频率较高，粒度较细，能够及时响应动态工作负载。
分层存储：数据移动频率较低，粒度较粗，通常以几天或几个小时为一个周期。

应用场景：

缓存：适用于需要快速响应的系统，如高频访问的 Web 应用、实时数据处理等。
分层存储：适用于需要优化存储成本和性能的系统，如大规模数据存储、数据湖等。

经典数仓和现代云数仓都可以简化为「本地-远程」的分层存储模型，不管是 Caching 还是 Tiering，都有几率取得最大化的性能效益。在过去基于 HDFS 的一些经典数仓相关的论文中，基于 Tiering 的技术已经得到广泛讨论。但是现代基于对象存储设计的云数仓，Caching 比 Tiering 得到了更为广泛的应用。现代云数据仓库（如 Databend 和 Snowflake）的分层存储结构中，通常包括内存、SSD、远程对象存储三层。常规做法是在内存中缓存元数据和计算结果，在 SSD 上缓存当前处理的数据副本，在远程对象存储上长期存放所有数据（比如归档数据）。此外，部分结果集也可能会被放置在对象存储之中，由于计算花费的时间远远超过数据存取的时间，这部分也可以视作是 Caching 技术的应用。

Tiering 采用固定周期移动数据，可能某种程度上比 Caching 更经济。那么，为什么现代云数仓，在设计决策上广泛采用 Caching，而不是 Tiering？

经济性：

使用云厂商提供的对象存储和 EBS 等服务，不需要更多的人力，不需要采购硬件，也不需要定期更新硬件，结合云上灵活的按需按量的计费机制，整体维护成本可能更低。

云原生环境的弹性实例：

弹性实例的临时唤起和关闭使得决定分层存储的时机变得复杂。而 Caching 技术则无需考虑复杂的分层时机，每次未命中时直接缓存数据，机会成本比 Tiering 更低。
由于 Tiering 相当于数据发生移动，在实例的生命周期终止以后，数据管理和完整性的保障会成为新的挑战；而 Caching 允许直接将对应的性能层空间释放，运维更加方便。

多租户和动态工作负载：

不同业务场景和不同租户之间的工作负载差异大，缓存技术能更灵活地应对动态和多变的工作负载，而针对不同的特征去制定分层存储的策略实施难度较大。

存储层次化结构的变化：

现代快速存储硬件缩小了存储层之间的性能差异，从过去的百倍到现在可能不足十倍。缓存由于在容量层会保持全部数据，可以在性能瓶颈时直接将请求转发到容量层，能够更加充分利用容量层的硬件性能。而 Tiering 技术中，对性能层的请求无法直接转发给容量层，造成系统整体资源的浪费。所以说 Caching 比 Tiering 可能会是一个更好的方式。

Part 2 范式迁移：LRU-like vs. FIFO-like

近年来，缓存逐出算法经历了一次范式迁移，从传统的 LRU-like（最近最少使用）算法向 FIFO-like（先进先出）算法转变。这些算法各有优劣，本文将探讨它们的评价标准、表现及应用场景。通常情况下我们会从五个维度去评价缓存算法：

高效性：高效性是指缓存的未命中率越低，这个缓存设计越高效。未命中率反映的是最后向存储后端发起请求的比例。向容量层发起的请求越少，就说明绝大多数热数据都在性能层里面，有利于优化系统整体性能。此外，考虑到缓存设计目标的不同，有时也会考虑对象大小对缓存的影响，此时可能会使用字节未命中率作为指标。
吞吐量：每秒钟能够处理的请求数量越多，说明缓存的设计越有效。
可扩展性：现在除了一些嵌入式环境外，现代处理器大多具备多核多线程能力。缓存性能应随着 CPU 核心和线程数的增加而提高或者至少不衰退；如果性能反而下降，则可能不适合高并发的环境。
闪存友好性：尽管大多数围绕缓存的讨论都使用内存作为介质（性能层），但是很多现代的数据中心和应用都使用闪存作为缓存层的介质，包括像谷歌的对象存储，Facebook 的 CacheLib。由于闪存寿命有限，要尽可能减少对闪存的写入次数和写放大效应，设计对闪存更友好的缓存算法。
简单性：影响缓存技术应用的重要因素之一是缓存设计的简单性，尽管针对不同系统已经设计了大量的高级缓存算法，但是难以实现和迁移到其他系统之中。简单的算法（如 LRU 和 FIFO）易于设计和实现，得到了最为广泛的应用；而复杂的机器学习算法可能面临实施动力不足的情况。

LRU-like 是最常见的缓存逐出算法，Databend 现在使用的也是非常经典的 LRU 优化实现。LRU-like 被广泛使用是因为数据的访问会呈现出一定的局部性和访问特征，最近使用或者最频繁使用的数据可能会具有更高的重用机会。研究表明，LRU-like 算法在高并发访问下的性能是有缺陷的，可以采用一些优化的设计去弥补这一缺陷，比如对冷热数据再进行二次分区，或者添加 FIFO 结构。 FIFO-like 常见于闪存上的缓存，因为这类算法写入顺序和逐出顺序是一致的。相比 LRU-like 算法，写放大更少，对闪存寿命比较友好。为了改善可扩展性，也有一部分系统（如 RocksDB）选择将内存层上的缓存迁移到 FIFO-like 算法上。这里比较经典的是 FIFO-Reinsertion，将访问过的对象重新插入缓存。这个算法和 CLOCK 时钟替换算法是同一个算法的两种不同的描述形式。近年来也提出了像 S3-FIFO 这样比较先进的 FIFO-like 算法，设计时应用了一些对工作负载和访问模式的关键洞察，取得了比较好的效果。

那么怎么区分 LRU-like 和 FIFO-like？

通常情况下我们认为 LRU-like 算法，会在缓存命中时候去执行一个解链操作。当命中率变得很高的时候，解链操作发生地越来越频繁，会对性能造成比较大的损害。从而呈现出一种反直觉的模式，即缓存命中率升高，但是系统性能反而下降了。像 LeCaR 是基于强化学习的算法，因为它使用 LRU 和 LFU 作为基本构建块，所以它会自然地被分类到 LRU-like 算法。FIFO-like 的算法在缓存命中时，不需要更新全局的数据结构。如果应用排队模型去看的话，增加命中率不会影响瓶颈设备上面的队列的长度，对性能释放友好。FIFO-like 算法可以归纳成下面两类：

第一种类型的算法使用 FIFO 作为基本构建块，例如 CLOCK 变体，S3-FIFO，QDLP 和 SIEVE。
第二种类型的算法没有全局数据结构，而是使用随机抽样来选择驱逐候选者。例如 LHD，LRB 和 Hyperbolic。因为这些算法不维护全局数据结构，所以它们永远不会受到缓存命中的限制，因此吞吐量总是随着命中率的增加而增加。

上面的图中总结了范式从 LRU-like 到 FIFO-like 迁移的原因，可以看作是对前面内容的一个简单总结。既然 FIFO-like 算法这么好，为什么过去在内存缓存中没有得到广泛应用？我们考察算法的时候，往往使用命中率作为关键指标。FIFO-like 在很多场景下表现不佳，但是近年来的一些对工作负载的大规模研究表明，像 FIFO-Reinsertion 这样采用 Lazy promotion 设计的 Weak LRU ，在整体上可能比 LRU 更具优势。像 Lazy promotion 和 Quick Demotion 这种缓存设计范式的引入，可以指导我们设计更加高效和高性能的 LRU-like 和 FIFO-like 算法。现代的 FIFO-like 算法的命中率在一些工作负载上，也能够达到最先进的水平。比如像 S3FIFO 在对象存储或者 CDN 之类的场景，SIEVE 在 Web 相关的缓存上。

那什么是 Lazy promotion 和 Quick Demotion？从上图可以比较清晰和直观地感受到几种不同范式的区别。 Lazy Promotion 是对象仅在驱逐时进行 Promotion。比较典型的技术就是重新插入：如果对象自上次插入缓存以来被请求过，那么在逐出时考虑将其重新插入缓存。具有懒惰促进的 FIFO 可以看作是 LRU 的近似。 Quick Demotion 考虑到等待新对象通过队列的机会成本可能很高，因此在插入后将大多数访问机会不大的对象快速移除会更为实际和有效。典型的 Quick Demotion 实现会在主体算法前添加一个小的 FIFO 队列，如果说在这个小队列中没有被访问过，就将该对象逐出。常用的准入算法也可以被视作是更激进的 Quick Demotion。但由于它们更激进，表现往往会显得更差一点。

这张图里是两个非常接近的算法，一个是 SIEVE，一个是 FIFO-Reinsertion。SIEVE 和 FIFO-Reinsertion 其实很类似，如果说它在这个期间内对象被访问过，那么我们就考虑将它保留在缓存中。二者的不同在于：
SIEVE 中的对象保留在原位置，指针不断前移处理较新的对象，幸存对象聚合。
FIFO-Reinsertion 对象重新插入队列头部，新老对象会混合在一起。这样一来，SIEVE 其实提供了类似 Quick Demotion 的机制，使它在寻找新的受欢迎对象和保留旧的受欢迎对象之间，取得一个比较好的平衡。通过对缓存算法的优化和范式迁移，现代数据处理系统能够更高效地应对动态工作负载，提升整体性能。

Part 3 缓存与机器学习

在过去的研究中，缓存系统与机器学习模型的结合已经得到了广泛讨论。比较典型的方式是使用监督学习，采用回归的方式来预测某个效用函数，将效用最小的对象逐出。基于机器学习的缓存系统面临两个主要挑战：

机器学习模型的开销：引入机器学习模型需要频繁训练和更新，以适应最近的访问模式。预测操作也可能带来显著的开销。
元数据管理的开销：无论是用于推测工作模式，还是选择最优策略，均需要维护大量元数据。

机器学习与缓存的结合主要有两种形式：

一种是使用机器学习来改进缓存算法的设计，即帮助选择缓存中需要保留或者逐出的对象。
一种是使用机器学习来选择更加适合当前工作负载的缓存算法。

例如，LRB（Learning-based Replacement）利用多个对象特征来预测对象的下一次访问时间，并逐出预测中预计请求时间最远的对象。引入更多特征（超过 40 个）可以提高预测的准确性，但也增加了内存和计算开销，限制了其在资源有限、需要高吞吐量环境中的应用。改善性能的简单方法包括攒批处理（batch processing），即将多个对象统一处理，但性能仍受机器学习干扰较大。使用提升树模型的方式本身计算开销就比较大，攒批后，每次训练和预测可能需要几毫秒甚至几十毫秒，因此在关键访问路径上进行预测并不现实。

策略选择上，使用多臂赌博机模型（Multi-Armed Bandit）的强化学习方法比较流行，如 LeCar 和 CACHEUS。这些方法的缺点包括：
适应性依赖：算法表现依赖于维护的简单方法对工作负载的适应情况。如果适应情况不佳，算法表现就会较差。LeCaR 只能覆盖两种组合（LRU 和 LFU），而 CACHEUS 通过设计新算法对抗扫描和循环工作负载，扩展了适应范围。
延迟奖励问题：使用强化学习时可能遇到延迟奖励问题，导致对工作负载的实时适应性差，从而降低命中率。基于监督学习的方法，如 FTRL 和提升树，在 CDN 缓存相关研究中被广泛应用。针对这个场景，性能不再是关键问题，因此更适合策略选择。但不管是哪种方式，都对元数据的采集和维护带来了一定的挑战。机器学习在缓存系统中的应用展示了其潜在的性能提升能力，但也面临显著的开销和管理挑战。通过优化特征选择、批处理和策略选择等方法，可以在一定程度上克服这些挑战。然而，机器学习模型的复杂性和资源需求仍然限制了其在某些环境中的应用。未来的研究需要继续探索如何在高效性和可扩展性之间取得平衡，以实现更优的缓存性能。

Part 4 学习型缓存：迈向轻量级和低开销

在现代高并发、高吞吐量的内存环境中，学习型缓存系统的研究正在向轻量级和低开销方向发展。为了适应实时工作负载的变化，我们需要减少元数据的维护量，并提升机器学习模型的效率。近年来，学习型缓存研究的重点从单纯追求命中率转向了吞吐量和扩展性。研究者们在特征维护上更加注重内存资源的高效使用，努力在轻量级和低开销的前提下实现学习型缓存。

首先比较值得学习的一个方式是 group level learning，之前在 Databend 公众号推送过关于 GL-Cache 的一篇解读。缓存系统可以按组积累学习信号，将学习和预测成本分摊到组内各个对象上。这种方法的优点是减少了计算和存储开销，但其实现非常复杂，且吞吐量受训练和预测频率的影响。论文中提到的实现方式是每天训练和预测一次，每次耗时几十毫秒。这种频率虽然避开了关键路径，但实时性较差，适用于相对稳定的缓存工作负载。尽管如此，该设计展示了 group level learning 在减少开销方面的潜力。在 GL-Cache 之后，可以看到很多相似的研究把 group level learning 的理念融合进去，做 block 级别的分组分帧的方式，然后应用到缓存系统中。

另一种有趣的方法是结合启发式算法来减少训练和预测的样本数。例如，MAT（Machine Learning At Tail）算法在启发式算法的尾部引入机器学习，将启发式算法作为过滤器。只有在最终逐出对象时才进行预测和决策，减少了模型的频繁调用。MAT 算法的一个特点是，当机器学习模块成为瓶颈时，可以仅使用启发式算法以保证系统整体性能。然而，由于 MAT 主要依赖 LRU 或 LRU-like 算法，其可扩展性受到一定限制。

利用 Sketch 进行特征管理是另一个有潜力的方向。Sketch 技术在缓存中并不罕见，如 Tiny LFU 和 Bloom 相关算法已经有所应用。在学习型缓存中，利用 Sketch 可以有效减少元数据的维护开销，提升系统效率。上图中的例子来自 ALPS ，它首先将访问流分割成帧，并使用 Sketch 作为先前识别到的启发式缓存模式的简明结构化表示（包括频率、最近性等），再应用机器学习来预测后续帧最适合的启发式缓存策略。在每个帧结束时，压缩和结构化信息被输入 ALPS 中，然后 ALPS 将预测的最优策略应用于下一个帧。ALPS 在理论上具有低计算开销和高吞吐量，但其实验是在高性能 DGX 服务器上进行的。现代学习型缓存系统正在向着轻量级和低开销方向发展，以适应高并发、高吞吐量的需求。通过引入 group level learning、结合启发式算法和利用 Sketch 管理特征，研究者们在减少计算和存储开销的同时，努力提升缓存系统的实时性和扩展性。这些创新方法展示了在复杂环境中，学习型缓存系统的广阔应用前景。

Part 5 遗珠之憾

在最后一个部分，我们将会尝试涵盖一些在前面的部分中没有得到讨论的一些内容。

缓存系统中，逐出算法往往被视为关键，但准入算法同样重要。准入算法决定哪些数据应该进入缓存，尤其在数据量达到一定规模时显得尤为重要。准入算法可以是主动式或被动式。在大型数据库系统中，主动式准入策略允许我们选择特定的表进行缓存，从而显著改善系统性能并减少写入磁盘的请求。准入算法通常可以被视作更加激进的 Quick Demotion 。启发式算法中有两个高效的准入算法：Tiny LFU 和基于窗口的 Tiny LFU，比如 Rust 实现的 Moka 和 Java 实现的 Caffeine 。这些算法在许多场景中被视为通用且优越的替换算法，展示了准入算法的潜力。然而，一直以来都比较缺乏明智的准入策略，现有的准入算法可能无法达到最佳未命中率。例如，在 LRU 前加一个 Bloom 过滤器可以在第一次请求时拒绝对象，直到第二次请求时才考虑将其准入缓存。这种方法对抵抗扫描------过滤仅访问一次的数据有较好的效果，但忽略了访问的局部性，即对象的下一次请求可能很快发生。因此，使用 Bloom 过滤器的 LRU 未命中率通常不如 LRU。

跨层缓存算法的设计是一个值得探讨的方向。FIFO-like 算法趋势可能导致同一种算法在内存和磁盘中同时使用，这简化了系统中缓存算法的维护。然而，不同介质之间的数据交互和特征差异需要进一步整合。例如，在三层缓存系统中（内存、磁盘等），我们需要一种方法同时管理热数据和温数据，使其更好地跨不同介质工作。目前，跨层数据交互的研究较少，但这是未来设计和实现缓存系统时必须考虑的方向。如何优化不同缓存层之间的数据交互，将是提升系统性能的重要途径。准入算法和跨层缓存算法是缓存系统中重要但常被忽视的部分。通过优化准入策略和设计高效的跨层缓存算法，可以显著提升系统性能和资源利用率。未来的研究应继续关注这些方向，以实现更智能、更高效的缓存系统。