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

阿里巴巴高级技术专家（OceanBase核心开发人员）撰写，阳振坤、章文嵩、杨卫华、汪源、余锋（褚霸）、赖春波等来自阿里、新浪、网易和百度的资深技术专家联袂推荐。
系统讲解构建大规模存储系统的核心技术和原理，详细分析Google、Microsoft和阿里巴巴的大规模分布式存储系统的原理。
实战性强，通过对阿里巴巴的分布式数据库OceanBase的实现细节进行深入分析，完整讲解了大规模分布式存储系统的架构方法与应用实践。

《大规模分布式存储系统：原理解析与架构实战》是分布式系统领域的经典著作，由阿里巴巴高级技术专家“阿里日照”（OceanBase核心开发人员）撰写，阳振坤、章文嵩、杨卫华、汪源、余锋（褚霸）、赖春波等来自阿里、新浪、网易和百度的专业技术专家联袂推荐。理论方面，不仅讲解了大规模分布式存储系统的核心技术和基本原理，而且对谷歌、微软和阿里巴巴等国际型大互联网公司的大规模分布式存储系统进行了分析；实战方面，首先通过对阿里巴巴的分布式数据库OceanBase的实现细节的深入剖析完整地展示了大规模分布式存储系统的架构与设计过程，然后讲解了大规模分布式存储技术在云计算和大数据领域的实践与应用。
《大规模分布式存储系统：原理解析与架构实战》内容分为四个部分：基础篇--分布式存储系统的基础知识，包含单机存储系统的知识，如数据模型、事务与并发控制、故障恢复、存储引擎、压缩/解压缩等；分布式系统的数据分布、复制、一致性、容错、可扩展性等。范型篇--介绍谷歌、微软、阿里巴巴等知名互联网公司的大规模分布式存储系统架构，涉及分布式文件系统、分布式键值系统、分布式表格系统以及分布式数据库技术等。实践篇--以阿里巴巴的分布式数据库OceanBase为例，详细介绍分布式数据库内部实现，以及实践过程中的经验。专题篇--介绍分布式系统的主要应用：云存储和大数据，这些是近年来的热门领域，本书介绍了云存储平台、技术与安全，以及大数据的概念、流式计算、实时分析等。

杨传辉，阿里巴巴高级技术专家，花名日照，OceanBase核心开发人员，对分布式系统的理论和工程实践有深刻理解。曾在百度作为核心成员参与类MapReduce系统、类Bigtable系统和百度分布式消息队列等底层基础设施架构工作。热衷于分布式存储和计算系统设计，乐于分享，有技术博客NosqlNotes。

★分布式存储系统是分布式系统中最基础、最复杂的部分，它涉及数据的持久化、一致性和可用性，针对不同的访问需求在架构上有很多不同的取舍。本书作者在分布式存储系统方面有多年的实践经验，将所见所思所得凝聚成这本书，其中涵盖很多典型的分布式存储系统，是了解分布式系统的很好读物。
—— 章文嵩，阿里巴巴高级研究员，核心系统部负责人，LVS作者

★本书覆盖的信息量及知识点非常全面，是了解分布式存储不可多得的书籍，对指导分布式领域开发也具有重要参考价值。
—— 杨卫华，新浪微博首席架构师

★分布式存储这个领域面宽水深，无论是分布式理论、存储还是案例，铺开写都是卷帙浩繁。本书一是胜在围绕颇具广泛实用价值的基于通用硬件构建大规模分布式存储系统这一核心进行了很好的材料组织选取；二是胜在对OceanBase实现机制的深度剖析。本书作者是OceanBase的核心开发人员，对分布式存储系统身体力行，自然有很多独特的洞见。因此，本书实用性和独特性俱佳，必须入手一读。
—— 汪源，网易杭州研究院副院长

★分布式系统固有的复杂性加上大规模存储系统的工程挑战，让真正理解这个体系变得非常困难。作者在相关领域拥有多年一线开发经验，从实践工作中将相关知识萃取出来，清晰地呈现给读者。因此，我愿意将此书推荐给真正想了解分布式存储系统原理并勇于实践的读者。
—— 余锋，阿里巴巴专业技术专家，花名褚霸

★作者先后在百度、阿里巴巴等公司长期致力于大规模存储和分布式等技术的研究，对BigTable、Dynamo等业界知名存储系统也有深入的了解，同时在Pyramid、OceanBase等系统的架构、设计和开发上有过大量的实践工作。大规模存储是互联网和云计算产业的基石，而作者的这些技术是能真正应用在工业系统中的。难能可贵的是，作者将这些技术细节和系统如此有条理地展现出来，无论对大规模存储和分布式领域的初学者还是进阶者，都有巨大的帮助。
—— 赖春波，百度架构师，分布式存储技术负责人

前言

第1章概述
1.1分布式存储概念
1.2分布式存储分类

第一篇基础篇

第2章单机存储系统
2.1硬件基础
2.1.1CPU架构
2.1.2IO总线
2.1.3网络拓扑
2.1.4性能参数
2.1.5存储层次架构
2.2单机存储引擎
2.2.1哈希存储引擎
2.2.2B树存储引擎
2.2.3LSM树存储引擎
2.3数据模型
2.3.1文件模型
2.3.2关系模型
2.3.3键值模型
2.3.4SQL与NoSQL
2.4事务与并发控制
2.4.1事务
2.4.2并发控制
2.5故障恢复
2.5.1操作日志
2.5.2重做日志
2.5.3优化手段
2.6数据压缩
2.6.1压缩算法
2.6.2列式存储

第3章分布式系统
3.1基本概念
3.1.1异常
3.1.2一致性
3.1.3衡量指标
3.2性能分析
3.3数据分布
3.3.1哈希分布
3.3.2顺序分布
3.3.3负载均衡
3.4复制
3.4.1复制的概述
3.4.2一致性与可用性
3.5容错
3.5.1常见故障
3.5.2故障检测
3.5.3故障恢复
3.6可扩展性
3.6.1总控节点
3.6.2数据库扩容
3.6.3异构系统
3.7分布式协议
3.7.1两阶段提交协议
3.7.2Paxos协议
3.7.3Paxos与2PC
3.8跨机房部署

第二篇范型篇

第4章分布式文件系统
4.1Google文件系统
4.1.1系统架构
4.1.2关键问题
4.1.3Master设计
4.1.4ChunkServer设计
4.1.5讨论
4.2Taobao File System
4.2.1系统架构
4.2.2讨论
4.3Facebook Haystack
4.3.1系统架构
4.3.2讨论
4.4内容分发网络
4.4.1CDN架构
4.4.2讨论

第5章分布式键值系统
5.1Amazon Dynamo
5.1.1数据分布
5.1.2一致性与复制
5.1.3容错
5.1.4负载均衡
5.1.5读写流程
5.1.6单机实现
5.1.7讨论
5.2淘宝Tair
5.2.1系统架构
5.2.2关键问题
5.2.3讨论

第6章分布式表格系统
6.1Google Bigtable
6.1.1架构
6.1.2数据分布
6.1.3复制与一致性
6.1.4容错
6.1.5负载均衡
6.1.6分裂与合并
6.1.7单机存储
6.1.8垃圾回收
6.1.9讨论
6.2Google Megastore
6.2.1系统架构
6.2.2实体组
6.2.3并发控制
6.2.4复制
6.2.5索引
6.2.6协调者
6.2.7读取流程
6.2.8写入流程
6.2.9讨论
6.3Windows Azure Storage
6.3.1整体架构
6.3.2文件流层
6.3.3分区层
6.3.4讨论

第7章分布式数据库
7.1数据库中间层
7.1.1架构
7.1.2扩容
7.1.3讨论
7.2Microsoft SQL Azure
7.2.1数据模型
7.2.2架构
7.2.3复制与一致性
7.2.4容错
7.2.5负载均衡
7.2.6多租户
7.2.7讨论
7.3Google Spanner
7.3.1数据模型
7.3.2架构
7.3.3复制与一致性
7.3.4TrueTime
7.3.5并发控制
7.3.6数据迁移
7.3.7讨论

第三篇实践篇

第8章OceanBase架构初探
8.1背景简介
8.2设计思路
8.3系统架构
8.3.1整体架构图
8.3.2客户端
8.3.3RootServer
8.3.4MergeServer
8.3.5ChunkServer
8.3.6UpdateServer
8.3.7定期合并&数据分发
8.4架构剖析
8.4.1一致性选择
8.4.2数据结构
8.4.3可靠性与可用性
8.4.4读写事务
8.4.5单点性能
8.4.6SSD支持
8.4.7数据正确性
8.4.8分层结构

第9章分布式存储引擎
9.1公共模块
9.1.1内存管理
9.1.2基础数据结构
9.1.3锁
9.1.4任务队列
9.1.5网络框架
9.1.6压缩与解压缩
9.2RootServer实现机制
9.2.1数据结构
9.2.2子表复制与负载均衡
9.2.3子表分裂与合并
9.2.4UpdateServer选主
9.2.5RootServer主备
9.3UpdateServer实现机制
9.3.1存储引擎
9.3.2任务模型
9.3.3主备同步
9.4ChunkServer实现机制
9.4.1子表管理
9.4.2SSTable
9.4.3缓存实现
9.4.4IO实现
9.4.5定期合并&数据分发
9.4.6定期合并限速
9.5消除更新瓶颈
9.5.1读写优化回顾
9.5.2数据旁路导入
9.5.3数据分区

第10章数据库功能
10.1整体结构
10.2只读事务
10.2.1物理操作符接口
10.2.2单表操作
10.2.3多表操作
10.2.4SQL执行本地化
10.3写事务
10.3.1写事务执行流程
10.3.2多版本并发控制
10.4OLAP业务支持
10.4.1并发查询
10.4.2列式存储
10.5特色功能
10.5.1大表左连接
10.5.2数据过期与批量删除

第11章质量保证、运维及实践
11.1质量保证
11.1.1RD开发
11.1.2QA测试
11.1.3试运行
11.2使用与运维
11.2.1使用
11.2.2运维
11.3应用
11.3.1收藏夹
11.3.2天猫评价
11.3.3直通车报表
11.4最佳实践
11.4.1系统发展路径
11.4.2人员成长
11.4.3系统设计
11.4.4系统实现
11.4.5使用与运维
11.4.6工程现象
11.4.7经验法则

第四篇专题篇

第12章云存储
12.1云存储的概念
12.2云存储的产品形态
12.3云存储技术
12.4云存储的核心优势
12.5云平台整体架构
12.5.1Amazon云平台
12.5.2Google云平台
12.5.3Microsoft云平台
12.5.4云平台架构
12.6云存储技术体系
12.7云存储安全

第13章大数据
13.1大数据的概念
13.2MapReduce
13.3MapReduce扩展
13.3.1Google Tenzing
13.3.2Microsoft Dryad
13.3.3Google Pregel
13.4流式计算
13.4.1原理
13.4.2Yahoo S4
13.4.3Twitter Storm
13.5实时分析
13.5.1MPP架构
13.5.2EMC Greenplum
13.5.3HP Vertica
13.5.4Google Dremel
参考资料

第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系统的实现，而是从分布式存储技术的角度探寻大规模存储系统背后的原理。
……

随着社交网络、移动互联网、电子商务等技术的不断发展，互联网的使用者贡献了越来越多的内容。为了处理这些内容，每个互联网公司在后端都有一套成熟的分布式系统用于数据的存储、计算以及价值提取。Google是全球最大的互联网公司，也是在分布式技术上相对成熟的公司，其公布的Google分布式文件系统GFS、分布式计算系统MapReduce、分布式表格系统Bigtable都成为业界竞相模仿的对象，最近公布的全球数据库Spanner更是能够支持分布在世界各地上百个数据中心的上百万台服务器。Google的核心技术正是后端这些处理海量数据的分布式系统。和Google类似，国外的微软以及国内互联网三巨头阿里巴巴、百度和腾讯的核心技术也是其后端的海量数据处理系统。
本书的内容是介绍互联网公司的大规模分布式存储系统。与传统的高端服务器、高端存储器和高端处理器不同的是，互联网公司的分布式存储系统由数量众多的、低成本和高性价比的普通PC服务器通过网络连接而成。互联网的业务发展很快，而且注重成本，这就使得存储系统不能依靠传统的纵向扩展的方式，即先买小型机，不够时再买中型机，甚至大型机。互联网后端的分布式系统要求支持横向扩展，即通过增加普通PC服务器来提高系统的整体处理能力。普通PC服务器性价比高，故障率也高，需要在软件层面实现自动容错，保证数据的一致性。另外，随着服务器的不断加入，需要能够在软件层面实现自动负载均衡，使得系统的处理能力得到线性扩展。
分布式存储和当今同样备受关注的云存储和大数据又是什么关系呢？分布式存储是基础，云存储和大数据是构建在分布式存储之上的应用。移动终端的计算能力和存储空间有限，而且有在多个设备之间共享资源的强烈的需求，这就使得网盘、相册等云存储应用很快流行起来。然而，万变不离其宗，云存储的核心还是后端的大规模分布式存储系统。大数据则更近一步，不仅需要存储海量数据，还需要通过合适的计算框架或者工具对这些数据进行分析，抽取其中有价值的部分。如果没有分布式存储，便谈不上对大数据进行分析。仔细分析还会发现，分布式存储技术是互联网后端架构的“九阳神功”，掌握了这项技能，以后理解其他技术的本质会变得非常容易。
分布式存储技术如此重要，市面上也有很多分布式系统相关的书籍。然而，这些书籍往往注重理论不重实践，且所述理论也不太适合互联网公司的大规模存储系统。这是因为，虽然分布式系统研究了很多年，但是大规模分布式存储系统是在近几年才流行起来，而且起源于以Google为首的企业界而非学术界。笔者2007年年底加入百度公司，师从阳振坤老师，从事大规模分布式存储的研究和实践工作，曾经开发过类似GFS、MapReduce和Bigtable的分布式系统，后来转战阿里巴巴继续开发分布式数据库OceanBase，维护分布式技术博客NosqlNotes。笔者在业余时间阅读并理解了绝大部分分布式系统原理和各大互联网公司的系统范型相关论文，深知分布式存储系统的复杂性，也能够体会到广大读者渴望弄清楚分布式存储技术本质和实现细节的迫切心情，因而集中精力编写了这本书，希望对从事分布式存储应用的技术人员有所裨益。
本书的目标是介绍互联网公司的大规模分布式存储系统，共分为四篇：
基础篇。基础知识包含两个部分：单机存储系统以及分布式系统。其中，单机存储系统的理论基础是数据库技术，包括数据模型、事务与并发控制、故障恢复、存储引擎、数据压缩等；分布式系统涉及数据分布、复制、一致性、容错、可扩展性等分布式技术。另外，分布式存储系统工程师还需要一项基础训练，即性能预估，因此，基础篇也会顺带介绍硬件基础知识以及性能预估方法。
范型篇。这部分内容将介绍Google、微软、阿里巴巴等各大互联网公司的大规模分布式存储系统，分为四章：分布式文件系统、分布式键值系统、分布式表格系统以及分布式数据库。
实践篇。这部分内容将以笔者在阿里巴巴开发的分布式数据库OceanBase为例详细介绍分布式数据库内部实现以及实践过程中的经验总结。
专题篇。云存储和大数据是近年来兴起的两大热门领域，其底层都依赖分布式存储技术，这部分将简单介绍这两方面的基础知识。
本书适合互联网行业或者其他从事分布式系统实践的工程人员，也适合大学高年级本科生和研究生作为分布式系统或者云计算相关课程的参考书籍。阅读本书之前，建议首先理解分布式系统和数据库相关基础理论，接着阅读第一篇。如果对各个互联网公司的系统架构感兴趣，可以选择阅读第二篇的某些章节；如果对阿里巴巴OceanBase的架构设计和实现感兴趣，可以顺序阅读第三篇。最后，如果对云存储或者大数据感兴趣，可以选择阅读第四篇的某个章节。
感谢阳振坤老师多年以来对我在云计算和分布式数据库这两个领域的研究实践工作的指导和鼓励。感谢在百度以及阿里巴巴与我共事多年的兄弟姐妹，我们患难与共，一起实现共同的梦想。感谢机械工业出版社的吴怡编辑、新浪微博的杨卫华先生、百度的侯震宇先生以及支付宝的童家旺先生在本书撰写过程中提出的宝贵意见。
杨传辉
2013年7月于北京