数据存储与检索(数据密集型应用系统设计)
如果你把东西整理得井井有条, 下次就不用查找了
--- 德国谚语
从最基本的层面看, 数据库只需要做两件事情
- 向它插入数据时, 它就保存数据
- 查询数据时, 它应该返回需要的数据
数据库核心: 数据结构
世界上最简单的数据库
#!/bin/bash
db_set() {
echo "$1,$2" >> database
}
db_get() {
grep "^$1," database | sed -e "s/^$1,//" | tail -n 1
}
这两个函数实现了一个 key-value 存储
$ db_set 123456 '{"name":"Jack"}'
$ db_set 78 '{"name":"Amy"}'
$ db_get 42
{"name":"Amy"}
它的实现非常简单, 使用
database
这个纯文本文件存储数据, 每次调用
db_set
就会追加新内容到文件末尾, 如果多次更新某个
key
, 旧版本值不会被覆盖, 而是需要查看文件中最后一次出现的
key
来找到最新的值(
tail -n 1
)
思考
由于是追加方式写入, 所有 db_set 函数性能很好, 里面借用了很多数据库都使用的日志
log
思想(这里的 log 并非程序运行日志), 另一方面 日志 保存了大量的记录, 那么 db_get 函数性能非常差, 需要从头扫描到尾部来查找 key 出现的最后位置(On 复杂度)
解决
为了高效的查找数据库中特定的键值对, 需要新的数据结构: 索引, 基本思想是保留一些额外的元数据, 帮助定位想要的数据. 同时, 维护索引势必会引入开销, 主要在数据写入时, 每次写入数据时, 需要更新索引, 因此任何类型的索引通常都会降低写的速度
这里涉及到存储系统中重要的权衡设计: 适当的索引可以加速读取, 但每个索引都会减慢写速度, 所以数据库通常不会对所有内容添加索引, 需要开发和数据库管理员手动选择索引, 避免不必要的开销
哈希索引
大多数编程语言内置的字典结构(hash map)非常适合存储 key-value, 例如
$ db_set 张三 [email protected]
这样会将张三的邮箱保存到
database
文件中, 同时在内存中创建一个哈希表 emails, db_set 写入时, 记录文件的偏移量 emails["张三"] = 0, 当多次调用
db_set 张三 [email protected]
是, 更新 哈希表中的偏移量即可 emails["张三"] = 645, 那么对于每次调用 db_get 来说, 性能是相同的, 每次先到哈希表中查找到偏移量, 从偏移量开始地方读取, 遇到结束符号(本例子中是 逗号)结束即可返回结果.
事实上, Bitcask (Riak 的默认存储引擎) 就是采用的这种做法
思考
如上所述, 只追加到一个文件, 如何避免用尽磁盘空间
- 日志分段: 文件到达一定大小, 数据写入新的文件
- 压缩: 在日志中丢弃重复的键, 只保留最新的 key-value
- 往往两者结合使用
以前的段在写入后不会再进行修改, 所以合并压缩可以在后台进程进行, 合并后的段会写入一个新的文件, 而且程序运行时, 旧的段依然可以正常读取, 合并完成后, 读取请求会切换到新的段上, 旧的段文件可以安全删除
细节
- 文件格式
- 文本形式存储不是最佳格式, 二进制格式更快更简单, 以字节记录长度, 之后跟上原始字符串(都不需要转义)
- 删除记录
- 删除不是立即删除, 而是做一个删除标记(墓碑), 当后台线程合并日志段时, 发现墓碑标记则丢弃这个键的所有值
- 崩溃恢复
- 如果数据库重启, 内存中的 hashmap 会丢失, 可以从头到尾遍历所有段文件, 重建 hashmap, 但是可能会重建很长时间, Bitcask 通过将每个段的 hashmap 快照存储在磁盘上, 可以更快的恢复
- 部分写入
- 追加到日志的过程中如果发生崩溃, 可以设置文件校验值来发现损坏部分并丢弃
- 并发控制
- 由于日志写入需要有严格的先后顺序, 通常只会有一个写线程, 读取可以有多个线程
- 为什么采用追加写 . 而不是覆盖写
- 顺序写比随机写快很多
- 并发控制和崩溃恢复实现起来简单, 防止覆盖写时候发生崩溃数据丢失
- 长时间运行不会出现碎片化问题
- 缺点
- 不支持区间查询
- 数据大时, 哈希表占用大量内存空间, 也会更容易发生哈希冲突
SSLTables 和 LSM-Tree
假设文件保存的 key-value 按 key 排序, 称这种格式为 排序字符串表 SSTable, 它要求每个键在每个合并的段文件中只能出现一次(合并段线程已经确保了)
SSTable 对比 哈希索引
优点:
- 合并段更加简单高效: 并发读取多个输入段文件, 比较每个文件的第一个键, 把最小的键拷贝到输出文件, 重复这个过程, 会产生一个新的按键排序的合并段文件. 如果相同的键出现在多个输入段文件中, 保留最新段的值
- 在文件中查找特定的键时, 不再需要内存中的hashmap, 假设查找 abc 的 value, 且不知道hashmap 没有记录 abc 具体的偏移量, 只记录了偏移量 aba = 100 字节 和 abd = 150 字节 , 那么可以直接跳到文件 100 字节开始扫描, 在150 字节扫描终止, 虽然仍然需要 hashmap 记录某些键的便宜, 但它是可以稀疏的, 并不需要每个键都记录, 这样可以很快在内存存放很多 key 的偏移量, 将 key 的快照保存在磁盘中, 也节省了空间和 io 次数
以上描述的算法本质上是 LevelDB 和 RocksDB 所使用的, 以合并日志树LSM-Tree 命名
在海量数据中 , LSM-Tree 查找某个不存在的 key 时候可能很慢(先检查内存表, 然后加载磁盘上的段文件, 在区间内寻找). 为了优化这种访问, 通常会使用布隆过滤器
LSM 的方式可以有效的执行区间查询, 并且磁盘是顺序写入的, 可以支持非常高的写入吞吐量
B-trees
虽然上面讨论的日志结构索引正在逐渐接受认可, 但使用最广泛的是 B-tree
像 SSTable 一样, B-tree 保留按键排序的特征, 这样可以实现高效的 key-value 查询和区间查询, B-tree 将数据库分解成固定大小的块或者页, 一般为 4KB, 页是数据库内部读写的最小单元, 这种设计更接近底层硬件, 因为磁盘也是按固定大小的排列
每个页可以使用地址进行标识, 这样可以让一个页引用另一个页. 类似指针, 不过指向的是磁盘地址.
例如:
某一页为 B-tree 的根, 每当查找 key 时, 总是从根开始, 页面包含若干个 key 和子页的地址, 每个子页都负责一个连续范围内的 key
假设查找 251, 因此从根上可以知道沿着 200 ~ 300 页之间的子页上查找, 找到第三层 250 ~ 270 之间, 然后来到第四层, 从开头遍历到 251, 获取到对应的 val
如果遇到更新操作, 首先搜索包含该 key 子页, 然后更改对应 key 的 val, 并将这一页写回到磁盘, 因为其他页式引用的地址而不是拷贝, 所以写会磁盘后, 对其他引用到这个页的子页也是生效的
如果遇到新增操作, 需要找到包含新的 key 的子页, 并将其添加到该页, 如果这个页没有空间容纳新键, 则将其分裂为两个半满的页, 并且父页也需要更新
具有 n 个键的 B-tree 总是具有 O(logn) 的深度, 大多数数据库适合 3~4 层的 B-tree, 因此不需要遍历非常深即可找到所需的页, 每层为 500 的 4KB 页的四级树可以存储 256TB
思考
如果插入时候发生页分裂, 那么需要写入磁盘两个分裂的页, 假如数据库完成部分页的写入之后发生崩溃, 会导致索引被破坏(存在一个孤儿页, 没有任何其他页指向它), 为了能在崩溃中恢复, 会采用预写日志(write-ahead log, WAL), 也叫重做日志, 这是一个仅支持追加修改的文件, 每个 B-tree 必须先更新 WAL 然后再修改树本身的页, 当数据库崩溃需要恢复时, 改日志用于将 B-tree 恢复到最近一致状态
索引中存的是什么
- 可以实际行, 也可以是对其他地方存储的行的引用,如果是行的引用, 那么行具体所在的位置为堆文件. 堆文件方法比较常见, 当存在多个二级索引时, 可以避免复制数据, 每个索引只引用堆文件的位置, 实际堆文件保存在另一个位置, 当更新值而不是添加新键时, 这个方法非常高效
- 某些情况下, 从索引查找到堆文件对应的行, 然后跳转过去读取意味着太多的性能损失, 希望将这一行数据直接保存在索引中, 称为聚集索引, 例如 Mysql InnoDB, 表的主键始终是聚集索引, 二级索引引用主键而不是堆文件