写点什么

给你一本武林秘籍,和 KeeWiDB 一起登顶高性能

  • 2022 年 9 月 30 日
    北京
  • 本文字数:6236 字

    阅读完需:约 20 分钟

给你一本武林秘籍,和KeeWiDB一起登顶高性能

KeeWiDB,骨骼清奇,是万中无一的 NoSQL 奇才。现将 KeeWiDB 高性能修炼之路整理至此秘籍,见与你有缘,随 KeeWiDB 一同登顶吧!


创新性分级存储架构设计,单节点读写能力超过 18 万 QPS,最高可线性堆叠至千万级并发吞吐量,同时兼容 Redis 协议,访问延迟达到毫秒级,新一代分布式 KV 存储数据库 KeeWiDB 在 NoSQL 江湖中脱颖而出。


由内而外深入探索其成长史,可从三个角度讲起,为并发而生的架构、量身“自”造的引擎以及新老硬件的加持。修炼的过程有点长,且听我娓娓道来。

江湖 · 风云涌动

随着 web2.0 的快速发展,SNS 网站的兴起彻底带火了 NoSQL,个性化实时的动态请求带来高并发负载问题、海量用户产生的动态数据带来存储效率问题等都把关系型数据库难得够呛。更别提突然爆火需要的超高吞吐、全球部署需要的超低延迟了。


至此数据库江湖一分为二,SQL 是“稳重”的高僧,而 NoSQL 则是“灵活”的新秀,以“轻”、“快”突出重围。


江湖道法:一生二,二生三,三生万物。


NoSQL 数据库领域逐渐演化出四大门派,分别是键值(Key-Value)存储派、文档(Document-Oriented)存储派、列(Wide Column Store/Column-Family)存储派和图形(Graph-Oriented)存储派,各具特色。


大弟子 KV 存储数据库应用最为广泛、技术最为成熟。过去几年,江湖中最受欢迎的数据库产品 Redis,就是 KV 一派,支持高并发、低延迟以及丰富的数据结构。但 Redis 本身是一个全内存的 KV 数据库,无法解决海量数据所带来的规模与成本问题;同时,随着近些年 Redis 的应用场景渐渐突破了缓存的范畴,其数据可靠性也面临巨大的挑战


为了解决 Redis 的痛点问题,江湖中出现了基于磁盘的 KV 数据库产品,例如 Pika、Kvrocks、SSDB 等。这些产品虽然一定程度上能够满足业务在成本、持久化、规模方面的诉求,但性能跟不上,且与 Redis 有着明显的差距


江湖在等待一位武林高手破解难题。KeeWiDB,应运而生,脱颖而出。

KeeWiDB·脱颖而出

擂台赛,突出重围!


来看一组基于 String 类型的单节点测试结果,得益于多线程优势,KeeWiDB 不仅在吞吐量上超过了 Redis,而且 P99 延迟能做到不超过 3 毫秒



这么高的吞吐是怎么做到的呢?简单说,目标导向(吸星大法)!


KeeWiDB 就是要做到 Redis 和基于磁盘的 KV 数据库产品做不到的,就是要实现集低成本、高并发、高性能于一体


具体地,新一代分布式 KV 存储数据库产品 KeeWiDB,保留了基于磁盘的 KV 数据库产品对于成本和规模问题优秀解法,通过创新性的软硬件结合方法进一步提供了媲美 Redis 的性能以及命令级持久化的能力,同时满足了业务在性能、成本、持久化、规模四个方面的核心诉求,带给用户最极致的使用体验。


台上一分钟,台下十年功!KeeWiDB 的成就并非凭空,也得是历经寒洞修炼才能走上高性能之路。

筋骨篇·为并发而生的软件架构

要想成为一个武林高手,首先要有一副强健的筋骨,这是一切武功的基础。对于 KeeWiDB 来说,一个优秀的软件架构就是它的钢筋铁骨。

(1)Scale Out 的整体架构

KeeWiDB 既是分布式 KV 存储产品,又能支持冷热分离。江湖都在传其架构必然复杂,但大道至简,“Simple is The Best”。


KeeWiDB 的架构就只分为 Server 和 Proxy 两层,如下图:



图:KeeWiDB 的整体架构


Server 层由多个 server 节点组成,实现数据存储与数据库核心特性


与 Redis Cluster 类似,Server 层的节点先被分为一个个独立的分片,再将整个系统中的数据划分到 16384 个虚拟 slot 中,由每个分片独立负责其中一部分 slot 的读写;分片内部有多个节点,节点之间通过 Replication 协议完成数据复制,构成一主多备的高可用架构;分片之间通过 Gossip 协议通信,一起组成一个去中心化的集群。这样,用户访问 Server 层中任意节点,请求都能路由到正确的节点。此外,Server 层还支持新节点自动发现、故障探测、故障自动切换、数据搬迁等能力,极大降低了运维成本。


Proxy 层由多个无状态的 proxy 节点组成,实现代理转发功能


这一层是可选的,主要是帮助没有实现集群重定向协议的客户端屏蔽 KeeWiDB 底层的实现,让用户可以用像访问原生 Redis 一样访问 KeeWiDB,减少用户的迁移成本。同时,我们在 Proxy 层也做了相当多的产品功能,例如监控指标采集,流量控制,读写分离等等。


这里再强调一点,无论是 Server 层还是 Proxy 层,都可以很方便地通过新增节点来快速地提升整个系统的并发能力。

(2)Shared Nothing 的多线程模型

作为一个基于持久化介质的数据库,KeeWiDB 很自然地选用了多线程模型,以便使用更多的 CPU 核心来提升单节点性能。传统的数据库存储引擎往往使用多线程共享资源的编程模型,在这种模型下,性能的优化方向是尽最大努力减少锁竞争,提高并行度。例如,LevelDB 的 MemTable 为了提升性能就是基于无锁 SkipList 来实现的。


但是存储引擎内部的共享资源除了各种数据结构和数据文件外,往往还包括 WAL 这样的日志文件。这些日志文件的写入过程涉及到持久化操作,相对较慢,但为了保证写入的顺序一般又需要加锁。这样一来,虽然是多线程并发地处理用户请求,但到了写日志时却退化成了串行执行,显然会成为性能瓶颈。同时,随着硬件技术的发展,网络和磁盘的访问延迟可降至 10us 量级,软件栈的处理延迟在整个 IO 路径上的占比逐渐凸显出来,这种情况下无论是锁冲突还是线程的上下文切换,都可能造成巨大的性能毛刺。


要解决上述这些问题,必须禁止线程间共享资源,即 Shared Nothing


在前文中我们谈到,Server 层每个节点独立负责一部分 slot,这里我们又进一步将每个节点的 slot 区间按规则划分为多个子区间,每个 worker 线程负责特定一组 slot 子区间的读写,并且每个 worker 线程享有单独的管理结构和存储资源,以此保证在每个用户请求的处理过程中都不涉及任何的线程锁和线程上下文切换,这无论是对单个请求延迟的降低,还是多个请求并发的提升,都有巨大的好处。



图:KeeWiDB 单个节点内部多线程的 Shared Nothing 架构

(3)协程,让并发更上一层楼

通过前文对整体架构和多线程模型的设计,KeeWiDB 已经可以让分属不同 slot 的用户请求高效地并发起来了。但一个线程负责的往往不止一个 slot,同一个 slot 内也远不止一个 key,所以用户的多个请求分发到同一个线程的概率还是有的,如果线程内部只能顺序地处理这些请求,那大量的时间都会花费在同步等待磁盘 IO 上,并发度还是不够。


为了进一步提升单个线程内部的并发度,我们引入了 C++20 的新特性——协程


协程的本质是函数。调用协程后,原来的地方就会被阻塞,主动把 CPU 让给别的协程,这就实现了线程内部的并发;等条件满足了再通过协程的中断可恢复特性在原来的地方继续运行,这种写法又跟同步一样自然。


简言之,协程用同步的语义解决了异步的问题,让我们用较小的开发代价实现了巨大的性能提升。

内功篇·量身打造的存储引擎

钢筋铁骨的基础已经打好,下一步 KeeWiDB 需要一套适合自己的内功心法。


如果内功心法高效,即使是简单的一拳一脚也能虎虎生风,威力十足;反之,如果内功心法弱鸡,那再华丽的招式也只能是花拳绣腿,中看不中用。


对于 KeeWiDB 这样的数据库存储产品来说,存储引擎就是我们要重点打造的内功心法。

(1)LSM Tree 的“功过是非”

当前业界主流的 KV 存储产品大都采用了基于 LSM Tree 的 RocksDB / LevelDB 作为自己的存储引擎。这主要是因为,LSM Tree 通过独特的“Out-of-Place Update”设计,可以将来自用户的离散随机写入转换为对持久化介质的批量顺序写入,而磁盘设备的顺序 IO 性能往往要优于随机 IO,这种设计有利于磁盘设备扬长避短。


但凡事有利必有弊,RocksDB / LevelDB 这类存储引擎优异的写入性能也是牺牲了一些东西才换来的,在《RocksDB Tuning Guide》中就有提到它的三大问题:


  • 空间放大(Space Amplification):用户对数据的所有更新操作都是“Out-of-Place Update”,数据可能有多个版本,但失效的旧版本数据需要等 Compaction 才能真正的删除,无法及时清理,从而造成空间放大。

  • 读放大(Read Amplification):用户读取数据时,可能需要从上到下(从新到旧)查找多个层的 SSTable 文件,并且在每一个 SSTable 文件中的查找都需要读取该文件的多个 meta 数据块,从而造成读放大。

  • 写放大(Write Amplification):用户写入数据时需要先写入 WAL 文件,后续无论是将内存中的 MemTable 持久化为 L0 层的 SSTable 文件,还是将每一层的小 SSTable 文件合并到下一层的大 SSTable 文件,都会产生重复写入,从而造成写放大。


其中,空间放大和读放大是“Out-of-Place Update”这种方式天生带有的特点,而写放大则是为了优化前两个问题,引入 Compaction 机制后带来的。这三个问题是一组矛盾体,就像分布式系统中的 CAP 一样不可兼得,只能根据具体的业务场景做均衡和取舍


在 HDD 作为主流磁盘设备的时代,顺序写入的性能比随机写入高 2~3 个数量级,用几十倍的写放大来换取近千倍的写入性能提升是一桩划算的买卖。但随着硬件技术的发展,SSD 逐渐替代 HDD 成为当前的主流磁盘设备,情况悄然发生了变化:


一则,SSD 的顺序写入性能虽然依旧高于随机写入,但差异已经缩小到十倍以内;二则,SSD 的使用寿命和其写入量有关,写放大太严重会导致 SSD 内部元件的可擦除次数急剧下降,大大缩短其使用寿命。


在这种情况下,这笔买卖是否依旧划算?

(2)基于哈希索引的自研存储引擎

KeeWiDB 作为一个云上的数据库产品,天然需要面对多租户场景,一台机器上往往会部署多个 server 节点,这些节点可能会共享同一块磁盘;同时,在前文“筋骨篇”的第二节中我们提到每个 server 节点的进程中还有多个 worker 线程,每个线程都有独立的专属存储引擎,但它们共享一块磁盘。所以,即使每个进程中的每个线程自身都是顺序地写入这块磁盘,但从磁盘的角度,来自不同进程不同线程的写入整体上还是随机的。


此外,KV 存储产品应对的业务场景里,用户请求都是以点查为主,范围查询较少,对应到对磁盘设备的访问上,就是随机读占绝大多数,顺序读较少。LSM Tree 类存储引擎虽然可以把随机写转换为顺序写,却不能把随机读也转为顺序读。相反,LSM Tree 类存储引擎的设计思想本质上就是牺牲一部分读性能来换取极致的写性能,对随机读反而更不友好。


综合前文提到的 LSM Tree 类存储引擎的优缺点,以及 KV 存储云产品的业务特点,KeeWiDB 最终选择自己来,推出基于哈希索引的全新自研存储引擎


新引擎基于 Page 页进行数据组织,并通过 Free List 进行页管理;而每个 Page 又包含数个 Block,它是最小的存储分配单元,并通过 Page 页首部的一个 Bitmap 进行管理。这样我们就能在 O(1)时间复杂度下,进行高效的数据块分配和释放,同时具有更加紧凑的数据组织形式,更小的写放大和更小的空间放大。



图:KeeWiDB 自研存储引擎的数据组织结构


打开 Page 页内部结构给大家瞧瞧!



图:KeeWiDB 自研存储引擎的 Page 页内部结构


新引擎采用哈希表作为主索引,主要是基于其优秀的等值查询时间复杂度。在工程实践中,每个哈希桶对应 1 个 Page 页,在 Meta Page 缓存到内存的情况下,每次读写操作平均只需要 1 次磁盘 IO。同时,作为磁盘型数据库,在内存资源有限的情况下,相较于 B 族索引,哈希索引的空间占用更小,具有更高的内存利用率。


为了避免哈希 resize 可能会导致的长尾延迟问题,KeeWiDB 选择了线性哈希表。线性哈希表能够将哈希桶分裂的消耗分摊到单次插入操作中,且每次只需要分裂 1 个哈希桶,绝大多数情况下,分裂只需要 1 次额外的磁盘 IO,操作消耗更小,用户请求的延迟更稳定。



图:KeeWiDB 自研存储引擎的线性哈希索引


在前文“筋骨篇”的第三节中我们提到,为了在处理磁盘 IO 时更好得利用 CPU 资源,我们引入了协程。为了适配协程并发的需求,KeeWiDB 在新引擎的线性哈希表做了并发安全的改造,能支持增删查改的并发操作,而基本的互斥操作单元仅为 1 个 Page 页,在 Shared Nothing 的多线程模型里,多协程的互斥基本不需要额外的同步消耗,能更好的利用计算资源,提高系统整体的吞吐量。

兵器篇·来自硬件技术的加持

工欲善其事,必先利其器!自我修炼已完成,如果再有一把称手的神兵利器,岂不是如虎添翼?

(1)拥抱新硬件

KeeWiDB 的立项之初,除了专注自身的软件架构和存储引擎设计之外,也一直在关注新型硬件技术的发展。当时市面上比较成熟的新型存储介质有:ScaleFlux 公司的可计算存储设备,Samsung 公司的 KV SSD,以及 Intel 公司的 Persistent Memory(PMem)。


KeeWiDB 综合考虑了易用性、成熟度、性价比等多方面的条件之后,最终选择 Intel 公司的 PMem,它具有以下特点:


  • 持久化:PMem 提供持久化相关指令,完成持久化的数据即使掉电也不丢失;

  • 低延迟:PMem 的读写速度比 SSD 还要快 1~2 个数量级,接近内存的读写速度;

  • 大容量:PMem 的单条最大容量可达 512GB,相比于传统内存的单条最大容量 64GB 有 8 倍的提升,单服务器容量轻松上 TB;

  • 字节寻址:PMem 的读写大小没有限制,相比于传统磁盘每次至少读写一个块(通常大小为 4KB)的限制,其读写粒度更细。



图:PMem 新硬件在整个存储硬件体系中的位置


数据库相关的研发和运维同学都知道,数据库虽然理论上需要保证事务的 ACID 四大特性,但实际上,这里面的 D(durability)很难百分百做到。以 MySQL 为例,要想做到严格的机器掉电不丢数据,必须开启“双 1 设置”;但因为磁盘的写入速度相比内存慢 2~3 个数量级,一旦开启“双 1 设置”,数据库的写入性能就会急剧下降到用户难以接受的地步。所以在实际使用中很少有用户开启 MySQL 的“双 1 设置”,这就只能做到进程崩溃时靠操作系统 Page Cache 刷脏的帮助不丢数据,机器掉电还是会丢一部分数据。


KeeWiDB 将事务日志选择性地存储到 PMem 中,利用其字节寻址的特性和低延迟持久化的特点,在实现命令级持久化的同时依然可以为用户提供高性能的写入



图:事务日志存磁盘和 PMem 的对比

(2)善用老技术

云上的数据库产品需要处理复杂多变的用户场景。俗话说,林子大了什么鸟都有,有的用户延迟敏感,有的用户并发高,还有的用户流量猛。


前文中提到,多个实例的 server 节点可能会被分配到同一块物理磁盘,虽然当前数据中心使用的 NVMe SSD 的性能已经非常强悍,但如果多个实例的用户同时发起高并发或大流量的读写,还是可能超出单块 SSD 的性能上限。


对于硬件技术的应用,KeeWiDB 从来都是喜新但不厌旧(吸星大法再现)。所以针对这种情况,KeeWiDB 采用成熟的 RAID 0 技术,将多块 SSD 以条带的方式组成一个磁盘组,对软件层展现为一块逻辑磁盘。这样一来每个节点都可以同时用到多块 SSD 的 IO 能力,单个节点的并发上限有效提升,也起到了在多个实例之间削峰填谷的作用,KeeWiDB 处理读写热点冲突的能力也大大提升。


当然,有读者有疑问了,RAID 0 固有的缺点是数据没有冗余,磁盘组中的任意一块 SSD 损坏都会导致丢数据,KeeWiDB 不会因此丢数据吗?


别担心,因为 KeeWiDB 的每个分片都是主备架构的,无论是 master 还是 replica 的磁盘组损坏,都还有另一个节点可以继续服务。即使是主备两个节点的磁盘组都损坏了,也还有备份机制可以恢复数据。

未完待续

有了高度可扩展的软件架构做筋骨,高效强大的自研存储引擎当内功,再加上来自新老硬件技术的兵器加持,KeeWiDB 已经是大家心中的“武林高手”了。但,KeeWiDB 的目标是要成为“绝顶高手”,还少了那么一些些的细节。


这里先放点预告,下次再展开说说!


  • 为了提升 server 节点的吞吐,KeeWiDB 做了组提交的优化,并去除了一般组提交方案中的主动等待来降低对延迟的影响;

  • 为了提升 hash/set 等复杂结构的并发度,KeeWiDB 细化了事务锁的粒度来允许同一个一级 key 的不同二级 key 之间做并发读写;

  • 为了解决现有基于 key 的冷热分离方案无法解决的大 key 问题,KeeWiDB 实现了基于 page 的冷热分离方案,提升了冷数据读取性能;

  • 为了让 replica 节点回放命令保证主备一致性的同时速度能跟上 master 节点的写入速度,KeeWiDB 做了并发回放的优化;


等等等等……

发布于: 刚刚阅读数: 3
用户头像

还未添加个人签名 2018.12.08 加入

还未添加个人简介

评论

发布
暂无评论
给你一本武林秘籍,和KeeWiDB一起登顶高性能_redis_腾讯云数据库_InfoQ写作社区