22|RUM猜想:想要读写快还是存储省?又是三选二
该思维导图由 AI 生成,仅供参考
RUM 猜想
- 深入了解
- 翻译
- 解释
- 总结
本文深入探讨了数据存储优化的相关观点,重点分析了B+Tree和LSM-Tree两种存储结构在读写存储方面的优劣。文章指出B+Tree适合读操作优化,但在面对大量随机写时会导致存储碎片化和写放大;而LSM-Tree通过将随机写转换为顺序写,提升了写入性能,但却带来了更多的写放大和空间放大。此外,文章还介绍了Leveled策略在LSM-Tree中的应用,以及分布式数据库中的存储结构实现。另外,文章还提到了OceanBase和WiscKey等存储优化的方法。最后,文章还介绍了TiDB和CockroachDB分别推出的自己的单机存储引擎TiTan和Pebble。整体来看,本文通过对比分析不同存储结构在读写存储方面的特点和适用场景,为读者提供了深入了解数据存储优化的视角。文章内容丰富,涉及了存储引擎的工程原因、存储模型的选择、以及存储优化的方法,对于对存储引擎和数据存储优化感兴趣的读者具有很高的参考价值。
《分布式数据库 30 讲》,新⼈⾸单¥59
全部留言(13)
- 最新
- 精选
- 扩散性百万咸面包思考题: 使用Bloom Filter的改造版,现在不用来判断某个key是否不存在,而判断某个key的前缀是否不存在。比如说我要查300-000 到 300-999的区间,那么他们拥有共同前缀300,我只要判断这个前缀是不是在当前SSTable里即可。
作者回复: 说的全中,点赞。
2020-09-2811 - Jxin课后题: 这样问,那就一定是可以了。但很遗憾,能力有限想不到。scan了的话,如果是常规的行式存储,bf起不到作用,毕竟边界不存在不等于边界内部不存在。 22讲下来的感觉: 有种搭建空中楼阁的感觉,费力还容易忘。这篇专栏前边,其实最好有篇实战做铺垫,比如tidb。两相验证虚实结合才能学得扎实。
作者回复: 嗯,谢谢,你的建议很中肯。因为这个专栏是中立视角,希望跳出某个具体的产品,讲一些共性的、原理层面的研究进展,然后选择有代表性的产品做一些映射。这样一来,所有的内容就不能与某一款产品完全匹配,会有些抽象,但我相信后面一定会有更多分布式数据库的课程作为补充,做到虚实结合。
2020-09-2823 - James想问下老师,就是我查一个键值对的时候,对于L1 往后的层级我是怎么找到对应的key的,我看图中画的是很多个区间,是去顺序遍历一遍这些区间,然后去对应的区间找元素吗(在区间内是通过调表算法来找元素的),还是说用二分法这类的算法来找到是哪个区间呢。PS:这个区间是可以不连续的吧(只要不重合就行),比如[a,b) [e,f]
作者回复: 从L1开始,每层的SSTable的Key值范围是不重叠的。所以简单来说,我们会每次通过文件的区间信息锁定一个文件,也就是当前Key所在的区间,然后在文件内部查找,如果没有对应的数据则继续向L2层查找,如此逐层向下,最终找到Key的对应键值对,或者确定不存在对应数据。
2021-01-2522 - kylexy_0817NewSQL的存储数据结构和策略和ES的十分相似。ES确实不是数据库,它不具备数据库应有的特性,例如事务等。之前的留言不严谨😄
作者回复: :)
2020-11-111 - licl1008想问一下 写放大和空间放大具体有啥区别 写得多了不是磁盘空间就占用更多了吗?
作者回复: 写入同样数据,空间占用也会有区别。这主要和增量数据的存储模式有关,比如直接update空间就小些,而转换为delete加insert空间就大些。
2020-09-281 - piboye即使不是前缀相同,范围查询也可以一个一个key去尝试,bf是内存操作,还是比磁盘快吧
作者回复: 首先范围查询可能是无法穷举的,例如对浮点数的范围查询。另外即使可以穷举,每个都查的时间复杂度就是O(N)了,而磁盘文件是有序的,加上磁盘会做预取,可能还是磁盘快些。
2020-09-281 - sanstyleL0 中的 key 是交叉的,所以读取 L0 的所有 SSTable 写入 L1,来保证 L1 开始的 SSTable 都是 key 不重叠的。 在 L1 划分边界的时候,[e, k) 里面是有交叉 key 的,重新划分为 [e, f), [f, k),怎么保证这两个 SSTable 不交叉?
作者回复: 就是在数据誊写(也就是compact)的过程中,控制每个文件写入的数据与边界相符。
2021-05-12 - JacksonCockroachDB 也推出了自己的存储引擎 Pebble,主要目的是解决工程问题,包括解决 CGo barrier 问题和避免 Rust 功能膨胀带来的变更风险。—— Rust应该是Rocksdb吧?笔误?
作者回复: 应该是Rocksdb,看得很仔细
2021-04-24 - 可怜大灰狼数据块里是按照顺序存储了很多条数据。我想对数据块建立一级布隆过滤器实例,这样scan定位起始和终止对应的数据块,应该能提速不少。 如果把数据块按照大小分级,类似LSM的level层那样。是不是会更快些?
作者回复: 说的很好,点赞。
2020-09-28 - 有铭为什么RUM是个猜想而不是个定论呢?这东西第一眼看上去好像CAP理论,不过CAP已经被证明了2020-09-284