《数据密集型应用系统设计》读书笔记整理(3)-- 数据存储与检索


如果你把东西整理得井井有条,下次就不用查找了。
——德国谚语

索引是基于原始数据派生来的额外数据结构。维护额外的结构会引入新的开销,特别是数据写入的时候。

带哈希索引的日志数据库

哈希索引的日志段

将key-value对顺序存入段文件中,段文件到达一定大小就关闭它,后续写入到新的段文件中。然后定期对段文件执行压缩和合并。
在查找时,把内存中哈希索引的每个键映射到数据段文件中特定的字节偏移量,从而找到值的位置。

优势:

  • 追加和分段合并主要是顺序写,它通常比随机写入快得多。
  • 如果段文件是追加的或不可变的,并发和崩溃恢复要简单得多。
  • 合并旧段可以避免随着时间推移数据文件出现碎片化的问题。

劣势:

  • 哈希表必须全部放入内存,如果有大量的键,哈希冲突会变多。
  • 区间查询效率不高。

SSTables和LSM-Tree

SSTables

将日志数据库的key-value对顺序进行按键排序,这种格式称为排序字符串表,简称为SSTable(Sorted Strings Table)。

SSTable相比哈希索引的日志段,优势:

  • 合并段更加简单高效。
  • 在文件中查找特定的键时,不再需要在内存中保存所有键的索引,哈希索引可以变稀疏。
构建和维护SSTables

基本工作流程:

  1. 写入时,添加到内存中的平衡树结构中,也叫内存表。
  2. 内存表大于某个阈值时,将其作为SSTable文件写入磁盘。新的SSTable文件成为数据库的最新部分。
  3. 处理读请求时,先在内存中查找键,然后是最新的磁盘段文件,接下来是老的磁盘段文件。
  4. 后台进程周期性地执行段合并与压缩过程,合并多个段文件。

上面的流程可以良好地工作。但还存在问题,如果数据库崩溃,最近还在内存的写入会丢失。可以在磁盘上保留单独的日志,每个写入立即追加到此日志上(不需要按键排序)。在崩溃之后通过此日志来恢复内存表。内存表写入SSTable后,日志可以被丢弃。

LSM-Tree

基于合并和压缩排序文件原理的存储引擎通常被称为LSM(Log-Structured Merge-Tree,或LSM-Tree)存储引擎。
上面描述的算法本质上正是LevelDB和RocksDB使用的。Lucene索引引擎也采用了类似的方法来保存其词典。

段文件压缩和合并的策略有:分层压缩和大小分级。LevelDB和RocksDB使用分层压缩,HBase使用大小分级,Cassandra同时支持两种。

LSM-Tree的基本思想(保存在后台合并多一系列SSTable)简单有效:

  • 数据集合远大于内存,仍可以正常工作。
  • 数据按排序存储,可有效执行区间查询。
  • 磁盘是顺序写入的,LSM-Tree可以支持非常高的写入量。

B-Tree

概述

B-Tree存储着按键排序的key-value对,同样可以实现高效的key-value查找和区间查询。B-Tree中一个页包含的子页引用数量称为分支因子。

B-Tree底层的基本写操作是使用新数据覆盖磁盘上的旧页。而LSM-Tree仅追加更新文件,但不会修改文件。

如果插入导致页溢出,需要分裂页,需要写两个分裂的页,同时更新父页对两个子页的引用。此过程被影响的话,可能会导致索引被破坏,可能会产生孤儿页。

为了从崩溃中恢复,B-Tree需要预写日志(write-ahead log,WAL),也叫重做日志。此日志只进行追加修改,先更新WAL再修改树本身的页,数据库在崩溃后恢复时,该日志用来将B-Tree恢复到最近一致的状态。

原地更新需要注意并发控制,通常需要用锁来保护树结构更新完成。而日志结构化在后台执行所有合并,不会干扰前端的查询,并会用新段原子地替换旧段。

一些B-Tree的优化方案:

  • 一些数据库(如LMDB)不使用覆盖页和维护WAL来进行崩溃恢复,而是使用写时复制方案。修改的页被写入不同的位置,树中父页新版本被创建,并指向新的位置,这种方式对并发控制也有帮助。
  • 保存键的缩略信息,而不是完整的键,节省页空间。特别是在树中间的页中,只提供足够的信息来描述键的起止范围。这样可以将更多的键压入到页中,让树具有更高的分支因子,从而减少层数。例如B+Tree 使相邻的叶子页按顺序保存在磁盘上。
  • 添加额外的指针到树中。例如,叶子页可以向左和右引用其同级的兄弟页,这样可以顺序扫描键,而不用跳回到父页。例如B+Tree

对比B-Tree和LSM-Tree

LSM-Tree优点

  • LSM-Tree通常可以承受比B-Tree更高的写入吞吐量。部分原因是它们有时具有较低的写放大,部分原因是它们以顺序方式写入紧凑的SSTable文件,而不必像B-Tree写入多次(B-Tree一次写入WAL,一次写入树,还可能发生页分裂)。
  • LSM-Tree可以更好地支持压缩和重写以消除碎片化,因此通常磁盘的文件比B-Tree小。

LSM-Tree缺点

  • 由于磁盘的并发资源有限,日志结构存储压缩有时会干扰到正在进行读写的操作,如果观察较高的响应时间的百分位数,有时日志结构化存储的查询时间会相当高,而B-Tree的响应时间更具确定性。
  • LSM-Tree的数据量越大,压缩所需的磁盘带宽就越大。在高写入量的情况下,有可能造成压缩跟不上写入速率。
  • B-Tree的优点是每个键都唯一对应于索引中的某个位置,而LSM-Tree可能在不同的段文件中具有相同键的多个副本。如果数据库需要支持事务,B-Tree会更合适:事务隔离对索引上键的锁可直接定义到树中。

其它索引结构

将索引的行数据(堆文件)直接存储在索引中,称为聚集索引(或聚簇索引)。二级索引引用聚集索引或堆文件。
一种折中设计称为覆盖索引或包含列的索引,在索引中保存一些表的列值,它通过索引可直接覆盖某些简单查询。

多维索引适用于一次范围查询多列,例如地理空间数据。

内存数据库

内存数据库通过特殊的硬件(如电池供电的内存),或通过将更改记录写入磁盘,或定期将快照写入磁盘,以及复制内存中的状态到其它机器等方式来实现持久化。

尽管写入磁盘,但仅是为了持久性目的追加日志,读取完全靠内存服务。

例如VoltDB、MemSQL和Oracle TimesTen是具有关系模型的内存数据库。RAMCloud是一个具有持久性的内存key-value存储。Redis和Couchbase通过异步写入磁盘提供较弱的持久性。

与直觉相反,内存数据库的优势并不是因为它们不需要从磁盘读取。如果有足够的内存,即使是基于磁盘的存储引擎,也可能永远不需要从磁盘读取,因为操作系统会将最近使用的磁盘块缓存在内存中。内存数据库可以更快,是因为它们避免使用写磁盘的格式对内存数据结构编码的开销。

除了性能之外,内存数据库提供了基于磁盘索引难以实现的某些数据模型。例如Redis为各种数据结构(如优先级队列和集合)提供了类似数据库的访问接口。由于所有的数据结构保存在内存中,所以实现可以比较简单。

事务处理与分析处理

在线服务应用程序通常使用索引中的某些键查找少量记录,根据用户的输入插入或更新记录。因为这些应用程序是交互式的,所以访问模式被称为在线事务处理(OnLine Transaction Processing,OLTP)。

而数据的分析查询需要扫描大量记录,并计算汇总统计信息,以形成有助于公司管理层更好决策(商业智能)的报告,称之为在线分析处理(OnLine Analytic Processing,OLAP)。

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

表:对比事务处理与分析处理系统的主要特性

一般OLAP使用单独的数据库,称为数据仓库。将数据导入数据仓库的过程称为提取-转换-加载(Extract-Transform-Load,ETL)。前半部分讨论的索引算法适合OLTP,但不擅长应对分析查询。

很多数据仓库使用了星型模式,也称为维度建模,一般由事实表和维度表组成。雪花模式是星型模式的变体,维度进一步细分为子空间。

一般数据仓库中事实表有几十上百行,而查询往往一次只访问其中的某几行,列存储可以提高数据查找效率。

每个列紧凑存储在一个单独的文件中,查询只需要读取和解析在该查询中使用的那些列,可以节省很多工作。同时面向列的存储很适合压缩,一种有效的压缩技术是位图编码。

另外可以通过物化视图来缓存一些聚合函数的结果提升查询效率。


参考文献:
[1] (美)Martin Kleppmann. 数据密集型应用系统设计(赵军平,吕云松,耿煜,李三平 译)[M]. 北京:中国电力出版社,2018.

Published

Author

Levin

Category

Web Arch

Tags

web arch database book report
Disqus loading now...