鄧定勝

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

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

鄧定勝

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

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

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

1 前言

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

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

2 實現(xiàn)

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

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

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

2.2.1 各參與進程的連接方式

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

2.2.2 失效檢測器

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

2.2.2.1 leader進程崩潰

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

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

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

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

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

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

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

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

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

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

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

3 實驗

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

4 總結(jié)

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

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

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

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

TP311.13

A

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