[笔记]数据存储与检索

[注释]数据存储和检索。

数据存储与检索(数据密集型应用系统设计)

如果你把东西整理好，下次就不用找了。

？-德国谚语。

在最基本的层面上，数据库只需要做两件事。

当数据插入其中时，它会保存数据。

查询数据时，应该返回需要的数据。

数据库核心： 数据结构

世界上最简单的数据库。

#!/bin/bash

db _ set(){ 0

echo '$1，$2 '数据库

}

db _ get(){ 0

grep '^$1,'数据库| sed -e 's/^$1,//' | tail -n 1

}

这两个函数实现了键值存储。

$ db _ set 123456 ' { name ' : ' Jack ' } '

$ db _ set 78 ' { ' name ' : ' Amy ' } '

$ db_get 42

{ '姓名' : '艾米' }

它的实现非常简单。当数据库用作存储数据的纯文本文件时，每次调用db_set时，都会在文件的末尾追加新内容。如果一个密钥更新多次，旧版本值不会被覆盖，但需要查看文件中的最后一个密钥才能找到最新值(tail-n ^ 1)。

思考

因为是以追加模式编写的，所以所有db_set函数都有很好的性能，借用了很多数据库使用的日志思想(这里的日志不是运行日志的程序)。另一方面，日志保存了大量的记录，因此db_get函数的性能很差，需要从头到尾扫描，才能找到键出现的最后位置(论复杂度)。

解决

为了有效地在数据库中找到特定的键值对，需要一个新的数据结构：索引。基本思想是保留一些额外的元数据来帮助定位所需的数据。同时，维护索引不可避免地会引入开销，这主要是由于写入数据时和每次写入数据时都需要更新索引。因此，任何类型的索引通常都会降低写入速度。

这涉及到存储系统中的一个重要权衡设计。适当的索引可以加快读取速度，但每个索引都会减慢写入速度。因此，数据库通常不会向所有内容添加索引，这需要开发和数据库管理员手动选择索引，以避免不必要的开销。

哈希索引

大多数编程语言的内置字典结构(哈希映射)非常适合存储键值，例如。

$ db_set张三。

这样，张三的邮箱将保存在数据库文件中，同时在内存中创建一个哈希表电子邮件。当db_set写入时，记录文件的偏移电子邮件['张三']将为0。当多次调用db _ set时，张三的xxxx@163.com是，更新哈希表中的偏移量，使电子邮件['张三']=645，那么每次调用db_get的性能都是一样的。每次在哈希表中第一次找到偏移量时，都会从偏移量的开始处读取，并且在满足结束符号(本例中为逗号)后可以返回结果。

事实上，Bitcast(Riak的默认存储引擎)就是这样一种方法。

思考

如上所述，如何通过只追加一个文件来避免磁盘空间不足？

日志：文件达到一定大小，数据写入新文件。

压缩：丢弃日志中的重复键，只留下最新的键值。

它们经常结合使用。

前一段写入后不会被修改，所以合并压缩可以在后台进程中进行，合并后的段会写入新文件。当程序运行时，老段依然可以正常阅读。合并完成后，读取请求将切换到新的段，旧的段文件可以安全删除。

细节

存储形式

正式存储不是最好的格式。二进制格式更快更简单。长度以字节记录，后跟原始字符串(不需要转义)。

删除记录

删除不是马上删除，而是做一个删除标记(墓碑)。当后台线程合并日志段时，会发现墓碑标记会丢弃该键的所有值。

故障修复

如果数据库重新启动，内存中的hashmap将丢失。您可以从头到尾遍历所有的段文件并重建hashmap，但是重建可能需要很长时间。比特桶传递每个段的散列。

map 快照存储在磁盘上, 可以更快的恢复

SSLTables 和 LSM-Tree

假设文件保存的 key-value 按 key 排序, 称这种格式为 排序字符串表 SSTable, 它要求每个键在每个合并的段文件中只能出现一次(合并段线程已经确保了)

SSTable 对比 哈希索引

优点:

1. 合并段更加简单高效: 并发读取多个输入段文件, 比较每个文件的第一个键, 把最小的键拷贝到输出文件, 重复这个过程, 会产生一个新的按键排序的合并段文件. 如果相同的键出现在多个输入段文件中, 保留最新段的值
2. 在文件中查找特定的键时, 不再需要内存中的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, 表的主键始终是聚集索引, 二级索引引用主键而不是堆文件

聚集索引和非聚集索引有个折中的设计叫索引覆盖, 它在索引中保存这一行数据某个列的值, 它可以支持只通过索引即可回答一些简单的查询, 称这次查询为索引覆盖了查询