全栈算力,加速行业AI落地 了解详情
写点什么

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

  • 2019-05-28
  • 本文字数:3885 字

    阅读完需:约 13 分钟

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 算法,新增了另外两个数据结构 forwardMapbackwardMap,他们的具体含义如下面注释所说。


当一个页面被释放时,他通过查询 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 中,供更多人使用。

作者简介

陈星宇(宇慕)


阿里云智能事业部高级开发工程师


本文转载自公众号阿里巴巴云原生(ID:Alicloudnative)


原文链接


https://mp.weixin.qq.com/s/oNfNK9DlI24gVkC-T5O_dw


2019-05-28 08:0012581

评论 1 条评论

发布
用户头像
666
2022-05-23 21:12
回复
没有更多了
发现更多内容

After Effects 2024 for Mac(视频特效制作软件) v24.0.1.2完整激活版

mac

苹果mac Windows软件 视频特效软件 After Effects 2024 AE2024

语音识别技术在智能客服领域的应用与挑战

来自四九城儿

基于大模型训练的中文自然语言处理平台

百度开发者中心

自然语言处理 模型训练 大模型

与创新者同行,Doris Summit Asia 2023 线下技术峰会圆满落幕!

SelectDB

数据库 大数据 数据分析 实时数仓 apache doris

Mac电脑专业思维导图软件 ConceptDraw MINDMAP最新激活版

胖墩儿不胖y

Mac软件 思维导图软件

3种方法,用Java找出两个List中的重复元素

华为云开发者联盟

Java 开发 华为云 华为云开发者联盟

故障解析丨Clone节点导致主从故障

GreatSQL

VideoProc Converter 4K for mac(视频转换软件)

展初云

Mac 格式转换 Mac软件 视频格式

Khronos: 面向万亿规模时间线的性能监控引擎建设实践

阿里技术

性能监控 Khronos 时序数据管理

语音识别技术在移动设备上的应用与优化

来自四九城儿

iStatistica Pro 5 for Mac(系统活动监控工具)

展初云

Mac Mac软件

概念回顾:负载均衡、四层负载均衡、七层负载均衡

NGINX开源社区

负载均衡 四层负载均衡 七层负载均衡

Vuepress 三分钟搭建一个精美的文档或博客

凌览

Vue 博客 vuepress

安全攻防实战丨如何预防利用中间人攻击进行小程序刷分

华为云开发者联盟

网络安全 安全 华为云 系统安全 华为云开发者联盟

【万字长文】基于阿里云PAI平台搭建知识库检索增强的大模型对话系统

阿里云大数据AI技术

人工智能

大模型训练助力获取高精度CV模型

百度开发者中心

自然语言 大模型

火山引擎 LAS Spark 升级:揭秘 Bucket 优化技术

字节跳动数据平台

数据库 大数据 火山引擎 企业号10月PK榜 Spark Bucket

大模型训练中CPU与GPU使用率的优化策略

百度开发者中心

训练 大模型

ConceptDraw PROJECT 14 for Mac(项目管理软件)

展初云

项目管理 Mac软件

「我在淘天做技术」双11背后的营销技术体系

阿里技术

营销 淘天 营销技术

Mac系统设置维护工具TinkerTool System最新激活版

mac大玩家j

系统维护 Mac软件 系统维护软件

18万奖金!开放原子开源大赛OpenCloudOS赛题征集开启

开放原子开源基金会

开源 大赛

Topaz Video AI for Mac:视频增强和修复工具

彩云

Topaz Video AI 视频增强修复工具

1024程序员节,飞桨星河社区开发者们一起闯关升级、玩转Prompt应用赢大奖~

飞桨PaddlePaddle

飞桨 大模型 Prompt 一言插件

ps插件:alpaca增效工具 v2.8.1 中文版

彩云

ps插件 Alpaca插件

为何在中国 Navicat 远比 DBeaver 流行

Bytebase

数据库 sql DevOps navicat Dbeaver

etcd在超大规模数据场景下的性能优化_数据库_陈星宇(宇慕)_InfoQ精选文章