如何将索引大小减少99.5%？解读流式存储Pravega的段属性

1 背景与简介

能够将事件（Event）按流水线的方式注入段存储（Segment Store）是Pravega客户端实现高吞吐量的关键技术之一，即便是处理小尺寸的写操作也是如此。Writer在接收到事之后立即将其追加到相应的段（Segment）中，并不会等待之前的写操作得到确认。 为保证顺序和仅一次（Exactly-Once）语义，段存储要求所有这些追加操作都有条件地基于某个已知状态，而该状态对于每一个Writer都是唯一的。这一状态存储在每个段的段属性（Segment Attribute）中 ，并且在每个段操作中可以被原子性地查询或者更新。

随着时间的推移，段属性已经逐渐演化并支持一系列不同的用例，从记录某个段（开启Auto-Scaling特性）内的事件数量到存储哈希表的索引。表段（Table Segment，一种用于保存Pravega所有流、事务和段的元信息的键值存储）的引入则要求每个段具有无缝管理成千上万条属性的能力。

这篇文章将解释段属性的运作机制以及它是如何提供一个高效的键值存储，成为其它上层高级特性的基石之一的。我们先从一个概览开始，看看Pravega Writer是如何使用段属性来避免数据重复和丢失的。接着，我们会详细描述段属性是如何在二级存储上被组织成B+树，并使用一种创新的压缩方法来减少写放大效应的。

2 利用段属性来避免数据重复或丢失

EventStreamWriter在写入更多数据之前，必须首先知道它在服务器端已经写入数据的状态，即便是在某些常见的失败场景下也是如此。它需要提供某些数值，而服务器端每次在尝试进行修改操作时都可以原子性地检查和更新这些数值。

在与服务器交互的过程中，大多数故障表现出来的形式都是事件没有得到确认回复，而在这种情况下，相关的EventStreamWriter会使用与之前相同的条件重试写操作。

如果在之前的尝试中事件已经被持久化了，那么段存储会使用ConditionalAppendFailedException异常拒绝本次重试，而EventStreamWriter则向调用者确认本次事件并继续处理下一批事件。相反，如果事件还没有被持久化，则段存储会立刻进行持久化并向Writer发送确认。这种错误重试和有条件失败的组合有助于避免数据丢失（事件未被持久化）和重复（事件被持久化了，但却没有被确认）。

每个EventStreamWriter都有一个唯一的标识符，Writer ID，并且依据当前正在处理的事件的路由键（Routing Key），可以同时写入多个段存储。它的内部状态由一个字典结构组成，对每个交互的段记录一个事件编号（Event Number）。每次处理一个新事件时，该内部状态都会发生改变。每一个事件都被作为一个条件追加（Conditional Append，以当前的事件编号和Writer ID为条件，期望在对应的段上得到匹配）操作发往段存储。段存储上的注入流水线按追加操作的接收顺序依次处理所有的追加，并且每一个条件追加操作都会被原子性地检查，提交和更新，因此保证了数据存储的一致性。

段存储以段属性的形式维护这一状态。图 1用一个示例展示了这一运作机制。

图 1 Writer W1和W2向段A和段B追加事件。每个Writer对每一个写入的段都有一张映射表，如下：{段，最后发送的事件编号，最后确认的事件编号}。段存储对每一个它管理的段都有一个从Writer ID到事件编号的映射，该映射在每次追加操作中都会被原子性地检查并更新。Writer每次向段存储发送事件时更新相应的最后发送事件的编号，并在每次收到确认回复时更新相应的最后确认事件的编号。

3 段属性

每个段都有一组属性集合，可以被独立使用或者与不同的段操作组合使用。例如，我们可以选择仅更新某些段属性，也可以选择原子性地向某个段追加并更新一些属性。Writer ID是一个128位的UUID，而事件编号是一个64位的长整型数值，因此我们将段属性设计为支持16字节键，8字节值的键值对。

目前有两种类型的属性：核心属性（Core Attribute），它的ID是硬编码的，用于保存段的内部状态（例如事件总数，扩展策略等）；扩展属性（Extended Attribute），它是从外部指定的，并无任何内部含义。两种类型的段属性具有相同的语义，唯一的区别是核心属性是永久内存绑定的，而扩展属性可以被换出。Writer ID就是使用段属性映射到事件编号的。

段属性可以使用如下动词原语进行更新：

1. 替换：某个属性值被设置为或更新为一个新值。
2. 如果大于则替换（Replace-If-Greater）：某个属性值被更新为一个新值v，仅当存在一个当前值v’并且v>v’。
3. 如果等于则替换（Replace-If-Equal）：某个属性值被更新为一个新值v，仅当当前值与v’（由调用者提供）匹配。这是经典的CAS（Compare-And-Set）操作，可以用来保证属性值在本次更新之前未被并发设置。
4. 累加：某个属性值被更新为当前值加上一个调用者提供的值。

以下是一个从Pravega的段存储源码中截取的示例，展示了如何使用段属性：

private CompletableFuture<Void> storeAppend(Append append) {
    ArrayList<AttributeUpdate> attributes = new ArrayList<>();
    // Atomically check-and-update the Writer Position while
    // performing this append.

    attributes.add(new AttributeUpdate(
        append.getWriterId(),                // Attribute Key.
        AttributeUpdateType.ReplaceIfEquals, // Compare-and-set.
        append.getEventNumber(),             // Value to set.
        append.getLastEventNumber()));       // Value to compare.
 
    // Atomically increase the number of events stored with this append.
    attributes.add(new AttributeUpdate(
        Attributes.EVENT_COUNT,              // Core Attribute.
        AttributeUpdateType.Accumulate,      // Add to existing value.
        append.getEventCount()));            // Value to add.
 
    // Perform the append. Pass the append payload and the attributes,
    // which tells the Segment Store to apply them atomically.
    return store.append(append.getSegment(), append.getData(), attributes);
}

在这段源码中，每次追加操作涉及到两个段属性：将Writer的事件编号条件更新至一个新值，并且更新段中所存储的事件总数。段存储的注入流水线自动在本次追加操作涉及的段（append.getSegment()）上进行如下操作：

1. 验证事件编号属性值值与append.getLastEventNumber()匹配。
2. 更新事件编号属性值至append.getEventNumber()。
3. 更新Attributes.EVENT_COUNT至先前值加上append.getEventCount()。
4. 将append.getData()作为一段连续字节序列追加到段尾端。

4 存储段属性

段属性是每个段上的额外元信息，它可以被客户端自由地设置或读取。然而，段属性没有被任何API对外暴露。如果这是段属性的唯一用途，那么只要把它们存储在一个与主段相关联的一个独立的内部段上就足够了。

但是，正如上文提到的，段属性同时也在注入流水线的内部计算中被大量使用，如果在每次需要的时候都暂时挂起流水线并从存储中加载属性值，必然会造成相当大的性能损失。我们需要一种方法缓存全部或者部分属性在某种内存数据结构中，使其可以很容易地被流水线访问和更新，但同时必须用一种高效的方式最终将这些更新持久化到二级存储中去。

为解决这一难题，我们设计 了一种两层缓存方案，最终将属性值保存到二级存储的属性段（Attribute Segment）上。第一层缓存是一个直接的Java哈希表（HashMap接口），用于保存最近使用的属性。这层缓存直接进行键值映射，使得查找和更新操作非常高效。下层缓存以原始格式将二级存储上的属性段部分保存在内存中，尽管这要求反序列化以便抽取信息，但对该层缓存的访问依然显著快于直接从二级存储加载。

下层缓存和二级存储上的属性段一同构成了所谓的属性索引（Attribute Index），它将段属性组织成一种适合只追加（Append-Only）存储介质的数据结构。

图 2 属性流水线。属性被保存在二级存储上；通过属性索引访问这些属性，属性索引在内存中缓存了部分二级存储的数据，并通过段容器（Segment Container）的注入流水线进行更新。

我们做出的关键决策之一便是尽量避免在注入流水线内直接从二级存储加载属性值，而是尽可能在处理操作之前就进行预取。图 2中的步骤1.1到步骤1.3展示了这一工作流程。

我们对那些已经在内存中的属性进行元数据查询（步骤1.1），并从属性索引拉取其余的属性（步骤1.2）。为了在那些针对相同数据的并发请求间保证一致性，我们使用条件属性更新（Conditional Attribute Update），通过注入流水线在段的元数据中加载属性：如果某些属性已经被加载了，则我们不希望它们的值被某些脏状态覆盖。

为了将属性值持久化到二级存储上去，我们使用现有的基础设施。Storage Writer将较小的段追加操作聚合成为较大的缓冲区一次性写入二级存储，同时它也能够将多个属性更新组合成较大的批操作，通过属性索引持久化到二级存储。这带来了一些额外的好处，那些频繁更新的属性（例如事件数）不必每次更改后都持久化到二级存储：我们可以将多个更新聚合起来（仅保留最新的值），如此避免了一些非必要的，昂贵的二级存储写操作。

5 段属性索引

我们面临的最大挑战或许就是该如何将大量属性保存到Pravega的二级存储上。首先明确一点，我们所说的大量究竟是多大？现实一点说，通常一个段大约会有上万个Writer，我们需要考虑比这更大的数据量吗？

我们最初采用的方案对每个段小于10万条属性的场景进行了优化，方法很简单：我们将每一个更新（24字节）追加到属性段，在持续写入了大约几兆字节的数据后，再将所有数据压缩成一个有序数组并同样进行追加。同时维护了一个指向最后一次压缩首部的指针，每次需要读取时，就从该首部一直读取到段的尾端。这个方法很简单，没有什么复杂的部分，也能很好地处理我们的用例（10万条属性意味着二级存储上的大约2.5MB到5MB数据，完全可以一次性读取并缓存）。

图 3 最初的方案。所有的属性更新都被追加到属性段。我们会进行一些周期性的压缩操作，仅保留最新的属性值。属性段同时也被从头部截断，丢弃过期数据。

从长远上看，我们还发现了有关属性的另外一些重要用途。表段，在Pravega的0.5版本中被引入，用于保存Pravega所有的元数据，并开放一个基于普通段的键值API。作为一个哈希表，它将整个索引都存储在段的属性中，因此它比EventStreamWriters需要更多的段属性支持。我们意识到我们需要支持每段千万级别的属性，这需要一种完全不同的方法将其保存到二级存储上。我们的解决方案就是B+树，然而，我们所选择的实现与大多数典型的数据库系统稍有不同。

6 只追加存储上的B+树

当修改操作只允许被追加到文件的尾端时，B+树通常不会是索引结构的首选。只追加的B+树变体已经有现有的实现，但它们都有一个显著的缺点：写放大（Write Amplification）。所有对该结构的修改都需要将从根节点到被更新数据节点路径上的所有节点重新追加到文件上。

随着时间的推移，这导致了超大的文件尺寸，其中包含了大量过期数据。周期性的全索引压缩似乎可以解决这个问题，但这一方法对Pravega并不适用。由于我们的系统本质上是一个分布式系统，节点失效时不可避免的，诸如压缩操作这类的非原子性操作很难在不影响段存储性能的前提下正确实现。

另一种方法就是使用LSM树（Log-Structured Merge Tree），但这种数据结构也大量使用了压缩操作。因此，我们使用了一些新技术和优化方法，让我们可以高效地将段属性保存到二级存储上的B+树上。

我们的键值永远是固定长度（分别为16字节和8字节），这让我们得以简化B+树的节点结构，并允许使用较大的分叉因子（Branching Factor）。设定最大节点大小为32KB并限制每条记录32字节，使得我们的分叉因子可以超过1000。对于一个存储超过10亿条记录的索引结构，我们最多只需要3到4次二级存储上的读操作就可以完成某个键的查询。

尽管我们所要查询的键的深度可能有数层，但任何B+树的操作都需要查询根节点，并且每一个二层节点都有大约千分之一的概率被查询。将节点进行缓存可以极大减少对二级存储的随机读取，尤其是对于深度较大的节点。对于最大节点大小32KB这样的设置，整个二层节点只占用大约32MB的缓存空间，我们完全可以把它们全部加载到内存中。由于访问模式的不同，缓存命中率也会相应有很大变化，但我们的测试显示，对于一个已经预热的索引，当使用缓存时，定位一个键仅需要不超过一次的二级存储读操作。

较大的分叉因子也能缓解写放大问题，但不能完全消除它。然而，一个很关键的事实是，尽管属性段可能会无限增长，但活动数据（最新版本的数据）总是集中在段的尾端，而段的首部倾向于包含大部分的过期数据。通过使用与Retention相同的方法，我们可以对段进行头部截断，删除那些已经被截断的数据块（Chunk）。段上的数据块是一组连续的字节序列，每一个数据块都对应二级存储上的一个文件或者对象。因此，通过对属性段使用现有的滚动存储（Rolling Storage）适配器，我们已经非常接近我们的期望目标了。

然而，我们只有在确认被丢弃的数据中不再包含任何仍在使用的B+树节点（那些在更新操作后已被重新追加的节点）后，才能进行头部截断。段的首部有很大概率包含过期数据，但偶尔也会包含一些仍在使用的B+树节点。经典的压缩操作已经考虑到这种情况了：扫描索引文件，找到最早的被过期数据包围的节点，通过追加的方式将它们移动到文件的尾端。虽然这并不会阻塞截断，但它还是需要同时对大量段维护一段较长的非原子性的压缩过程。

我们采用了另一种被称为渐进式压缩（Progressive Compaction）的方法。每次修改B+树，我们都会定位属性段上偏移最小的相关节点，通过追加的方式将其移动到段尾端（同时可能还会移动它的祖先节点）。尽管这看起来有点像我们把写放大问题变得更糟糕了，但这确实是一个让属性段文件尺寸变小的折衷方案。二级存储的写操作通常被认为是高吞吐量的，所以每次多写32KB到100KB的数据不会有多少差别。而我们所得到的回报就是，我们从一开始就可以对大数据块进行截断，因此能够让属性段的大小始终保持在合理范围内。

为了定位具有最小偏移的结点，每个B+树节点保存了以它为根的子树中所有节点偏移的最小值。知道了这个值，我们就可以沿着根节点的路径，定位到具有最小偏移的那个节点。

维护这个值也非常简单：因为每次更新都需要修改从叶节点到根节点间的所有节点，我们所要做的就是利用现有节点内编码的信息重新为每个节点计算该值。我们不需要额外的IO操作，因此也不会对性能造成影响。

图 4 三层B+树以及属性段的布局（有渐进式压缩和无渐进式压缩）。索引图例：键前缀标注在顶部；底部是子页偏移:最小页偏移。该树处于最终状态。

我们看一下在图 4中，随着B+树的创建，文件布局是如何变化的。

1. 起始，我们只有一棵单节点的树，仅包含节点6。
   • 无论有无渐进式压缩，我们都对节点6进行追加。
2. 节点6分裂为6和7，节点3作为根节点，而节点6和7为子节点。
   • 无论有无渐进式压缩，我们都追加节点6，7和3。文件布局为：6，6，7，3。
   • 对于渐进式压缩，我们跳过重新追加节点6，因为它已经包含在更新中了。
3. 节点6分裂为5和6。节点3的子节点为节点5，6和7。
   • 无论有无渐进式压缩，我们都追加节点5，6和3。文件布局为：6，6，7，3，5，6，3。
   • 对于渐进式压缩，我们跳过重新追加节点6，因为它已经包含在更新中了。
4. 节点5分裂为4和5；节点3分裂为2和3；节点1创建为根。节点1的子节点为2和3，节点2的子节点为4和5，节点3的子节点为6和7。
   • 无渐进式压缩：我们追加节点5，4，3，2和1。文件布局为：6，6，7，3，5，6，3，5，4，3，2，1。
   • 有渐进式压缩：我们追加节点7，然后是节点5，4，3，2和1。文件布局是：6，6，7，3，5，6，3，7，5，4，3，2，1。
5. 节点6被更新。B+树没有结构性变化。
   • 无论有无渐进式压缩，我们都需要追加6，3和1。
   • 对于渐进式压缩，我们跳过重新追加节点6，因为它已经包含在更新中。
   • 无渐进式压缩的布局：6，6，7，3，5，6，3，5，4，3，2，1，6，3，1。
   • 有渐进式压缩的布局：6，6，7，3，5，6，3，7，5，4，3，2，1，6，3，1。

在这个例子中，渐进式压缩允许我们在位置7（在无压缩的例子中为位置2）进行属性段的截断，因此帮助我们释了放不再需要的磁盘空间。

7 实际应用中的渐进式压缩

为了验证渐进式压缩在现实场景中的运作情况，我们设计并运行了一系列测试。通过将多个更新操作组合成一个大的批操作，我们可以减少写放大，因为批操作越大，B+树就越少需要重写它的上层节点。我们使用不同的插入/更新批操作大小，并对比有压缩和无压缩情况下的索引（在二级存储上）大小。在这些测试中使用的批操作尺寸反映了Storage Writer如何聚合更新操作：较小的批尺寸适用于那些具有较少并发Writer的段，而较大的批尺寸通常被用于表段。

表 1 顺序插入1,000.000条段属性。对较小的批尺寸，渐进式压缩的效果最显著（大小减少了97%），而较大的批尺寸则效果并不明显（由于较小的写放大）。

表 2 批量加载1,000,000条段属性，并按随机顺序更新。无论批尺寸如何，写放大问题都十分严重，渐进式压缩也因此取得了显著效果：索引大小被减少了至少99.5%。

8 总结

属性在段的整个生命周期中扮演着核心角色。除了存储段本身的元信息外，它们还大量参与到段的修改操作中去。它们被用于保存段内的统计数据（例如事件总数），允许EventStreamWriters实现仅一次语义。在传统数据结构上使用创新的方法使得段存储可以为每个段有效管理10亿数量级的段属性。渐进式压缩在不使用后台任务和不影响性能的情况下减小了写放大效应，为只追加B+树减小了99.5%的尺寸。

在下一篇文章中，我们会讨论如何使用段属性来实现一个完全基于段的可持久化哈希表：这是创建基于Pravega的大规模分布式元数据存储的第一步。

致谢：感谢Srikanth Satya和Flavio Junqueira为本文提出宝贵建议。