Two is Better Than One
原文链接:https://www.cidrdb.org/cidr2023/papers/p57-zhou.pdf

Content

• Intro
• 现有技术中的Cache策略
• 2-Tree 总体架构
• 数据迁移原则
• 实现思路
• 总结

头图来源:雨の日-暮雨-#pixiv

Intro

该篇论文的提出有以下背景：
现实世界中的数据总是高度倾斜的。所谓倾斜意思就是数据中的一个子集（通常是整体数据量的一小部分）比其余部分具有更高的访问频率。通常热门的数据可能分散地分布在整个数据空间的任何区域，而不是仅聚集在几个子范围中。同时数据集的体积、内容等会随着时间发生变化。
以传统的索引结构B+树为例，在读取索引数据时会将辅存中一部分索引块读入内存然后再根据索引块读取辅存中其他索引块，如此往复直到定位到目标数据。然而这样通常会存在一个问题，那就是读取进内存中的索引块中，热数据可能仅仅占其中很小的一部分，这意味着读进内存的数据有很大一部分大概率不会被访问，这造成了大量的空间浪费以及性能损失。
在这样的背景下，作者提出了一种2-Tree架构，采用了两颗树形数据结构分别存储冷热数据，其中热门索引记录位于一棵树中（为方便表达，以下称为热树），冷门记录位于另一棵树中（方便表达称为冷树）。热门树块经常被访问并且可能保留在主内存中，同时当热数据边冷时，就将该数据迁移至冷树中，冷数据边热时就会迁移到热树中，数据就这样在冷热树中来回迁移。作者还为2-Tree规定了迁移协议以精确检测并维护热点数据。
除了能够提升内存利用率外，冷热树还对其底层存储做了优化：热树由于常常会被访问，因此常保留于内存中，因此热树是针对主存进行的优化；冷树存储于辅存中，因此针对辅存进行优化。
作者同时将2-tree结构推广到了N-tree结构来适应具有多种存储级别或设备的系统（这里可能指的是类似于LSM-tree的多层结构？），作者将N-tree与LSM-tree做类比，N-tree在读取时将向上移动数据，如此做可以提高读取密集型工作负载下的内存利用率。

现有技术中的Cache策略

LSM-tree

传统LSM-tree为了提升读取性能，会将近期读取的SSTable的block缓存进内存（参考Leveldb中的BlockCache）,高频更新的数据常常会因compaction操作被推至LSM-tree的高层，并且较为集中。然而某些数据常常仅被用于读取而不是更新，这些数据常常分散在LSM-tree中的各层，因此BlockCache往往仅缓存了少部分甚至未命中热点数据。

Record Caching

与BlockCache以块为缓存单位不同，RecordCache是以record（也许是一批数据）为单位缓存，该缓存策略确保了缓存在内存中的数据大部分是热点数据。但该缓存策略仅适用于read-only的查询，如果修改操作涉及缓存数据，则需要设计一种恢复机制使得在缓存中的更新能同步应用于该缓存所对应在辅存中的数据。
此外，RecordCache更适用于加速点查询，当面对范围查询时，其性能并不如BlockCache

Anti-Caching

该策略是H-Store团队为全内存数据库所设计，其思想就是将主要数据存储在内存中，而将冷数据驱逐到辅存，同时内存保留了每个被驱逐数据的元数据，并将所有的辅助索引都驻留于内存。此外，由于Anti-Caching中被驱逐的数据在辅存中的存储是无序的，因此其并不能很有效地处理范围扫描。

Siberia

Siberia与2-Tree有些相似，采用基于内存优化的数据结构索引存储热数据，并采用辅存存储冷数据。但是有和2-Tree有两个主要区别：1. Siberia在读取过程中不会将数据从冷存储迁移到热存储。这对于只读的工作负载来说并不能达到性能最大化。2. Siberia对热数据的判断是基于离线分析访问日志来实现的，相比之下2-Tree的轻量级在线识别热数据用了更少的计算资源，同时能更及时地适应工作负载的变化。

2-Tree 总体架构

2-tree的架构如下图所示：

• (a) 可当做是2-Tree版本的Anti-Caching，热树完全地存储于内存中，以record为粒度建立索引，冷树存储于辅存并通过图中的small buffer pool对冷树的数据进行交互。冷热数据的迁移也以record为单位。
• (b) 冷热树均采用B+树结构存储，两树共享一个buffer pool。
• (c) 为LSM-Tree采用迁移策略。注意到高层级的数据块通常更经常被访问（这里想是因为高层级的数据块通过compaction数据更为集中）。

数据迁移原则

Downward Migration

上图为2-tree record的格式，第一位为引用位（为1表示该记录正在使用，为0表示该记录未被引用）。当需要将数据驱逐至冷树时，将通过clock handle循环扫描每个record（clock handle可以看做扫描的游标），clock handle将收集经过的记录中ref位为0的记录，当收集数量达到阈值时扫描停止，同时将收集的记录驱逐至冷树。

Probabilistically Deferred Upward Migration

作者采用一种基于抽样的方法，对访问过的数据进行采样并将其向上移动（可以看做向热区移动）。这里定义抽样率为D(0<D≤1)。对于正在变热的数据其访问频率会增加，因此这些数据出现在样本集中的概率更大。作者提供了一种可调节的抗抖动方法，并且让CPU和内存的开销最小。
较大的抽样率可以快速预热缓存，但是缓存抗抖动能力将减小（理解为抽样率大将意味着一次性换入大量的缓存，这样在缓存数量有限的情况下将造成大量的缓存换出）；相反小的抽样率将会牺牲缓存预热速率换取更高的抗抖动能力。因此需要调整抽样率D以权衡系统的抗抖动能力和缓存预热速率。

Inclusive versus Exclusive Migration Policy

在迁移记录时，另一个重要的决定是系统中要保留多少份记录。作者给出了两种策略：独占策略（exclusive policy）和包容性策略（inclusive policy）。

• 在独占策略中，系统只在顶部树或底部树中保留一份记录。当从底部树向上迁移数据时，记录将从底部树中擦除。
• 在包容性策略中，当记录被复制到顶部树时，它仍然保留在底部树中。包容性策略避免了在迁移过程中修改底部树，这对于IO绑定的工作负载是有益的。然而，包容性策略会导致整体树大小增加。

实现思路

UpLSM-tree

作者保留了传统的LSM树的向下迁移（compaction），并同时应用了2-Tree向上迁移的思想。具体来说，当点读操作在块缓存中发生未命中时，则考虑将记录向上迁移到最高级别（C0，位于内存），这是考虑到I/O可能发生在较低层，较高层的数据量通常很小，并且很大概率被块缓存缓存。注意这里的高层、低层其实和Leveldb中的高层低层相反（Leveldb中高层的数据量大，低层数据量小，compaction将SSTable从低层推至高层）。

总结

总的来说作者提出了一种新颖的索引结构来解决现实中数据集普遍存在的数据倾斜问题，这种结构采用了轻量级的通用迁移协议，能在各种工作负载中动态地对数据进行冷热切换。同时在作者给出的benchmark中，通过将2-Tree思想应用于B+树和LSM-tree使得它们在高度倾斜的工作负载下内存利用率分别提高15倍和20倍。同时，在内存使用率相同的情况下，与传统的B+树和LSM-tree相比，在Zipfian倾斜的IO限制工作负载下，吞吐量最高提高了1.7倍。作者在论文的最后也给出了未来的一些研究方向，例如目前2-Tree是单线程，或许未来可以加上并发（这需要对2-Tree设计一套并发控制策略）、将2-Tree应用于Non-tree-based结构（如哈希表等）、将2-Tree应用于云数据库等等。
此外，对于抽样率D取值的选择，作者也做了一些保留（或许未来也可以加入AI技术训练出一个模型以针对不同工作负载选择最优的抽样率？）
还有就是，热缓存似乎不是read-only，那么在高并发的场景下该如何去保障缓存的一致性、如何解决并发安全问题，以及这些问题会带来怎样的性能影响。