共计 6924 个字符，预计需要花费 18 分钟才能阅读完成。
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 做了并发回放的优化；
等等等等……