前期知識準備
一、分布式架構
- 組件：四層。從上到下為：計算層——>Communication layer——>分布式文件存儲——>本地磁盤
A. 計算層： 從存儲中加載圖數(shù)據(jù)并執(zhí)行實際的計算，是和用戶交互的一層，這一層其實也就是指程序員編寫的程序。
B. Communication layer：雷同API，向計算層提供簡潔的接口
C. 分布式文件存儲：存儲著圖數(shù)據(jù)和分析的結果。 - 圖分割：利用頂點ID來劃分?？苫趇d(v)的哈希值、范圍，或者子圖進行分割。
- 同步與異步：同步執(zhí)行具有確定性，易于分析和調(diào)試，并且避免了競爭狀況以及鎖定/解鎖成本；異步執(zhí)行允許那些緩慢收斂（或快速收斂）的頂點運行更多輪次，從而更高效。
Vertex-centric 模型（Pregel-like）
一、 Computation and Programming Model
- 哈希分配，每個頂點維護其鄰接表、頂點值和活動標志。
- 超級步中，每個頂點只給自己的鄰接點發(fā)送消息。
（一個典型的Pregel計算過程如下：讀取輸入，初始化該圖，當圖被初始化好后，運行一系列的supersteps，每一次superstep都在全局的角度上獨立運行，直到整個計算結束，輸出結果。） - 基于消息傳遞（另一種是 共享內(nèi)存）
二、Optimizations in Communication Mechanism（通信機制的優(yōu)化）
- Pregel+： （1） 在高度數(shù)頂點的所有鄰居工作站中，建立其狀態(tài)鏡像，以減少消息傳遞；
（2）將每個worker的所有請求合并為一個r請求，而r只響應每個請求的工作者而不是每個請求頂點。 - GPS
- MOCgraph：采取message online computing (MOC) 模型，直接接受數(shù)據(jù)而不經(jīng)過buffer
三、Load balance（負載均衡）
————超級步中發(fā)送消息的頂點叫做工作窗口，又叫wind
- Vertex migration（頂點遷移）：在計算中把頂點從高工作量的工作站遷往輕量工作站，但難以獲取wind，且哈希值難改，工作量大
?。?）Lookup Table存儲Hash map。
?。?）GPS記錄每個頂點的地理位置，但不推薦使用。 - Dynamic Concurrency Control（動態(tài)并發(fā)控制）：PAGE系統(tǒng)測量消息產(chǎn)生速度、本地和遠程消息各自的處理速度，從而動態(tài)地調(diào)整處理本地消息和遠程消息的線程數(shù)。
四、Out-of-core Execution（核外執(zhí)行）
GraphD：工作站與消息傳輸并行地存儲磁盤駐留數(shù)據(jù)（例如，邊緣和消息），則在網(wǎng)絡通信的時間內(nèi)可同時實現(xiàn)磁盤流傳輸。
減少內(nèi)存占用，降低各類成本消耗。 只需要O(|V|)的內(nèi)存
- Distributed Semi-Streaming Model（DSS）：每個工作站在主存中只存儲其頂點的信息，鄰接表存儲在本地磁盤文件中，表示為SE（上角標）。在對每個頂點v調(diào)用compurt()函數(shù)時，需要從SE中讀其鄰接頂點及其度數(shù)。
為了只讀活躍頂點的鄰接列表，從SE中只發(fā)送頂點的存儲位置，看其與內(nèi)存中活躍頂點是否一致，否則就填充新的
- Message Streams（消息流）：每個工作站W(wǎng)i都持有|W|條發(fā)出的消息流S1~S|w|。若Wi中的頂點欲發(fā)消息給Wj中的頂點，則將消息附在Wi的消息流Sj中。
為并行執(zhí)行，Si被分成了多個文件：
（1）. 若Si寫的文件尺寸已達閾值，則新建文件；
（2）. 發(fā)送線程(sending thread持續(xù)探索所有消息流，一旦發(fā)現(xiàn)有沒發(fā)送的Si則執(zhí)行消息融合并發(fā)送。
GraphD中消息流先存儲在本地，再由發(fā)送線程加載，因為消息生成速度遠快于發(fā)送速度。若全存在內(nèi)存等待發(fā)送，可能導致計算死機。
?。。⊥獯娴?strong>join、group by操作是沒有必要的。
五、Fault Tolerance（容錯機制）
checkpoint：檢查點
- ChandyLamport snapshot：為異步消息傳遞系統(tǒng)設計的不協(xié)調(diào)的檢查點協(xié)議
- Recovery by Message-Logging：讓每個頂點發(fā)送消息之前在本地磁盤記錄其日志信息。在恢復期間，只需要重傳目標為重新分配的頂點的消息。
（1）. 幸存頂點只向重新分配的頂點發(fā)送日志消息；
（2）. 重新分配的頂點執(zhí)行自己的計算并記錄下所有消息日志，同時只向其他重新分配的頂點發(fā)送日志信息。 - Lightweight Checkpointing：之存儲狀態(tài)，不存儲發(fā)送消息(out-going message)，在恢復故障時，頂點僅從檢查點加載之前的狀態(tài)，然后從這個狀態(tài)生成發(fā)送消息。
