单机存储系统

单机存储引擎就是哈希表，B树等数据结构在机械磁盘，SSD等持久化介质上的实现。

硬件基础

CPU架构

1. 经典的多CPU架构为对称对处理结构（Symmetric Multi-Processing,SMP），即在一个计算机上汇集了一组处理器，他们之间对称工作，无主次或从属关系，共享相同的物理内存及总线。
2. CPU与内存之间通过总线通信。每个核心有各自的L1d Cache(L1数据缓存)及L1i Cache(L1指令缓存)，同一个CPU的多个核心共享L2以及L3缓存。
3. SMP架构的主要特征是共享，系统中所有资源(CPU,内存,I/O等)都是共享的，由于多CPU对前端总线的竞争，SMP的扩展能力非常有限。
4. 为了提高扩展性，现在主流服务器架构一般为NUMA(Non-Uniform Memory Access，非一致存储访问)架构。它具有多个NUMA节点，每个NUMA节点是一个SMP结构，一般由多个CPU（如4个）组成，并且具有独立的本地内存，IO槽口等。
5. NUMA节点可以直接快速访问本地内存，也可以通过NUMA互联互通模块访问其他NUMA节点的内存，访问本地内存的速度远远高于远程访问的速度。

IO总线

1. 以Intel x48主板为例，他是典型的南，北桥架构。北桥芯片通过前端总线与CPU相连，内存模块以及PCI-E设备（如高端SSD）挂接在北桥上。
2. 北桥与南桥之间通过DMI连接，DMI的带宽为1GB/s。
3. 网卡，硬盘以及中低端固态盘挂接在南桥上。

网络拓扑

1. 数据中心网络拓扑（三层）：接入层（Edge），汇聚层（Aggregation），核心层（Core）。
2. 同一个接入层下的服务器之间带宽为1Gb，不同接入层交换机下的服务器之间的带宽小于1Gb。由于同一个接入层的服务器往往部署在一个机架内，因此设计系统时需要考虑服务器是否在一个机架内，减少跨机架拷贝大量数据。
3. 为减少系统对网络拓扑结构的依赖，google在2008年将网络改造为扁平化拓扑结构，即三级CLOS网络，同一个集群内最多支持20480台服务器，且任何两台都有1Gb带宽。CLOS网络需要额外投入更多的交换机，好处是设计系统时不需要考虑底层网络拓扑，从而很方便的将整个集群当作一个计算资源池。

单机存储引擎

概述

哈希存储引擎是哈希表的持久化实现，支持增删改以及随机读取操作，但不支持顺序扫描，对应的存储系统为键值(Key-Value)存储系统；
B树(B-Tree)存储引擎是B树的持久化实现，不仅支持单条记录的增删读改操作，还支持顺序扫描，对应的存储系统是关系数据库；
LSM树（Log-Structured Merge Tree）存储引擎和B树存储引擎一样，支持增删改，随机读以及顺序扫描，它通过批量转储技术规避磁盘随机写入问题。

哈希存储引擎

1. 数据结构
   memory: hashtable: key -> [file_id | value_sz | value_pos | timestamp]
   disk: old/new file : [crc | timestamp | key_sz | value_sz | key | value]
   数据删除操作不会删除旧的条目，而是将value设定为一个特殊的值用作标识。
   内存中采用哈希表的索引数据结构，哈希表的作用是通过主键快速定位到value位置。
   每个写操作总共需要进行一次顺序的磁盘写入和一次内存操作。
2. 定期合并
   将所有老数据文件中的数据扫描一遍生成新的数据文件，这里的合并其实就是对同一个key的多个操作以只保留最新一个的原则进行删除。

B树存储引擎(InnoDB)

1. 数据结构
   
   叶子节点保存每行的完整数据，非叶子节点保存索引信息。数据在每个节点中有序存储，数据库查询时需要从根节点开始二分查找直到叶子节点，每次读取一个节点，如果对应的页面不在内存中，需要从磁盘中读取并缓存起来。
   修改操作首先需要记录提交日志，接着修改内存中的B+树，如果内存中的被修改过的页面超过一定比率，后台线程会将这些页面刷到磁盘中持久化。
2. 缓冲区管理

• LRU
  LRU算法淘汰最长时间没有读或者写的块。
  缺点：假如某一个查询做了一次全表扫描，将导致缓冲池中大量页面（可能包含很多很快被访问的热点页面）被替换，从而污染缓冲池。
• LIRS
  将缓冲池分为两级，数据首先进入第一级，如果数据在较短的时间内被访问两次或以上（或以停留时间判定），则成为热点数据进入第二级，每一级内部还是采用LRU替换算法。

LSM树存储引擎(levelDB)

主要思想：将对数据的修改增量保持在内存中，达到指定的大小限制后将这些修改操作批量写入磁盘，读取时需要合并磁盘中的历史数据和内存中最近的修改操作。LSM树的优势在于有效规避了磁盘随机写入问题，但读取时可能需要访问较多的磁盘文件。

1. 存储结构
   

• levelDB存储引擎主要包括：内存中的MemTable和不可变的MemTable(Immutable MemTable)以及磁盘上的：current文件，manifest文件，commit log文件以及SSTable文件。
• 当应用写入一条记录时，LevelDB会首先将修改操作写入到操作日志文件，成功后再将修改操作应用到MemTable。
• 当MemTable占用的内存达到一个上限值后，需要将内存的数据转储到磁盘上，此时会将MemTable冻结为Immutable MemTable，并生成一个新的MemTable。
• 新到来的数据被记入新的操作日志文件和新生成的MemTable。而Immutable MemTable只能读取不能写入和删除。
• LevelDB后台线程会将Immutable MemTable数据排序后转储到磁盘，这个操作成为Compaction。
• SSTable文件是内存中的数据不断进行Compaciton后形成的，具有层级结构。
• SSTable文件按记录的主键排序，有最小最大主键，manifest文件记录了这些元数据，包括属于哪个层级，文件名称。
• current文件记录了当前使用的manifest文件名。
• 查询读取的顺序为MemTable->Immutable MemTable->SSTable_0->SSTable_1

1. 合并

• 为加快读取速度，LevelDB内部会执行Compaction操作来对已有的记录进行整理压缩，从而删除一些不再有效的记录，减少数据规模和文件数量。
• minor compaction：当MemTable大小达到阈值时，将内存数据转储到SSTable文件中。
• major compaction: 当某个层级下的SSTable文件数目超过阈值后，levelDB会从这个层级选择SSTable文件，将其和高一层级的SSTable合并。
• major compaction相当于执行一次多路归并：按照主键顺序依次迭代出所有SSTable文件中的记录，如果没有保存价值，则直接抛弃，否则将其写入到新的SSTable中。

数据模型

• 文件模型：文件系统以目录树的形式组织文件。
• 关系模块：每个关系是一个表格，由多个元组（行）构成，而每个元组又包含多个属性（列）。关系名，属性名，属性类型称为该关系的模式（Schema）。
• 键值模型：Key-Value。表格模型弱化了关系模型中的多表关联，支持基于单表的简单操作。

事务与并发控制

事务

事务规范了数据库操作的语义，每个事务使得数据库从一个一致的状态原子地转变到另一个一致的状态。具有ACID属性。

并发控制

• 写时复制
  因读事务比例远高于写事务，写时复制（copy-on-write）在读操作时不用加锁，可以极大提高读取性能。
  B-Tree copy-on-write:
  1）拷贝：将叶子节点到根节点路径上的所有节点拷贝出来
  2）修改：对拷贝的节点执行修改
  3）提交：原子地切换根节点的指针，使之指向新的根节点。
• 多版本并发控制（MVCC）
  MVCC对每行数据维护多个版本，无论事务的执行时间有多长，MVCC总是能够提供与事务开始时刻相一致的数据。
  MVCC读取时不用加锁，每个查询都通过版本检查，只获得自己需要的数据版本，从而提高并发度。但必须对每行存储额外的多个版本数据，而且需要定期删除不再需要的版本。

数据压缩

数据压缩分为有损压缩与无损压缩。有损压缩算法压缩比高，但数据可能失真，一般用于压缩图片，音频，视频；无损压缩算法能够完全还原原始数据。
压缩算法的核心是找重复数据，列式存储技术通过把相同列的数据组织在一起，不仅减少了大数据分析需要查询的数据量，还大大提高了数据的压缩比。
Huffman编码即是通过统计字符出现的频率计算最优前缀编码。
LZ系列算法一般有一个窗口的概念，在窗口内部找重复并维护数据字典。

分布式存储

数据分布

数据分布的方式主要有两种，一种是哈希，如一致性哈希（Dynamo）；一种是顺序分布，将每张表格上的数据按照主键整体有序（Bigtable）。

1. 哈希分布
   如果哈希函数的散列特性很好，哈希方式可以将数据比较均匀的分布到集群中去。
   然后找出一个散列特性很好的哈希函数是比较困难的。这是因为，如果按照主键散列，那么同一用户id下的数据可能被分散到多台服务器，这会使一次操作同一个用户id下的多条记录变得困难；如果按照用户id散列，容易出现数据倾斜（data skew）问题，即某些大用户的数据量很大，无论集群规模有多大，这些用户始终由一台服务器处理。
2. 顺序分布
   顺序分布在分布式表格系统中比较常见，一般的做法是将大表顺序划分为连续的范围，每个范围称为一个子表，总控服务器负责将这些子表按照一定得策略分配到存储节点上。
   顺序分布于B+树数据结构比较类似，每个子表相当于叶子节点，随着数据的插入和删除，某些子表可能变得很大，某些变得很小，数据分布不均匀。如果采用顺序分布，则要考虑子表的分裂与合并。

分布式协议

paxos & 2pc，这里略

容错及可扩展性

这里暂略，其他地方详述

参考链接

大规模分布式存储系统-原理解析与架构实战
NOSQL Notes