分布式存储架构技术基础

分布式存储架构技术基础

【摘要】本文介绍了分布式存储的架构类型、分布式理论、不同的分布式文件系统和分布式键值系统等，较为系统详尽。全文约2万字，可收藏。目录一、集中存储结构二、分布式存储1、分布式存储的兴起2、分布式存储的重要性3、分布式存储的种类和比较三、分布式理论浅析1、一致性和可用性2、数据分布3、复制4、分布式协议5、跨机房部署四、分布式文件系统1、Google文件系统（GFS）2、Taobao文件系统（TFS）3、FackbookHaystack文件系统4、CDN内容分发网络五、分布式键值系统1、AmazonDynamo2、TaobaoTiar3、ETCD4、产品选型比较（Etcd，Zookeeper，Consul）一、集中存储结构说到分布式存储，我们先来看一下传统的存储是怎么个样子。传统的存储也称为集中式存储，从概念上可以看出来是具有集中性的，也就是整个存储是集中在一个系统中的，但集中式存储并不是一个单独的设备，是集中在一套系统当中的多个设备，比如下图中的EMC存储就需要几个机柜来存放。在这个存储系统中包含很多组件，除了核心的机头（控制器）、磁盘阵列（JBOD）和交换机等设备外，还有管理设备等辅助设备。结构中包含一个机头，这个是存储系统中最为核心的部件。通常在机头中有包含两个控制器，互为备用，避免硬件故障导致整个存储系统的不可用。机头中通常包含前端端口和后端端口，前端端口用户为服务器提供存储服务，而后端端口用于扩充存储系统的容量。通过后端端口机头可以连接更多的存储设备，从而形成一个非常大的存储资源池。在整个结构中，机头中是整个存储系统的核心部件，整个存储系统的高级功能都在其中实现。控制器中的软件实现对磁盘的管理，将磁盘抽象化为存储资源池，然后划分为LUN提供给服务器使用。这里的LUN其实就是在服务器上看到的磁盘。当然，一些集中式存储本身也是文件服务器，可以提供共享文件服务。无论如何，从上面我们可以看出集中式存储最大的特点是有一个统一的入口，所有数据都要经过这个入口

，这个入口就是存储系统的机头。这也就是集中式存储区别于分布式存储最显著的特点。如下图所示：二、分布式存储分布式存储最早是由谷歌提出的，其目的是通过廉价的服务器来提供使用与大规模，高并发场景下的Web访问问题。它采用可扩展的系统结构，利用多台存储服务器分担存储负荷，利用位置服务器定位存储信息，它不但提高了系统的可靠性、可用性和存取效率，还易于扩展。1、分布式存储的兴起分布式存储的兴起与互联网的发展密不可分，互联网公司由于其数据量大而资本积累少，而通常都使用大规模分布式存储系统。与传统的高端服务器、高端存储器和高端处理器不同的是，互联网公司的分布式存储系统由数量众多的、低成本和高性价比的普通PC服务器通过网络连接而成。其主要原因有以下三点（1）互联网的业务发展很快，而且注意成本消耗，这就使得存储系统不能依靠传统的纵向扩展的方式，即先买小型机，不够时再买中型机，甚至大型机。互联网后端的分布式系统要求支持横向扩展，即通过增加普通PC服务器来提高系统的整体处理能力。（2）普通PC服务器性价比高，故障率也高，需要在软件层面实现自动容错，保证数据的一致性。（3）另外，随着服务器的不断加入，需要能够在软件层面实现自动负载均衡，使得系统的处理能力得到线性扩展。2、分布式存储的重要性从单机单用户到单机多用户，再到现在的网络时代，应用系统发生了很多的变化。而分布式系统依然是目前很热门的讨论话题，那么，分布式系统给我们带来了什么，或者说是为什么要有分布式系统呢？（1）升级单机处理能力的性价比越来越低；企业发现通过更换硬件做垂直扩展的方式来提升性能会越来越不划算；（2）单机处理能力存在瓶颈；某个固定时间点，单颗处理器有自己的性能瓶颈，也就说即使愿意花更多的钱去买计算能力也买不到了；（3）出于稳定性和可用性的考虑如果采用单击系统，那么在这台机器正常的时候一切OK，一旦出问题，那么系统就完全不能用了。当然，可以考虑做容灾备份等方案，而这些方案就会让系统演变为分布式系统了；（4）云存储和大数据发展的必然要求云存储和大数据是构建在分布式存储之上的应用。移动终端的计算能力和存储空间有限，而且有在多个设备之间共享资源的强烈的需求，这就使得网盘、相册等云存储应用很快流行起来。然而，万变不离其宗，云存储的核心还是后端的大规模分布式存储系统。大数据则更近一步，不仅需要存储海量数据，还需要通过合适的计算框架或者工具对这些数据进行分析，抽取其中有价值的部分。如果没有分布式存储，便谈不上对大数据进行分析。仔细分析还会发现，分布式存储技术是互联网后端架构的神器，掌握了这项技能，以后理解其他技术的本质会变得非常容易。3、分布式存储的种类和比较分布式存储包含的种类繁多，除了传统意义上的分布式文件系统、分布式块存储和分布式对象存储外，还包括分布式数据库和分布式缓存等，但其中架构无外乎于三种A、中间控制节点架构以HDFS（HadoopDistributionFileSystem）为代表的架构是典型的代表。在这种架构中，一部分节点NameNode是存放管理数据（元数据），另一部分节点DataNode存放业务数据，这种类型的服务器负责管理具体数据。这种架构就像公司的层次组织架构，namenode就如同老板，只管理下属的经理（datanode），而下属的经理，而经理们来管理节点下本地盘上的数据。在上图中，如果客户端需要从某个文件读取数据，首先从NameNode获取该文件的位置（具体在哪个DataNode），然后从该NameNode获取具体的数据。在该架构中NameNode通常是主备部署（SecondaryNameNode），而DataNode则是由大量节点构成一个集群。由于元数据的访问频度和访问量相对数据都要小很多，因此NameNode通常不会成为性能瓶颈，而DataNode集群中的数据可以有副本，既可以保证高可用性，可以分散客户端的请求。因此，通过这种分布式存储架构可以通过横向扩展datanode的数量来增加承载能力，也即实现了动态横向扩展的能力。B、完全无中心架构–计算模式以Ceph为代表的架构是其典型的代表。在该架构中与HDFS不同的地方在于该架构中没有中心节点。客户端是通过一个设备映射关系计算出来其写入数据的位置，这样客户端可以直接与存储节点通信，从而避免中心节点的性能瓶颈。如上图所示，在Ceph存储系统架构中核心组件有MON服务、OSD服务和MDS服务等。(1)MON服务用于维护存储系统的硬件逻辑关系，主要是服务器和硬盘等在线信息。MON服务通过集群的方式保证其服务的可用性。(2)OSD服务用于实现对磁盘的管理，实现真正的数据读写，通常一个磁盘对应一个OSD服务。(3)MDS只为CephFS文件存储系统跟踪文件的层次机构和存储元数据。Ceph块设备和RADOS并不需要元数据，因此也不需要CephMDS守护进程(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)RADOSGW：RGW提供对象存储服务，它允许应用程序和Ceph对象存储建立连接，RGW提供了与AmazonS3和openstackSwift兼容的RUSTFULAPI客户端访问存储的大致流程是，客户端在启动后会首先通过RADOSGW进入，从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之前，我们就说e1happenbeforee2。对于同一个线程来说，前面的事件一定happenbefore后面的事件。但是对于不同线程上的两个事件来说，它们之间只有在在时间线上没有交叉的情况下，才会存在happenbefore关系。对于有交叉的那些事件，比如下图中的event2和event3，它们两个就不存在happenbefore关系，对于我们要寻找的合法顺序执行过程来说，它们两个的顺序可以是任意的。B、顺序一致性顺序一致性弱于严格一致性。对变量的写操作不一定要在瞬间看到，但是，不同处理器对变量的写操作必须在所有处理器上以相同的顺序看到，这里处理器再分布式系统中可以换成不同的节点。

假设有两个线程A和B并发执行。其中A线程由3个操作构成，它们在程序中的顺序是：A1->A2->A3.B线程也有3个操作，它们在程序中的顺序是：B1->B2->B3.假设如果在顺序一致的模型中的效果就是如上两个图所示。C、因果一致性因果一致性是弱于顺序一致性的一致性模型，顺序一致性要求所有的操作的顺序都必须按照某个单个处理器(节点)的顺序，而因果一致性只需要满足有因果关系的操作是顺序一致性即可。简单来说如果有人问你一个问题，那么你给出答案，这两个就是因果关系，但如果你给出答案再问题之前，那么这个就违反了因果关系。举个简单的例子如果节点1更新了数据A，节点2读取数据A，并更新数据B，这里的数据B有可能是根据数据A计算出来的，所有具备因果关系，但是如果节点3看到的是先更新的B，再更新的A那么就破坏了因果一致性。D、最终一致性其实除了强一致以外，其他的一致性都可以看作为最终一致性，只是根据一致性不同模型的不同要求又衍生出了很多具体一致性模型。当然最简单的最终一致性，是不需要关注中间变化的顺序，只需要保证在某个时间点一致即可。只是这个某个时间点需要根据不同的系统，不同业务再去衡量。再最终一致性完成之前，有可能返回任何的值，不会对这些值做任何顺序保证。E、可用性可用性指“Readsandwritesalwayssucceed”，即服务一直可用，而且是正常响应时间。对于一个可用性的分布式系统，每一个非故障的节点必须对每一个请求作出响应。所以，一般我们在衡量一个系统的可用性的时候，都是通过停机时间来计算的。可用性分类可用水平（%）年可容忍停机时间容错可用性99.9999<1min极高可用性99.999<5min具有故障自动恢复能力的可用性99.99<53min高可用性99.9<8.8h商品可用性99<43.8min通常我们描述一个系统的可用性时，我们说淘宝的系统可用性可以达到5个9，意思就是说他的可用水平是99.999%，即全年停机时间不超过(1-0.99999)36524*60=5.256min，这是一个极高的要求。好的可用性主要是指系统能够很好的为用户服务，不出现用户操作失败或者访问超时等用户体验不好的情况。一个分布式系统，上下游设计很多系统如负载均衡、WEB服务器、应用代码、数据库服务器等，任何一个节点的不稳定都可以影响可用性F、分布式系统的一致性2000年7月，加州大学伯克利分校的EricBrewer教授在ACMPODC会议上提出CAP猜想。2年后，麻省理工学院的SethGilbert和NancyLynch从理论上证明了CAP。之后，CAP理论正式成为分布式计算领域的公认定理。CAP理论概述：一个分布式系统最多只能同时满足一致性（Consistency）、可用性（Availability）和分区容错性（Partitiontolerance）这三项中的两项。需要特别指出的CAP中的一致性是allnodesseethesamedataatthesametime，也就是线性一致性。一致性必须从两个维度看：（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。包含两种系统：CPwithoutA**、APwithoutC**我们在上文所提到的Hdfs、Ceph、Swift,均是属于CPwithoutA的这个大类，只是并不是完全没有A，为了实现一定的可用性，一般设置副本的个数为N>=3。不同的N,W,R组合，是在可用性和一致性之间取一个平衡，以适应不同的应用场景。那么，实际生活中，也有一些是APwithoutC的案例，如CAP图中所示，大部分是Nosql、CoachDB、Cassandra数据库，那场景是哪些呢？其实就是不要求正确性的场合，如某米的抢购手机场景或12306抢购火车票的场景，可能前几秒你浏览商品的时候页面提示是有库存的，当你选择完商品准备下单的时候，系统提示你下单失败，商品已售完。这其实就是先在A（可用性）方面保证系统可以正常的服务，然后在数据的一致性方面做了些牺牲。2、数据分布分布式系统区别于传统单机系统在于能够将数据分布到多个节点，并在多个节点之间实现负载均衡。数据分布的方式主要有两种，一种是哈希分布，如一致性哈希，代表系统为Amazon的Dynamo系统，Openstack的Swift系统；另外一种方法是顺序分布，即每张表格上的数据按照主键整体有序，代表系统为Google的Bigtable系统。Bigtable将一张大表根据主键切分为有序的范围，每个有序范围是一个子表。A、哈希分布（Swift）哈希函数的散列特性很好，哈希方式可以将数据比较均匀地分布到集群中去。而且，哈希方式需要记录的元信息也非常简单，每个节点只需要知道哈希函数的计算方式以及模的服务器的个数就可以计算出处理的数据应该属于哪台机器。然而，找出一个散列特性很好的哈希函数是很难的。这是因为，如果按照主键散列，那么同一个用户id下的数据可能被分散到多台服务器，这会使得一次操作同一个用户id下的多条记录变得困难；如果按照用户id散列，容易出现“数据倾斜”（dataskew）问题，即某些大用户的数据量很大，无论集群的规模有多大，这些用户始终由一台服务器处理。处理大用户问题一般有两种方式，一种方式是手动拆分，即线下标记系统中的大用户（例如运行一次MapReduce作业），并根据这些大用户的数据量将其拆分到多台服务器上。这就相当于在哈希分布的基础上针对这些大用户特殊处理；另一种方式是自动拆分，即数据分布算法能够动态调整，自动将大用户的数据拆分到多台服务器上。其中包含两种算法。一种是传统的哈希算法，访问数据时，首先计算哈希值，再查询元数据服务器，获得该哈希值对应的服务器。在这种算法下，服务器的上线和下线将导致大量的数据迁移，不适合于生产。另一致性哈希（DistributedHashTable,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,DecentralizedPlacementofReplicatedData.严格说起来Crush算法，其实也是以Hash算法为基础的。只不过映射的方法和一致性哈希不同。我们用Ceph分布的过程来加以说明。Ceph分布数据的过程：首先计算数据x的Hash值并将结果和PG数目取余，以得到数据x对应的PG编号。然后，通过CRUSH算法将PG映射到一组OSD中。最后把数据x存放到PG对应的OSD中。注明：PG全称是PlacementGroup（放置组）。这个过程中包含了两次映射，第一次是数据x到PG的映射。如果把PG当作存储节点，那么传统Hash算法一样。不同的是，PG是抽象的存储节点，它不会随着物理节点的加入或则离开而增加或减少，因此数据到PG的映射是稳定的。以Dynamo为例，在这个过程中，PG起到了两个作用：第一个作用是划分数据分区。每个PG管理的数据区间相同，因而数据能够均匀地分布到PG上；第二个作用是充当Dynamo中Token的角色，即决定分区位置。实际上，这和Dynamo中固定分区数目，以及维持分区数目和虚拟节点数目相等的原则是同一回事。以Ceph为例，CRUSH算法通过两次映射计算数据存储位置来确定如何存储和检索数据。CRUSH使Ceph客户机能够直接与OSDs通信，而不是通过集中的服务器或代理。通过算法确定的数据存储和检索方法，Ceph避免了单点故障、性能瓶颈和对其可伸缩性的物理限制。CRUSH需要集群的映射，并使用CRUSH映射在OSDs中伪随机存储和检索数据，数据在集群中均匀分布。3、复制为了保证分布式存储系统的高可靠和高可用，数据在系统中一般存储多个副本。当某个副本所在的存储节点出现故障时，分布式存储系统能够自动将服务切换到其他的副本，从而实现自动容错。分布式存储系统通过复制协议将数据同步到多个存储节点，并确保多个副本之间的数据一致性。A、强同步复制客户端将写请求发送给主副本，主副本将写请求复制到其他备副本，常见的做法是同步操作日志（CommitLog）。主副本首先将操作日志同步到备副本，备副本回放操作日志，完成后通知主副本。接着，主副本修改本机，等到所有的操作都完成后再通知客户端写成功。下图中的复制协议要求主备同步成功才可以返回客户端写成功，这种协议称为强同步协议。假设所有副本的个数为N，且N＞2，即备副本个数大于1。那么，实现强同步协议时，主副本可以将操作日志并发地发给所有备副本并等待回复，只要至少1个备副本返回成功就可以回复客户端操作成功。强同步的好处在于如果主副本出现故障，至少有1个备副本拥有完整的数据，分布式存储系统可以自动地将服务切换到最新的备副本而不用担心数据丢失的情况。B、异步复制与强同步对应的复制方式是异步复制。在异步模式下，主副本不需要等待备副本的回应，只需要本地修改成功就可以告知客户端写操作成功。另外，主副本通过异步机制，比如单独的复制线程将客户端修改操作推送到其他副本。异步复制的好处在于系统可用性较好，但是一致性较差，如果主副本发生不可恢复故障，可能丢失最后一部分更新操作。C、NWR复制分布式存储系统中还可能使用基于写多个存储节点的复制协议（Replicated-writeprotocol）。比如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是ReplicatedAndFaultTolerant的缩写，Paxos的简化版本。在一个分布式系统中，要提高系统的健壮性，可用性和数据的安全性，我们最正确的姿势是什么？当然是靠多备份了，服务多备份，数据多备份，去除单点，确保即使相关组件挂掉一些，系统还能健康服务。去除单点，没有固定不变的权威，固然好，但是带来的问题就是，以谁的意见为准，在信息可能丢失的环境下，这是一个相当困难的事（可见沟通是多么的重要）！在1990年提出来之时，几乎没有人能够理解。经过作者多次简化，再解释，包括谷歌等团队的实践再创造，再解释的过程，十几年过去了，才渐渐的成为事实标准并被大家所了解和接受。但直到现在，无比抽象的Paxos算法，还是没有几个人能理解。大道至简！这是永恒不变的真理，Raft的目标问题，是构建一个容易理解和构建的分布式一致性协议，在容易的基础上，确保理论正确的。Raft协议，如果照本宣读，还是需要点时间的，本文采用通俗的办法给大家做解释Raft大致的原理，这是一个选主（leaderselection）思想的算法，集群总每个节点都有三种可能的角色：（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成为candidatec、对于相同条件的candidate，follower们采取先来先投票的策略。如果超过半数的follower都认为他是合适做领导的，那么恭喜，新的leader产生了，假如S3变成了新一届的大哥leader；d、S1很不幸，没有人愿意选这个悲剧的candidate，那它只有老老实实的变回小弟的状态follower;e、同样的，如果在timer期间内没有收到大哥的联络，这时很可能大哥已经跪了，如下图，所有小弟又开始蠢蠢欲动，新的一轮(term)选举开始了。（2）日志复制：（假设有5个节点，S1~S5）a、leader扮演的是分布式事务中的协调者，每次有数据更新的时候产生二阶段提交（two-phasecommit）。在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__，有很高的一致性，但有些同学会问，那分布式的价值在什么地方呢？如何才能负载均衡呢？在实际中我们采用MultiRaft架构，结合应用，不同的应用选举不同的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,BigTable,MapReduce称为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、FackbookHaystack文件系统到2014年，Facebook大概有超4000亿张图片，总大小为30PB，通过计算可以得出每张照片的平均大小为30PB/260GB，约为100KB。用户每周新增照片数为10亿（总大小为60TB），平均每秒新增的照片数为109/7/40000（按每天40000s计），约为每秒3800次写操作，读操作峰值可以达到每秒百万次。Facebook相册后端早期采用基于NAS的存储，通过NFS挂载NAS中的照片文件来提供服务。后来出于性能和成本考虑，自主研发了FacebookHaystack存储相册数据。和TFS类似，FacebookHaystack新架构主要解决图片存取IO次数过多的文件，主要的思路是多个逻辑文件共享同一个物理文件。Haystack架构及读请求处理流程图如下Haystack架构主要有三个部分：HaystackDirectory，HaystackStore以及HaystackCache。HaystackStore是物理存储节点，以物理卷轴(physicalvolume)的形式组织存储空间，每个物理卷轴一般很大，比如100GB，这样10TB的数据也只有100个物理卷轴。每个物理卷轴对应一个物理文件，因此，每个存储节点上的物理文件元信息都很小。多个物理存储节点上的物理卷轴组成一个逻辑卷轴(logicalvolume)，用于备份。HaystackDirectory存放逻辑卷轴和物理卷轴的对应关系，假设每个卷轴的大小为100GB，对应关系的条数为20PB/100GB=0.2MB，占用的内存可以忽略。Haystackcache主要用于解决对CDN提供商过于依赖的问题，提供最近增加的图片的缓存服务。Haystack图片读取请求大致流程为：用户访问一个页面时，WebServer请求HaystackDirectory构造一个URL：http://＜CDN＞/＜Cache＞/＜Machineid＞/＜Logicalvolume,Photo＞，后续根据各个部分的信息依次访问CDN，Cache和后端的HaystackStore存储节点。HaystackDirectory构造URL时可以省略部分从而使得用户直接请求HaystackCache而不必经过CDN。Haystackcache收到的请求包含两个部分：用户Browser的请求及CDN的请求，Haystackcache只缓存用户Browser发送的请求且要求请求的HaystackStore存储节点是可写的。一般来说，HaystackStore的存储节点写一段时间以后达到容量上限变为只读，因此，可写节点的图片为最近增加的图片，是热点数据。Haystack的写请求(图片上传)处理流程为：WebServer首先请求HaystackDirectory获取图片的id和可写的逻辑卷轴，接着将数据写入对应的每一个物理卷轴(备份数一般为3)。FacebookHaystack及TaobaoTFS这样的文件系统一般称为Blob文件系统。它们都是解决大量的小图片文件的问题，因此架构很类似，不同点包括（1）逻辑卷轴大小的选择，比如Haystack选择100GB的逻辑卷轴大小，TFS中block大小一般为64MB；（2）Haystack使用RAID6，且底层文件系统使用性能更好的XFS，淘宝后期摈除了RAID机制，文件系统使用Ext3；（3）Haystack使用了Akamai&Limelight的CDN服务，而Taobao已经使用自建的CDN，当然，Facebook也在考虑自建CDN。4、CDN内容分发网络CDN的全称是ContentDeliveryNetwork，即内容分发网络。其目的是通过在现有的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。用户访问淘宝网的图片时，通过全局调度系统（GlobalLoadBalancing）调度到某个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密集型的服务，因此，选用IntelAtomCPU定制低功耗服务器，在保证服务性能的前提下大大降低了整体功耗。五、分布式键值系统分布式键值系统是用于存储关系简单的半结构化数据，半结构化数据均封装成由键值对组成的对象，其中key为唯一标示符；value为属性值，可以为任何类型，如文字、图片，也可以为空；timestamp为时间戳，提供对象的多版本支持。分布式键值系统以键值对存储，它的结构不固定，每一元组可以有不一样的字段，可根据需要增加键值对，从而不局限于固定的结构，适用面更大，可扩展性更好。分布式键值系统支持针对单个键值对的增、删、查、改操作，可以运行在PC服务器集群上，并实现集群按需扩展，从而处理大规模数据，并通过数据备份保障容错性，避免了分割数据带来的复杂性和成本。总体来说，分布式键值系统从存储数据结构的角度看，分布式键值系统与传统的哈希表比较类似，不同的是，分布式键值系统支持将数据分布到集群中的多个存储节点。分布式键值系统可以配置数据的备份数目，可以将一份数据的所有副本存储到不同的节点上，当有节点发生异常无法正常提供服务时，其余的节点会继续提供服务。1、AmazonDynamoDynamo以很简单的键值方式存储数据，不支持复杂的查询。Dynamo中存储的是数据值的原始形式，不解析数据的具体内容。Dynamo主要用于Amazon的购物车及S3云存储服务。在实现过程中解决了如下问题：问题采用的技术数据分布改进的哈希算法复制协议复制写协议（NRW参数可调）数据冲突的解决向量时钟临时故障处理数据回传机制永久故障处理Merkle哈希树成员资格及错误检测基于Gossip的成员资格和错误检测协议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（DistributedHashTable，也称为一致性哈希表）环中原有的其他节点也会定期和种子节点交换集群信息，从而发现新节点的加入。集群不断变化，可能随时有机器下线，因此，每个节点还需要定期通过Gossip协议同其他节点交换集群信息。如果发现某个节点很长时间状态都没有更新，比如距离上次更新的时间间隔超过一定的阈值，则认为该节点已经下线了。2、TaobaoTiarTair是一个分布式的key/value系统。Tair有四种引擎：mdb,rdb,kdb和ldb。分别基于四种开源的key/value数据库：memcached,Redis,KyotoCabinet和leveldb。Tair可以让你更方便地使用这些KV数据库。比如Redis没有提供sharding操作，如果有多个RedisServer，你需要自己写代码实现sharding，Tair帮你封装了这些。Tair有以下优点：（1）统一的API。无论底层使用何种引擎，上层的API是一样的。（2）Tair将集群操作封装起来，解放了开发者。淘宝内部在使用Tair时，一般都是双机房双集群容错，利用invalidserver保证两个集群间的一致性，这些对于开发者都是透明的。A、Tair使用场景（1）非持久化(mdb,rdb)•数据可以以key/value的形式存储•数据可以接受丢失•访问速度要求很高•单个数据大小不是很大，一般在KB级别•数据量很大，并且有较大的增长可能性•数据更新不频繁（2）持久化(kdb,ldb)•数据可以以key/value的形式存储•数据需要持久化•单个数据大小不是很大，一般在KB级别•数据量很大，并且有较大的增长可能性•数据的读写比例较高B、Tair的架构Tair作为一个分布式系统，是由一个中心控制节点和若干个服务节点组成，a、configserver功能：（1）通过维护和dataserver心跳来获知集群中存活节点的信息；（2）根据存活节点的信息来构建数据在集群中的分布表；（3）根据数据分布表的查询服务；（4）调度dataserver之间的数据迁移、复制；b、dataserver功能（1）提供存储引擎；（2）接受client的put/get/remove等操作；（3）执行数据迁移，复制等；（4）插件：在接受请求的时候处理一些自定义功能；（5）访问统计；c、client功能（1）在应用端提供访问tair集群的接口；（2）更新并缓存数据分布表和invalidserver地址等；（3）localcache，避免过热数据访问影响tair集群服务；（4）流控；在下图中，。客户端首先请求ConfigServer获取数据所在的DataServer，接着往DataServer发送读写请求。Tair允许将数据存放到多台DataServer，以实现异常容错。C、数据分布均衡性Tair的分布采用的是一致性哈希算法，对于所有的key，分到Q个桶中，桶是负载均衡和数据迁移的基本单位，configserver根据一定的策略把每个桶指派到不同的dataserver上，因为数据按照key做hash算法，保证了桶分布的均衡性，从而保证了数据分布的均衡性。D、容错当某台DataServer故障不可用时，ConfigServer能够检测到。每个哈希桶在Tair中存储多个副本，如果是备副本，那么ConfigServer会重新为其指定一台DataServer，如果是持久化存储，还将复制数据到新的DataServer上。如果是主副本，那么ConfigServer首先将某个正常的备副本提升为主副本，对外提供服务。接着，再选择另外一台DataServer增加一个备副本，确保数据的备份数。E、数据迁移增加或减少dataserver的时候，configserver会发现这个情况，configserver负责重新计算一张新的桶在dataserver上的分布表，将原来由减少的机器服务的桶的访问重新指派到其他的dataserver中，这个时候就会发生数据的迁移。比如原来由dataserverA负责的桶，在新表中需要由B负责，而B上并没有该桶的数据，