第一章 概述
1.1 分布式存储的概念：
分布式存储系统是大量普通PC服务器通过Internet互联,对外作为一个整体提供存储服务。
分布式存储系统有如下特征：可扩展，低成本，高性能，易用。
分布式存储系统的挑战主要在于数据、 态信息的持 ,要求在自动迁移、自动容错、并发读写的过程中保证数据的一致性。分布式存储涉及的技术主要来自两个领 域:分布式系统以及数据库。
1.2分类
分布式存储面临的数据需求比较复杂,大致可以分为三类:非结构化数据，结构化数据，半结构化数据
（1）分布式文件系统
互联网应用需要存储大量的图片 、照片 、视频等非结构化数据对象,这类数据以对象的形式组织 ,对象之间没有关联,这样的数据一般为Blob (Binary Large Object, 二进制大对象)数据。分布式文件系统用于存储Blob对象,典型的系统有Facebook Haystack以及Taobao File System(TFS)。
（2）分布式键值系统
分布式键值系统用于存储关系简单的半结构化数据,它只提供基于主键的CRUD(Create/Read/Update/Delete)功能,即据主键创建、读取、更新或者删除一键值记录。典型的系统有Amazon Dynamo以及Taobao Tair。
（3）分布式表格系统
分布式表格系统用于存储关系较为复杂的半结构化数据,与分布式键值系统相比, 分布式表格系统不仅仅支持简单的CRUD操作,而且支持扫描某个主键范围 。分布式表格系统以表格为单位组织数据,每个表格包括很多行,通过主键标识一行,支持根据主键的CRUD功能以及范围查找功能。典型的系统包括Google Bigtable以及Megastore,Microsoft Azure Table Storage,Amazon DynamoDB等。
（4）分布式数据库
分布式数据库一 是从单机关系数据库扩展而来,用于存储结构化数据。分布式数据库采用二维表格组织数据,根据SQL关系查询语言,支持多表关联, 嵌套子查询等复杂操作,并提供数据库事务以及并发控制。典型的系统包括MySQL数据库分 (MySQL Sharding)集 ,Amazon RDS以及Microsoft SQL Azure。
第二章 单机存储系统
单机存储引擎就是哈希表、B树等数据结构在机械磁盘、SSD等持久化介质上的实现。单机存储系统是单机存储引擎的一种封装,对外提供文件、键值、表格或者关系模型。
2.1硬件基础
cpu架构
经典的多CPU架构为对称多处理结构(SMP),即在一个计算机上汇集了一组处理器,它们之间对称工作, 无主次或从属 关系,共享相同的物理内存及总线。
SMP架构的主要特点是共享,系统中所有资源(CPU、内存、I/O等)都是共享的, 由于多 CPU 对前端总线的竞 ,SMP的扩展能力非常有限。为了提高可扩展性,现在的主流服务器架构一般为NUMA(非一致存储访问)架构。
IO总线
北桥芯片通过前端总线(FSB)与CPU相连,内存模块以及PCI-E设备(如高端 的 SSD设备Fusion-IO) 接在北桥上。
网络拓扑
下图为传统的数据中心网络 ,思科过去一直提倡这样的拓扑,分为三层,最下面是接入层,中间是汇聚层,上面是核心层。
存储层次架构
从分布式系统的 度 ,整个集群中所有服务器上的存储介质(内存、机械硬盘,SSD)构成一个整体,其他服务器上的存储介质与本机存储介质一样都是可访问的,区别仅仅在于需要额外的网络传输及网络协议栈等访问开销。
2.2单机存储引擎
存储引擎是存储系统的发动机, 直接决定了存储系统能够提供的性能和功能。存储系统的基本功能包括 :增、删 、读、改 ,其中,读取操作又分为随机读取和顺序扫描。 希存储引擎是 希表的持久化实现,支持增、删 、改 ,以及随机读取操作,但不支持顺序扫描,对应的存储系统为键值存储系统;B树 存储引擎是B树的持久化实现,不仅支持单条记录的增、删 、读、改操作,还支持顺序扫描,对应的存储系统是关系数据库。当然,键值系统也可以通过B树存储引擎实现 ;LSM存储引擎和B树存储引擎一样,支持增、删 、改 、随机读取以及顺序扫描。它通过批量转储技术规避磁盘随机写入问题,广泛应用于互联网的后台存储系统,例如Google Bigtable、Google LevelDB以及Facebook开源的Cassandra系统。（1）哈希存储引擎
Bitcask是一个基于哈希表结构的键值存储系统,它仅支持追加操作,即所有的写操作只追加而不修改老的数据。在Bitcask系统中,每个文件有一定的大小限制,当文件增加到相应的大小时,就会产生一个新的文件,老的文件只读不写。
数据结构：Bitcask数据文件中的数据是一条一条的写入操作,每一条记录的数据项分别为主键)、内容、主键长度、value度、时间戳以及crc较验值。
定期合并：Bitcask系统中的记录删除或者更新后,原来的记录成为垃圾数据。如果这些数据一直保存下去,文件会无限膨胀下去,为了解这个问题,Bitcask需要定期行合并操作以实现回收。所谓合并操作,即将所有老数据文件中的数据扫描一遍并生成新的数据文件,这里的合并其实就是对同一个key的多个操作以只保留最新一个的原则进行删除,每次合并后,新生成的数据文件就不再有余数据了。
快速恢复：Bitcask系统中的哈希索引存储在内存中,如果不做额外的工作,服务器断电重启重建哈希表需要扫描一遍数据文件,如果数据文件很大,这是一个非常耗时的过程。Bitcask通过索引文件来提高重建哈希表的速度。
（2）B树存储引擎
B树存储引擎不仅支持随机读取,还支持范围扫描。关系数据库中通过索引访问数据,在Mysql InnoDB中,有一个称为 聚集索引的特殊索引,行的数据存于其中, 组成B+树数据结构。
数据结构：MySQL InnoDB按照页面来组织数据,每个页面对应B+的一个节点。其中, 子节点保存每行的完整数据,非 子节点保存索引信息。数据在每个节点中有序存储,数据库查询时需要从根节点开始二分查找到叶子节点，每次读取一个节点,如果对应的页面不在内存中,需要从磁盘中读取并缓存起来。
缓冲区管理：
LRU：LRU算法淘汰最长时间没有读或者写过的块。这种方法要求缓冲区管理器按照页面最后一次被访问的时间组成一个链表,每次淘汰链表尾部的页面。
LIRS：LIRS算法将缓冲池分为两级,数据首先进入第一级,如果数据在较 的时间内被访问两次或者以上,则成为热点数据进入第二级,每一级内部还是采用LRU 替换算法。
（3）LSM树存储引擎：将对数据的修改增量保持在内存中, 到指定的大小限制后将这些修改操作批量写入磁盘,读取时需要合并磁盘中的历史数据和内存中最近的修改操作。LSM 树的优势在于有效地规避了磁盘随机写入问题,但读取时可能需要访问较多的磁盘文件。
数据结构：LevelDB存储引擎主要包括:内存中的MemTable和不可变MemTable(Immutable MemTable,也 为Frozen MemTable,即 结MemTable)以 及磁盘上的几种主要文件 :当前(Current)文件、清单(Manifest)文件、操作日 (Commit Log,也 为提交日 )文件以及SSTable文件。当应用写入一 记录 时,LevelDB会首先将修改操作写入到操作日志文件,成功后再将修改操作应用到MemTable,这样就完成了写入操作。
合并：LevelDB的Compaction操作分为两种:minor compaction和major compaction。
2.3数据模型
存储系统的数据模型主要包括三类 :文件、关系以及随着NoSQL技术流行起来的键值模型。传统的文件系统和关系数据库系统分别采用文件和关系模型。关系模型描述能力强,产业链完整,是存储系统的业界标准。
文件模型：文件系统以目录树的形式组织文件,以类UNIX操作系统为例, 根目录为/,包含/usr、/bin、/home等子目录,每个子目录又包含其他子目录或者文件。POSIX是应用程序访问文件系统的API标准, 它定 了文件系统存储接 及操作集。POSIX主要接口如下。Open/close:打开/关闭 一个文件,获取文件描述 ;Read/write:读取一个文件或者往文件中写入数据;Opendir/closedir:打开或者关闭一个目录;Readdir: 遍历目录。
关系模型：每个关系是一个表格,由多个元 (行)构成,而每个元 又包含多个属性( )。 关系名、属性名以及属性类型称作 关系的模式(schema)。
键值模型：大量的NoSQL系统采用了键值模型,每行记录由主键和 值两个部分组成,支持基于主键的如下操作:
Put:保存一个Key-Value对。Get:读取一个Key-Value对。Delete: 除一个Key-Value对。
Key-Value模型过于简单,支持的应用 景有限,NoSQL系统中使用比较广泛的模型是表格模型。表格模型弱化了关系模型中的多表关联,支持基于单表的简单操作,典型的系统是Google Bigtable以及其开源Java实现HBase。表格模型除了支持简单的基于主键的操作,还支持范围扫描,另外,也支持基于列的操作。主要操作如下:Insert: 入一行数据,每行包括 ;Delete: 删除一行数据;Update:更新整行或者其中的某些列的数据;Get:读取整行或者其中某些列数据;Scan: 描一段范 围的数据, 根据主键确定扫描的范围 ,支持扫描部分列 ,支持按列过滤、排序、分组等。
2.4事务与并发控制
事务规范了数据库操作的 ,每个事务使得数据库从一个一致的状态原子地转移到另一个一致的状态。数据库事务具有原子性、一致性、 隔离性以及持久性即ACID 属性,这些特性使得多个数据库事务并发执行时互不干扰 ,也不会获取到中间状态的错误结果。
事务：事务是数据库操作的基本单 ,它具有原子性、一致性、隔离性和持久性这四个基本属性。
并发控制：分为数据库锁，写时复制，多版本并发控制
2.5故障恢复：
数据库运行过程中可能会发生故障,这个时候某些事务可能执行到一半但没有提交,当系统重启时,需要能够恢复到一致的状态,即要么提交整个事务,要么回滚 。 数据库系统以及其他的分布式存储系统一般采用操作日志 (有时也称为提交日志 ,即Commit Log)技术来实现故障恢复。操作日志分为回滚日志、重做日志以及UNDO/REDOr日志。如果记录事务修改前的状态,则为回滚日志 ; 相应地,如果记录事务修改后的状态,则为重做日志。
2.6数据压缩
数据压缩分为有损压缩与无损压缩两种,有损压缩算法压缩比率高,但数据可能 ,一般用于压缩图片 、音频 、视频 ;而无损压缩算法能够完全还原原始数据。早期的数据压缩技术就是基于编码上的优化技术,其中以 Huffman 编码最为知名,它通过统计字符出现的频率计算最优前缀编码。