文档章节

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

阿里云云栖社区
 阿里云云栖社区
发布于 05/15 10:58
字数 2415
阅读 209
收藏 9

作者 | 阿里云智能事业部高级开发工程师 陈星宇(宇慕)

概述

etcd是一个开源的分布式的kv存储系统, 最近刚被cncf列为沙箱孵化项目。etcd的应用场景很广,很多地方都用到了它,例如kubernetes就用它作为集群内部存储元信息的账本。本篇文章首先介绍我们优化的背景,为什么我们要进行优化, 之后介绍etcd内部存储系统的工作方式,之后介绍本次具体的实现方式及最后的优化效果。

优化背景

由于阿里巴巴内部集群规模大,所以对etcd的数据存储容量有特殊需求,之前的etcd支持的存储大小无法满足要求, 因此我们开发了基于etcd proxy的解决方案,将数据转储到了tair中(可类比redis))。这种方案虽然解决了数据存储容量的问题,但是弊端也是比较明显的,由于proxy需要将数据进行搬移,因此操作的延时比原生存储大了很多。除此之外,由于多了tair这个组件,运维和管理成本较高。因此我们就想到底是什么原因限制了etcd的存储容量,我们是否可以通过技术手段优化解决呢?

提出了如上问题后我们首先进行了压力测试不停地像etcd中注入数据,当etcd存储数据量超过40GB后,经过一次compact(compact是etcd将不需要的历史版本数据删除的操作)后发现put操作的延时激增,很多操作还出现了超时。监控发现boltdb内部spill操作(具体定义见下文)耗时显著增加(从一般的1ms左右激增到了8s)。之后经过反复多次压测都是如此,每次发生compact后,就像世界发生了停止,所有etcd读写操作延时比正常值高了几百倍,根本无法使用。

etcd内部存储工作原理

etcd存储层可以看成由两部分组成,一层在内存中的基于btree的索引层,一层基于boltdb的磁盘存储层。这里我们重点介绍底层boltdb层,因为和本次优化相关,其他可参考上文。

etcd中使用boltdb作为最底层持久化kv数据库,boltdb的介绍如下:

Bolt was originally a port of LMDB so it is architecturally similar. 
Both use a B+tree, have ACID semantics with fully serializable transactions, and support lock-free MVCC using a single writer and multiple readers.
Bolt is a relatively small code base (<3KLOC) for an embedded, serializable, transactional key/value database so it can be a good starting point for people interested in how databases work。

如上介绍,它短小精悍,可以内嵌到其他软件内部,作为数据库使用,例如etcd就内嵌了boltdb作为内部存储k/v数据的引擎。
boltdb的内部使用B+ tree作为存储数据的数据结构,叶子节点存放具体的真实存储键值。它将所有数据存放在单个文件中,使用mmap将其映射到内存,进行读取,对数据的修改利用write写入文件。数据存放的基本单位是一个page, 大小默认为4K. 当发生数据删除时,boltdb不直接将删掉的磁盘空间还给系统,而是内部将他先暂时保存,构成一个已经释放的page池,供后续使用,这个所谓的池在boltdb内叫freelist。例子如下:

红色的page 43, 45, 46, 50 页面正在被使用,而page 42, 44, 47, 48, 49, 51 是空闲的,可供后续使用。

如下etcd监控图当etcd数据量在50GB左右时,spill 操作延时激增到了8s

问题分析

由于发生了用户数据的写入, 因此内部B+ tree结构会频繁发生调整(如再平衡,分裂合并树的节点)。spill操作是boltdb内部将用户写入数据commit到磁盘的关键一步, 它发生在树结构调整后。它释放不用的page到freelist, 从freelist索取空闲page存储数据。

通过对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
}

之前etcd内部内部工作原理讲到boltdb将之前释放空闲的页面存储为freelist供之后使用,如上代码就是freelist内部page再分配的函数,他尝试分配连续的n个page页面供使用,返回起始页page id。 代码中f.ids是一个数组,他记录了内部空闲的page的id。例如之前上图页面里f.ids=[42,44,47,48,49,51]

当请求n个连续页面时,这种方法通过线性扫描的方式进行查找。当遇到内部存在大量碎片时,例如freelist内部存在的页面大多是小的页面,比如大小为1或者2,但是当需要一个size为4的页面时候,这个算法会花很长时间去查找,另外查找后还需调用copy移动数组的元素,当数组元素很多,即内部存储了大量数据时,这个操作是非常慢的。

优化方案

由上面的分析, 我们知道线性扫描查找空页面的方法确实比较naive, 在大数据量场景下很慢。前yahoo的chief scientist Udi Manber曾说过在yahoo内最重要的三大算法是 hashing, hashing and hashing!(From algorithm design manual)

因此我们的优化方案中将相同大小的连续页面用set组织起来,然后在用hash算法做不同页面大小的映射。如下面新版freelist结构体中的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).我们通过hash算法,新增了另外两个数据结构forwardMapbackwardMap, 他们的具体含义如下面注释所说。

当一个页面被释放时,他通过查询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)
}

新的算法借鉴了内存管理中的segregated freelist的算法,它也使用在tcmalloc中。它将page分配时间复杂度由O(n)降为O(1), 释放从O(nlgn)降为O(1),优化效果非常明显。

实际优化效果

以下测试为了排除网络等其他原因,就测试一台etcd节点集群,唯一的不同就是新旧算法不同, 还对老的tair作为后端存储的方案进行了对比测试. 模拟测试为接近真实场景,模拟100个客户端同时向etcd put 1百万的kv对,kv内容随机,控制最高5000qps,总计大约20~30GB数据。测试工具是基于官方代码的benchmark工具,各种情况下客户端延时如下

旧的算法时间

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

新的segregated hashmap

etcd over tail 时间

方案 完成耗时 性能提升倍数
新的hashmap算法 210s 1x
旧array算法 4974s 24x
etcd over tair 1705 8x

在数据量更大的场景下,并发度更高的情况下新算法提升倍数会更多。

总结

这次优化将boltdb中freelist分配的内部算法由O(n)降为O(1), 释放部分从O(nlgn)降为O(1), 解决了在超大数据规模下etcd内部存储的性能问题,使etcd存储100GB数据时的读写操作也像存储2GB一样流畅。并且这次的新算法完全向后兼容,无需做数据迁移或是数据格式变化即可使用新技术带来的福利!

目前该优化经过2个多月的反复测试, 上线使用效果稳定,并且已经贡献到了开源社区link,在新版本的boltdb和etcd中,供更多人使用。

阅读原文

本文为云栖社区原创内容,未经允许不得转载。

© 著作权归作者所有

阿里云云栖社区
粉丝 337
博文 1249
码字总数 2919187
作品 0
朝阳
私信 提问
etcd 在超大规模数据场景下的性能优化

本文被收录在 5 月 9 日 cncf.io 官方 blog 中,链接:https://www.cncf.io/blog/2019/05/09/performance-optimization-of-etcd-in-web-scale-data-scenario/ 概述 etcd 是一个开源的分布式的......

阿里巴巴云原生
05/14
0
0
Kyligence发布最新旗舰产品KAP 2.1,为Apache Kylin企业用户提供更快更强的大数据分析能力

据悉,领先的智能大数据分析技术及解决方案供应商上海跬智信息技术有限公司(Kyligence)今日宣布正式发布企业级产品KyligenceAnalytics Platform (KAP) 2.1版本。KAP2.1在既有基础上进行了一...

kyligence
2016/11/14
205
1
面向高维稀疏数据场景的深度学习框架 - X-DeepLearning

X-DeepLearning (简称 XDL ) 是面向高维稀疏数据场景(如广告/推荐/搜索等)深度优化的一整套解决方案。 现有开源框架在分布式性能、计算效率、水平扩展能力以及实时系统适配性的等方面往往难...

匿名
2018/12/29
0
0
etcd:从应用场景到实现原理的全方位解读

原文出自: http://www.infoq.com/cn/articles/etcd-interpretation-application-scenario-implement-principle 随着CoreOS和Kubernetes等项目在开源社区日益火热,它们项目中都用到的etcd组件...

ponpon_
2017/02/16
0
0
【杭州】源创会第37期开始报名

本期图文回顾链接:http://www.oschina.net/question/12_243706 请大家下载 OSC 客户端用于现场扫描二维码签到和抽奖: http://www.oschina.net/app 本次源创会视频直播地址:http://mudu.t...

阿娇OSC
2015/06/23
58.4K
102

没有更多内容

加载失败,请刷新页面

加载更多

运维规范

命名规范 发布流程 监控告警 故障定位 状态 日志 监控

以谁为师
28分钟前
1
0
约瑟夫环(报数游戏)java实现

开端 公司组织考试,一拿到考题,就是算法里说的约瑟夫环,仔细想想 以前老师将的都忘了,还是自己琢磨把~ package basic.gzy;import java.util.Iterator;import java.util.LinkedList;...

无极之岚
45分钟前
2
0
Kernel字符设备驱动框架

Linux设备分为三大类:字符设备,块设备和网络设备,这三种设备基于不同的设备框架。相较于块设备和网络设备,字符设备在kernel中是最简单的,也是唯一没有基于设备基础框架(device结构)的...

yepanl
今天
3
0
Jenkins 中文本地化的重大进展

本文首发于:Jenkins 中文社区 我从2017年开始,参与 Jenkins 社区贡献。作为一名新成员,翻译可能是帮助社区项目最简单的方法。 本地化的优化通常是较小的改动,你无需了解项目完整的上下文...

Jenkins中文社区
昨天
4
0
Spring中如何使用设计模式

关于设计模式,如果使用得当,将会使我们的代码更加简洁,并且更具扩展性。本文主要讲解Spring中如何使用策略模式,工厂方法模式以及Builder模式。 1. 策略模式 关于策略模式的使用方式,在S...

爱宝贝丶
昨天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部