云计算核心算法（二）

云计算核心算法（二）

二、DHT算法

  从整个计算机发展历史来看，集中式与分布式计算模式交替占了一段历史时期。如今，云计算应用中各大公司都建立了自己的数据中心和计算中心。当云计算的应用越来越多，用户越来越多后，集中式的计算模式将受到网络带宽等因素的制约。P2P是云计算的未来。云计算与物联网的计算模式未来5年后将主要采用P2P计算模式（对等计算模式）。Client/Server计算模式（客户—服务器计算模式）主要应用于小规模的网络环境。Client/Server计算模式采用中央集中式架构，中央节点（服务器）对整个网络服务具有决定性的作用。如果服务器失效，则整个服务失效。这就是所谓的“单点失效问题”。此外，大部分的计算都集中在服务器端，因而引起负载的不平衡。即所谓的“服务器端的计算瓶颈”，而客户机端则存在资源浪费的情况。此外，集中式计算模式对用户的隐私以及数据安全也将存在不可能解决的难题。P2P计算模式是一种非集中计算模式。P2P网络中的每台计算机（或称对等点），具有同样的地位，既可以请求服务，也可以提供服务。P2P计算模式具有资源充分利用，网络规模可扩展（节点越多网络越稳定，不存在瓶颈）等优点。下一代计算机网络（云计算和物联网）都是巨大的网络，因此，未来的计算模式应该是P2P计算模式。

  P2P按照拓扑结构的不同可以分为三种。   （1）集中式拓扑模式，如apster。这种模式必须有中央服务器。当系统中节点数增多时，中央服务器就成为系统的瓶颈。   （2）分布式非结构化拓扑模式，如Gnutella和Freenet。在非结构化P2P系统中，信息搜索的算法难免会带有一定的盲目性。   （）分布式结构化拓扑模式。基于DHT技术，如Chord、CA、Pastry和Tapestry。由于用户预先知道应该搜索哪些节点，避免了非结构化P2P系统中使用的泛洪式查，提高了信息搜索的效率。

（一）DHT原理介绍

  DHT中主要使用相容哈希函数进行散列。相容哈希又称一致性哈希 (Cistem Hashing)。相容哈希为每个节点和关键词分配m位的标识符。标志符长度越长，则经过Hash后得到的值相同的可能性越小，因此只要使标志位数m足够大，可以认为关键字在Hash后得到了一个唯一的值。另外使用相容哈希得到的值能够体现负载均衡，节点在经过散列后得到的标识符ID，一般在散列空间中均匀分散，使得每个节点的负责管理的内容比较平均。DHT中常见的Hash函数有SHA-1、MD4、MD5等。其中SHA-1算法消息摘要的固定长度为160位，MD5算法为128位。   基于DHT进行网络资源定位的方式是一种结构化资源定位方法。如图所示，所谓DHT技术就是在P2P网络应用层和网络/路由层间假设单独的DHT层来进行P2P网络资源定位和查。DHT分布式哈希表采用Hash函数加速了查速度和增强了安全性，而且便于管理，同时不会占用太多的网络带宽。

  基于DHT分布式哈希表技术是与应用无关的技术，因为DHT层单独加入在应用层和下层通信层之间，可以不考虑具体的应用，只利用DHT层负责上层数据和下层通信节点之间查询和插入。利用哈希函数得到关键字并不能反映数据的含义，具体关键字的产生，又完全取决于应用层的开发者。DHT的应用层接口如图所示。DHT系统基本的操作就是LookUp(key)。由于系统中的每一个节点负责存储一定范围的关键字，通过LookUpd(key)操作返回一个存储该关键字节点的节点标识符 (odelD)，这个操作允许节点根据关键字进行存储和读取。通过DHT层LookUp(key)操作，可以把应用层的数据均匀分布在网络的各个节点内，这种方法使下层网络完全不受中心控制。

  DHT作为应用层接口与传统的应用层接口相比还具有更多的优点。传统应用层接口UDP/IP是通信中心的接口，一定要具体指出要查和发送数据的节点IP地址。由于现在的Internet过分依赖DS网关，只要其中有一个服务器出现“问题”，相应的其他任何服务就无法获得。DHT是以数据为中心的接口，只要给出与数据唯一对应的key就可以进行资源查，并不需要关心数据具体存放在哪个节点上和数据具体来自哪个应用。   DHT是一个好的共享下层设施，由于DHT使用资源名字不必再编码成位置或路由链路，这样形成一个统一的基于内容的命名层，增加了寻对象的灵活性。并且由于DHT也是一个均衡的体系结构，可以提供多种选择用于考虑在哪些节点空间存放对象副本，以及用哪一条路径寻存放对象副本来确保应用层的安全。基于DHT基础结构是自组织和自治的，所以不需要人们事先预见额外操作，这样就降低了执行、维护和管理的代价。使用DHT技术使一个实体并不知道它要保存什么样的数据，因此所有实体必须能够自愿地提供PC资源、网络带宽，并且能够接收任何类型的数据。   所有的DHT路由算法都主要包括三个方面，一是DHT的散列空间的描述，即如何进行散列。二是DHT中各节点如何分配管理散列空间，即散列后的信息如何决定其存储的节点位置。三是路由发现算法，即对散列值进行查询时节点如何高效地路由到存储目标信息的节点。

（二）Chord中DHT的具体实现

  Chord是由麻省理工学院的Ion Stoica等人设计的一种简单的结构化P2P搜索策略。

• Chord设计目标是提供一个具有完全分布、可扩展性及可用性好、负载均衡的P2P搜索策略。
• 后继节点successor：消息的目标节点就是节点ID大于或者等于消息Key值的节点中节点ID最小的一个。
• Chord环：Chord中所有节点按节点ID大小顺时针排列并首尾相接组成一个拥有2m（m一般为160）个节点的环空间。

  m=6且只有10个节点的查示意图，其中节点标识前加上而关键字标识前加上K加以区别，图中给出了节点8、42、51的finger表。

1. 节点的加入过程

  节点的加入过程如下。   步骤1，初始化新节点的指针表。假设节点在加入网络之前通过某种机制知道网络中的某个节点M。这时，为了初始化的指针表，将要求节点M为它查指针表中的其他表项。   步骤2，更新现有其他节点的指针表。节点加入网络后将调用其他节点的更新函数，让其他节点更新其指针表。   步骤，从后继节点把关键字传递到节点。这一步是把所有后继节点是的关键字转移到上。整个加入操作的时间复杂度是O(log2)，如果采用更复杂的算法，可以把复杂度降低到O(log)。

2. 节点的退出过程

  节点的退出过程如下。   在P2P网络中，某个对等节点随时可能退出系统或者发生失效，因此处理节点失效是一个更重要的问题。在Chord中，当节点失效时，所有指针表中包括的节点都必须把替换成的后继节点。另外，节点的失效不能影响系统中正在进行的查询过程。   在失效处理中最关键的步骤是维护正确的后继指针。为了保证这一点，每个Chord节点都维护一张包括t个最近后继的后继列表。如果节点注意到它的后继节点失效了，那么它就用后继列表中第一个正常节点替换已经失效了的节点。

（三）Pastry中DHT的具体实现

  Pastry是微软研究院提出的一种可扩展的分布式对象定位和路由协议，可用于构建大规模的P2P系统。在Pastry中，为每个节点分配一个128位的节点标识符，所有的节点标识符形成了一个环形的ID空间，ID范围从0到2

-1。   Pastry网络中的每个节点都有一个唯一的节点ID。当给定一条消息和一个关键字时，Pastry节点将会把这条消息路由到在当前所有的Pastry节点中节点ID和关键字最接近的那个节点。Pastry考虑了网络的位置信息，它的目标是使消息传递的距离短，距离按照节点ID的数值差来计算。每个Pastry节点记录在节点空间和它直接相邻的邻居节点，当新节点加入、原有节点失效和恢复时通知上层应用。   为了实现消息路由，每个Pastry节点都要维护一张状态表，状态表由Leaf set，Routing table和eighborhood set三张表组成。Pastry的路由过程是:当收到一条消息时，节点首先检查消息的关键字是否落在叶子节点集合中。如果是，则直接把消息转发给对应的节点，也就是叶子节点集合中节点号和关键字最接近的节点；如果关键字没有落在叶子节点集合中，那么将使用路由表进行路由。当前节点将会把消息发送给节点号和关键字直接的共同前缀至少比现在节点长一个数位的节点。当然，在某些情况下，会出现路由表对应表项为空，或者路由表表项对应的节点不可达。这时候消息将会被转发给共同前缀一样长的节点，但是该节点和当前节点相比，其节点号从数值上将更接近关键字。这样的节点一定位于叶子节点集合中。因此，只要叶子节点集合中不会出现一半以上的节点同时失效，路由过程就可以继续。从上述过程可以看出，路由的每一步和上一步相比都向目标节点前进了一步，因此这个过程是收敛的。

1. 节点的加入

• 假定新加入节点的节点号为，节点号的分配过程是由应用程序决定的。
• 在加入Pastry之前，需要知道一个相邻节点A的位置信息。
• 的加入过程主要包括初始化自己的节点数据结构，并通知其他节点自己已经加入系统。

2. 节点的退出

• Pastry网络中的节点可能会随时失效或者不发出通知离开系统。
• 当相邻节点不能和某个Pastry节点通信时，就认为该节点发生了失效。

（四）CA中DHT的具体实现

  CA是内容可编址网络（Content-Addressable etwork）的缩写。2001年由加州大学伯克利分校设计。   CA可以在Internet规模的大型对等网络上提供类似哈希表的功能。CA具有可扩展、容错和完全自组织等特点。CA类似于一张大哈希表，基本操作包括插入、查和删除。CA由大量自治的节点组成，每个节点保存哈希表的一部分，称为一个区。CA的设计完全是分布式的，不需要任何形式的中央控制点。CA具有很好的可扩展性，节点只需要维护少量的控制状态而且状态数量独立于系统中的节点数量。CA支持容错特性，节点可以绕过错误节点进行路由。

  整个区域坐标由5个节点A，B，C，D，E组成，每个节点负责部分区域，CA中通过哈希函数把资源映射到d维空间中的一点，资源对象就发布在该节点上。

  查询操作通过在d维笛卡儿坐标空间中转发查询消息被执行，转发从查询初始化点沿着坐标系上最接近直线的路径到达存储关键字的节点。

（五）Tapestry中DHT的具体实现

  Tapestry是由加州大学伯克利分校计算机系设计的分层路由和组织结构的查询算法，它为面向广域网的分布式应用提供了一个分布式查和路由定位基础平台。Tapestry网络中每个节点和文档通过哈希变换得到各自160位比特的唯一标识符，每个节点都拥有一个邻居表，记录邻居节点的信息。Tapestry基于文档标识符的后缀进行路由，即从标识符的最后一位开始依次向前一步一步逼近目标节点的标识符，直到达到最大程度的匹配。查询时，节点通过比较收到的文档标识符和本地保存的邻居节点的标识符，选择节点标识符和文档标识符有着最长后缀匹配的节点作为路由路径中的下一跳节点。   Tapestry基于Plax ton中提出的定位和路由机制进行优化。Plax ton提出了一种分布式数据结构，用于在网络范围内定位资源对象。在Plax ton中，每个节点都可以承担服务器（保存对象）、路由器（转发消息）和客户端（请求发起者）的功能。另外，对象和节点的标识符和它们的位置以及具体内容无关，用某种固定长度的位串采用随机方式确定。系统假定对象和节点的标识符在整个名字空间中是均匀分布的。   Tapestry采用的基本定位和路由机制和Plax ton很类似。Tapestry中的每个节点都可以用Plax ton中描述的算法转发消息。每张邻居映射表都按照路由层次组织，每个层次都包括匹配该层次对应的前缀并离该节点最近的一组节点。每个节点还维护一张后向指针列表指向把自己作为邻居的那些节点，在节点加入算法中会用到这些指针。

1. 节点的加入

• Tapestry的节点加入算法和Pastry很类似。
• 构造过程中还需要进行一些优化工作。
• 构造完自己的数据结构后，节点将通知网络中的其他节点，自己已经加入网络。

2. 节点的退出

• 一种情况是节点从网络中自行消失，在这种情况下，它的邻居可以检测到它已经退出网络并可以相应地调整路由表；
• 另一种机制是节点在退出系统之前，利用后向指针确定所有把它作为邻居的节点，这些节点会相应调整路由表并通知对象服务器该节点已经退出网络。

三、Gossip协议

  Gossip协议因为Cassandra而名声大噪，其完整定义最早由Demers提出，他在论文中介绍了一种传染病算法 (Epidemic Algorithm) 用于解决分布式数据库的数据备份问题。随后该协议被广泛用于异构环境下的信息分发、P2P网络节点信息管理等多种应用中。   Gossip协议如其名，灵感来自办公室八卦，只要一个人八卦一下，在有限的时间内，所有人都会知道该八卦的信息，这种信息传播方式与病毒传播类似，因此Gossip协议有众多别名：“闲话算法”、“疫情传播算法”、“病毒感染算法”、“谣言传播算法”等。在Demers提出该方法之前，Gossip协议的思想已经被广泛使用，洪泛查、路由算法等都归属这一范畴，不同的是Demers利用Gossip对这类算法提供了明确的语义、具体实施方法以及收敛性证明。   Gossip协议所使用的算法被称为反熵算法 (Anti-Entropy)。熵是物理学上的一个概念，反映系统的杂乱程度，反熵则意味着在杂乱无章中寻求一致。这充分说明了Gossip协议的特点：在一个有界的网络中，每个节点都随机地与其他节点通信，经过一番杂乱无章的阶段，最终所有节点的状态都达成一致。每个节点可能知道所有其他节点，也可能仅知道几个邻居节点，但只要这些节点通过网络连通，最终所有节点的状态都将是一致的。当然，这也是疫情传播的特点。

（一）Gossip协议的特点

  Gossip协议具有以下几个优点：   （1）分布式容错。当系统中有节点因为宕机而重启，或有新节点加入，经过一段时间后，这些节点的状态仍会与系统中其他节点达成一致，也就是说Gossip天然具有分布式容错的特点。   （2）最终一致性。Gossip协议虽然无法保证在某个时刻所有节点状态保持一致，但可以保证在“最终”所有节点一致。“最终”是一个现实中存在，但理论上难以证明的时间点。   （）去中心化。Gossip协议不要求节点知道系统中所有节点的状态，节点之间完全对等，不需要任何中心节点。

  Gossip协议的缺点也很明显，冗余通信会大大增加网络和CPU的负载，并进一步影响算法收敛的速度。

（二）Gossip协议的通信方式及收敛性

  传染病算法 (Epidemic Algorithm) 中存在三种不同单元：人口 (population)，交互 (a set of interactive)，交流 (communicating)。这三个单元通过既定规则决定如何传递信息。规则可以由用户自由设定，但是任意单元在特定时间 内必须处于以下三种状态之一。   （1）易受感染 (Susceptible)：单元不了解信息的内容，但可以收到这条信息。   （2）传染 (Infective)：单元知道（接收到）信息，按照指定规则进行传播。   （）恢复 (Recovered)：单元知道（接收到）信息，但不进行转发。

1. 感染-传染（Susceptible-Infective, SI）

  该类算法中几乎每个单元最初都设定为感染状态，当一个单元接收到更新的信息后立即转为传染状态，并保持这种状态直到所有单元都成为传染状态。假定一个单元中遇到的单元数为

，第

次循环后，传染者的相对数量为

，则有

易受感染单元相对数量

为

2. 感染—传染—感染（SIS）

  与SI算法模型不同，SIS算法可以决定在全部人口被传染前停止传播。在

次循环后，传染单元相对数量为

. 感染—传染—恢复（SIR）

  SIR算法和SIS算法唯一区别是恢复单元在停止传播信息之后便不再收到传染。

  Gossip协议属于SIR类传染病算法，早期的Gossip协议中，系统中的节点会将接收到的需要扩散的信息发送给它随机选择的邻居节点。通过这种冗余的信息频繁转发机制，Gossip协议无须依靠具体的机制去选择建立连接的节点，确保了在部分节点损坏和网络丢包率高的情况下信息扩散的可靠性。此外，当节点规模扩展后，每个节点的通信负载随着体规模以对数级速度缓慢增加，从而保证了系统通信的可扩展性。由于Gossip协议的高容错性，以及易扩展和部署等特性，非常适用于系统稳定但节点通信关系变化复杂的场景中。

（三）Gossip节点管理算法

1. 节点加入

  （1）接触 (Contact)。运行初期，节点的局部视图只包含这些接触记录。   （2）新加入 (ew subscription)。当一个节点收到一个新加入请求时，它会把新节点的标识符转发到局部视图里的所有成员。   （）转发加入 (Forward subscription)。这些被转发的加入请求或者被某个节点保留，或者被转发，直到一些节点将其保留才会消失。   （4）保持加入 (Keeping a subscription)。体中每个节点都会维护两张表：局部视图 (Partial View)、入度视图 (In View)。

2. 节点离开

  离开机制是用来控制节点局部视图大小的。机制的缺陷是一个节点可能需要在局部视图中保存某个节点的多个副本，或者保存自己的ID，此时只需要把相关ID删除即可。

（四）Cassandra中Gossip协议的具体实现方式

  有4台机器，分别用A、B、C、D表示，并且配置它们都是seed节点，当它们同时启动时，可能会出现如下情形。   （1）A节点启动了，发现不存在其他在线节点，走到步骤c，和任意一个seed节点同步，假设选择了seed节点B。   （2）B节点和A节点完成同步，则认为A在线，它将和A同步，由于A是种子，B将不再和其他种子节点同步。   （）C节点启动后发现没有其他节点在线，同样走到步骤C，和任意一个seed节点同步，假设这次恰好选择了seed节点D。   （4）D节点和C节点完成同步，则认为C在线，它将和C同步，由于C是种子，D将不再和其他种子节点同步。

  下面介绍一下Cassandra中Gossip协议的数据结构。Gossip协议通信的状态信息主要有三种：   （1）EndPointState封装了一个节点的所有ApplicationState和HeartBeatState。   （2）HeartBeatState由generation和version组成：generation每次启动都会变化，用于区分机器重启前后的状态；version只能增长，每次心跳之前进行递增。   （）ApplicationState用于表示系统的状态，由state和version组成：state表示节点的状态；version是递增的，每个对象表示节点一种状态。

（五）CoolStreaming系统中Gossip协议的具体实现方式

1. 节点管理

  CoolStreaming中存在三类节点。   （1）伙伴节点 (partner)：某个节点维护了系统中部分其他节点信息的列表，称这些节点为该节点的伙伴节点或候选节点。   （2）请求节点 (requester) 与活动节点 (supplier)：节点A从他的伙伴节点中挑选出一个子集E，由这个子集中的节点为A提供流媒体数据，则称节点A为请求节点或接收节点，称子集E中的节点为活动节点或提供节点。

2. 数据表示

  在CoolStrearning中，节点的伙伴及伙伴之间数据的传输方向并不固定，伙伴之间根据各自缓存的数据情况进行数据交换，所以节点和伙伴需要相互知道所缓存的数据的内容。在CoolStreaming中，视频数据被分割成相同大小的块，用一个缓存映射 (Buffer Map, BM) 来表示节点中是否拥有某个数据块。节点和伙伴通过不断交换BM来了解相互间的缓存情况。在CoolStreaming的实现中，每个数据块代表一秒的数据，用一个滑动窗口 (Sliding window) 来代表BM，大小为120个片断，BM中120比特来记录， 每比特位代表一个数据块，比特值为1表示有这个片断，0表示没有。由于不同节点的滑动窗口代表的并不是完全一样的数据，CoolStreaming用2字节表示滑动窗E1中第一个数据块的序列号。

. 数据调度

  调度的目的就是如何从伙伴节点获取数据块。在一个静态、同构的环境中，由于各节点的带宽基本相同，可以随机地从各伙伴节点获取数据块；然而在一个动态、异构的网络中，需要更智能的调度算法。调度的约束有两个。   （1）每个数据块必须在播放的最大延迟之前获取，错过最大延迟的数据块应尽可能少。   （2）每个伙伴的带宽情况不同。如果某个数据块的提供者越少，就越难满足最大延迟的要求，因此在CoolStreaming中，采用最少块优先的算法。

4. 错误恢复与伙伴节点优化

  在CoolStreaming系统中，节点同样会在任意时刻离开或者中断。不管什么情况，定时的BM的交换和CoolStreaming系统中部署了TFRC (TCP Friendly Rate Control) 协议都可以发现离开的节点，除了这些机制以外，CoolStreaming内建了一些机制来增强系统的容错性。   节点正常离开的情况下会产生一个离开的消息，如果是节点异常中断，它的伙伴节点会检测到它的中断，伙伴将发出该节点离开的消息。节点离开的消息的传递方式和节点加入时的消息一样。中断节点离开的消息会被不同的伙伴重复发出，节点只有在第一次收到消息时进行转发，所有收到消息的节点会更新它的mCache。   CoolStreaming的伙伴节点优化策略，新节点从服务器上获得初始伙伴节点，并从中选出活动节点，而这些节点不一定是的“最佳”活动节点，就算是“最佳”的活动节点，随着系统节点的变化、时间的变化，节点的伙伴节点的数量和连接带宽会发生变化，因此，每个节点都需要定期更新它的活动节点，即删除一些连接速度慢的活动节点，从各用节点中选择一些连接速度快的节点成为新活动节点。在CoolStreaming中，每个节点会为它的活动节点

计算一个分数

，其中

表示单位时间内点

从节占

平均获取的片段数。因为每个节点既是提供者，也是接收者，所以考虑了两个方向的分数。在到更好的活动节点后，原有活动节点中分数最低的节点将从伙列表里删除。