????????今天要講的文章是SOSP 2017年的一篇文章，Wukong+S?：Sub-millisecond Stateful Stream Querying over Fast-evolving Linked Data。本文主要解決的問題是：隨著流數據和存儲數據量的不斷增加，及時查詢有用的信息十分重要。對于公共數據集合數據流，可能有大量的用戶不同的數據流查詢請求，因此需要支持高并發的查詢。而且流數據通常包含巨大的有用信息， 這樣的數據應該被一致地和立即地整合到存儲系統，以用于將來的連續查詢。

????????然而目前現有的系統對于正在變化的數據集的側重點在于流計算。流計算和流查詢不同的是 前者通常傾向于對大部分流數據進行序列化計算，而后者側重于對流和存儲數據的特定集合的并發查詢。大多數先前的系統也沒有集成流數據為了并發的查詢中，或者不查詢持久化存儲的歷史數據來獲得基礎知識，因此是無狀態的。 盡管大多數流處理數據庫都明確支持語義和SQL接口，但是他們在快速演化的Linked 數據下，當面臨大量并發的查詢請求下，由于高昂的Join操作開銷和一些ACID的語義，他們的查詢性能是低效的。

????????Wukong+S為了尊重數據本地化并最大限度地減少數據傳輸，它使用由基于時間的臨時存儲和連續持久化存儲組成的混合存儲，為正在到來的數據和持久化的數據提供不同的存儲管理。Wukong + S提供了流數據的快速訪問流索引。流數據通過局部感知分區進行分片，其中一些流索引在節點間動態復制。這節省了查詢成本并提供高效的負載平衡。為了在多個不同規模的流數據上提供一致的流查詢，Wukong + S使用分散的矢量時間戳來推導出最近一致性狀態的流式數據插入。Wukong + S使用有限的標量化方案將矢量時間戳投影到標量快照數量中，通過協調多個流的更新到底層持久存儲區。這樣的設計在有效的內存使用情況下擴展了Wukong + S節點和大量查詢。

1. RDF and SPARQL?

????????那么什么是RDF數據呢？RDF全稱就是資源描述框架。他將我們生活中的描述成每一個實體和實體之間的關系。每一個實體就是圖中的一個頂點，相鄰頂點的邊就是兩個實體之間的關系。他通過一組基于主題、謂詞、對象的三元組集合 來描述現實生活中的資源。

2. BackGround

????????在我們生活中，每時每刻都在產生著大量的數據。不同的數據源高速不斷地生成實時流數據。比如說社交網絡數據、城市監控數據、視頻圖像數據。

????????在各種各樣的應用場景下，產生的大數據主要可以分為以下兩類。一類是實時流數據：這樣的數據是非常快速的產生。一類是存儲數據：也就是歷史數據（存在的有價值的歷史數據），這些數據是非常巨大的并且它由于stremdata，它還會不斷演化。????????

????????然而對于社交網絡，城市監控和市場反饋等應用需要有狀態的流式查詢，狀態流查詢不僅要查詢存儲歷史數據，也要從實時流數據從提出有用的信息，查詢實時流數據。實時流數據提取的有用信息，也需要持續不斷地整合到存儲的數據中，以便為上述和未來提供查詢服務。 然而目前現有的系統對于正在變化的數據集的側重點在于流計算。流計算和流查詢不同的是 前者通常傾向于對大部分流數據進行序列化計算，而后者側重于對流和存儲數據的特定集合的并發查詢。大多數先前的系統也沒有集成流數據為了并發的查詢中，比如關系型數據庫，或者不查詢持久化存儲的歷史數據來獲得基礎知識，因此是無狀態的。

3.Example Dataset for Stateful Stream Query

我們來舉一個簡單的狀態流查詢的實例。

????????LinkeData 表示就是實體和實體之間的關系信息，存儲的靜態數據。假設目前存在這樣一個查詢需求：在過去30分鐘內，哪些IPADS 成員發布了一個推文。這個推文被其他IPADS的成員點贊了。當這個查詢請求被用戶提交后，這個查詢請求將不斷在后臺服務器中計算，并且不斷地產生查詢結果。直到這個查詢請求被用戶取消。

????????我們仔細分析上面的Example，可以得出這樣的一個抽象的系統。在這樣的一個系統中，存在著連接屬性圖數據。狀態流查詢不僅讀取Store數據還讀取實時流數據。并且這個存儲的數據還是隨著時間不斷演化的，它會從實時流數據中吸收永恒的數據。

4.?Conventional Approach

????????傳統的解決方案是將實時流處理系統和圖儲存系統相結合。一次性查詢任務直接被發送到Graph Store System 中，直接查詢歷史存儲數據。而連續查詢將被拆分成分別在流處理系統中和面向查詢為主的圖處理系統兩部分分別執行。這兩部分的結果將被join連接起來以得到最終結果。然而這樣的混合設計仍然不全是狀態查詢。因為一次性查詢只會運行在靜態的存儲數據中而沒有從實時流數據得到更新后的實時數據。除此之外，這里還存在一些關鍵性的缺陷。

????????由于目前存在的CSPARQL-engine運行在單機節點中。作者將Wukong（分布式RDF圖存儲數據庫）與Apache Storm（高吞吐量低延遲的實時流處理系統相結合）。

????????作者通過實驗發現通過將實時流處理系統和圖處理系統簡單組合存在高延遲、低吞吐量的問題。主要是由于以下的這幾個原因：
1. 首先，它存在跨系統的開銷。因為它是將實時流處理系統和圖儲存系統簡單結合，在二個不同系統之間存在數據轉換和數據傳輸的開銷。

2. 其次，為了降低跨系統執行的次數，組合設計會改變查詢計劃。通過改變查詢條件的執行順序，Strom首先將兩個實時流數據進行join，得到一部分中間結果。然后將這個中間結果發送到Wukong中去，Wukong進行檢索，最終得到查詢結果。然而，對于兩個實時流數據進行join操作，這通常會造成巨大的冗余數據和時間開銷。

5. System? Desgin

????????Wukong + S使用一種新穎的集成設計，用于快速演化的鏈接數據的狀態流查詢。Wukong+S在一個系統中管理實時流數據和靜態歷史數據。如何正常整合實時流數據和存儲的數據？永恒持久化的數據和時效性很強的數據。

????????為了保證一次性查詢，它既查詢存儲數據，也可以對實數流數據吸收其中永恒數據。Wukong+S提出了一個集中化的設計，在這個設計中數據被分成兩個類型。一種是永恒持久化的數據，他被存儲在Continuos Persisten Store這樣的一個結構中它還會不斷地從實時流數據中提取一些永恒可以用來持久化的數據（比如Like流和Tweet流）。還有一種數據是Timing data 瞬時實時的數據。這種數據和時間關聯性很大，比如一些GPS 地理位置數據。一次性查詢直接查詢永恒的數據，因為這種查詢不關心實時性的數據。持久化的查詢會不斷地從Timing Data以及Timeless Data中查詢結果。

????????流處理系統首先由用戶定義的謂語。將實時流數據分成兩類分別是Timing數據和Timeless數據。Timeless數據被底層數據存儲吸收寫入到服務器引擎的持久化存儲中。Timing數據被存儲在Time-based transient store存儲中。

5.1 Hybrid Store

????? ? Wukong+S 對于這樣的永恒持久化的數據和瞬時實時的數據采用一種混合存儲的策略。對于這種永恒持久化的數據，Wukong+S采用一種Continuous Persistent Store的結構。持續持久化存儲不斷從實時流數據中吸收永恒持久化的數據。他的設計目標就是支持持續的狀態流查詢和最新的一次性查詢。

????????對于這種瞬時實時的數據，Wukong+S采用一種Time-based Transient 存儲（基于時間的瞬時存儲）。瞬時數據只會在一個時間間隔內被相關的連續查詢請求訪問。它的設計目標是：對于一部分瞬時的數據流，它能夠支持快速垃圾收集(GC)。定期掃除過期的瞬時數據。

具體的細節設計如下圖所示：

使用混合存儲來存儲實時流數據和永恒持久化數據，存在以下兩點優點：
1.在實時數據和永恒數據之間不存在互相干擾。
2.由于設計數據存儲分開來存儲，我們可以針對不同的操作模式進行優化。

對于永恒持久化數據采用continuous persistent store 對于實時Timed數據采用time-based transient store。

6. Wukong+S Architecture

????????數據是被分區存儲在多個服務器上的。每個服務器引擎都可以提供狀態流查詢功能和支持數據被分區存儲功能。

6.1 Stream Index? ??????

????????那么如何在一定的時間間隔內快速訪問持續持久化存儲？Wukong+S提供了Strem Index機制，方便查詢根據時間戳快速定位到相應的KV-Strore相應的存儲中。

????? ? Wukong+S采用Stream Index機制，方便查詢根據時間戳快速定為到相應的KV-Store相應的存儲中。

6.2 Locality-aware partitioning

????????分區存儲流索引的一般方法是將流索引和數據一起放置存儲，這可以為連續查詢提供數據局部性。然而，這種分區策略會造成連續查詢的執行被拆分成多個節點，即遷移執行。然而同實驗表明：這種遷移執行的方式，會造成嚴重額的網絡傳輸的開銷以及額外的調度延遲。Wukong+S考慮到索引大小一般都比較小，連續流查詢可以從遠程的節點中抓取數據，并且在一個機器上執行查詢任務。這種策略叫做遷移數據。連續流查詢還需要將Stream Index復制到執行持續性查詢任務的機器上去，這樣執行查詢任務的機器可以通過Stream Index快速訪問到流數據。

7 Consistent Data Snapshot

????????Wukong+S設計用于處理大量的查詢請求。在分布式系統的實現中，面對大量的并發查詢請求的時候，以及不斷演化的Liked數據的時候，如何去提供一個一致性查詢視圖成為一個重要的挑戰。

7.1 Decentralized Vector Timestamp （VTS）

Wukong+S 針對持續的查詢工作，提出了一個向量時間戳的解決方案。

????? ? 因為不同的服務器執行實時流數據插入的速度不一樣，導致系統在執行RDF查詢的時候。系統要給出一個整個集群插入數據的一致性視圖。VTS：就是用來做這個工作的，首先每個服務器都有一個本地Local_VTS,用來標識本地服務器已經插入批次的位置。然后每個服務器將自己本地的Local_VTS發送給Master協調器Coordinator，協調器Coordinator維持一個Stable_VTS服務器用來保存全局信息。這個全局信息可以用來進行Continous Query操作。

7.2 Bounded Snapshot Scalarization

????????VTS的這種解決方案要求與矢量時間戳相關聯的值中的所有流數據，由于大量的Key/Value鍵值對造成大量內存的開銷，并且無邊界的數據流還會造成大量的資源浪費。因此Wukong+S提出了一種Bounded Snapshot Scalarization的解決方案。

????????Wukong + S通過將矢量時間戳（VTS）轉換為標量快照編號（SN）來解決此問題。 首先，協調員將預先公布快照號（SN）與矢量時間戳（VTS）范圍之間的映射計劃（即，SN-VTS計劃），其次，每個節點上的工作進程確保所有流批次與相同的快照號碼（SN）連續存儲在鍵/值對中; 以這種方式，每個鍵的快照僅與一個存儲間隔相關聯。 最后，每個查詢將獲得穩定的快照編號（Sta ble_SN）而不是Stable_VTS，并使用它從持久性存儲中讀取一致的快照。

8.Evaluation

8. Conclusion

????? ? Wukong+S提出了一種分布式流查詢引擎采用新型集成設計，實現快速演進鏈接數據的狀態流查詢。實現超過每秒100萬次查詢的亞毫秒延遲和吞吐量。

總結

以上是生活随笔為你收集整理的[SOSP 17] Wukong+S : 不断演化的RDF数据的亚毫秒级别的状态流查询的全部內容，希望文章能夠幫你解決所遇到的問題。

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