作者：杨传辉
出版社：机械工业出版社
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
大规模分布式存储系统:原理解析与架构实战试读：
前言
随着社交网络、移动互联网、电子商务等技术的不断发展，互联网的使用者贡献了越来越多的内容。为了处理这些内容，每个互联网公司在后端都有一套成熟的分布式系统用于数据的存储、计算以及价值提取。Google是全球最大的互联网公司，也是在分布式技术上相对成熟的公司，其公布的Google分布式文件系统GFS、分布式计算系统MapReduce、分布式表格系统Bigtable都成为业界竞相模仿的对象，最近公布的全球数据库Spanner更是能够支持分布在世界各地上百个数据中心的上百万台服务器。Google的核心技术正是后端这些处理海量数据的分布式系统。和Google类似，国外的亚马逊、微软以及国内互联网三巨头阿里巴巴、百度和腾讯的核心技术也是其后端的海量数据处理系统。
本书的内容是介绍互联网公司的大规模分布式存储系统。与传统的高端服务器、高端存储器和高端处理器不同的是，互联网公司的分布式存储系统由数量众多的、低成本和高性价比的普通PC服务器通过网络连接而成。互联网的业务发展很快，而且注重成本，这就使得存储系统不能依靠传统的纵向扩展的方式，即先买小型机，不够时再买中型机，甚至大型机。互联网后端的分布式系统要求支持横向扩展，即通过增加普通PC服务器来提高系统的整体处理能力。普通PC服务器性价比高，故障率也高，需要在软件层面实现自动容错，保证数据的一致性。另外，随着服务器的不断加入，需要能够在软件层面实现自动负载均衡，使得系统的处理能力得到线性扩展。
分布式存储和当今同样备受关注的云存储和大数据又是什么关系呢？分布式存储是基础，云存储和大数据是构建在分布式存储之上的应用。移动终端的计算能力和存储空间有限，而且有在多个设备之间共享资源的强烈的需求，这就使得网盘、相册等云存储应用很快流行起来。然而，万变不离其宗，云存储的核心还是后端的大规模分布式存储系统。大数据则更近一步，不仅需要存储海量数据，还需要通过合适的计算框架或者工具对这些数据进行分析，抽取其中有价值的部分。如果没有分布式存储，便谈不上对大数据进行分析。仔细分析还会发现，分布式存储技术是互联网后端架构的“九阳神功”，掌握了这项技能，以后理解其他技术的本质会变得非常容易。
分布式存储技术如此重要，市面上也有很多分布式系统相关的书籍。然而，这些书籍往往注重理论不重实践，且所述理论也不太适合互联网公司的大规模存储系统。这是因为，虽然分布式系统研究了很多年，但是大规模分布式存储系统是在近几年才流行起来，而且起源于以Google为首的企业界而非学术界。笔者2007年年底加入百度公司，师从阳振坤老师，从事大规模分布式存储的研究和实践工作，曾经开发过类似GFS、MapReduce和Bigtable的分布式系统，后来转战阿里巴巴继续开发分布式数据库OceanBase，维护分布式技术博客NosqlNotes（http://www.nosqlnotes.net）。笔者在业余时间阅读并理解了绝大部分分布式系统原理和各大互联网公司的系统范型相关论文，深知分布式存储系统的复杂性，也能够体会到广大读者渴望弄清楚分布式存储技术本质和实现细节的迫切心情，因而集中精力编写了这本书，希望对从事分布式存储应用的技术人员有所裨益。
本书的目标是介绍互联网公司的大规模分布式存储系统，共分为四篇：
●基础篇。基础知识包含两个部分：单机存储系统以及分布式系统。其中，单机存储系统的理论基础是数据库技术，包括数据模型、事务与并发控制、故障恢复、存储引擎、数据压缩等；分布式系统涉及数据分布、复制、一致性、容错、可扩展性等分布式技术。另外，分布式存储系统工程师还需要一项基础训练，即性能预估，因此，基础篇也会顺带介绍硬件基础知识以及性能预估方法。
●范型篇。这部分内容将介绍Google、亚马逊、微软、阿里巴巴等各大互联网公司的大规模分布式存储系统，分为四章：分布式文件系统、分布式键值系统、分布式表格系统以及分布式数据库。
●实践篇。这部分内容将以笔者在阿里巴巴开发的分布式数据库OceanBase为例详细介绍分布式数据库内部实现以及实践过程中的经验总结。
●专题篇。云存储和大数据是近年来兴起的两大热门领域，其底层都依赖分布式存储技术，这部分将简单介绍这两方面的基础知识。
本书适合互联网行业或者其他从事分布式系统实践的工程人员，也适合大学高年级本科生和研究生作为分布式系统或者云计算相关课程的参考书籍。阅读本书之前，建议首先理解分布式系统和数据库相关基础理论，接着阅读第一篇。如果对各个互联网公司的系统架构感兴趣，可以选择阅读第二篇的某些章节；如果对阿里巴巴OceanBase的架构设计和实现感兴趣，可以顺序阅读第三篇。最后，如果对云存储或者大数据感兴趣，可以选择阅读第四篇的某个章节。
感谢阳振坤老师多年以来对我在云计算和分布式数据库这两个领域的研究实践工作的指导和鼓励。感谢在百度以及阿里巴巴与我共事多年的兄弟姐妹，我们患难与共，一起实现共同的梦想。感谢机械工业出版社的吴怡编辑、新浪微博的杨卫华先生、百度的侯震宇先生以及支付宝的童家旺先生在本书撰写过程中提出的宝贵意见。
由于分布式存储技术涉及一些公司的商业机密，加上笔者水平有限、时间较紧，所以书中难免存在谬误，很多技术点涉及的细节描述得还不够详尽，恳请读者批评指正。可将任何意见和建议发送到我的邮箱knuthocean@163.com，本书相关的勘误和技术细节说明也会发布到我的个人博客NosqlNotes。我的新浪微博账号是“阿里日照”，欢迎读者通过邮件、博客或者微博与我交流分布式存储相关的任何问题。我也将密切跟踪分布式存储技术的发展，吸收您的意见，适时编写本书的升级版本。杨传辉2013年7月于北京第1章 概述
Google、Amazon、Alibaba等互联网公司的成功催生了云计算和大数据两大热门领域。无论是云计算、大数据还是互联网公司的各种应用，其后台基础设施的主要目标都是构建低成本、高性能、可扩展、易用的分布式存储系统。
虽然分布式系统研究了很多年，但是，直到近年来，互联网大数据应用的兴起才使得它大规模地应用到工程实践中。相比传统的分布式系统，互联网公司的分布式系统具有两个特点：一个特点是规模大，另一个特点是成本低。不同的需求造就了不同的设计方案，可以这么说，Google等互联网公司重新定义了大规模分布式系统。本章介绍大规模分布式系统的定义与分类。1.1 分布式存储概念
大规模分布式存储系统的定义如下：“分布式存储系统是大量普通PC服务器通过Internet互联，对外作为一个整体提供存储服务。”
分布式存储系统具有如下几个特性：
●可扩展。分布式存储系统可以扩展到几百台甚至几千台的集群规模，而且，随着集群规模的增长，系统整体性能表现为线性增长。
●低成本。分布式存储系统的自动容错、自动负载均衡机制使其可以构建在普通PC机之上。另外，线性扩展能力也使得增加、减少机器非常方便，可以实现自动运维。
●高性能。无论是针对整个集群还是单台服务器，都要求分布式存储系统具备高性能。
●易用。分布式存储系统需要能够提供易用的对外接口，另外，也要求具备完善的监控、运维工具，并能够方便地与其他系统集成，例如，从Hadoop云计算系统导入数据。
分布式存储系统的挑战主要在于数据、状态信息的持久化，要求在自动迁移、自动容错、并发读写的过程中保证数据的一致性。分布式存储涉及的技术主要来自两个领域：分布式系统以及数据库，如下所示：
●数据分布：如何将数据分布到多台服务器才能够保证数据分布均匀？数据分布到多台服务器后如何实现跨服务器读写操作？
●一致性：如何将数据的多个副本复制到多台服务器，即使在异常情况下，也能够保证不同副本之间的数据一致性？
●容错：如何检测到服务器故障？如何自动将出现故障的服务器上的数据和服务迁移到集群中其他服务器？
●负载均衡：新增服务器和集群正常运行过程中如何实现自动负载均衡？数据迁移的过程中如何保证不影响已有服务？
●事务与并发控制：如何实现分布式事务？如何实现多版本并发控制？
●易用性：如何设计对外接口使得系统容易使用？如何设计监控系统并将系统的内部状态以方便的形式暴露给运维人员？
●压缩/解压缩：如何根据数据的特点设计合理的压缩/解压缩算法？如何平衡压缩算法节省的存储空间和消耗的CPU计算资源？
分布式存储系统挑战大，研发周期长，涉及的知识面广。一般来讲，工程师如果能够深入理解分布式存储系统，理解其他互联网后台架构不会再有任何困难。1.2 分布式存储分类
分布式存储面临的数据需求比较复杂，大致可以分为三类：
●非结构化数据：包括所有格式的办公文档、文本、图片、图像、音频和视频信息等。
●结构化数据：一般存储在关系数据库中，可以用二维关系表结构来表示。结构化数据的模式（Schema，包括属性、数据类型以及数据之间的联系）和内容是分开的，数据的模式需要预先定义。
●半结构化数据：介于非结构化数据和结构化数据之间，HTML文档就属于半结构化数据。它一般是自描述的，与结构化数据最大的区别在于，半结构化数据的模式结构和内容混在一起，没有明显的区分，也不需要预先定义数据的模式结构。
不同的分布式存储系统适合处理不同类型的数据，本书将分布式存储系统分为四类：分布式文件系统、分布式键值（Key-Value）系统、分布式表格系统和分布式数据库。
1.分布式文件系统
互联网应用需要存储大量的图片、照片、视频等非结构化数据对象，这类数据以对象的形式组织，对象之间没有关联，这样的数据一般称为Blob（Binary Large Object，二进制大对象）数据。
分布式文件系统用于存储Blob对象，典型的系统有Facebook Haystack以及Taobao File System（TFS）。另外，分布式文件系统也常作为分布式表格系统以及分布式数据库的底层存储，如谷歌的GFS（Google File System，存储大文件）可以作为分布式表格系统Google Bigtable的底层存储，Amazon的EBS（Elastic Block Store，弹性块存储）系统可以作为分布式数据库（Amazon RDS）的底层存储。
总体上看，分布式文件系统存储三种类型的数据：Blob对象、定长块以及大文件。在系统实现层面，分布式文件系统内部按照数据块（chunk）来组织数据，每个数据块的大小大致相同，每个数据块可以包含多个Blob对象或者定长块，一个大文件也可以拆分为多个数据块，如图1-1所示。分布式文件系统将这些数据块分散到存储集群，处理数据复制、一致性、负载均衡、容错等分布式系统难题，并将用户对Blob对象、定长块以及大文件的操作映射为对底层数据块的操作。图 1-1 数据块与Blob对象、定长块、大文件之间的关系
2.分布式键值系统
分布式键值系统用于存储关系简单的半结构化数据，它只提供基于主键的CRUD（Create/Read/Update/Delete）功能，即根据主键创建、读取、更新或者删除一条键值记录。
典型的系统有Amazon Dynamo以及Taobao Tair。从数据结构的角度看，分布式键值系统与传统的哈希表比较类似，不同的是，分布式键值系统支持将数据分布到集群中的多个存储节点。分布式键值系统是分布式表格系统的一种简化实现，一般用作缓存，比如淘宝Tair以及Memcache。一致性哈希是分布式键值系统中常用的数据分布技术，因其被Amazon DynamoDB系统使用而变得相当有名。
3.分布式表格系统
分布式表格系统用于存储关系较为复杂的半结构化数据，与分布式键值系统相比，分布式表格系统不仅仅支持简单的CRUD操作，而且支持扫描某个主键范围。分布式表格系统以表格为单位组织数据，每个表格包括很多行，通过主键标识一行，支持根据主键的CRUD功能以及范围查找功能。
分布式表格系统借鉴了很多关系数据库的技术，例如支持某种程度上的事务，比如单行事务，某个实体组（Entity Group，一个用户下的所有数据往往构成一个实体组）下的多行事务。典型的系统包括Google Bigtable以及Megastore,Microsoft Azure Table Storage,Amazon DynamoDB等。与分布式数据库相比，分布式表格系统主要支持针对单张表格的操作，不支持一些特别复杂的操作，比如多表关联，多表联接，嵌套子查询；另外，在分布式表格系统中，同一个表格的多个数据行也不要求包含相同类型的列，适合半结构化数据。分布式表格系统是一种很好的权衡，这类系统可以做到超大规模，而且支持较多的功能，但实现往往比较复杂，而且有一定的使用门槛。
4.分布式数据库
分布式数据库一般是从单机关系数据库扩展而来，用于存储结构化数据。分布式数据库采用二维表格组织数据，提供SQL关系查询语言，支持多表关联，嵌套子查询等复杂操作，并提供数据库事务以及并发控制。
典型的系统包括MySQL数据库分片（MySQL Sharding）集群，Amazon RDS以及Microsoft SQL Azure。分布式数据库支持的功能最为丰富，符合用户使用习惯，但可扩展性往往受到限制。当然，这一点并不是绝对的。Google Spanner系统是一个支持多数据中心的分布式数据库，它不仅支持丰富的关系数据库功能，还能扩展到多个数据中心的成千上万台机器。除此之外，阿里巴巴OceanBase系统也是一个支持自动扩展的分布式关系数据库。
关系数据库是目前为止最为成熟的存储技术，它的功能极其丰富，产生了商业的关系数据库软件（例如Oracle,Microsoft SQL Server,IBM DB2，MySQL）以及上层的工具及应用软件生态链。然而，关系数据库在可扩展性上面临着巨大的挑战。传统关系数据库的事务以及二维关系模型很难高效地扩展到多个存储节点上，另外，关系数据库对于要求高并发的应用在性能上优化空间较大。为了解决关系数据库面临的可扩展性、高并发以及性能方面的问题，各种各样的非关系数据库风起云涌，这类系统成为NoSQL系统，可以理解为"Not Only SQL"系统。NoSQL系统多得让人眼花缭乱，每个系统都有自己的独到之处，适合解决某种特定的问题。这些系统变化很快，本书不会尝试去探寻某种NoSQL系统的实现，而是从分布式存储技术的角度探寻大规模存储系统背后的原理。第一篇 基础篇
本篇内容
第2章 单机存储系统
第3章 分布式系统第2章 单机存储系统
单机存储引擎就是哈希表、B树等数据结构在机械磁盘、SSD等持久化介质上的实现。单机存储系统是单机存储引擎的一种封装，对外提供文件、键值、表格或者关系模型。单机存储系统的理论来源于关系数据库。数据库将一个或多个操作组成一组，称作事务，事务必须满足原子性（Atomicity）、一致性（Consistency）、隔离性（Isolation）以及持久性（Durability），简称为ACID特性。多个事务并发执行时，数据库的并发控制管理器必须能够保证多个事务的执行结果不能破坏某种约定，如不能出现事务执行到一半的情况，不能读取到未提交的事务，等等。为了保证持久性，对于数据库的每一个变化都要在磁盘上记录日志，当数据库系统突然发生故障，重启后能够恢复到之前一致的状态。
本章首先介绍CPU、IO、网络等硬件基础知识及性能参数，接着介绍主流的单机存储引擎。其中，哈希存储引擎是哈希表的持久化实现，B树存储引擎是B树的持久化实现，而LSM树（Log Structure Merge Tree）存储引擎采用批量转储技术来避免磁盘随机写入。最后，介绍关系数据库理论基础，包括事务、并发控制、故障恢复、数据压缩等。2.1 硬件基础
硬件发展很快，摩尔定律告诉我们：每18个月计算机等IT产品的性能会翻一番；或者说相同性能的计算机等IT产品，每18个月价钱会降一半。但是，计算机的硬件体系架构保持相对稳定。架构设计很重要的一点就是合理选择并且能够最大限度地发挥底层硬件的价值。2.1.1 CPU架构
早期的CPU为单核芯片，工程师们很快意识到，仅仅提高单核的速度会产生过多的热量且无法带来相应的性能改善。因此，现代服务器基本为多核或多个CPU。经典的多CPU架构为对称多处理结构（Symmetric Multi-Processing,SMP），即在一个计算机上汇集了一组处理器，它们之间对称工作，无主次或从属关系，共享相同的物理内存及总线，如图2-1所示。图 2-1 SMP系统结构
图2-1中的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槽口等。
图2-2为包含4个NUMA节点的服务器架构图，NUMA节点可以直接快速访问本地内存，也可以通过NUMA互联互通模块访问其他NUMA节点的内存，访问本地内存的速度远远高于远程访问的速度。由于这个特点，为了更好地发挥系统性能，开发应用程序时需要尽量减少不同NUMA节点之间的信息交互。图 2-2 NUMA架构示例2.1.2 IO总线
存储系统的性能瓶颈一般在于IO，因此，有必要对IO子系统的架构有一个大致的了解。以Intel x48主板为例，它是典型的南、北桥架构，如图2-3所示。北桥芯片通过前端总线（Front Side Bus,FSB）与CPU相连，内存模块以及PCI-E设备（如高端的SSD设备Fusion-IO）挂接在北桥上。北桥与南桥之间通过DMI连接，DMI的带宽为1GB/s，网卡（包括千兆以及万兆网卡），硬盘以及中低端固态盘（如Intel 320系列SSD）挂接在南桥上。如果采用SATAZ接口，那么最大带宽为300MB/s。图 2-3 Intel X48主板南北桥架构2.1.3 网络拓扑
图2-4为传统的数据中心网络拓扑，思科过去一直提倡这样的拓扑，分为三层，最下面是接入层（Edge），中间是汇聚层（Aggregation），上面是核心层（Core）。典型的接入层交换机包含48个1Gb端口以及4个10Gb上行端口，汇聚层以及核心层的交换机包含128个10Gb的端口。传统三层结构的问题在于可能有很多接入层的交换机接到汇聚层，很多的汇聚层交换机接到核心层。同一个接入层下的服务器之间带宽为1Gb，不同接入层交换机下的服务器之间的带宽小于1Gb。由于同一个接入层的服务器往往部署在一个机架内，因此，设计系统的时候需要考虑服务器是否在一个机架内，减少跨机架拷贝大量数据。例如，Hadoop HDFS默认存储三个副本，其中两个副本放在同一个机架，就是这个原因。图 2-4 数据中心网络拓扑（三层结构）
为了减少系统对网络拓扑结构的依赖，Google在2008年的时候将网络改造为扁平化拓扑结构，即三级CLOS网络，同一个集群内最多支持20480台服务器，且任何两台都有1Gb带宽。CLOS网络需要额外投入更多的交换机，带来的好处也是明显的，设计系统时不需要考虑底层网络拓扑，从而很方便地将整个集群做成一个计算资源池。
同一个数据中心内部的传输延时是比较小的，网络一次来回的时间在1毫秒之内。数据中心之间的传输延迟是很大的，取决于光在光纤中的传输时间。例如，北京与杭州之间的直线距离大约为1300公里，光在信息传输中走折线，假设折线距离为直线距离的1.5倍，那么光传输一次网络来回延时的理论值为1300×1.5×2/300000=13毫秒，实际测试值大约为40毫秒。2.1.4 性能参数
常见硬件的大致性能参数如表2-1所示。
磁盘读写带宽还是不错的，15000转的SATA盘的顺序读取带宽可以达到100MB以上，由于磁盘寻道的时间大约为10ms，顺序读取1MB数据的时间为：磁盘寻道时间+数据读取时间，即10ms+1MB/100MB/s×1000=20ms。存储系统的性能瓶颈主要在于磁盘随机读写。设计存储引擎的时候会针对磁盘的特性做很多的处理，比如将随机写操作转化为顺序写，通过缓存减少磁盘随机读操作。
固态磁盘（SSD）在最近几年得到越来越多的关注，各大互联网公司都有大量基于SSD的应用。SSD的特点是随机读取延迟小，能够提供很高的IOPS（每秒读写，Input/Output Per Second）性能。它的主要问题在于容量和价格，设计存储系统的时候一般可以用来做缓存或者性能要求较高的关键业务。
不同的持久化存储介质对比如表2-2所示。
从表2-2可以看出，SSD单位成本提供的IOPS比传统的SAS或者SATA磁盘都要大得多，而且SSD功耗低，更加环保，适合小数据量并且对性能要求更高的场景。2.1.5 存储层次架构
从分布式系统的角度看，整个集群中所有服务器上的存储介质（内存、机械硬盘，SSD）构成一个整体，其他服务器上的存储介质与本机存储介质一样都是可访问的，区别仅仅在于需要额外的网络传输及网络协议栈等访问开销。
如图2-5所示，假设集群中有30个机架，每个机架接入40台服务器，同一个机架的服务器接入到同一个接入交换机，不同机架的服务器接入到不同的接入交换机。每台服务器的内存为24GB，磁盘为10×1TB的SATA机械硬盘（15000转）或者10×160GB的SSD固态硬盘。那么，对于每台服务器，本地内存大小为24GB，访问延时为100ns，本地SATA磁盘的大小为4TB（假设利用率为40%），随机访问的寻道时间为10ms，本地SSD磁盘的大小为1TB（假设利用率为60%），访问延时为0.1ms,SATA磁盘和SSD的访问带宽受限于SATA接口，最大不超过300MB/s。同一个机架下的服务器的内存总量大致为1TB，访问延时和带宽受限于网络，访问延时大约为300µs，带宽为100MB/s，磁盘总容量为160TB，访问延时为网络延时加上磁盘寻道时间，大约为11ms,SSD容量为40TB，访问延时为网络延时加上SSD访问延时，大约为2ms。整个集群下所有服务器的内存总量为30TB，访问延时和带宽受限于网络，跨机架访问需要经过聚合层或者核心层的交换机，访问延时大约为500µs，带宽大约为10MB/s，磁盘和SSD的访问延时分别为11ms以及2ms，带宽为10MB/s。图 2-5 存储层次结构图
存储系统的性能主要包括两个维度：吞吐量以及访问延时，设计系统时要求能够在保证访问延时的基础上，通过最低的成本实现尽可能高的吞吐量。磁盘和SSD的访问延时差别很大，但带宽差别不大，因此，磁盘适合大块顺序访问的存储系统，SSD适合随机访问较多或者对延时比较敏感的关键系统。二者也常常组合在一起进行混合存储，热数据（访问频繁）存储到SSD中，冷数据（访问不频繁）存储到磁盘中。2.2 单机存储引擎
存储引擎是存储系统的发动机，直接决定了存储系统能够提供的性能和功能。存储系统的基本功能包括：增、删、读、改，其中，读取操作又分为随机读取和顺序扫描。哈希存储引擎是哈希表的持久化实现，支持增、删、改，以及随机读取操作，但不支持顺序扫描，对应的存储系统为键值（Key-Value）存储系统；B树（B-Tree）存储引擎是B树的持久化实现，不仅支持单条记录的增、删、读、改操作，还支持顺序扫描，对应的存储系统是关系数据库。当然，键值系统也可以通过B树存储引擎实现；LSM树（Log-Structured Merge Tree）存储引擎和B树存储引擎一样，支持增、删、改、随机读取以及顺序扫描。它通过批量转储技术规避磁盘随机写入问题，广泛应用于互联网的后台存储系统，例如Google Bigtable、Google LevelDB以及Facebook开源的Cassandra系统。本节分别以Bitcask、MySQL InnoDB以及Google LevelDB系统为例介绍这三种存储引擎。2.2.1 哈希存储引擎
Bitcask是一个基于哈希表结构的键值存储系统，它仅支持追加操作（Append-only），即所有的写操作只追加而不修改老的数据。在Bitcask系统中，每个文件有一定的大小限制，当文件增加到相应的大小时，就会产生一个新的文件，老的文件只读不写。在任意时刻，只有一个文件是可写的，用于数据追加，称为活跃数据文件（active data file）。而其他已经达到大小限制的文件，称为老数据文件（older data file）。
1.数据结构
如图2-6所示，Bitcask数据文件中的数据是一条一条的写入操作，每一条记录的数据项分别为主键（key）、value内容（value）、主键长度（key_sz）、value长度（value_sz）、时间戳（timestamp）以及crc校验值。（数据删除操作也不会删除旧的条目，而是将value设定为一个特殊的值用作标识）。内存中采用基于哈希表的索引数据结构，哈希表的作用是通过主键快速地定位到value的位置。哈希表结构中的每一项包含了三个用于定位数据的信息，分别是文件编号（file id），value在文件中的位置（value_pos），value长度（value_sz），通过读取file_id对应文件的value_pos开始的value_sz个字节，这就得到了最终的value值。写入时首先将Key-Value记录追加到活跃数据文件的末尾，接着更新内存哈希表，因此，每个写操作总共需要进行一次顺序的磁盘写入和一次内存操作。图 2-6 Bitcask数据结构
Bitcask在内存中存储了主键和value的索引信息，磁盘文件中存储了主键和value的实际内容。系统基于一个假设，value的长度远大于主键的长度。假如value的平均长度为1KB，每条记录在内存中的索引信息为32字节，那么，磁盘内存比为32:1。这样，32GB内存索引的数据量为32GB×32=1TB。
2.定期合并
Bitcask系统中的记录删除或者更新后，原来的记录成为垃圾数据。如果这些数据一直保存下去，文件会无限膨胀下去，为了解决这个问题，Bitcask需要定期执行合并（Compaction）操作以实现垃圾回收。所谓合并操作，即将所有老数据文件中的数据扫描一遍并生成新的数据文件，这里的合并其实就是对同一个key的多个操作以只保留最新一个的原则进行删除，每次合并后，新生成的数据文件就不再有冗余数据了。
3.快速恢复
Bitcask系统中的哈希索引存储在内存中，如果不做额外的工作，服务器断电重启重建哈希表需要扫描一遍数据文件，如果数据文件很大，这是一个非常耗时的过程。Bitcask通过索引文件（hint file）来提高重建哈希表的速度。
简单来说，索引文件就是将内存中的哈希索引表转储到磁盘生成的结果文件。Bitcask对老数据文件进行合并操作时，会产生新的数据文件，这个过程中还会产生一个索引文件，这个索引文件记录每一条记录的哈希索引信息。与数据文件不同的是，索引文件并不存储具体的value值，只存储value的位置（与内存哈希表一样）。这样，在重建哈希表时，就不需要扫描所有数据文件，而仅仅需要将索引文件中的数据一行行读取并重建即可，大大减少了重启后的恢复时间。2.2.2 B树存储引擎
相比哈希存储引擎，B树存储引擎不仅支持随机读取，还支持范围扫描。关系数据库中通过索引访问数据，在Mysql InnoDB中，有一个称为聚集索引的特殊索引，行的数据存于其中，组织成B+树（B树的一种）数据结构。
1.数据结构
如图2-7所示，MySQL InnoDB按照页面（Page）来组织数据，每个页面对应B+树的一个节点。其中，叶子节点保存每行的完整数据，非叶子节点保存索引信息。数据在每个节点中有序存储，数据库查询时需要从根节点开始二分查找直到叶子节点，每次读取一个节点，如果对应的页面不在内存中，需要从磁盘中读取并缓存起来。B+树的根节点是常驻内存的，因此，B+树一次检索最多需要h-1次磁N盘IO，复杂度为O（h）=O（logd）（N为元素个数，d为每个节点的出度，h为B+树高度）。修改操作首先需要记录提交日志，接着修改内存中的B+树。如果内存中的被修改过的页面超过一定的比率，后台线程会将这些页面刷到磁盘中持久化。当然，InnoDB实现时做了大量的优化，这部分内容已经超出了本书的范围。图 2-7 B+树存储引擎
2.缓冲区管理
缓冲区管理器负责将可用的内存划分成缓冲区，缓冲区是与页面同等大小的区域，磁盘块的内容可以传送到缓冲区中。缓冲区管理器的关键在于替换策略，即选择将哪些页面淘汰出缓冲池。常见的算法有以下两种。（1）LRU
LRU算法淘汰最长时间没有读或者写过的块。这种方法要求缓冲区管理器按照页面最后一次被访问的时间组成一个链表，每次淘汰链表尾部的页面。直觉上，长时间没有读写的页面比那些最近访问过的页面有更小的最近访问的可能性。（2）LIRS
LRU算法在大多数情况下表现是不错的，但有一个问题：假如某一个查询做了一次全表扫描，将导致缓冲池中的大量页面（可能包含很多很快被访问的热点页面）被替换，从而污染缓冲池。现代数据库一般采用LIRS算法，将缓冲池分为两级，数据首先进入第一级，如果数据在较短的时间内被访问两次或者以上，则成为热点数据进入第二级，每一级内部还是采用LRU替换算法。Oracle数据库中的Touch Count算法和MySQL InnoDB中的替换算法都采用了类似的分级思想。以MySQL InnoDB为例，InnoDB内部的LRU链表分为两部分：新子链表（new sublist）和老子链表（old sublist），默认情况下，前者占5/8，后者占3/8。页面首先插入到老子链表，InnoDB要求页面在老子链表停留时间超过一定值，比如1秒，才有可能被转移到新子链表。当出现全表扫描时，InnoDB将数据页面载入到老子链表，由于数据页面在老子链表中的停留时间不够，不会被转移到新子链表中，这就避免了新子链表中的页面被替换出去的情况。2.2.3 LSM树存储引擎
LSM树（Log Structured Merge Tree）的思想非常朴素，就是将对数据的修改增量保持在内存中，达到指定的大小限制后将这些修改操作批量写入磁盘，读取时需要合并磁盘中的历史数据和内存中最近的修改操作。LSM树的优势在于有效地规避了磁盘随机写入问题，但读取时可能需要访问较多的磁盘文件。本节介绍LevelDB中的LSM树存储引擎。
1.存储结构
如图2-8所示，LevelDB存储引擎主要包括：内存中的MemTable和不可变MemTable（Immutable MemTable，也称为Frozen MemTable，即冻结MemTable）以及磁盘上的几种主要文件：当前（Current）文件、清单（Manifest）文件、操作日志（Commit Log，也称为提交日志）文件以及SSTable文件。当应用写入一条记录时，LevelDB会首先将修改操作写入到操作日志文件，成功后再将修改操作应用到MemTable，这样就完成了写入操作。图 2-8 LevelDB存储引擎
当MemTable占用的内存达到一个上限值后，需要将内存的数据转储到外存文件中。LevelDB会将原先的MemTable冻结成为不可变MemTable，并生成一个新的MemTable。新到来的数据被记入新的操作日志文件和新生成的MemTable中。顾名思义，不可变MemTable的内容是不可更改的，只能读取不能写入或者删除。LevelDB后台线程会将不可变MemTable的数据排序后转储到磁盘，形成一个新的SSTable文件，这个操作称为Compaction。SSTable文件是内存中的数据不断进行Compaction操作后形成的，且SSTable的所有文件是一种层级结构，第0层为Level 0，第1层为Level 1，以此类推。
SSTable中的文件是按照记录的主键排序的，每个文件有最小的主键和最大的主键。LevelDB的清单文件记录了这些元数据，包括属于哪个层级、文件名称、最小主键和最大主键。当前文件记录了当前使用的清单文件名。在LevelDB的运行过程中，随着Compaction的进行，SSTable文件会发生变化，新的文件会产生，老的文件被废弃，此时往往会生成新的清单文件来记载这种变化，而当前文件则用来指出哪个清单文件才是当前有效的。
直观上，LevelDB每次查询都需要从老到新读取每个层级的SSTable文件以及内存中的MemTable。LevelDB做了一个优化，由于LevelDB对外只支持随机读取单条记录，查询时LevelDB首先会去查看内存中的MemTable，如果MemTable包含记录的主键及其对应的值，则返回记录即可；如果MemTable没有读到该主键，则接下来到同样处于内存中的不可变Memtable中去读取；类似地，如果还是没有读到，只能依次从新到老读取磁盘中的SSTable文件。
2.合并
LevelDB写入操作很简单，但是读取操作比较复杂，需要在内存以及各个层级文件中按照从新到老依次查找，代价很高。为了加快读取速度，LevelDB内部会执行Compaction操作来对已有的记录进行整理压缩，从而删除一些不再有效的记录，减少数据规模和文件数量。
LevelDB的Compaction操作分为两种：minor compaction和major compaction。Minor compaction是指当内存中的MemTable大小到了一定值时，将内存数据转储到SSTable文件中。每个层级下有多个SSTable，当某个层级下的SSTable文件数目超过一定设置值后，levelDB会从这个层级中选择SSTable文件，将其和高一层级的SSTable文件合并，这就是major compaction。major compaction相当于执行一次多路归并：按照主键顺序依次迭代出所有SSTable文件中的记录，如果没有保存价值，则直接抛弃；否则，将其写入到新生成的SSTable文件中。2.3 数据模型
如果说存储引擎相当于存储系统的发动机，那么，数据模型就是存储系统的外壳。存储系统的数据模型主要包括三类：文件、关系以及随着NoSQL技术流行起来的键值模型。传统的文件系统和关系数据库系统分别采用文件和关系模型。关系模型描述能力强，产业链完整，是存储系统的业界标准。然而，随着应用在可扩展性、高并发以及性能上提出越来越高的要求，大而全的关系数据库有时显得力不从心，因此，产生了一些新的数据模型，比如键值模型，关系弱化的表格模型，等等。2.3.1 文件模型
文件系统以目录树的形式组织文件，以类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甚至不支持目录结构。与文件模型不同的是，对象模型要求对象一次性写入到系统，只能删除整个对象，不允许修改其中某个部分。2.3.2 关系模型
每个关系是一个表格，由多个元组（行）构成，而每个元组又包含多个属性（列）。关系名、属性名以及属性类型称作该关系的模式（schema）。例如，Movie关系的模式为Movie（title,year,length），其中，title、year、length是属性，假设它们的类型分别为字符串、整数、整数。
数据库语言SQL用于描述查询以及修改操作。数据库修改包含三条命令：INSERT、DELETE以及UPDATE，查询通常通过select-from-where语句来表达，它具有图2-9所示的一般形式。Select查询语句计算过程大致如下（不考虑查询优化）：图 2-9 SQL查询
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特性（原子性、一致性、隔离性、持久性），后续会专门介绍。2.3.3 键值模型
大量的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）特性，也就是说，不需要预先定义每行包括哪些列以及每个列的类型，多行之间允许包含不同列。2.3.4 SQL与NoSQL
随着互联网的飞速发展，数据规模越来越大，并发量越来越高，传统的关系数据库有时显得力不从心，非关系型数据库（NoSQL,Not Only SQL）应运而生。NoSQL系统带来了很多新的理念，比如良好的可扩展性，弱化数据库的设计范式，弱化一致性要求，在一定程度上解决了海量数据和高并发的问题，以至于很多人对“NoSQL是否会取代SQL”存在疑虑。然而，NoSQL只是对SQL特性的一种取舍和升华，使得SQL更加适应海量数据的应用场景，二者的优势将不断融合，不存在谁取代谁的问题。
关系数据库在海量数据场景面临如下挑战：
●事务 关系模型要求多个SQL操作满足ACID特性，所有的SQL操作要么全部成功，要么全部失败。在分布式系统中，如果多个操作属于不同的服务器，保证它们的原子性需要用到两阶段提交协议，而这个协议的性能很低，且不能容忍服务器故障，很难应用在海量数据场景。
●联表 传统的数据库设计时需要满足范式要求，例如，第三范式要求在一个关系中不能出现在其他关系中已包含的非主键信息。假设存在一个部门信息表，其中每个部门有部门编号、部门名称、部门简介等信息，那么在员工信息表中列出部门编号后就不能加入部门名称、部门简介等部门有关的信息，否则就会有大量的数据冗余。而在海量数据的场景，为了避免数据库多表关联操作，往往会使用数据冗余等违反数据库范式的手段。实践表明，这些手段带来的收益远高于成本。
●性能 关系数据库采用B树存储引擎，更新操作性能不如LSM树这样的存储引擎。另外，如果只有基于主键的增、删、查、改操作，关系数据库的性能也不如专门定制的Key-Value存储系统。
随着数据规模越来越大，可扩展性以及性能提升可以带来越来越明显的收益，而NoSQL系统要么可扩展性好，要么在特定的应用场景性能很高，广泛应用于互联网业务中。然而，NoSQL系统也面临如下问题：
●缺少统一标准。经过几十年的发展，关系数据库已经形成了SQL语言这样的业界标准，并拥有完整的生态链。然而，各个NoSQL系统使用方法不同，切换成本高，很难通用。
●使用以及运维复杂。NoSQL系统无论是选型，还是使用方式，都有很大的学问，往往需要理解系统的实现，另外，缺乏专业的运维工具和运维人员。而关系数据库具有完整的生态链和丰富的运维工具，也有大量经验丰富的运维人员。
总而言之，关系数据库很通用，是业界标准，但是在一些特定的应用场景存在可扩展性和性能的问题，NoSQL系统也有一定的用武之地。从技术学习的角度看，不必纠结SQL与NoSQL的区别，而是借鉴二者各自不同的优势，着重理解关系数据库的原理以及NoSQL系统的高可扩展性。2.4 事务与并发控制
事务规范了数据库操作的语义，每个事务使得数据库从一个一致的状态原子地转移到另一个一致的状态。数据库事务具有原子性（Atomicity）、一致性（Consistency）、隔离性（Isolation）以及持久性（Durability），即ACID属性，这些特性使得多个数据库事务并发执行时互不干扰，也不会获取到中间状态的错误结果。
多个事务并发执行时，如果它们的执行结果和按照某种顺序一个接着一个串行执行的效果等同，这种隔离级别称为可串行化。可串行化是比较理想的情况，商业数据库为了性能考虑，往往会定义多种隔离级别。事务的并发控制一般通过锁机制来实现，锁可以有不同的粒度，可以锁住行，也可以锁住数据块甚至锁住整个表格。由于互联网业务中读事务的比例往往远远高于写事务，为了提高读事务性能，可以采用写时复制（Copy-On-Write,COW）或者多版本并发控制（Multi-Version Concurrency Control,MVCC）技术来避免写事务阻塞读事务。2.4.1 事务
事务是数据库操作的基本单位，它具有原子性、一致性、隔离性和持久性这四个基本属性。（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）：可序列化，即数据库的事务是可串行化执行的，就像一个事务执行的时候没有别的事务同时在执行，这是最高的隔离级别。
试读结束[说明：试读内容隐藏了图片]