etcd在大规模数据场景中的性能优化

作者：陈星宇，阿里云软件工程师

摘要

etcd是一个开源分布式kv存储系统，最近被CNCF列为孵化项目。etcd在许多分布式系统中得到了广泛的应用。例如，Kubernetes使用etcd作为分类账，在集群中存储各种元信息。本文首先介绍优化的背景。然后介绍etcd内部存储的工作机制和具体的优化实现。最后给出了评估结果。

背景

由于阿里巴巴庞大的Kubernetes集群规模，对etcd的容量要求非常高，超出了支持的极限。因此，我们实现了一个基于etcd代理的解决方案，将溢出的数据转储到另一个像Redis的KV存储系统。虽然这种方案解决了存储容量问题，但是缺点是显而易见的。由于etcd代理需要移动数据，因此操作延迟比原生etcd大得多。此外，由于使用另KV储存系统，操作和维修费用较高。因此，我们希望了解决定etcd存储支持限制的基本因素，并尝试优化它以获得更高的容量限制。

要了解etcd的容量问题，我们首先对etcd进行了持续注入数据的应力测试。当etcd中存储的数据量超过40GB时，经过compact操作，我们发现put操作的延迟显著增加，许多put操作超时。仔细查看监视工具，我们发现延迟的增加是由于boltdb的内部spill操作（参见下面的定义）变慢造成的，这大约需要8秒，远远高于通常的1ms。监视结果如图1所示。在多次运行中，实验结果是一致的，这意味一旦etcd容量超过40GB，所有的读和写操作都比正常情况下慢得多，这对于大规模数据应用程序来说是不可接受的。

图1. 当数据超过40GB时，etcd的性能下降。

etcd内部

etcd存储层由内存中基于btree的索引层和基于boltdb的磁盘存储层两大部分组成。文档主要关注底层boltDB层，因为它是优化目标。以下是对boltDB的介绍，引用自https://github.com/boltdb/bolt/blob/master/README.md

Bolt最初是LMDB的一个移植，所以它在架构上是类似的。

它们都使用B+树，具有ACID语义和完全可序列化的事务，并且使用一个写入器和多个读取器支持无锁MVCC。

Bolt是一个相对较小的代码库（<3KLOC），适用于嵌入式、可序列化的事务键/值数据库，因此它可以成为对数据库如何工作感兴趣的人的一个很好的起点。

如上所述，bolteDB设计简洁，可以嵌入到其他软件中作为数据库使用。例如，etcd内置了boltDB作为内部存储k/v数据的引擎。boltDB使用B+树存储数据，叶子节点存储真实的键/值。它将所有数据存储在一个文件中，使用mmap syscall将其映射到内存。它使用write syscall读取和更新文件。基本的数据单元称为页（page），默认为4KB。当页删除发生时，boltdb不会直接回收已删除页的存储。相反，它临时保存已删除的页，以形成一个空闲的页池供后续使用。这个自由页池在boltDB中称为freelist。图2给出了一个boltDB页元数据的示例。

图2. boltDB页元数据

红色页43、45、46、50正在使用，而42、44、47、48、49、51页以后可以供使用。

问题

当用户数据频繁写入etcd时，内部的B+树结构将被调整（例如重新平衡、拆分节点）。spill操作是boltDB中将用户数据持久化到磁盘的关键步骤，这发生在调整树结构之后。它向freelist释放未使用的页，或者向freelist请求页来保存数据。

通过对spill操作的深入调查，我们发现在spill操作中存在如下代码的性能瓶颈：

// arrayAllocate returns the starting page id of a contiguous list of pages of a given size.
// If a contiguous block cannot be found then 0 is returned.
func (f *freelist) arrayAllocate(txid txid, n int) pgid {
         ...
    var initial, previd pgid
    for i, id := range f.ids {
        if id <= 1 {
            panic(fmt.Sprintf("invalid page allocation: %d", id))
        }
        // Reset initial page if this is not contiguous.
        if previd == 0 || id-previd != 1 {
            initial = id
        }
        // If we found a contiguous block then remove it and return it.
        if (id-initial)+1 == pgid(n) {
            if (i + 1) == n {
                f.ids = f.ids[i+1:]
            } else {
                copy(f.ids[i-n+1:], f.ids[i+1:])
                f.ids = f.ids[:len(f.ids)-n]
            }
            ...
            return initial
        }
        previd = id
    }
    return 0
}

上面的代码表明，当boltDB在freelist中重新分配页时，它尝试分配连续的n个空闲页供使用，如果找到了连续的空间，则返回起始页面id。代码中的f.ids是一个数组，记录了内部空闲页的id。例如，对于图2所示的情况，f.ids=[42,44,47,48,49,51]

该方法对连续n页执行线性扫描。例如，当freelist中有很多内部片段时，freelist中存在的连续页大多是小尺寸的，例如1或2，如果请求连续页大小较大，则算法将花费很长时间执行。此外，算法需要移动数组的元素。当有很多数组元素时，即大量的数据存储在内部，这个操作非常慢。

优化

通过以上分析，我们了解到线性扫描空页并不是一个可伸缩的算法。受到前雅虎首席科学家Udi Manber的启发，他曾经说过雅虎最重要的三种算法是哈希，哈希和哈希！（hashing, hashing and hashing!），我们尝试使用多个散列来解决可伸缩性问题。

在我们的优化中，使用集（set）来组织大小相同的连续页，然后使用哈希算法将不同的页大小映射到不同的集。请参见下面新freelist结构中的freemaps数据结构。当用户需要一个大小为n的连续页时，我们只查询freemaps来找到连续空间的第一个页。

type freelist struct {
  ...
    freemaps map[uint64]pidSet // key is the size of continuous pages(span), value is a set which contains the starting pgids of same size
    forwardMap map[pgid]uint64 // key is start pgid, value is its span size
    backwardMap map[pgid]uint64 // key is end pgid, value is its span size
    ...
}

此外，在释放连续页时，我们需要将尽可能多的内容合并到更大的连续页中。原始算法使用一种耗时的方法（O（nlgn））。我们也使用哈希算法对其进行优化。新方法使用了两个新的数据结构，forwardMap和backwardMap，在代码上面的注释中提供了解释。

当一个页被释放时，它试图通过查询backwardMap与前一个页合并，并通过查询forwardMap与下一个页合并。具体算法如下面的mergeWithExistingSpan函数所示。

// mergeWithExistingSpan merges pid to the existing free spans, try to merge it backward and forward
func (f *freelist) mergeWithExistingSpan(pid pgid) {
    prev := pid - 1
    next := pid + 1
    preSize, mergeWithPrev := f.backwardMap[prev]
    nextSize, mergeWithNext := f.forwardMap[next]
    newStart := pid
    newSize := uint64(1)
    if mergeWithPrev {
        //merge with previous span
        start := prev + 1 - pgid(preSize)
        f.delSpan(start, preSize)
        newStart -= pgid(preSize)
        newSize += preSize
    }
    if mergeWithNext {
        // merge with next span
        f.delSpan(next, nextSize)
      newSize += nextSize
    }
    f.addSpan(newStart, newSize)
}

新的算法如图3所示。当第45、46页被释放时，算法尝试与第44页合并，然后与第47、48、49页合并，以形成一个新的自由页跨。

图3. 合并整个页跨度的说明

上面的算法类似于内存管理中使用的隔离自由列表算法。它将页分配时间复杂度从O（n）降低到O（1），并将发布时间从O（nlgn）降低到O（1）。

评估

以下测试在一个单节点etcd集群中进行，以排除网络等其他因素。该测试模拟了100个客户机同时向etcd输入100万kv对。键/值内容是随机的，我们将吞吐量限制为5000 op/s。测试工具是etcd官方基准测试工具。给出了延迟结果。

使用新的隔离hashmap的性能

旧算法的性能

有一些超时没有完成测试。

比较

时间越短，性能越好。性能提升因子是归一化到最新哈希算法的运行时。

新算法的性能在更大的场景下会更好。

结论

新的优化方法降低了etcd中的时间复杂度，内部自由列表分配算法从O（n）到O（1），页释放算法从O（nlgn）到O（1），解决了etcd在大数据库规模下的性能问题。实际上，etcd的性能不再受存储大小的限制。etcd存储100GB数据时的读写操作可以与存储2GB数据一样快。此新算法是完全向后兼容的，你可以在不需要数据迁移或数据格式更改的情况下获得此新算法的好处！目前，该优化在阿里巴巴已经进行了2个多月的反复测试，没有出现意外。它已被贡献给开源社区，这里有链接。你可以在新版本的boltdb和etcd享受它。

关于作者

陈星宇（github id: WIZARD-CXY），阿里云软件工程师。他是阿里巴巴etcd集群管理的所有者，也是etcd/kubernetes的活跃贡献者。他的主要兴趣是etcd集群的性能和稳定性。