xiaohanliang
Database
DatabaseDockerGolangNetworkOS
Database
DatabaseDockerGolangNetworkOS
  • review
  • MySQL
    • 0. 索引就是树吗
    • 1. 索引是怎么发挥作用的
    • 2. 聊聊怎么估时间
    • 3. 主键玄学
    • 4. 事务的执行过程@ACD
    • 5. MVCC就是用undolog回退
    • 6. 事务如何彼此隔离@I
    • 7. 如何人为的制造死锁
    • 8. 引擎是干什么的
    • 9. 主从复制怎么做到的
    • 10. 寻找同步起始点GTID
    • 11. 预解析Statement
  • Redis
    • 0. Hash@数据结构
    • 1. ZSet@数据结构
    • 2. 场景与玩法@数据结构
    • 3. 可能的风险点
    • 4. Redis的落盘
    • 5. 关于效率的讨论
    • 6. 主从模式@集群化
    • 7. [WIP]Proxy实现@集群化
    • 8. 标准玩法@集群化
  • KV/Distributed
    • 0. 面临的问题
    • 1.Raft@原理
    • 2. LSM@原理
    • 3. [WIP]分布式事务@原理
Powered by GitBook
On this page
  • Introduction
  • 磁盘顺序追加的速度
  • 写入 - 怎样实现磁盘追加的效果
  • 读取 - 那么怎样读呢
  • 进一步去优化这个过程:

Was this helpful?

  1. KV/Distributed

2. LSM@原理

Previous1.Raft@原理Next3. [WIP]分布式事务@原理

Last updated 3 years ago

Was this helpful?

Introduction

  • OLTP: 我们日常使用数据库的思路: 存入一行, 取出/更新某一行, 或者按行join, 我们操作的对象, 都是表里的"行", 一行就是一条数据. 因此我们叫它 "Transaction".

  • OLAP: 但如果我们换一条思路, 按列去看. 去统计表里所有人的, 平均年龄这种操作, 那么我们操作的对象就是列, 经常出现在 "统计" 的应用场景里. 因此我们叫它 "Analysis"

一旦明白这种场景上的变化, 我们就能立刻明白, 为什么会有一些 "讳莫如深", "高大上" 的存储组件我们不去用了. 因为我们的确很少做分析嘛, 我们做业务只关心行的数据是否准确, 我们也不统计什么, 我们只会要求实时性高, 精准度足够高的Transaction相关的存储方式, 来获得足够多的精确度.

但对于Analysis, 实时性要求就没那么高了, 因为数据太他妈大了, 多一个多两个根本就无所谓了. 常见的场景: 根据你的操作, 你的一大堆行为日志, 去更新你的用户画像, 那这根本就无所谓的. 所以他们搜索推荐, 或者大数据分析之类的组, 就会要求这种按列存储, 实时性不高, 精准度不高的存储方式. 这些比较奇怪的组件, 主要也是他们在用. 因此我们可以放下MySQL那一套, ACID的精确属性, 进入一种新的模式, 就是精确度没那么大, 写入速度足够大, 然后针对一大票不那么精确的数据去做统计的场景.

我们回想一下innodb的工作模式, 任何写都先写到内存里的buffer, 然后每一次commit的时候fsync到磁盘里, merge进之前的B+树. 这是我们熟悉的工作模式: 但是想想, 如何B+树是怎么Merge进去的? 就算你用id去定位, B+树最后也只能告诉你这在磁盘上的那一页, 然后经历磁盘寻道等等一系列操作前往那一页完成更新操作. 而在这之前这一行总是锁上的, 因此我们会说: "写入的效率, 并不是那么高". 但对应的好处是, B+树在任何时刻下总是处于一种sorted的状态, 因此我们会说B+树读的效率也蛮可观.

磁盘顺序追加的速度

但针对我们上面所说的, 海量数据(就比如说一瞬间能产生一大堆的日志好了), 的写入. 用户画像又不急着更新, 我过段时间更新也完全无所谓, 因此产生了 "请给我快点写, 但读的效率就无所谓慢点就慢点" 这样的需求. 怎样做才能满足这种需求呢? 怎样写的够快? 内存? 我们先看一张著名的图片, 下图有一个颠覆三观的数据, 磁盘顺序追加写入, 速度是非常恐怖的, 而且比内存随机读还要更快.

image-20210812203938429

写入 - 怎样实现磁盘追加的效果

那么如果数据库的写操作, 就用磁盘的顺序写, 这种方式实现的写操作就一定很快, 那么怎样写, 算是磁盘顺序写呢? 日志追加. 假设我们现在已经存了一些数据了, 那么在追加的时候, 我们使用一种类似下图效果的方式实现追加写入:

echo '(add, k1, v1)' >> file
echo '(add, k2, v2)' >> file
echo '(update, k1, v1')' >> file

读取 - 那么怎样读呢

每次一产生修改就继续往后追加, 这样至少是实现了使用顺序写的方式完成数据库的写操作. 但如何读呢 ? 直球的去想, 如果越靠后面的数据就越新, 那么如果我们从文件尾出发向头的位置找, 找到的第一个就是最新的数据. 但是这种方式实际上极其愚蠢, 换句话说, 如果查找一个不存在的key, 需要你从最后面翻到最前面, 才能断言出 "这个key并不存在"

=因此为了实现快速读, 我们需要引入某种 sorted 的结构 , 因为 sorted 查永远比无序快. 使得我们能按照日志追加的模式去写, 并按照 sorted 树的方式去查找. 现在假设我们存在某种数据结构, 处于 sorted 状态, 可以是红黑树, 也可以是跳表. 那么我们假设它是一种树好了, ok 那么我们数据库里所有的数据, 最终都是按照一种树的结构存在着.

**重点** : 那么, 我们首先要把变更记录顺序追加到磁盘上, 最终这个日志文件所象征的全量数据, 还要以sorted树的方式存在着.** 在变更记录产生的时候, 先追加到磁盘上 . 然后将日志里记录的变动Merge到全量树上. 因此很明显的, 日志扮演着一个增量的角色, 树扮演着增量的角色. 查询的时候, 我们也是先查询增量的日志, 后查询全量的树. 为了保证查增量日志的时候, 不至于遍历日志全文, 我们也给增量日志设置一个 "小树", 或者叫 "增量树".

那么此时我们就维护了一个增量日志文件, 以及这个日志文件所对应的小树 (维护在内存里). 每次执行写操作就先写到磁盘上, 再把这条修改记录更新, 并维护到内存里的小树上. (这种顺序的玩法其实就是 Write Ahead Log玩法. 因为要保证重启后依然有效, 而且我们总是有办法从磁盘里的日志文件, 恢复出一个内存里的小树)

这样, 临时文件就变成了一个 日志文件 & 日志文件对应的小树. 后面直接把小树与全量树 Merge在一起, 我们都知道如果两者都是sorted状态, 那么Merge起来会更快. 效果类比 merge sort. 这种merge, 把两段数据压缩在一起的过程我们叫 Compaction. Compaction的过程可以在后台异步完成.

进一步去优化这个过程:

我们在内存里养小树, 等小树大到一定程度Compact到磁盘上的全量树. 想法不错, 但实际落地可能存在一些问题:

  • 小树合大树进行的过程中, 我新的变更请求, 往哪儿写?

    • 正常情况下, 我们直接操作灰色的小树, 一旦发现小树够大了, 它直接变成黑色小树, 然后另起一个灰色的小树. 此时我们在后台负责将黑色的小树Compact进全量树, 而不影响你的写请求, 你继续往灰色小树里写. 那么显然, 黑色小树是只读的, 我们的查找过程也会查到黑色小树.

  • 全量树非常非常大, 即使是MergeSort, 合小树也非常不方便. 有无办法避免碰全量树

    • 上图里的全量树就是1TB大小, 但如何避免碰到全量树就能完成合并? 我们的解决方法是继续在上面放更多的小树. 比如L6层是全量树, L5层就是简化版的L6, 一路往下, 极简到最后变成了L1. 每一层有自己的极限容量: 10M/100M/1G...

    • 每一个白色小方块就是一个小树, 所有小树在一起构成了这一层的所有数据. 小树之间彼此不会相互影响

    • 我们理一下这个过程, 描述一下我们是如何避免碰到全量树的: 每次黑色小树直接变成L0, 然后尝试把原先的L0跟L1进行合并, L0是最新的数据, 里面可能存在一些对L1的更新, 一些插入, 两者Compact成全量汇聚成L1. 一旦L1汇聚完成以后, 发现大小超过了这一层的极限容量, 就会出发L1 → L2层的转移

image-20210813032117092
img
image-20210813032135553