学习总结 2021.12.19

本周，主要学习了如何进行高性能、高可用的架构设计，在学习高性能时，关于存储模型部分的知识点，进行了如下的扩展学习，重点是学习了 Hash、B-Tree、LSM 这三种存储模型的相关知识

1. 应用情况

• Hash：redis、memcache

• B+ Tree：MySQL、MongoDB

• LSM：HBase、RocksDB

2. 三种模型的特点

2.1. Hash 存储模型

Hash 存储模型的特点是与 HashMap 有密切关系，Hashmap 是无序的，不支持顺序扫描，但是读写都很快。

也就是说：

• put(key) 增加/修改、delete(key) 删除、get(key) 查询单个，时间复杂度都是 O(1)

• 但不支持 get(1) 操作

因此，适合在应用中无需遍历数据，针对单个 Key 的操作；对于以下场景是不支持的：

• 最左原则，因为 hash 的联合查询是这样，比如 where a=1 and b=2，是把 a=1 and b=2 转成一个 hash 码来进行查询，如果换成 b=2 and a=1，那么 hash 码将完全不同，索引失效。

• 范围查询，因为 hash 是无序的，和 b+tree 不一样，b 树是有序的

• order by 排序，因为是无序的

• 模糊查询，因为是精确查找

2.2. B+Tree 存储模型

既然二叉查找树的查询复杂度已经是 O（logN），那为什么数据库中的索引没有使用二叉树？

这是由于数据库索引是存储在磁盘上，当数据量比较大的时候，比如有几个 G；这时去查询索引时，无法将整个索引加载到内存，需要逐一加载磁盘页（磁盘页对应着索引树的节点）：

• 假设，利用二叉树作为索引结构，在最坏的情况下，磁盘 IO 的次数等于索引树的高度

• 那么，使用 B 树（也称之为 B-树）的好处就是，降低树的高度，从而减少磁盘 IO 的次数，从而提升查找性能

那么，什么是 B 树？

B 树是一种多路平衡查找树，它的每一个节点最多包含 k 个孩子，k 被称之为 B 树的阶，k 的大小取决于磁盘页的大小；一个 m 阶的 B 树具有如下特征

• 根节点至少有两个子女；如，节点（2,6）和（11,13）

• 每个中间节点都包含 k-1 个元素和 k 个孩子，其中 m/2 <= k <= m；如，节点（2,6），有 1、（3,5）、（7,8）三个孩子

• 每个叶子节点都包含 k-1 个元素，其中 m/2 <= k <= m

• 所有的叶子节点都位于同一层

• 每个节点中的元素从小到大排列，节点当中 k-1 个元素正好是 k 个孩子包含的元素的值域分划

为什么还需要 B+树？

• 首先，B+树，比 B 树更加“矮胖”，查询时磁盘 IO 会更少；这是因为，B+树的中间节点只存放索引，不存放数据，而在 B 树中，所有节点都存放数据（我们称这些存放数据的节点为卫星数据）

• 其次，在进行查询时，B+树必须最终查找到叶子节点，因此，比 B 树更加稳定

• 最后，在进行范围查询时，比如，3~11，B+树查找到范围下限（3），再通过链表指针，遍历到（6,8），接着再遍历到（9,11），而 B 树，则需要通过中续遍历，更加的复杂

因此，是 B+树的优势是：

• 单一节点存储更多的元素，使得查询的 IO 次数更少

• 所有查询都要查找到叶子节点，查询性能更稳定

• 所有叶子节点形成有序链表，便于范围查询

2.3. LSM 树存储模型

Log-Structured-Merge-Tree，与 B+树类似，都是为了更好地将数据存储到大容量磁盘中

上图来自《The Pathologies of Big Data》，它揭示出，磁盘顺序写的吞吐量甚至可以超过内存随机写的吞吐量。而 LSM 树正是利用了这一点，通过将磁盘随机写操作转化为顺序写操作，从而将写入操作的吞吐量提升，更加适合写多读少的场景。

LSM 树是如何做到将随机写转换为顺序写的

LSM 树会将所有数据插入、修改、删除等操作保存在内存中，当此类操作达到一定的数量后，再批量写入到磁盘中。而在写入磁盘时，会和以前的数据做合并，合并过程，并不会像 B+树一样，在原数据的位置上修改，而是直接插入新的数据，从而避免随机写。

LSM 树的结构是横跨内存和磁盘的，包含 memtable、immutable memtable、SSTable 三个部分：

• memtable：是在内存中的数据结构，保存最近的更新操作，当写入到 memtable 中时，会先通过 WAL（Write-ahead logging）的方式备份到磁盘中，以防止数据因为内存掉电而丢失

• memtable 使用跳跃表或者搜索树等数据结构来组织数据，以保持数据的有序性

• 当 memtable 达到一定数据量后，会转化为 immutable memtable，同时会创建一个新的 memtable 来处理新的数据

• immutable memtable：在内存中是不可修改的数据结构，它是将 memtable 转变为 SSTable 的一种中间状态，目的是为了在转存过程中不阻塞写操作，写操作由新的 memtable 处理，而不用锁住 memtable

• SSTable：是 Sorted String Table，即为有序键值对集合，是 LSM 树组在磁盘中的数据结构。如果 SSTable 比较大的时候，可以根据键的值建立一个索引来加速 SSTable 的查询

memtable 中的数据，最终都会被转化为 SSTable，并保存在磁盘中，后续还会有相应的 SSTable 日志合并操作（compaction）

LSM 树会将所有的数据插入、修改、删除等操作记录保存在内存之中，当此类操作达到一定的数据量后，再批量地顺序写入到磁盘当中，数据更新是日志式的，当一条数据更新是直接 append 一条更新记录完成，这样的设计就是为了顺序写，但是会带来一写问题：

• 冗余存储，对于某个 key，除了最新的记录外，其他的记录都是冗余无用的，因此需要进行合并操作来清除冗余

• 读取时，需要从最新的倒着查询，直到找到某个 key 的记录，最坏情况需要查询完所有的 SSTable，这里可以通过前面说的索引/布隆过滤器来优化查找速度

因此，合并操作是十分关键的操作，否则 SSTable 会不断膨胀，在合并策略上有两种基本策略：

• size-tiered 策略：保证每层 SSTable 的大小接近，同时限制每一层 SSTable 的数量；当每层 SSTable 达到 N 后，除非 Compact 操作，合并这些 SSTable，并将合并后的结果写入到下一层，成为更大的 SSTable；因此，size-tiered 策略会导致空间方达比较严重

• leveled 策略：也是采用分层的思想，每一层限制总文件的大小，但是跟 size-tiered 不同的是，leveled 会将每一层切分成多个大小相近的 SSTable，这些 SSTable 是这一层全局有序的，即一个 key 在每一层至多只有 1 条记录，不存在冗余记录