一種欺負算法的改進與實現

鄧定勝

（四川民族學院 計算機科學系，四川 康定 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.

4 總結

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

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

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

〔3〕Stevens WR.Unix網絡編程[M].北京：清華大學出版社,2006.

TP311.13

A

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