????????今天要講的文章是OSDI 2016年的一篇文章，Fast and Concurrent RDF Queries with RDMA-based Distributed Graph Exploration。RDF全稱是資源描述框架，RDF將現實生活中的關系描述成實體與實體之間的關系。這種實體與實體之間的關系可以用圖來描述。實體可以用頂點來描述，實體與實體之間的關系可以用邊來描述。

RDF圖Graph應用場景：

通過對大量且不斷增長的RDF數據進行大量查詢，RDF圖形存儲庫為并發查詢處理提供低延遲和高吞吐量勢在必行。
現有的工作存在的問題：
????????先前的系統在大數據集上仍然經歷高的查詢延遲，并且大多數先前的設計具有較差的資源利用率，使得每個查詢被順序地處理。查詢處理集中的依賴于潛在大表的連接操作，這通常會產生巨大的冗余中間數據。 此外，使用關系表triplets來存儲三元組可能會限制一般性，使得現有系統難以支持RDF數據的一般圖形查詢，如可達性分析和社區檢測。
現有的解決方案：
1.使用triple 存儲和 triple join方法
????????存在的問題：First,使用三元組存儲會過度依賴Join操作，特別是分布式環境下的merge/hash join操作。Second, scan-join操作會產生大量的中間冗余結果。Third, 盡管現有的工作使用redundant six primary SPO4 permutation index 可以加速join操作，但是索引會導致大量的內存開銷。
2.使用Graph store 和 Graph exploration

????????存在的問題：之前的工作表明，最后一步join相應的子查詢結果會造成一個潛在的性能瓶頸。特別是查詢那些存在環的語句，或者有很大的中間結果的情況下。

????? ? Wukong針對現有的系統存在的問題，提處理一個可以在查詢階段進行優化中間結果的基于RDMA-Based的RDF Query系統。

1. Graph Model And Graph Indexs

類型的索引結構。分在Wukong中這里有兩種不同別是 Predicate Index和Type Index索引。、

????????Wukong提出了謂詞索引（P-idx）來維護所有使用其特定謂詞標記的主體和對象入邊和出邊。索引頂點本質上充當從謂詞到相應的主體或對象的倒排索引。Wukong還提出了一種Type Index索引方便查詢一個Subject屬于的類型。與先前基于圖的方法（使用單獨的數據結構管理索引）不同，Wukong將索引作為RDF圖的基本部分（頂點和邊）處理，同時還考慮了這些索引的分割和存儲。?好處：首先，這使用圖探索簡化了查詢處理，以便圖探索可以直接從索引頂點開始。 其次，這使得在多個服務器之間分配索引變得簡單而高效。

2.Differentiated Graph Partitioning

受到PowerLyra的啟發，Wukong采用不同的分區策略算法對于正常頂點和索引頂點來說。每個正常頂點（例如，DS）將被隨機分配（即，通過 散列頂點ID）到只有一個機器的所有邊緣（鄰居的ID）。與正常頂點不同的是，每個索引頂點（例如，takeCourse和Course）將被拆分并復制到多個機器，其邊緣鏈接到同一機器上的正常頂點。 這很自然地將索引和它們的負載分配給每臺機器。?

3.RDMA-friendly Predicate-based Store

Wukong采用一種基于RDMA-Based的分布式hash表結構存儲RDF Graph Data。在這樣的結構中，它包含兩種不同的索引結構，一種是Type-index索引，存儲Subject/Objetc的類型索引。一種是Predicate-Index索引，存儲的是謂詞的相鄰頂點的索引。

4. Processing Query

4.1 Basic Query Processing

????????Wukong利用圖探索通過沿著圖特別是根據子圖的每個邊。對于大多數情況下(謂詞通常是知道的恒定變量，然而subject/object是自由變量)，Wukong利用謂詞索引開始進行圖探索。對于那些查詢是一個子圖環的查詢，三個Subjet/Object都是自由變量。Wukong根據基于cost的方法和一些啟發式的選擇一個探索順序。對于一些罕見的情況，那些謂詞都是不知道的情況下，Wukong從一個靜態的(常量)的頂點進行圖形探索（通過pred 已知的頂點相關聯的謂詞）。

4.2 Full-history Pruning

????????在探索查詢的每一個階段中，通過RDMA READ讀取其他機器上的數據，進行裁剪。裁剪那些沒有必要的冗余數據。

4.3 Migrating Execution or Data

????????在探索查詢的每一個階段中，通過RDMA READ讀取其他機器上的數據，進行裁剪。裁剪那些沒有必要的冗余數據。對于一個查詢階段，如果有很少的頂點數據需要抓取從遠程機器中，Wukong 使用一個本地執行的模式同步利用單邊RDMA READ直接從遠程頂點抓取數據。對于一個查詢階段，如果許多頂點需要被抓取。Wuong 利用一個Fork-Join 執行模式異步的分開查詢計算到多個子查詢在遠程機器上。

4.4 Concurrent? Query Processing?

Work-obliger work 竊取算法
????????鄰近的Worker進程的查詢超時時間（s.end < now）。如果是這樣的話這個Worker可能在處理冗長的查詢，因此后續的查詢任務可能被延遲。在這種情況下，這個Worker從該Worker的工作對隊列中竊取一個查詢任務來處理。在逼迫相鄰的woker(知道看到一個不忙的Worker)，Worker 進程持續通過從其中自己的工作隊列中，持續處理自己的查詢。持續處理自己的查詢。

總結

以上是生活随笔為你收集整理的[OSDI 16] Wukong : 基于RDMA的高并发、快速的分布式RDF Graph Query系统的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。