【正文】 計算密集 構(gòu)件化 構(gòu)件化 過濾挖掘 文件系統(tǒng) 即時消息 共享應(yīng)用 游戲 2022/6/3 李之棠 HUST 23 可并行化 P2P應(yīng)用 ?計算密集型：把一個大的任務(wù)分解成許多可在大量獨立對等端省并行執(zhí)行的子任務(wù)。如 CPU處理能力 ， 帶寬 ， 能量 和 磁盤空間 等等 2022/6/3 李之棠 HUST 35 可靠性 ?P2P系統(tǒng)中 困難的問題 – 固有的分布式特點使保障可靠性很困難 ?通常解是： 冗余 – 計算密集模式中，當(dāng)檢測到某機(jī)失效，則該任務(wù)可 啟動其它可用計算機(jī) – 相同的任務(wù)可分配到 多個 Peers上 – 在文件共享系統(tǒng)，可在許多 Peers上 部署重復(fù)DB – 丟失的消息可 重發(fā) 或沿著 多個通路同時 發(fā)送 2022/6/3 李之棠 HUST 36 類說明 ?兩類構(gòu)件 – 前面所討論的構(gòu)件是 可應(yīng)用 到 P2P結(jié)構(gòu) – 應(yīng)用類說明是構(gòu)件每類 P2P應(yīng)用的 功能抽象 或概要 ?類說明 – 調(diào)度：應(yīng)用于可并行化或計算密集類（任務(wù)分塊調(diào)度給Peers） – 元數(shù)據(jù)：應(yīng)用于內(nèi)容和文件管理，描述存儲在各 Peers上的內(nèi)容，并可被查閱以決定所求信息的位置 – 消息：應(yīng)用于協(xié)同，在各 Peers間發(fā)送以完成通信 – 管理：支持先行 P2P基礎(chǔ)設(shè)施的管理 2022/6/3 李之棠 HUST 37 應(yīng)用說明 ?構(gòu)成與功能 – 工具、例程和服務(wù) – 詳細(xì)描述應(yīng)用，以協(xié)調(diào)現(xiàn)行 P2P設(shè)施上的某些應(yīng)用 ?適應(yīng)于 – 分布式調(diào)度（科學(xué)、金融、生物計算） – 內(nèi)容和文件共享（音樂 MP3文件交換） – 運(yùn)行在協(xié)同和通信系統(tǒng)上面的特別應(yīng)用，如日歷、筆記、消息和聊天 2022/6/3 李之棠 HUST 38 模式與算法 ?集中目錄模式 – 最流行， Napster使用 – 群組的 Peers連接到發(fā)布其能提供共享內(nèi)容的中心目錄上，匹配請求與索引 – 文件直接交換在兩個 Peers間進(jìn)行 – 需要一些可管理的設(shè)施（目錄服務(wù)器：記載群組所有參加者的信息） – 限制了規(guī)模的擴(kuò)大：大量用戶增加－ 大量請求 大服務(wù)器 存儲器 – 然 Napster經(jīng)驗表明 ,除開法律問題外 ,該模式還很有效和強(qiáng)大 Index 1 2 3 5 4 搜索 下載 2022/6/3 李之棠 HUST 39 Napster原理 I have X! Publish insert(X, ) ... 2022/6/3 李之棠 HUST 40 Napster原理 Where is file A? Query Reply search(A) Fetch 2022/6/3 李之棠 HUST 41 洪泛請求模式 ?過程 – 每個 Peer的請求直接廣播到連接的 Peers – 各 Peers又廣播到各自的 Peers – 直到收到應(yīng)答或 達(dá)到最大洪泛步數(shù) (典型 59) ?特點 – 無廣告性共享資源 – Gnutella 使用該算法 ,限于公司內(nèi)通信有效 – 大量請求占用網(wǎng)絡(luò)帶寬 ,可擴(kuò)展性并不一定最好 ?改進(jìn) – Kazaa 設(shè)立 SuperPeer客戶軟件 ,以集中大量請求 – BT 文件分塊 – Cache最近請求 1 2 3 5 4 搜索 下載 6 2022/6/3 李之棠 HUST 42 Gnutella原理 I have file A. I have file A. Where is file A? Query Reply 2022/6/3 李之棠 HUST 43 KaZaA原理 I have X! Publish insert(X, ) ... 2022/6/3 李之棠 HUST 44 KaZaA原理 Where is file A? Query search(A) search(A) Replies 2022/6/3 李之棠 HUST 45 BitTorrent原理 Tracker A D C B 2022/6/3 李之棠 HUST 46 BitTorrent原理 A C B D 2022/6/3 李之棠 HUST 47 文件路由模式 ?過程 – 每個網(wǎng)上 Peer分配一個隨機(jī) ID,并知道其他 Peers的給定號碼 – 當(dāng)共享文件發(fā)布到系統(tǒng)上時 ,根據(jù)文件名字和內(nèi)容 Hash成為 ID – 每個 Peer將根據(jù) 該 ID向該文件路由 – 該過程重復(fù)執(zhí)行 ,直到最近的 PeerID是現(xiàn)行 Peer的 ID – 每個路由操作還 保持文件副本在本地 – 當(dāng) Peer請求某文件時 ,該請求將 用該文件的 ID到達(dá) Peer,過程重復(fù)直到發(fā)現(xiàn)文件副本 ,最終文件下載到請求源端 2022/6/3 李之棠 HUST 48 4個算法實現(xiàn)文件路由 ?Chord/CAN/Tapestry/Pastry ?目標(biāo)相同 – 減少 路由到指定文件的 P2P跳數(shù) – 減少 每個 Peer必須保持的 路由狀態(tài) ?算法異同 – 都保證算法的跳數(shù)與 Peer群組的大小相關(guān) – 或都指出算法能以高概率完成 – 方法上的差別很小 2022/6/3 李之棠 HUST 49 ?Chord – 每個 Peer保持 LogN其他 Peer的蹤跡 (N是群組的全部 Peer數(shù) ) – 當(dāng) Peer加入或離開時 ,高優(yōu)化算法版本僅需關(guān)注LogN個 Peers的變化 ?CAN – 每個 Peer保持 少于 LogN個其他 Peers的蹤跡 – 在插入和刪除時僅這些 Peers受影響 – 其路由表較小 ,但到達(dá)的路徑較長 – 可能 更適合動態(tài)通信 ?Tapestry與 Pastry很相似 – 除減少跳數(shù)外 ,還積極削減每個 P2P跳上的時延 2022/6/3 李之棠 HUST 50 路由表 ?路由表內(nèi)容 – id－文件標(biāo)識符 – next_hop－存儲文件 id的另一個節(jié)點 – file－保存在本地的 id標(biāo)識文件 ?搜索過程 – 如果文件 id存儲在本地，停止搜索，上傳文件 – 如果不在本地， 搜索 路由表中 最接近的 id，將請求 轉(zhuǎn)到 next_hop – 如果所有節(jié)點都沒有找到，返回失敗，返回路由表 中下一個最接近的 id ID Next_hop file … 2022/6/3 李之棠 HUST 51 文件路由原理 4 n1 f4 12 n2 f12 5 n3 9 n3 f9 3 n1 f3 14 n4 f14 5 n3 14 n5 f14 13 n2 f13 3 n6 n1 n2 n3 n4 4 n1 f4 10 n5 f10 8 n6 n5 query(10) 1 2 4 4’ 5 ?網(wǎng)絡(luò)趨向于一個小世界－ small world,類似六度分隔（ Six Degrees of Separation）理論 ?因此，大部分查詢只需經(jīng)過少量跳數(shù) 2022/6/3 李之棠 HUST 52 Distributed Hash Table ?分布式數(shù)據(jù)結(jié)構(gòu)系統(tǒng)中，可以是環(huán)，樹，超立方體，跳表，蝶形網(wǎng)絡(luò) ... ?CFS, OceanStore, PAST, ChordDNS 分布式 Hash表 分布式應(yīng)用 get (key) data node node node …. put(key, data) 查找服務(wù) lookup(key) node IP address (文件共享 ) (DHash) (Chord) 2022/6/3 李之棠 HUST 53 ?結(jié)構(gòu)化 重疊路由 – 加入 ：開始時，聯(lián)系一個 “ bootstrap”節(jié)點，加入分布式數(shù)據(jù)結(jié)構(gòu)， 獲得一個節(jié)點 id – 發(fā)布 ：向數(shù)據(jù)結(jié)構(gòu)中最近的節(jié)點發(fā)布 文件 id的路由信息 – 搜索 ：向路由表中最近的節(jié)點查詢文件 id，數(shù)據(jù)結(jié)構(gòu)保證查詢會找到發(fā)布節(jié)點 – 獲取 ：兩個選項 ? 查詢到的節(jié)點保存有文件，則從查詢結(jié)束的節(jié)點獲取 ? 查詢到的節(jié)點返回結(jié)果：節(jié)點 x有文件，則從節(jié)點 x獲取 ?DHT示例－ Chord:在一維空間（環(huán)）中給每個節(jié)點和文件一個唯一的 id – 例如從 [0...2m]中選取 – 通常是文件和 IP地址的 hash 2022/6/3 李之棠 HUST 54 Chord：插入 N32 N90 N105 K80 K20 K5 Circular ID space Key 5 Node 105 2022/6/3 李之棠 HUST 55 Chord：查找 N32 N90 N105 N60 N10 N120 K80 “Where is key 80?” “N90 has K80” 2022/6/3 李之棠 HUST 56 4 P2P關(guān)鍵技術(shù)特性 非集中化 :置疑 C/S 模式 ?集中化 – 在訪問權(quán)限和安全上容易管理 – 但不可避免導(dǎo)致 :低效 /瓶頸 /資源浪費(fèi) – 盡管硬件性能和成本有了改進(jìn) ,但建立和維護(hù)集中化知識庫成本高昂 ,需要人員智能化地建立 ,保持信息的相關(guān)和更新 ?非集中化 :更強(qiáng)有力的思想 – 強(qiáng)調(diào)用戶端所有權(quán) ,對數(shù)據(jù)和資源的控制 – 每個 Peer都是平等的參與者 – 實現(xiàn)更困難 (無全局服務(wù)器 ,看不到全局 Peers及其文件 ) – 這也是當(dāng)前混合模式存在的原因 2022/6/3 李之棠 HUST 57 ?全非集中化文件系統(tǒng) (Gnutella Free) – 發(fā)現(xiàn)網(wǎng)絡(luò)是很困難的 – 新節(jié)點必須知道其他節(jié)點 – 或由主機(jī)列表知道其他 Peers的 IP地址 – 該節(jié)點通過和現(xiàn)行網(wǎng)絡(luò)中至少一個 Peer建立連接而加入網(wǎng)絡(luò) – 從而能發(fā)現(xiàn)其他 Peers并 Cache它們的 IP地址在本地 專用單服務(wù)器 (通過 Master) 混合 SETIhome Avaki 純 所有節(jié)點相同 超級 Peers/Masters 多個專用服務(wù)器 Kazaa Free Gnutella Napster 平臺 分布計算 協(xié)同通信 文件共享 非集中化程度 JXTA .NET 各種P2P系統(tǒng)按非集中化程度分類 2022/6/3 李之棠 HUST 58 可擴(kuò)展性 ?可擴(kuò)展性受限的主要原因 – 需要完成大量的集中化操作 :如同步與一致 – 需要維護(hù)許多狀態(tài) – 固有的并行性應(yīng)用展開 – 用來表示計算的編程模式 ?P2P解決可擴(kuò)展性問題 – Napster在其服務(wù)的高峰用戶達(dá)到 600萬 – 然 SETIhone2022年止用戶 僅接近 350萬 .因為它集中在并行度有限的任務(wù)上 ,依靠因特網(wǎng)上的可用計算力來分析從天文望遠(yuǎn)鏡收集來的數(shù)據(jù) ,搜索外星生命 – Avaki通過提供分布式對象模型來解決可擴(kuò)展性問題 2022/6/3 李之棠