前言

在这个存储系统中包含很多组件，除了核心的机头(控制器)、磁盘阵列( JBOD )和交换机等设备外，还有管理设备等辅助设备

一、集中存储结构

说到分布式存储，我们先来看一下传统的存储是怎么个样子。

传统的存储也称为集中式存储， 从概念上可以看出来是具有集中性的，也就是整个存储是集中在一个系统中的，但集中式存储并不是一个单独的设备，是集中在一套系统当中的多个设备，比如下图中的 EMC 存储就需要几个机柜来存放。

在这个存储系统中包含很多组件，除了核心的机头(控制器)、磁盘阵列( JBOD )和交换机等设备外，还有管理设备等辅助设备。

结构中包含一个机头，这个是存储系统中最为核心的部件。通常在机头中有包含两个控制器，互为备用， 避免硬件故障导致整个存储系统的不可用。机头中通常包含前端端口和后端端口，前端端口用户为服务器提供存储服务，而后端端口用于扩充存储系统的容量。通过后端端口机头可以连接更多的存储设备，从而形成一个非常大的存储资源池。

在整个结构中，机头中是整个存储系统的核心部件，整个存储系统的高级功能都在其中实现。控制器中的软件实现对磁盘的管理，将磁盘抽象化为存储资源池，然后划分为 LUN 提供给服务器使用。这里的 LUN 其实就是在服务器上看到的磁盘 。当然，一些集中式存储本身也是文件服务器，可以提供共享文件服务。无论如何，从上面我们可以看出集中式存储 最大的特点是有一个统一的入口，所有数据都要经过这个入口 ，这个入口就是存储系统的机头。

这也就是集中式存储区别于分布式存储最显著的特点。

如下图所示：

一文看懂分布式存储架构，这篇分析值得收藏 在这个存储系统中包含很多组件，除了核心的机头(控制器)、磁盘阵列(JBOD)和交换机等设备外，还有管理设备等辅助设备。

二、分布式存储

分布式存储最早是由谷歌提出的，其目的是通过廉价的服务器来提供使用与大规模，高并发场景下的Web访问问题。它 采用可扩展的系统结构，利用多台存储服务器分担存储负荷，利用位置服务器定位存储信息，它不但提高了系统的可靠性、可用性和存取效率，还易于扩展。

1 、分布式存储的兴起

分布式存储的兴起与互联网的发展密不可分，互联网公司由于其数据量大而资本积累少，而通常都使用大规模分布式存储系统。

与传统的高端服务器、高端存储器和高端处理器不同的是，互联网公司的分布式存储系统由数量众多的、低成本和高性价比的普通PC服务器通过网络连接而成。其主要原因有以下三点

(1) 互联网的业务发展很快，而且注意成本消耗，这就使得存储系统不能依靠传统的纵向扩展的方式，即先买小型机，不够时再买中型机，甚至大型机。互联网后端的分布式系统要求支持横向扩展，即通过增加普通PC服务器来提高系统的整体处理能力。

(2) 普通PC服务器性价比高，故障率也高，需要在软件层面实现自动容错，保证数据的一致性。

(3) 另外，随着服务器的不断加入，需要能够在软件层面实现自动负载均衡，使得系统的处理能力得到线性扩展。

2 、分布式存储的重要性

从单机单用户到单机多用户，再到现在的网络时代，应用系统发生了很多的变化。而分布式系统依然是目前很热门的讨论话题，那么，分布式系统给我们带来了什么，或者说是为什么要有分布式系统呢?

(1)升级单机处理能力的性价比越来越低;

企业发现通过更换硬件做垂直扩展的方式来提升性能会越来越不划算;

(2)单机处理能力存在瓶颈;

某个固定时间点，单颗处理器有自己的性能瓶颈，也就说即使愿意花更多的钱去买计算能力也买不到了;

(3)出于稳定性和可用性的考虑

如果采用单击系统，那么在这台机器正常的时候一切OK ，一旦出问题，那么系统就完全不能用了。当然，可以考虑做容灾备份等方案，而这些方案就会让系统演变为分布式系统了;

(4)云存储和大数据发展的必然要求

云存储和大数据是构建在分布式存储之上的应用。移动终端的计算能力和存储空间有限，而且有在多个设备之间共享资源的强烈的需求，这就使得网盘、相册等云存储应用很快流行起来。然而，万变不离其宗，云存储的核心还是后端的大规模分布式存储系统。大数据则更近一步，不仅需要存储海量数据，还需要通过合适的计算框架或者工具对这些数据进行分析，抽取其中有价值的部分。如果没有分布式存储，便谈不上对大数据进行分析。仔细分析还会发现，分布式存储技术是互联网后端架构的神器，掌握了这项技能，以后理解其他技术的本质会变得非常容易。

3、分布式存储的种类和比较

分布式存储包含的种类繁多，除了传统意义上的分布式文件系统、分布式块存储和分布式对象存储外，还包括分布式数据库和分布式缓存等，但其中架构无外乎于三种

A、中间控制节点架构

以HDFS (Hadoop Distribution File System)为代表的架构是典型的代表。在这种架构中，一部分节点NameNode 是存放管理数据(元数据)，另一部分节点DataNode存放业务数据，这种类型的服务器负责管理具体数据。这种架构就像公司的层次组织架构，namenode就如同老板，只管理下属的经理(datanode)，而下属的经理，而经理们来管理节点下本地盘上的数据。

一文看懂分布式存储架构，这篇分析值得收藏 在这个存储系统中包含很多组件，除了核心的机头(控制器)、磁盘阵列(JBOD)和交换机等设备外，还有管理设备等辅助设备。

B、完全无中心架构–计算模式

以 Ceph 为代表的架构是其典型的代表。在该架构中与 HDFS 不同的地方在于该架构中没有中心节点。客户端是通过一个设备映射关系 计算出来 其写入数据的位置，这样客户端可以直接与存储节点通信，从而避免中心节点的性能瓶颈。

如上图所示，在Ceph存储系统架构中核心组件有MON服务、OSD服务和MDS服务等。

(1) MON服务用于维护存储系统的硬件逻辑关系，主要是服务器和硬盘等在线信息。MON服务通过集群的方式保证其服务的可用性。

(2) OSD服务用于实现对磁盘的管理，实现真正的数据读写，通常一个磁盘对应一个OSD服务。

(3) MDS只为CephFS文件存储系统跟踪文件的层次机构和存储元数据。Ceph块设备和RADOS并不需要元数据，因此也不需要Ceph MDS守护进程

(4) RADOS ：RADOS就是包含上述三种服务的ceph存储集群。在Ceph中所有的数据都以对象形式存在的，并且无论哪种数据类型RADOS对象存储都将负责保存这些对象。RADOS层可以确保数据始终保持一致性。要做到这一点必须执行数据复制、故障检测和恢复，以及数据迁移和所在集群节点实现在平衡

(5) RBD (块设备)：原名RADOS块设备，提供可靠的分布式和高性能块存储磁盘给客户端。

(6) CephFS：Ceph文件系统提供了一个使用Ceph存储集群存储用户数据的与POSIX兼容的文件系统

(7) Librados：libRADOS库为PHP、RUBY、Java、Python、C++等语言提供了方便的访问RADOS接口的方式

(8) RADOS GW：RGW提供对象存储服务，它允许应用程序和Ceph对象存储建立连接，RGW提供了与Amazon S3和 openstack Swift兼容的RUSTFUL API

客户端访问存储的大致流程是，客户端在启动后会首先通过RADOS GW进入，从MON服务拉取存储资源布局信息，然后根据该布局信息和写入数据的名称等信息计算出期望数据的位置(包含具体的物理服务器信息和磁盘信息)，然后和该位置信息对应的CephFS对应的位置直接通信，读取或者写入数据

C、 完全无中心架构–一致性哈希

以swift为代表的架构是其典型的代表。与Ceph的通过计算方式获得数据位置的方式不同，另外一种方式是通过一致性哈希的方式获得数据位置。一致性哈希的方式就是将设备做成一个哈希环，然后根据数据名称计算出的哈希值映射到哈希环的某个位置，从而实现数据的定位。

Swift中存在两种映射关系，对于一个文件，通过哈希算法(MD5)找到对应的虚节点(一对一的映射关系)，虚节点再通过映射关系(ring文件中二维数组)找到对应的设备(多对多的映射关系)，这样就完成了一个文件存储在设备上的映射。

D 、分布式存储的比较

那么现在问题来了，如果我们要选择分布式存储，选择哪种好呢?其实它们各有各的优势和使用场景，具体要看需求。

(1)HDFS

主要用于大数据的存储场景，是Hadoop大数据架构中的存储组件。HDFS在开始设计的时候，就已经明确的它的应用场景，就是大数据服务。主要的应用场景有：

a、对大文件存储的性能比较高，例如几百兆，几个G的大文件。因为HDFS采用的是以元数据的方式进行文件管理，而元数据的相关目录和块等信息保存在NameNode的内存中， 文件数量的增加会占用大量的NameNode内存。如果存在大量的小文件，会占用大量内存空间，引起整个分布式存储性能下降，所以尽量使用HDFS存储大文件比较合适。

b、适合低写入，多次读取的业务。就大数据分析业务而言，其处理模式就是一次写入、多次读取，然后进行数据分析工作，HDFS的数据传输吞吐量比较高，但是数据读取延时比较差，不适合频繁的数据写入。

c、 HDFS采用多副本数据保护机制，使用普通的X86服务器就可以保障数据的可靠性，不推荐在虚拟化环境中使用。

(2) Ceph

目前应用最广泛的开源分布式存储系统，已得到众多厂商的支持，许多超融合系统的分布式存储都是基于Ceph深度定制。而且Ceph已经成为LINUX系统和OpenStack的 “ 标配 ” ，用于支持各自的存储系统。Ceph可以提供对象存储、块设备存储和文件系统存储服务。同时支持三种不同类型的存储服务的特性，在分布式存储系统中，是很少见的。

a、Ceph没有采用HDFS的元数据寻址的方案，而且采用CRUSH算法，数据分布均衡，并行度高。而且在支持块存储特性上，数据可以具有强一致性，可以获得传统集中式存储的使用体验。

b、对象存储服务，Ceph支持Swift和S3的API接口。在块存储方面，支持精简配置、快照、克隆。在文件系统存储服务方面，支持Posix接口，支持快照。但是目前Ceph支持文件的性能相当其他分布式存储系统，部署稍显复杂，性能也稍弱，一般都将Ceph应用于块和对象存储。

c、Ceph是去中心化的分布式解决方案，需要提前做好规划设计，对技术团队的要求能力比较高。特别是在Ceph扩容时，由于其数据分布均衡的特性，会导致整个存储系统性能的下降

(3)Swift

主要面向的是对象存储。和Ceph提供的对象存储服务类似。主要用于解决非结构化数据存储问题。它和Ceph的对象存储服务的主要区别是。

a、客户端在访问对象存储系统服务时， Swift要求客户端必须访问Swift网关才能获得数据。而Ceph使用一个运行在每个存储节点上的OSD (对象存储设备)获取数据信息，没有一个单独的入口点，比Swift更灵活一些。

b、数据一致性方面，Swift的数据是最终一致，在海量数据的处理效率上要高一些，但是主要面向对数据一致性要求不高，但是对数据处理效率要求比较高的对象存储业务。而Ceph是始终跨集群强一致性。主要的应用场景，在 OpenStack中，对象存储服务使用的就是Swift，而不是Ceph 。

三、分布式理论浅析1、一致性和可用性

由于异常的存在，分布式存储系统设计时往往会将数据冗余存储多份，每一份称为一个副本)。这样，当某一个节点出现故障时，可以从其他副本上读到数据。可以这么认为，副本是分布式存储系统容错技术的唯一手段。由于多个副本的存在，如何保证副本之间的一致性是整个分布式系统的理论核心。

数据一致性这个单词在平常开发中，或者各种文章中都能经常看见，我们常常听见什么东西数据不一致了，造成了一定的损失，赶快修复一下。那有几种一致性呢?

a、时间一致性：要求所有数据组件的数据在任意时刻都是完全一致的;

b、事物一致性：事务一致性只能存在在事务开始前的和事务完成之后，在事务过程中数据有可能不一致，比如A转 100元给B，A扣减100，B加上100，在事务开始前和事务完成之后都能保证他们的帐是对上的，那么这就是事务一致性。但是在事务过程中有可能会出现A扣减了100 元，B没有加上100元的情况，这就是不一致

c、在应用程序中涉及多个不同的单机事务，只有在所有的单机事务完成之前和完成之后，数据是完全一致的。

仅仅靠这三种一致性在实际的一些复杂场合是很难描述清楚的，所以，我们引出了一致性模型，这里我们由强到弱简单的介绍几种常见的一致性模型。

A、线性一致性

又称强一致性，可以看做只有一个单核处理器，或者可以看做只有一个数据副本，并且所有操作都是原子的。

如上图所示，对于事件e1和e2来说，如果事件e1的response是在事件e2的invoke之前，我们就说e1 happen before e2 。

对于同一个线程来说，前面的事件一定happen befor后面的事件。但是对于不同线程上的两个事件来说，它们之间只有在在时间线上没有交叉的情况下，才会存在happen before关系。对于有交叉的那些事件，比如下图中的event2和event3 ，它们两个就不存在happen before关系，对于我们要寻找的合法顺序执行过程来说，它们两个的顺序可以是任意的。

B、顺序一致性

顺序一致性弱于严格一致性。对变量的写操作不一定要在瞬间看到，但是，不同处理器对变量的写操作必须在所有处理器上以相同的顺序看到，这里处理器再分布式系统中可以换成不同的节点。

假设有两个线程A和B并发执行。其中A线程由3个操作构成，它们在程序中的顺序是：A1->A2->A3. B线程也有3个操作，它们在程序中的顺序是：B1->B2->B3. 假设如果在顺序一致的模型中的效果就是如上两个图所示。

C、因果一致性

因果一致性是弱于顺序一致性的一致性模型，顺序一致性要求所有的操作的顺序都必须按照某个单个处理器 (节点) 的顺序，而因果一致性只需要满足有因果关系的操作是顺序一致性即可。

简单来说如果有人问你一个问题，那么你给出答案，这两个就是因果关系，但如果你给出答案再问题之前，那么这个就违反了因果关系。举个简单的例子如果节点1更新了数据A，节点2读取数据A，并更新数据B，这里的数据B有可能是根据数据A计算出来的，所有具备因果关系，但是如果节点3看到的是先更新的B，再更新的那么就破坏了因果一致性。

D、最终一致性

其实除了强一致以外，其他的一致性都可以看作为最终一致性，只是根据一致性不同模型的不同要求又衍生出了很多具体一致性模型。当然最简单的最终一致性，是不需要关注中间变化的顺序，只需要保证在某个时间点一致即可。只是这个某个时间点需要根据不同的系统，不同业务再去衡量。再最终一致性完成之前，有可能返回任何的值，不会对这些值做任何顺序保证。

E、可用性

可用性指“Reads and writes always succeed” ，即服务一直可用，而且是正常响应时间。对于一个可用性的分布式系统，每一个非故障的节点必须对每一个请求作出响应。所以，一般我们在衡量一个系统的可用性的时候，都是通过停机时间来计算的。

通常我们描述一个系统的可用性时，我们说淘宝的系统可用性可以达到5个9 ，意思就是说他的可用水平是99.999% ，即全年停机时间不超过 (1-0.99999)36524*60=5.256 min，这是一个极高的要求。

好的可用性主要是指系统能够很好的为用户服务，不出现用户操作失败或者访问超时等用户体验不好的情况。一个分布式系统，上下游设计很多系统如负载均衡、WEB服务器、应用代码、数据库服务器等，任何一个节点的不稳定都可以影响可用性

F、分布式系统的一致性

2000年7月，加州大学伯克利分校的Eric Brewer教授在ACM PODC会议上提出CAP猜想。2年后，麻省理工学院的Seth Gilbert和Nancy Lynch从理论上证明了CAP之后，CAP理论正式成为分布式计算领域的公认定理。

CAP理论概述：一个分布式系统最多只能同时满足一致性(Consistency)、可用性(Availability)和分区容错性( Partition tolerance)这三项中的两项。

需要特别指出的CAP中的一致性是all nodes see the same data at the same time，也就是线性一致性。

一致性必须从两个维度看：

(1)从客户端角度，多进程并发访问时，非分布式数据库要求更新过的数据能被后续的访问都能看到，所有都是强一致的;

(2)从服务端角度，如何尽快将更新后的数据分布到整个系统，降低达到最终一致性的时间窗口，是提高系统的可用度和用户体验非常重要的方面。

参考以下公式：

N — 数据复制的份数

W — 更新数据时需要保证写完成的节点数

R — 读取数据的时候需要读取的节点数

(1) 如果W+R>N ，写的节点和读的节点重叠，则是强一致性。例如对于典型的一主一备同步复制的关系型数据库， N=2,W=2,R=1 ，则不管读的是主库还是备库的数据，都是一致的。

(2) 如果W+R<=N ，则是弱一致性。例如对于一主一备异步复制的关系型数据库，N=2,W=1,R=1 ，则如果读的是备库，就可能无法读取主库已经更新过的数据，所以是弱一致性。

对于一个分布式系统来说。P是一个基本要求，CAP三者中，只能在CA两者之间做权衡，并且要想尽办法提升 P 。

包含两种系统：CP without A**、 AP without C**

我们在上文所提到的 Hdfs 、 Ceph 、 Swift, 均是属于CP without A的这个大类，只是并不是完全没有 A ，为了实现一定的可用性，一般设置副本的个数为 N>=3 。不同的 N,W,R 组合，是在可用性和一致性之间取一个平衡，以适应不同的应用场景。

那么，实际生活中，也有一些是AP without C的案例，如 CAP 图中所示，大部分是 Nosql 、 CoachDB 、 Cassandra 数据库，那场景是哪些呢?

其实就是不要求正确性的场合，如某米的抢购手机场景或 12306 抢购火车票的场景，可能前几秒你浏览商品的时候页面提示是有库存的，当你选择完商品准备下单的时候，系统提示你下单失败，商品已售完。这其实就是先在 A(可用性)方面保证系统可以正常的服务，然后在数据的一致性方面做了些牺牲。

2、数据分布

分布式系统区别于传统单机系统在于能够将数据分布到多个节点，并在多个节点之间实现负载均衡。数据分布的方式主要有两种，一种是哈希分布，如一致性哈希，代表系统为

Amazon的Dynamo系统，Openstack的Swift 系统;另外一种方法是顺序分布，即每张表格上的数据按照主键整体有序，代表系统为Google的Bigtable系统。Bigtable将一张大表根据主键切分为有序的范围，每个有序范围是一个子表。

A 、哈希分布( Swift )

哈希函数的散列特性很好，哈希方式可以将数据比较均匀地分布到集群中去。而且，哈希方式需要记录的元信息也非常简单，每个节点只需要知道哈希函数的计算方式以及模的服务器的个数就可以计算出处理的数据应该属于哪台机器。

然而，找出一个散列特性很好的哈希函数是很难的。这是因为，如果按照主键散列，那么同一个用户id下的数据可能被分散到多台服务器，这会使得一次操作同一个用户id下的多条记录变得困难;如果按照用户id散列，容易出现 “ 数据倾斜 ” (data skew)问题，即某些大用户的数据量很大，无论集群的规模有多大，这些用户始终由一台服务器处理。

处理大用户问题一般有两种方式，一种方式是手动拆分，即线下标记系统中的大用户(例如运行一次MapReduce作业)，并根据这些大用户的数据量将其拆分到多台服务器上。这就相当于在哈希分布的基础上针对这些大用户特殊处理;

另一种方式是自动拆分，即数据分布算法能够动态调整，自动将大用户的数据拆分到多台服务器上。其中包含两种算法。

一种是传统的哈希算法，访问数据时，首先计算哈希值，再查询元数据服务器，获得该哈希值对应的服务器。在这种算法下，服务器的上线和下线将导致大量的数据迁移，不适合于生产。

另一致性哈希(Distributed Hash Table,DHT)算法。算法思想如下：给系统中每个节点分配一个随机token，这些 token构成一个哈希环。执行数据存放操作时，先计算Key (主键)的哈希值，然后存放到顺时针方向第一个大于或者等于该哈希值的token所在的节点。一致性哈希的优点在于节点加入/删除时只会影响到在哈希环中相邻的节点，而对其他节点没影响。

如上图所示，算法本身的特性可以使得 磁盘划分为比较多的较为均匀的虚拟分区，每个虚拟分区是哈希环上的一个节点，整个环是从0到32位最大值的一个区间，并且首尾相连，当计算出数据(或者数据名称)的哈希值后，必然落到哈希环的某个区间，然后以顺时针，必然能够找到一个节点。那么这个节点就是存储数据的位置。可见如果只有一个节点，最大到32还未找到节点，那么数据就在第一个唯一节点上。

整个的数据定位就是基于上述的一致算法，实现将请求重新定向到该设备进行处理

(1) 在对象存储上，通过账户名/容器名/对象名三个名称组成一个位置的标识，通过该唯一标识可以计算出一个整型数;

(2) 存储设备方面，Swift构建一个虚拟分区表，表的大小在创建集群是确定(通常为几十万)，这个表其实就是一个数组;

(3) 整数值和这个数组，通过一致性哈希算法就可以确定该整数在数组的位置。

一致性算法原理上可以保证数据的均衡性、单调性，避免数据的分散性，有效的保证数据的一致性，使得负载尽可能的被映射到一个特定的缓存区。

因为 一致性哈希算法在服务节点太少时，容易因为节点分部不均匀而造成数据倾斜问题。所以在实际应用中，通常将虚拟节点数设置为比 32 更大的值，因此即使很少的服务节点也能做到相对均匀的数据分布。

B 、顺序分布(Bigtable)

哈希散列破坏了数据的有序性，只支持随机读取操作，不能够支持顺序扫描。某些系统可以在应用层做折衷，比如互联网应用经常按照用户来进行数据拆分，并通过哈希方法进行数据分布，同一个用户的数据分布到相同的存储节点，允许对同一个用户的数据执行顺序扫描，由应用层解决跨多个用户的操作问题。另外，这种方式可能出现某些用户的数据量太大的问题，由于用户的数据限定在一个存储节点，无法发挥分布式存储系统的多机并行处理能力。

顺序分布在分布式表格系统(Bigtable)中比较常见，一般的做法是将大表顺序划分为连续的范围，每个范围称为一个子表，总控服务器负责将这些子表按照一定的策略分配到存储节点上。

如图所示，用户表(User表)的主键范围为1～7000，在分布式存储系统中划分为多个子表，分别对应数据范围1～1000 ，1001～2000 ，……6001～7000。其中Meta表是为了支持更大的集群规模，它将原来的一层索引结分成两层，使用Meta表来维护 User 子表所在的节点，从而减轻Root节点的负担。

顺序分布与B+树数据结构比较类似，每个子表相当于叶子节点，随着数据的插入和删除，某些子表可能变得很大，某些变得很小，数据分布不均匀。如果采用顺序分布，系统设计时需要考虑子表的分裂与合并，这将极大地增加系统复杂度。

C、CRUSH分布

CRUSH算法，全称叫Controlled, Scalable, Decentralized Placement of Replicated Data.严格说起来 Crush算法，其实也是以Hash算法为基础的。只不过映射的方法和一致性哈希不同。我们用Ceph分布的过程来加以说明。

Ceph分布数据的过程：首先计算数据x的Hash值并将结果和PG数目取余，以得到数据x对应的PG 编号。然后，通过CRUSH算法将PG映射到一组OSD中。最后把数据x存放到PG对应的OSD中。注明：PG全称是Placement Group(放置组)。

这个过程中包含了两次映射，第一次是数据x到PG 的映射。如果把PG当作存储节点，那么传统Hash算法一样。不同的是，PG是抽象的存储节点，它不会随着物理节点的加入或则离开而增加或减少，因此数据到PG的映射是稳定的。

以Dynamo为例，在这个过程中，PG起到了两个作用：第一个作用是划分数据分区。每个PG管理的数据区间相同，因而数据能够均匀地分布到PG上;第二个作用是充当Dynamo中Token的角色，即决定分区位置。实际上，这和Dynamo中固定分区数目，以及维持分区数目和虚拟节点数目相等的原则是同一回事。

以Ceph为例，CRUSH算法通过两次映射计算数据存储位置来确定如何存储和检索数据。CRUSH使Ceph客户机能够直接与OSDs通信，而不是通过集中的服务器或代理。

通过算法确定的数据存储和检索方法，Ceph避免了单点故障、性能瓶颈和对其可伸缩性的物理限制。CRUSH需要集群的映射，并使用CRUSH映射在OSDs中伪随机存储和检索数据，数据在集群中均匀分布。

3、复制

为了保证分布式存储系统的高可靠和高可用，数据在系统中一般存储多个副本。当某个副本所在的存储节点出现故障时，分布式存储系统能够自动将服务切换到其他的副本，从而实现自动容错。分布式存储系统通过复制协议将数据同步到多个存储节点，并确保多个副本之间的数据一致性。

A、强同步复制

客户端将写请求发送给主副本，主副本将写请求复制到其他备副本，常见的做法是同步操作日志( Commit Log )。主副本首先将操作日志同步到备副本，备副本回放操作日志，完成后通知主副本。接着，主副本修改本机，等到所有的操作都完成后再通知客户端写成功。下图中的复制协议要求主备同步成功才可以返回客户端写成功，这种协议称为强同步协议。

假设所有副本的个数为N，且N>2，即备副本个数大于1。那么，实现强同步协议时，主副本可以将操作日志并发地发给所有备副本并等待回复，只要至少1个备副本返回成功就可以回复客户端操作成功。强同步的好处在于如果主副本出现故障，至少有1个备副本拥有完整的数据，分布式存储系统可以自动地将服务切换到最新的备副本而不用担心数据丢失的情况。

B、异步复制

与强同步对应的复制方式是异步复制。在异步模式下，主副本不需要等待备副本的回应，只需要本地修改成功就可以告知客户端写操作成功。另外，主副本通过异步机制，比如单独的复制线程将客户端修改操作推送到其他副本。异步复制的好处在于系统可用性较好，但是一致性较差，如果主副本发生不可恢复故障，可能丢失最后一部分更新操作。

C、NWR复制

分布式存储系统中还可能使用基于写多个存储节点的复制协议(Replicated-write protocol)。比如Dynamo系统中的NWR复制协议，其中，N为副本数量，W为写操作的副本数，R为读操作的副本数。

NWR协议中多个副本不再区分主和备，客户端根据一定的策略往其中的W个副本写入数据，读取其中的R个副本。只要W+R>N ，可以保证读到的副本中至少有一个包含了最新的更新。然而，这种协议的问题在于不同副本的操作顺序可能不一致，从多个副本读取时可能出现冲突。这种方式在实际系统中比较少见，不建议使用。

4、分布式协议

分布式协议有很多，其中以两阶段提交和Paxos协议最具代表性。两阶段提交协议(2PC)或三阶段提交(3PC)用于保证跨多个节点操作的原子性，也就是说，跨多个节点的操作要么在所有节点上全部执行成功，要么全部失败。Paxos协议用于确保多个节点对某个投票(例如哪个节点为主节点)达成一致。

A、两阶段提交

二阶段提交的算法思路可以概括为 : 参与者将操作成败通知协调者，再由协调者根据所有参与者的反馈情报决定各参与者是否要提交操作还是中止操作。

(1)请求阶段 (表决) ：

事务协调者协调者通知事务参与者准备提交或者取消事务，然后进入表决过程。在表决过程中，参与者将告知协调者自己的决策：同意(事务参与者本地执行成功)或者取消(事务参与者本地执行失败)。

(2)提交阶段 (执行):

在该阶段，协调者将基于第一个阶段的投票结果进行决策 : 提交或取消，当且仅当所有的参与者同意提交事务，协调者才通知所有的参与者提交事务，否则协调者将通知所有的参与者取消事务参与者在接收到协调者发来的消息后将执行响应的操作。

(3)两阶段提交无法解决的问题

A)、如果一个参与者迟迟不投票，那整个阶段都会处于等待状态，但这可以通过超时机制解决

B)、当协调者出错，同时参与者也出错时，两阶段无法保证事务执行的完整性。

考虑协调者在发出commit消息之后宕机，而唯一接收到这条消息的参与者同时也宕机了。

那么即使协调者通过选举协议产生了新的协调者，这条事务的状态也是不确定的，没人知道事务是否被已经提交。

B、三阶段提交

三阶段提交拥有CanCommit、PreCommit、DoCommit三个阶段

(1)其中CanCommit阶段近似等同于两阶段的请求阶段;DoCommit近似等同于两阶段的提交阶段。而准备阶段 PreCommit是一个缓冲，保证了在最后提交阶段之前各参与节点的状态是一致的。

(2)三阶段提交在两阶段提交的第一阶段与第二阶段之间插入了一个准备阶段(PreCommit)，使得原先在两阶段提交中，参与者在投票之后，由于协调者发生崩溃或错误，而导致参与者处于无法知晓是否提交或者中止的“不确定状态”所产生的可能相当长的延时的问题得以解决。

(3)三阶段提交无法解决的问题

如果进入PreCommit后，协调者发出的是commit请求，假设只有一个参与者收到并进行了commit操作，而其他参与者对于网络中断没有收到，会根据3PC选择abort操作，此时系统状态发生不一致性。

C、Paxos协议

要讲Paxos，先要从拜占庭问题讲起，其故事背景是这样的：拜占庭位于现在土耳其的伊斯坦布尔，是东罗马帝国的首都。由于当时拜占庭罗马帝国国土辽阔，为了防御目的，因此每个军队都分隔很远，将军与将军之间只能靠信差传消息。在战争的时候，拜占庭军队内所有将军必需达成一致的共识，决定是否有赢的机会才去攻打敌人的阵营。但是，军队可能有叛徒和敌军间谍，这些叛徒将军们会扰乱或左右决策的过程。这时候，在已知有成员谋反的情况下，其余忠诚的将军在不受叛徒的影响下如何达成一致的协议，这就是拜占庭将军问题。

我们否定假设，给出了非拜占庭模型定义：

(1)一致性模块的行为可以以任意速度执行，允许运行失败，在失败后也许会重启并再次运行;

(2)一致性模块之间通过异步方式发送信息通信，通信时间可以任意长，信息可能会在传输过程中丢失，也允许重复发送相同的信息，多重信息的顺序可以任意。但是有一点：信息不允许被篡改。

由此，我们得出了Paxos的基本二阶段：Prepare阶段、Accept阶段，这个两个阶段的逻辑非常复杂，是互信算法的基础，本文并不打算做过深的解读。有兴趣的读者可以去参考《区块链算法》一书。

D、Raft协议

Raft是Replicated And Fault Tolerant的缩写，Paxos的简化版本。

在一个分布式系统中，要提高系统的健壮性，可用性和数据的安全性，我们最正确的姿势是什么?当然是靠多备份了，服务多备份，数据多备份，去除单点，确保即使相关组件挂掉一些，系统还能健康服务。

去除单点，没有固定不变的权威，固然好，但是带来的问题就是，以谁的意见为准，在信息可能丢失的环境下，这是一个相当困难的事(可见沟通是多么的重要)!

在1990年提出来之时，几乎没有人能够理解。经过作者多次简化，再解释，包括谷歌等团队的实践再创造，再解释的过程，十几年过去了，才渐渐的成为事实标准并被大家所了解和接受。但直到现在，无比抽象的Paxos算法，还是没有几个人能理解。

大道至简!这是永恒不变的真理，Raft的目标问题，是构建一个容易理解和构建的分布式一致性协议，在容易的基础上，确保理论正确的。

Raft协议，如果照本宣读，还是需要点时间的，本文采用通俗的办法给大家做解释

Raft大致的原理，这是一个选主(leader selection)思想的算法，集群总每个节点都有三种可能的角色：

(1) leader

对客户端通信的入口，对内数据同步的发起者，一个集群通常只有一个leader节点

(2) follower:

非leader的节点，被动的接受来自leader的数据请求

(3) candidate:

一种临时的角色，只存在于leader的选举阶段，某个节点想要变成leader，那么就发起投票请求，同时自己变成 candidate。如果选举成功，则变为candidate，否则退回为follower 。

算法包含两个过程：leader 选举和日志复制：

(1) 选举过程：(假设有5个节点，S1~S5)

a、初始状态下，大家都是平等的follower，那么follow谁呢，总要选个老大吧。大家都蠢蠢欲动，每个follower 内部都维护了一个随机的timer;

b、在timer时间到了的时候还没有人主动联系它的话，那它就要变成candidate，同时发出投票请求(RequestVote)给其他人，假设S1,S3成为candidate

c、对于相同条件的candidate ，follower们采取先来先投票的策略。如果超过半数的follower都认为他是合适做领导的，那么恭喜，新的leader产生了，假如S3变成了新一届的大哥leader ;

d、S1很不幸，没有人愿意选这个悲剧的 candidate ，那它只有老老实实地变回小弟的状态 follower;

e、同样的，如果在timer期间内没有收到大哥的联络，这时很可能大哥已经跪了，如下图，所有小弟又开始蠢蠢欲动，新的一轮 (term) 选举开始了。

(2) 日志复制：(假设有5个节点，S1~S5 )

a、leader 扮演的是分布式事务中的协调者，每次有数据更新的时候产生二阶段提交( two-phase commit )。在 leader 收到数据操作的请求，先不着急更新本地数据(数据是持久化在磁盘上的)，而是生成对应的log ，然后把生成 log 的请求广播给所有的 follower ;

b、每个follower在收到请求之后有两种选择：一种是听从leader的命令，也写入log，然后返回success回去;另一种情况，在某些条件不满足的情况下，follower认为不应该听从leader的命令，返回false;

c、此时如果超过半数的follower都成功写了log，那么leader开始_第二阶段_的提交：正式写入数据，然后同样广播给follower，follower也根据自身情况选择写入或者不写入并返回结果给 leader ，最终所有节点的数据达成一致。

d、这两阶段中如果任意一个都有超过半数的follower返回false或者根本没有返回，那么这个分布式事务是不成功的。此时虽然不会有回滚的过程，但是由于数据不会真正在多数节点上提交，所以会在之后的过程中被覆盖掉

Raft协议保证_leader_的强领导地位,client 读写都_通过_leader_，有很高的一致性，但有些同学会问，那分布式的价值在什么地方呢?如何才能负载均衡呢?在实际中我们采用 Multi Raft 架构，结合应用，不同的应用选举不同的leader节点，在负载均衡。

5、跨机房部署

在分布式系统中，跨机房问题一直都是老大难问题。机房之间的网络延时较大，且不稳定。跨机房问题主要包含两个方面：数据同步以及服务切换。跨机房部署方案有三个：集群整体切换、单个集群跨机房、 Paxos 选主副本。下面分别介绍。

A 、集群整体切换

集群整体切换是最为常见的方案。如图所示，假设某系统部署在两个机房：机房1和机房2。两个机房保持独立，每个机房部署单独的总控节点，且每个总控节点各有一个备份节点。当总控节点出现故障时，能够自动将机房内的备份节点切换为总控节点继续提供服务。另外，两个机房部署了相同的副本数，例如数据分片A在机房1存储的副本为A11和A12，在机房2存储的副本为A21和A22。在某个时刻，机房1为主机房，机房2为备机房。

机房之间的数据同步方式可能为强同步或者异步。如果采用异步模式，那么，备机房的数据总是落后于主机房。当主机房整体出现故障时，有两种选择：要么将服务切换到备机房，忍受数据丢失的风险;要么停止服务，直到主机房恢复为止。因此，如果数据同步为异步，那么，主备机房切换往往是手工的，允许用户根据业务的特点选择“丢失数据”或者“停止服务”。

如果采用强同步模式，那么，备机房的数据和主机房保持一致。当主机房出现故障时，除了手工切换，还可以采用自动切换的方式，即通过分布式锁服务检测主机房的服务，当主机房出现故障时，自动将备机房切换为主机房。

B、单个集群跨机房

将单个集群部署到多个机房，允许不同数据分片的主副本位于不同的机房，如图3-11所示。每个数据分片在机房1和机房2，总共包含4个副本，其中A1、B1、C1是主副本，A1和B1在机房1，C1在机房2 。整个集群只有一个总控节点，它需要同机房1和机房2的所有工作节点保持通信。当总控节点出现故障时，分布式锁服务将检测到，并将机房2的备份节点切换为总控节点。

如果采用这种部署方式，总控节点在执行数据分布时，需要考虑机房信息，也就是说，尽量将同一个数据分片的多个副本分布到多个机房，从而防止单个机房出现故障而影响正常服务。

C、Paxos选主副本

如果采用Paxos协议选主副本，那么，每个数据分片的多个副本构成一个Paxos复制组。如图所示，B1、B2、B3、B4构成一个复制组，某一时刻B1为复制组的主副本，当B1出现故障时，其他副本将尝试切换为主副本，Paxos协议保证只有一个副本会成功。这样，总控节点与工作节点之间不再需要保持租约，总控节点出现故障也不会对工作节点产生影响。它的优点在于能够降低对总控节点的依赖，缺点在于工程复杂度太高，很难在线下模拟所有的异常情况。

四、分布式文件系统

分布式文件系统的主要功能有两个：一个是存储文档、图像、视频之类的Blob类型数据;另外一个是作为分布式表格系统的持久化层。

1、Google文件系统(GFS)

GFS,Big Table,Map Reduce称为Google的三驾马车，是许多基础服务的基石。

GFS于2003年提出，是一个分布式的文件系统，与此前的很多分布式系统的前提假设存在很大的不同，适用于以下场景

(1)认为组件失效是一种常态，提供了容错机制，自动负载均衡，使得分布式文件系统可以在廉价机器上运行;

(2)面向大文件存储，系统主要的工作负载是大规模的流式读取，写操作主要是追加方式写，很少有随机写;

(3)一次写入，多次读取，例如互联网上的网页存储

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

主控服务器中维护了系统的元数据，包括文件及chunk命名空间、文件到chunk之间的映射、chunk位置信息。它也负责整个系统的全局控制，如chunk租约管理、垃圾回收无用chunk、chunk复制等。主控服务器会定期与CS通过心跳的方式交换信息。

客户端是GFS提供给应用程序的访问接口，它是一组专用接口，不遵循POSIX规范，以库文件的形式提供。客户端访问 GFS时，首先访问主控服务器节点，获取与之进行交互的CS信息，然后直接访问这些CS，完成数据存取工作。

需要注意的是，GFS中的客户端不缓存文件数据，只缓存主控服务器中获取的元数据，这是由GFS的应用特点决定的。GFS最主要的应用有两个：MapReduce与Bigtable。对于MapReduce,GFS客户端使用方式为顺序读写，没有缓存文件数据的必要;而Bigtable作为分布式表格系统，内部实现了一套缓存机制。另外，如何维护客户端缓存与实际数据之间的一致性是一个极其复杂的问题。

由此可见，Hadoop的HDFS其实是GFS的简化版，是Cutting博士“山寨” GFS出来的产物。是盗火种的产物。

2、Taobao 文件系统( TFS )

互联网应用经常需要存储用户上传的文档、图片、视频等，比如Facebook相册、淘宝图片、Dropbox文档等。文档、图片、视频一般称为Blob数据。Blob文件系统的特点是数据写入后基本都是只读，很少出现更新操作，这就是Taobao 文件系统(TFS )的主要特点。

TFS架构上借鉴了GFS，但与GFS又有很大的不同。

(1) TFS内部不维护文件目录树，扁平化的数据组织结构，可将文件名映射到文件的物理地址，简化了文件的访问流程;

(2) 针对海量小文件的随机读写访问性能做了特殊优化，满足了淘宝对小文件存储的需求，被广泛地应用在淘宝各项应用中;

(3) 采用了HA架构和平滑扩容，保证了整个文件系统的可用性和扩展性。

一个TFS集群由两个NameServer节点(一主一备)和多个DataServer节点组成，NameServer通过心跳对DataSrver的状态进行监测。NameServer相当于GFS中的Master,DataServer相当于GFS 中的ChunkServer。NameServer区分为主 NameServer和备NameServer,只有主 NameServer提供服务，当主NameServer出现故障时，能够被心跳守护进程检测到，并将服务切换到备NameServer。每个DataServer上会运行多个dsp进程，一个dsp对应一个挂载点，这个挂载点一般对应一个独立磁盘，从而管理多块磁盘。

在TFS中，将大量的小文件(实际数据文件)合并成一个大文件(这一点比HDFS有优化和改进)，这个大文件称为块(Block)，每个Block拥有在集群内唯一的编号(块ID)，通过<块ID，块内偏移>可以唯一确定一个文件。TFS中Block的实际数据都存储在DataServer中，大小一般为64MB ，默认存储三份，相当于GFS中的chunk。应用客户端是TFS提供给应用程序的访问接口，应用客户端不缓存文件数据，只缓存NameServer的元数据。

3、Fackbook Haystack文件系统

到2014年，Facebook大概有超4000亿张图片，总大小为30PB，通过计算可以得出每张照片的平均大小为 30PB/260GB，约为100KB 。用户每周新增照片数为10亿(总大小为60TB)，平均每秒新增的照片数为109/7/40000(按每天40000s计)，约为每秒3800次写操作，读操作峰值可以达到每秒百万次。

Facebook相册后端早期采用基于NAS的存储通过NFS挂载NAS中的照片文件来提供服务。后来出于性能和成本考虑，自主研发了Facebook Haystack存储相册数据。

和TFS类似，Facebook Haystack新架构主要解决图片存取IO次数过多的文件，主要的思路是多个逻辑文件共享同一个物理文件。Haystack架构及读请求处理流程图如下

Haystack架构主要有三个部分：Haystack Directory，Haystack Store以及Haystack Cache 。Haystack Store是物理存储节点，以物理卷轴 (physical volume) 的形式组织存储空间，每个物理卷轴一般很大，比如100GB ,这样10TB的数据也只有100个物理卷轴。每个物理卷轴对应一个物理文件，因此，每个存储节点上的物理文件元信息都很小。多个物理存储节点上的物理卷轴组成一个逻辑卷轴 (logical volume) ，用于备份。Haystack Directory存放逻辑卷轴和物理卷轴的对应关系，假设每个卷轴的大小为100GB ，对应关系的条数为20PB/100GB=0.2MB，占用的内存可以忽略。Haystack cache主要用于解决对CDN提供商过于依赖的问题，提供最近增加的图片的缓存服务。

Haystack图片读取请求大致流程为：用户访问一个页面时，Web Server请求Haystack Directory构造一个URL：http:// < CDN > / < Cache > / < Machine id > / < Logical volume,Photo > ，后续根据各个部分的信息依次访问CDN ， Cache 和后端的Haystack Store存储节点。Haystack Directory构造URL时可以省略 部分从而使得用户直接请求Haystack Cache而不必经过CDN。Haystack cache 收到的请求包含两个部分：用户Browser的请求及 CDN 的请求，Haystack cache只缓存用户Browser发送的请求且要求请求的Haystack Store存储节点是可写的。一般来说，Haystack Store的存储节点写一段时间以后达到容量上限变为只读，因此，可写节点的图片为最近增加的图片，是热点数据。

Haystack的写请求 (图片上传) 处理流程为：Web Server首先请求Haystack Directory获取图片的id和可写的逻辑卷轴，接着将数据写入对应的每一个物理卷轴 ( 备份数一般为3) 。

Facebook Haystack及Taobao TFS这样的文件系统一般称为 Blob文件系统。它们都是解决大量的小图片文件的问题，因此架构很类似，不同点包括

(1) 逻辑卷轴大小的选择，比如Haystack选择100GB的逻辑卷轴大小，TFS中block大小一般为64MB ;

(2) Haystack使用RAID 6，且底层文件系统使用性能更好的XFS ，淘宝后期摈除了RAID机制，文件系统使用 Ext3 ;

(3) Haystack使用了Akamai&Limelight的CDN服务，而Taobao已经使用自建的CDN，当然，Facebook也在考虑自建CDN 。

4、CDN内容分发网络

CDN的全称是Content Delivery Network，即内容分发网络。其目的是通过在现有的Internet中增加一层新的网络架构，将网站的内容发布到最接近用户的网络"边缘"。实现如下三个目的

(1)解决因分布、带宽、服务器性能带来的访问延迟问题，适用于站点加速、点播、直播等场景。使用户可就近取得所需内容，解决Internet网络拥挤的状况，提高用户访问网站的响应速度和成功率。

(2)控制时延无疑是现代信息科技的重要指标，CDN的意图就是尽可能的减少资源在转发、传输、链路抖动等情况下顺利保障信息的连贯性。

(3) CDN就是扮演者护航者和加速者的角色，更快准狠的触发信息和触达每一个用户，带来更为极致的使用体验。

如下图所示DNS在对域名解析时不再向用户返回源服务器的IP，而是返回了由智CDN负载均衡系统选定的某个边缘节点的IP。用户利用这个IP访问边缘节点，然后该节点通过其内部DNS解析得到源服务器IP并发出请求来获取用户所需的页面，如果请求成功，边缘节点会将页面缓存下来，下次用户访问时可以直接读取，而不需要每次都访问源服务器。

Taobao的CDN架构是自研的，用于支持用户购物,尤其是“双11” 光棍节时的海量图片请求，图片存储在后台的TFS集群中，CDN系统将这些图片缓存到离用户最近的边缘节点。CDN采用两级Cache：L1-Cache以及L2-Cache 。用户访问淘宝网的图片时，通过全局调度系统(Global Load Balancing)调度到某个L1-Cache节点。如果L1-Cache命中，那么直接将图片数据返回用户;否则，请求L2-Cache节点，并将返回的图片数据缓存到L1-Cache节点。如果L2-Cache命中，直接将图片数据返回给L1-Cache节点;否则，请求源服务器的图片服务器集群。每台图片服务器是一个运行着Nginx的 Web服务器，它还会在本地缓存图片，只有当本地缓存也不命中时才会请求后端的TFS集群，图片服务器集群和TFS 集群部署在同一个数据中心内。

对于每个CDN节点，其架构如图4-11所示。从图中可以看出，每个CDN节点内部通过LVS+Haproxy的方式进行负载均衡。其中，LVS是四层负载均衡软件，性能好;Haproxy是七层负载均衡软件，能够支持更加灵活的负载均衡策略。通过有机结合两者，可以将不同的图片请求调度到不同的Squid服务器。

上图是CDN的单节点架构，它有以下三个特点

(1) Squid服务器构成淘宝单节点中的CDN中的分布式缓存，这个实现比分布式缓存简单很多，因为不需要考虑数据持久化。

(2) 分级缓存，由于缓存数据有较高的局部性，在Squid服务器上使用SSD+SAS+SATA混合存储，图片随着热点变化而迁移，最热门的存储到SSD，中等热度的存储到SAS，轻热度的存储到SATA。通过这样的方式，能够很好地结合SSD的性能和SAS、SATA磁盘的成本优势;

(3) 低功耗服务器定制，CDN缓存服务是IO密集型而不是CPU密集型的服务，因此，选用Intel Atom CPU定制低功耗服务器，在保证服务性能的前提下大大降低了整体功耗。

五、分布式键值系统

分布式键值系统是用于存储关系简单的半结构化数据，半结构化数据均封装成由 键值对组成的对象，其中key为唯一标示符;value为属性值，可以为任何类型，如文字、图片，也可以为空;timestamp为时间戳，提供对象的多版本支持。分布式键值系统以键值对存储，它的结构不固定，每一元组可以有不一样的字段，可根据需要增加键值对，从而不局限于固定的结构，适用面更大，可扩展性更好。

分布式键值系统支持针对单个 键值对的增、删、查、改操作，可以运行在PC服务器集群上，并实现集群按需扩展，从而处理大规模数据，并通过数据备份保障容错性，避免了分割数据带来的复杂性和成本。

总体来说，分布式键值系统从存储数据结构的角度看，分布式键值系统与传统的哈希表比较类似，不同的是，分布式键值系统支持将数据分布到集群中的多个存储节点。分布式键值系统可以配置数据的备份数目，可以将一份数据的所有副本存储到不同的节点上，当有节点发生异常无法正常提供服务时，其余的节点会继续提供服务。

1、 Amazon Dynamo

Dynamo以很简单的键值方式存储数据，不支持复杂的查询。Dynamo中存储的是数据值的原始形式，不解析数据的具体内容。Dynamo主要用于Amazon的购物车及S3云存储服务。在实现过程中解决了如下问题：

Dynamo采用一致性哈希将数据分布到多个存储节点中，概括来说：给系统中的每个节点分配一个随机token，这些 token构成一个哈希环。执行数据存放操作时，先计算主键的哈希值，然后存放到顺时针方向的第一个大于或者等于该哈希值的token所在的节点。一致性哈希的有点在于节点加入/删除只会影响到在哈希环相邻的节点，而对其他节点没影响。

A、Dynamo架构

考虑到节点的异构性，不同节点的处理能力差别很大，Dynamo使用了改进的一致性哈希算法：每个物理节点根据其性能的差异分配多个token，每个token对应一个虚拟节点，每个虚拟节点的处理能力基本相当，并随机分布在哈希空间中。存储时，数据按照哈希值落到某个虚拟节点负责的区域，然后被存储到该虚拟节点所对应的物理节点。

如下图，某Dynamo集群中原有3个节点，每个节点分配3个token。存放数据时，首先计算主键的哈希值，并根据哈希值将数据存放到对应token所在的节点。假设增加节点4，节点token分配情况发生变化，这就实现了自动负载均衡。

为了找到数据所属的节点，要求每个节点维护一定的集群信息用于定位。Dynamo系统中每个节点维护整个集群的信息，客户端也缓存整个集群的信息，因此，绝大部分请求能够一次定位到目标节点。

B、Gossip 协议

由于机器或者人为的因素，系统中的节点成员加入或者删除经常发生，为了保证每个节点缓存的都是Dynamo集群中最新的成员信息，所有节点每隔固定时间(比如1s)通过Gossip协议的方式从其他节点中任意选择一个与之通信的节点。如果连接成功，双方交换各自保存的集群信息。

Gossip协议用于P2P系统中自治的节点协调对整个集群的认识，比如集群的节点状态、负载情况。我们先看看两个节点A和B是如何交换对世界的认识的。

(1) A告诉B其管理的所有节点的版本(包括Down状态和Up状态的节点);

(2) B告诉A哪些版本它比较旧了，哪些版本它有最新的，然后把最新的那些节点发给A (处于Down状态的节点由于版本没有发生更新所以不会被关注);

(3) A将B中比较旧的节点发送给B ，同时将B发送来的最新节点信息做本地更新;

(4) B收到A发来的最新节点信息后，对本地缓存的比较旧的节点做更新。

由于种子节点的存在，新节点加入可以做得比较简单。新节点加入时首先与种子节点交换集群信息，从而对集群有了认识。DHT(Distributed Hash Table ，也称为一致性哈希表)环中原有的其他节点也会定期和种子节点交换集群信息，从而发现新节点的加入。

集群不断变化，可能随时有机器下线，因此，每个节点还需要定期通过Gossip协议同其他节点交换集群信息。如果发现某个节点很长时间状态都没有更新，比如距离上次更新的时间间隔超过一定的阈值，则认为该节点已经下线了。

2、Taobao Tiar

Tair是一个分布式的key/value系统。

Tair有四种引擎：mdb, rdb, kdb和ldb。分别基于四种开源的key/value数据库：memcached, Redis, Kyoto Cabinet和leveldb。Tair可以让你更方便地使用这些KV数据库。比如Redis没有提供sharding操作，如果有多个Redis Server，你需要自己写代码实现sharding，Tair帮你封装了这些。

Tair有以下优点：

(1)统一的API 。无论底层使用何种引擎，上层的API是一样的。

(2) Tair将集群操作封装起来，解放了开发者。淘宝内部在使用Tair时，一般都是双机房双集群容错，利用invalid server保证两个集群间的一致性，这些对于开发者都是透明的。

A、Tair使用场景

(1)非持久化 (mdb,rdb)

数据可以以 key/value 的形式存储

数据可以接受丢失

访问速度要求很高

单个数据大小不是很大，一般在KB级别

数据量很大，并且有较大的增长可能性

数据更新不频繁

(2)持久化(kdb,ldb)

数据可以以key/value的形式存储

数据需要持久化

单个数据大小不是很大，一般在KB级别

数据量很大，并且有较大的增长可能性

数据的读写比例较高

B、Tair 的架构

Tair作为一个分布式系统，是由一个中心控制节点和若干个服务节点组成，

a、config server功能：

( 1 )通过维护和data server心跳来获知集群中存活节点的信息;

( 2 )根据存活节点的信息来构建数据在集群中的分布表;

( 3 )根据数据分布表的查询服务;

( 4 )调度data server之间的数据迁移、复制;

b、data server功能

( 1 )提供存储引擎;

( 2 )接受client的put/get/remove 等操作;

( 3 )执行数据迁移，复制等;

( 4 )插件：在接受请求的时候处理一些自定义功能;

( 5 )访问统计;

c、client功能

( 1 )在应用端提供访问tair集群的接口;

( 2 )更新并缓存数据分布表和invalid server地址等;

( 3 ) local cache，避免过热数据访问影响tair集群服务;

( 4 )流控;

在下图中，户端首先请求Config Server获取数据所在的Data Server，接着往Data Server发送读写请求。Tair允许将数据存放到多台Data Server，以实现异常容错。

C、数据分布均衡性

Tair 的分布采用的是一致性哈希算法，对于所有的key，分到Q个桶中，桶是负载均衡和数据迁移的基本单位， config server根据一定的策略把每个桶指派到不同的data server上，因为数据按照key做hash算法，保证了桶分布的均衡性，从而保证了数据分布的均衡性。

D、容错

当某台 Data Server 故障不可用时， Config Server 能够检测到。每个哈希桶在 Tair 中存储多个副本，如果是备副本，那么 Config Server 会重新为其指定一台 Data Server ，如果是持久化存储，还将复制数据到新的 Data Server 上。如果是主副本，那么 ConfigServer 首先将某个正常的备副本提升为主副本，对外提供服务。接着，再选择另外一台 Data Server 增加一个备副本，确保数据的备份数。

E、数据迁移

增加或减少data server的时候，config server会发现这个情况，config server负责重新计算一张新的桶在data server上的分布表，将原来由减少的机器服务的桶的访问重新指派到其他的data server中，这个时候就会发生数据的迁移。比如原来由data server A负责的桶，在新表中需要由B负责，而B上并没有该桶的数据，那么就将数据迁移到B上来，同时config server会发现哪些桶的备份数目减少了，然后根据负载均衡情况在负载较低的data server上增加这些桶的备份。当系统增加data server的时候，config server根据负载，协调data server将他们控制的部分桶迁移到新的 data server上，迁移完成后调整路由;

数据迁移时data server 对外提供服务的策略，假设data server A要把桶1,2,3迁移到data server B ，因为迁移完成前，客户端的路由表没有变化，客户端对1,2,3 的访问请求都会路由到A，现在假设1还没迁移，2正在迁移，3已经迁移完成，那么如果访问1 ，则还是访问data server A，如果访问3，则A会把请求转发给B，并且将B的返回结果返回给客户，如果访问2 ，则在A上处理，同时如果是对2的修改操作，会记录修改log，当桶2完成迁移的时候，还有把log发送给B，在B上应用这些log ，最终AB数据一致才是真正完成迁移。如果A是由于宕机而引发的迁移，客户端会收到一张中间临时状态的分配表，把宕机的data server负责的桶临时指派给有其备份的data server来处理，此时服务是可用的，负载可能不均衡，当迁移完成后，又能达到一个新的负载均衡状态。

3、ETCD

ETCD etcd是一个高可用的键值存储系统，主要用于共享配置和服务发现。

(1) 由CoreOS开发并维护的，灵感来自于ZooKeeper和Doozer ;

(2) 它使用Go语言编写，并通过Raft一致性算法处理日志复制以保证强一致。

(3) Google的容器集群管理系统Kubernetes、开源PaaS平台Cloud Foundry和CoreOS的Fleet都广泛使用了etcd ;

(4) 当集群网络出现动荡，或者当前master节点出现异常时，etcd可以进行master节点的选举工作，同时恢复集群中损失的数据

A、ETCD的特点

( 1 )简单：基于HTTP+JSON的API让你用curl就可以轻松使用。

( 2 )安全：可选SSL客户认证机制。

( 3 )快速：每个实例每秒支持一千次写操作。

( 4 )可信：使用Raft算法充分实现了分布式。

B、提供的能力

Etcd主要提供以下能力

(1) 提供存储以及获取数据的接口，它通过协议保证Etcd集群中的多个节点数据的强一致性。用于存储元信息以及共享配置。

(2) 提供监听机制，客户端可以监听某个key或者某些key的变更。用于监听和推送变更。

(3) 提供key的过期以及续约机制，客户端通过定时刷新来实现续约(v2和v3的实现机制也不一样)。用于集群监控以及服务注册发现。

(4) 提供原子的CAS(Compare-and-Swap)和CAD(Compare-and-Delete)支持(v2通过接口参数实现，v3通过批量事务实现)。用于分布式锁以及 leader 选举。

C、ETCD架构

( 1 ) Etcd v2存储，Watch以及过期机制

Etcd v2是个纯内存的实现，并未实时将数据写入到磁盘，持久化机制很简单，就是将store整合序列化成json写入文件。数据在内存中是一个简单的树结构。

store中有一个全局的currentIndex，每次变更，index会加1. 然后每个event都会关联到currentIndex.

当客户端调用watch 接口(参数中增加wait参数)时，如果请求参数中有waitIndex，并且waitIndex小于 currentIndex，则从EventHistroy表中查询index小于等于waitIndex，并且和watch key匹配的event，如果有数据，则直接返回。如果历史表中没有或者请求没有带waitIndex，则放入WatchHub中，每个key会关联一个watcher列表。当有变更操作时，变更生成的event会放入EventHistroy表中，同时通知和该key相关的watcher 。

(2) Etcd v3存储，Watch以及过期机制

Etcd v3将watch和store拆开实现，我们先分析下store的实现。Etcd v3 store分为两部分，一部分是内存中的索引，kvindex，是基于google开源的一个golang的btree实现的，另外一部分是后端存储。

按照它的设计，backend可以对接多种存储，当前使用的boltdb。boltdb是一个单机的支持事务的kv存储，Etcd的事务是基于boltdb的事务实现的。Etcd在boltdb中存储的key是reversion，value是Etcd自己的key-value组合，也就是说Etcd会在boltdb中把每个版本都保存下，从而实现了多版本机制。

4、产品选型比较(Etcd，Zookeeper，Consul比较)

这三个产品是经常被人拿来做选型比较的。

(1) Etcd和Zookeeper提供的能力非常相似，都是通用的一致性元信息存储，都提供watch机制用于变更通知和分发，也都被分布式系统用来作为共享信息存储，在软件生态中所处的位置也几乎是一样的，可以互相替代的。二者除了实现细节，语言，一致性协议上的区别，最大的区别在周边生态圈。Zookeeper是apache下的，用java写的，提供rpc接口，最早从hadoop项目中孵化出来，在分布式系统中得到广泛使用(hadoop,solr,kafka,mesos等)。Etcd是coreos公司旗下的开源产品，比较新，以其简单好用的rest接口以及活跃的社区俘获了一批用户，在新的一些集群中得到使用(比如 kubernetes)。虽然v3为了性能也改成二进制rpc接口了，但其易用性上比Zookeeper还是好一些。

(2) Consul的目标则更为具体一些，Etcd和Zookeeper提供的是分布式一致性存储能力，具体的业务场景需要用户自己实现，比如服务发现，比如配置变更。而Consul则以服务发现和配置变更为主要目标，同时附带了kv存储。在软件生态中，越抽象的组件适用范围越广，但同时对具体业务场景需求的满足上肯定有不足之处。

最后

另外还整理成了40多套PDF文档：全套的Java面试宝典手册，“性能调优+微服务架构+并发编程+开源框架+分布式”等七大面试专栏，包含Tomcat、JVM、MySQL、SpringCloud、SpringBoot、Dubbo、并发、Spring、SpringMVC、MyBatis、Zookeeper、Ngnix、Kafka、MQ、Redis、MongoDB、memcached等等。如果你对这个感兴趣，小编可以免费分享。

资料获取方式：关注小编+转发文章+私信【面试题】获取上述资料~

重要的事情说三遍，转发+转发+转发，一定要记得转发哦！！！