一、背景

贝格迈思自主研发的分布式AiSQL智能数据库，基于LSM-Tree的键值存储引擎在部署上具有高灵活性和在性能上的横向可扩展性，应用为AiSQL中BrightDB的存储底座。

数据读写性能直接与存储引擎相关，AiSQL智能数据库在优化存储引擎方面花了大量的功夫，本文将介绍AiSQL智能数据库中BrightDB在缓存优化的设计。

二、LSM-Tree读写流程

为了利于读者理解本文讨论的问题，我们先简单回顾一下LSM-Tree读写流程。

一条数据在LSM-Tree中的生命旅途，首先为了保证Ta在出生时不会意外流产，Ta先会被临时写入预写日志中，然后会被转移到内存表中，这是Ta整个生命周期的第一处落脚点。随后，flush操作将Ta刻在持久化介质上，compaction操作将Ta带往更深远的去处，或是在途中丢弃，取决于Ta的继任者何时到来。
 LSM的本质是，所有写入操作并不做原地更新，而是以追加的方式写入内存。每次写到一定程度，即冻结为一层(Level)，写入持久化存储。所有写入的行，都以主键(Key)排序好后存放，无论是在内存中，还是持久化存储中。在内存中即为一个排序的内存数据结构(通常为跳表)，在持久化存储也作为一个只读的全排序持久化存储结构，即SST（Sorted String Table）文件。

由此可见，LSM-Tree是一种十分利于写入的数据结构，可以提升数据库的插入和更新操作的性能。但是，读取操作就会变得十分的曲折，因LSM-Tree多层的存储结构，查找一条数据可能需要逐层遍历SST文件，即使有布隆过滤器（Bloom Filter）和栅栏指针（Fence Pointer）可以节省IO次数，读取的开销依然很大。

三、缓存

目前，最为主流的读取性能优化方法就是缓存，数据库的读取请求存在较高的访问局部性，少部分的热点数据回答了大量的查询请求，因此将这些热点数据缓存在内存中可以显著地提升数据库的查询性能。针对键值存储引擎的查询分为点查询和范围查询。

针对键值存储系统共存在三种缓存模式，分别为KV（键值缓存）、KP（键值指针缓存）和Block（块缓存）。

KV：是指将完整的键和值缓存；

KP：是指缓存完整的键以及其指对应的指针（在整个键值空间中存储的位置以及大小），在该模式下命中缓存，只需要一次I/O即可完成查询；

Block：单元为SST文件中的一个Block，即一个连续的键值列表，显然该缓存模式消耗的内存空间最多。

需要特别关注的是范围查询，几乎80%以上的查询延迟都来源于它，而这三种缓存模式中，只有块缓存能够服务范围查询。目前RocksDB和LevelDB都只支持块缓存，这种设计对于数据库这种数据查询负载多变的应用中显然是不合理的。因此BrightDB设计了一种全新的数据缓存结构，综合利用了三种缓存模式的优点，最大化的提高内存空间的利用率，提出了一种新的视角来评价缓存策略，即每GB空间能回答的平均查询数目QPG（Query Per GB) 。

首先我们发现三种缓存模式的空间利用率和对不同的查询负载的加速效果是不同的。

对于空间利用率来说KP、KV、Block三种缓存模式依次递减。

对于查询加速效果来说：

KP适用于访问局部性不强的温数据，因为有很多数据用户可能只会访问一遍，缓存完整的键值对并没有太大的意义，比如说是单次的一个大范围的查询，将整个范围内的键值对都缓存起来，会将原真正的热点数据替换出去；

KV适用于局部性较强的热数据，工作负载如果存在热点数据那么此时大部分的查询都由它们来回答，将这些热数据缓存起来收益非常高；

Block则是在拥有较多的范围查询的工作负载中比较适用，但是需要时刻注意内存空间的利用效率，大粒度的缓存也比较有可能出现系统抖动现象（缓存被频繁地来回的换入换出）。

四、BrightDB中的动态缓存

目前在工业界主流的实现中，并没有将以上三种混合的缓存设计方案，取其所长，以适应数据库动态变化的工作负载。

基于以上发现，我们在BrightDB中实现了一种动态缓存模型，将三种缓存模式进行融合，并且使用一种巧妙的设计（影子缓存）来动态调整整体缓存内存空间的分配。

模型的结构如下图所示，首先将整个缓存空间分成三个区域，KV缓存区、KP缓存区和Block缓存区，存在两条边界，控制着三个缓存区域的大小。不同缓存区域的大小分别适用于不同的数据负载，比如KV缓存区域较多时，缓存系统能够保存大量的热点键值数据，适用于有大量点查且数据倾斜的数据负载；当Block缓存区域较多时，适用于范围查询较多的数据负载。

所谓动态缓存模型，就是我们可以根据数据负载来动态调整两条边界来控制各个缓存区的大小，以适应不同的数据负载，在稳定的业务负载中三者空间大小存在一个“Sweet-Point”能够最大化的提高系统吞吐量。那么我们如何感知我们线上业务负载的变化，让缓存系统自适应的找到“Sweet-Point”呢？

首先是缓存内存空间的分配，从上层角度看分为单点缓存和块缓存，这两个区域大小设置一个边界控制，块缓存缓存的基本单元则是SST文件的Block块，包括数据块、元数据块和布隆过滤器块；从下层角度看，单点缓存又被细分成KV和KP缓存。我们将缓存在KP上的数据定义为温数据，在LSM-Tree中KP缓存的条目一般为<Key ：<SstID|BlockOffset>>，值的大小只有16B，我们可以在内存中缓存大量的条目，每次命中只需要一次I/O就可以读到包含该键值对的数据块。在KV上的数据定义为热数据，同样设置一个边界控制这两块缓存空间的大小。

为了追踪数据负载的变化，实时调整缓存区域，BrightDB引入了一个新的数据结构，称之为影子缓存。顾名思义，当一条数据从各个区域被淘汰时，它存在过的痕迹保存在影子缓存中，比如KV缓存的影子缓存区保存了被淘汰出的键的哈希值。

动态调整的规则如下：

（1）针对单点缓存，当一个查询从SST文件中第一次读到结果时，我们首先将其视为温数据并缓存在KP中，因为该数据可能不会再访问。而当它在KP缓存中第二次被命中时，我们就需要将他提升为热数据放到KV中，因为它在短时间内（没有被淘汰出去就可以认为两次访问间隔时间不长）被命中两次，则可以合理的判断它极大可能会变成热点数据。当升级后需要将其在KP缓存中删除，避免重复数据。因此所有的数据并不会直接插入到KV缓存中，唯一的路径就是在KP缓存中第二次被命中。这样就保证了缓存不会被大范围的扫描污染。

（2）针对Block缓存，每次查询到的SST文件的数据块后，都会被缓存在该区域中。Block缓存主要就是为了加速范围查询的，因此其大小的设置需要根据负载来调整。此外，一些元数据可以在Block常驻，比如LSM-Tree上层的布隆过滤器，因为其对查询的加速效果最大。

（3）影子缓存可以帮助我们追踪数据负载的变化，实时调整缓存区域的大小。当缓存条目被淘汰时，我们将被淘汰的键保留在影子缓存中。为了节省空间我们只保存键的哈希值，相对于存储完整的键来说，哈希值只有4-8B，因此可以缓存大量的条目。当查询请求没有在缓存区域命中时，会查看是否在对应的影子缓存中是否命中。当某一块缓存区域的影子缓存的命中率θ提高时，说明该缓存区域大小的设置不合理，就需要给他进行扩容。用户可以自定义各个缓存区域θ的调整阈值，比如说在热点查询中优先保障KV缓存的扩容。当然，影子缓存也需要采用简单FIFO的淘汰策略来保证不会占用过多的内存空间。

我们在BrightDB中实施该缓存策略时，BrightDB中采用了高性能的存储介质（Optane DC SSD)做冷热分层存储的架构，动态缓存中的KP缓存区域给系统性能带来了巨大的提升，因为在高性能存储介质中的直接读取Block的延迟可以达到<10us的级别，IOPS也高达数百万。在BrightDB中实现了精准的冷热分离算法，可以将热数据保留在高性能存储介质中。因此在实际工作负载中，KP与KV的配合使用，让BrightDB点查性能接近了In-Memory的程度，范围查找的性能也得到了巨大的提升。我们后续会分享BrightDB的分层存储架构以及数据冷热分离策略。

五、性能评估

性能评估我们将只有Block Cache的BrightDB作为基线版本，分别与BrightDB-with Block&KV Cache和BrightDB-with Block&KV&KP Cache两个版本对比。

（1）在不同的数据倾斜率中

从测试结果来看，在倾斜率99.9%的场景中（通常业务也是这种特征数据负载），动态缓存模型可以提升约223%的性能。

（2）在不同的范围查询比例中

范围查询是查询延迟的主要来源，且在数据库中该查询十分常见。可以看到范围查询在动态缓存模型中可以优化性能达到100%以上。

六、总结

贝格迈思自主研发的分布式AiSQL智能数据库中BrightDB设计的动态缓存模型综合利用了不同的缓存模式的优势，并以极低的代价监控实施数据负载的变化，实时的调整缓存空间的分配，最大化的利用内存空间。

通过测试，我们发现这种策略极大地提升了查询性能，考虑到真实线上数据负载情况多变，我们相信动态缓存模型的自适应适配策略可以进一步带来性能收益。此外，BrightDB利用了高性能存储硬件做数据冷热分离存储，使用动态缓存模型后，BrightDB在查询性能上获得了额外的性能提升，充分发挥了高性能存储硬件的能力。

贝格迈思将持续关注存储介质和工业负载特征的演进，把握技术发展脉搏，满足用户对数据存储和管理不断变化的需求。不断进行技术创新和产品升级，为用户提供更加高效、安全、可靠的数据库产品和服务。

参考文献：

1．Jaeheon Jeong and Michel Dubois. Cost-sensitive cache replacement algorithms. In The Ninth International Symposium on High-Performance Computer Architecture, 2003. HPCA-9 2003. Proceedings., pages 327–337. IEEE, 2003.

2．Ziqi Fan, David HC Du, and Doug Voigt. H-arc: A nonvolatile memory based cache policy for solid state drives. In 2014 30th Symposium on Mass Storage Systems and Technologies (MSST), pages 1–11. IEEE, 2014.

3．Zhichao Cao, Siying Dong, Sagar Vemuri, and David HC Du. Characterizing, modeling, and benchmarking rocksdb key-value workloads at facebook. In 18th USENIX Conference on File and Storage Technologies (FAST 20), pages 209–223, 2020.