当前位置：首页 > news >正文

「阅读」数据密集型系统设计第三章

news 来源：原创 2024/9/20 12:24:34

总结

总结写在最开始，阅读过程中可能对内容的理解会更好一些。

作者在本章节的总结大致如下：
本章节讨论的内容是数据库如何存储和检索，并将存储引擎分为两大类：事务处理 && 事务分析，基于两类存储引擎进行了如下讨论

两种存储引擎的不同特征
事务处理引擎
1. 两种常见的存储结构：日志结构 && 面向页面结构
2. 基于上述两种存储结构的索引结构 && 使用方法
事务分析引擎
1. 列式存储：列式存储的介绍，列式存储如何更好的存储&&查询

笔记的顺序基本遵从了作者的写作章节顺序，但是我认为作者总结的这种思路和他的写作思路明显是有冲突的，在我理解中日志结构 && 面向页面结构既不单独属于事务处理引擎，也不是事务存储引擎的专属。在我看来本章内容的理解应该如下

概念部分介绍了不同的存储结构 && 索引结构，这些内容是下面不同倾向的数据库的实现组件。
对于大型公司的存储架构而言，对存储的使用存在两种不同模式：事务处理 && 事务分析（数据仓库）
1. 面向事务处理的数据库强调高可用 && 低延时，本章节中描述了实现该目标非常重要的索引
2. 面向事务分析的数据库，本章节基于事务分析过程中着重于一行中少部分列的特点，着重介绍了列式存储，强调了在事务分析过程中，列式存储相较于行式存储的优势。

在写笔记的时候，舍弃了列式存储中的“聚合”部分，原因很简单，看不懂，以后再说。

1. 概念

存储结构

日志结构存储（Log-Structured Storage, LSS）

数据库在硬盘的存储形式之一，通过追加形式写入磁盘中，并通过使用追加日志文件存储数据的更新和删除操作。

日志结构将数据库分为可变大小的数据段。每段日志达到一定大小后，会创建新的日志段继续写入；对于已经写完的数据段，可以通过压缩减少空间占用。
在这里插入图片描述

关键词：追加写入、顺序写入、数据段、压缩

面向页面结构存储

和日志结构不同，面向页面的存储结构将数据库分解为固定大小的块/分页，每次只能读取或者写入一个页面。

不同页面之间通过引用互相串联，构成一个页面树。
![[索引范围查询.png]]

索引

索引是在主数据外衍生的数据结构，主要目的是：高效查找数据库中特定键。

hash 索引

日志结构存储索引
hash 索引类似编程语言中的 map/dict 等结构，key-value 分别代表 key && value offset。

图中很清晰的表示了 hash 索引和日志的交互模式。

hash 索引特点

hash 表必须放入内存
- 如果键值对非常多，要么扩容内存，要么使用硬盘进行散列映射，but 前者贵，后者性能一般
范围查询效率不高
- 显而易见，map 的范围查询的速度本身不高（数据不连续）

SSTable 结构 && LSM 机制

介绍

hash 索引结构对数据存储时的顺序并不做要求，索引在范围查询效率不高。

SSTable（The Sorted String Table）则是一种特殊的数据格式，该格式的文件内部数据具有有序性。
该结构有一个可选内容：（key offset）的 index，用于快速查询
该结构由于其有序性，可以进行随机读写&&范围查询。
在这里插入图片描述

从运行机制的角度考虑，SSTable 结构保证了数据有序性，提供了较好的随机读写&&范围查询能力，但是该数据在不同存储介质上有不同的表现：

内容中的 SSTable 数据：提供了较好的随机写入能力
硬盘中的 SSTable 数据：适合静态数据的快速查询，写入能力很差，需要很多额外的 IO

LSMTree（LogStructed Merge Trees 日志结构合并树）是一种机制，该机制主要完成内存排序、刷盘、压缩和快速读取等工作，配合 SSTable 数据结构，提供了较好的随机读写能力。LSMTree 机制约定了以下内容

硬盘中的 SSTable index 需要加载到内存中
所有写入操作必须在 memTable 中完成
读取时首先查找 memTable，其次查找 SSTable index
memTable 过大时，需要以 SSTable 格式刷入磁盘中
磁盘中的 SSTable 数据都 “collapsed 折叠”在一起

在这里插入图片描述

SSTable && LSM 如何完成增删改查操作？

写入请求的处理方式
1. 内存中将新写入数据添加到内存中的平衡树数据结构（内存表）
2. 内存表大于阈值后，作为 SSTable 文件写入硬盘，这个文件就是数据库最新的段
读取请求
1. 首先在内存中读取对应的值，如果找到返回
2. 如果没有找到，在最近的硬盘段中寻找，如果没有找到在另一个旧的段中寻找
增删操作
1. LSM && SSTable 的操作机制决定了对写入类的操作不能在硬盘上执行
2. 增删操作的实现在于修改 MemTable 中的数据
  1. 如果修改，在 MemTable 中存储修改后的 k-v
  2. 如果删除，在 MemTable 中对 k-v 对增加删除标识
段的压缩和重写
1. 后台程序会不定时进行合并压缩

书中对 SSTable 和 LSM 的描述相对简单，更基础详细的介绍可以参考 https://www.igvita.com/2012/02/06/sstable-and-log-structured-storage-leveldb/

B 树

B 树时一种面向页面的索引类型
在这里插入图片描述

B 树要求键值对有序，这个设计理念和 LSM 相同。

比较 B 树和 LSM 树

LSM 优点
1. B 树索引需要两次写入操作（WAL 日志 && 数据本身）；LSM 树需要一次写入操作 && 后台合并写操作
2. B 树的写入是随机读写，LSM 写入是顺序读写
3. 综合，LSM 写入磁盘时 IO 效率更高
LSM 缺点
1. 由于磁盘写入带宽需要在初始写入和后台运行的压缩线程中共享，当数据越大时，后台压缩所需要的带宽越多，磁盘写入收到影响。B 树面向页面，即使是进行类似压缩合并的操作，一般情况下，并不会对所有页面进行。

2. 事务处理 or 事务分析？

概念

本书中对事务处理和事务分析并没明确的概念，只是通过以下特征进行区分

	事务处理系统	事务分析系统
读取模式	少量记录，按照键获取	大批量记录中聚合
写入模式	随机访问，写入要求时延较低	批量导入
用户	终端用户	内部数据分析师
处理的数据	最新的数据	历史数据
数据集尺寸	GB-TB	TB-PB

从上述两种对数据的处理方式，可以得到以下的架构，通过对多个 DB 抽取-转换-加载的方式，可以得到事务分析所需的数据内容。
在这里插入图片描述

由于事务处理和事务分析的侧重点不同，他们对数据库的要求不同

事务处理：要求高可用 && 低延迟
事务分析：要求高效存储 && 查询

本书中对单独进行事务分析的数据称之为 数据仓库

星型和雪花型：分析的模式

下图以食物零售商为例，展示了一个数据仓库的样式，处在数据仓库中心的称之为事实表，事实表中存在列是其他表的外键引用，这些表称之为维度表。

书中对事实表中行的定义为：每一行定义了一个具体的事件。
我理解事实表代表了某次操作的目的，维度表是对这次操作的约束。

在这里插入图片描述

从上图可以看到，这种事实表被维度表包围的结构被称之为星型结构。

在分析过程中，分析师通常将事实表中每一行代表了一个独立行为进行分析。

雪花模式是星型模式的一种变体，其中维度可以继续分裂。由于分析师更关注事实表，所以一般还是使用星型模型分析。

tips 这个鬼东西为啥会是星型呢？
根据维基百科描述，所谓星形是几何学中的概念，大致含义为有多个凸起的多边形，可以去想想五角星。
书中将星型模型描述为：事实表在中间，被维度表包围，这些连接像是星型的光芒。这么描述挺好理解的，那为啥不叫太阳模型，太阳太大了吗（doge

3. 列式存储

介绍

列式存储解决的场景是：大规模数据（PB）级别下，对数据的高效存储和查询。

已知：

以行为单位存储时，大数据量下，事实库会变得异常庞大。
在对数据分析的场景中，每次查询会涉及很多行，但是只会使用行中的小部分列数据。
面向行的存储引擎需要将每行读取到内存中，过滤掉大部分无用列

列式存储理念：将每列的所有值存储在一起。
在这里插入图片描述

和面向行的存储对比，优势

由于同一列数据集中在一起，类型一致的数据可以进行压缩
1. 压缩方法
  1. 位图编码，过于稀疏，空间浪费
  2. 游程编码，对方法一的优化，通过出现次数进行表示
IO 读入总量减少
1. 分析时只需要对需要的列进行读取
减少查询过程中节点函数调用次数
1. 列数据每次以一个数据块返回，相较于行数据能带来更多的有效信息
列数据通过数组（向量）表示，可以通过向量操作加快计算速度