北京大學(xué)學(xué)士學(xué)位論文 一種支持動態(tài)可配置的高效組通信系統(tǒng)的設(shè)計與實現(xiàn) - 1 - 摘 要 快速有效地搜集 的網(wǎng)頁，使搜索引擎索引更多的網(wǎng)頁，是其提供高質(zhì)量服務(wù)的基礎(chǔ)。采用分布式搜集策略可以很好完成這一任務(wù)。但由于網(wǎng)上信息分布的不規(guī)律性和廣域性。要應(yīng)用可靠的組播通訊（ 術(shù)來實現(xiàn)搜集系統(tǒng)的負(fù)載平衡和動態(tài)調(diào)度性，即運行過程中添加和刪除主控于分布式的 集系統(tǒng)中。 本文基于“天網(wǎng)”搜索引擎系統(tǒng) 構(gòu)建了一個可靠的組播通訊系統(tǒng)平臺。它借鑒了 學(xué)的 統(tǒng)，實現(xiàn)了分布式 集系統(tǒng)的組視圖維護(hù)和可靠的組播通訊。本文論述的系統(tǒng) 結(jié)構(gòu)和方法，將用于“天網(wǎng)” 的開發(fā)，達(dá)到提高系統(tǒng)能力，改善系統(tǒng)的可擴(kuò)展性的目的。 關(guān)鍵詞 可靠的組播 傳送、組視圖、分布式、動態(tài)可配置、搜索引擎、萬維網(wǎng) 北京大學(xué)學(xué)士學(xué)位論文 一種支持動態(tài)可配置的高效組通信系統(tǒng)的設(shè)計與實現(xiàn) - 2 - 第一章 引言 景簡介 介 萬維網(wǎng) (簡稱 一種特殊的結(jié)構(gòu)框架，它的目的是為了訪問遍布在因特網(wǎng)上數(shù)以萬計的機(jī)器上的鏈接文件。在短短的五年之內(nèi)，它從一種發(fā)布高能物理數(shù)據(jù)的方式演變?yōu)槿缃駭?shù)百萬人腦中的“因特網(wǎng)”。它之所以如此流行是由于它有一個豐富多彩的界面，初學(xué)者很容易使用，并且還提供了大量 的信息資源，幾乎涉及人們所能想象的所有主題，如從土著人到動物學(xué)。 989年 瑞士日內(nèi)瓦歐洲粒子物理實驗室 先開發(fā)的一個分布式超媒體信息查詢系統(tǒng)。 在 物理學(xué)家 1989 年 3 月 倡導(dǎo)下開發(fā)出來的， 牛津大學(xué)的畢業(yè)生，從事過文字處理及實時通信方面的研究。他開發(fā) 動機(jī)是建立一個信息系統(tǒng)，在此系統(tǒng)中許多科學(xué)家可以相互合作，交流信息。 用超文本 (術(shù)將許多信息資源連接成一個信息網(wǎng)，信息網(wǎng)由結(jié)點和超鏈接組成。 結(jié)構(gòu)不同于文件系統(tǒng)的線性結(jié)構(gòu)， 的結(jié)點的連接關(guān)系是相互交叉的，一個結(jié)點可以以各種方式與另外的結(jié)點相連接。超文本的優(yōu)點是用戶可以通過傳遞一個超鏈接得到與當(dāng)前結(jié)點相關(guān)的其它結(jié)點的信息。超媒體是一個與超文本類似的概念，在超媒體中，超鏈接的兩端可以是文本結(jié)點，也可以是圖像，語音等各種媒體的數(shù)據(jù)。 第一個原型（基于文本）于 18 個月后運行。 1991 年 12 月在德克薩斯州的 1 超文本會議上進(jìn)行了一次演示，并于 1993 年 2 月，隨著第一個圖形界面 發(fā)布而達(dá)到了其發(fā)展的高峰。 在 1993 年下半年， 不到三個月的時間里翻了一翻。在 1995 年 4月， 網(wǎng)上的流量超過了其它 其它服務(wù)的流量，成為 1997 年 12 月，根據(jù) 究院在科學(xué)雜志上發(fā)布的數(shù)據(jù)，網(wǎng)上大約有 3 億 2000 萬網(wǎng)頁。 在最近兩年里， 得到了長足的發(fā)展，不僅成為企業(yè)必不可少的組成部分，并且開始走進(jìn)千家萬戶。根據(jù) 究院截止到 2000 年 2 月， 務(wù)的有效網(wǎng)站 4,217,324 個；共有不重復(fù) 頁超過 10 億。 北京大學(xué)學(xué)士學(xué)位論文 一種支持動態(tài)可配置的高效組通信系統(tǒng)的設(shè)計與實現(xiàn) - 3 - 索引擎簡介 發(fā)展給人們帶來了巨大的方便，使得人們可以跨越時間和空間的界限來共享大量的信息。但是，面對如此大量的信息，我們同時也開始感到無所適從。太多的信息使我們很難迅速定位到我們真正需要的部分；由于 有統(tǒng)一的組織和規(guī)劃，僅靠超鏈 (無目的地漫游則會浪費大量的時間，而且很可能徒勞無功。因此，人們迫切需要有效的信息發(fā)現(xiàn)工具來為他們在 進(jìn) 行導(dǎo)航。 目前，一個有效的途徑是建立搜索引擎。搜索引擎系統(tǒng)通過程序自動地從網(wǎng)上搜集和分析網(wǎng)頁，建立索引，為用戶服務(wù)。這類系統(tǒng)的優(yōu)點是涵蓋的網(wǎng)頁數(shù)量巨大，但搜索的準(zhǔn)確率相對比較低，其典型代表是 搜索引擎出現(xiàn)于 1994 年，在短短的 7 年時間里，經(jīng)歷了天翻覆地的變化。1994 年， 作為最早出現(xiàn)的搜索引擎之一，可以索引 110,000 網(wǎng)頁。 1994 年 3 月、 4 月， 均每天收到 1500 個查詢。 1997年 12 月，當(dāng)時的頂級搜索引擎 稱可以索引 1 億網(wǎng)頁， 千萬條查詢。進(jìn)入 2000 年搜索引擎開始以嘗試索引“整個標(biāo)志。幾個主流的搜索引擎，如 都不斷擴(kuò)展自己的搜集能力，企圖將整個 的數(shù)據(jù)都搜集到，建立索引并為用戶提供服務(wù)。 2000 年 12 月， 索引擎可以索引 1,326,920,000 網(wǎng)頁， 儲超過 10 億的網(wǎng)頁，每天可以收到億萬計的查詢。 隨著搜索引擎的發(fā)展，逐漸出現(xiàn)了自動分類技術(shù)代替人工分類。 2000 年 3 月， 布研 制出先進(jìn)的目錄搜索技術(shù)，準(zhǔn)備與 訊公司合作推出更加快捷、全面的目錄搜索引擎服務(wù)。 在一定程度上使用了該技術(shù)。 搜索引擎面世后，雖然抱怨不斷，但它迅速成為人們網(wǎng)上搜索的有效工具。根據(jù)統(tǒng)計，大約 85%的用戶使用搜索引擎去定位他們需要的信息 5；并且，幾個著名的搜索引擎一直都穩(wěn)定的處于全球訪問量最大的 10 個網(wǎng)站之列。 網(wǎng)搜索引擎簡介 國外搜索引擎雖然起步較早，功能全面，性能良好，但是它們的共同缺點是都 不能很好地支持中文信息的發(fā)現(xiàn)和查詢。雖然 搜索引擎在 1998 年上半年宣布支持中文，但在對中文信息的處理上還存在很多不足，如不能準(zhǔn)確切詞，不能在上下文環(huán)境中理解語義等等。 天網(wǎng) (英文搜索引擎是北京大學(xué)計算機(jī)系網(wǎng)絡(luò)與分布式系統(tǒng)研究室在“九五”科技攻關(guān)項目基金的資助下研制開發(fā)的，它是主要針對中國豐富的信息資源而開發(fā)的具有中文特色的搜索引擎。自 1997 年 10 月正式在 提供查詢服務(wù)以來，“天網(wǎng)” (總訪問量已突北京大學(xué)學(xué)士學(xué)位論文 一種支持動態(tài)可配置的高效組通信系統(tǒng)的設(shè)計與實現(xiàn) - 4 - 破 800 萬次，目前日訪問量約為 3、 4 萬次，得到了廣大用戶的好評。 網(wǎng)搜索引擎的系統(tǒng)結(jié)構(gòu) 圖 索引擎的系統(tǒng)結(jié)構(gòu) 圖 出了 系統(tǒng)結(jié)構(gòu)?？梢钥闯觯瑥墓δ苣K上劃分，統(tǒng) 集子系統(tǒng)）、 引子系統(tǒng)）、 索子系統(tǒng)）和 志挖掘子系統(tǒng)）四個子系統(tǒng)構(gòu)成。 括制器 )、 集器 )和 始數(shù)據(jù)庫 )； 括 引器）和 引數(shù)據(jù)庫）； 括 索器）和戶接口）； 括 戶行為日志數(shù)據(jù)庫）和 志分析器）。 了按照啟發(fā)式算法優(yōu)先選擇重要的 完成站點過濾、實現(xiàn) 議及域名解析 功能。 照 議負(fù)責(zé)從網(wǎng)上抓取網(wǎng)頁，為提高網(wǎng)頁搜集速度，通?？梢酝瑫r啟動上百個 時工作。 時對搜集回來的網(wǎng)頁內(nèi)容進(jìn)行分析處理，包括調(diào)用切詞軟件以提取關(guān)鍵詞和摘要，提取 鏈，記錄網(wǎng)頁的元信息（如作者、修改日期、長度等），并將這些內(nèi)容存入 內(nèi)容重新組織，建立 提高檢索效率。 它轉(zhuǎn)發(fā)給 據(jù)查詢項和內(nèi)容，找到匹配的網(wǎng)頁后，進(jìn)行相關(guān)度計算并排序，然后通過回給用戶。另外， 序還將用戶行為信息（包括用戶查詢項、用戶點擊的 戶翻頁情況等）記錄到 于跟蹤用戶行為，以提高搜索引擎的服務(wù)質(zhì)量，如可以學(xué)習(xí)新詞來動態(tài)更新詞典控制器 搜集器 原始 數(shù)據(jù)庫據(jù)庫 索引器 索引 數(shù)據(jù)庫 檢索器 用戶接口 戶 用戶行為日志數(shù)據(jù)庫 日志分析器 北京大學(xué)學(xué)士學(xué)位論文 一種支持動態(tài)可配置的高效組通信系統(tǒng)的設(shè)計與實現(xiàn) - 5 - 內(nèi)容。 網(wǎng)的技術(shù)特色 天網(wǎng)的搜索范圍除中國 豐富的信息資源外，還包括 務(wù)器的 網(wǎng)屬于機(jī)器人搜索引擎范疇，主要采取了基于服務(wù)器模式具有導(dǎo) 向功能的搜索和提供文本摘要的方式。在實現(xiàn)中，天網(wǎng)使用了中文自動識別和中文編碼自動轉(zhuǎn)換技術(shù)、根據(jù)中文的語言特點和表達(dá)習(xí)慣對中文信息進(jìn)行詞語切分和詞類標(biāo)注技術(shù)以及基于詞的大型、高效的信息索引數(shù)據(jù)庫和快速準(zhǔn)確的檢索技術(shù)等先進(jìn)的中文信息處理和索引技術(shù)，從而大大提高了中文信息的理解程度和發(fā)現(xiàn)、檢索效率，同時也提高了漢語的查準(zhǔn)率。 目前，天網(wǎng)還不支持中文分類目錄，只提供關(guān)鍵詞（或關(guān)鍵字）查詢。 系統(tǒng)的前端提供了 種接口，后臺則由若干 主控的導(dǎo)向控制下，使用具有高度智能性和適應(yīng)性的信息發(fā)現(xiàn) 算法搜索網(wǎng)頁及 取關(guān)鍵詞及摘要，形成原始數(shù)據(jù)庫，然后在此基礎(chǔ)上建立索引數(shù)據(jù)庫。 來自前端的用戶信息，傳給檢索服務(wù)器，經(jīng)過查詢優(yōu)化，產(chǎn)生結(jié)果回送用戶。 天網(wǎng)搜索引擎的檢索是基于詞匯的，克服了中文分詞的困難，同時具有中英文詞匯自動學(xué)習(xí)的能力。 它側(cè)重于中文信息的發(fā)現(xiàn)，向全世界的中文用戶提供準(zhǔn)確、有效的網(wǎng)絡(luò)中文信息。 于采用了可伸縮的分布式結(jié)構(gòu)、查詢 引數(shù)據(jù)庫和檢索數(shù)據(jù)庫分開等先進(jìn)、有效的技術(shù)，使得系統(tǒng)占用資源少、信息收集速度快、用戶查詢響應(yīng)時間快（系統(tǒng)對 上的查詢可在 1秒鐘之內(nèi)作出響應(yīng)）、查準(zhǔn)率和查全率較高，基本達(dá)到了實用化程度。 系統(tǒng)在設(shè)計和實現(xiàn)過程中，充分考慮到了用戶和管理員的使用習(xí)慣，提供了瀏覽器、電子郵件、中英文用戶接口和方便使用、功能豐富的管理工具，因而有很好的可用性和易用性。 綜上，天網(wǎng)搜索引擎具有以下技術(shù)特色： 信息收集符合 相關(guān)協(xié)議和標(biāo)準(zhǔn)。 實用、高效的信息分析方法 高度智能性和適應(yīng)性的信息發(fā)現(xiàn)方法 中文信息處理技術(shù) 可伸縮的分布式結(jié)構(gòu) 基于詞的大型、高效的信息索引數(shù)據(jù)庫和快速、準(zhǔn)確的檢索方法。 智能化、多功能的 用戶檢索接口 北京大學(xué)學(xué)士學(xué)位論文 一種支持動態(tài)可配置的高效組通信系統(tǒng)的設(shè)計與實現(xiàn) - 6 - 網(wǎng)的搜集系統(tǒng)中引入分布策略及組通訊技術(shù)的意義 要在搜索引擎中盡可能地找到用戶所需信息，就要求搜索引擎索引盡可能多的網(wǎng)頁。因此索引網(wǎng)頁數(shù)量是評價一個搜索引擎好壞的關(guān)鍵因素之一。要索引更多的網(wǎng)頁就要獲取更多的網(wǎng)頁，因此高效 地獲取網(wǎng)頁是一個好的搜索引擎的基礎(chǔ)。 提到“高效”執(zhí)行某些大數(shù)據(jù)量的工作，人們?nèi)菀紫氲健胺植际健?、“并行處理”這樣的字眼。事實也是如此。目前，日訪問量已突破 3 萬的北大“天網(wǎng)”中英文搜索引擎系統(tǒng)（ 采用集中式搜集網(wǎng)頁的處理方式（一個 主控控制多個搜集程序并行工作），索引網(wǎng)頁達(dá)到 100 萬量級。全部網(wǎng)頁更新周期為 10 天，即 每天大約要搜集 10 萬網(wǎng)頁，達(dá)到 100 萬量級。 出自斯坦福大學(xué)的 索引擎在 2000 年 7 月可以索引 560,000,000 網(wǎng)頁，要達(dá)到這個量級，網(wǎng)頁的更新是集中式系統(tǒng)在短時間內(nèi)所不能勝任的。如果以 達(dá)到 1000 萬量級需要 100 天， 100 天中由于網(wǎng)頁的更新，將使搜集到的部分網(wǎng)頁失去意義。因此，采用分布式技術(shù)在盡可能短的時間內(nèi)搜集盡可能多的網(wǎng)頁，是研制高效搜索引擎的關(guān)鍵技術(shù)。 與傳統(tǒng)的集中式系 統(tǒng)相比，分布式系統(tǒng)具有下述優(yōu)點： 優(yōu)點 說明 經(jīng)濟(jì)性 微處理器能提供比大型機(jī)更好的性能價格比 速度 分布式系統(tǒng)能提供比大型機(jī)更強(qiáng)的計算能力 固有的分布性 有一些應(yīng)用包含物理上分散的機(jī)器 可靠性 當(dāng)某臺機(jī)器崩潰時，整個系統(tǒng)仍能正常工作 可擴(kuò)展性 計算能力逐步增加 表 布式系統(tǒng)的優(yōu)點 盡管分布式系統(tǒng)有自己的優(yōu)勢，它也有自身的缺點。首先是軟件問題。即便使到今天，我們依然沒有多少設(shè)計、實現(xiàn)和使用分布式軟件的經(jīng)驗。第二個問題與通信網(wǎng)絡(luò)有關(guān)。網(wǎng)絡(luò)可能丟失數(shù)據(jù)，需要有特殊 的軟件處理。它也有可能過載，當(dāng)網(wǎng)絡(luò)飽和時，要么被替換掉，要么增加一個新的網(wǎng)絡(luò)。這兩種選擇都需要全部或部分地重新布線，更換網(wǎng)卡。當(dāng)系統(tǒng)依賴于網(wǎng)絡(luò)時，網(wǎng)絡(luò)中的數(shù)據(jù)丟失或過載會抵消分布式系統(tǒng)的優(yōu)點。第三，數(shù)據(jù)共享導(dǎo)致安全性問題。 盡管有上述潛在的問題，總的說來分布式的優(yōu)點超過了它的缺點，并且分布式系統(tǒng)將越來越重要。就搜索引擎系統(tǒng)而言，采用分布式系統(tǒng)更是利大于弊。身就是分布式的，適合于采用分布式方案搜集索引。搜索引擎系統(tǒng)采用分布式，可以繼承分布式系統(tǒng)本身的優(yōu)點，同時，通過精心設(shè)計，可以避免分布式 系統(tǒng)本身的缺點。我們首先面臨的就是分布系統(tǒng)中軟件問題，為使我們的分布式系統(tǒng)具有高可用性、動態(tài)可配置性，負(fù)載平衡，需要解決分布式系統(tǒng)中進(jìn)程之間的組通信問題。 北京大學(xué)學(xué)士學(xué)位論文 一種支持動態(tài)可配置的高效組通信系統(tǒng)的設(shè)計與實現(xiàn) - 7 - 程組通訊技術(shù)簡介 在分布式系統(tǒng)結(jié)構(gòu)中，互相協(xié)作的進(jìn)程需要通信和同步。例如，分布在不同計算機(jī)上一到多個進(jìn)程，通過互相之間的通信實現(xiàn)一個服務(wù)，也許還要提供容錯功能以增加可用性，采用簡單的點到點的信息交換方式并不是最好的方法。組通信（ 適合這種方式。組通信是一個進(jìn)程發(fā)送消息給一組進(jìn)程。在分布式應(yīng)用中，能夠提供容錯功 能的組通信是一種非常有用的方法。引入組概念的目的是想將進(jìn)程的集合作為一個抽象的整體來處理。這樣一個進(jìn)程可以發(fā)送一個消息給一組服務(wù)器，而不需知道該組的成員數(shù)目，它們的位置等等。 根據(jù)對可靠性的要求組通信協(xié)議主要分兩大類 5。一類是保證組通信具有很強(qiáng)的可靠性。這一類組通信通常包含原子性性。原子性保證一個發(fā)送給某個組的消息，它要么被該組所有成員接收，要么就不被任何成員接收。原子性同時可以提供消息傳遞的順序性，虛擬同步，安全性，時時性，網(wǎng)絡(luò)斷開等要求。但是要保證很高的可靠性，必須采用昂貴的協(xié)議，從而帶了了系統(tǒng)在 大負(fù)荷運行條件下的不穩(wěn)定和性能不可預(yù)測，以及有限的可伸縮性。短暫的系統(tǒng)性能問題可以導(dǎo)致這些協(xié)議處理能力的大幅下降。即使在很穩(wěn)定的網(wǎng)絡(luò)條件下，也很難將這類協(xié)議擴(kuò)展到有幾百個參與者的情況。 另一類協(xié)議努力保證大規(guī)模條件下的最大可能的可靠性。如 用于網(wǎng)絡(luò)新聞的分發(fā)） 25， 26， 12， 27。這些系統(tǒng)包含了可伸縮的多播協(xié)議來克服消息的丟失和失敗，但是不能保證端到端的可靠性。沒有核心系統(tǒng)跟蹤組中的成員，因此可能不清楚哪些進(jìn)程屬于多播的目的進(jìn)程，也不清楚多播組是大還是小。典型的情況是，進(jìn)程匿名加入多播發(fā)送樹。同樣的，一個進(jìn)程組的成員可以退出或者失敗而不用事先通知它的臨近進(jìn)程。 組通信的實現(xiàn)很大程度上取決于硬件。在一些網(wǎng)絡(luò)里，可以創(chuàng)建一些特殊的特殊網(wǎng)絡(luò)（例如，將地址高位置 1），來通知監(jiān)聽的多臺機(jī)器。當(dāng)消息包被送往這些地址中的一個時，它會自動被傳遞到所有在該 地址上監(jiān)聽的機(jī)器。這種方法稱為多播（ 用多播實現(xiàn)組通信很容易，只要為每一組指定一個不同的多播地址就可以了。第二種實現(xiàn)組通信的方法是采用廣播 ,即目的地址為某個特定地址（比如說， 0）的包被發(fā)送到所有的機(jī)器。但是效率低，每臺機(jī)器都將收到廣播包，都需要特殊的軟件來檢測這一個包是不是自己應(yīng)該接受的。如果不是，包被丟棄。但是，處理中斷浪費了大量時間。第三種方法，在上述兩種方法均不存在時，組通信可以通過發(fā)送者分別發(fā)送消息給組中每一個成員來實現(xiàn)。盡管效率低，這種方法確實是可以使用的，特別是在大多數(shù) 組都很小的情況下。 組通信設(shè)計方案上需要考慮如下問題：閉合組和開放組；對等組和層次組；組成員；組編址；發(fā)送和接收原語；原子性；消息序列；組重疊；可擴(kuò)展性。 北京大學(xué)學(xué)士學(xué)位論文 一種支持動態(tài)可配置的高效組通信系統(tǒng)的設(shè)計與實現(xiàn) - 8 - 1. 閉合組和開放組：閉合組指只有該組的成員才可以發(fā)送消息給該組。開放組指系統(tǒng)里任何進(jìn)程都可以發(fā)送消息給任意組。 2. 對等組和層次組：對等組中所有進(jìn)程都是處于同等地位的。所有決策都由組中所有進(jìn)程共同決定。層次組中協(xié)調(diào)者進(jìn)程進(jìn)行決策，當(dāng)有一個來自外部客戶或組內(nèi)成員的請求時，它被首先送給協(xié)調(diào)進(jìn)程，由協(xié)調(diào)進(jìn)程來決定那個參與者進(jìn)程適合完成這項請求。 3. 組成員問題涉及 到組的創(chuàng)建和刪除，進(jìn)程加入或離開某個組。 4. 組編址：為了向一個組發(fā)送消息，進(jìn)程必須要能夠指定它的目的組地址。 5. 發(fā)送和接收原語：理想情況下，點到點和組通信應(yīng)該采用用一組原語。但是，若采用 不是原始的 為通常的用戶通信機(jī)制，會很難將 6. 原子性：大多數(shù)組通信系統(tǒng)里，一個被發(fā)送給某個組的消息，它要么被該組所有成員正確接收，要么就不被任何成員接收。不允許組內(nèi)一些成員接收了該消息，而另一些成員卻沒有。這種整體傳遞的性質(zhì)稱為原子性。 7. 消息序列：來自于不同進(jìn)程的 多播消息包可能以不同的順序到達(dá)多播的目的進(jìn)程，從而產(chǎn)生數(shù)據(jù)的不一致。組通訊需要保證存在因果關(guān)系的消息以同樣的順序到達(dá)各組成員。 8. 組重疊：一個進(jìn)程可以同時是多個組的成員。這樣會導(dǎo)致同時屬于兩個組以上的進(jìn)程接收到不同順序的消息。在不同組之間實現(xiàn)時間排序通常很難辦到，因此需要考慮這樣做是否值得。 9. 可擴(kuò)展性：許多算法在組內(nèi)只有少數(shù)幾個成員時工作得很好，但如果每個組內(nèi)有幾十個，幾百個，或是幾千個成員呢？或者，有幾千個組呢？同樣的，如果系統(tǒng)大到單個局域網(wǎng)已不能滿足要求，而需要多個局域網(wǎng)和網(wǎng)關(guān)時，該怎么辦呢？如果組被 分散到幾個大洲，又該如何處理呢？ 最早包含組通信系統(tǒng)的是 V28系統(tǒng)。其后有了在第二章中要重點介紹的學(xué)的組通信以及 統(tǒng)的組通信等支持組通信的系統(tǒng)。 們采用的方案 由于我們開發(fā)的組播通訊系統(tǒng)是面向“天網(wǎng) ”的分布式搜集系統(tǒng)的一個工具包，它所采用的設(shè)計方案以保證“天網(wǎng)”的高效準(zhǔn)確運行為主，同時考慮到軟件的復(fù)用性及以后系統(tǒng)的升級，兼顧效率和功能的完備性。 目標(biāo)是搜集中國所有的網(wǎng)頁。 根據(jù)計算， 要搜集9,520,000 左右的網(wǎng)頁。以 10 天為周期，仍然按照 有的速度進(jìn)行搜北京大學(xué)學(xué)士學(xué)位論文 一種支持動態(tài)可配置的高效組通信系統(tǒng)的設(shè)計與實現(xiàn) - 9 - 集，則需要 10 臺機(jī)器分布式協(xié)作，并且在單臺性能沒有降低的條件下才能夠完成。達(dá)到上述目標(biāo)的同時，希望分布式系統(tǒng)具有如下特點： 1. 負(fù)載平衡 2. 主控通訊量少 3. 具有可擴(kuò)展性，即隨著主控的增加性能應(yīng)有所提高 4. 具有動態(tài)調(diào)度性，即運行過程中添加和刪除主控 因此，我們的組播通訊系統(tǒng)面向的是一個規(guī)模較小，組視圖變化不頻繁，要求通訊量盡量小，運行速度盡量快，而且要求提供消息傳播的高可靠性和完備的組視圖維護(hù)功能的進(jìn)程組。 基于目前的設(shè)備，這個組播通訊系統(tǒng)以 議為通信基礎(chǔ) 。它是一個閉合組，任何一個搜集主控要想和組中的進(jìn)程互發(fā)消息，都要首先加入組。它是一個層次組，存在著一個協(xié)調(diào)者，組中所有成員的 址按照順序存儲在一個組地址數(shù)組中，每個組成員在自己的內(nèi)存中維護(hù)這樣一個組地址數(shù)組，它的一致性由協(xié)調(diào)者發(fā)送特殊的組播消息來維護(hù)；規(guī)定組地址數(shù)組中的第一個成員為協(xié)調(diào)者，因此當(dāng)組視圖發(fā)生變化時，協(xié)調(diào)者有可能改變。其中的組播消息必須有嚴(yán)格的可靠性，原子性， 組通訊系統(tǒng)還需要保證存在因果關(guān)系的消息以同樣的順序到達(dá)各組成員。 章的組織和結(jié)構(gòu) 本文的實踐工作主要包括參與了北大“天網(wǎng) ”中英文搜索引擎的分布式搜集系統(tǒng)中的進(jìn)程組通信系統(tǒng)的設(shè)計和實現(xiàn)。本文主要介紹了進(jìn)程組通信技術(shù)的一些基本概念，目前比較有代表性的幾個進(jìn)程組通信系統(tǒng)，以及如何在“天網(wǎng)”的分布式搜集系統(tǒng)中應(yīng)用相關(guān)技術(shù)實現(xiàn)我們的進(jìn)程組通信系統(tǒng)。其中重點是應(yīng)用于“天網(wǎng) ”的進(jìn)程組通信系統(tǒng)的設(shè)計和實現(xiàn)。 文章余下各章的內(nèi)容大致如下： 第二章（進(jìn)程組通信相關(guān)研究）主要介紹目前比較有代表性的進(jìn)程組通訊系統(tǒng)： 學(xué)的組通信以及 統(tǒng)的組通信等支持組通信的系統(tǒng)。 第三章（進(jìn)程組通信系統(tǒng)的設(shè)計）主要介紹“天網(wǎng)”的進(jìn)程組通 信系統(tǒng)設(shè)計方案。首先介紹了設(shè)計的目標(biāo)和整體結(jié)構(gòu)；其后，詳細(xì)介紹了在進(jìn)程組通信系統(tǒng)中是如何確保消息的可靠性，有序性和當(dāng)組視圖變化時組播消息的一致性。 第四章（進(jìn)程組通信系統(tǒng)的實現(xiàn)）主要介紹了“天網(wǎng)”的進(jìn)程組通信系統(tǒng)的實現(xiàn)。首先介紹了用戶接口，接著介紹了幾個工作線程和主要的數(shù)據(jù)結(jié)構(gòu)，然后詳細(xì)介紹了消息接收和處理過程及消息發(fā)送過程的實現(xiàn)。 第五章（總結(jié)與展望）總結(jié)了目前的“天網(wǎng)”進(jìn)程組通信系統(tǒng)的現(xiàn)狀和不足，為以后的進(jìn)一步工作進(jìn)行了展望和設(shè)想。 北京大學(xué)學(xué)士學(xué)位論文 一種支持動態(tài)可配置的高效組通信系統(tǒng)的設(shè)計與實現(xiàn) - 10 - 第二章 進(jìn)程組通訊相關(guān)研究 目前比較有代表性的進(jìn)程組通訊系統(tǒng)是 下面要重點介紹的 學(xué)的組通信以及 統(tǒng)的組通信等支持組通信的系統(tǒng)。 學(xué)的組通信系統(tǒng) a) b) c) 圖 2.1 a)同步系統(tǒng) b)弱同步系統(tǒng) c)虛擬同步系統(tǒng) 學(xué)已經(jīng)開發(fā)了三代可靠性組通信技術(shù)以及正在開發(fā)的第四代可靠性組通信技術(shù)。 具集 : 1987 統(tǒng) : 1990 統(tǒng) : 1994 統(tǒng) : 1999- 統(tǒng)的結(jié)構(gòu)目標(biāo)是基于進(jìn)程組的可靠性分布式計算。 一個建立分布式應(yīng)用的工具包，類似的應(yīng)用如，協(xié)調(diào)紐約、瑞士證券公司各個代理的股票交易，法國航空交通管制系統(tǒng)，西南貝爾電話網(wǎng)絡(luò)等。 是一個完全的操A B C D 2 時間 A B C D 2 A B C D 2 達(dá) 達(dá) 北京大學(xué)學(xué)士學(xué)位論文 一種支持動態(tài)可配置的高效組通信系統(tǒng)的設(shè)計與實現(xiàn) - 11 - 作系統(tǒng)，而是一組程序的集合，這些程序可以在 其他現(xiàn)存的操作系統(tǒng)上運行。 主要思想是“同步”，它的主要通信原語是形式各異的原子廣播。在討論 何實現(xiàn)原子廣播之前，有必要首先來看一下幾種同步類型。一個同步的系統(tǒng)是這樣的，它 的事件按照嚴(yán)格的順序發(fā)生，每個事件理論上都只是在 0時間內(nèi)完成。例如，如果進(jìn)程 、 ，如圖 2消息將瞬間到達(dá)所有的目的地。同樣，接著一個從 D 發(fā)送的消息也只需要 0時間被傳送到各個目的地。從外部觀察者的角度看來，系統(tǒng)由離散的事件構(gòu)成，彼此之間互不重疊。 同步系統(tǒng)是不可能創(chuàng)建的，所以需要考察其它在時間上要求較低的系統(tǒng)。如圖 2個“弱同步系統(tǒng)”可以滿足要求，它的每個事件需要一個有限的時間，但是任何一方看來，所有時間順序都是一樣的。特別是，所有的進(jìn)程按照同樣的順序接收消息。 這樣的系統(tǒng)是有可能實現(xiàn)的，但對于一些應(yīng)用來說，甚至更弱的語義也可以接收，因此就可以減弱語義，換取性能。圖 2一個“虛擬同步系統(tǒng)”，它放寬了包的順序限制。 在一個分布式系統(tǒng)中，兩個事件被稱為“因果相關(guān)”，如果第二個事件的行為可能受到第一個事件的影響。所以如果 A 發(fā)送一個消息給 B， B 接收了，然后發(fā)送一個新的消息給 C，那么第二個消息就和第一個消息因果相關(guān)，因為它的內(nèi)容可能包含了第一個消息的一部分，而是實際上是否如此并沒有關(guān)系。只要可能存在影響，這種相關(guān)就成立。 兩個不相關(guān)的事件稱為“并發(fā)事件”。如果 A 發(fā)送了一個消息給 B，同時 ，這兩個事件就是并發(fā)的，因為互相沒有影響。虛擬同步的真正含義就是，如果兩個消息是因果相關(guān)的，那么所有的進(jìn)程必須以相同的順序接收它們。但是，若它們是并發(fā)的，就沒有什么限制，系統(tǒng)可以隨意的按不同的順序?qū)⑺鼈儼l(fā)送給不同的進(jìn)程。 現(xiàn)在討論 用的廣播原語。其中有包括三個： 它們具有不同的語義。 供弱同步通信，用于傳送數(shù)據(jù)到一個組的成員。 供虛擬同步通信，用于發(fā)送數(shù)據(jù)。 些類似于和 它用于管理組成員，而不是發(fā)送普通數(shù)據(jù)。 送者 常是一個序列號），把它發(fā)送給所有的組成員（顯示的指出所有組成員的名字）。每個成員檢查該消息的時間輟，域它所發(fā)送和接收過的時間輟比較，從選出最大的，北京大學(xué)學(xué)士學(xué)位論文 一種支持動態(tài)可配置的高效組通信系統(tǒng)的設(shè)計與實現(xiàn) - 12 - 把它發(fā)送回 A。 A 收到所有返回的時間戳以后，選擇其中最大的，在一次發(fā)送一個含有 該時間戳的“提交”消息給所有的成員。提交的消息被按時間戳的順序傳遞給應(yīng)用程序。這樣的協(xié)議保證了所有的消息可以以相同的順序被接收。 這種協(xié)議很復(fù)雜，而且代價太昂貴。因此， 設(shè)計者們又提出了 只保證有因果相關(guān)的消息被順序接收。（ 議現(xiàn)在已經(jīng)更新過了，但即使如此，也比 慢。） 議工作如下：如果一個組有 么每個進(jìn)程就維護(hù)一個 個元素對應(yīng)于一個成員。第 始時，該向量設(shè)為 0，如圖 圖 息只能在所有與它有因果關(guān)系的“原因”消息被傳送后，才能被傳送 當(dāng)一個進(jìn)程有消息要發(fā)送時，它在自己保留的向量里，將相應(yīng)于自己的元素加 1，然后將該向量作為消息的一部分發(fā)送出去。當(dāng)圖 1到達(dá) 將檢查該消息是否依賴于某些 向量的第一個元素應(yīng)該比B 自己保留的值多 1，其他都一樣，因此該消息被接收，然后被傳遞給在 B 上運行的組成員。 現(xiàn)在 B 發(fā)送了一個消息 ，它將在 該向量里， C 發(fā)現(xiàn)在 發(fā)送的消息，而因為它還沒收到任何來自A 發(fā)送的消息， 到 A 的消息到來。無論如何， 的消息之前被傳遞出去。 下面介紹一個通用算法，它決定將進(jìn)來的消息緩存還是傳遞給用戶進(jìn)程。設(shè) i 分量， i 個分量。假設(shè)消息是從 接收的首要條件是 。它表明，這是從2 A B C (0,0,0) (0,0,0) (1,0,0) (1,1,0) (1,0,0) (0,0,0) 初始 向量 消息 達(dá)但不能發(fā)出 在 達(dá)并發(fā)給應(yīng)用程序后， 被發(fā)給它 北京大學(xué)學(xué)士學(xué)位論文 一種支持動態(tài)可配置的高效組通信系統(tǒng)的設(shè)計與實現(xiàn) - 13 - 就是說，沒有消息被漏掉。（來自同一發(fā)送者的消息總是因果相關(guān)的。）其次，必須對所有的 i j， 表明發(fā)送者還沒有發(fā)現(xiàn)任何接收者錯過的消息。如果一個進(jìn)來的消息符合這兩項檢驗，系統(tǒng)就可以將它傳遞給用戶進(jìn)程，而不用延遲。否則，它必須等待。 圖 示了一個有關(guān)向量機(jī)制的更詳細(xì)的例子。進(jìn)程 0 發(fā)送一個包含向量（ 4,6,8,2,1,5）的消息給其他 5 個組成員。進(jìn)程 1 已經(jīng)看見了和進(jìn)程 0 一樣的消息，因此該消息通過檢驗，被接收，并被傳遞給用戶進(jìn)程。進(jìn)程 2錯過了進(jìn)程 1發(fā)送的消息 6，所以進(jìn)來的消息必須等待。進(jìn)程 3看見了和進(jìn)程 0所看見的所有消息，此外還有來自進(jìn)程 1的消息 7，它顯然還沒有被進(jìn)程 0得到，因此 該消息被接收。進(jìn)程 4錯過了來自進(jìn)程 0的簽一個消息，所以新的消息必須等待。最后，進(jìn)程 5也比進(jìn)程 0稍微超前，因此該消息被進(jìn)程 5接收。 在 最重要的是 達(dá)了弱化的基于因果關(guān)聯(lián)的通信語義，它的實現(xiàn)是在消息里加上了一個序列號向量，這樣允許接收者檢查該消息是應(yīng)該被立即傳遞，還是延遲到在它之前的消息到來之后。 持重疊分組得消息排序，但算法比較復(fù)雜。 圖 供了基于組通信的分布式應(yīng)用框架，這些應(yīng)用包括容錯系統(tǒng)、可管理的分布式系統(tǒng)，以及使用數(shù)據(jù)復(fù)制、緩存一致和群件的應(yīng)用?？偟恼f來，的是以最小的代價為應(yīng)用程序的需求提供通訊模塊。 案原先是為重新設(shè)計 出的，結(jié)果發(fā)展成為一種通用意義上的組通信體系機(jī)構(gòu)，為開發(fā)健壯的分布式系統(tǒng)提供更高級的支持。如當(dāng)應(yīng)用程序?qū)Π踩曰蛘邥r時性有特別的要求時， 能支持，但 夠支持。 由進(jìn)程 0 送出的 消息 中的向量 在其他機(jī)器中向量狀態(tài) 0 4 6 8 2 1 5 1 3 6 8 2 1 5 2 3 5 8 2 1 5 4 2 6 8 2 1 5 5 3 7 8 3 1 5 3 3 7 8 2 1 5 接收 延遲 接收 延遲 接收 北京大學(xué)學(xué)士學(xué)位論文 一種支持動態(tài)可配置的高效組通信系統(tǒng)的設(shè)計與實現(xiàn) - 14 - 行的更快，消耗資源更少。 建 立組通信中虛擬同步（ 準(zhǔn)做出了巨大的貢獻(xiàn)。 通信系統(tǒng)是由 學(xué)聯(lián)合完成的。允許進(jìn)程創(chuàng)建進(jìn)程組，支持進(jìn)程組的具有可伸縮的可靠的多播和點到點通信，同時支持因果序，全序，流控等屬性。 似于 堆疊式結(jié)構(gòu)，可以運行的象樣快速。 展了 性能，增加支持多重分裂，有效的密鑰重發(fā)，應(yīng)用程序定義安全策略。 用現(xiàn)成的認(rèn)證系統(tǒng)，如 不是象 計了自己的安全機(jī)制，采用了非標(biāo)準(zhǔn)的密鑰分發(fā)系統(tǒng)和定時服務(wù)。為了便于系統(tǒng)驗證， 程語言完成。 創(chuàng)了基于 虛擬同步的組通信先河。但是為了解決虛擬同步本身具有的很大限制，例如，當(dāng)參加虛擬同步的進(jìn)程在 3 到 100 個時，工作的很好，但是當(dāng)組成員繼續(xù)增加時，系統(tǒng)變得很脆弱。尤其是當(dāng)組逐漸變大，數(shù)據(jù)吞吐量變得不穩(wěn)定。因此 開始了 統(tǒng)研制。 于全 新的方法。其核心協(xié)議支持多點數(shù)據(jù)傳送，并能保證相當(dāng)高的可靠性。這種模型采用可伸縮性協(xié)議，即使在不同形式的攻擊下，或者在每組包含成千上萬成員的多組通訊情況下，也能保證穩(wěn)定的吞吐量。 統(tǒng)的目標(biāo)是嵌入重要的軟件結(jié)構(gòu)和網(wǎng)絡(luò)操作系統(tǒng)中。 通信 一個分布式操作系統(tǒng)，它使許多 I/O 設(shè)備象一臺獨立的計算機(jī)一樣工作，它還為并行程序設(shè)計提供條件。 1981 年誕生于荷蘭阿姆斯特丹的 學(xué)，主要由 . 他的 3 個博士生. 計的。在 1983 年，第一個版本 入使用。 持組通信。 的組由一個或多個協(xié)同執(zhí)行某個任務(wù)或提供某個服務(wù)的進(jìn)程組成，這些進(jìn)程可以同時是幾個組的成員。組是封閉的，客戶存取一個由某個組提供的服務(wù)的典型方法是用 組中的一個成員通信，那個成員通過組通信決定組內(nèi)哪個成員應(yīng)該做什么（如果必要的話）。 選擇這種設(shè)計是為了提供比開放組結(jié)構(gòu)更大的透明度。這種思 想的深層是客戶通過 單獨的服務(wù)器通信，所以它也可以通過 整個組通信。開北京大學(xué)學(xué)士學(xué)位論文 一種支持動態(tài)可配置的高效組通信系統(tǒng)的設(shè)計與實現(xiàn) - 15 - 放組利用 單獨的服務(wù)器通信（而不是利用組通信和組服務(wù)器通信），透明度不高。一旦可以使組外的客戶用 組通信（實際上是和組中的一個進(jìn)程通信），就用不著開放組了，采用封閉組就足夠了。 組通信原語 組通信可使用的操作如表 示。 立一個新組同時返回一個別的調(diào)用能夠識別的組標(biāo)識符，參數(shù)指定組的大小和需要的容錯度（組能夠容忍且同時能夠正常工作的死成員個數(shù)）。 許進(jìn)程進(jìn)入和離開一存在的組。 一個參數(shù)是送給組中所有成員申明新來者存在的一條短消息。相似的，一個參數(shù)是一條短消息和組中所有成員道別并祝它們好運。段消息的要點是使所有的成員明白它們的通知是誰（如果他們感興趣）。然而，保持跟蹤對他們并不是必要的。但組中最后一個成員調(diào)用 ，組便刪除了。 動廣播一條消息給該組的所有成員，即使是信息丟失，緩沖區(qū)優(yōu)先或者進(jìn)程崩潰。 持全局時間順序，所以，如果兩個進(jìn)程近乎同時的調(diào)用 統(tǒng)保證組中成員與原來同樣的順序接收信息。這時系統(tǒng)保證的，程序員可以依賴這一點，如果兩個調(diào)用幾乎同時進(jìn)行，先被發(fā)送到 的保認(rèn)為先發(fā)。 圖從一個特定的組接收信息。如果沒有可用信息，調(diào)用浙江一致阻塞到有可用信息。如果信息已經(jīng)到來，調(diào)用立即返回。協(xié)議保證任何情況下信息不會不可挽回的丟失。 來恢復(fù)一個崩潰的組，它指明一個新組中成員的最小個樹。如國內(nèi)核能和必要數(shù)目的進(jìn)程建立連接且能重建的話， 回心組的大小，否則，調(diào)用失敗。 調(diào)用 描述 立新組并且設(shè)置參數(shù) 入組 開組 消息可靠傳送給組中成員 塞直到組中有消息送到 程崩潰后的初始恢復(fù) 表 通信原語 可靠廣播協(xié)議 支持組播和廣播（如以太網(wǎng)）的 工作得最好。用組播實現(xiàn)組間通信能夠避免打擾那些對送來的消息不感興趣的機(jī)器。 北京大學(xué)學(xué)士學(xué)位論文 一種支持動態(tài)可配置的高效組通信系統(tǒng)的設(shè)計與實現(xiàn) - 16 - 靠 廣播協(xié)議需要的軟硬件配置如圖 示。所有機(jī)器的配置通常是一樣的，同時它們運行相同的內(nèi)核。然而當(dāng)應(yīng)用程序啟動時，一臺機(jī)器將被選作 序器，就象一個委員會選舉一個主席一樣）。如果 下的成員重新選舉一個。許多選舉算法可以使用，如選擇擁有最高網(wǎng)絡(luò)地址的進(jìn)程。 實現(xiàn)可靠廣播的一系列步驟總結(jié)如下： 1). 用戶進(jìn)程陷入內(nèi)核并傳入消息。 2). 內(nèi)核接收消息并阻塞用戶進(jìn)程。 3). 內(nèi)核將消息通過一般的點到點通信方式送給 4). 當(dāng) 到消息，它分派下一個可用的序列號，將序列號存入為其保存的域中，同時廣播此消息和序列。 5). 當(dāng)發(fā)送內(nèi)核發(fā)現(xiàn)廣播消息頭中的消息，它激活被阻塞的調(diào)用進(jìn)程，使其繼續(xù)執(zhí)行。 圖 組通信的系統(tǒng)結(jié)構(gòu) 組通信的容錯功能 組通信協(xié)議提供容錯功能，可以承受通信組內(nèi)任意 K 個處理器（含 然崩潰的意外情況?；謴?fù)系數(shù) K 是在通信組創(chuàng)建時指定的，K 的值越大，就容易產(chǎn)生越多的冗余，在正常情況下操作也會越慢。 許多分布式算法中都要由一個進(jìn) 程充當(dāng)協(xié)調(diào)者（發(fā)起者、序列生成器或擔(dān)任其他特殊角色）。下面介紹選舉這種協(xié)調(diào)者 的算法。 如果所有進(jìn)程都完全相同，沒有可以區(qū)分的特征，就無法選出其中一個作為特殊進(jìn)程，因此假定每個進(jìn)程都由一個唯一的進(jìn)程號，如它的網(wǎng)絡(luò)地址（為簡單起見，假設(shè)每個進(jìn)程占用一臺機(jī)器）。通常選舉算法都指定具有最高進(jìn)程號的進(jìn)程作為協(xié)調(diào)者。但具體做法各有不通。 二期還要假定所有進(jìn)程都知道其他進(jìn)程的進(jìn)程號。它所不知道的是當(dāng)前哪內(nèi)核 內(nèi)核 A S 內(nèi)核 內(nèi)核 A S 內(nèi)核 內(nèi)核 A S 應(yīng)用 程序 能 能北京大學(xué)學(xué)士學(xué)位論文 一種支持動態(tài)可配置的高效組通信系統(tǒng)的設(shè)計與實現(xiàn) - 17 - 個進(jìn)程是活動的，哪個進(jìn)程已經(jīng)終止。選舉算法的目的就是：保證在選舉執(zhí)行后，所有進(jìn)程都認(rèn)可某個進(jìn)程成為新的協(xié)調(diào)者。 法 當(dāng)某個進(jìn)程 注意到協(xié)調(diào)者無法響應(yīng)進(jìn)程的請求時，該進(jìn)程就初始啟動一個選舉過程。進(jìn)程 P，執(zhí)行的選舉過程如下： 1)P 向所有進(jìn)程號比它高的進(jìn)程發(fā) 息。 2)如果得不到其他進(jìn)程的響應(yīng)，進(jìn)程 P 獲勝，成為協(xié)調(diào)者。 3)如果有一個進(jìn)程號更高的進(jìn)程響應(yīng)，該進(jìn)程就接管選舉過程。進(jìn)程 任何時刻進(jìn)程都有可能收到進(jìn)程號比她小的進(jìn)程發(fā)送的 息。該消息到達(dá)時，消息的接收者就向消息發(fā)送者發(fā)送一個 息，說明它仍是活動進(jìn)程，如果接收者沒有掌管選舉過程，它將接管選舉過程。最后，其他進(jìn)程都放棄只剩一個進(jìn)程是，該進(jìn)程成為新的協(xié)調(diào)者。然后它向所有進(jìn)程發(fā)送消息，通知這些進(jìn)程從此刻起它已是新的協(xié)調(diào)者了，從而宣布它的勝利。 一個以前被終止的進(jìn)程重新恢復(fù)后，也有選舉權(quán)。如果它碰巧是目前運行的所有進(jìn)程中進(jìn)程號最大的一個，就贏得選舉，并接管協(xié)調(diào)者的工作。由于在小鎮(zhèn)上總是最厲害的家伙獲勝，因此有了“ 法”的名稱。 算法 假定對所有進(jìn)程進(jìn)行了物理或邏輯排序，因此每個進(jìn)程都知道它的后繼進(jìn)程是哪個進(jìn)程。任何一個進(jìn)程發(fā)現(xiàn)協(xié)調(diào)者不再起作用時，就創(chuàng)建一條包含該進(jìn)程進(jìn)程號的 息，并將該消息發(fā)送給其他后繼進(jìn)程。如果后繼進(jìn)程已經(jīng)中止，就跳過它發(fā)送給下一個進(jìn)程，以此類推，直到找到一個正在運行的進(jìn)程為止。每個進(jìn)程接收到 息后，就將自己的進(jìn)程號加入消息中的進(jìn)程表。 最后 息會回到創(chuàng)建它的那個進(jìn)程。進(jìn)程接收到的 息中已經(jīng)包含該進(jìn)程的進(jìn)程號 時，就可以斷定這條消息是由它自己創(chuàng)建的。這時，將消息類型該為 次在環(huán)上循環(huán)發(fā)送。這次是將新的協(xié)調(diào)者（進(jìn)程表中進(jìn)程號最大的進(jìn)程）和環(huán)上現(xiàn)有的成員通知給其他進(jìn)程。 息在環(huán)上循環(huán)一周后，從環(huán)上移去該消息，各進(jìn)程恢復(fù)其原有操作。 章小結(jié) 本章高度概括了當(dāng)前進(jìn)程組通訊領(lǐng)域所采用的系統(tǒng)結(jié)構(gòu)和方法，具體分析了幾種具有代表性的系統(tǒng)，并分析比較了它們的核心技術(shù)。 就搜索引擎系統(tǒng)而言，采用分布式系統(tǒng)利大于弊。 身就是分布式的，適合于采用分布式方案搜集索引 。搜索引擎系統(tǒng)采用分布式，尤其需要解決進(jìn)程之間的組通信問題。分布式系統(tǒng)中需要一個協(xié)調(diào)者，因此介紹了兩種協(xié)調(diào)者北京大學(xué)學(xué)士學(xué)位論文 一種支持動態(tài)可配置的高效組通信系統(tǒng)的設(shè)計與實現(xiàn) - 18 - 的算法： 法和環(huán)算法。 北京大學(xué)學(xué)士學(xué)位論文 一種支持動態(tài)可配置的高效組通信系統(tǒng)的設(shè)計與實現(xiàn) - 19 - 第三章 進(jìn)程組通信系統(tǒng)的設(shè)計 計