本文首发于 2020-06-22 21:55:10
《ClickHouse 和他的敌人们》系列文章转载自圈内好友 BohuTANG 的博客,原文链接:
https://bohutang.me/2020/06/2…
以下为注释。
21 世纪的第二个 10 年,虎哥曾经在存储引擎一线奋战近 10 年,因为弱小的趣味驱动,这么多年来简直不放过 arXiv 上与存储相干的每一篇 paper。
尤其是看到带有 draft 的 paper 时,有一种乞丐听到“叮当”响时的愉悦。
看 paper 这玩意就像鉴宝,少数是“赝品”,须要你有“鉴真”的本事,否则明天是张三的算法超过 xx,明儿又是王二的硬件晋升了 yy,让你永远跟不上节奏 zz,湮灭在这些没有养分的技术垃圾中,节约大好青春。
言归正传,接下来的 3 篇,跟 ClickHouse 的 MergeTree 引擎无关:
上篇介绍存储引擎的技术演进史,从”远古”的 B-tree 登程推演到目前支流的技术架构。
中篇会从存储构造介绍 MergeTree 原理,对 ClickHouse MergeTree 有一个深刻的意识,如何正当设计来进行迷信减速。
下篇会从 MergeTree 代码登程,看看 ClickHouse MergeTree 如何实现读、写。
本文为上篇,先来个热身,置信本篇大部分内容对大家来说都比拟生疏,很少人写过。
位置
存储引擎 (事务型) 在一个数据库 (DBMS) 中的位置如何呢?
MySQL 的商业胜利能够说大部分来自于 InnoDB 引擎,Oracle 收买 InnoDB 比 MySQL 早好几年呢!
20 年前,能亲手撸一套 ARIES (Algorithms for Recovery and Isolation Exploiting Semantics) 标准引擎,实力还是相当震撼的,置信 Oracle 收买的不仅是 InnoDB 这个引擎,更重要的是人,InnoDB 作者在哪里,在干什么?!
Fork 进去的 MariaDB 这么多年始终找不到本人的灵魂,在 Server 层磨磨蹭蹭堪称是如日方升,只能到处收买碰碰运气,当年 TokuDB 战斗过的 commit 依在,但这些曾经是历史了。
另,WiredTiger 被 MongoDB 收买并应用,对整个生态所起的作用也是无可估计的,这些发动机引擎对于一辆汽车是十分重要的。
有人问道,都曾经 2020 年了,开发一个存储引擎还这么难吗?不难,然而造出来的未必有 RocksDB 好用?!
如大家所见,很多的分布式存储引擎都是基于 RocksDB 研发,堪称短期内还算理智的抉择。
从工程角度来看,一个 ACID 引擎要打磨的货色十分之多,到处充斥着人力、钱力、急躁的耗费,一种可能是写到一半就停滞了(如 nessDB),还有一种可能是写着写着发现跟 xx 很像,沃茨法克。
当然,这里并不是激励大家都去基于 RocksDB 去构建本人的产品,而是要依据本人的状况去做抉择。
B-tree
首先要尊称一声大爷,这个大爷年方 50,目前撑持着数据库产业的半壁江山。
50 年来不变而且人们还没有扭转它的动向,这个大爷厉害的很!
鉴定一个算法的优劣,有一个学派叫 IO 复杂度剖析,简略推演虚实便知。
上面就用此法剖析下 B-tree(traditional b-tree) 的 IO 复杂度,对读、写 IO 高深莫测,真正明确读为什么快,写为什么慢,如何优化。
为了能够欢快的浏览,本文不会做任何公式推导,复杂度剖析怎么可能没有公式呢!
读 IO 剖析
这里有一个 3-level 的 B-tree,每个方块代表一个 page,数字代表 page ID。
上图 B-tree 构造是 内存 的一个表现形式,如果咱们要读取的记录在 leaf- 8 上,read-path 如蓝色箭头所示:
root-9 –> branch-6 –> leaf-8
下图是 B-tree 在 磁盘 上的存储模式,meta page 是终点:
这样读取的随机 IO (假如内存里没有 page 缓存且 page 存储是随机的)总数就是(蓝色箭头):
1(meta-10)IO + 1(root-9)IO + 1(branch-6)IO + 1(leaf-8)IO = 4 次 IO,这里疏忽始终缓存的 meta 和 root,就是 2 次随机 IO。
如果磁盘 seek 是 1ms,读取提早就是 2ms。
通过推演就会发现,B-tree 是一种读优化 (Read-Optimized) 的数据结构,无论 LSM-tree 还是 Fractal-tree 等在读上只能比它慢,因为读放大 (Read Amplification) 问题。
存储引擎算法堪称突飞猛进,然而大部分都是在跟写优化 (Write-Optimized) 做奋斗,那怕是一个常数项的优化那就是冲破,自从 Fractal-tree 冲破后再无来者了!
写 IO 剖析
当初写一条记录到 leaf-8。
能够发现,每次写都须要先读取一遍,如上图蓝色门路所示。
假如这次写入导致 root, branch 都产生了变动,这种 in-place 的更新反映到磁盘上就是:
根本是 2 次读 IO 和写 2 次写 IO+WAL fsync,粗略为 4 次随机 IO。
通过剖析发现,B-tree 对写操作不太敌对,随机 IO 次数较多,而且 in-place 更新必须减少一个 page 级的 WAL 保障失败回滚,几乎是要命。
Write-Optimized B-tree
说到写优化,在机械盘的年代,大家的方向根本是把随机 IO 转换为程序 IO,充分发挥磁盘的机械劣势,于是呈现一种 Append-only B-tree:
- 更新生成新的 page(蓝色)
- page 回写磁盘时 append only 到文件开端
- 无需 page WAL,数据不 overwrite,有写放大 (Write Amplification) 问题,须要做空洞重利用机制
Append-only B-tree 节俭了回写时的 2 次随机 IO,转换为常数级 (constant) 的 1 次程序 IO,写性能大幅晋升,总结起来就是:
随机变程序,空间换工夫
LSM-tree, Fractal-tree 等写优化算法的核心思想也是这个,只不过其实现机制不同。
LSM-trees
随着 LevelDB 的问世,LSM-tree 逐步被大家所熟知。
LSM-tree 更像一种思维,含糊了 B-tree 里 tree 的严肃性,通过文件组织成一个更加涣散的 tree。
这里不谈一个具体的 LSM-tree 是 Leveled 还是 Size-tiered,只谈大体思维。
写入
- 先写入内存的 C0
- 后盾线程依据规定 (Leveled/Sized) 进行 merge,C0 –> C1, C1 –> C2 … CL
- 写入 C0 即可返回,IO 放到后盾的 Merge 过程
- 每次 Merge 是硬伤,动作大就抖,动作小性能不好,每次 Merge 的数据流向不明确
- 写放大问题
读取
- 读取 C0
- 读取 C1 .. CL
- 合并记录返回
- 读放大问题
Fractal-tree
终于倒退到了“终极”优化 (目前最先进的索引算法),Fractal-tree。
它是在 Append-only B-tree 的根底上,对每个 branch 节点减少了一个 message buffer 作为缓冲,能够看做是 LSM-tree 和 Append-only B-tree 完满合体。
绝对于 LSM-tree 它的劣势非常明显:
Merge 更加有序,数据流向十分明显,打消了 Merge 的抖动问题,大家始终寻找的 compaction 防抖计划始终存在的!
这个高科技目前只有 TokuDB 在应用,这个算法能够开篇新介,这里不做累述,感兴趣的能够参考原型实现 nessDB。
Cache-oblivious
这个词对于大部分人都是生疏的,不过别怕。
在存储引擎里,有一个数据结构十分十分重要,它负责 page 数据有序性保护,比方在一个 page 里怎么疾速定位到我要的记录。
在 LevelDB 里应用 skiplist,但大部分引擎应用的是一个有序数组来示意,比方 [1, 2, 3, … 100],而后应用二分查找。
大略 10 年前一位内核开发者发表了一篇 <You’re Doing It Wrong>,这个小文讲了一个很有意思的事件:
数据的组织模式对性能有很大的影响,因为 CPU 有 cache line。
抛开这篇文章不谈,咱们来看一张“神仙”图:
这是一个 binary-tree 的 4 种 layout 示意模式,那么哪种 layout 对 CPU cache line 最敌对?
兴许你曾经猜对了,那就是 van Emde Boas,简称 vEB。
因为它的相邻数据“扎堆”存储,point-query 和 range-query 的 cache line 能够最大化共享,skiplist 对 cache line 是十分不敌对的,还能够更快!
对于 cache oblivious 数据结构,这里有一个简略的原型实现: omt
B-tree 优化魔力象限
写优化算法从原生的 B-tree 到 Append-only B-tree(代表作 LMDB),又到 LSM-tree(LevelDB/RocksDB 等),最初进化到目前最先进的 Fractal-tree (TokuDB)。
这些算法消耗了很多年才在工程上实现并被认可,研发一款存储引擎缺的不是算法而是“鉴宝”的能力,这个“宝”可能曾经躺了几十年了。
其实,”科学家”们曾经总结出一个 B-tree 优化魔力象限:
横坐标是写性能,纵坐标是读性能,B-tree 和 Logging 数据结构散布在曲线的两个极其。
B-tree 的读性能十分好,然而写性能差。
Logging 的写性能十分好,然而读性能差(想想咱们每次写都把数据追加到文件开端,是不是很快?然而读…)。
在它们两头有一个优化曲度(Optimal Curve)。
在这个曲度上,你能够通过减少 / 缩小一个常数 (1-epsilon) 来做读和写优化组合,LSM-tree/Fractal-tree 都在这个曲度之上。
总结
本文次要探讨事务性引擎的技术演进,其中蕴含了 IO 复杂度剖析,其实这个剖析是基于一个 DAM(Disk Access Machine) 模型,这里不再开展。
这个模型要解决什么问题呢?
如果工程中波及硬件层级关系,比方 Disk / Memory / CPU,数据在 Disk,读取 (以 block 为单位) 到 Memory,查找计算 (cache-line) 在 CPU,不同介质间性能差距又十分之大,咱们怎么做能力让整体性能更优的问题。
和当今的硬件相交融,这个模型也一样实用。
最初回到 ClickHouse 的 MergeTree 引擎,它只应用了本文中的局部优化,实现也比拟简洁、高效,毕竟没有事务,撸起来也没啥心理累赘。
随机变程序,空间换工夫,MergeTree 原理,请听下回分解。
References
- [1] Cache-Oblivious Data Structures
- [2] Data Structures and Algorithms for Big Databases
- [3] The buffer tree: A new technique for optimal I/O-algorithms
- [4] how the append-only btree works
- [5] 写优化的数据结构(1):AOF 和 b -tree 之间
- [6] 写优化的数据结构(2):buffered tree
- [7] 存储引擎数据结构优化(1):cpu bound
- [8] 存储引擎数据结构优化(2):io bound
- [9] nessDB
- [10] omt
欢送关注我的微信公众号【数据库内核】:分享支流开源数据库和存储引擎相干技术。
题目 | 网址 |
---|---|
GitHub | https://dbkernel.github.io |
知乎 | https://www.zhihu.com/people/… |
思否(SegmentFault) | https://segmentfault.com/u/db… |
掘金 | https://juejin.im/user/5e9d3e… |
开源中国(oschina) | https://my.oschina.net/dbkernel |
博客园(cnblogs) | https://www.cnblogs.com/dbkernel |