[OSDI 2016'] Fast and Concurrent RDF Queries with RDMA-based Distributed Graph Exploration

文章概況

這篇文章是OSDI16年的文章，作者來自上海交通大學的IPADS小組。

1. motivation

基於大規模RDF的計算query請求的性能差，之前的系統每個請求的延遲高，並且大部分之前的設計的資源利用率不高，這樣每個請求都是被順序處理。

2. innovation

這篇文章對於RDF圖數據的存儲和處理的優化是多方面的，對圖數據的存儲模型，索引方式，數據分布，處理模式，負載均衡四個方面進行了優化。

主要目標是利用基於RDMA的圖搜索來提供在大數據集上的高並發和低延遲query。

具體做了以下幾件事情

• 1. 針對檢索對RDF加入了新的索引節點種類，對RDF三元組中的謂詞進行了兩種索引，分別是謂詞索引和類型索引。
• 2. 使用了對RDMA友好的「differentiated編碼劃分策略[1]」來減少RDMA傳輸。先用differentiated編碼對普通頂點和索引頂點分開存儲，然後實現在各個主機上複製索引節點，而只劃分普通節點的策略。
• 3. 在query請求處理時，為了降低最後join操作的開銷，在每一步子檢索操作中都帶入了過去檢索得到的歷史
• 4. 對於在RDF圖進行query的時候，面臨了何時應當遷移執行進程，何時應當遷移數據的選擇，本文對這個的選擇是根據要取的頂點數據量決定的，如果要取的數據量大，那就遷移執行，如果要取的數據量小，那就在本地完成執行。
• 5. 由於每個請求不可避免的延遲不同，為了避免請求之間的干擾，為了防止長時間執行的query霸佔工作線程阻塞後續query的完成，造成延遲大，本文的worker可以操作和它相鄰的幾個工作進程，如果一個worker在執行一個長時間執行的進程，可以把後續的進程交給他操作的工作進程進行執行。

3. implementation

略

概念

RDF

Resource Description Framework是一種格式，每一個數據集被表示為<主語，謂語，賓語>，所有的節點構成了一個有向的帶標記的圖。例如google的 Google』s knowledge graph和facebook的social graph。

推薦閱讀：