单机存储引擎

存储引擎是存储系统的发动机，直接决定存储系统能够提供的性能和功能。存储系统的基本功能包括：增、删、读、改，其中，读取操作分为随机读取和顺序扫描。哈希存储引擎是哈希表的持久化实现，支持增、删、改、以及随机读取操作，但不支持顺序扫描，对应的存储系统为键值存储系统；B树存储引擎是B树的持久化实现，不仅支持单条记录的增删读改操作，还支持顺序扫描，对应的存储系统是关系数据库。当然，键值系统也可以通过B树存储引擎实现；LSM数（Log-Structured Merge Tree）存储引擎和B树存储引擎一样，支持增、删、改、随机读取以及顺序扫描。它通过批量转储技术规避磁盘随机写入问题，广泛应用于互联网的后台存储系统。例如Google Bigtable、Google LevelDB以及Facebook开源的Cassandra系统

哈希存储引擎：

Bitcask是一个基于哈希表结构的键值存储系统，它仅支持追加操作，即所有的写操作只追加而不修改老数据

B树存储引擎：

不仅支持随机读取，还支持范围扫描。关系数据库中通过索引访问数据，在Mysql InnoDB中，有一个称为聚集索引的特殊索引，行的数据存于其中，组织成B+树数据结构。Mysql InnoDB按照页面来组织数据，每个页面对应B+树的一个节点。其中，叶子节点保存每行的完整数据，非叶子节点保存索引信息。数据在每个节点中有序存储，数据查询时需要从根节点开始二分查找直到叶子节点。读取一个节点，如果对应的页面不存在内存中，需要从磁盘中读取并缓存起来。B+树根基点是常驻内存的，因此，B+树一次检索最多需要h-1次磁盘IO，h为B+树高度。修改操作首先需要记录提交日志，接着修改内存中的B+。如果内存中的被修改过的页面超过一定的比率，后台线程会将这些页面刷到磁盘中持久化。

缓存区管理：将可用的内存划分成缓冲区，缓冲区是与页面同等大小的区域，磁盘块的内容可以传送到缓冲区中。缓冲区管理器的关键在于替换策略，即选择将哪些页面淘汰出缓冲池。常见算法：

LRU（淘汰最长时间没有读写过的块，缓冲区管理器按照页面最后一次被访问的时间组成一个链表，每次淘汰链表尾部的页面），全表扫描容易污染缓冲池

LIRS，是LRU算法的升级，现代数据库一般采用LIRS算法，将缓冲池分为两级，数据首先进入第一级，如果数据在较短的时间内被访问两次或者以上，则成为热点数据进入第二级，每一级内部还是采用LRU替换算法。Oracle数据库中的Touch Count算法和MySql InnoDB中的替换算法都采用类似的分级思想。

LSM树存储引擎：(Log Structured Merge Tree)将对数据的修改增量保持在内存中，达到指定的大小限制后将这些修改操作批量写入磁盘，读取时需要合并磁盘中的历史数据和内存中最近的修改操作。LSM树的优势在于有效地规避磁盘随机写入问题。但读取时需要访问较多的磁盘文件。LevelDB存储引擎主要包括：内存中的MemTable和不可变MemTable(Immutable MemTable)以及磁盘上的几种主要文件：当前文件(Current)、清单文件(ManIfest)、操作日志(Commint Log)文件以及SSTable文件。当应用写入一条记录时，LevelDB会首先将修改操作写入到操作日志文件，成功后再将修改操作应用到MemTable,这样就完成了写入操作。

数据模型

存储引擎相当于存储系统的发动机，数据模型就是存储系统的外壳。

存储系统的数据模型主要包括三类：文件、关系以及随着NoSQL技术流行起来的键值模型。

传统的文件系统和关系数据库系统分别采用文件和关系模型。关系模型描述能力强，产业链完整，是存储系统的业界标准。然而，随着应用在可扩展性、高并发以及性能上提出越来越高的要求。大而全的关系数据库有时显得力不从心，因此，产生了一些新的数据模型，比如键值模型，关系弱化的表格模型。

文件模型  POSIX(Portable Operationg System Interace)是应用程序访问文件系统的API标准，它定义了文件系统存储接口及操作集。POSIX标准不仅定义文件操作接口，而且还定义了读写操作语义，例如要求读写并发时能够保证操作的原子性，即读操作要么读到所有结果，要么什么也读不到；另外，要求读操作能够读到之前所有写操作的结果。POSIX标准适合单机文件系统，在分布式文件系统中，出于性能考虑，一般不会完全遵守这个标准。

对象模型与文件模型比较类似，用于存储图片、视频、文档等二进制数据块。对象模型要求对象一次性写入到系统，只能删除整个对象，不允许修改其中某个部分。

关系模型  每个关系是一个表格，由多个元组构成，而每个元组又包含多个属性（列）。关系名、属性名以及属性类型称作该关系的模式。

SQL还包括两个重要的特性：索引以及事务。其中，数据库索引用于减少SQL执行时扫描的数据量，提高读取性能；数据库事务规则定了各个数据库操作的语义，保证了多个操作并发执行时ACID(原子性、一致性、隔离性、持久性)

键值模式：大量的NoSQL系统采用了键值模型，每行记录由主键和值两个部分组成，支持基于主键的如下操作：（PUT、GET、Delete）。Key-Value模型过于简单，支持的应用场景有限，NoSQL系统中使用比较广泛的模型是表格模型。表格模型弱化了关系模型中的多表关联，支持基于单表的简单操作，典型的系统是Google Bigtable以及其开源Java实现HBase。表格模型除了支持简单的基于主键的操作，还支持范围扫描，另外，也支持基于列的操作。与关系模型不同的是，表格模型一般不支持多表关联操作，Bigtable这样的系统也不支持二级索引，事务操作支持也比较弱，各个系统支持的功能差异较大，没有统一标准。另外，表格模式往往还支持无模式（schema-less）特性，也就是说，不需要预先定义每行包括哪些列以及每个列的类型，多行之间允许包含不同列

SQL与NoSQL

随着互联网的飞速发展，数据规模越来越大，并发量越来越高，传统的关系数据库有时显得力不从心，非关系数据数据库（NoSQL, Not Only SQL）应运而生。NoSQL系统带来了很多新的理念，比如良好的可扩展性，弱化数据库的涉及范式，弱化一致性要求，在一定程度上解决了海量数据和高并发的问题，以至于很多人对“NoSQL是否会取代SQL”存在疑虑。然而，NoSQL只是对SQL特性的一种取舍和升华，使得SQL更加适应海量数据的应用场景，二者的优势将不断融合，不存在谁取代谁的问题

关系数据库在海量数据场景面临如下挑战：

事务：关系模型要求多个SQL操作满足ACID特性，所有的SQL操作要么全部成功，要么全部失败。在分布式系统中，如果多个操作属于不同的服务器，保证它们的原子性需要用到两阶段提交协议，而这个协议的性能很低，而且不能容忍服务器故障，很难应用到海量数据场景。

联表：传统的数据库设计时需要满足范式要求，例如，第三范式要求在一个关系中不能出现在其他关系汇总已包含的非主键信息。而在海量数据的场景，为了避免数据库多表关联操作，往往会使用数据冗余等违反数据库范式的手段。实践表明，这些手段带来的收益远高于成本

性能：关系数据库采用B树存储引擎，更新操作性能不如LSM树这样的存储引擎。另外，如果只有基于主键的增、删、改、查操作，关系数据库的性能也不如专门定制的Key-Value存储系统

随着数据规模越来越大，可扩展性以及性能提升可以带来越来越明显的收益，而NoSQL系统要么可扩展性好，要么在特定的应用场景性能很高，广泛应用于互联网业务中。但，NoSQL系统也面临如下问题：

缺少统一标准：各个NoSQL系统使用方法不同，切换成本高，很难通用

使用以及运维复杂：NoSQL系统无论是选型，还是使用方式，都有很大学问，往往需要理解系统的实现，另外，缺乏专业的运维工具和运维人员。

总而言之，关系数据库很通用，是业界标准，但在一些特定应用场景存在可扩展性和性能问题，NoSQL系统也有一定用武之地。从技术学习角度看，不必纠结SQL与NoSQL的区别，而是借鉴二者各自不同优势，着重理解关系数据库的原理及NoSQL系统的高可扩展性。

事务与并发控制

事务规范了数据库操作的语义，每个事务使得数据库从一个一致的状态原子地转移到另一个一致的状态。数据库事务具有原子性（Atomicity）、一致性（Consistency）、隔离性（Isolation）以及持久性（Durability）,即ACID属性，这些特性使得多个数据库事务并发执行时互不干扰，也不会获取到中间状态的错误结果。

多个事务并发执行时，如果它们的执行结果和按照某种顺序一个接着一个串行执行的效果等同，这种隔离级别称为可串行化。可串行化是比较理想的情况，商业数据库为了性能考虑，往往会定义多种隔离级别。事务的并发控制一般通过锁机制来实现，锁可以有不同的粒度，可以锁住行，也可以锁住数据块甚至锁住整个表格。由于互联网业务中度事务的比例往往高于写事务，为了提高读事务性能，可以采用写时复制（Copy-On-Write, COW）或者多版本并发控制（Multi-Version Concurrency Control, MVCC）技术来避免写事务阻塞读事务。

事务：事务是数据库操作的基本单位，它具有原子性、一致性、隔离性和持久性这四个基本属性。

原子性：首先体现在事务对数据的修改，即要么全都执行，要么全都不执行。但是，事务的原子性并不总是能保证修改一定完成了或者一定没有进行。事务的原子性也体现在事务对数据的读取上，例如，一个事务对同一数据项的多次读取的结果一定是相同的

一致性：事务需要保持数据库数据的正确性、完整性和一致性，有些时候这种一致性有数据库的内部规则保证。另外一些时候这种一致性由应用保证

隔离性：许多时候数据库在并发执行多个事务，每个事务可能需要对多个表项进行修改和查询，与此同时，更多的查询请求可能也在执行中。数据库需要保证每一个事务在它的修改全部完成之前，对其他的事务是不可见的。

持久性：事务完成后，它对于数据库的影响是永久性的，即使系统出现各种异常也是如此。

处于性能考虑，许多数据库允许使用者选择隔离属性来换取并发度，从而获得性能的提升。SQL定义了4中隔离级别。

Read Uncommitted(RU):读取未提交的数据，即其他事务已经修改但还未提交的数据，这是最低的隔离级别

Read Committed(RC):读取已提交的数据，但是，在一个事务中，对同一项，前后两次读取的结果可能不一样

Repeatable Read(RR):可重复读取，在一个事务中，对同一个项，确保前后两次读取的结果一样

Serializalbe(S):可序列化，即数据库的事务是可串行化执行的，就像一个事务执行的时候没有别的事务同时在执行，这是最高的隔离级别。

隔离级别的降低可能导致到脏数据或者事务执行异常：

Lost Update(LU): 第一类丢失更新：两个事务同时修改一个数据项，但后一个事务中途失败回滚，则前一个事务已提交的修改都可能丢失

Dirty Reads(DR): 一个事务读取了另外一个事务更新却没有提交的数据项

Non-Repeatable Reads(NRR):一个事务对同一数据项的多次读取可能得到不同的结果

Second Lost Updates problem(SLU):第二类丢失更新：两个并发事务同时读取和修改同一数据项，则后面的修改可能使得前面的修改失效

Phantom Reads(PR):事务执行过程中，由于前面的插叙和后面的查询的期间有另外一个事务插入数据，后面的查询结果出现了前面查询结果中未出现的数据

所有的隔离级别都保证不会出现第一类丢失更新，在最高隔离级别(Serializable)下，数据不会出现读写的不一致。

并发控制

数据库锁：事务分为几种类型：读事务，写事务以及读写混合事务。相应地，锁也分为两种类型：读锁以及写锁，允许对同一个元素加多个读锁，但只允许加一个写锁，且写事务将阻塞读事务。这里的元素可以是一行，也可以是一个数据块甚至一个表格。事务如果只操作一行，可以对该行加相应的读锁或者写锁；如果操作多行，需要锁住整个行范围。

多个事务并发执行可能引入死锁，解决死锁的思路主要有两种：第一种思路是为每个事务设置一个超时时间，超时后自动回滚。第二种思路是死锁检测。死锁出现的原因在于事务之间相互依赖，检测到死锁后可以通过回滚其中某些事务来消除循环依赖

写时复制：互联网业务中读事务占的比例往往远远超过写事务，很多应用的读写比例达到6：1，甚至10:1。写时复制（Copy-On-Write,COW）读操作不用加锁，极大地提高率读取性能。

拷贝->修改->提交

写时复制技术涉及引用计数，对每个节点维护一个引用计数，表示被多少节点引用，如果引用计数变为0，说明没有节点引用，可以被垃圾回收。

写时复制技术原理简单，问题是每次写操作都需要拷贝从叶子到根节点路径上的所有节点，写操作成本高，另外，多个写操作之间是互斥的，同一时刻只允许一个写操作

多版本并发控制：即MVCC(Multi-Version Concurrency Control)，也能够实现读事务不加锁。MVCC对每行数据维护多个版本，无论事务的执行时间有多长，MVCC总是能够提供与事务开始时刻相一致的数据

以MySQL InnoDB存储引擎为例，InnoDB对每一行维护了两个隐含的列，其中一列存储行被修改的时间，另外一列存储行被删除的时间，注意，InnoDB存储的并不是决定时间，而是与时间对应的数据库系统的版本号，每当一个事务开始时，InnoDB都会给这个事务分配一个递增的版本号，也可以被认为是事务号。对于每一行查询语句，InnoDB都会把这个查询语句的版本号同这个查询语句遇到的行的版本号进行对比，然后结合不同的事务隔离级别，来决定是否返回该行

MVCC读取数据的时候不用加锁，每个查询都通过版本查询，只获得自己需要的数据版本，从而大大提高了系统的并发度。为了实现多版本，必须对每行存储额外的多个版本数据。另外MVCC存储引擎还必须定期删除不再需要的版本，及时回收空间

转载请注明：学时网 » 大规模分布式存储系统原理与架构（二）