cover

前言

本篇繼續探討 Design Data-Intensive Application 這本書的第三章：Storage and Retrieval

簡單整理一下本小節主要談論的架構：

  • OLTP(Transaction)
    • Row-orient storage
    • Database engine
      • Log-structure -> ex: LSM, SSTable, Lucene…
      • page-orient(B tree) -> some RDBMs and NoSQL
  • OLAP(Analytic)
    • data warehouse(ETL)
    • Column-orient storage
      • bitmap encoding
      • run-length encoding
    • Column Families(Cassandra)

今天這篇主要要談論的是 OLAP 的部分

OLTP vs OLAP

兩者比較的關鍵是

事務處理(Transaction)還是分析(Analytic)？

OLTP(OnLine Transaction Processing)

以往來說，資料庫交互都圍繞在商業交易這類跟錢相關的交易(commercial transcation)，當應用拓展到不同領域後，漸漸已經跟錢無關，最後就剩下保留 交易/事務(transcation) 這個術語與概念，用於描述一組讀寫操作的邏輯單元

使用上，應用程式會需要透過索引(index)的方式查找某個鍵值對應的少量資料，依據 user 的 input(insert, update, delete)來更新紀錄

這種交互式的方式關心的是能否快速的回應 user 的 query 或 insert，在大量負載時能降低操作時的延遲，所以 disk search time 會是瓶頸，而 OLTP 應付的資料量相對於 OLAP 來說更少，也比較關心的是即時的資料．

OLAP(OnLine Analytic Processing)

OLAP 常見的 user 是商業分析師，他們不會只關心少量的數據，而是聚集(aggregate)各種領域的歷史資料，作為統計、歸納、分析等等的決策目標，也因此 OLAP 的資料庫關心的不是延遲，而是如何在查詢量變大時，解決昂貴查詢成本帶來的 disk bandwith 瓶頸

The disk bandwidth is the total number of bytes transferred, divided by the total time between the first request for service and the completion of the last transfer.

而 OLAP 在查詢資料時，常常僅關心某個 column 的聚合表現(ex: max, sum, count…)，而非在意整筆 row 的資料，所以相對於 row-orient storage 的儲存引擎，OLAP 更適合 column-orient storage 的儲存引擎

舉例來說，上面是 row-orient storage，底下是 column-orient storage，值得注意的是下面是依據不同 column 來查找資料，不需要查詢不考慮的欄位

column_orient_storage

bitmap encoding

為了降低硬碟吞吐量，column-orient storage 還可以再進行壓縮，使用bitmap encoding，將每個 column 內的值都用 0, 1 來表示其存在的位置，概念有點類似 onehot encoding，如下圖所示

bitmap

這時搜尋底下語句就可以用 bitwise 的方式來計算，速度會較快

WHERE product_sk IN（30，68，69）

run-length encoding

除此之外，當 column 內的 distinct 值較少時，組建的 bitmap 會較稀疏(sparse)，可以再用 Run-length encoding 來描述幾個 0 幾個 1，達到無損壓縮的目的

總結來說，OLTP 和 OLAP 的比較可見下表

OLTP_vs_OLAP

Why data warehouse?

起初 OLTP 和 OLAP 都是使用同一個資料庫，但後來企業漸漸停止在 OLTP 的資料庫上做分析，原因跟上述提到的有關，分析師所查詢的語句往往是非常昂貴，在 end user 使用時造成的大量負載下還要應付這種昂貴查詢會犧牲掉部分的 performance，拉垮高可用、低延遲的效能，所以最後演變成在單獨的資料庫上分析，這種單獨的資料庫就被稱為數據倉庫(data warehouse)

end user 操作的資料庫屬於 OLTP，需具備高可用與低延遲的需求，而商業分析師為了統計目的的搜尋對象則是 OLAP 的資料庫，當架構上有多種 OLTP 資料庫時，系統規劃上會定期從 OLTP 的資料庫上透過 ETL 方式將轉置後的資料存入另一個專門分析的資料庫，如下圖所示

ETL

Column-orient storage vs Column families

此外，書中在談到 Column-orient storage 時特別提到 Column families，Column families 與 Column-orient storage 的儲存方式不同，Column families 是具有 row key，這個 row key 對應到一組 columns，所以儲存方式仍然屬於 Row-orient storage，而 Cassandra and HBase 就是採用 column families 的方式來儲存

super-column-family

Read/Write Performance of Column-orient storage

最後來探討一下 Column-orient storage 的寫入和讀取效能

OLAP 因為是分析聚合的用途，常常伴隨著有多個 column 需要聚合，所以會選用 Column-orient storage 更為適合，而靜態數據的分析與統計往往是複雜且成本昂貴的搜尋語句，再加上寫入的需求不大，就算有也是批次的寫入，所以整體來說屬於讀多寫少的情境

讀取的時候，雖然 B-tree 實作的結構適合 read-heavy，但就地 replae 的方式極有可能在寫入一筆新 row 資料時，不得不重寫(rewrite)所有的 column 資料，再加上 Column-orient storage 透過壓縮(compression)與排序(sort)後已能滿足快速查詢的需求，所以 Column-orient storage 不太會採用 B-tree 的結構，反而會採用適合範圍搜尋的 LSM 樹

寫入的時候，OLAP 的情境常常是批次寫入，所以 LSM 樹的批量處理與壓縮技術就很適合解決這種需求，所有的寫入都先進入一個 in-memory 的 store，無需考慮這是 row-orient 或是 column-orient，直到累積夠多的寫入資料後，就會與 disk 上的 column files 做 merge，並 batch 寫入 disk

總結

結合這篇與上篇的結論，第三章可以歸納出以下重點

  • B-tree 是 read-heavy，LSM 樹是 write-heavy
    • 因為 B-tree 是平衡樹，讀取寫入都很穩定
    • LSM 樹讀取較弱，因為需要遍歷多個 disk 的 block 來查找，寫入效能較強是因為寫入內存再定期批次的寫入 disk
    • 常見的 RDBMs 和部分 NoSQL 是 B-tree 實作，Cassandra 是 LSM 樹實作(所以 Cassandra 適合大量寫入和較少讀取的情境)
  • OLTP 的情境是高併發、低延遲的事務處理，對於讀寫的要求較高，適合 B-Tree
    • 大多採取 B-tree 這種讀寫穩定的索引結構，少部分遇到需要大量寫入的情境時再考慮 LSM 樹
  • OLAP 的情境是大規模的數據分析與統計，要求上讀取大於寫入，因為 OLAP 的一些特性所以適合 LSM 樹
    • 雖然 B-tree 是 read heavy，但因為 LSM 樹有壓縮技術能夠降低 disk 空間，而 B-tree 讀取大量 column 資料時會因為數據就地更新的方式造成整體讀取效能沒有 LSM 樹來的好
    • 寫入本就是 LSM 樹的強項，非常適合需要批量寫入的 OLAP