单机存储引擎就是哈希表、B树等数据结构在机械磁盘、SSD等持久化介质上的实现。
单机存储系统是单机存储引擎的一种封装，对外提供文件、键值、表格或者关系模型。

硬件基础

CPU架构

早期的CPU为单核芯片，工程师们很快意识到，仅仅提高单核的速度会产生过多的热量且无法带来相应的性能改善。因此，现代服务器基本为多核或多个CPU。经典的多CPU架构为对称多处理结构（Symmetric Multi-Processing,SMP），即在一个计算机上汇集了一组处理器，它们之间对称工作，无主次或从属关系，共享相同的物理内存及总线，如图所示。

图上SMP系统由两个CPU组成，每个CPU有两个核心（core），CPU与内存之间通过总线通信。每个核心有各自的L1d Cache（L1数据缓存）及L1i Cache（L1指令缓存），同一个CPU的多个核心共享L2以及L3缓存，另外，某些CPU还可以通过超线程技术（Hyper-Threading Technology）使得一个核心具有同时执行两个线程的能力。

SMP架构的主要特征是共享，系统中所有资源（CPU、内存、I/O等）都是共享的，由于多CPU对前端总线的竞争，SMP的扩展能力非常有限。为了提高可扩展性，现在的主流服务器架构一般为NUMA（Non-Uniform Memory Access，非一致存储访问）架构。它具有多个NUMA节点，每个NUMA节点是一个SMP结构，一般由多个CPU（如4个）组成，并且具有独立的本地内存、IO槽口等。

下图为包含4个NUMA节点的服务器架构图，NUMA节点可以直接快速访问本地内存，也可以通过NUMA互联互通模块访问其他NUMA节点的内存，访问本地内存的速度远远高于远程访问的速度。由于这个特点，为了更好地发挥系统性能，开发应用程序时需要尽量减少不同NUMA节点之间的信息交互。

IO总线

存储系统的性能瓶颈一般在于IO，因此，有必要对IO子系统的架构有一个大致的了解。以Intel x48主板为例，它是典型的南、北桥架构，如图所示。北桥芯片通过前端总线（Front Side Bus,FSB）与CPU相连，内存模块以及PCI-E设备（如高端的SSD设备Fusion-IO）挂接在北桥上。北桥与南桥之间通过DMI连接，DMI的带宽为1GB/s，网卡（包括千兆以及万兆网卡），硬盘以及中低端固态盘（如Intel 320系列SSD）挂接在南桥上。如果采用SATAZ接口，那么最大带宽为300MB/s。

网络拓扑

图2-4为传统的数据中心网络拓扑，思科过去一直提倡这样的拓扑，分为三层，最下面是接入层（Edge），中间是汇聚层（Aggregation），上面是核心层（Core）。典型的接入层交换机包含48个1Gb端口以及4个10Gb上行端口，汇聚层以及核心层的交换机包含128个10Gb的端口。传统三层结构的问题在于可能有很多接入层的交换机接到汇聚层，很多的汇聚层交换机接到核心层。同一个接入层下的服务器之间带宽为1Gb，不同接入层交换机下的服务器之间的带宽小于1Gb。由于同一个接入层的服务器往往部署在一个机架内，因此，设计系统的时候需要考虑服务器是否在一个机架内，减少跨机架拷贝大量数据。例如，Hadoop HDFS默认存储三个副本，其中两个副本放在同一个机架，就是这个原因。

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

同一个数据中心内部的传输延时是比较小的，网络一次来回的时间在1毫秒之内。数据中心之间的传输延迟是很大的，取决于光在光纤中的传输时间。例如，北京与杭州之间的直线距离大约为1300公里，光在信息传输中走折线，假设折线距离为直线距离的1.5倍，那么光传输一次网络来回延时的理论值为1300×1.5×2/300000=13毫秒，实际测试值大约为40毫秒。

性能参数

磁盘读写带宽还是不错的，15000转的SATA盘的顺序读取带宽可以达到100MB以上，由于磁盘寻道的时间大约为10ms，顺序读取1MB数据的时间为：磁盘寻道时间+数据读取时间，即10ms+1MB/100MB/s×1000=20ms。存储系统的性能瓶颈主要在于磁盘随机读写。设计存储引擎的时候会针对磁盘的特性做很多的处理，比如将随机写操作转化为顺序写，通过缓存减少磁盘随机读操作。

固态磁盘（SSD）在最近几年得到越来越多的关注，各大互联网公司都有大量基于SSD的应用。SSD的特点是随机读取延迟小，能够提供很高的IOPS（每秒读写，Input/Output Per Second）性能。它的主要问题在于容量和价格，设计存储系统的时候一般可以用来做缓存或者性能要求较高的关键业务。

存储层次架构

从分布式系统的角度看，整个集群中所有服务器上的存储介质（内存、机械硬盘，SSD）构成一个整体，其他服务器上的存储介质与本机存储介质一样都是可访问的，区别仅仅在于需要额外的网络传输及网络协议栈等访问开销。

存储系统的性能主要包括两个维度：吞吐量以及访问延时，设计系统时要求能够在保证访问延时的基础上，通过最低的成本实现尽可能高的吞吐量。磁盘和SSD的访问延时差别很大，但带宽差别不大，因此，磁盘适合大块顺序访问的存储系统，SSD适合随机访问较多或者对延时比较敏感的关键系统。二者也常常组合在一起进行混合存储，热数据（访问频繁）存储到SSD中，冷数据（访问不频繁）存储到磁盘中。

单机存储引擎

存储引擎是存储系统的发动机，直接决定了存储系统能够提供的性能和功能。存储系统的基本功能包括：增、删、读、改，其中，读取操作又分为随机读取和顺序扫描。

哈希存储引擎是哈希表的持久化实现，支持增、删、改，以及随机读取操作，但不支持顺序扫描，对应的存储系统为键值（Key-Value）存储系统；

B树（B-Tree）存储引擎是B树的持久化实现，不仅支持单条记录的增、删、读、改操作，还支持顺序扫描，对应的存储系统是关系数据库。当然，键值系统也可以通过B树存储引擎实现；

LSM树（Log-Structured Merge Tree）存储引擎和B树存储引擎一样，支持增、删、改、随机读取以及顺序扫描。它通过批量转储技术规避磁盘随机写入问题，广泛应用于互联网的后台存储系统，例如Google Bigtable、Google LevelDB以及Facebook开源的Cassandra系统。

数据模型

如果说存储引擎相当于存储系统的发动机，那么，数据模型就是存储系统的外壳。存储系统的数据模型主要包括三类：文件、关系以及随着NoSQL技术流行起来的键值模型。传统的文件系统和关系数据库系统分别采用文件和关系模型。关系模型描述能力强，产业链完整，是存储系统的业界标准。然而，随着应用在可扩展性、高并发以及性能上提出越来越高的要求，大而全的关系数据库有时显得力不从心，因此，产生了一些新的数据模型，比如键值模型，关系弱化的表格模型，等等。

文件模型

文件系统以目录树的形式组织文件，以类UNIX操作系统为例，根目录为/，包含/usr、/bin、/home等子目录，每个子目录又包含其他子目录或者文件。文件系统的操作涉及目录以及文件，例如，打开/关闭文件、读写文件、遍历目录、设置文件属性等。POSIX（Portable Operating System Interface）是应用程序访问文件系统的API标准，它定义了文件系统存储接口及操作集。POSIX主要接口如下所示。

Open/close：打开/关闭一个文件，获取文件描述符；

Read/write：读取一个文件或者往文件中写入数据；

Opendir/closedir：打开或者关闭一个目录；

Readdir：遍历目录。

POSIX标准不仅定义了文件操作接口，而且还定义了读写操作语义。例如，POSIX标准要求读写并发时能够保证操作的原子性，即读操作要么读到所有结果，要么什么也读不到；另外，要求读操作能够读到之前所有写操作的结果。POSIX标准适合单机文件系统，在分布式文件系统中，出于性能考虑，一般不会完全遵守这个标准。

NFS（Network File System）文件系统允许客户端缓存文件数据，多个客户端并发修改同一个文件时可能出现不一致的情况。举个例子，NFS客户端A和B需要同时修改NFS服务器的某个文件，每个客户端都在本地缓存了文件的副本，A修改后先提交，B后提交，那么，即使A和B修改的是文件的不同位置，也会出现B的修改覆盖A的情况。

对象模型与文件模型比较类似，用于存储图片、视频、文档等二进制数据块，典型的系统包括Amazon Simple Storage（S3），Taobao File System（TFS）。这些系统弱化了目录树的概念，Amazon S3只支持一级目录，不支持子目录，Taobao TFS甚至不支持目录结构。与文件模型不同的是，对象模型要求对象一次性写入到系统，只能删除整个对象，不允许修改其中某个部分。

关系模型

每个关系是一个表格，由多个元组（行）构成，而每个元组又包含多个属性（列）。关系名、属性名以及属性类型称作该关系的模式（schema）。例如，Movie关系的模式为Movie（title,year,length），其中，title、year、length是属性，假设它们的类型分别为字符串、整数、整数。

数据库语言SQL用于描述查询以及修改操作。数据库修改包含三条命令：INSERT、DELETE以及UPDATE，查询通常通过select-from-where语句来表达，它具有图2-9所示的一般形式。Select查询语句计算过程大致如下（不考虑查询优化）：

1）取FROM子句中列出的各个关系的元组的所有可能的组合。

2）将不符合WHERE子句中给出的条件的元组去掉。

3）如果有GROUP BY子句，则将剩下的元组按GROUP BY子句中给出的属性的值分组。

4）如果有HAVING子句，则按照HAVING子句中给出的条件检查每一个组，去掉不符合条件的组。

5）按照SELECT子句的说明，对于指定的属性和属性上的聚集（例如求和）计算出结果元组。

6）按照ORDER BY子句中的属性列的值对结果元组进行排序。

SQL查询还有一个强大的特性是允许在WHERE、FROM和HAVING子句中使用子查询，子查询又是一个完整的select-from-where语句。

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

键值模型

大量的NoSQL系统采用了键值模型（也称为Key-Value模型），每行记录由主键和值两个部分组成，支持基于主键的如下操作：

Put：保存一个Key-Value对。

Get：读取一个Key-Value对。

Delete：删除一个Key-Value对。

Key-Value模型过于简单，支持的应用场景有限，NoSQL系统中使用比较广泛的模型是表格模型。表格模型弱化了关系模型中的多表关联，支持基于单表的简单操作，典型的系统是Google Bigtable以及其开源Java实现HBase。表格模型除了支持简单的基于主键的操作，还支持范围扫描，另外，也支持基于列的操作。主要操作如下：

Insert：插入一行数据，每行包括若干列；

Delete：删除一行数据；

Update：更新整行或者其中的某些列的数据；

Get：读取整行或者其中某些列数据；

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

与关系模型不同的是，表格模型一般不支持多表关联操作，Bigtable这样的系统也不支持二级索引，事务操作支持也比较弱，各个系统支持的功能差异较大，没有统一的标准。另外，表格模型往往还支持无模式（schema-less）特性，也就是说，不需要预先定义每行包括哪些列以及每个列的类型，多行之间允许包含不同列。

SQL与NoSQL

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

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

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

联表　传统的数据库设计时需要满足范式要求，例如，第三范式要求在一个关系中不能出现在其他关系中已包含的非主键信息。假设存在一个部门信息表，其中每个部门有部门编号、部门名称、部门简介等信息，那么在员工信息表中列出部门编号后就不能加入部门名称、部门简介等部门有关的信息，否则就会有大量的数据冗余。而在海量数据的场景，为了避免数据库多表关联操作，往往会使用数据冗余等违反数据库范式的手段。实践表明，这些手段带来的收益远高于成本。

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

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

缺少统一标准。经过几十年的发展，关系数据库已经形成了SQL语言这样的业界标准，并拥有完整的生态链。然而，各个NoSQL系统使用方法不同，切换成本高，很难通用。

使用以及运维复杂。NoSQL系统无论是选型，还是使用方式，都有很大的学问，往往需要理解系统的实现，另外，缺乏专业的运维工具和运维人员。而关系数据库具有完整的生态链和丰富的运维工具，也有大量经验丰富的运维人员。

事务与并发控制

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

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

事务

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

（1）原子性

事务的原子性首先体现在事务对数据的修改，即要么全都执行，要么全都不执行，例如，从银行账户A转一笔款项a到账户B，结果必须是从A的账户上扣除款项a并且在B的账户上增加款项a，不能只是其中一个账户的修改。但是，事务的原子性并不总是能够保证修改一定完成了或者一定没有进行，例如，在ATM机器上进行上述转账，转账指令提交后通信中断或者数据库主机异常了，那么转账可能完成了也可能没有进行：如果通信中断发生前数据库主机完整接收到了转账指令且后续执行也正常，那么转账成功完成了；如果转账指令没有到达数据库主机或者虽然到达但后续执行异常（例如写操作日志失败或者账户余额不足），那么转账就没有进行。要确定转账是否成功，需要待通信恢复或者数据库主机恢复后查询账户交易历史或余额。事务的原子性也体现在事务对数据的读取上，例如，一个事务对同一数据项的多次读取的结果一定是相同的。

（2）一致性

事务需要保持数据库数据的正确性、完整性和一致性，有些时候这种一致性由数据库的内部规则保证，例如数据的类型必须正确，数据值必须在规定的范围内，等等；另外一些时候这种一致性由应用保证，例如一般情况下银行账务余额不能是负数，信用卡消费不能超过该卡的信用额度等。

（3）隔离性

许多时候数据库在并发执行多个事务，每个事务可能需要对多个表项进行修改和查询，与此同时，更多的查询请求可能也在执行中。数据库需要保证每一个事务在它的修改全部完成之前，对其他的事务是不可见的，换句话说，不能让其他事务看到该事务的中间状态，例如，从银行账户A转一笔款项a到账户B，不能让其他事务（例如账户查询）看到A账户已经扣除款项a但B账户却还没有增加款项a的状态。

（4）持久性

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

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

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

Read Committed（RC）：读取已提交的数据，但是，在一个事务中，对同一个项，前后两次读取的结果可能不一样，例如第一次读取时另一个事务的修改还没有提交，第二次读取时已经提交了；

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

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

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

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

Dirty Reads（DR）：一个事务读取了另外一个事务更新却没有提交的数据项；

Non-Repeatable Reads（NRR）：一个事务对同一数据项的多次读取可能得到不同的结果；

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

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

表2-3说明了隔离级别与读写异常（不一致）的关系。容易发现，所有的隔离级别都保证不会出现第一类丢失更新，另外，在最高隔离级别（Serializable）下，数据不会出现读写的不一致。

并发控制

1.数据库锁

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

表2-4中T1和T2两个事务操作不同行，初始时A=B=25，T1将A加100，T2将B乘以2，由于T1和T2操作不同行，两个事务没有锁冲突，可以并行执行而不会破坏系统的一致性。

表2-5中T1扫描从A到C的所有行，将它们的结果相加后更新A，初始时A=C=25，假设在T1执行过程中T2插入一行B，那么，事务T1和T2无法做到可串行化。为了保证数据库一致性，T1执行范围扫描时需要锁住从A到C这个范围的所有更新，T2插入B时，由于整个范围被锁住，T2获取锁失败而等待T1先执行完成。

多个事务并发执行可能引入死锁。表2-6中T1读取A，然后将A的值加100后更新B,T2读取B，然后将B的值乘以2更新A，初始时A=B=25。T1持有A的读锁，需要获取B的写锁，而T2持有B的读锁，需要A的写锁。T1和T2这两个事务循环依赖，任何一个事务都无法顺利完成。

解决死锁的思路主要有两种：第一种思路是为每个事务设置一个超时时间，超时后自动回滚，表2-6中如果T1或T2二者之中的某个事务回滚，则另外一个事务可以成功执行。第二种思路是死锁检测。死锁出现的原因在于事务之间互相依赖，T1依赖T2，T2又依赖T1，依赖关系构成一个环路。检测到死锁后可以通过回滚其中某些事务来消除循环依赖。

2.写时复制

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

1）拷贝：将从叶子到根节点路径上的所有节点拷贝出来。

2）修改：对拷贝的节点执行修改。

3）提交：原子地切换根节点的指针，使之指向新的根节点。

如果读操作发生在第3步提交之前，那么，将读取老节点的数据，否则将读取新节点，读操作不需要加锁保护。写时复制技术涉及引用计数，对每个节点维护一个引用计数，表示被多少节点引用，如果引用计数变为0，说明没有节点引用，可以被垃圾回收。

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

3.多版本并发控制

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

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

故障恢复

数据库运行过程中可能会发生故障，这个时候某些事务可能执行到一半但没有提交，当系统重启时，需要能够恢复到一致的状态，即要么提交整个事务，要么回滚。数据库系统以及其他的分布式存储系统一般采用操作日志（有时也称为提交日志，即Commit Log）技术来实现故障恢复。操作日志分为回滚日志（UNDO Log）、重做日志（REDO Log）以及UNDO/REDO日志。如果记录事务修改前的状态，则为回滚日志；相应地，如果记录事务修改后的状态，则为重做日志。本节介绍操作日志及故障恢复基础知识。

操作日志

为了保证数据库的一致性，数据库操作需要持久化到磁盘，如果每次操作都随机更新磁盘的某个数据块，系统性能将会很差。因此，通过操作日志顺序记录每个数据库操作并在内存中执行这些操作，内存中的数据定期刷新到磁盘，实现将随机写请求转化为顺序写请求。

操作日志记录了事务的操作。例如，事务T对表格中的X执行加10操作，初始时X=5，更新后X=15，那么，UNDO日志记为＜T,X,5＞，REDO日志记为＜T,X,15＞，UNDO/REDO日志记为＜T,X,5,15＞。

关系数据库系统一般采用UNDO/REDO日志，相关技术可以参考数据库系统实现方面的资料。可以将关系数据库存储模型做一定程度的简化：

1）假设内存足够大，每次事务的修改操作都可以缓存在内存中。

2）数据库的每个事务只包含一个操作，即每个事务都必须立即提交（Auto Commit）。

REDO日志要求我们将所有未提交事务修改的数据块保留在内存中。简化后的存储模型可以采用单一的REDO日志，大大简化了存储系统故障恢复。

重做日志

存储系统如果采用REDO日志，其写操作流程如下：

1）将REDO日志以追加写的方式写入磁盘的日志文件。

2）将REDO日志的修改操作应用到内存中。

3）返回操作成功或者失败。

REDO日志的约束规则为：在修改内存中的元素X之前，要确保与这一修改相关的操作日志必须先刷入到磁盘中。顾名思义，用REDO日志进行故障恢复，只需要从头到尾读取日志文件中的修改操作，并将它们逐个应用到内存中，即重做一遍。

为什么需要先写操作日志再修改内存中的数据呢？假如先修改内存中的数据，那么用户就能立刻读到修改后的结果，一旦在完成内存修改与写入日志之间发生故障，那么最近的修改操作无法恢复。然而，之前的用户可能已经读取了修改后的结果，这就会产生不一致的情况。

优化手段

1.成组提交

存储系统要求先将REDO日志刷入磁盘才可以更新内存中的数据，如果每个事务都要求将日志立即刷入磁盘，系统的吞吐量将会很差。因此，存储系统往往有一个是否立即刷入磁盘的选项，对于一致性要求很高的应用，可以设置为立即刷入；相应地，对于一致性要求不太高的应用，可以设置为不要求立即刷入，首先将REDO日志缓存到操作系统或者存储系统的内存缓冲区中，定期刷入磁盘。这种做法有一个问题，如果存储系统意外故障，可能丢失最后一部分更新操作。

成组提交（Group Commit）技术是一种有效的优化手段。REDO日志首先写入到存储系统的日志缓冲区中：

a）日志缓冲区中的数据量超过一定大小，比如512KB；

b）距离上次刷入磁盘超过一定时间，比如10ms。

当满足以上两个条件中的某一个时，将日志缓冲区中的多个事务操作一次性刷入磁盘，接着一次性将多个事务的修改操作应用到内存中并逐个返回客户端操作结果。与定期刷入磁盘不同的是，成组提交技术保证REDO日志成功刷入磁盘后才返回写操作成功。这种做法可能会牺牲写事务的延时，但大大提高了系统的吞吐量。

2.检查点

如果所有的数据都保存在内存中，那么可能出现两个问题：

故障恢复时需要回放所有的REDO日志，效率较低。如果REDO日志较多，比如超过100GB，那么，故障恢复时间是无法接受的。

内存不足。即使内存足够大，存储系统往往也只能够缓存最近较长一段时间的更新操作，很难缓存所有的数据。

因此，需要将内存中的数据定期转储（Dump）到磁盘，这种技术称为checkpoint（检查点）技术。系统定期将内存中的操作以某种易于加载的形式（checkpoint文件）转储到磁盘中，并记录checkpoint时刻的日志回放点，以后故障恢复只需要回放checkpoint时刻的日志回放点之后的REDO日志。

由于将内存数据转储到磁盘需要很长的时间，而这段时间还可能有新的更新操作，checkpoint必须找到一个一致的状态。checkpoint流程如下：

1）日志文件中记录"START CKPT"。

2）将内存中的数据以某种易于加载的组织方式转储到磁盘中，形成checkpoint文件。checkpoint文件中往往记录"START CKPT"的日志回放点，用于故障恢复。

3）日志文件中记录"END CKPT"。

故障恢复流程如下：

1）将checkpoint文件加载到内存中，这一步操作往往只需要加载索引数据，加载效率很高。

2）读取checkpoint文件中记录的"START CKPT"日志回放点，回放之后的REDO日志。

上述checkpoint故障恢复方式依赖REDO日志中记录的都是修改后的结果这一特性，也就是说，即使checkpoint文件中已经包含了某些操作的结果，重新回放一次或者多次这些操作的REDO日志也不会造成数据错误。如果同一个操作执行一次与重复执行多次的效果相同，这种操作具有“幂等性”。有些操作不具备这种特性，例如，加法操作、追加操作。如果REDO日志记录的是这种操作，那么checkpoint文件中的数据一定不能包含"START CKPT"与"END CKPT"之间的操作。为此，主要有两种处理方法：

checkpoint过程中停止写服务，所有的修改操作直接失败。这种方法实现简单，但不适合在线业务。

内存数据结构支持快照。执行checkpoint操作时首先对内存数据结构做一次快照，接着将快照中的数据转储到磁盘生成checkpoint文件，并记录此时对应的REDO日志回放点。生成checkpoint文件的过程中允许写操作，但checkpoint文件中的快照数据不会包含这些操作的结果。

数据压缩

数据压缩分为有损压缩与无损压缩两种，有损压缩算法压缩比率高，但数据可能失真，一般用于压缩图片、音频、视频；而无损压缩算法能够完全还原原始数据，本文只讨论无损压缩算法。早期的数据压缩技术就是基于编码上的优化技术，其中以Huffman编码最为知名，它通过统计字符出现的频率计算最优前缀编码。1977年，以色列人Jacob Ziv和Abraham Lempel发表论文《顺序数据压缩的一个通用算法》，从此，LZ系列压缩算法几乎垄断了通用无损压缩领域，常用的Gzip算法中使用的LZ77，GIF图片格式中使用的LZW，以及LZO等压缩算法都属于这个系列。设计压缩算法时不仅要考虑压缩比，还要考虑压缩算法的执行效率。Google Bigtable系统中采用BMDiff和Zippy压缩算法，这两个算法也是LZ算法的变种，它们通过牺牲一定的压缩比，换来执行效率的大幅提升。

压缩算法的核心是找重复数据，列式存储技术通过把相同列的数据组织在一起，不仅减少了大数据分析需要查询的数据量，还大大地提高了数据的压缩比。传统的OLAP（Online Analytical Processing）数据库，如Sybase IQ、Teradata，以及Bigtable、HBase等分布式表格系统都实现了列式存储。本节介绍数据压缩以及列式存储相关的基础知识。

压缩算法

压缩是一个专门的研究课题，没有通用的做法，需要根据数据的特点选择或者自己开发合适的算法。压缩的本质就是找数据的重复或者规律，用尽量少的字节表示。

Huffman编码是一种基于编码的优化技术，通过统计字符出现的频率来计算最优前缀编码。LZ系列算法一般有一个窗口的概念，在窗口内部找重复并维护数据字典。常用的压缩算法包括Gzip、LZW、LZO，这些算法都借鉴或改进了原始的LZ77算法，如Gzip压缩混合使用了LZ77以及Huffman编码，LZW以及LZO算法是LZ77思想在实现手段的进一步优化。

存储系统在选择压缩算法时需要考虑压缩比和效率。读操作需要先读取磁盘中的内容再解压缩，写操作需要先压缩再将压缩结果写入到磁盘，整个操作的延时包括压缩/解压缩和磁盘读写的延迟，压缩比越大，磁盘读写的数据量越小，而压缩/解压缩的时间也会越长，所以这里需要一个很好的权衡点。Google Bigtable系统中使用了BMDiff以及Zippy两种压缩算法，它们通过牺牲一定的压缩比换取算法执行速度的大幅提升，从而获得更好的折衷。

1.Huffman编码

前缀编码要求一个字符的编码不能是另一个字符的前缀。假设有三个字符A、B、C，它们的二进制编码分别是0、1、01，如果我们收到一段信息是01010，解码时我们如何区分是CCA还是ABABA，或者ABCA呢？一种解决方案就是前缀编码，要求一个字符编码不能是另外一个字符编码的前缀。如果使用前缀编码将A、B、C编码为：

A：0　B：10　C：110

这样，01010就只能被翻译成ABB。Huffman编码需要解决的问题是，如何找出一种前缀编码方式，使得编码的长度最短。

假设有一个字符串3334444555556666667777777，它是由3个3，4个4，5个5，6个6，7个7组成的。那么，对应的前缀编码可能是：

1）3:000　4:001　5:010　6:011　7:1

2）3:000　4:001　7:01　5:10　6:11

第1种编码方式的权值为（3+4+5+6）*3+7*1=61，而第2种编码方式的权值为（3+4）*3+（5+6+7）*2=57。可以看出，第2种编码方式的长度更短，而且我们还可以知道，第2种编码方式是最优的Huffman编码。Huffman编码的构造过程不在本书讨论范围之内，感兴趣的读者可以参考数据结构的相关图书。

2.LZ系列压缩算法

LZ系列压缩算法是基于字典的压缩算法。假设需要压缩一篇英文文章，最容易想到的压缩算法是构造一本英文字典，这样，我们只需要保存每个单词在字典中出现的页码和位置就可以了。页码用两个字节，位置用一个字节，那么一个单词需要使用三个字节表示，而我们知道一般的英语单词长度都在三个字节以上。因此，我们实现了对这篇英文文章的压缩。当然，实际的通用压缩算法不能这么做，因为我们在解压时需要一本英文字典，而这部分信息是压缩程序不可预知的，同时也不能保存在压缩信息里面。LZ系列的算法是一种动态创建字典的方法，压缩过程中动态创建字典并保存在压缩信息里面。

LZ77是第一个LZ系列的算法，比如字符串ABCABCDABC中ABC重复出现了三次，压缩信息中只需要保存第一个ABC，后面两个ABC只需要把第一个出现ABC的位置和长度存储下来就可以了。这样，保存后面两个ABC就只需要一个二元数组＜匹配串的相对位置，匹配长度＞。解压的时候，根据匹配串的相对位置，向前找到第一个ABC的位置，然后根据匹配的长度，直接把第一个ABC复制到当前解压缓冲区里面就可以了。

如表2-7所示，{S}*表示字符串S的所有子串构成的集合，例如，{ABC}*是字符串A、B、C、AB、BC、ABC构成的集合。每一步执行时如果能够在压缩字典中找到匹配串，则输出匹配信息；否则，输出源信息。执行第1步时，压缩字典为空，输出字符'A'，并将'A'加入到压缩字典；执行第2步时，压缩字典为{A}*，输出字符'B'，并将'B'加入到压缩字典；依次类推。执行到第4步和第6步时发现字符ABC之前已经出现过，输出匹配的位置和长度。

LZ系列压缩算法有如下几个问题：

1）如何区分匹配信息和源信息？通用的解决方法是额外使用一个位（bit）来区分压缩信息里面的源信息和匹配信息。

2）需要使用多少个字节表示匹配信息？记录重复信息的匹配信息包含两项，一个是匹配串的相对位置，另一个是匹配的长度。例如，可以采用固定的两个字节来表示匹配信息，其中，1位用来区分源信息和匹配信息，11位表示匹配位置，4位表示匹配长度。这样，压缩算法支持的最大数据窗口为2_{11}=2048字节，支持重复串的最大长度为2_{4}=16字节。当然，也可以采用变长的方式表示匹配信息。

3）如何快速查找最长匹配串？最容易想到的做法是把字符串的所有子串都存放到一张哈希表中，表2-7中第4步执行前哈希表中包含ABC的所有子串，即A、AB、BC、ABC。这种做法的运行效率很低，实际的做法往往会做一些改进。例如，哈希表中只保存所有长度为3的子串，如果在数据字典中找到匹配串，即前3个字节相同，接着再往后顺序遍历找出最长匹配。

3.BMDiff与Zippy

在Google的Bigtable系统中，设计了BMDiff和Zippy两种压缩算法。BMDiff和Zippy（也称为Snappy）也属于LZ系列，相比传统的LZW或者Gzip，这两种算法的压缩比不算高，但是处理速度非常快。Zippy和BMDiff的压缩/解压缩速度是Gzip算法的5～10倍。

列式存储

传统的行式数据库将一个个完整的数据行存储在数据页中。如果处理查询时需要用到大部分的数据列，这种方式在磁盘IO上是比较高效的。一般来说，OLTP（Online Transaction Processing，联机事务处理）应用适合采用这种方式。

一个OLAP类型的查询可能需要访问几百万甚至几十亿个数据行，且该查询往往只关心少数几个数据列。例如，查询今年销量最高的前20个商品，这个查询只关心三个数据列：时间（date）、商品（item）以及销售量（sales amount）。商品的其他数据列，例如商品URL、商品描述、商品所属店铺，等等，对这个查询都是没有意义的。

如图2-11所示，列式数据库是将同一个数据列的各个值存放在一起。插入某个数据行时，该行的各个数据列的值也会存放到不同的地方。上例中列式数据库只需要读取存储着“时间、商品、销量”的数据列，而行式数据库需要读取所有的数据列。因此，列式数据库大大地提高了OLAP大数据量查询的效率。当然，列式数据库不是万能的，每次读取某个数据行时，需要分别从不同的地方读取各个数据列的值，然后合并在一起形成数据行。因此，如果每次查询涉及的数据量较小或者大部分查询都需要整行的数据，列式数据库并不适用。

很多列式数据库还支持列组（column group,Bigtable系统中称为locality group），即将多个经常一起访问的数据列的各个值存放在一起。如果读取的数据列属于相同的列组，列式数据库可以从相同的地方一次性读取多个数据列的值，避免了多个数据列的合并。列组是一种行列混合存储模式，这种模式能够同时满足OLTP和OLAP的查询需求。

由于同一个数据列的数据重复度很高，因此，列式数据库压缩时有很大的优势。例如，Google Bigtable列式数据库对网页库压缩可以达到15倍以上的压缩率。另外，可以针对列式存储做专门的索引优化。比如，性别列只有两个值，“男”和“女”，可以对这一列建立位图索引：

如图2-12所示，“男”对应的位图为100101，表示第1、4、6行值为“男”；“女”对应的位图为011010，表示第2、3、5行值为“女”。如果需要查找男性或者女性的个数，只需要统计相应的位图中1出现的次数即可。另外，建立位图索引后0和1的重复度高，可以采用专门的编码方式对其进行压缩。