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)

今天這篇主要要談論的是 OLTP 的部分，以 index structure 的設計為主題

Database storage engine

書中從被應用至 RDBMs 和 NoSQL 底層的 database storage engine 談起

Log-structured

許多資料庫都會有內部的日誌(log)，本身是一個 append-only 的文件，用於描述應用程式正在發生的事情的紀錄，或許是二進位制的，因為本來就不是設計給人類看的．但當紀錄變多時，查詢時間會很久，所以為了加速搜尋，就需要有額外的結構來輔助我們，這個 additional structure 就是 index

但為了維護這個額外的結構，會多多少少的影響到寫入的速度，因為每增加一筆資料都要更新 index，正因如此，資料庫預設都不會加上 index，而是交給程式開發者或是 DBA 來設計該用什麼樣的 index 來增快查詢，避免額外的開銷

Hash Indexes

首先，書中一開始提到的是 Hash Indexes，是 key/value 的儲存結構，每個 key 對應的是 file value 的 byte offset，如下圖所示

讀取的時候直接看該 hash table 有沒有這個 key，有的話直接依據 byte offset 找到 file 中的值，寫入的時候也要更新 hash table 的 key value

缺點是少量的 key 存在 in-memory 還可以接受，一但數量變大有可能會耗掉內存空間，且維護 key/value 的成本會較大

由於每次都是 append 加入到 file 中，不僅有可能會加入重複的 key，也有可能漸漸耗盡 disk 的空間，為了解決空間問題，將資料分為特定的 segment，一旦達到 segment 容量的限制，就關閉該 segment，將寫入的資料導入到新的 segment，再來為了節省 disk 空間，也去除存到的重複 key，會定期的在後台線程把關閉的 segment 壓縮(compaction)與丟棄重複的鍵(deduplicate)，只保留最新的鍵

以上有個問題，就是範圍搜尋時效率較低，例如：有 10000 個 key，就需要一一迭代去找

SSTable

如果將 hash table 的 key 排序，就稱為Sorted String Table，又稱 SSTable

乍看之下破壞了原先寫入的順序，但其實可以解決範圍搜尋的問題，因為一旦 key 是排序過，在壓縮合併時，只要查看每一個 segment 的第一個 key，複製順序最低的 key 到下一個 segment，不斷重複就能產生一個新的合併過後的 segment，且內部的鍵也是排序過的

此時不再需要在 memory 內保存所有 key 的索引，可以透過鍵的順序來快速查詢

以下圖為例，假設我們正在尋找 handiwork 這個 key，但我們不知道這個 key 在 segment 中的 offset，但是我們知道 handbag 和 handsome 的偏移，由於字母排序的關係，我們可以快速知道 handiwork必定在這兩者之間，意味者我們可以跳到 handbag 的 offset 開始查找，直到找到 handiwork這個 key

如何讓數據寫入時可以預先排好序呢？

仰賴的是 B-Tree structure，常聽到的 balanced tree 有：AVL、紅黑樹、B 樹

寫入流程變成是，在 memory 中維護一個 in-memory balanced tree data structure，稱為 memtable，當 memtable 超過某個閥值(幾兆字節)後就將其作為 SSTable 寫入 disk，這時因為 balanced tree 的緣故，寫到 disk 的資料也是排序過的

讀取流程則是先讀取 memtable，讀不到再去 disk 讀取，如果還是沒有就去舊的 segment 查詢，以此類推

後台線程依舊要時不時地去做壓縮，將重複的鍵移除

以上效果很好，但有個問題就是當資料庫崩潰時，來不及寫入 disk 的 memtable 就會遺失，這時可以單獨額外寫一個 log 用來維護 restart 的操作，一旦重啟後，log 紀錄就可以移除

LSM tree

後來 SSTable + memtable 漸漸演變成 LSM tree(Log-Structured Merge-Tree)

LSM Tree 的核心思想是將資料寫入到一個階段性的緩存區(memtable)，當 memtable 的大小達到一定閾值後，會被寫入到磁碟上的 SSTable 中。SSTable 是一種靜態的資料結構，只能被追加而不能被修改，因此所有的更新操作都是寫入到 memtable 中。當 memtable 的資料寫入 SSTable 後，它會被清空並開始一個新的 memtable，這樣就能實現不斷循環的寫入操作。

當讀取操作需要進行時，LSM Tree 會首先查詢 memtable 中的資料，如果找不到再到 SSTable 中查詢。由於 SSTable 是靜態的資料結構，查詢速度比 memtable 慢。為了提高讀取速度，LSM Tree 可以將多個 SSTable 合併成一個更大的 SSTable，以減少查詢的層級和磁碟 I/O 次數。

LSM Tree 的優點是能夠處理大量的寫入操作，因為寫入操作只需要寫入到 Memtable 中，而不需要直接寫入磁碟。此外，LSM Tree 的 SSTable 是靜態的，可以進行很好的壓縮和運算，從而提高查詢效率。LSM Tree 的缺點是讀取效率不如 B-tree 等傳統的資料結構，因為需要在多個層級上進行查詢，並且 SSTable 中的資料需要進行合併和排序才能進行查詢。此外，由於 SSTable 是靜態的，因此當需要進行更新操作時，需要寫入到 memtable 中，並進行 SSTable 的合併和重寫，這也會影響更新操作的效率。

Page-orient

底下才是最常見的索引類型：B-tree

如同 SSTable 一樣，B-tree 也是按鍵排序的，造就高效的鍵值查詢，也解決範圍查詢的問題．但除此之外，就沒有相似之處了，因為他底層的設計與上述的 log-structure 是截然不同

與 log-structure 的索引相比，B-tree 會將資料庫分解成固定大小的 block 或 page，一次只能讀取或寫入一個 page，透過類似 pointer 的方式 reference 到不同的 page 來彼此關聯，建立一個 page tree，這種設計與 log-structure 可變動大小的 segment 機制有很大的不同

這種設計在新增鍵時會有分裂的現象，當新增的鍵 334 沒有出現在原本的 tree 中，就會需要將其分成兩個半滿的 page，還要更新父 page (鍵 337)以反映新鍵的範圍

為了避免資料庫崩潰造成數據遺失，B-tree 會額外寫一個結構叫 WAL(Write-ahead log) 又稱為 redo log，本身是 append-only 的文件，每個對 B-tree 的修改都會先寫入這個 log 中，這樣當資料庫意外崩潰時，還能透過這個 log 來還原 B-tree 的狀態

B-tree vs LSM tree

B-tree 是屬於一塊一塊 page 的設計，其本身資料結構是平衡樹，對於小數據的查詢與寫入來說性能很足夠，但遇到數據較大的時候就會有瓶頸。整體而言 B-tree 適合處理 read-heavy 的情境。

LSM 樹相較於 B-tree 更適合大量數據的寫入，因為他會先寫入 memtable，達到某個閥值後才會壓縮合併成 SSTable 寫入 disk 中， 這種壓縮批量處理的能力在應付大量數據時效能更好。整體而言，相對於讀取來說，LSM 樹更適合 write-heavy 的情境。