UIUC《云计算概论》课程学习笔记(二) —— 流言方式、成员关系与网格

UIUC《云计算概论》课程学习笔记(二) —— 流言方式、成员关系与网格

一、流言方式(Gossip)

1.多播(Multicast)

组播是将某些节点划分为一个组,然后信息发送者将信息发给组内的每一个节点。

2.容错与扩展性(Fault-Tolerance And ScalaBility)

一般而言,进行通讯时要考虑如下因素:

  • 节点可能会出现意外
  • 数据包有可能丢失
  • 1000个节点

 

 

3.集中统一(Centralized)

想要实现多播的话,最简单的形式是一种集中的方法。消息发送者有一个收件人列表,然后发送者对列表中的每一个接收者都发送一份消息。它的容缺缺点是,如果在循环发送途中,发送者出错了,那么剩下的一半接收者就不可能收到消息了。此外,该方法的延时很高,因为只有一个发送者在不停发送,所以会导致接收者存在延时,这在接收者名单很长的时候表现尤为明显。

 

4.基于树的形式(Tree-Based)

为了解决上面的问题,人们提出了基于树的多播协议。协议在节点集内生成一棵树,这样就把任意节点之间的消息延迟给减小到了logN级别。可以看到,正常情况下,组内每个成员的开销都是固定的。但是这里有个问题是树的开发和维护,假如某个节点发生负载故障或者丢失了组播信息,会出现一些问题:如果叶子节点出错,那么它是唯一受影响的节点;如果是非叶子节点出错,那么它的子孙节点都将无法收到任何消息。针对这个问题,我们又引入了一些容错机制。

 

5.基于树的组播协议(Tree-Based Multicast Protocols)

  • 根据划分的组构建一棵简单的树
  • 使用生成树来进行多播
  • 同时使用ACKs(acknowledgements)和NAKs(negative acknowledgements)来进行错误修复
  • SRM(Scalable Reliable Multicast)
    – 使用NAKs
    – 引入随机延迟和指数式后推来避免NAK风暴
  • RMTP(Reliable Multicast Transport Protocol)
    – 使用ACKs
    – ACKs只发送给特定的接收者,如果接收者没收到ACKs则会重发信息
  • 这些协议仍然会有O(N)的时间代价

 

二、成员关系(Membership)

1.什么是成员关系(What is a Group Membership)

一个挑战:

  • 你被委托负责数据中心,然后你的经理告诉你,“不!我们的数据中心没有出过任何错误!”
  • 你会相信他吗?
  • 你的首要职责是什么?
  • 建立一个错误检测者
  • 如果你不这么做的话,可能会出现什么问题?

出错很正常(Failures Are The Norm):

  • 平均来说,一台机器(系统、存储、主板、网络等)的出错率是每十年一次
  • 当你的数据中心有120台服务器的时候,数据中心的平均出错间隔MTTF(mean time to failure)是一个月
  • 当你有12000台服务器的时候,MTTF是7.2小时!

构造一个错误检测器(To Build A Failure Detector):

你有几个选择:

  1. 雇佣1000个人,每一个人管理一台机器,并在出错的时候报告你
  2. 写一个错误检测程序(分布式的)来自动检测错误并且向工作站报告

那么该用哪一个呢?当然是2了。

目标设定:

  • 处理基于“组”的系统
    – 云/数据中心
    – 复制服务器
    – 分布式数据库
  • 意外停止、出错停止等处理错误的方法

成员关系服务:

一个组内的成员都拥有一个名单,名单保留了大部分或者全部的正常成员列表。该成员列表可以通过各种应用程序访问,比如基于流言的、基于覆盖的、基于分布式哈希表的等。可以看到,这里面重要的一环是成员表,所以,我们接下来要做的是构建成员协议,来维护成员表。

其中最大的挑战之一是,成员协议多是通过不可靠媒介进行通信的,其中可能会发生延迟和丢包等;此外,成员列表的语义质量(the quality of the semantics of the list)可能有不同的风格——该列表可能是一个始终保持一致的完整列表,组中所有成员都依赖于此,这称为强一致的成员关系。虚拟同步(virtual synchrony)这个众所周知的分布式计算范例即依赖于此。还有一些算法例如流言,也依赖于几乎完整的成员列表。此外还有其他算法,如SCAMP,T-MAN和Cyclon等,是依靠部分随机列表的。这里我们关注的重点是那些“几乎完整的列表”,因为它们是弱一致的成员关系,但是它们足够接近完整列表本身。

稍后你会注意到,我们在成员关系中会加入两个子协议,一个是检测故障的机制,一个是传播信息的机制。

 

假设我们有两个进程,pi和pj,它们是通过不可靠的通信媒介进行通信的。我们只处理崩溃停止错误,当进程pj崩溃的时候,一些进程会很快发现这个错误,这就是成员协议的故障检测组件的目标。多个进程可能会发现这个错误,但是我们要确保的是,至少有一个非故障的进程能发现这个错误,然后通过组播组件将这个信息传递给其他的进程。

 

接下来,我们讨论如何设计具有成员协议的故障检测器组件和传播组件。

 

2.错误检测器(Failure Detectors)

当节点pj出现了错误的时候:

  • 我们没有什么可以对它做的
  • 这种状况很常见
  • 最好将其看作一个常规情况而不是一个意外来进行处理
  • 出现频率通常随着数据中心的尺寸而线性增长

分布式错误检测器之理想的属性:

  • 完备性=每个错误都被检测到    (保障)
  • 准确性=没有任何误判        (局部/概率保障)
  • 速度
    – 首先发现错误的所需时间
  • 扩展性                 (没有瓶颈/单独的错误节点)
    – 平等地负载于每个成员上
    – 网络信息负载

这里要注意的是,完备性和准确性不可兼得,必须有所取舍。

 

集中式心跳机制(Centralized Heartbeating):

  • 该机制下,所有节点都周期性地向一个节点发送心跳信息
  • 如果特定时间间隔后没有接收到某个节点i的信息,则认为该节点i出错了
  • 该机制下,存在一个热点(Hotspot),没有很好地做到负载均衡

 

环形心跳机制(Ring Heartbeating):

环形心跳机制,顾名思义,所有的节点连接成一个环,然后向其邻居发送消息。但是该机制存在一个缺陷:在同时出现多个错误的时候,环会被切割开来,这样会造成正常节点之间也无法正常通信。

 

所有对所有心跳机制(All-To-All Heartbeating):
在这种机制下,实现了通信的负载均衡,每个节点具有同等的通信任务量。可是如果节点中存在某个特别慢的节点,它接收其他节点信息的延时比较长,那么有可能最后它将所有其他节点都标记为失败,这种情况下准确度变得比较低,稍后我们会讨论如何改善这一问题。

 

3.流言式心跳机制(Gossip-Style Heartbeating)

在流言式心跳机制中

  • 所有节点周期性地向它们的成员名单发送心跳信息
  • 接收到心跳信息的节点会更新其成员名单
    – 如果在阈值​\( T_{fail} \)​时间内没有接收到某一成员的心跳,那么就认为该成员出错
    – 如果在阈值​\( T_{cleanup} \)​时间内没有接收到心跳信息,那么就会将该成员从成员名单中删除

 

 

多级流言机制:

  • 网络拓扑结构是分级的
  • 如果采取全局随机流言机制,会导致核心路由的负载为O(N)
  • 固定:选取流言机制的目标子网络i,其中包含ni个节点,每个节点的概率是1/ni
    – 在固定机制下,路由负载将变为1
    – 传播时间将变为O(logN)
    – 原因是,此时整个网络依据流言子网被划为多层网络,不同层级之间只通过少数“共有节点”进行传播

 

4.错误检测器的性能(Which Is The Best Failure Detector)

我们可以从如下几个方面来评估一个错误检测器的优劣:

  • 完备性
  • 精确性。这里引入“时间T内出错的概率”为PM(T)。
  • 速度
    – 第一次检测到错误的时间
  • 扩展性
    – 节点负载平衡
    – 网络信息负载

在all-to-all心跳机制下,时间代价的计算如下:

在最佳的情况下,

最远的一对节点之间只需要经过logN次传递就能接收到对方的消息,此时,超时时间阈值​\( T=logN*tg \)​,其中tg是一次信息传递所需的时间。每个节点在每个流言周期内的负载是​\( L=N/tg=NlogN/T \)​。

 

但是在实际情况下,信息的传递具有一定的丢失率(记作​\( p_{ml} \)​),我们把最坏情况下的负载记作​\( L^* \)​,那么有

\[ L^*=\frac{log(PM(T))}{log(p_{ml})} \frac{1}{T} \]

我们该如何优化呢?

  • 首先我们注意到,负载L与节点规模N无关
  • all-to-all模式与流言模式:子集优化
    – L=O(N/T)
    – 尝试在所有节点同时发现错误
    – 没有将错误发现与信息传播给区分开来

5.SWIM错误检测协议(SWIM Failure Detector Protocol)

Scalable Weekly consistent Infection style Membership protocol(SWIM)是一种错误检测协议。

这里以进程pi向进程pj进行错误检测的过程为例来看看该协议是怎么工作的:

  • 最开始pi直接向pj发送ping消息,pj收到该消息并返回一个ACK
  • 但是ACK在返回的过程中丢失了,因此pi向pj的“直接确认”方法失败
  • pi会尝试再ping一次pj进行检测,不同的是,这次它会通过“间接确认”的方法,先ping另一个进程pk,然后节点pk再ping进程pj,如果pk收到pj返回的ACK,那么pk会返回ACK给pi表示pj没有出错
  • 如果通过pk进行间接确认的过程中也出现了问题,那么pi会通过成员名单内的其他进程来间接确认

 

 

SWIM错误检测协议的参数主要有如下几种:

  • 首次发现时间:
    – 期望周期为\( \frac{e}{e-1} \)
    – 是常数,与分组大小无关
  • 处理负载:
    – 常数每周期
    – 对于15%的丢失率的情况下,实际负载小于最佳负载的8倍
  • 误报率
    – 可以通过调节K来改变
    – 其改变是指数式的
  • 完备性
    – 取决于时间边界
    – 在O(logN)周期内

 

6.传播与怀疑(Dissemination and Suspicion)

我们有如下几种传播方式可以选择:

  • 多播(硬件、IP)
    – 不可靠的
    – 多路同时多播
  • 点对点(TCP/UDP)
    – 代价很高
  • 零额外信息:在错误检测信息上捎带其他信息
    – 感染模式的传播

SWIM错误检测协议:

 

感染模式的传播:

  • 疫情式的传播
    – 在​\( \lambda log(N) \)​协议周期后,​\( N^{-(2\lambda-2)} \)​进程将不再更新
  • 维护一张最近加入/移除进程的缓存表
    – 用这个缓存的信息进行捎带
    – 更偏向于最近的更新
  • 缓存信息在一段时间后将被垃圾回收
    – 在​\( \lambda logN \)​协议周期后;这个定义是弱约束的。

 

怀疑机制:

  • 错误检测依赖于如下现象:
    – 扰动过程
    – 丢包,例如拥塞
  • 间接地ping也许并不能解决这个问题
    – 例如,相关信息是在被ping主机附近丢失的
  • 关键:在一个进程被标记为出错之前就开始怀疑它

 

怀疑机制:

  • 区分对一个进程的不同怀疑
    – 每个进程的化身号
    – pi的化身号只能被pi更新
    – 和DSDV有些相似
  • 更高的化身号能够覆盖低的化身号
  • 对于一个化身号,怀疑其出错的信息的优先级会高于认为其正常的信息的优先级
  • 对一个化身号标记为失败的信息,会覆盖其他任何信息

总结:

  • 在数据中心中,出错是常态,并不是意外
  • 每一个分布式系统都会使用错误检测器
  • 很多分布式系统使用了成员关系服务
  • 使用环形错误检测的有
    – IBM SP2和很多其他相似的集群/机器
  • 使用流言式的错误检测的有
    – 亚马逊Amazon EC2/S3

 

三、网格(Grids)

1.网格应用(Grid Applications)

网格的应用有很多,这里举一个例子:科罗拉多州立大学开发的快速大气模拟系统(Rapid Atmospheric Modeling System, RAMS)

  • 1998年9月的时候,代号乔治的飓风袭击了美国
    – RAMS建立了这场飓风的模型并进行模拟,最终结果与实际记录吻合良好
    – 使用了5km的空间而不是通常的10km空间进行计算
    – 在256个以上的处理器上运算
  • 计算密集型计算(或者高性能计算)
  • 在无法使用超级计算机的情况下,有没有办法运行这样一个程序呢?

 

在某些机构,对于特定任务可能具有专门的集群;但是也有很多地方,其计算资源平时是分配给员工们分别单独使用的,但是员工下班后这些分散的计算资源便闲置出来了,这种情况下,我们是否有办法调用它们?这种情况下,如果任务可以分解成多个高度并行化的子任务的话,那么可以将这些子任务分发给不同的计算资源,当计算资源取得运算结果后,再把结果返回给调度机器。

 

 

在这种情况下,网格通常使用两级调度基础架构,每个站点都运行一个站内协议,然后不同站点之间有一个协议。有时候,站内和站间协议可以是一种通用的协议。

之后协议会进行任务的分发,决定哪个任务工作在哪个机器上面。计算资源空闲的时候,会运行协议的守护进程,去访问协议的中央服务器,寻求任务,此时协议将会分发一个任务给该计算资源。如果任务完成过程中,计算资源被本地用户使用,此时意味着计算资源不是闲置的了。那么它会停止手头得到的子任务,要么直接杀死子任务的进程,要么将中间结果整理之后返回中央服务器,以便后续的计算资源接手其任务继续运算。但是通常而言,协议的策略都是直接杀死子任务,不再返回中间结果了,因为这样的实现方法要简单一些。

 

Tags:


Leave a Reply

Your email address will not be published.

*
*
*

Insert math as
Block
Inline
Additional settings
Formula color
Text color
#333333
Type math using LaTeX
Preview
\({}\)
Nothing to preview
Insert