第1章 概述
互联网公司的分布式两个特点：规模大、成本低。
1.1 分布式存储概念
定义：分布式存储系统是大量普通PC服务器通过Internet互联，对外作为一个整体提供存储服务。
特性：
- 可扩展。集群，性能随规模线性增长。
- 低成本。有自动容错，自动负载均衡机制。所以可以构建在普通PC机器。
- 高性能。
- 易用。提供易用的对外接口。
主要挑战：数据、状态信息的持久化，要求在自动迁移、自动容错、并发读写的过程中保证数据的一致性。
主要技术来自于分布式系统和数据库：
- 数据分布：如何保证均匀？如何实现跨服务器读写？
- 一致性：如何复制？如何保证出现异常也一致？
- 容错：如何检测？出错如何迁移？
- 负载均衡：如何实现？如何做到迁移时不影响其他业务？
- 事务与并发控制：如何实现分布式事务？如何实现MVCC？
- 易用性：如何易用？如何方便运维？
- 压缩/解压缩：如何根据数据特点设计压缩/解压缩算法？如何平衡节省的存储空间和消耗的CPU资源浪费？
1.2 分布式存储分类
数据大致分为三类：
- 非结构化数据：包括所有格式的办公文档、文本、图片、图像、音频和视频信息等。
- 结构化数据：一般存储在关系数据库中，可用二位关系表结构来表示。
- 半结构化数据：与结构化的区别在于，半结构化数据的模式结构和内容混在一起，没有明显的区分，也不需要预先定义数据的模式结构。
存储系统分为四类：
- 分布式文件系统
图片、照片、视频等非结构化数据对象，以对象组织，对象之间没有关联，称为Blob（Binary Large Object，二进制大对象）数据。
总体上看：分布式文件系统存储三种类型的数据：Blob对象、定长块以及大文件。在系统层面，分布式文件系统内部按照数据块来组织数据，每个数据块的大小大致相同，每个数据块可以包含多个Blob对象或者定长块，一个大文件也可以拆分成多个数据块。
- 分布式键值系统
用于存储关系简单的半结构化数据，它只提供基于主键的CRUD功能，即根据主键创建、读取、更新或者删除一条键值记录。
与传统哈希表相似，但是支持将数据分布到多个存储节点。
分布式键值系统是分布式表格系统的一种简化实现，一般用作缓存。
- 分布式表格系统
用于存储较为复杂的半结构化数据。不仅仅支持简单的CRUD操作，而且支持扫面某个主键范围。
借鉴了许多关系型数据库的技术，例如支持某种程度上的事务，比如单行事务，某个实体组下的多行事务。
与分布式数据库先比，仅支持针对单张表格的操作，不支持复杂操作。
- 分布式数据库
一般从单机数据库扩展而来，用于存储结构化数据。
第2章 单机存储系统
单机存储引擎就是哈希表、B树等数据结构在机械磁盘、SSD等持久化介质上的实现。
2.1 硬件基础
2.1.1 CPU架构
经典的多CPU架构为对称多处理结构（Symmetric Multi-Processing，SMP），即在一个计算机上汇集了一组处理器，它们之间对称工作，无主次或从属关系，共享相同的物理内存及总线。
2.1.2 IO总线
存储系统的性能瓶颈一般在与IO。
2.1.3 网络拓扑
传统的数据中心网络拓扑，分三层。最下面是接入层，中间是汇聚层，上面是汇聚层。存在的问题：大量下层接入，导致同一个接入层下的服务器之间的带宽减小。
2.1.4 性能参数
2.1.5 存储层次架构
存储系统的性能主要包括两个维度：吞吐量以及访问延时。
2.2 单机存储引擎
2.2.1 哈希存储引擎
Bitcask是一个基于哈希表结构的键值寸尺系统，它仅支持追加操作（Append-only），即所有的写操作只追加而不修改老的数据。
在Bitcask系统中，每个文件有一定的大小限制，当文件增加到相应的大小时，就会产生一个新的文件，老的文件只读不写。在任意时刻，只有一个文件市可写的，用于数据追加，称为活跃数据文件。而其他已经达到大小限制的文件，称为老数据文件。
- 数据结构
一条一条写入，每条记录的数据项分别为：主键（key），value内容（value），主键长度（key_sz），value长度（value_sz），时间戳（timetamp）以及crc校验值。（删除不会删除旧的条目，而是将value设定为一个特殊的之作标识）。内存中的结构是hash表。
- 定期合并
为解决垃圾文件问题。将所有老数据文件中的数据扫描一遍生成一个新的数据文件。对用一个key的多个操作以保留最新的一个原则进行删除。
- 快速恢复
每次合并时，将内存中的哈希索引表转储到磁盘中，生成一个索引文件。这个索引文件只存储value的位置。
2.2.2 B树存储引擎
不仅支持随机读取，还支持范围扫描。
- 数据结构
InnoDB按照页面（Page）来组织数据，每个页面对用B+树的一个节点。
B+树的根节点是常驻内存的。修改操作首先需要记录提交日志，接着修改内存中的B+树。
- 缓冲区管理
LRU、LIRS
2.2.3 LSM树存储引擎
将对数据的修改增量保持在内存中，达到指定的大小先之后将这些修改操作批量写入磁盘，读取时需要合并磁盘中的历史数据和内存中最近的修改操作。