一種欺負(fù)算法的改進(jìn)與實(shí)現(xiàn)

鄧定勝

（四川民族學(xué)院 計(jì)算機(jī)科學(xué)系，四川 康定 626001）

一種欺負(fù)算法的改進(jìn)與實(shí)現(xiàn)

鄧定勝

（四川民族學(xué)院 計(jì)算機(jī)科學(xué)系，四川 康定 626001）

改進(jìn)并實(shí)現(xiàn)了欺負(fù)算法，利用二次連接檢測的方法，構(gòu)架了一個(gè)用于欺負(fù)算法的故障檢測器.并針對在新進(jìn)程啟動(dòng)時(shí)，協(xié)調(diào)者可能重新選舉的問題，提出了設(shè)置穩(wěn)定時(shí)間的方法.

欺負(fù)算法；二次連接檢測；分布式系統(tǒng)；選舉算法

1 前言

空中交通管理系統(tǒng)需要實(shí)時(shí)的采集處理和保存大量的數(shù)據(jù)，如地圖信息、雷達(dá)信息、飛行情報(bào)等.這就要求空中交通管理系統(tǒng)具有強(qiáng)大的處理能力、并具有高可靠性；為了滿足性能需求，空中交通管理系統(tǒng)選擇分布式系統(tǒng)來作為其解決方案.

在多數(shù)分布式算法中，都需要一個(gè)進(jìn)程來充當(dāng)協(xié)調(diào)者，通常來說，選擇哪一個(gè)進(jìn)程來作為協(xié)調(diào)者并不重要，重要的是需要由一個(gè)唯一的進(jìn)程來充當(dāng)[1].欺負(fù)算法是由Garcia-Molina提出的，其基本思想是：“當(dāng)任何一個(gè)進(jìn)程發(fā)現(xiàn)協(xié)調(diào)者不再響應(yīng)時(shí)就發(fā)起一次選舉”，目前已有許多關(guān)于欺負(fù)算法討論的文章[2]，據(jù)此，本文改進(jìn)并實(shí)現(xiàn)了欺負(fù)算法.

2 實(shí)現(xiàn)

其實(shí)現(xiàn)的功能有：

2.1 保證在leader進(jìn)程崩潰、leader進(jìn)程所在的節(jié)點(diǎn)崩潰和leader網(wǎng)斷時(shí)可以選舉出新的leader.

2.2 改進(jìn)欺負(fù)算法，使得只要leader不出現(xiàn)故障，就不重新選舉新的leader.

2.2.1 各參與進(jìn)程的連接方式

各個(gè)參與進(jìn)程的通信方式為TCP，連接方式為兩兩相連，同時(shí)，為了簡化為各參與進(jìn)程創(chuàng)建TCP連接的過程及減少TCP鏈路的數(shù)量，應(yīng)該使進(jìn)程間的連接有方向，因此在本文中使用小IP連接大IP的方法.當(dāng)連接完成后，各參與進(jìn)程間的關(guān)系如圖所示：

2.2.2 失效檢測器

這里所講的失效檢測器可以處理兩種故障.

2.2.2.1 leader進(jìn)程崩潰

由于各參與節(jié)點(diǎn)間以TCP來連接，所以當(dāng)參與進(jìn)程崩潰或結(jié)束時(shí)，與此失效的進(jìn)程相連接的所有進(jìn)程都會(huì)收到由失效進(jìn)程節(jié)點(diǎn)發(fā)出的FIN，收到FIN的進(jìn)程的rev函數(shù)會(huì)返回0，所以利用TCP的這個(gè)特性，就可以檢測出此類故障并處理.

2.2.2.2 leader進(jìn)程所在的主機(jī)崩潰和leader斷網(wǎng)

當(dāng)leader所在的主機(jī)崩潰或leader斷網(wǎng)時(shí)，由于進(jìn)程來不及向其它節(jié)點(diǎn)發(fā)送FIN，所以其它所有的非leader進(jìn)程都將不會(huì)檢測到leader是否已經(jīng)失效.雖然TCP的SO_KEEPALIVE套接口選項(xiàng)可以在一定的時(shí)間之后發(fā)現(xiàn)leader已經(jīng)崩潰，但此套接口選項(xiàng)的超時(shí)間過長，且不可更改，所以這種方法不可采用.

為了能在較短的時(shí)間內(nèi)獲知leader是否已經(jīng)失效，可以使用UDP(心跳)的方法，然而使用這種方法有個(gè)缺點(diǎn)：可能會(huì)出現(xiàn)leader沒有失效，而錯(cuò)誤的認(rèn)為leader已經(jīng)失效的情況.據(jù)此，本文采用一種二次連接的方法來檢測leader所在的主機(jī)崩潰和斷網(wǎng)的故障.詳細(xì)方法如下[3]：

2.2.2.2.1為了進(jìn)行連接測試，每個(gè)進(jìn)程都創(chuàng)建兩個(gè)套接口A、B，每一個(gè)進(jìn)程都在A套接口上監(jiān)聽.

2.2.2.2.2連接檢查時(shí)，用接口B向所有由系統(tǒng)中其它進(jìn)程創(chuàng)建的套接口A發(fā)起非阻塞連接connect函數(shù)，若非阻塞函數(shù)connect函數(shù)返回值為0，就表示被連接節(jié)點(diǎn)沒有發(fā)生故障；若非阻塞函數(shù)connect函數(shù)返回值為-1(而windows則返回SOCKET_ERROR)，則取其錯(cuò)誤代碼err，如果err=EINPROGRESS，則表示TCP的三路握手已經(jīng)發(fā)起，連接正在進(jìn)行中，但不能馬上完成，需要進(jìn)行第二次連接檢查；若是其它錯(cuò)誤，就表示連接失敗，被連接進(jìn)程可能已經(jīng)出現(xiàn)故障了，不需要進(jìn)行第二次連接檢查了；在上面的第一次連接完成后，若需要進(jìn)行第二次連接檢查，就先等待數(shù)秒，再進(jìn)行第二次連接檢查，第二次連接檢查使用select函數(shù)，其方法是：

第一步：將連接方的文件描述符加入到select函數(shù)的讀集和寫集中，并設(shè)置select的超時(shí)間為一個(gè)很小的值.

第二步：若select函數(shù)的返回值為0，就表示連接錯(cuò)誤；若select函數(shù)的返回值為非0，則檢測讀、寫集的狀態(tài)，若讀集或?qū)懠杏幸粋€(gè)被觸發(fā)，就再調(diào)用getsockopt函數(shù)獲取其SO_ERROR選項(xiàng)的狀態(tài)，若getsockopt函數(shù)值返回0，就表示連接成功.若getsockopt函數(shù)值返回-1，則表示連接失敗，并將自己的第四個(gè)參數(shù)設(shè)置為發(fā)生錯(cuò)誤的原因(用代碼的編寫來表示).

2.2.2.2.3無論連接是否成功，都需要將連接套接口B關(guān)閉，并重新創(chuàng)建此套接口，以便進(jìn)行下一次連接.

2.2.2.2.4連接測試每隔一定的時(shí)間就要執(zhí)行一次，所以需要使用一個(gè)定時(shí)器，用來定時(shí)調(diào)用做連接測試的函數(shù)，當(dāng)連續(xù)失敗一定的次數(shù)以后，就可以說本進(jìn)程與被連接的進(jìn)程已經(jīng)斷開了.

只要leader不出現(xiàn)故障，就不重新選擇新的leader，在原有的欺負(fù)算法中，只要有新的編號更大IP的進(jìn)程啟動(dòng)時(shí)，leader將被切換為新啟動(dòng)的編號最大的進(jìn)程，正如上面所講到的，重要的不是選擇那一個(gè)進(jìn)程作為leader，而是選出唯一的一個(gè)進(jìn)程作為leader.所以在這種情形下，leader的改變是不必要的.不僅如此，在極端的情形下，還有可能出現(xiàn)leader震蕩.考慮如下情形：假設(shè)有5個(gè)進(jìn)程1、2、3、4、5，若進(jìn)程1先啟動(dòng)，而其它的進(jìn)程都沒有啟動(dòng)，則進(jìn)程1會(huì)被選為leader，當(dāng)進(jìn)程1工作一段時(shí)間后，進(jìn)程2又啟動(dòng)了，那么此時(shí)進(jìn)程2將被選舉為leader，以此類推，若進(jìn)程1、2、3、4、5在較短的時(shí)間內(nèi)依次啟動(dòng)，而中間的時(shí)間差又足夠挑選新的leader的時(shí)候，將會(huì)發(fā)生4次leader的變化.為了防止這種情形的出現(xiàn)，本文采用如下方法：每一個(gè)進(jìn)程在啟動(dòng)時(shí)都設(shè)置一個(gè)穩(wěn)定的時(shí)間，在這個(gè)穩(wěn)定的時(shí)間內(nèi)，此進(jìn)程除用于新節(jié)點(diǎn)發(fā)現(xiàn)的廣播外，任何事情都不做，若當(dāng)前l(fā)eader發(fā)現(xiàn)有新進(jìn)程啟動(dòng)時(shí)，leader就給此新啟動(dòng)的進(jìn)程發(fā)送一個(gè)通知消息，告訴新進(jìn)程當(dāng)前l(fā)eader的編號；若新啟動(dòng)的進(jìn)程在穩(wěn)定的時(shí)間內(nèi)沒有收到此通知信息，它就認(rèn)為系統(tǒng)中沒有l(wèi)eader存在，于是便發(fā)起選舉.

3 實(shí)驗(yàn)

實(shí)驗(yàn)采用5臺(tái)PC機(jī)，在每臺(tái)PC機(jī)上都運(yùn)行一個(gè)相同的程序，并設(shè)置連接檢查的時(shí)間為3秒，當(dāng)連續(xù)3次測試連接都錯(cuò)誤時(shí)，就認(rèn)為被測試的進(jìn)程崩潰，將每臺(tái)PC機(jī)的IP分別設(shè)置為：210.41.113.1—210.41.113.5.先啟動(dòng)進(jìn)程1(其中IP: 210.41.113.1),等待進(jìn)程1成為leader后，再以任意順序啟動(dòng)其它的進(jìn)程，在所有進(jìn)程都穩(wěn)定后，leader沒有發(fā)送改變.此時(shí)結(jié)束進(jìn)程1，進(jìn)程5(IP: 210.41.113.5)就被推選為leader.最后將進(jìn)程5所在的PC機(jī)的電源斷開，以此來模擬主機(jī)崩潰的情況，在經(jīng)過大約9秒后，當(dāng)然進(jìn)程4被選為了leader.

4 總結(jié)

文章改進(jìn)并實(shí)現(xiàn)了欺負(fù)算法，具有良好的容錯(cuò)性，成功的解決了欺負(fù)算法在選舉過程中，產(chǎn)生大量的消息的問題；同時(shí)通過二次連接的方法，實(shí)現(xiàn)了一個(gè)故障檢測器，可以有效的檢測到進(jìn)程崩潰和主機(jī)崩潰的故障.

〔1〕特南鮑姆.分布式系統(tǒng)原理與泛型[M].北京：清華大學(xué)出版社,2004.

〔2〕吳寧,馬文忠.基于欺負(fù)算的優(yōu)化算法[J].計(jì)算機(jī)工程,2008,34(19).

〔3〕Stevens WR.Unix網(wǎng)絡(luò)編程[M].北京：清華大學(xué)出版社,2006.

TP311.13

A

1673-260X（2014）02-0017-02