哪種列存格式適合平行計算?

大資料量時,硬碟掃描和讀取的時間佔比很大。採用列式儲存,在總列數很多而計算涉及的列很少時,只要讀取需要的列即可,能夠減少硬碟訪問量,提高效能。事實上,很多資料倉庫產品都採用了列式儲存。

但是,資料按列儲存,做多執行緒平行計算時會出現分段同步性問題。分段是平行計算的前提,行存分段比較簡單,按資料量大體平均分段,再找記錄結束標記確定分段點位置就可以。而列存不能採用同樣的辦法。由於列存的不同列是分別儲存的,也必須分別分段,又因為不定長欄位和壓縮資料的存在,各個列相同的分段點位置不一定會落在同一條記錄上,會錯位導致讀取錯誤。

業界普遍採用分塊列存方案解決分段同步性問題:塊內資料用列式儲存,分段必須以塊為單位,在塊內不再分段並行。這樣會出現一個矛盾:如果分塊數太少,就無法做到靈活分段,而均勻、靈活的分段是決定平行計算效能的關鍵;如果分塊數很多,列資料在物理上會被拆成很多不連續的小塊,會多讀入分塊之間的少量無用資料,考慮機械硬碟的尋道時間,分塊數越多這些問題越嚴重。很多資料倉庫或大資料平臺都無法解決這個矛盾,很難充分利用平行計算的效能。

開源的集算器 SPL 研發了創新的倍增分段技術,並在其組表列存中實現,解決了上述矛盾,這樣就可以充分利用平行計算來提高效能了。

倍增分段是將固定(物理)分塊改為動態(邏輯)分塊。具體做法是:為每列資料建立確定大小(例如 1024 個索引位)的索引區,每個索引位儲存一條記錄的起始位置,相當於一條記錄為一塊。追加記錄到索引位填滿後,重寫索引區,丟棄偶數索引位,奇數位向前移動,空出索引區後一半位置。相當於將分塊數縮減為 512 個,兩條記錄為一塊。依次類推,重複追加資料、填滿、重寫索引區的過程。隨著資料量的增加,塊的大小(塊內記錄數)不斷翻倍。所有列的索引區要同步填充,且填滿後同步重寫,始終保持一致。倍增分段實質上是以記錄數作為分段依據的,而不是位元組數,所以可以保證各個列即使分別分段也是同步的,不會出現錯位的情況。

以動態塊為單位分段時,塊個數保持在 512 到 1024 之間(記錄數小於 512 除外),可以滿足分段靈活的要求。各列的動態塊對應記錄數完全相同,也可以滿足分段均勻的要求。資料量無論大小,都可以獲得良好的分段效果。

SPL 組表會預設支援倍增分段方案,生成這種分段的列存資料非常簡單:

file(“T。ctx”)。create(…)。append(cs)

基於列存的多執行緒並行程式碼也很簡單:

=file(“T。ctx”)。open()。cursor@m(f1,amt1)。groups(f1;sum(amt1)) 開啟列存資料後,建立多執行緒遊標,做並行分組彙總。

更詳細的原理講解參見這裡:倍增分段,組表與列存(底部原文中檢視連結)

開源SPL討論