2 单机存储系统

ACID：

1. 原子性 Atomicity
2. 一致性 Consistency
3. 隔离性 Isolation
4. 持久性 Durability

存储引擎：

1. 哈希存储引擎
2. B 树存储引擎
3. LSM 树（Log Structure Mereg Tree）存储引擎

2.1 硬件基础

CPU：对称多处理结构(SMP)。SMP 扩展能力有限。

为了提高可扩展性，现在的主流服务器架构一般为 NUMA（Non-Uniform Memory Access，非一致性存储访问）架构。它具有多个 NUMA 节点，每个 NUMA 节点是一个 SMP 结构，一般由多个 CPU（如 4 个）组成，并且具有独立的本地内存、io 槽口等。

NUMA 节点可以直接快速访问本地内存，也可以通过 NUMA 互联互通模块访问其他 NUMA 节点的内存，访问本地内存的速度要远远高于访问远程的速度。

2.1.2 IO 总线

Interl x48 主板为例，典型的南北桥架构。北桥芯片通过前端总线（Front Side Bus，FSB）与 CPU 相连，内存模块以及 PIC-E 设备（如高端 SSD 设备 Fusion-IO）挂接在北桥上。北桥与南桥之间通过 DMI 连接。

2.1.3 网络拓扑

三层拓扑。

接入层（Edge），汇聚层（Aggregation）、核心层（Core）。

问题：可能有很多接入层的交换机接到汇聚层，很多汇聚层交换机接到核心层。同一个接入层下的服务器之间的带宽比如为 1Gb，那么不同接入层交换机下的服务器之间的带宽小于 1Gb。由于同一个接入层的服务器往往部署在一个机架内，因此，设计系统的时候需要考虑服务器是否在一个机架内，减少跨机架拷贝大量数据。如：Hadoop HDFS 默认 3 副本，其中两副本放在同一个机架。

Google 在 2008 年将网络改造为扁平化拓扑结构，即三层 CLOS 网络，同一个集群内最多支持 20480 台服务器，且任何两台都有 如 1Gb 带宽。CLOS 网络需要额外投入更多的交换机。好处是：设计系统时不需要考虑底层网络拓扑，从而很方便地将整个集群做成一个资源池。

🤔 如何计算光纤延时？

如：北京杭州直线距离 1300 公里，光在光线中走折线，假设折线距离为直线距离的 1.5 倍，那么光传输一次网络来回延时的理论值为 1300*1.5*2/300 000 = 13ms, 实际测试值大约为 40ms。

2.1.4 性能参数

存储系统的性能瓶颈主要在于磁盘 随机读写。

SSD 特点：随机读取延迟小。

存储系统性能主要：吞吐量以及访问延时，在保证访问延时的基础上，通过最低的成本实现尽可能高的吞吐量。磁盘适合大块顺序访问，ssd 适合随机访问较多或对延时较敏感的关键系统。二者常常结合，热数据存储在 ssd 上，冷数据存储在磁盘中。

2.2 单机存储引擎

• 哈希：不支持顺序扫描
• B 树：适合关系型数据库
• LSM 树：通过批量转储技术规避磁盘随机写入问题。

2.3 数据模型

2.3.1 文件模型

POSIX（Portable Operating System Interface)，要求读写并发时保证操作的原子性，即读操作要么读取到所有结果，要么什么都读不到；另外，要求读操作能够读到之前所有写操作的结果。适合单机文件系统。分布式文件系统不会严格遵守该标准。

NFS 允许客户端缓存文件数据，多个客户端并发修改同一文件时可能出现不一致的情况。

对象模型与文件模型类似，弱化了目录树的概念 ，要求 对象一次性写入到系统，只能删除整个对象，不允许修改其中某个部分。

2.3.2 关系模型

每个关系是一个表格，由多个元祖（行）组成，每个元祖又包含多个属性（列）。

关系名、属性名、以及属性类型称作该关系的模式（Schema）。如：Movie 关系的模式为Movie(title, year, length), title year length 为属性，类型分别为字符串 整数 整数

1

2

3

4

5

6

SELECT  <属性表 >
FROM  < 关系表 >
WHERE < 条件 >
GROUP BY  < 属性表 >
HAVING  < 条件 >
ORDER BY  < 属性表>
SQL

SQL 特性：

1. 允许在 WHRER FROM HAVING 字句中使用子查询，子查询又是一个完整的select-from-where 语句
2. 索引（用于减少 SQL 执行时扫描的数据量，提高读取性能）
3. 事务（保证多个操作并发执行时的 ACID 特性）

2.3.3 键值模型

键值模型：

• Put
• Get
• Delete

表格模型：

Google Bigtable、HBase，除了支持简单的基于主键的操作，还支持 范围扫描 ，另外，也支持 基于列的操作。主要操作如下：

• Insert
• Delete
• Update
• Get
• Scan：扫描一段范围的数据，根据主键确定扫描的范围，支持扫描部分列，支持按列过滤、排序、分组等。

不支持多表关联操作，一般不支持二级索引，事务操作支持比较弱，没有统一标准。另外，表格模型支持 无模式（schema-less——特性，不需要预先定义每行包括哪些列以及每个列的类型，多行之间允许包含不同列。

2.3.4 SQL 与 NoSQL

非关系型数据库（NoSQL，Not Only SQL），良好的可扩展性，弱化一致性要求，一定程度上解决了海量数据和高并发的问题。

关系型数据库在海量数据场景存在问题：

1. 事务。在分布式系统中，如果多个操作属于不同的服务器，保证它们的原子性需要用到两阶段提交协议，该协议性能很低，且不能容忍服务器故障，很难应用在海量数据场景。
2. 联表。在海量数据场景，为了避免数据库多表关联操作，往往会使用数据冗余等违反数据库范式的手段。但是收益高于成本。
3. 性能。

NoSQL 的问题：

1. 缺少统一标准
2. 使用及运维复杂。

2.4 事务并发控制

为了性能考虑，会定义多个隔离级别，事务的并发控制往往通过锁机制来实现，锁可以有不同粒度，可以锁住行，可以锁住数据块甚至整个表。

互联网业务，读比写多，为提高性能，可以采用 写时复制 （Copy-On-Write, COW) 或 多版本并发控制(Multi-Version Concurrency Control, MVCC) 来避免写事务阻塞读事务.

2.4.1 事务

• 原子性
• 一致性
• 隔离性
• 持久性

原子性

事务对数据的修改, 要么全执行, 要么全不执行. 如: A 转账一笔钱 x 给到 B, 结果必须是 A 扣了 x, B 加了 x.

一致性

数据的正确性、完整性、一致性。如：数据类型必须正确，数据值必须在规定范围内。

隔离性

保证每一个事务在它的修改全部完成之前，对其他事务是不可见的。还是上边的例子，转账过程中，查询操作不能看到 A 账户已经扣款 x，B 账户却还没扣款 x 的状态。

持久性

事务完成后，对数据库的影响是永久的。

处于性能考虑，允许使用者选择牺牲隔离属性换取并发度。

4 种隔离级别：

1. Read Uncommitted (RU): 读取未提交的数据, 最低隔离级别.
2. Read Committed (RC): 读取已提交的数据
3. Repeatable Read (RR): 可重复读取.
4. Serializable(S): 可序列化. 最高隔离级别

隔离级别的降低可能导致脏数据和事务执行异常, 如:

1. Lost Update (LU): 丢失更新
2. Dirty Reads (DR): 脏读. 一个事务读取了另一个事务更新却没有提交的数据.
3. Non-Repeatable Reads (NRR): 对同一数据的多次读取得到不同的结果.
4. Second Lost Updates problem (SLU): 第二类丢失更新. 两个并发事务同时读取和修改同一数据, 则后面的修改可能使得前面的修改失效.
5. Phantom Reads (PR): 事务执行过程中, 由于前面的查询和后面的查询的期间有另外一个事务插入数据, 后面的查询结果出现了前面查询结果中未出现的数据.

2.4.2 并发控制

数据库锁

读锁和写锁. 允许对同一行元素加多个读锁, 但只允许一个写锁. 这里的元素可以是一行, 一个数据块, 甚至一个表.

解决死锁的思路:

1. 事务设置超时时间, 超时自动回滚.
2. 死锁检测.

写时复制

读操作不加锁.

多版本并发控制

对每行数据维护多个版本.

InnoDB 对每一行维护两个隐含的列.

2.5 故障恢复

操作日志 (提交日志 Commit Log) 技术来实现故障恢复.

操作日志分为: 回滚日志 (UNDO Log), 重做日志(REDO Log) 以及 UNDO/REDO 日志.

记录事务修改前的状态, 则为回滚日志; 记录事务修改后的状态, 则为重做日志.

2.5.1 操作日志

通过操作日志顺序记录每个数据库操作并将在内存中执行这些操作, 内存中的数据定期刷新到磁盘, 实现将随机写请求转化为顺序写请求.

ℹ 示例:

事务 T 对表格中的 X 执行加 10 操作, 初始 X = 5, 更新后 X = 15, 那么

UNDO 日志记为 <T, X, 5>, REDO 日志记为 <T, X, 15>

UNDO/REDO 日志记为 <T, X, 5, 15>

2.5.2 重做日志

2.5.3 优化手段

1. 成组提交(Group Commit)
2. 检查点(checkpoint): 定期将内存中的数据 Dump 到磁盘,

2.6 数据压缩

有损和无损压缩.

无损: LZ 系列压缩算法. 如: GZip

压缩算法核心: 找重复数据. 列式存储大大提高了数据的压缩比.

2.6.1 压缩算法

1. Huffman 编码
2. LZ 系列压缩算法: 就基于字典的压缩算法
3. BMDiff 与 Zippy (相比于传统 LZ, 优势在于处理速度非常快)

2.6.2 列式存储

OLAP: 一个查询要访问几百万甚至几十亿数据行, 且查询往往只关心少数几个列. 如: 查询今年销量最高的前 20 个商品. 只关注 3 列: 时间, 商品和销量.

列组(column group): 多个经常一起访问的数据列的各个值存放在一起.

由于同一列数据重复度很高, 因此, 列式数据库压缩时有很大优势.

可以针对列式存储做专门索引优化.