iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 8
1
AI & Data

資料工程師修煉之路系列 第 8

[Day 8] Storage and Retrieval (1) - Log structured and Hash Index

前面幾天我們談了 Data Model,為你的數據系統挑個合適 Data Model 後,接下來就要談談怎麼儲存與檢索了,資料庫 (database) 就做這 2 件事,給它資料後它儲存,之後還要能檢索資料,

每個 Data Model 都有對應之資料庫,它們會實做不同的儲存引擎 (storage engine),我們有幸活在這個年代,現在不太需要動手實做資料庫了,但我們得知道它們的原理,否則我們無法選合適的資料庫,首先我們來聊聊 2 個類似的儲存引擎,log-structuredpage-oriented

資料庫的原力:Data Structure

首先用 Bash 來建立個簡單的資料庫,

#!/bin/bash
db_set () {
	echo "$1,$2" >> database
}

db_get () {
	grep "^$1," database | sed -e "s/^$1,//" | tail -n 1
}

我們有 2 個在簡單不過的 function,給 db_set key 及 value,它會用逗號組合起來後 append (附加) 到檔案中 (CSV-like 格式), db_get 則是找到符合 key 的最新資料 (用 tail -n 1),我們新增幾個 JSON 來舉例:

$ db_set 123456 '{"name":"London","attractions":["Big Ben","London Eye"]}' 

$ db_set 42 '{"name":"San Francisco","attractions":["Golden Gate Bridge"]}'

$ db_get 42 
{"name":"San Francisco","attractions":["Golden Gate Bridge"]}

在新增一次 key 為 42 的資料,db_get 取到的是最近一次新增的資料,

$ db_set 42 '{"name":"San Francisco","attractions":["Exploratorium"]}' 

$ db_get 42
    {"name":"San Francisco","attractions":["Exploratorium"]}

$ cat database
123456,{"name":"London","attractions":["Big Ben","London Eye"]}
42,{"name":"San Francisco","attractions":["Golden Gate Bridge"]}
42,{"name":"San Francisco","attractions":["Exploratorium"]}

db_set 有非常好的 performance,因為夠簡單、有效率,許多資料庫內部實做時稱 append-only log

db_get 就不是這麼有效率了,如果你的 database 筆數非常大,你得需要 O(n) 的時間才能找到指定的 key,若多一倍資料,你得多花一倍的時間,為了有效率的查找資料,我們得建立另一個不同的 data strucutre:index

index 的概念是替我們的主要增加額外 meta data,不同的方式會建立不同的 index,index 影響的層面只有查詢,你無法用 index 加速寫入,因為你很難打敗 append-only log,另外任何 iindex 都會提高寫入資料的時間,因為額外的 meta data 也需要更新,這裡依舊需要工程師選擇適合的欄位建立 index。

這裡的 log 不是指系統執行時產生的,而是 append-only 且有序的記錄,它不用一定要讓工程師看得懂,通常是 binary 字串或者是某些程式語言讀的格式。

Hash Index

讓我們用 key-value 資料來開始學學第一個 Index 吧,key-value 資料很像許多程式語言有的 dictionary 型態,也是 Hash map 的實做方式,我們也可以用相同的概念為我們在硬碟的資料建立 index,延用前面提到的範例,我們在記憶體中建立一個 hash map 存我們 database 的資料是從哪個 byte offset (偏移)開始,如下圖所示:

figure_3-1

這聽起來很簡單對吧!?但這真的是一個非常有效的辦法。

壓實 (compaction)

再來要談談怎麼避免硬碟爆掉,我們知道 append-only log 是很有效的方式,但總不能無止盡的 append 吧!

一個好的解決方案就是我們指定每個 segment log 的大小,當達到該容量時,我們可以對該 log 做 compaction (壓實) ,compaction 後該 log 只會有最新的 key value,如下圖:

figure_3-2

若 segement log 不大,一次做多個也 OK,

figure_3-3

當然在 compaction 期間並不會對查詢有任何影響,當 compaction 完成後,只要把查詢 request 切到新的 segment log 去就好了,舊的 log 就可刪除了。

每個 segment log 都有自己的 hash map index,查詢時,會依序從最新的 hashmap 找資料,其他實務上該注意的地方還有:

  • 刪除資料 (Deleting records)

    當你想要刪除資料時,並不會真的找到所有有該 key 的 segment log 裡刪掉該筆檔案,我們會另外新增一個刪除用的檔案 (稱 tombstone),當查詢或 compaction 時,會去忽略該筆被刪除的資料。

  • 故障恢復 (Crash recovery)

    當資料庫重啟時,理論上在記憶體中的 hash map 會全部消失,所以我們需要重建毎個 segment log 的 hash map,有些資料庫也會把 hash map 的 index 資料寫到硬碟中。

  • 部份寫入 (Partially written records)

    不幸的當資料庫掛掉時,有些正在寫的 log 會寫不完全,有些資料庫會有 檢查點 (checksums) 機制,讓資料庫能略過爛掉的資料。

  • 並發控制 (Concurrent control)

    寫入時需要嚴格控制寫入時的順序,所以通常只會有一個執行緒執行寫入動作,除了 append 以外,log 是不可變的,所以查詢就可以並發多個執行緒一起作業。

當然,hash map index 也是有幾個限制:

  • hash map 必須存在記憶體中,我們不能期望維護存在硬碟的 hash map 會快到哪裡去,會有太多的隨機訪問存取 I/O。
  • 範圍查詢非常沒效率,舉例來說,你無法簡單的找 st0001~st0009 的所有資料,在 hash index 下,你只能一次次的獨立找。

明天會介紹 SSTables 跟 LSM-Tree 是怎麼突破這些限制的。


上一篇
[Day 7] Data Model(4) - Triple-Store Graph Model 和 總結
下一篇
[Day 9] Storage and Retrieval(2) - SSTables and LSM-Tree
系列文
資料工程師修煉之路30

尚未有邦友留言

立即登入留言