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做了并发回放的优化；
等等等等……
发表回复