《数据密集型应用系统设计》整理02

第三章 数据存储与检索

If you keep things tidily ordered, you're just too lazy to go searching.
—German proverb

分为面向日志结构的存储引擎和面向页的存储引擎。

面向日志结构的存储

顺序追加日志,哈希索引

以日志追加的方式存储数据,其索引使用内存中的hash map,存储每个键在数据文件中特定的字节偏移量。定时采用该日止压缩的方式来减轻磁盘的负担。使用的时候需要考虑以下几个问题:

  • 文件格式使用二进制
  • 删除的时候追加删除flag
  • 崩溃恢复:加载每个段的快照
  • 部分写入:文件包括校验值可以教研
  • 并发控制:单线程写,多线程读

哈希表索引的缺点:键过多的时候内存装不下需要在磁盘上维护。区间查询效率不高。为了解决这些缺点引入了SSTables和LSM-Tree。

SSTable(Sorted String Table)

段文件格式要求key-value对的顺序按键排序。

  • 合并段更加简单高效:并发读多个段文件,对比第一个键即可
  • 还是需要内存索引保存键的偏移,但是可以是稀疏的
  • 可以分块压缩提高I/O效率
  • 段文件使用内存表维护:AVL树或者红黑树,维护着按键排序的key-value对
    • 写入内存中的平衡树
    • 内存表大于阈值的时候写入磁盘
    • 查找的时候先在内存表查找,然后是最新的磁盘段文件,然后是次新的次判段文件,以此类推
  • 这种基于合并和压缩排序文件原理的存储引擎称为LSM(Log-Structured Merge-Tree)存储引擎
  • 优化:当键不存在的时候需要追溯到最旧的段文件,这时候可以用布隆过滤器,通过一组相互独立的哈希函数来用较少的内存标识一系列的数据是否存在,对于不存在的情况不会误判,但是对于存在的情况会有错误情况。

B-trees

最广泛的索引结构。
保留建值排序的索引结构。将数据库分解为固定大小的页或块。
WechatIMG1-1
每个页面可以使用地址或者位置标识,让一个页引用另一个页面。某一页被指定为根,查找的时候从这里开始,每个页面都包含了若干个键和对子页对引用。每个孩子负责一个连续范围内的键,相邻引用之间的键可以指示这些范围之间的边界。

  • 写操作使用原地更新:使用新数据覆盖磁盘上的旧页,假设覆盖不会改变页的磁盘存储位置(如果更改了则需要修改父页)
  • 崩溃恢复使用WAL,每个B-trees的修改必须先更新WAL再修改树本身的页
  • 一些优化:
    • 一些数据库不采用覆盖页和WAL,而使用写时复制。修改的页被写入不同的位置,父页的新版本被创建,并指向新的位置
    • 保存键的缩略信息
    • 相邻叶子叶按顺序保存在磁盘上
    • 添加额外的指针,比如指向兄弟的指针
  • B-trees对比LSM:前者读取更快,后者写入更快
    • LSM优点:顺序写,不需要重写树中的多个页
    • LSM缺点:压缩操作耗费磁盘资源
    • B-trees的优点:每个键都恰好唯一对应索引中的某个位置,在许多关系型数据库中,事务隔离是通过键范围上的锁来实现的

其他

  • 聚集索引:将索引行直接存储在索引中
  • 多维索引
  • 全文搜索和模糊索引:支持对一个单词以及同义词进行查询,忽略单词语法上的变体
    • 比如在Lucence中,内存中的索引是键中的字符序列的有限状态自动机,这个自动机可以转换为Levenshtein自动机,可以支持在给定编辑距离内高校搜索单词
  • 内存索引:其性能优势并不是因为他们不需要从磁盘读取,(如果有足够的内存,则操作系统会将最近使用的磁盘快缓存在内存中),而是因为避免使用写磁盘的格式对内存数据结构编码的开销。

事务处理与分析处理

OLTP(online transaction processing):交互式访问,事务处理
OLAP(online analytic processing):数据分析

属性 OLTP OLAP
主要读特征 基于键,每次返回少量数据 对大量数据进行汇总
主要写特征 随机访问,低延迟写入用户的输入 批量导入(ETL)或事件流
典型应用场景 终端用户,通过网络应用程序 内部分析师,为决策提供支持
数据表征 最新的数据状态 随着时间而变化的所有事件历史
数据规模 GB到TB TB到PB

数据仓库

从OLTP数据库中提取数据,转换为分析友好的模式,执行必要的清理,加载到数据仓库中,称为ETL(Extract-Transform-Load)过程。
WechatIMG2

星型和雪花型分析模式

WechatIMG3

列式存储

面向行的存储引擎会将所有行从磁盘加载到内存中,解析病过滤出不符合所需条件的行。
面向列的想法很简单:不要讲一行中的所有值存储在一起,而是将每列中的所有值存储在一起,查询只需读取和解析在该查询中使用的那些列。
WechatIMG4

列压缩

n非常小的时候:由位图来对应列中每个不同的值,一个位对应一行
n非常大的时候:在位图的基础上使用游程编码
WechatIMG5

数据立方体与物化视图

物化数据立方体:预先计算出来并写入磁盘。

comments powered by Disqus