一种欺负算法的改进与实现

2014-03-29邓定胜

赤峰学院学报·自然科学版 2014年3期

关键词：协调者PC机进程

邓定胜

（四川民族学院计算机科学系，四川康定 626001）

一种欺负算法的改进与实现

邓定胜

（四川民族学院计算机科学系，四川康定 626001）

改进并实现了欺负算法，利用二次连接检测的方法，构架了一个用于欺负算法的故障检测器.并针对在新进程启动时，协调者可能重新选举的问题，提出了设置稳定时间的方法.

欺负算法；二次连接检测；分布式系统；选举算法

1 前言

空中交通管理系统需要实时的采集处理和保存大量的数据，如地图信息、雷达信息、飞行情报等.这就要求空中交通管理系统具有强大的处理能力、并具有高可靠性；为了满足性能需求，空中交通管理系统选择分布式系统来作为其解决方案.

在多数分布式算法中，都需要一个进程来充当协调者，通常来说，选择哪一个进程来作为协调者并不重要，重要的是需要由一个唯一的进程来充当[1].欺负算法是由Garcia-Molina提出的，其基本思想是：“当任何一个进程发现协调者不再响应时就发起一次选举”，目前已有许多关于欺负算法讨论的文章[2]，据此，本文改进并实现了欺负算法.

2 实现

其实现的功能有：

2.1 保证在leader进程崩溃、leader进程所在的节点崩溃和leader网断时可以选举出新的leader.

2.2 改进欺负算法，使得只要leader不出现故障，就不重新选举新的leader.

2.2.1 各参与进程的连接方式

各个参与进程的通信方式为TCP，连接方式为两两相连，同时，为了简化为各参与进程创建TCP连接的过程及减少TCP链路的数量，应该使进程间的连接有方向，因此在本文中使用小IP连接大IP的方法.当连接完成后，各参与进程间的关系如图所示：

2.2.2 失效检测器

这里所讲的失效检测器可以处理两种故障.

2.2.2.1 leader进程崩溃

由于各参与节点间以TCP来连接，所以当参与进程崩溃或结束时，与此失效的进程相连接的所有进程都会收到由失效进程节点发出的FIN，收到FIN的进程的rev函数会返回0，所以利用TCP的这个特性，就可以检测出此类故障并处理.

2.2.2.2 leader进程所在的主机崩溃和leader断网

当leader所在的主机崩溃或leader断网时，由于进程来不及向其它节点发送FIN，所以其它所有的非leader进程都将不会检测到leader是否已经失效.虽然TCP的SO_KEEPALIVE套接口选项可以在一定的时间之后发现leader已经崩溃，但此套接口选项的超时间过长，且不可更改，所以这种方法不可采用.

为了能在较短的时间内获知leader是否已经失效，可以使用UDP(心跳)的方法，然而使用这种方法有个缺点：可能会出现leader没有失效，而错误的认为leader已经失效的情况.据此，本文采用一种二次连接的方法来检测leader所在的主机崩溃和断网的故障.详细方法如下[3]：

2.2.2.2.1为了进行连接测试，每个进程都创建两个套接口A、B，每一个进程都在A套接口上监听.

2.2.2.2.2连接检查时，用接口B向所有由系统中其它进程创建的套接口A发起非阻塞连接connect函数，若非阻塞函数connect函数返回值为0，就表示被连接节点没有发生故障；若非阻塞函数connect函数返回值为-1(而windows则返回SOCKET_ERROR)，则取其错误代码err，如果err=EINPROGRESS，则表示TCP的三路握手已经发起，连接正在进行中，但不能马上完成，需要进行第二次连接检查；若是其它错误，就表示连接失败，被连接进程可能已经出现故障了，不需要进行第二次连接检查了；在上面的第一次连接完成后，若需要进行第二次连接检查，就先等待数秒，再进行第二次连接检查，第二次连接检查使用select函数，其方法是：

第一步：将连接方的文件描述符加入到select函数的读集和写集中，并设置select的超时间为一个很小的值.

第二步：若select函数的返回值为0，就表示连接错误；若select函数的返回值为非0，则检测读、写集的状态，若读集或写集中有一个被触发，就再调用getsockopt函数获取其SO_ERROR选项的状态，若getsockopt函数值返回0，就表示连接成功.若getsockopt函数值返回-1，则表示连接失败，并将自己的第四个参数设置为发生错误的原因(用代码的编写来表示).

2.2.2.2.3无论连接是否成功，都需要将连接套接口B关闭，并重新创建此套接口，以便进行下一次连接.

2.2.2.2.4连接测试每隔一定的时间就要执行一次，所以需要使用一个定时器，用来定时调用做连接测试的函数，当连续失败一定的次数以后，就可以说本进程与被连接的进程已经断开了.

只要leader不出现故障，就不重新选择新的leader，在原有的欺负算法中，只要有新的编号更大IP的进程启动时，leader将被切换为新启动的编号最大的进程，正如上面所讲到的，重要的不是选择那一个进程作为leader，而是选出唯一的一个进程作为leader.所以在这种情形下，leader的改变是不必要的.不仅如此，在极端的情形下，还有可能出现leader震荡.考虑如下情形：假设有5个进程1、2、3、4、5，若进程1先启动，而其它的进程都没有启动，则进程1会被选为leader，当进程1工作一段时间后，进程2又启动了，那么此时进程2将被选举为leader，以此类推，若进程1、2、3、4、5在较短的时间内依次启动，而中间的时间差又足够挑选新的leader的时候，将会发生4次leader的变化.为了防止这种情形的出现，本文采用如下方法：每一个进程在启动时都设置一个稳定的时间，在这个稳定的时间内，此进程除用于新节点发现的广播外，任何事情都不做，若当前leader发现有新进程启动时，leader就给此新启动的进程发送一个通知消息，告诉新进程当前leader的编号；若新启动的进程在稳定的时间内没有收到此通知信息，它就认为系统中没有leader存在，于是便发起选举.

3 实验

实验采用5台PC机，在每台PC机上都运行一个相同的程序，并设置连接检查的时间为3秒，当连续3次测试连接都错误时，就认为被测试的进程崩溃，将每台PC机的IP分别设置为：210.41.113.1—210.41.113.5.先启动进程1(其中IP: 210.41.113.1),等待进程1成为leader后，再以任意顺序启动其它的进程，在所有进程都稳定后，leader没有发送改变.此时结束进程1，进程5(IP: 210.41.113.5)就被推选为leader.最后将进程5所在的PC机的电源断开，以此来模拟主机崩溃的情况，在经过大约9秒后，当然进程4被选为了leader.