# 資料倉儲 如何建立一個可供快速分析的資料庫。 [文本於此](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 低，但是每次請求可能都需要遍歷資料庫來取得特定分析結果（頻寬越高，拉取大資料效率越快） --- ### 磁碟和記憶體 | 飲水機 | 保溫瓶 | |:---------------------------------------------------------------------------------------------------:|:------------------------------------------------------------------------------------------------------------------------------------------------------------------:| |  |  | ```javascript // 從飲水機取水就好像： 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 的訂單總數。 有看沒有懂？沒關係，看下圖。 ----  ---- #### 搜尋 ```sql WHERE product_sk IN (30, 68, 69) ``` ```sql 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** ```assembly 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) 報告過程中也可以注意到，其實很多內容都和批次處理、串流處理有關，所以未來聽完批次處理和串聯處理時，再回來看這章就會有更完整的體悟。 ---- ### 預告