分布式数据库30讲
王磊
光大银行首席数据架构师
新⼈⾸单¥19.9
2412 人已学习
课程目录
已更新 24 讲 / 共 33 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词|为什么要学习分布式数据库?
免费
基础篇 (8讲)
01|什么是分布式数据库?
02|强一致性:那么多数据一致性模型,究竟有啥不一样?
03|强一致性:别再用BASE做借口,来看看什么是真正的事务一致性
04 | 架构风格:NewSQL和PGXC到底有啥不一样?
05 | 全局时钟:物理时钟和逻辑时钟你Pick谁?
06 | 分片机制:为什么说Range是更好的分片策略?
07 | 数据复制:为什么有时候Paxos不是最佳选择?
08 | 基础篇大串讲:重难点回顾+思考题答疑+知识全景图
开发篇 (15讲)
09|原子性:2PC还是原子性协议的王者吗?
10 | 原子性:如何打破事务高延迟的魔咒?
11|隔离性:读写冲突时,快照是最好的办法吗?
12 | 隔离性:看不见的读写冲突,要怎么处理?
13 | 隔离性:为什么使用乐观协议的分布式数据库越来越少?
14 | 隔离性:实现悲观协议,除了锁还有别的办法吗?
15 | 分布式事务串讲:重难点回顾+思考题答疑+知识全景图
16 | 为什么不建议你使用存储过程?
17 | 为什么不建议你使用自增主键?
18 | HTAP是不是赢者通吃的游戏?
19 | 查询性能优化:计算与存储分离架构下有哪些优化思路?
20 | 关联查询:如何提升多表Join能力?
21 | 查询执行引擎:如何让聚合计算加速?
22|RUM猜想:想要读写快还是存储省?又是三选二
23 | 数据库查询串讲:重难点回顾+思考题答疑+知识全景图
分布式数据库30讲
15
15
1.0x
00:00/00:00
登录|注册

22|RUM猜想:想要读写快还是存储省?又是三选二

王磊 2020-09-28
你好,我是王磊。
从第 18 讲,我们开始介绍查询过程中全部重要节点的相关技术,从并行框架到查询执行引擎,再从关联运算符到行式和列式存储。今天这一讲我们面临最后的一个步骤,直接和磁盘打交道,实现最终的数据存储,这就是存储引擎。

RUM 猜想

说到数据存储,我相信很多人都有一种直觉,那就是读写两种操作的优化在很多时候是互斥的。
我们可以想一下,数据以什么形式存储,可以实现最快的写入速度?答案肯定是按照顺序写入,每次新增数据都追加在文件尾部,因为这样物理磁盘的磁头移动距离最小。
但这种方式对于读取显然是不友好的,因为没有任何有意义的数据结构做辅助,读操作必须从头到尾扫描文件。反过来,如果要实现更高效的读取,就要设计更复杂的数据结构,那么写入的速度当然就降低了,同时在存储空间上也会有额外的要求。
2016 年的一篇论文将我们这种朴素的理解提升到理论层面,这就是 RUM 猜想。RUM 猜想来自论文“Designing Access Methods: The RUM Conjecture”(Manos Athanassoulis et al.(2016)),同时被 SIGMOD 和 EDBT 收录。它说的是,对任何数据结构来说,在 Read Overhead(读)、Update Overhead(写) 和 Memory or Storage Overhead(存储) 中,同时优化两项时,需要以另一项劣化作为代价。论文用一幅图展示了常见数据结构在这三个优化方向中的位置,这里我摘录下来便于你理解。
确认放弃笔记?
放弃后所记笔记将不保留。
新功能上线,你的历史笔记已初始化为私密笔记,是否一键批量公开?
批量公开的笔记不会为你同步至部落
公开
同步至部落
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《分布式数据库30讲》,如需阅读全部文章,
请订阅文章所属专栏新⼈⾸单¥19.9
立即订阅
登录 后留言

精选留言(7)

  • piboye
    即使不是前缀相同,范围查询也可以一个一个key去尝试,bf是内存操作,还是比磁盘快吧

    作者回复: 首先范围查询可能是无法穷举的,例如对浮点数的范围查询。另外即使可以穷举,每个都查的时间复杂度就是O(N)了,而磁盘文件是有序的,加上磁盘会做预取,可能还是磁盘快些。

    2020-09-28
    1
  • Jxin
    课后题:
    这样问,那就一定是可以了。但很遗憾,能力有限想不到。scan了的话,如果是常规的行式存储,bf起不到作用,毕竟边界不存在不等于边界内部不存在。

    22讲下来的感觉:
    有种搭建空中楼阁的感觉,费力还容易忘。这篇专栏前边,其实最好有篇实战做铺垫,比如tidb。两相验证虚实结合才能学得扎实。

    作者回复: 嗯,谢谢,你的建议很中肯。因为这个专栏是中立视角,希望跳出某个具体的产品,讲一些共性的、原理层面的研究进展,然后选择有代表性的产品做一些映射。这样一来,所有的内容就不能与某一款产品完全匹配,会有些抽象,但我相信后面一定会有更多分布式数据库的课程作为补充,做到虚实结合。

    2020-09-28
    1
  • 扩散性百万咸面包
    思考题:
    使用Bloom Filter的改造版,现在不用来判断某个key是否不存在,而判断某个key的前缀是否不存在。比如说我要查300-000 到 300-999的区间,那么他们拥有共同前缀300,我只要判断这个前缀是不是在当前SSTable里即可。

    作者回复: 说的全中,点赞。

    2020-09-28
    1
  • licl1008
    想问一下 写放大和空间放大具体有啥区别 写得多了不是磁盘空间就占用更多了吗?
    2020-09-28
  • piboye
    lsm最核心的是顺序写特性,即使写放大和b+一样大,因为顺序写比随机写还是快很多。写放大和空间放大比较影响ssd的寿命。
    2020-09-28
  • 有铭
    为什么RUM是个猜想而不是个定论呢?这东西第一眼看上去好像CAP理论,不过CAP已经被证明了
    2020-09-28
  • 可怜大灰狼
    数据块里是按照顺序存储了很多条数据。我想对数据块建立一级布隆过滤器实例,这样scan定位起始和终止对应的数据块,应该能提速不少。
    如果把数据块按照大小分级,类似LSM的level层那样。是不是会更快些?

    作者回复: 说的很好,点赞。

    2020-09-28
收起评论
7
返回
顶部