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

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

划重点

  • etcd 优化背景
  • 问题分析
  • 优化方案展示
  • 实际优化效果

本文被收录在 5 月 9 日 cncf.io 官方 blog 中,链接:https://www.cncf.io/blog/2019/05/09/performance-optimization-of-etcd-in-web-scale-data-scenario/

概述

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 操作中如下代码耗时最多:

 1// arrayAllocate returns the starting page id of a contiguous list of pages of a given size. 2// If a contiguous block cannot be found then 0 is returned. 3func (f *freelist) arrayAllocate(txid txid, n int) pgid { 4         ... 5    var initial, previd pgid 6    for i, id := range f.ids { 7        if id <= 1 { 8            panic(fmt.Sprintf("invalid page allocation: %d", id)) 9        }1011        // Reset initial page if this is not contiguous.12        if previd == 0 || id-previd != 1 {13            initial = id14        }1516        // If we found a contiguous block then remove it and return it.17        if (id-initial)+1 == pgid(n) {18            if (i + 1) == n {19                f.ids = f.ids[i+1:]20            } else {21                copy(f.ids[i-n+1:], f.ids[i+1:]) # 复制22                f.ids = f.ids[:len(f.ids)-n]23            }2425            ...26            return initial27        }2829        previd = id30    }31    return 032}

之前 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 数据结构。

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

除此之外,当页面被释放,我们需要尽可能的去合并成一个大的连续页面,之前的算法这里也比较简单,是个是耗时的操作 O(nlgn).我们通过 hash 算法,新增了另外两个数据结构 forwardMap  和 backwardMap, 他们的具体含义如下面注释所说。

当一个页面被释放时,他通过查询 backwardMap 尝试与前面的页面合并,通过查询 forwardMap 尝试与后面的页面合并。具体算法见下面mergeWithExistingSpan 函数。

 1// mergeWithExistingSpan merges pid to the existing free spans, try to merge it backward and forward 2func (f *freelist) mergeWithExistingSpan(pid pgid) { 3    prev := pid - 1 4    next := pid + 1 5 6    preSize, mergeWithPrev := f.backwardMap[prev] 7    nextSize, mergeWithNext := f.forwardMap[next] 8    newStart := pid 9    newSize := uint64(1)1011    if mergeWithPrev {12        //merge with previous span13        start := prev + 1 - pgid(preSize)14        f.delSpan(start, preSize)1516        newStart -= pgid(preSize)17        newSize += preSize18    }1920    if mergeWithNext {21        // merge with next span22        f.delSpan(next, nextSize)23        newSize += nextSize24    }2526    f.addSpan(newStart, newSize)27}

新的算法借鉴了内存管理中的 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 时间

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

总结

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

目前该优化经过 2 个多月的反复测试, 上线使用效果稳定,并且已经贡献到了开源社区(https://github.com/etcd-io/bbolt/pull/141),在新版本的 boltdb 和 etcd 中,供更多人使用。

Image placeholder
hero_sky
未设置
  37人点赞

没有讨论,发表一下自己的看法吧

推荐文章
超大规模商用 K8s 场景下,阿里巴巴如何动态解决容器资源的按需分配问题?

导读:资源利用率一直是很多平台管理和研发人员关心的话题。本文作者通过阿里巴巴容器平台团队在这一领域的工作实践,整理出了一套资源利用提升的方案,希望能够带给大家带来一些讨论和思考。引言不知道大家有没有过

多云时代下大规模数据库管理,该怎么做?

中国经济的高速发展是世界各国人们有目共睹的,随着数字经济时代的到来,金融数据库的管理,也随之面对一系列的新技术与挑战。云计算一直以来被认为是极具颠覆性的技术力量,随着云计算的应用普及,越来越为企业重视

运营商大规模数据集群治理的实践指南

写在开头的话Q: 军哥,你们运营商行业的大规模集群,都有啥特点啊?A: 我们集群主要是承载B域、信令和互联网日志等去标识化数据,简单的说,有三个特点:1)集群规模较大:数千节点规模,近百PB数据量,日

美团大规模微服务通信框架及治理体系OCTO核心组件开源

微服务通信框架及治理平台OCTO作为美团基础架构设施的重要组成部分,目前已广泛应用于公司技术线,稳定承载上万应用、日均支撑千亿级的调用。业务基于OCTO提供的标准化技术方案,能够轻松实现服务注册/发现

高并发业务场景下的秒杀解决方案 (初探)

文章简介 本文内容是对并发业务场景出现超卖情况而写的一片解决方案。主要是利用到了Redis中的队列技术。 超卖介绍 所谓的超卖,就是我们的售卖量大于了物品的库存量。该情况一般出现在电商系统中促销类的业

架构转型先行——金融业务场景下的新一代架构实践

  赵勇中国农业银行研发中心架构管理办公室主任工程师中国农业银行研发中心架构管理办公室主任工程师,十年以上金融行业信息化架构设计与管控经验。历经互联网金融、两地三中心、分布式核心银行等大型银行系统工程

百度智能监控场景下的HBase实践

作者简介   张洋洋  百度高级研发工程师负责百度智能运维产品(Noah)的分布式时序数据库和通用配额管理平台的设计研发工作,在分布式存储和配额管理方向有广泛的实践经验。干货概览通过百度大规模时序数据

Elasticsearch 亿级数据检索性能优化案例实战!

一、前言数据平台已迭代三个版本,从头开始遇到很多常见的难题,终于有片段时间整理一些已完善的文档,在此分享以供所需朋友实现参考,少走些弯路,在此篇幅中偏重于ES的优化,关于HBase,Hadoop的设计

PHP 性能优化 - php.ini 配置

内存 默认设置 memory_limit=128M 单个进程可使用的内存最大值,这个值的设定可以从以下几点考虑: 应用的类型。如果是内存集中型应用,可增加该值; 单个PHP进程平均消耗的内存,该值

为高性能优化 PHP-FPM

PHP是无处不在的,可以说是互联网Web应用上使用最广泛的语言。 然而,它的高性能并不为人所知,尤其是在涉及到高并发系统时。这就是为什么对于这样特殊的用例,正在被Node(是的,我知道,它不是一种语

上线清单 —— 20 个 Laravel 应用性能优化项

让我们开始吧!假若你的laravel应用已经投入生产环境中。 从第一个用户,到第十,第一百,直到成千上万的用户!慢慢地,随着用户越多,你的网站会越来越慢 那我们应该如何做?细节决定成败 经过一番搜索

Hadoop YARN:调度性能优化实践

背景YARN作为Hadoop的资源管理系统,负责Hadoop集群上计算资源的管理和作业调度。美团的YARN以社区2.7.1版本为基础构建分支。目前在YARN上支撑离线业务、实时业务以及机器学习业务。离

MySQL 性能优化:8 种常见 SQL 错误用法!

1、LIMIT语句分页查询是最常用的场景之一,但也通常也是最容易出问题的地方。比如对于下面简单的语句,一般DBA想到的办法是在type,name,create_time字段上加组合索引。这样条件排序都

一场HBase2.x的写入性能优化之旅

本文通过实战跑分来展示HBase2.x的写入性能首先,简单介绍一下我们的测试环境:集群由5个节点组成,每个节点有12块800GB的SSD盘、24核CPU、128GB内存;集群采用HBase和HDFS混

Xcode调试、性能优化基本工具使用简单整理

断点1.普通断点在行号那儿点一下就加上了,最常用的断点,略。2.条件断点很多时候问题代码是被高频调用直到特定条件下才出现问题的,这种时候可以使用条件断点。在任意断点右击选择EditBreakpoint

一文带你掌握常见的Pandas性能优化方法,让你的pandas飞起来!

微信公众号:「Python读财」如有问题或建议,请公众号留言Pandas是Python中用于数据处理与分析的屠龙刀,想必大家也都不陌生,但Pandas在使用上有一些技巧和需要注意的地方,尤其是对于较大

分布式场景下Kafka消息顺序性的思考

在业务中使用kafka发送消息异步消费的场景,并且需要实现在消费时实现顺序消费,利用kafka在partition内消息有序的特点,实现消息消费时的有序性。1、在发送消息时,通过指定partition

软件定义一切,企业数字化背景下的新一代IT基础架构

 在数字经济飞速发展的背景下,企业数字化转型已经成为目标共识,企业需要建立更敏捷、智能、安全和可控的数字化转型平台,而云为这一切提供了便利条件。  软件定义作为云的一项重要技术,这几年的也变得越发火热

PostgreSQL 12 正式发布:全面的性能提升

PostgreSQL12已经发布,该版本在各方面都得到了加强,包括显著地提升查询性能,特别是对大数据集,总的空间利用率方面。这个版本为应用程序开发人员提供了更多的功能,比如对SQL/JSON路径表达式

pymysql fetchone () , fetchall () , fetchmany ()

最近在用python操作mysql数据库时,碰到了下面这两个函数,标记一下: 1.定义 1.1fetchone(): 返回单个的元组,也就是一条记录(row),如果没有结果则返回None 1.2fet

准独角兽雷鸟科技出席SACC2019,讲述AI在场景互联网下的创新革命

10月31日至11月2日,由IT168旗下ITPUB企业社区平台主办的第十一届中国系统架构师大会(SACC2019)在北京召开。作为国内最具价值的技术交流盛会,也少不了今年热门的智慧大屏话题。据了解,

etcd 常用操作介绍

安装 最简单的安装方法是直接去etcdGitHub的Release页下载预编译好的二进制文件。etcd官方为各个系统提供了不同的二进制文件,供开发者根据自己的系统去下载。 下载地址:https://g

etcd 常用操作介绍

安装 最简单的安装方法是直接去etcdGitHub的Release页下载预编译好的二进制文件。etcd官方为各个系统提供了不同的二进制文件,供开发者根据自己的系统去下载。 下载地址:https://g

降低 80% 的读写响应延迟!我们测评了 etcd 3.4 新特性(内含读写发展史)

导读:etcd作为 K8s集群中的存储组件,读写性能方面会受到很多压力,而 etcd 3.4 中的新特性将有效缓解压力,本文将从etcd 数据读写机制的发展历史着手,深入解读 etcd 3.4 新特性

阿里提出针对多目标优化的全新算法框架,同时提升电商推荐场景 GMV 和 CTR

在推荐系统中,多目标优化一直是热门话题,阿里巴巴的XiaoLin、HongjieChen等人针对推荐中的多目标优化问题提出了一种基于帕累托效率的优化算法框架,并应用在电商推荐场景中,对GMV和CTR