論文閱讀筆記- Dremel

作者：劉旭晖 Raymond 轉載請注明出處

Email：colorant at 163.com

BLOG：http://blog.csdn.net/colorant/

更多論文閱讀筆記 http://blog.csdn.net/colorant/article/details/8256145

閱讀筆記 -  Dremel: Interactive Analysis ofWebScaleDatasets

關鍵字

列存儲

== 目标問題 ==

在大規模的稀疏型結構化資料上的快速互動式Ad-hoc查詢

== 核心思想 ==

首先Dremel面向使用者提供了一個類SQL文法的查詢語言，但更重要的是它對嵌套式的結構化資料的處理方式

• 使用特定結構的Column Base的存儲方案，用一個三元組表示一個資料單元，這個三元組包含了這個資料單元的值，以及它在嵌套的資料結構中的層級和重複級别。結合與資料表關聯的Schema定義，可以高效的表達出該資料單元在整個資料結構中的實際存儲情況，具體細節請參考論文相關章節。

• 在這種存儲方案下，結合巧妙的算法strip部分空資料，在資料稀疏的情況下
  • 能對資料采用更簡單的壓縮算法
  • 能減少實際存儲的資料量
  • 針對Column結構優化的檢索，在無需重構資料的前提下能夠實作快速檢索
  • 在隻檢索部分域的情況下，因為按需讀取（同時巧妙的算法又能建構比全表掃描更簡單的掃描流程），能大量減少所需讀取的資料。

再有就是叢集節點的工作模型

• Serving Tree分層處理模型
  • 每個leaf節點隻處理少量的資料，結果分層彙總到上級節點，較少的層級拓撲對于通常的大量輸入/中少量輸出的檢索能有效處理，較多的層級拓撲則有利于處理大量輸出的情況。

總體上，個人了解 Dremel能在特定場合比Row base的MapReduce模式的應用快的原因，根本上來至于資料IO量的減少，輔助以大量葉結點的分層彙總結構來最大化并發處理資料。

== 實作 ==

Query Plan的執行不轉換成Map-Reduce任務，而是由Serving Tree模型自己處理。

在實作中，除了巧妙的算法實作Record和列式存儲模型的快速轉換外，還有各種優化，比如定義允許部分結果傳回時就提前結束查詢的Sample方式，犧牲适當的精度來換取速度等等

适用的場合應該是針對稀疏資料，對部分資料域進行ad-hoc類分析的場合

== 資料 ==

Paper測試的典型資料在20-100T之間，一行（也就是一個Record）包含的域在30-1200個左右，當所需查詢處理域在個位數的時候，提升的速度在3-10倍之間，基本上相當于所需讀取資料量的比值除2的樣子（比如相比完整的Row存儲結構，讀1/10的域，所花時間是1/5）

當所需處理的域增加到一定程度後，Row base的MR應用的速度則會反超（按Paper的說法，取決于具體的表的結構和稀疏程度，通常在幾十個（Dozens of）域（field）的情況下，速度對比會翻轉）

== 相關研究，項目等 ==

Apache Drill : http://incubator.apache.org/drill/ Dremel的開源實作版本，看起來還僅僅處于起步階段，計劃了很多功能，但是實作的并不多, 目前大概核心的代碼大概隻有 2K行左右的JAVA code

Open Dremel : 合并到Drill項目了