论文部分内容阅读
【摘 要】组通信是构造高可靠分布式系统的重要基石。以组通信技术为基础，提出了基于Internet的多媒体考试系统平台中集群管理器的结构和设计，详细描述了实现中所采用的可靠全序组播算法、组成员管理、流量控制算法、负载平衡及失效转发算法。通过主动状态复制，该集群系统提供了高可靠和高扩展性，并且具有较高的性能，它已经在多个烟草公司和高校得到成功使用。
【关键词】集群；组通信；可靠组播；流量控制；负载平衡
引言
当前，企业级的计算系统应用日益广泛，而高可用性、高容错性和高可靠性是这些企业级的关键性应用所必须具有的特性，使用集中式的服务架构将无法满足这些需求。除使用专用硬件冗余设备（如磁盘阵列、双机热备份等）外，构建一个集群环境，将多个服务节点有机组织起来，对数据和服务进行复制，统一对外提供服务，是一种更加灵活、扩展性更强、成本较低的方法。但是集群系统的开发是一项复杂的工作，面临一些关键问题的挑战。
本文以我们开发的基于Internet的多媒体考试系统平台作为实例，具体描述了将组通信技术应用于构造服务集群系统的方法，总结了我们在实现中对于关键问题的解决方案。该系统已经被多所高校和政府机构成功使用。
1.系统需求和体系结构
基于Internet的多媒体考试系统平台是一项实用推广产品，它基于Internet，提供从题库系统、成卷系统、考试规划一直到计算机考试、自动阅卷、答卷信息评价的全线服务，自动化程度高，实现了考试的完全无纸化。由于该系统一般应用在基于Internet的大规模环境下，作为关键性的应用，它对于系统的性能提出了以下需求：
高扩展性：由于可以通过Internet进行考试，考生人数不受局域网计算机数的限制，因此要求系统必须能够承受大量考生同时参加多门课程的考试，而不会产生性能瓶颈。
高可靠性：考试信息、试题、考生答案等重要数据不能丢失，系统能够自动检测软它所管理的软硬件故障，局部的失效不影响系统的功能，具有高容错性。
高可用性：当系统出现故障时，应该在限定时间内（秒级）自动恢复，不影响考试的进行。
为了满足以上需求，我们基于组通信技术将系统设计为一个集群结构，其包含多个考试服务器，客户端通过负载平衡技术选择一个服务器进行通信，当连接的服务器失效后，客户端可以重新连接到其他服务器，继续进行相关的操作而考试不受影响，这一过程对于用户（考生）是透明的。显然，为了达到这一目的，考试服务器之间需要进行实时的相互通信以维持状态的一致性。图1显示了系统的体系结构。
每个服务器结点主要由web服务、集群管理器（Cluster Manager，CM）、考试服务器（Exam Server，ES）和数据库服务器四种服务组成，其中CM主要负责使用组通信协议和其它结点的CM进行可靠通信以实现状态复制，ES和数据库服务器进行交互，具体实现应用逻辑如登陆、交卷、查询等。我们以考生登录为例说明系统各组件间的交互，图1显示了一个具有两个结点的集群。首先考生浏览器从一个结点的Web服务器下载ActiveX控件（①），运行之（②），考生输入认证信息后，ActiveX将认证信息发送到结点的CM（③），该CM首先和其它结点的CM通信（④），复制状态，然后将信息发送到ES（⑤），ES和数据库服务器交互（⑥），进行相应处理。
集群管理器CM主要包括以下处理模块：
可靠全序组播：由于一个节点的消息要发送给集群内所有其他节点，为了使节点之间进行高效的消息传输，一个很自然的想法就是采用组播（multicast）方式，实现一对多通信。但是其缺陷是不能保证消息的可靠传递，此外为了保证各节点的状态一致，使各个节点按照相同的顺序接收消息也很重要（即全序，Total order）。可靠全序组播模块就是要保证节点之间使用IP multicast达到消息的可靠、全序传递的目的。
组成员管理：将集群内的服务节点有机组织起来，负责节点的加入、离开和失效的处理，保证所有生存的节点保持相同的组成员视图。
流量控制：如果一个结点由于不能及时处理接收的消息而导致其缓冲区溢出，从而引起大量消息重传。为此采用流量控制机制控制消息的发送速率，以达到流控的目的。
负载平衡和失效转发：解决系统负载平衡和容错的问题。
下面我们就这几个模块的算法进行阐述。
2.可靠全序组播算法
每个结点都各自维护着一个本地消息计数器，作为发送的消息的顺序号，称为结点顺序号。当某个结点要向全组的结点发送消息m时，给m设置结点顺序号，然后将m发送给集群内一个称为sequencer的结点S（sequencer的产生见下一节）。S还维护着一个全局消息计数器，称为全局顺序号。S每收到一个消息，就给消息设置全局顺序号，再将消息放入它的发送队列。一个线程负责将发送队列中的消息依次按照一定速率在网络中组播。
发送结点将消息m发送给S后，以组播形式接收，如果接收到m，则说明m已经可靠到达S，可以继续发送下一个消息；如果在一定时间内未接收到m，则认为m丢失，重新发送m直到S接收成功为止。同时，S记录着每个结点最后发送的消息的结点顺序号，从而避免接收到重复消息。算法1说明了发送结点的发送过程。
算法1 发送结点发送消息
输入：消息m；sequencer节点S
Begin
（1） 设置m的节点顺序号
（2） 向S单播m
（3） 接收组播消息m’
（4） if m’ = m then
（5） end
（6） else if 超时 then
（7） 转到（2）重新执行 （8） end if
End.
所有接收结点对于S组播的消息采取负向应答方式。每个结点都记录着下一个预期接收的消息的全局顺序号Ne。当接收到全局顺序号为Nm的消息时，如果Ne>Nm，则说明此消息是重复消息，将其丢弃；如果Ne=Nm，则将此消息放入接收队列，并且Ne加1；如果Ne 算法2 接收结点接收消息
输入：接收的消息m；m的全局顺序号Nm；sequencer节点S；预期的全局顺序号Ne
Begin
（1） 接收组播消息m
（2） if Ne>Nm then
（3） m是重复消息，丢弃
（4） else if Ne=Nm then
（5） 将m放入到接收队列等待处理
（6） Ne：= Ne+1
（7） else
（8） 向S发送NACK应答，NACK包含Ne
（9） end if
End.
另外为了能够重传丢失的消息，S必须保持一个最近发送的消息日志以便重新发送，但是日志不可能无限大，日志应该保留多少消息是一个问题。我们的设计是：日志是一个存储最近发送消息的缓冲区（约1千个，可以配置），每个发送消息的结点在发送的消息中捎带它预期接收消息的全局顺序号，这样S就可以记录每个结点的接收进度，显然进度中最小全局顺序号以下的消息都已经被所有结点收到，可以从日志中删除了。但是如果某个结点基本不发送消息，则无法得到该结点的接收进度。解决该问题的方法是：当日志使用率达到80%，则S组播Query消息直到所有结点都应答，各结点在应答中说明自己的预期接收消息的全局顺序号。
为了防止慢接收者影响日志空间的回收，规定当结点发现它的预期接收消息的全局顺序号和当前的全局顺序号的差距大于日志大小时，则自动退出集群。
另外为了实现容错，每个节点都保持了和S相同的发送消息的日志，当S失效后可以由其他节点立即接替。
算法3说明了sequencer结点对不同消息的处理。
算法3 sequencer结点的处理过程
输入：接收的消息m；消息日志log；m的全局顺序号Nm；当前最大全局顺序号Ng
Begin
（1） 接收单播消息m
（2） if m是待发送的消息 then
（3） if log∈m then
（4） m是重复消息，丢弃
（5） else
（6） 把m放入发送队列，等待组播发送
（7） end if
（8） else if m是NACK then
（9） 将从Nm到Ng的消息重新组播发送
（10）end if
End.
3.组成员管理算法
3.1结点启动和加入
结点p启动后，首先周期性的组播一个Discover消息，以查找当前集群内的sequencer；如果在一定时间内（10秒）没有收到应答，则将自己设置为sequencer，初始化各种状态，建立集群并准备接受其它结点随后的加入。
如果集群已经存在，则当前的sequencer S接收到Discover消息后，对p进行权限验证，如果合法，则向p发送应答，然后S将当前成员列表信息和应用状态信息（如已登陆考生信息、已交卷考生信息等）发送给p，状态传输完成后，S使用可靠组播向其它所有结点发送p加入的消息。各结点都更新自己的成员列表信息。p正式加入了集群。
由于每时刻只能有一个结点加入，如果这时S在处理其它结点的加入，S向p发送Waiting消息，p等待一段时间后重新再加入。
如果这时恰好S失效（见下文），则集群内的结点向p发送Waiting消息，p等待一段时间后重新再加入。
3.2结点离开
如果结点p要离开集群，则向sequencer S发送Leave消息，S接收到后，使用可靠组播向其它所有结点发送p离开的消息。各结点都更新自己的成员列表信息。然后S向p发送应答，同意其离开，p正式离开集群。
如果这时S恰好失效，则p将等到新的sequencer产生后再重新发送Leave消息。在p正式离开之前，它仍是集群内的成员。
3.3失效处理
为了进行失效检测，除S以外的其它结点在不发送消息时周期性的向S发送Alive消息，而S也在空闲时周期性组播Alive消息。如果当前只有一个成员结点（即sequencer），则停止组播Alive消息。
如果在一定时间内，S没有收到结点p发来的任何消息，则认为p已经失效，使用可靠组播向其它所有结点发送p失效的消息。各结点都更新自己的成员列表信息，从而将失效结点排除在集群之外。如果p并没有真正失效（可能由于负载过重、网络阻塞等原因而被怀疑失效），当p向S发送消息，S以Dead消息应答，则p就知道自己已经脱离集群，需要重新加入。
如果在一定时间内（10秒），没有收到从S发送的任何消息，则认为S失效，需要选举一个新的sequencer。由于各结点的成员列表都是按照结点加入顺序排列的，因此它们必然保持一致。于是各结点都将排序仅次于S的结点q设为新的sequencer（q结点也将自己设置为sequencer）。 一个复杂的问题是当S失效时，之前由S组播的消息可能只有部分节点收到，而其他节点还未收到（需要进行重传），这时节点的状态并不一致。那么新的sequencer q该从哪个消息开始进行组播呢？
我们的设计分为两个阶段，在第一阶段，q在一定时间内周期组播一个Checkout消息，声明自己的地址、端口等信息，其他节点收到后，向q发送SequenceNumber消息，说明自己预期的全局顺序号，这样q就收集到了目前所有存活的成员信息以及它们各自的全局顺序号。
在第二阶段，q首先检查自己的预期全局顺序号是否小于第一阶段收集的最大预期全局顺序号，如果是这样，则说明自己缺少消息，于是向具有最大预期全局顺序号的结点发出请求，使其重传自己缺少的消息；然后q检查其他节点是否也缺少消息，如果是这样，就向它们进行消息重传。至此，所有结点达到了相同的状态。最后q在一定时间内周期组播一个Regroup_result消息，其包含所有成员列表信息、新的sequencer（q本身）和新的初始全局顺序号。各结点收到后，更新自己的各项信息，进入正常操作状态，并向q发送应答。当q收到所有成员的应答或者超时后，也进入正常操作状态。对于没有应答的节点，按照其失效进行处理。如果在这期间q崩溃了，那么其他结点由于监听不到q发送的消息而重新进行下一轮的选举。
4、结束语
本文总结了我们在开发基于Internet的多媒体考试系统平台中，将组通信应用于构造服务集群所采用的关键技术与算法。详细说明了我们采用的可靠全序组播算法、组成员管理、流量控制算法。实际部署的具有3个结点的系统在100M/S的网络带宽和1000个考生的环境下，可靠组播的消息速率达到50M/S，具有较高的性能。该系统已经在多个烟草公司和高校得到成功使用，得到用户的好评。
参考文献：
[1]Gregory Chockler， Idit Keidar， and Roman Vitenberg. Group communication specifications： A comprehensive study[J]. ACM Computing Surveys， 33（4）：1-43， December 2001.
[2]K.P. Birman. A Review of Experiences with Reliable Multicast[J]. Software-Practice and Experience 29（9）， 741- 774 ， 1999.
[3]KAASHOEK， M. F. AND TANENBAUM， A. S. An evaluation of the Amoeba group communication system[C]. In 16th International Conference on Distributed Computing Systems （ICDCS） （May）， pp. 436-447， 1996.
【关键词】集群；组通信；可靠组播；流量控制；负载平衡
引言
当前，企业级的计算系统应用日益广泛，而高可用性、高容错性和高可靠性是这些企业级的关键性应用所必须具有的特性，使用集中式的服务架构将无法满足这些需求。除使用专用硬件冗余设备（如磁盘阵列、双机热备份等）外，构建一个集群环境，将多个服务节点有机组织起来，对数据和服务进行复制，统一对外提供服务，是一种更加灵活、扩展性更强、成本较低的方法。但是集群系统的开发是一项复杂的工作，面临一些关键问题的挑战。
本文以我们开发的基于Internet的多媒体考试系统平台作为实例，具体描述了将组通信技术应用于构造服务集群系统的方法，总结了我们在实现中对于关键问题的解决方案。该系统已经被多所高校和政府机构成功使用。
1.系统需求和体系结构
基于Internet的多媒体考试系统平台是一项实用推广产品，它基于Internet，提供从题库系统、成卷系统、考试规划一直到计算机考试、自动阅卷、答卷信息评价的全线服务，自动化程度高，实现了考试的完全无纸化。由于该系统一般应用在基于Internet的大规模环境下，作为关键性的应用，它对于系统的性能提出了以下需求：
高扩展性：由于可以通过Internet进行考试，考生人数不受局域网计算机数的限制，因此要求系统必须能够承受大量考生同时参加多门课程的考试，而不会产生性能瓶颈。
高可靠性：考试信息、试题、考生答案等重要数据不能丢失，系统能够自动检测软它所管理的软硬件故障，局部的失效不影响系统的功能，具有高容错性。
高可用性：当系统出现故障时，应该在限定时间内（秒级）自动恢复，不影响考试的进行。
为了满足以上需求，我们基于组通信技术将系统设计为一个集群结构，其包含多个考试服务器，客户端通过负载平衡技术选择一个服务器进行通信，当连接的服务器失效后，客户端可以重新连接到其他服务器，继续进行相关的操作而考试不受影响，这一过程对于用户（考生）是透明的。显然，为了达到这一目的，考试服务器之间需要进行实时的相互通信以维持状态的一致性。图1显示了系统的体系结构。
每个服务器结点主要由web服务、集群管理器（Cluster Manager，CM）、考试服务器（Exam Server，ES）和数据库服务器四种服务组成，其中CM主要负责使用组通信协议和其它结点的CM进行可靠通信以实现状态复制，ES和数据库服务器进行交互，具体实现应用逻辑如登陆、交卷、查询等。我们以考生登录为例说明系统各组件间的交互，图1显示了一个具有两个结点的集群。首先考生浏览器从一个结点的Web服务器下载ActiveX控件（①），运行之（②），考生输入认证信息后，ActiveX将认证信息发送到结点的CM（③），该CM首先和其它结点的CM通信（④），复制状态，然后将信息发送到ES（⑤），ES和数据库服务器交互（⑥），进行相应处理。
集群管理器CM主要包括以下处理模块：
可靠全序组播：由于一个节点的消息要发送给集群内所有其他节点，为了使节点之间进行高效的消息传输，一个很自然的想法就是采用组播（multicast）方式，实现一对多通信。但是其缺陷是不能保证消息的可靠传递，此外为了保证各节点的状态一致，使各个节点按照相同的顺序接收消息也很重要（即全序，Total order）。可靠全序组播模块就是要保证节点之间使用IP multicast达到消息的可靠、全序传递的目的。
组成员管理：将集群内的服务节点有机组织起来，负责节点的加入、离开和失效的处理，保证所有生存的节点保持相同的组成员视图。
流量控制：如果一个结点由于不能及时处理接收的消息而导致其缓冲区溢出，从而引起大量消息重传。为此采用流量控制机制控制消息的发送速率，以达到流控的目的。
负载平衡和失效转发：解决系统负载平衡和容错的问题。
下面我们就这几个模块的算法进行阐述。
2.可靠全序组播算法
每个结点都各自维护着一个本地消息计数器，作为发送的消息的顺序号，称为结点顺序号。当某个结点要向全组的结点发送消息m时，给m设置结点顺序号，然后将m发送给集群内一个称为sequencer的结点S（sequencer的产生见下一节）。S还维护着一个全局消息计数器，称为全局顺序号。S每收到一个消息，就给消息设置全局顺序号，再将消息放入它的发送队列。一个线程负责将发送队列中的消息依次按照一定速率在网络中组播。
发送结点将消息m发送给S后，以组播形式接收，如果接收到m，则说明m已经可靠到达S，可以继续发送下一个消息；如果在一定时间内未接收到m，则认为m丢失，重新发送m直到S接收成功为止。同时，S记录着每个结点最后发送的消息的结点顺序号，从而避免接收到重复消息。算法1说明了发送结点的发送过程。
算法1 发送结点发送消息
输入：消息m；sequencer节点S
Begin
（1） 设置m的节点顺序号
（2） 向S单播m
（3） 接收组播消息m’
（4） if m’ = m then
（5） end
（6） else if 超时 then
（7） 转到（2）重新执行 （8） end if
End.
所有接收结点对于S组播的消息采取负向应答方式。每个结点都记录着下一个预期接收的消息的全局顺序号Ne。当接收到全局顺序号为Nm的消息时，如果Ne>Nm，则说明此消息是重复消息，将其丢弃；如果Ne=Nm，则将此消息放入接收队列，并且Ne加1；如果Ne
输入：接收的消息m；m的全局顺序号Nm；sequencer节点S；预期的全局顺序号Ne
Begin
（1） 接收组播消息m
（2） if Ne>Nm then
（3） m是重复消息，丢弃
（4） else if Ne=Nm then
（5） 将m放入到接收队列等待处理
（6） Ne：= Ne+1
（7） else
（8） 向S发送NACK应答，NACK包含Ne
（9） end if
End.
另外为了能够重传丢失的消息，S必须保持一个最近发送的消息日志以便重新发送，但是日志不可能无限大，日志应该保留多少消息是一个问题。我们的设计是：日志是一个存储最近发送消息的缓冲区（约1千个，可以配置），每个发送消息的结点在发送的消息中捎带它预期接收消息的全局顺序号，这样S就可以记录每个结点的接收进度，显然进度中最小全局顺序号以下的消息都已经被所有结点收到，可以从日志中删除了。但是如果某个结点基本不发送消息，则无法得到该结点的接收进度。解决该问题的方法是：当日志使用率达到80%，则S组播Query消息直到所有结点都应答，各结点在应答中说明自己的预期接收消息的全局顺序号。
为了防止慢接收者影响日志空间的回收，规定当结点发现它的预期接收消息的全局顺序号和当前的全局顺序号的差距大于日志大小时，则自动退出集群。
另外为了实现容错，每个节点都保持了和S相同的发送消息的日志，当S失效后可以由其他节点立即接替。
算法3说明了sequencer结点对不同消息的处理。
算法3 sequencer结点的处理过程
输入：接收的消息m；消息日志log；m的全局顺序号Nm；当前最大全局顺序号Ng
Begin
（1） 接收单播消息m
（2） if m是待发送的消息 then
（3） if log∈m then
（4） m是重复消息，丢弃
（5） else
（6） 把m放入发送队列，等待组播发送
（7） end if
（8） else if m是NACK then
（9） 将从Nm到Ng的消息重新组播发送
（10）end if
End.
3.组成员管理算法
3.1结点启动和加入
结点p启动后，首先周期性的组播一个Discover消息，以查找当前集群内的sequencer；如果在一定时间内（10秒）没有收到应答，则将自己设置为sequencer，初始化各种状态，建立集群并准备接受其它结点随后的加入。
如果集群已经存在，则当前的sequencer S接收到Discover消息后，对p进行权限验证，如果合法，则向p发送应答，然后S将当前成员列表信息和应用状态信息（如已登陆考生信息、已交卷考生信息等）发送给p，状态传输完成后，S使用可靠组播向其它所有结点发送p加入的消息。各结点都更新自己的成员列表信息。p正式加入了集群。
由于每时刻只能有一个结点加入，如果这时S在处理其它结点的加入，S向p发送Waiting消息，p等待一段时间后重新再加入。
如果这时恰好S失效（见下文），则集群内的结点向p发送Waiting消息，p等待一段时间后重新再加入。
3.2结点离开
如果结点p要离开集群，则向sequencer S发送Leave消息，S接收到后，使用可靠组播向其它所有结点发送p离开的消息。各结点都更新自己的成员列表信息。然后S向p发送应答，同意其离开，p正式离开集群。
如果这时S恰好失效，则p将等到新的sequencer产生后再重新发送Leave消息。在p正式离开之前，它仍是集群内的成员。
3.3失效处理
为了进行失效检测，除S以外的其它结点在不发送消息时周期性的向S发送Alive消息，而S也在空闲时周期性组播Alive消息。如果当前只有一个成员结点（即sequencer），则停止组播Alive消息。
如果在一定时间内，S没有收到结点p发来的任何消息，则认为p已经失效，使用可靠组播向其它所有结点发送p失效的消息。各结点都更新自己的成员列表信息，从而将失效结点排除在集群之外。如果p并没有真正失效（可能由于负载过重、网络阻塞等原因而被怀疑失效），当p向S发送消息，S以Dead消息应答，则p就知道自己已经脱离集群，需要重新加入。
如果在一定时间内（10秒），没有收到从S发送的任何消息，则认为S失效，需要选举一个新的sequencer。由于各结点的成员列表都是按照结点加入顺序排列的，因此它们必然保持一致。于是各结点都将排序仅次于S的结点q设为新的sequencer（q结点也将自己设置为sequencer）。 一个复杂的问题是当S失效时，之前由S组播的消息可能只有部分节点收到，而其他节点还未收到（需要进行重传），这时节点的状态并不一致。那么新的sequencer q该从哪个消息开始进行组播呢？
我们的设计分为两个阶段，在第一阶段，q在一定时间内周期组播一个Checkout消息，声明自己的地址、端口等信息，其他节点收到后，向q发送SequenceNumber消息，说明自己预期的全局顺序号，这样q就收集到了目前所有存活的成员信息以及它们各自的全局顺序号。
在第二阶段，q首先检查自己的预期全局顺序号是否小于第一阶段收集的最大预期全局顺序号，如果是这样，则说明自己缺少消息，于是向具有最大预期全局顺序号的结点发出请求，使其重传自己缺少的消息；然后q检查其他节点是否也缺少消息，如果是这样，就向它们进行消息重传。至此，所有结点达到了相同的状态。最后q在一定时间内周期组播一个Regroup_result消息，其包含所有成员列表信息、新的sequencer（q本身）和新的初始全局顺序号。各结点收到后，更新自己的各项信息，进入正常操作状态，并向q发送应答。当q收到所有成员的应答或者超时后，也进入正常操作状态。对于没有应答的节点，按照其失效进行处理。如果在这期间q崩溃了，那么其他结点由于监听不到q发送的消息而重新进行下一轮的选举。
4、结束语
本文总结了我们在开发基于Internet的多媒体考试系统平台中，将组通信应用于构造服务集群所采用的关键技术与算法。详细说明了我们采用的可靠全序组播算法、组成员管理、流量控制算法。实际部署的具有3个结点的系统在100M/S的网络带宽和1000个考生的环境下，可靠组播的消息速率达到50M/S，具有较高的性能。该系统已经在多个烟草公司和高校得到成功使用，得到用户的好评。
参考文献：
[1]Gregory Chockler， Idit Keidar， and Roman Vitenberg. Group communication specifications： A comprehensive study[J]. ACM Computing Surveys， 33（4）：1-43， December 2001.
[2]K.P. Birman. A Review of Experiences with Reliable Multicast[J]. Software-Practice and Experience 29（9）， 741- 774 ， 1999.
[3]KAASHOEK， M. F. AND TANENBAUM， A. S. An evaluation of the Amoeba group communication system[C]. In 16th International Conference on Distributed Computing Systems （ICDCS） （May）， pp. 436-447， 1996.