---
tags: DDIA
---

# 資料倉儲

如何建立一個可供快速分析的資料庫。

[文本於此](https://evan361425.github.io/feedback/designing-data-intensive-applications/foundation-dw/)

note:
注意是分析，不是索引提到的搜尋。

----

複習一下

- 索引，根據鍵快速找到值
- 內存散列表
- 樹狀結構儲存
- 犧牲少量寫入，提升特定讀取

note:
簡而言之，當我們要找使用者 123，索引可以幫助我們快速找到。適用於小量的異動和讀取。

----

但是...

- 一月份收入總額？
- 今年成功應徵的人數？
- 哪種職類最多人應徵？

note:
但我們上次討論的索引方式好像都對上述問題沒什麼幫助？（都需要遍歷）

---

## 異動和分析

- 線上異動處理（OnLine Transaction Processing，OLTP）
- 更新我的自我介紹
- 查看新店區有什麼職缺
- 線上分析處理（OnLine Analytic Processing，OLAP）
- 一月份收入總額
- 哪種職類最多人應徵

note:
我們定義一下上面兩種搜尋的種類，方便之後討論。

線上異動處理

- 特定資料的讀寫
- 即時

> 早期資料庫的操作幾乎是商務交易，所以保留舊稱「交易」（transaction）。

線上分析處理

- 所有的資料做讀取

----

| 屬性 | 線上異動處理 | 線上分析處理 |
| ------ | ----------------------------- | ------------------------------ |
| 讀取 | 小量資料 | 聚合大量資料 |
| 寫入 | 低潛時，隨機寫入 | 一次性大量寫入，或透過事件流入 |
| 用於 | 線上使用者 | 後台分析 |
| 代表 | 最新狀態 | 事件的歷史紀錄 |
| 大小 | GB~TB | TB~PB |
| 注重於 | 磁碟中找尋的速度（seek time） | 磁碟中的頻寬（bandwidth） |

note:
在開始詳細介紹專門處理 OLAP 的資料庫之前，先來比較一下。

> 有時候並不是那麼清楚就可以區分

- 主要的讀取模式
- 小量資料，且透過鍵篩選
- 聚合（aggregate）大量資料
- 主要的寫入模式
- 低潛時（latency），且隨機寫入
- 一次性大量寫入，或透過事件流入
- 主要使用於
- 透過網路溝通的服務使用者
- 內部分析師，幫助決策
- 磁碟運算注重於
- 大量的請求會被需要處理，請求通常只會接觸資料庫中一部份資料。應用程式可能會透過索引來加速搜尋。
- 雖然請求量比 OLTP 低，但是每次請求可能都需要遍歷資料庫來取得特定分析結果（頻寬越高，拉取大資料效率越快）

---

### 磁碟和記憶體

| 飲水機 | 保溫瓶 |
|:---------------------------------------------------------------------------------------------------:|:------------------------------------------------------------------------------------------------------------------------------------------------------------------:|
|  |  |

// 從飲水機取水就好像：
function decoder(fileName) {
  const content = readFile(fileName);
  return JSON.parse(content);
}

note:
上次報告沒仔細提到什麼是磁碟（disk/filesystem），什麼是記憶體（memory），可以想像成飲水機和保溫瓶。

一個有非常大的空間儲水，但是離辦公室座位很遠，雖然可以從中存取很多水，但是很耗時。

一個是雖然存取空間有限，但是可以根據自己的喜好設計，例如馬克杯、保溫瓶等等。除此之外，存取非常快速，伸手就拿得到了。

以程式語言為例，磁碟通常對應著檔案的讀寫，每次讀寫都只能是字串。反之，從檔案拉出來的字串，你可以做各種轉換，物件、陣列、字典等等。而且拿取（變數）非常快速。

----

**效能**

| 單位 | Latency |
| --------------- | ------- |
| 第一層快取 | 1 ns |
| 第二層快取 | 4 ns |
| 第三層快取 | 40 ns ↑ |
| 主記憶體（DDR） | 80 ns ↑ |
| 讀取磁碟 | 80 us ↑ |

> [Intel - Memory Performance in a Nutshell](https://www.intel.com/content/www/us/en/developer/articles/technical/memory-performance-in-a-nutshell.html)

note:
回到主題，OLAP 注重的是頻寬，也就是第二、三層快取和主記憶體的大小建議較大；反過來 OLTP 注重在磁碟中查找的效能，例如我要找到 `/usr/var/db/data/page100-page1000/page456` 的位置效能。

----

### 概圖


note:
我們之前學到的索引演算法，並不適合這類分析性的行為。為此需要設計一個新的資料庫。

目前也越來越多資料庫針對不同場域做特定的優化，也就是很少會看到一個資料庫同時滿足 OLTP 和 OLAP 的需求。

我們最後會再回到這張圖，把很多區塊補齊，現在所知的東西比較少，先給大家看一下兩者的關係圖。

---

## 資料倉儲

*Data Warehouse*

針對線上分析處理而去設計的資料庫。

note:
我們現在知道什麼是 OLAP、OLTP，和其差異。現在就來定義適合 OLAP 的資料庫，就叫資料倉儲（Data Warehouse）。

----

### 角色

- 整合各自獨立的資料庫們
- 避免和線上使用者搶資源
- dedicated，獻身的

note:
對於公司來說可能會有很多資料庫去滿足各個單位的需求。這些資料庫很可能彼此是各自獨立的（負責單位不同），但卻都是在替同一群使用者在服務。例如：人力銀行的

- **求職者**履歷資料庫
- **求職者**的性向測驗

都是在為求職者服務，但是負責單位可能不一樣。這時資料倉儲就可以用來整合這些資料庫，方便分析師下搜尋指令。

除此之外，這些線上的資料庫為了滿足 OLTP 低潛時性，當你要下指令去搜集全域的資訊時（例如，上個月的下單金額），你很可能會被 DBA 拒絕。為了同時滿足線上使用者高效率的運作和分析師的數據爬取，這時資料儲倉（Data Warehouse，DW）便出現了。

----

### 資料怎麼來

**Extract–Transform–Load，ETL**

- 萃取
- 定時（periodic data dump）
- 串流（continuous stream of updates）
- 變換
- 綱目
- 清理（deduplication）
- 載入

note:
把所有不同服務的資料，定時（periodic data dump）或串流（continuous stream of updates）從 OLTP 資料庫中擷取資料。

存入適合分析的綱目（schema），做一些重複資料的清理等等。

這一系列的行為稱作萃取、變換及載入（Extract–Transform–Load，ETL）

----


note:

- 整合各自獨立的資料庫們
- 避免和線上使用者搶資源

這次報告不會討論這些細節。不過會在第十章（批次處理）和第十一章（串流處理）討論。

ETL 是一個大主題，書中在多個章節都會稍微提到一點（包括下一次的「編碼和演進」），這需要了解一定的背景知識再去講，會比較透徹。我們這次就專注於討論資料倉儲的設計。

----

### 有哪些產品

Google [Dremel] 為基礎。

| Vendor | Open Source |
| -------------- | --------------- |
| [Teradata] | [Apache Hive] |
| [Vertica] | [Apache Spark] |
| SAP [HANA] | [Apache Impala] |
| [ParAccel] | [Presto] |
| [AWS RedShift] | [Apache Drill] |

note:
雖然大部分資料倉儲都是關連式資料庫，其內部運算邏輯卻和常見的 OLTP 關連式資料庫不同。為什麼大部分資料倉儲都是關連式資料庫？

- 易於分析
- SQL 語法很適用（概念抽象）且很成熟
- 視覺化

未來也會講不是 SQL 語法的分析方式，例如 Python Notebook、機器學習。

[dremel]: https://research.google/pubs/pub36632
[teradata]: https://www.teradata.com
[vertica]: https://www.vertica.com
[hana]: https://www.sap.com/taiwan/products/hana.html
[paraccel]: https://www.actian.com
[aws redshift]: https://en.wikipedia.org/wiki/Amazon_Redshift
[apache hive]: https://github.com/apache/hive
[apache spark]: https://github.com/apache/spark
[apache impala]: https://github.com/apache/impala
[presto]: https://github.com/prestodb/presto
[apache drill]: https://github.com/apache/drill

----

### 複習

- 資料倉儲，用於 OLAP
- 整合線上資料庫
- 加速搜尋遍歷的資料
- 透過 ETL 得到資料

---

## 實作細節

- 整合資料庫，綱目
- 星狀綱目
- 雪花綱目
- 加速搜尋，行式導向
- 壓縮
- 排序
- 硬體面優化
- 暫存

note:
我們已經了解資料倉儲的定位和優勢了，現在來聊聊他的實作細節。

要整合資料庫，就需要定義一組綱目，有哪些方式？

我們透過行式導向（column-oriented）幫助我們加速搜尋。除此之外，他也便於壓縮。

透過排序，例如消費記錄以產品編號為排序，可以幫助我們查找特定產品的分析結果。排序也可以幫助資料的壓縮。

最後講一些硬體面的東西和暫存的機制。

> 有些資料倉儲是不需要綱目的，他甚至可以允許你把圖片、影片丟到資料庫中。
這一類的資料庫通常是以分散式資料系統（HDFS）為基底，不過這個我們會在批次處理中比較細部的討論。
> 這類型的資料庫我們稱為資料湖（data lake）。

----

### 星狀綱目


note:
在細看這些資料代表的意義之前，先注意到表（table）的前綴詞有兩種：

- `dim` 對資料提供維度（dimension）的表
- `fact` 展示所有狀態的表，事實表

以上述圖片為例子，產品、商店、顧客、日期、推廣活動等等就是提高事實表維度的資料庫。而 `fact_sales` 就是銷售相關的事實表，或者說該表紀錄了所有銷售相關的行為（事件）。

儘管有些是對照其他表的外區鍵（foreign key），但仍有很多欄位是相關行為（事件）的屬性，例如：該「顧客」於該「商店」購買該「產品」的數量、原價、售價等等。由此可知，若提供細節信息，該表格將會有非常多的欄位，或者說屬性（property），甚至可能到數百種屬性。

----

### 雪花綱目


note:
類似於星狀綱目，只是他的維度表可能會有很多層，例如：「產品表」又會有外區鍵連到「品牌表」和「種類表」。

----

### 比較

大部分都使用星狀綱目：

- 好擴充、調整
- 較好理解
- 優化搜尋速度

note:
- 好擴充，例如：當有新的種類，就不用同時去改種類表和產品表
- 好調整，新增屬性時，不需要考慮放在哪個表比較適合
- 較好理解，不用層層堆砌，層層解析
- 優化搜尋速度，相對於雪花是，較低的正規化讓他更單純，故而更好的搜尋

---

## 行式導向

橫列（row）直行（column）

- 壓縮
- 硬體面優化
- 排序
- 暫存聚合

note:
待會介紹完後會再細部討論的東西。
不過這裡要提，用行為單位和以往用列為單位，思考上需要轉方向，所以一開始可能很難理解。盡量慢慢講。

----

**在假日購買水果的人數**


note:
由此例可知，在該特性下，若每次操作僅拿取部分資料做運算，是否有必要做功讓其他欄位的資料一起從磁碟（disk）中讀取出來？
尤其是在資料量有好幾 PB，而每一行可能有好幾百個屬性時，這類「小缺點」將會被放大。

----


note:
列式資料庫（column-oriented storage）的概念就是由此而生，我不以每行為單位做儲存，而是改為每列為單位。這樣在讀取時，就只需要讀取少部分的資料。

並非只有關連式資料庫適合做行式資料庫，僅僅因為關連式資料庫在講解上是最好理解的。Parquet 就是一個以 Google's Dremel paper 為基礎的文件式資料庫。

這同時也代表，每一列都需要擁有相同的順序和數量，而這條件在 OLAP 是符合的，因為其不會刪除任一行資料。

---

### 壓縮

很多事件（列，row），很少種類（ID）

note:
好的資料壓縮，可以降低在讀取海量資料的時間，而 OLAP 還有個特性，就是「行」可能的值是有限的。

例如：產品數量可能只有數萬或數十萬個，但是訂單卻可能每年有好幾億筆。

----

| 產品 | 訂單 1 | 訂單 2 | 訂單 3 | ... |
| ---- | ------ | ------ | ------ | --- |
| 1 | 1 | 0 | 1 | ... |
| 2 | 0 | 1 | 0 | ... |
| 3 | 0 | 0 | 0 | ... |
| ... | - | - | - | ... |

note:
以操作為行，產品編號為列（異於資料庫每筆訂單（操作）都以列存在，而產品編號是行（一種欄位）），可得上表。

其意義代表：

- `訂單 1` 購買 `產品 1`
- `訂單 2` 購買 `產品 2`
- `訂單 3` 購買 `產品 1`
- ...

此時並不能壓縮資料，事實上，他只是把各操作的各產品編號，展開成二進位而已。也就是，位元映射（_bitmap encoding_）。然而，因為 OLAP 的特性讓每行有多個為 0 的欄位，此時就可以透過執行長度編碼（_run-length encoded_）進行壓縮。

除了壓縮外，這類編碼可以幫助特定搜尋。例如，產品 2 的訂單總數。

有看沒有懂？沒關係，看下圖。

----


----

#### 搜尋

WHERE product_sk IN (30, 68, 69)

WHERE product_sk = 31 AND store_sk = 3

> [The Design and Implementation of Modern Column-Oriented Database Systems. Ct4-2][tdaiomcords]

note:
而展開成二進位的格式，不止利於壓縮，在計算時，也可以單純透過 OR AND 去做計算。

- 讀取產品的位元映射表中的第 `30`，`68` 和 `69` 列，然後比較這三段位元向量（bit vector）做位元間的 OR 運算。
- 讀取位產品的元映射表中的第 `31` 列，然後讀取商店的元映射表中的第 `3` 列做位元間的 AND 運算。

這類操作之所以可以運作，就是因為我們同步所有行的數量和順序。也就是每列都擁有所有欄位（每個訂單都有產品編號、商店編號等等）。

若需要查看更多壓縮的演算法，可以查看 [The Design and Implementation of Modern Column-Oriented Database Systems. Ct4-2][tdaiomcords]。
（雖然我自己看完後，過了一個月忘光光了，但是滿有趣的。大家晚上睡不著可以讀讀。）

> _[Column Family]_ 和 _Column Oriented_ 是不同的概念，其被應用於基於 [Bigtable] 架構的資料庫 [Cassandra] 和 [HBase] 中。其原理是把所有行（節點）整合成一個單位，就像是把每個文件當成關連式資料庫的表（table），並且不會對這單位進行列壓縮（_column compression_），因此該模型仍主要是以列式資料庫（row-oriented）為主。

[column family]: https://www.rubyscale.com/post/143067472270/understanding-the-cassandra-data-model-from-a-sql
[tdaiomcords]: http://www.cs.umd.edu/~abadi/papers/abadi-column-stores.pdf
[bigtable]: http://research.google.com/archive/bigtable.html
[cassandra]: https://github.com/apache/cassandra
[hbase]: https://github.com/apache/hbase

---

### 硬體面優化

- [減少分支預測錯誤][mis-prediction]
- 使用[單指令，多資料（Single-Instruction-Multiple-Data, SIMD）](https://www.sciencedirect.com/topics/computer-science/single-instruction-multiple-data)

note:
書中用了[一小段文字](https://github.com/Vonng/ddia/blob/master/zh-tw/ch3.md#記憶體頻寬和向量化處理)解釋資料庫怎麼透過硬體機制去優化。

但是為了避免失焦，僅概述。

[mis-prediction]: https://zh.wikipedia.org/wiki/指令管線化
[simd]: https://www.sciencedirect.com/topics/computer-science/single-instruction-multiple-data "João M.P. Cardoso, ... Pedro C. Diniz, 2017, High-performance embedded computing"

----

**CISC** v.s. **RISC**

LOAD R1, A
LOAD R2, B 
ADD R3, R1, R2
STORE R3, C
// next instruction

note:
要了解為什麼要避免分支預判錯誤，需要先了解 RISC 和 CISC 的演進。

----

**指令管線化**


note:
RISC 建立在指令管線化之上，但是當發生分支錯誤的時候，會讓他白做工。

故而，在資料庫設計上特地將程式寫的極少分支化來避免預測失敗。

----

**SIMD**


note:
除了盡可能減少拉取的資料，每次拉取時也須有效的配合 CPU 的週期。例如，搜尋時，會把壓縮後的行式資料分成好幾段（chunk），並持續且緊密地放進 CPU 第一層快取中。

在做運算時，透過 SIMD 單一指令（可能是 AND/OR/ADD 等等），也就是過程中不呼叫任何函示，避免 function call/jump。

---

### 排序

- 加速
- 壓縮

note:
來談一下排序的好處吧！

----

#### 加速


note:
我們以前面例子提到零售業為例。

若發現常常使用日期單位做搜尋，如每月的購買產品總數，則可以使用 `date_key` 來做排序。

也可以再新增一個行來排序。例如，使用產品編號額外做一組排序的資料，這樣資料就會以日期排序，讓資料庫快速找到指定日期。同時又再使用產品編號排序，這時幫助分析師快速判斷**哪天有哪些產品熱賣**。

----

#### 壓縮


note:
再拿前面的例子討論。

如果產品排序過後再壓縮，位元映射（_bitmap encoding_）就會變成

29: 1,
30: 1,2
31: 3,7
68: 10,1
...

----

#### 多排序

- 列式資料庫多索引：堆積檔、群聚式索引
- 行式資料庫多排序：各行的檔案根據規則排序

note:
排序的行種越多，其能強化的壓縮量和搜尋速度就越少。

可以想像其和列式資料庫的多索引的差異。
列式資料庫在多索引中，常常會在索引中儲存檔案的來源。如，heap file、cluster index。
而行式資料庫則是根據特定排序方式直接儲存該資料。

還有：

- 怎麼寫入
- 排序的行種越多，其能強化的壓縮量和搜尋速度就越少
- 反正資料都要做備份和 HA 而把資料複製到各機器，你就可以把各機器的資料做不同方式去儲存。例如資料庫 A 以日期作為排序，資料庫 B 以產品作為排序
- Vertica

---

### 暫存聚合

既然常常要聚合（aggregation），那就暫存他吧！

note:
搜尋時，常常會用到聚合（aggregation）資料，例如總數（sum）、平均（avg）等等。而這類操作常常都需要遍歷資料庫，既然這些資料很耗時又需要常常用到，就暫存他吧。

----


note:
物化視圖（materialized view）只是一種方式而已。

圖中展示，二維資料在做物化整合時的方式。

每一個單元（cell）儲存某一天的某一個產品銷售總額，列尾儲存某一天的所有產品銷售總額，行尾儲存某一產品的所有銷售總額。

除此之外，資料更可能被進行多維度的儲存，例如購物者的年齡等等。

----

#### 缺點

- 去正規化（de-normalized）
- 低彈性

note:

- 相同資料放在多個地方，提高資料同步的困難，降低寫入時的效能，所以在 OLTP 的資料庫中很少會看到其存在。
- 以上面為例，如果要搜尋產品金額大於 100 塊的產品銷售總數，就沒辦法。

原則上，一般的資料倉儲都會盡可能的保存原始資料（壽司策略）。當在搜尋時，如果需要加速某些結果，再使用這些加速手法。

---

## 總結

- OLTP v.s. OLAP
- OLAP 適合什麼綱目、硬體
- 資料倉儲的實作細節

note:
我們比較了線上異動處理和線上分析處理，什麼適合隨機存取、什麼適合遍歷資料等等。

我們也討論了一些綱目設計原則和硬體面需要注意的東西

我們還闡述了資料倉儲的東西，他可以分擔線上使用者資源、整合資料，而且非常利於分析。
除此之外我們有提到資料倉儲透過 ETL 獲取資料，這塊在資料庫也是非常重要，未來我們會再進一步討論。

最後我們從很多面向介紹了一下行式資料庫。

----

行式資料庫（column-oriented）

- 壓縮
- 硬體面優化
- 排序
- 暫存聚合

note:
行式資料庫非常適合壓縮，我們講了位元映射的方式，有想學更多方式的歡迎看上面的連結。
我們也討論了向量運算在硬體面是非常具有優勢的

同時，根據商務邏輯設計好的排序也可以優化搜尋效能和壓縮量。

最後我們提到了可以暫存聚合的資料，類似於 Google Analytic 的邏輯。

再提一次：原則上，一般的資料倉儲都會盡可能的保存原始資料（壽司策略）。當在搜尋時，如果需要加速某些結果，再使用這些加速手法。

----

### 資料庫的存取


note:
並不是所有資料倉儲都是行式資料庫，只是他是[主流](https://www.slideshare.net/julienledem/th-210pledem)

報告過程中也可以注意到，其實很多內容都和批次處理、串流處理有關，所以未來聽完批次處理和串聯處理時，再回來看這章就會有更完整的體悟。

----

### 預告