第9章互联网分布式系统的数据资源存储与管理--KeyValue存储模式(ppt)课件.ppt

1、 第第9 9章章 互联网分布式系统的数据资源存储与互联网分布式系统的数据资源存储与管理管理 -key/valuekey/value模式模式l 提纲提纲l 9 9.1.1 引言引言l 9 9.2.2.分布式分布式Key/valueKey/value数据存储与管理系统数据存储与管理系统l 9.3 9.3 支持都多租户的数据库支持都多租户的数据库l 9.4 9.4 基于基于MapReduceMapReduce并行编程的海量数据处理并行编程的海量数据处理l 9.5 9.5 典型实例分析典型实例分析12 9.1 引言引言 先了解在互联网数据资源存储和管理中设计的相关研究先了解在互联网数据资源存储和管理中

2、设计的相关研究问题问题，包括：从，包括：从互联网和互联网和WebWeb相关一些数据看数据管理、互联网数据资源存储和管理面临的相关一些数据看数据管理、互联网数据资源存储和管理面临的基本问题、数据密集型应用对数据管理模型的要求。基本问题、数据密集型应用对数据管理模型的要求。l 1.1.从互联网和从互联网和WebWeb相关一些数据看数据管理相关一些数据看数据管理l 互联网上有互联网上有1.091.09亿亿个个独立的独立的WebWeb站点，站点，297297亿亿个个的网页，平均世界上每人的网页，平均世界上每人拥有拥有5 5个网页。仅个网页。仅20062006年，互联网上就有年，互联网上就有108 TB

3、108 TB新产生的或复制的数据。这新产生的或复制的数据。这个数字比过去个数字比过去50005000年世界上产生的数据总和还多。每个月都有年世界上产生的数据总和还多。每个月都有7272个亿的个亿的WebWeb搜索发生，这个数字超过了世界人口的数量。搜索发生，这个数字超过了世界人口的数量。l 2001 2001年左右，随着年左右，随着网格网格的出现，兴起了一批数据网格、数据库网格等项的出现，兴起了一批数据网格、数据库网格等项目，例如目，例如TeraGridTeraGrid,MyGridMyGrid等，这些项目有的面向科学领域的应用，有的面等，这些项目有的面向科学领域的应用，有的面向分布环境下的行

4、业企业应用，其最终目标向分布环境下的行业企业应用，其最终目标都都是是建立异构分布式环境下海量建立异构分布式环境下海量数据的一体化存储、管理、访问、传输与服务的架构和环境数据的一体化存储、管理、访问、传输与服务的架构和环境。l 2007 2007年年云计算云计算的出现，对数据的管理提出了更高的要求。的出现，对数据的管理提出了更高的要求。Amazon S3Amazon S3在在不到一年的时间里，就已拥有不到一年的时间里，就已拥有5050亿个对象。亿个对象。SaaSSaaS的代表性公司的代表性公司SalesforceSalesforce“交易量交易量”（即该公司数据库调用应用编程接口（即该公司数据库

5、调用应用编程接口APIAPI的次数）已在的次数）已在3 3年内从年内从5 5亿亿次次/季度窜升到季度窜升到5454亿次亿次/季度。季度。l 3 2.2.互联网数据资源存储和管理面临的基本问题互联网数据资源存储和管理面临的基本问题 （1 1）如何存储和管理规模剧增的数据如何存储和管理规模剧增的数据？（2 2）如何帮助用户从海量信息中快速定位并获取自己需要的信息如何帮助用户从海量信息中快速定位并获取自己需要的信息？l （3 3）如何有效集成多源、异构、自主变化的信息源如何有效集成多源、异构、自主变化的信息源？l l3.3.对数据管理对数据管理有迫切有迫切要求要求的互联网应用系统的互联网应用系统l

6、随着互联网上大量数据的产生，以数据为中心的互联网应用也在突飞猛随着互联网上大量数据的产生，以数据为中心的互联网应用也在突飞猛进地发展，下面是集中对数据管理有着迫切需求的互联网应用举例：进地发展，下面是集中对数据管理有着迫切需求的互联网应用举例：l （1 1）数据网格和数据库网格）数据网格和数据库网格l （2 2）WebWeb信息集成应用信息集成应用l （3 3）搜索和日志分析等互联网应用）搜索和日志分析等互联网应用 （4 4）支持多租户的）支持多租户的SaaSSaaS应用应用l 互联网环境下，要求数据可伸缩能力强，应对快速变化和增长的能力高互联网环境下，要求数据可伸缩能力强，应对快速变化和增长

7、的能力高，而关系数据库在单一节点上有很好的可伸缩能力，涉及多个节点时则显出，而关系数据库在单一节点上有很好的可伸缩能力，涉及多个节点时则显出不足，一种新型的不足，一种新型的面向互联网的面向互联网的KVKV数据库数据库（Key/Value StoreKey/Value Store）产生，它是）产生，它是针对互联网规模数据管理需要的主要解决方案之一。针对互联网规模数据管理需要的主要解决方案之一。9.2 分布式分布式Key/Value数据存储与管理数据存储与管理l 传统关系数据库发展已经有传统关系数据库发展已经有40年的历史，在此期间出现了很多成熟和应年的历史，在此期间出现了很多成熟和应用广泛的关系

8、型数据库管理系统，如用广泛的关系型数据库管理系统，如Oracle MS、SQL Server和和 MySQL等等。然而，在互联网计算环境下，传统关系数据库遇到了新的挑战。然而，在互联网计算环境下，传统关系数据库遇到了新的挑战。l 传统关系数据库是针对结构化数据以及这些数据之上的复杂查询设计的传统关系数据库是针对结构化数据以及这些数据之上的复杂查询设计的。互联网计算环境下，互联网计算环境下，数据的规模较大，要处理的互联网数据有很多是非结数据的规模较大，要处理的互联网数据有很多是非结构化的数据，很多互联网应用构化的数据，很多互联网应用（例如互联网搜索、电子商务等应用）（例如互联网搜索、电子商务等应

9、用）并不需并不需要对数据进行复杂的查询要对数据进行复杂的查询，这就使得传统关系型数据库的一些优点在互联网，这就使得传统关系型数据库的一些优点在互联网环境下反而成为了缺点。环境下反而成为了缺点。l 传统关系数据库对事务的管理的严格要求也严重影响了系统在分布式环传统关系数据库对事务的管理的严格要求也严重影响了系统在分布式环境下的可用、可伸缩性等性质保障。境下的可用、可伸缩性等性质保障。互联网环境中处理互联网环境中处理的的数据规模较大，数数据规模较大，数据存储必须便于扩展据存储必须便于扩展，并且，并且大多是非结构化的数据；大多是非结构化的数据；而而关系数据库数据结构关系数据库数据结构化、为进行复杂的

10、数据查询设计化、为进行复杂的数据查询设计、表结构较为复杂表结构较为复杂、不便于在分布式环境下不便于在分布式环境下进行数据扩展进行数据扩展。l 分布式分布式key/value存储系统比关系数据库更适于互联网环境存储系统比关系数据库更适于互联网环境，所以，所以，只需只需主键简单查询的需求广泛存在于互联网应用主键简单查询的需求广泛存在于互联网应用中中，分布式，分布式key/value存储和管存储和管理系统日益受到重视理系统日益受到重视。45 一一个好的个好的 key/value存储存储系统系统需要满需要满足以下条件：足以下条件：l （1）Availability 可用性可用性l （2）Scalabi

11、lity 可扩展性可扩展性l （3）Failover 故障恢复故障恢复l （4）Performance 高性能高性能 简单来说，就是数据不能丢失，服务不能中断，能对故障进行感简单来说，就是数据不能丢失，服务不能中断，能对故障进行感知并能自动恢复，读写性能极高。知并能自动恢复，读写性能极高。下面先介绍下面先介绍key/valuekey/value的数据结构的数据结构，然后介绍为了满足上面要求，然后介绍为了满足上面要求，用到的相关技术：，用到的相关技术：数据划分数据划分、复制和一致性保障复制和一致性保障、可用性保障可用性保障。9 9.2.1.2.1 基础数据结构及数据访问基础数据结构及数据访问l1

12、.key/value的数据结构的数据结构：域域(Domain)数据项数据项(Item)l 域域类似于类似于传统关系数据库中的传统关系数据库中的“表表”，但，但域域无结构无结构，作用是作用是容纳数据项容纳数据项；数据项数据项用用Key定义，一个域中的定义，一个域中的不同不同数据项可数据项可能能具有不同的结构，数据属性全部是字符串类型，但在有些实现具有不同的结构，数据属性全部是字符串类型，但在有些实现中，属性也可以具有简单的类型，如整型、字符串数组等。中，属性也可以具有简单的类型，如整型、字符串数组等。l2.Key/Value数据模型和关系数据库模型举例数据模型和关系数据库模型举例l 一个域中，不

13、同数据项中很可能有重复存储的数据内容，一个域中，不同数据项中很可能有重复存储的数据内容，好在由于磁盘的单位价格越来越低，重复存储并不是很大的问好在由于磁盘的单位价格越来越低，重复存储并不是很大的问题了，而这种数据结构却为系统的可伸缩性带来了很大的便利题了，而这种数据结构却为系统的可伸缩性带来了很大的便利，数据可以容易得扩展到其他机器上。，数据可以容易得扩展到其他机器上。67 关系数据库关系数据库模型如下图模型如下图：一个Key/Value数据模型例子如下图：8 l 3.3.关系数据库中的关系数据库中的SQL SQL 与与Key/ValueKey/Value模型中的模型中的 APIAPIl l

14、关系数据库的数据创建、更新、删除和获取都使用关系数据库的数据创建、更新、删除和获取都使用SQLSQL完成，完成，SQLSQL查查询可以从单个表或者通过多个表的询可以从单个表或者通过多个表的JoinJoin操作来获取数据，操作来获取数据，SQLSQL查询包括查询包括聚集、复杂的数据过滤等功能。传统关系数据库还包括将一些数据处理聚集、复杂的数据过滤等功能。传统关系数据库还包括将一些数据处理逻辑嵌入到数据存储中的实现，例如存储过程、触发器等。逻辑嵌入到数据存储中的实现，例如存储过程、触发器等。l l Key/ValueKey/Value数据的创建、更新、删除和获取都是用数据的创建、更新、删除和获取都

15、是用APIAPI方法调用。方法调用。例如：亚马逊的分布式例如：亚马逊的分布式Key/ValueKey/Value数据存储与管理系统数据存储与管理系统DynamoDynamo是是通过一通过一个简单的接口将对象与个简单的接口将对象与keykey关联，它暴露了两个操作：关联，它暴露了两个操作：get()get()和和put()put()。l l Key/Value Key/Value已有广泛的应用，如已有广泛的应用，如Amazon Dynamo,Yahoo!PNUTSAmazon Dynamo,Yahoo!PNUTS等，等，也有一些也有一些Key/ValueKey/Value的变体，如的变体，如Go

16、ogle Google BigTableBigTable,FacebookFacebook Cassandra,Cassandra,HyperTableHyperTable等等.4.Key/Value4.Key/Value的特的特点点 l 数据模型数据模型：无数据模式，与数据项相关的内容都存储在一个单独的数：无数据模式，与数据项相关的内容都存储在一个单独的数据项中据项中l 要获取一个数据项的相关内容无需多个表之间的要获取一个数据项的相关内容无需多个表之间的JoinJoin操作操作l 便于扩展便于扩展l 重复存储重复存储l 在数据模型设计时，没有范式的概念，没有表示关系和关系约在数据模型设计时，

17、没有范式的概念，没有表示关系和关系约束的机制（增加了应用程序的负担）束的机制（增加了应用程序的负担）数据访问机制数据访问机制:l API，而非，而非SQL，少数提供类似，少数提供类似SQL的语法定义过滤规则的语法定义过滤规则。l 关系数据库有存储过程、触发器等，将数据处理逻辑在数据存储和管关系数据库有存储过程、触发器等，将数据处理逻辑在数据存储和管理系统中实现，但理系统中实现，但Key/Value的这些处理逻辑全部实现在应用代码中。的这些处理逻辑全部实现在应用代码中。l 应用接口应用接口:l SOAP/REST服务接口服务接口l 一个数据项和一个一个数据项和一个“对象对象”对应，直接映射到应用

18、程序代码，无需进行对应，直接映射到应用程序代码，无需进行对象关系映射对象关系映射.910 l 5.Key/Value5.Key/Value数据模式与关系数据库的比数据模式与关系数据库的比较较lKey/ValueKey/Value的优点：的优点：l 便于扩展，适于云计算的环境便于扩展，适于云计算的环境l 与应用程序代码的兼容性更好与应用程序代码的兼容性更好lKey/ValueKey/Value的缺点：的缺点：l 数据完整性约束转移至应用程序数据完整性约束转移至应用程序l 目前的很多目前的很多Key/ValueKey/Value数据存储系统之间不兼容数据存储系统之间不兼容l 在云环境中，很多用户和

19、应用使用同一个系统。为了避免一在云环境中，很多用户和应用使用同一个系统。为了避免一个进程使共享环境超载，往往严格限制一个单独的查询所能够产生的全个进程使共享环境超载，往往严格限制一个单独的查询所能够产生的全局影响。局影响。l 例如，在例如，在Amazon Simple DBAmazon Simple DB中，不允许用户运行一个超过中，不允许用户运行一个超过5 5秒钟秒钟的查询，在的查询，在GoolgeGoolge AppEngineAppEngine数据存储中，用户一次查询返回的数据项数据存储中，用户一次查询返回的数据项只允许在只允许在10001000条以内。这对于很多商业应用来说，是不现实的

20、。特别是条以内。这对于很多商业应用来说，是不现实的。特别是对于数据分析应用，例如用户使用模式跟踪、推荐系统等来说，这样的对于数据分析应用，例如用户使用模式跟踪、推荐系统等来说，这样的限制是不可容忍的。限制是不可容忍的。l11 l 9 9.2.2 .2.2 数据划分数据划分l l 因为系统要具备高扩展性，因此，增加因为系统要具备高扩展性，因此，增加和和删除机器是频繁的操作，删除机器是频繁的操作，如何将数据均匀分散到集群中呢？如何将数据均匀分散到集群中呢？采用的方法就是对数据进行切分。采用的方法就是对数据进行切分。l l 数据切分数据切分：在系统扩展时，系统提供一定的机制将数据切分到新增的：在系统

21、扩展时，系统提供一定的机制将数据切分到新增的机器（或节点）上。在分布式机器（或节点）上。在分布式Key/Value数据存储系统中，一般将切分功数据存储系统中，一般将切分功能以数据自动迁移的方式实现能以数据自动迁移的方式实现。在数据存储系统中在数据存储系统中，有三种数据切分技，有三种数据切分技术：术：基于基于简单简单哈希算法的哈希算法的Key/Value数据切分机制数据切分机制、基于一致性哈希算基于一致性哈希算法的数据切分机制法的数据切分机制、基于映射表的数据切分机制基于映射表的数据切分机制。l1.基于基于简单简单哈希算法的哈希算法的Key/Value数据切分机制数据切分机制l 基本原理：根据基

22、本原理：根据Key和哈希算法来决定数据存储的节点和哈希算法来决定数据存储的节点.l 算法：有算法：有N个个cache服务器（后面简称服务器（后面简称cache），将一个数据对象），将一个数据对象object映射到映射到N个个cache上，采用上，采用哈希算法哈希算法：hash(object)%N，得到数，得到数据据object的的hash值，然后将数据对象均匀的映射到到值，然后将数据对象均匀的映射到到N个个cache服务器上服务器上。l l 例如：某互联网应用系统例如：某互联网应用系统拥有拥有10个数据库节点个数据库节点，用户，用户ID作为数据作为数据的的Key，采用简单哈希算法，采用简单哈希

23、算法，即使用即使用用户用户ID值对节点总数值对节点总数取模，余数就是取模，余数就是数据存数据存储位置所在节点储位置所在节点，即：所在节点，即：所在节点=用户用户ID%总节点数总节点数。那么，用户那么，用户ID为为125的用户所在节点为：的用户所在节点为：125%10=5，即，即编号为编号为5的节点上。的节点上。l 一切都运行正常，再考虑如下的两种情况；一切都运行正常，再考虑如下的两种情况；l（1）一个一个cache服务器服务器m down掉了，这样所有映射到掉了，这样所有映射到cache m的对象都的对象都会失效，怎么办，需要把会失效，怎么办，需要把cache m从从cache中移除，这时候中

24、移除，这时候cache是是N-1台台，映射公式变成了，映射公式变成了hash(object)%(N-1)；l（2）由于访问加重，需要添加由于访问加重，需要添加cache，这时候，这时候cache是是N+1台，映射公式台，映射公式变成了变成了hash(object)%(N+1)；l （1）和（）和（2）意味着什么？这意味着突然之间几乎所有的）意味着什么？这意味着突然之间几乎所有的cache都失效都失效了；对于服务器而言，这是一场灾难，洪水般的访问都会直接冲向后台服了；对于服务器而言，这是一场灾难，洪水般的访问都会直接冲向后台服务器。务器。l 再来考虑第三个问题，由于硬件能力越来越强，你可能想让后

25、面添加的再来考虑第三个问题，由于硬件能力越来越强，你可能想让后面添加的节点多做点活，显然上面的节点多做点活，显然上面的hash算法也做不到。算法也做不到。l 简单简单哈希算法哈希算法优点：优点：简单、快速简单、快速。l 简单简单哈希算法哈希算法缺点：缺点：当节点加入或者退出时，原有的数据将定位到不同当节点加入或者退出时，原有的数据将定位到不同的节点上，当节点数多时，数据迁移的代价很高的节点上，当节点数多时，数据迁移的代价很高.l 12 2.基于一致性哈希算法的数据切分机制基于一致性哈希算法的数据切分机制l 采用简单采用简单hash取模的办法，增加机器的瞬间需要对数据进行迁移，等待取模的办法，增

26、加机器的瞬间需要对数据进行迁移，等待机器预热，数据无法读取机器预热，数据无法读取，这是很不好的办法。目前比较公认的解决办法就是这是很不好的办法。目前比较公认的解决办法就是一致性哈希一致性哈希(consistent hashing)。l 一致性哈希算法一致性哈希算法：哈希函数的输出范围被看作一个固定的哈希函数的输出范围被看作一个固定的“环环”。系统中。系统中的的每个节点被赋予环中的一个随机值每个节点被赋予环中的一个随机值，该随机值用来表示其在，该随机值用来表示其在“环环”中的位置。中的位置。每个每个“键值键值”对应一个数据项，根据该键值的哈希值可生成数据项在环中的位置对应一个数据项，根据该键值的

27、哈希值可生成数据项在环中的位置position=hash(key)，然后顺时针沿着环找到，然后顺时针沿着环找到value大于大于position的第一个的第一个节点，这个节点就是该数据项的存储节点。节点，这个节点就是该数据项的存储节点。l 下面就来按照下面就来按照5个步骤简单介绍个步骤简单介绍consistent hashing算法的基本原理。算法的基本原理。l（1）环形）环形hash空间空间 考虑通常的考虑通常的hash算法都是将算法都是将value映射到一个映射到一个32位的位的key值，也即是值，也即是0232-1次方的数值空间；我们可以将这个空间想象成一个首（次方的数值空间；我们可以将

28、这个空间想象成一个首（0）尾（）尾（232-1）相接的圆环，如下面图）相接的圆环，如下面图1所示的那样：所示的那样：13l（2）把数据对象映射到把数据对象映射到hash空间空间l 接下来考虑接下来考虑4个对象个对象object1object4，通过，通过hash函数计算出函数计算出的的hash值值key在环上的分布如下图所示。在环上的分布如下图所示。lhash(object1)=key1;l lhash(object4)=key4;14l（3）把把cache映射到映射到hash空间空间lConsistent hashing的基本思想就是将对象和的基本思想就是将对象和cache都映射到同一个都映

29、射到同一个hash数值空间中，并且使用相同的数值空间中，并且使用相同的hash算法。算法。l假设当前有假设当前有A,B和和C共共3台台cache，那么其映射结果将如图，那么其映射结果将如图3所示，他们在所示，他们在hash空间中，以对应的空间中，以对应的hash值排列。值排列。lhash(cache A)=key A;l lhash(cache C)=key C;l cache的的hash计算：一般的方法可以使用计算：一般的方法可以使用cache机器的机器的IP地址或者机器地址或者机器名作为名作为hash输入。输入。15l（4）把对象映射到把对象映射到cachel 现在现在cache和对象都已

30、经通过同一个和对象都已经通过同一个hash算法映射到算法映射到hash数值空间数值空间中了，接下来要考虑的就是如何将数据对象映射到服务器中了，接下来要考虑的就是如何将数据对象映射到服务器cache上面了。上面了。l 在这个环形空间中，如果沿着顺时针方向从对象的在这个环形空间中，如果沿着顺时针方向从对象的key值出发，直到值出发，直到遇见遇见一个一个cache，那么就将该对象存储在这个，那么就将该对象存储在这个cache上，因为对象和上，因为对象和cache的的hash值是固定的，因此这个值是固定的，因此这个cache必然是唯一和确定的。这样就必然是唯一和确定的。这样就找到了对象和找到了对象和c

31、ache的映射方法！的映射方法！l 依然继续上面的例子，那么根据上面的方法，数据对象依然继续上面的例子，那么根据上面的方法，数据对象object1将被将被存储到服务器存储到服务器cache A上；上；object2和和object3对应到对应到cache C；object4对对应到应到cache B。16l（5 5）考察考察cachecache的变动的变动l 前面讲过，通过简单前面讲过，通过简单hash然后求余的方法带来的最大问题就在于：当然后求余的方法带来的最大问题就在于：当cache有所变动时，有所变动时，cache会失效，进而对后台服务器造成巨大的冲击，现会失效，进而对后台服务器造成巨大

32、的冲击，现在就来分析分析在就来分析分析consistent hashing算法。算法。l（a）移除）移除cachel 考虑假设考虑假设cache B挂掉了，根据上面讲到的映射方法，这时受影响的挂掉了，根据上面讲到的映射方法，这时受影响的将仅是那些沿将仅是那些沿cache B逆时针遍历直到下一个逆时针遍历直到下一个cache（cache A）之间的）之间的对象，也即是本来映射到对象，也即是本来映射到cache B上的那些数据对象。上的那些数据对象。l 因此这里仅需要变动对象因此这里仅需要变动对象object4，将其重新映射到，将其重新映射到cache C上即可；上即可；参见下图。参见下图。17l

33、（b）添加添加cachel 再考虑添加一台新的再考虑添加一台新的cache D的情况，假设在这个环形的情况，假设在这个环形hash空间中空间中，cache D被映射在对象被映射在对象object2和和object3之间。这时受影响的将仅是那之间。这时受影响的将仅是那些沿些沿cache D逆时针遍历直到下一个逆时针遍历直到下一个cache（cache B）之间的对象（它）之间的对象（它们是本来映射到们是本来映射到cache C上对象的一部分），将这些对象重新映射到上对象的一部分），将这些对象重新映射到cache D上即可。上即可。l 因此这里仅需要变动对象因此这里仅需要变动对象object2，将

34、其重新映射到，将其重新映射到cache D上。上。一致性哈希一致性哈希算法算法优点：优点：每个节点都负责存储环中该节点与其后继节每个节点都负责存储环中该节点与其后继节点之间区域对应的存储对象，也称为点之间区域对应的存储对象，也称为“区间负责制区间负责制”。区间负责制使得节。区间负责制使得节点的加入和退出只需要其邻居节点进行数据迁移，而不影响其它节点点的加入和退出只需要其邻居节点进行数据迁移，而不影响其它节点l 一致性哈希一致性哈希算法算法缺点：缺点：采用随机的位置值来决定数据项存储在哪个采用随机的位置值来决定数据项存储在哪个节点上，这导致节点之间负载不均衡。节点上，这导致节点之间负载不均衡。l

35、 比如在上面的例子中，仅部署比如在上面的例子中，仅部署cache A和和cache C的情况下，在的情况下，在4个对个对象中，象中，cache A仅存储了仅存储了object1，而，而cache C则存储了则存储了object2、object3和和object4；分布是很不均衡的。；分布是很不均衡的。l 为了解决这种情况，为了解决这种情况，consistent hashing引入了引入了“虚拟节点虚拟节点”的概的概念，它可以如下定义：念，它可以如下定义：18l “虚拟节点虚拟节点”（virtual nodevirtual node）是实际节点在）是实际节点在hashhash空间的复制品（空间的

36、复制品（replicareplica），一实际个节点对应了若干个），一实际个节点对应了若干个“虚拟节点虚拟节点”，这个对应个数也，这个对应个数也成为成为“复制个数复制个数”，“虚拟节点虚拟节点”在在hashhash空间中以空间中以hashhash值排列。值排列。l 仍以仅部署仍以仅部署cache Acache A和和cache Ccache C的情况为例，的情况为例，cachecache分布并不均匀。分布并不均匀。现在我们引入虚拟节点，并设置现在我们引入虚拟节点，并设置“复制个数复制个数”为为2 2，这就意味着一共会存，这就意味着一共会存在在4 4个个“虚拟节点虚拟节点”，cache A1,c

37、ache A2cache A1,cache A2代表了代表了cache Acache A；cache C1,cache C1,cache C2cache C2代表了代表了cache Ccache C；假设一种比较理想的情况，参见下图：；假设一种比较理想的情况，参见下图：1920 3.基于映射表的数据切分机制基于映射表的数据切分机制l 对数据进行水平切分，数据存放在哪个节点上是非常灵活的（并不对数据进行水平切分，数据存放在哪个节点上是非常灵活的（并不一定是根据哈希函数来决定）一定是根据哈希函数来决定）l 将数据和存储单元之间的映射关系存放在一个单独的表中，当需要将数据和存储单元之间的映射关系存放

38、在一个单独的表中，当需要访问某个节点的时候，首先去映射表中查找，找到以后再定位到相应节访问某个节点的时候，首先去映射表中查找，找到以后再定位到相应节点点l例子：例子：lKey NodeIDl18 2l198 7l 17 6l 25 9l l 根据此表可以确认用户根据此表可以确认用户ID为为17的用户所在的节点是的用户所在的节点是6，那么就可以，那么就可以迅速定位到该节点，并进行数据的处理。迅速定位到该节点，并进行数据的处理。9.2.3 复制和一致性保障复制和一致性保障l 在分布式在分布式Key/ValueKey/Value数据存储系统中，为了获得更好的可用性和持数据存储系统中，为了获得更好的可

39、用性和持久性，需要将久性，需要将数据复制到多个节点数据复制到多个节点上。上。l 在大规模互联网计算环境下，出于提高系统可用性的考虑，分布在大规模互联网计算环境下，出于提高系统可用性的考虑，分布式式Key/ValueKey/Value数据存储系统在副本数据的一致性保障方面最典型的一个数据存储系统在副本数据的一致性保障方面最典型的一个特征是特征是不保证严格的一致性不保证严格的一致性。其中，。其中，最终一致性最终一致性是大多数分布式是大多数分布式Key/ValueKey/Value存储系统的选择，即只保障更新操作最终被传播到各个副本存储系统的选择，即只保障更新操作最终被传播到各个副本上，而在此之前，

40、各个副本的数据之间可能会出现冲突。上，而在此之前，各个副本的数据之间可能会出现冲突。l 此外，还有一些分布式此外，还有一些分布式Key/ValueKey/Value存储系统选择在严格一致性和最存储系统选择在严格一致性和最终一致性之间的折中方案。终一致性之间的折中方案。l 在分布式系统中，在分布式系统中，复制协议包括两种类型：主动复制和基于法定复制协议包括两种类型：主动复制和基于法定数量的协议。数量的协议。l 主动复制主动复制：每个副本有一个关联的进程，该进程执行更新操作。：每个副本有一个关联的进程，该进程执行更新操作。操作被发送到操作被发送到每个副每个副本。本。l 基于法定数量的协议基于法定数

41、量的协议，其基本思想是：在读或写一个复制的数据，其基本思想是：在读或写一个复制的数据项之前要求申请并获得项之前要求申请并获得多个服务器多个服务器的允许。的允许。21 1.1.分布式系统中的数据复制和一致性保障机制分布式系统中的数据复制和一致性保障机制 l 为了达到高可用性和数据不丢失，需要通过复制将数据备份到多台机器为了达到高可用性和数据不丢失，需要通过复制将数据备份到多台机器，replication(复制机制复制机制)的实现一般是通过的实现一般是通过Master与与replica之间的之间的TCP/IP连连接，然后根据相应的一致性策略将数据分发到接，然后根据相应的一致性策略将数据分发到rep

42、lica上，这里的上，这里的一致性策略一致性策略主要包括两项主要包括两项：l （1)replica1)replica能够延迟能够延迟mastermaster的时间，就是说，在这个时间内更新的数据的时间，就是说，在这个时间内更新的数据，replicareplica可能是看不到的。例如你设置的一致性时间是可能是看不到的。例如你设置的一致性时间是3s3s，那么在某个特，那么在某个特定的时刻，定的时刻，replicareplica上的数据实际上可能是上的数据实际上可能是master 3s master 3s 以前的以前的snapshotsnapshot。l （2 2）mastermaster事务提交返

43、回之前是否需要得到事务提交返回之前是否需要得到replicareplica的确认。为了尽量的确认。为了尽量保证数据不丢失，保证数据不丢失，mastermaster需要得到一定数量的需要得到一定数量的replicareplica确认数据更新成功之确认数据更新成功之后才能提交事务。后才能提交事务。l 关于数据可靠性和性能之间，是需要进行折衷的，很显然，越是高的关于数据可靠性和性能之间，是需要进行折衷的，很显然，越是高的数据保障，那么性能肯定会受到影响。在这样的情况下，需要对上层的应用数据保障，那么性能肯定会受到影响。在这样的情况下，需要对上层的应用进行分析，看是否允许丢失一部分数据。进行分析，看是

44、否允许丢失一部分数据。l 另外，还有一个问题就是，数据的同步是采用另外，还有一个问题就是，数据的同步是采用mastermaster分发还是分发还是replicareplica定时请求的问题，两者各有优缺点，前者会在定时请求的问题，两者各有优缺点，前者会在replicareplica较多的情况下遇到瓶较多的情况下遇到瓶颈，而后者可能会有一些延迟。颈，而后者可能会有一些延迟。22l master管理管理写写请求而请求而replica管理读请求，至于如何决定读管理读请求，至于如何决定读写请求的分发，可以使用写请求的分发，可以使用monitor节点，由它来作为读写的入口，节点，由它来作为读写的入口，如

45、下图，然后如下图，然后Monitor管理集群的状态和生命周期，例如管理集群的状态和生命周期，例如Master fail后，后，monitor将收到事件，它将发起一次选举选出新的将收到事件，它将发起一次选举选出新的Master，一般的选举算法就是在集群中寻找最后一次更新的节点，因为，一般的选举算法就是在集群中寻找最后一次更新的节点，因为往往它的数据是最新。往往它的数据是最新。l 还有就是在有新的机器加入集群的情况下，还有就是在有新的机器加入集群的情况下，Monitor会告诉新会告诉新机器集群内的机器集群内的master是谁，是谁，replica机器才能与机器才能与master取得连接同取得连接同

46、步数据。步数据。23l 2.Key/Value 2.Key/Value 一致性模型的实现机制一致性模型的实现机制举例举例l -Dynamo -Dynamo的最终一致性的最终一致性l l 前提：始终可写前提：始终可写“always writable”l 数据项的写操作无需等到更新操作传播到所有副本上便可返回给数据项的写操作无需等到更新操作传播到所有副本上便可返回给客户，这就会导致随后的读操作可能会读到更新操作之前的数据版本。客户，这就会导致随后的读操作可能会读到更新操作之前的数据版本。在没有任何节点失效发生的情况下，更新操作最终会传播到所有副本。在没有任何节点失效发生的情况下，更新操作最终会传播

47、到所有副本。l Dynamo最终一致性的实现最终一致性的实现机制机制：配额设置：配额设置l 三个关键参数三个关键参数(N,R,W)：l N指一份数据将被复制到指一份数据将被复制到N 个节点上；个节点上；l R表示在读取某一存储的数据时，最少参与节点数，也就是最少需表示在读取某一存储的数据时，最少参与节点数，也就是最少需要有多少个节点返回存储的信息才算是成功读取了该数据内容；要有多少个节点返回存储的信息才算是成功读取了该数据内容；l W表示在存储某一个数据时，最少参与节点数，也就是最少要有表示在存储某一个数据时，最少参与节点数，也就是最少要有多少个节点表示存储成功才算是成功存储了该数据。多少个节

48、点表示存储成功才算是成功存储了该数据。24 配额设置配额设置用来灵活地调整系统的可用性与一致性用来灵活地调整系统的可用性与一致性，比如，比如,N=3时时l （1）如果如果R=1，表示最少只需要去一个节点读数据即可，读到即，表示最少只需要去一个节点读数据即可，读到即返回，这时是可用性是很高的，但并不能保证数据的一致性；返回，这时是可用性是很高的，但并不能保证数据的一致性；l （2）如果如果R=1，W=1，那可用性更新是最高的一种情况，但这，那可用性更新是最高的一种情况，但这时完全不能保障数据的一致性，因为在可供复制的时完全不能保障数据的一致性，因为在可供复制的N个节点里，只需个节点里，只需要写成

49、功一次就返回了，也就意味着，有可能在读的这一次并没有真要写成功一次就返回了，也就意味着，有可能在读的这一次并没有真正读到需要的数据（一致性相当的不好）。正读到需要的数据（一致性相当的不好）。l (3)如果如果W=R=3，每次写的时候，都保证所有要复制的点都写成，每次写的时候，都保证所有要复制的点都写成功，读的时候也是都读到，这样子读出来的数据一定是正确的，但是功，读的时候也是都读到，这样子读出来的数据一定是正确的，但是其性能大打折扣，也就是说，数据的一致性非常的高，但系统的可用其性能大打折扣，也就是说，数据的一致性非常的高，但系统的可用性却非常低了。性却非常低了。l 复制中的一致性，采用类似于

50、基于法定数量协议实现。复制中的一致性，采用类似于基于法定数量协议实现。l 当配置当配置R+W N时，就和法定数量的协议完全一样时，就和法定数量的协议完全一样；读读(或写或写)操操作的延迟是由作的延迟是由R(或或W)副本中最慢的副本来决定的。副本中最慢的副本来决定的。l (N,R,W)的值典型设置为的值典型设置为(3,2,2),兼顾性能与可用性。兼顾性能与可用性。R 和和W 直直接影响性能、扩展性、一致性接影响性能、扩展性、一致性。l l 25l 9.2.4 可用性保障机制可用性保障机制 1.节点失效情况下的冲突解决节点失效情况下的冲突解决l l 在分布式在分布式Key/ValueKey/Val