學習手記：2018清華大學DB/AI Bootcamp — I — 緣起與 Hash Indexing

緣起

這次有幸參加由清華大學吳尚鴻教授實驗室舉辦的 DB/AI Bootcamp 完全是出於意外。由於老闆的以前是清華大學研究人員的關係，與清大之間的互動到現在仍十分熱絡，也因此第一時間得知有這個活動時，便力薦我參與。

而今年7、8這二個月期間，個人又遭逢許多不甚順遂的變故，不論是健康或心理都受到非常嚴重的衝擊。經歷了這麼多意外後，我思忖了非常多關於往後行事以及待人上的方針，認清現階段必須好好規劃及調整這些方面的行為準則。雖然代價甚高，但也算是好好上了一堂寶貴的人生課程。

不論如何，這段期間內我的心理狀況絕稱不上是健康。藉著這個參加這個活動，一方面能學習新的知識（雖然從網站上看不出來葫蘆裡賣什麼藥），另一方面也是給自己一個能好好調適、整理心情的機會。

從這篇開始，我會將個人在課後針對每個章節，查找並補齊相關背景知識後的筆記，記敘成一系列文章，除了留下這些知識的補遺之外，也期望能幫上往後對這些資訊有需要的朋友；也以這一系列文章，聊表對於期間付出努力的各位助教的感謝。如果發現有錯誤或不明之處，也歡迎各位來信或留言指教。

What’s the purpose of this course?

其實這個活動從網站上能獲得的資訊並不多，能理解到的大致上是：

1. 講解 Database 的設計和原理
2. 會帶入 Source Code 探討
3. 結合 AI 技術

起先見到「結合AI技術」這個標題時，原以為又是另一個一時跟風的活動，並不有帶有多大期望。畢竟現階段「AI」二字在台灣，不論是業界或學界都已經過於氾濫，然而實質上對於學術或實務上有做出貢獻的單位並不多，大多為口號式的洗錢＼洗經費＼洗補助之輩。正如早些年前的「物聯網」及「雲端」之流等，不得不慎。

不過這個想法在第一天參與時便有所改觀。五天的課程下來著實讓我獲益良多，在對資料庫的想法以及系統設計的概念上得到了諸多啟發，也是我始料未及的。整體而言，這五天課程的大致依循著以下的脈絡而行：

1. 最低階的 File System Access （Indexing）
2. 較高層次的 SQL Commands Parsing （Query Processing） & Query Optimization
3. 系統層級的 Database System Design 及 Distributed Database System Design

每個部分則在這篇文章剩下的篇幅裡逐個講述。在課程當下，對於一些理論上的細節並沒有融會貫通，僅限於粗略理解其功能和原理。所以文章內是再額外查找資料、補齊相關背景知識的筆記。再次聲明，內容僅以我個人的理解來闡述，如果發現有錯誤或不明之處，非常歡迎各位來信或留言指教。

課程內容

1. Database System 有什麼？

在這次 bootcamp 前，我對於Database的概念十分粗淺，大體上停留於「用」的層次，亦即針對不同場景，建置需要的方案：

• 離線型或小規模連網型應用：SQLite
• 小型至中型規模應用：單機型 MySQL ／ MariaDB ／ PostgreSQL 或其他 RM ／非 RM Database
• 高存取量的大型應用：叢集型 MySQL／MariaDB／PostgreSQL或其他可以多點佈署型 RM ／非 RM Database

把一個＼一組 Database 架起來、初步的調校參數以令應用能夠連接，並不是困難的事情，差異只在於熟練與否。尤其現在有太多整合式的 Containerized ／ VM Based 佈署方案，又大大降低了建置到調校的門檻。所以就我的角度而言， Database System 一直只是一個因應不同需求、隨時能夠置換的資料儲存方案。理解其內容與否並非至關重要 ，重要的是我能不能對應每個場景，熟練地抽換與擴展。

而這次的bootcamp從「用」的層次，進一步切入「組成」的層次。把以往被我視為黑箱子的Database打開，仔細探究對於 Database 而言，至關重要的部分。這堂課上作為範例的 Database 是一樣由清華大學吳尚鴻教授實驗室基於 Java 開發的VanillaDB，功能間的結構圖如下（節錄自課程用投影片）：

據bootcamp總召所述， VanillaDB 的功能結構已經接近現代 Database System 的設計，如 MySQL 等，不過 VanillaDB 是因應教學目的而生，因此是精簡過後的版本，相較於商用的 Database System ，Source Code 的規模約略只有1／20左右，易於閱讀、修改及添加實驗性功能。

上圖紅框處兩功能對應到 bootcamp 前半部分課程的重點：

• Index ：資料庫是怎麼存取資料的？
• Planner：資料庫是怎麼把 SQL Commands 變成實質的存取行為的？

而後半課程部分著重於 Transaction 與 Distributed Database System 的設計。

2. Index

對於人類而言， SQL Commands 本身具備不少功能，諸如建立＼刪除資料表、新增＼修改＼刪除資料等，然而對於 File System 而言，這些不過只是單純的讀與寫的行為。那麼問題來了：要怎麼加速這個過程？

一般 Database System中，資料通常會被寫入於單一或多個檔案之內，如果 Database 只是純粹地開檔＼讀檔＼寫檔，顯然不能夠因應當儲存資料量攀升時對於 IO 的負載。要知道， Database System 不論在 KB ＼ MB ＼ GB 等級的資料量下，都必須要能夠保證一定水準的讀＼寫速度。如果只是純粹的File IO，當資料量增加時，「定位」出目標資料時的速度就會呈正比上升，這樣子的作法顯然不敷使用，必需有其他的機制來輔助「定位」。因此在現代 Database System 的設計中， Index 機制應運而生，

除儲存資料的檔案（DB File）外，另外在其他檔案中，建立對資料的Index，紀錄目標資料在 DB File 中所在的位置資訊，如下圖所示：

至於這邊提到的 Data ，不論在課程中或是手邊能找到的資料，都會解釋為在 Table 中的 Data Row，即：

而 Index 則是針對某單一欄位建立的快速索引，所以實際上 Index 的內容和指向 Data 間的會是如下圖所示（以針對 Age 這個 Field 建立 Index 為例 ）：

這邊用 Record ID 代表每一筆紀錄的位置，與前述的 Data 1 、 Data2 … 的原意相同，只是正式上的名詞如此。然而若只是單純對 Field 建立 Index ，當資料量上升時， Index 數量還是會隨之成長，並不會實質解決問題，為此還有額外的輔助機制－Index Mechanism 。其運作下圖所示；

Key 的部分指的是對 Value 的 Query 條件，如：

• Age = 10
• Age < 13 and Age >= 10

可以理解為，此機制是利用 Index Mechanism 對 Key 進行邏輯或數值運算，生成Index的對應位置。相較於直接逐筆查詢 Index ， Index Function 擁有常數級或是非線性的較低運算時間，能夠極大化加速找出 Index 並取得 Data 的過程。而這一次的課程介紹了兩種經典的 Index Mechanism：

• Hash-Based Index
• B-Tree Index

2.1 Hash-Based Index

Hash-Based Index 即是利用 Hash Table 來建立 Key 對 Index 的映射，基本原理如下圖：

其中，Hash Function 將輸入的 Key 轉換成一組獨特的 Hash Value ，直接透過 Hash Value 查找對應的 Record ID。單從這部分，不難看出 Hash-Based Index 註定會有先天上的限制，即輸入的 Key 只能直接對值索引，像是：

• Age = 10
• Student = John

但如範圍性的索引：

• Age > 20
• Age <=15

便不能作為 Key 輸入，畢竟 Hash Function 不會知道數值範圍的上界或下界，致使無法得知究竟要搜尋到什麼程度。另外 Hash Function 不保證生成的 Hash Value 絕對會是 Unique ，所以實際上會有重複儲存不同 Key 於相同位置及 Overflow 兩情形存在，而令 Hash Table 呈下圖之形式：

上圖中，每個 Hash Value 對映到一組獨立的 Bucket ，包含起始的 Primary Bucket 以及擴充出的 Overflow。要注意的是 Bucket 內可存放的 Index 數（ Slot ）並不只限於一筆，只是一旦建立出 Primary Bucket 後，後續擴充出的每一塊 Overflow ，其 Slot 數亦與 Primary Bucket 相同。

在有 Overflow 的情況下，除了 Hash Function 的運算外，還需要額外的搜尋時間，即定位到 Hash Value 後，還要往後繼續逐筆對照 Value 。因應這種情形，實務上的 Hash-Based Index 有兩種設計：

1. Static Hashing
2. Extendable Hashing

2.1.1 Static Hashing

針對每一組 Hash Value 建立一個對應檔案 ， 每當有相同 Hash Value 的 Index 加入時，動態延伸每個檔案大小。初始建立檔案以及後續因應Overflow擴充時， 一樣遵從 Hash Table 中，延伸 Overflow 時的 Slot 數規則，即每一次都將檔案延伸固定、可存放同等數量 Index 的大小。

而實務上並不會讓檔案數量無限制增加，會透過餘數運算縮限 Hash Value 的範圍，原理如下：

其中「3」可以代換為任意整數，取決於最後要保留多少 Bucket 。

Static Hashing 的作法相當直觀，而壞處也十分明顯，若是 Hash Function 轉換出的 Hash Value 大量分布在少數值上時，查找這些檔案的時間就會大幅增加。

2.1.2 Extendable Hashing

Extendable Hashing 的用意在於，由於Collision無法避免（尤其在 Hash Value 被縮限過的情形下），於是轉而設法降低往 Bucket 搜尋時的成本。其結構如下所示：

設計上在 Bucket 前加入一層 Directory ，每當有新的 Index 加入時，針對其 Hash Value 取其 Binary Value ，如：

hash(index value) = 13 -> 1101

再對 Binary Value 取倒數 Global Depth 個 Bits ，決定要插入的 Bucket。延續上例：

1101 -> 01 -> 此新 Index 插入 Bucket B

其中：

• Global Depth： 分辨 Index 所屬 Bucket 時需要的最大Bit數
• Local Depth： 分辨 Index 是否屬此 Bucket 時需要的Bit數

當 Bucket 的 Slot 被填滿時，以如下示例方式加開 Bucket 並插入其中：

1. 欲插入一 Hash Value 為20的 Index (10100) ，而 Bucket A 已滿（其餘 Bucket 以*表示填滿的 Slot ）

2. 建立一額外 Bucket A2 ，依倒數 Local Depth + 1 個 Bits 分割 Bucket A的儲存內容，再插入Hash Value 為20的 Index。

3. 拓展 Directory 為 Global Depth = 3，再重新規劃 Directory 與 Bucket 間的連結。此時一樣依照倒數 Local Depth 個 Bit 劃分，因此會有複數個 Directory 指向同一 Bucket 的情形。 而 Bucket A 與 Bucket A2 在切割後，Local Depth 增加為 3，其餘未分割過的 Bucket 的 Local Depth 維持不變。

利用 Extendable Hashing ，能夠以較低成本的方式拓展 Buckets ，同時保留下 Hash-Based Index 快速的特性。

外部參考資料

1. Hash Table on Wikipedia
2. TechBridge 技術共筆部落格 — 白話的 Hash Table 簡介
3. 大毛電腦科學筆記 — #47 資料庫基礎 — 以 Hash 為基礎的 Index
4. 課程投影片（這邊可能有版權上疑慮，因此不便提供，歡迎各位明年透過自己參加 DB/AI Bootcamp 取得）