技术综述

分布式存储概念

大规模分布式存储系统的定义如下：

分布式存储系统是大量普通PC服务器通过Internet互联，对外作为一个整体提供存储服务。

分布式存储系统具有如下几个特性：

可扩展：分布式存储系统可以扩展到几百台甚至几千台的集群规模，而且随着集群规模的增长，系统整体性能表现为线性增长。
低成本：分布式存储系统的自动容错、自动负载均衡机制使其可以构建在普通PC机之上。另外线性扩展能力也使得增加、减少机器非常方便，可以实现自动运维。
高性能：无论是针对整个集群还是单台服务器，都要求分布式存储系统具备高性能。
易用：分布式存储系统需要能够提供易用的外对接口，另外也要求具备完善的监控、运维工具，并能够方便地与其他系统集成，例如从Hadoop云计算系统导入数据。

分布式存储系统的挑战主要在于数据、状态信息的持久化，要求在自动迁移、自动容错、并发读写的过程中保证数据的一致性。

分布式存储涉及的技术主要来自两个领域——分布式系统以及数据库：

数据分布：如何均匀分布数据到多台服务器？如何实现跨服务器读写操作？
一致性：如何将数据的多个副本复制到多台服务器？如何保证不同副本之间的数据一致性？
容错：如何检测服务器故障？如果自动处理数据和服务迁移？
负载均衡：新增或减少服务器时如何实现集群自动负载均衡？数据迁移的过程如何保证不影响已有服务？
事务与并发控制：如何实现分布式事务？如何实现多版本并发控制？
易用性：如何设计对外易用接口？如何设计方便的运维形式？
压缩/解压缩：如何根据数据特点设计合理的压缩/解压缩算法？如何平衡算法压缩的存储空间与消耗的CPU计算资源？

分布式存储分类

分布式存储面临的数据需求比较复杂，大致可以分为三类：

非结构化数据：包括所有格式的办公文档、文本、图片、图像、音频和视频信息等。
结构化数据：一般存储在关系数据库中，可以用二维关系表结构来表示。结构化数据的模式（Schema，包括属性、数据类型以及数据之前的联系）和内容是分开的，数据的模式需要预先定义。
半结构化数据：介于非结构化数据和结构化数据之间，HTML文档就属于半结构化数据。它一般是自描述的，与结构化数据最大的区别在于，半结构化数据的模式结构和内容混在一起，没有明显的区分，也不需要预先定义数据的模式结构。

不同分布式存储系统适合处理不同类型的数据，分布式存储系统可分为四类：

分布式文件系统
分布式键值系统
分布式表格系统
分布式数据库

分布式文件系统

分布式文件系统用于存储Blob对象（Binary Large Object，二进制大对象，非结构化数据对象，对象之间没有关联），典型的系统有Facebook Haystack以及Taobao File System（TFS）。分布式文件系统也常作为分布式表格系统以及分布式数据库的底层存储，如谷歌的GFS（Google File System，存储大文件）可以作为分布式表格系统Google Bigtable的底层存储，Amazon的EBS（Elastic Block Store，弹性块存储）系统可以作为分布式数据库Amazon RDS的底层存储。

分布式文件系统存储三种类型的数据：Blob对象、定长块以及大文件。在系统实现层面，分布式文件系统内部按照数据块（chunk）来组织数据，每个数据块的大小大致相同，每个数据块可以包含多个Blob对象或者定长块，一个大文件也可以拆分为多个数据块。分布式文件系统将这些数据块分散到存储集群，处理数据复制、一致性、负载均衡、容错等分布式系统难题，并将用户对Blob对象、定长块以及大文件的操作映射为对底层数据块的操作。

分布式键值系统

分布式键值系统用于存储关系简单的半结构化数据，它只提供基于主键的CRUD（Create/Read/Update/Delete）功能。从数据结构的角度看，分布式键值系统与传统的哈希表比较类似，不同的是分布式键值系统支持将数据分布到集群中的多个存储节点，一致性哈希是这当中常用的数据分布技术。

分布式键值系统是分布式表格系统的一种简化实现，一般用作缓存，比如Amazon Dynamo、Taobao Tair、Memcahced以及Redis等。

分布式表格系统

分布式表格系统用于存储关系较为复杂的半结构化数据，以表格为单位组织数据，与分布式键值系统相比，分布式表格系统不仅仅支持简单的CRUD操作，而且支持扫描某个主键范围。

分布式表格系统借鉴了很多关系数据库的技术，例如支持某种程度上的事务，比如单行事务，某个实体组（Entity Group，一个用户下的所有数据往往构成一个实体组）下的多行事务。

与分布式数据库相比，分布式表格系统主要支持针对单张表格的操作，不支持一些特别复杂的操作，比如多表关联、多表联接、嵌套子查询等，另外同一个表格的多个数据行也不要求包含相同类型的列，适合半结构化数据。典型的系统包括Google Bigtable、Megastore、Microsoft Azure Table Storage、Amazon DynamoDB等。

分布式数据库

分布式数据库一般是从单机关系数据库扩展而来，用于存储结构化数据。分布式数据库采用二维表格组织数据，提供SQL关系查询语言，支持多表关联，嵌套子查询等复杂操作，并提供数据库事务以及并发控制。

典型的系统包括MySQL数据库分片（MySQL Sharding）集群，Amazon RDS以及Microsoft SQL Azure。分布式数据库支持的功能最为丰富，符合用户使用习惯，但可扩展性往往受到限制。当然这一点并不是绝对的，Google Spanner系统是一个支持多数据中心的分布式数据库，它不仅支持丰富的关系数据库功能，还能扩展到多个数据中心的成千上万台机器，除此之外，阿里巴巴的OceanBase系统也是一个支持自动扩展的分布式关系数据库。

存储产品调研分析

分布式文件系统

Google File System

Google File System（GFS）是构建在廉价服务器之上的大型分布式系统。它将服务器故障视为正常现象，通过软件的方式自动容错，在保证系统可靠性和可用性的同时，大大降低系统的成本。

GFS是Google分布式存储的基石，其他存储系统，如Google Bigtable、Google Megastore、Google Percolator均直接或者间接地构建在GFS之上。另外，Google大规模批处理系统MapReduce也需要利用GFS作为海量数据的输入输出。

GFS整体架构如下：

如图，GFS系统的节点可分为三种角色：GFS Master（主控服务器）、GFS ChunkServer (CS，数据块服务器）以及GFS Client。

GFS文件被划分为固定大小的数据块（chunk），由Master在创建时分配一个64位全局唯一的chunk句柄。CS以普通的Linux文件的形式将chunk存储在磁盘中，为了保证可靠性，chunk在不同的机器中复制多份，默认为三份。

数据交互链路：

Master中维护了系统的元数据，包括文件及chunk命名空间、文件到chunk之间的映射、chunk位置信息。它也负责整个系统的全局控制，如chunk租约管理、垃圾回收以及chunk复制等。Master会定期与CS通过心跳的方式交换信息。
Client访问GFS时，首先访问Master节点，获取与之进行交互的CS信息，然后直接访问CS，完成数据存取工作。Client不缓存文件数据，只缓存Master中获取的元数据。

GFS关键问题：

租约机制：GFS通过租约（lease）机制将chunk写操作授权给CS，避免Master成为系统的性能瓶颈。
一致性模型：GFS主要是为了追加（append）而不是改写（overwrite）而设计的，追加的一致性模型相比改写要更加简单有效，在追加失败的时候，读操作只是读到过期而不是错误的数据。
追加流程：GFS默认追加的数据量都比较大，追加流程有两个特色：流水线及分离数据流与控制流。流水线操作用来减少延时，分离数据流与控制流主要是为了优化数据传输，每一台机器都是把数据发送到网络拓扑图上“最近”的尚未收到数据的机器。
容错机制：Master容错与传统方法类似，通过操作日志加checkpoint的方式进行，并且有一台称为“Shadow Master”的实时热备。CS的容错通过复制多个副本的方式实现，对于每个chunk，必须将所有的副本全部写入才视为成功，另外会对存储的数据维持校验和。

从GFS的架构设计可以看出，GFS是一个具有良好可扩展性并能够在软件层面自动处理各种异常情况的系统，由于软件层面能够做到自动化容错，底层的硬件可以采用廉价的错误率较高的硬件，比如廉价的SATA盘，大大降低云服务的成本。

GFS也证明单Master的设计是可行的，单Master的设计不仅简化了系统，而且能够更好地实现一致性。

Taobao File System

2007年以前淘宝的图片存储系统使用了昂贵的NetApp存储设备，由于淘宝数据量大且增长很快，出于性能和成本的考虑，淘宝自主研发了Blob存储系统Tao File System（TFS）。

TFS架构设计时需要考虑两个问题：

Metadata信息存储。由于图片数量巨大，单机存放不了所有的元数据信息，即单台机器无法提供元数据服务。
减少图片读取的IO次数。由于小文件个数太多，无法将所有目录及文件的inode信息缓存到内存，因此磁盘IO次数很难达到每个图片只需要一次磁盘IO的理想状态。

TFS整体架构如下：

如图，TFS系统有几个主要角色：

NameServer（NS）：相当于GFS当中的Master，采用一主一备方式，主NS故障时能被心跳守护进程检测到，将服务切换到备NS。
DataServer（DS）：相当于GFS当中的ChunkServer，每个DS会运行多个dsp进程，从而管理多个磁盘。在TFS中，不维护文件目录数，每个小文件使用一个64位编号表示，将大量的小文件（实际数据文件）合并成一个大文件，这个大文件称为块（Block，相当于GFS的Chunk），每个块拥有在集群内唯一的编号（块ID），通过<块ID，文件编号>可以唯一确定一个文件。
Client：应用客户端不缓存文件数据，只缓存NS的元数据。

TFS关键问题

追加流程：TFS的追加流程相比GFS要简单有效，因为TFS是写少读多的应用，即使每次写操作都通过NS也不会出现问题，大大简化了系统的设计——不需要租约机制，另外也不需要支持类似GFS的多客户端并发追加操作。

分布式键值系统

Amazon Dynamo

Dynamo以很简单的键值方式存储数据，不支持复杂的查询，存储的是数据值的原始形式，不解析数据的具体内容，主要用于Amazon的购物车及S3云存储服务。

Dynamo通过组合P2P的各种技术打造了线上可运行的分布式键值系统，主要面临及最终采取的解决方案如下：

问题	采用的技术
数据分布	改进的一致性哈希（虚拟节点）
复制协议	复制写协议（Replicated-write protocol，NWR参数可调）
数据冲突处理	向量时钟
临时故障处理	数据回传机制（Hinted handoff）
永久故障后的恢复	Merkle哈希树同步
成员资格及错误检测	基于Gossip的成员资格和错误检测协议

Dynamo的存储节点包含三个组件：请求协调、成员和故障检测、存储引擎。

Dynamo设计支持可插拔的存储引擎，比如Berkerly DB（BDB）、MySQL InnoDB等，默认为BDB。
请求协调组件采用基于事件驱动的设计，每个客户端的读写请求对应一个状态机，系统根据发生的事件及状态机中的状态决定下一步的操作。

Dynamo采用无中心节点的P2P设计，增加了系统可扩展性，但同时带来了一致性问题，影响上层应用，使得异常情况下的测试变得更加困难。由于只保证最基本的最终一致性，多客户端并发操作的时候很难预测操作结果，也很难预测不一致的时间窗口，影响测试用例设计。

总体上看，Dynamo的使用场景有限，主流的分布式系统一般都带有中心节点，这样能够简化设计，而且中心节点只维护少量元数据，一般不会成为性能瓶颈。

Taobao Tair

Tair是淘宝开发的一个分布式键值存储引擎，分为持久化和非持久化两种使用方式。为了解决磁盘损坏导致数据丢失，Tair可以配置数据的备份数目，Tair自动将一份数据的不同备份放到不同的节点上。

Tair整体架构如下：

Tair作为一个分布式系统，由一个中心控制节点和若干个服务节点组成。其中，中心控制结点称为Config Server，服务节点称为Data Server。Config Server负责管理所有的Data Server，维护其状态信息；Data Server对外提供各种数据服务，并以心跳的形式将自身状况汇报给Config Server。Config Server是控制点，而且是单点，目前采用一主一备的形式来保证可靠性，所有的Data Server地位都是等价的。

Tair关键问题：

数据分布：根据数据的主键计算哈希值，分布到多个桶中，桶是负载均衡和数据迁移的基本单位。根据Dynamo论文中的实验结论，桶的数量需要远大于集群的物理机器数。
容错：当某台Data Server不可用时，Config Server能够检测到。对于这台Data Server上的哈希桶，如果是备副本，那么Config Server会重新为其指定一台Data Server，如果是持久化存储，还将复制数据到新的Data Server上。如果是主副本，那么Config Server首先将某个正常的备副本提升为主副本，对外提供服务，然后再增加一个备副本。
数据迁移：迁移过程需要保证对外服务，迁移完成前，客户端的路由表没有变化，通过原节点转发的方式实现。
版本更新：客户端缓存路由表，大多数情况不需要访问Config Server，每次路由变更，Config Server会将新的配置信息推给Data Server，如果客户端访问Data Server时附带的版本号过旧，则会通过客户端去Config Server获取一份新的路由表。

与Dynamo对比，Tair引入了中心节点Config Server，这种方式很容易处理数据的一致性，不再需要向量时钟、数据回传、Merkle树、冲突处理等复杂的P2P技术，另外中心节点的负载很低，分布式键值系统的整体架构参考Tair更合理。

分布式表格系统

Google Bigtable

Google Bigtable是分布式表格系统的始祖，它采用双层结构，底层采用GFS作为持久化存储层。GFS + Bigtable双层架构是一种里程碑式的架构，其他系统，包括Microsoft分布式存储系统Windows Azure Storage以及开源的Hadoop系统，均为其模仿者。

Bigtable系统由很多表格组成，每个表格包含很多行，每行通过一个主键（Row Key）唯一标识，每行又包含很多列（Column）。某一行的某一列构成一个单元（Cell），每个单元包含多个版本数据。

Bigtable将多个列组织成列族（Column Family），列族是Bigtable中访问控制的基本单元，列名由两个部分组成：(column family, qualifier)。

从整体上看，Bigtable是一个分布式多维映射表：(row: string, column: string, timestamp: int64) -> string

Bigtable整体架构如图：

Bigtable构建在GFS之上，为文件系统增加一层分布式索引层。另外Bigtable依赖Google的Chubby（分布式锁服务）进行服务器选择及全局信息维护。

Bigtable将大表划分为大小在100-200MB的子表（tablet），每个子表对应一个连续的数据范围。

Bigtable主要由三个部分组成：客户端程序库（Client）、主控服务器（Master）和多个子表服务器（Tablet Server），职责与GFS对应角色类似。

Bigtable关键问题：

数据分布：Bigtable包含两级元数据，元数据表及根表。用户表在进行某些操作，如子表分裂的时候需要修改元数据表，元数据表的某些操作又需要修改根表，通过使用两级元数据，提高了系统能够支持的数据量。
复制与一致性：Bigtable系统保证强一致性，同一时刻同一个子表只能被一台Tablet Server服务（通过Chubby实现）。
容错：Bigtable中Master切换和Master对Tablet Server的监控是通过Chubby的独占锁实现的。
负载均衡：子表是Bigtable负载均衡的基本单位，通过Tablet Server定期向Master汇报状态检测实现。负责均衡过程中会停一会读写服务，负载均衡策略不应当过于激进。
存储：Bigtable采用Merge-dump存储引擎（类似Level DB）。

GFS + Bigtable两层架构以一种很优雅的方式兼顾系统的强一致性和可用性，但也面临一些问题：

单副本服务：Tablet Server节点出现故障时部分数据短时间内无法提供读写服务，不适合实时性要求特别高的业务。
SSD使用：随着SSD等硬件技术的发展，系统宕机的概率变得更小，SSD和SAS混合存储也变得比较常见，存储和服务分离的构架有些不太适应。
架构复杂：依赖GFS和Chubby，本身与依赖服务都比较复杂，如果出现问题难以定位。

总体来看，Bigtable架构把可扩展性和成本做到了极致，但在线实时服务能力有一定的改进空间，适合通用的离线和半线上应用结合。

分布式数据库

MySQL Sharding

为了扩展关系数据库，最简单也是最为常见的做法就是应用层按照规则将数据拆分为多个分片，分布到多个数据库节点，并引入一个中间层对应用屏蔽后端的数据库拆分细节。

以MySQL Sharding为例，整体架构如图：

主要角色如下：

MySQL客户端库：应用程序通过MySQL原生的客户端与系统交互，支持JDBC，原有的单机访问数据库程序可以无缝迁移。
中间层dbproxy：解析客户端SQL请求并转发到后端的数据库，包括解析MySQL协议、执行SQL路由、SQL过滤、读写分离、结果归并、排序以及分组等。
数据库组dbgroup：由多台数据库机器组成，采用一主多备形式，通过biglog复制到备机，备机可以支持有一定延迟的读事务。
元数据服务器：主要负责维护dbgroup拆分规则并用于dbgroup选主，元数据服务器本身也需要多个副本实现HA，一种常见的方式是采用Zookeeper实现。
常驻进程agents：部署在每台数据库服务上，用于实现监控、单点切换、安装/卸载程序等。

引入数据库中间件将后端分库分表对应用透明化这种做法实现简单，对应用友好，但也有一些问题：

数据库复制延迟：MySQL主备只支持异步复制，主库压力大时可能产生较大延迟。
扩容问题：增加新机器时涉及数据重新划分，整体过程比较复杂且容易出错。
动态数据迁移问题：数据迁移过程需要总控节点整体协调，以及数据库节点配合，很难做到自动化。