上一篇(ch.1)

下一篇(ch.5)

第三章 数据存储与检索

SSTable

存储有序不可变键值对；排序字符串表

要求每个键在每个压缩合并的段文件中只出现一次；

优点

  1. 合并段更加简单高效：即使文件大于可用内存，也可以通过类似于合并排序算法的方式并发读取多个输入段文件。比较每个文件的第一个键，把最小的键（按照排序顺序）复制到输出文件。遇到重复的键时，保留最新的键（每个段是在某个时间段内追加写入键，因此不同段的时间一定有差别，可以根据时间判断键的新旧），重复直到合并完成；

  2. 查找特定键的高效性：在文件内查找特定的键时，不需要额外维护所有键的索引，因为文件本身已经有序。仅需要建立稀疏的索引，按照压缩段为单位建立索引，直接遍历段内即可。注意：当键值对（KV）具有固定大小时，可以通过二分查找，这样就不需要索引。但通常 KV 是可变大小的，所以需要一定程度上的索引来确定单个记录的起始与结尾；

在磁盘上维护排序结构

  • 磁盘 B-trees：用于大规模数据存储的平衡树结构；
  • 内存：红黑树、AVL 树：在内存中使用的平衡二叉树；

存储引擎的基本工作流程

  1. 写入时：将键值对添加到内存中的平衡树结构（又称内存表）；
  2. 内存表大小超阈值时：当内存表超过阈值（一般 <10MB），将其作为 SSTable 文件写入磁盘。SSTable 刷进磁盘的同时，可以向新的 SSTable 实例写入新的键值对；
  3. 读请求：先在内存表中查找键，然后按照时间从新到旧的顺序查找对应的磁盘段文件，直到找到目标或判定为不存在；
  4. 后台压缩合并：后台进程周期性压缩合并段文件，回收被删除或覆盖的旧键值对；

数据库宕机后的经典问题

  由于内存数据全丢失，存储引擎使用 WAL（预写日志）机制。写入操作会先持久化为日志，日志主要是为了防止数据丢失，不需要维护顺序；

LSM-Tree

   SSTable 是 LSM-Tree 的基础存储格式；通过将需要写入的数据先写入内存（通常是平衡树），再批量写入磁盘，形成不可变的 SSTable 文件；

  牺牲一定的读性能换取写性能大幅提升；

  业界上的应用如：Hbase、Cassandra、LevelDB等；

合并：

  合并不同层级的 SSTable 文件以优化存储空间和查询效率，对多个 SSTable 文件进行合并和去重。

LSM-Tree vs B-Tree

LSM-Tree 的优点

  1. 写入效率：B-tree 需要至少两次写入：一次写入预写日志，另一次写入树的页（如果发生页分裂，则需要更多写入）；而 LSM-tree 以顺序方式写入紧凑的 SSTable 文件，不必重写树的多个页，从而降低了写放大；
  2. 压缩能力：LSM-Tree 的存储空间利用率更高；B-tree 的存储页中可能存在碎片，而 LSM-tree 会通过定期重写 SSTable 来消除碎片，因此存储开销通常小于 B-tree；

大小分级压缩：较新的和较小的SSTable文件被连续合并到较旧的、较大的文件SSTable中；

分层压缩：按照key的范围分裂成多个小文件SSTable，旧数据被移动到单独的层级；

LSM-Tree 的缺点

  1. 压缩干扰读写操作：压缩过程中可能干扰正常的读写操作;
  2. 磁盘空间管理：如果写入速度超过压缩速度，磁盘空间可能会耗尽，因为压缩和写入共享磁盘带宽;

Lucene

  Lucene 是 Elasticsearch 和 Solr 等全文搜索系统使用的索引引擎，其采用类似 SSTable 的方法保存词典（词库）；

  主要采用KV实现，key为词条，value为包含该词条的文档ID的列表（倒排索引）；

  它通过倒排索引实现对单词的快速搜索，即给定搜索查询中的某个单词时，找到提及该单词的所有文档，倒排索引中的 key 为词条，value 为包含该词条的文档 ID 列表；

  KV，映射关系，就保存在类似SSTable的排序文件中；

内存数据库

  内存数据库的性能优势在于避免了磁盘写入格式对内存数据结构编码时的开销

  例如，Redis 能够提供基于磁盘索引难以实现的数据结构（如优先队列、集合等）；

非易失性存储（NVM）（Non-Volatile Memory）用于保证在断电或崩溃后，内存中的数据不会丢失；

事务处理与分析处理

注意：事务不一定具有ACID，只是允许客户端进行低延迟的读取和写入；

OLTP（在线事务处理系统）（日志结构流派、原地更新流派）

  • 读：基于键的查询，每次查询返回少量记录；
  • 写：低延迟的随机写入；
  • 场景：用户，通过网络访问；
  • 数据特征：保存最新的数据状态（当前时间点）；
  • 数据规模：GB ~ TB ；

OLAP（在线分析处理系统）

  • 读：汇总大量记录；
  • 写：批量导入（ETL）或事件流；
  • 场景：专业人员，用于数据分析；
  • 数据特征：随着时间而变化的索引事件历史，即保存历史数据；
  • 数据规模：TB ~ PB ；

数仓

  数据仓库保存所有业务的 OLTP 数据库的只读副本，通常通过 ETL（提取-转换-加载）周期性或流式更新；

  数仓的优势在于可以针对分析访问模式进行优化（OLTP的索引算法并不善于：分析查询）；

星型与雪花型模式

  相当一部分数仓使用星型模式（维度建模），即以行为（一个事实）为单位（即为一行）存储数据；即将业务的多张表将有效信息全部合在一起，组成一个事实（行为），

  如三张表，user，goods，purchase，一个30岁男人身高为170cm，购买了一个放在7号货柜中的xx牌子的番茄酱，价格为10元，折后价为7.5元，

  这句话即为一个事实，为数仓的一行数据；此时合并后的事实表基本均为宽表，列为属性；

  当然列也可能引用其他表的外键（其他表被称为维度表），即一个事实表散射出多张维度表；

  而雪花模式则是在此基础上，进一步分裂维度表；

列式存储

在分析查询中，通常只会访问少数字段，少用*。列式存储允许只读取需要的列，而不必像行式存储一样读取所有数据再过滤；