DDIA閱讀紀錄(10) – 第三章總結:column-based storage

距離上次整10天了,閱讀進度愈來愈不穩定了啊啊啊啊啊。公司讀書會的進度其實已經到第6章,俺已經放棄追車尾燈,改成用自己的步調慢慢看了。

第三章的最後著重在解釋analytics資料庫在檔案的佈局上的一個有趣的實作策略:以資料欄為基礎(column-based)的序列化,而非一般transactional database的資料列為基礎(row-based)。所謂資料列為基礎的佈局,就是把每個資料列(row)一個接一個地寫到檔案中,而column-based就是反過來:把每個資料欄(column)一個接一個地寫到檔案中。會這樣做是因為硬碟的讀取頻寬有限,但統計分析經常要對百萬級以上的資料做運算,但同時又只需要少部分欄位即可。以資料欄為基礎去序列化,就可以有效做到只讀取需要的欄位了。

舉例來說,假設我們是個超級水果電商,我們可能會有長這樣的資料庫:

那麼,如果是資料列為基礎的檔案佈局概念上就長這樣:

那麼資料欄為基礎的佈局就大約是這樣:

從上圖也可以觀察到兩件事: 第一,資料列因為被以欄位打散到許多檔案中,因此一個資料欄檔中的順序是非常重要的,因為那是我們重建一個資料列的唯一依據。第二,因為一個欄位的值域通常不大,因此很容易壓縮,例如書中用的例子是run-length encoding。

但這樣一來column-based的資料庫寫入上會需要不同的策略。像B-tree那種會需要in-place寫入並維持排序的檔案結構自然是不行的,因為一個資料列現在可以橫跨數千個欄位檔,如果要從中間插入一個資料欄,那就意味著要去動那數千個欄位檔,保證機房人員整天換硬碟換到手軟,硬碟廠商笑開懷。前面的章節提過的log-structured storage便是一個解方:每次寫入只從檔尾附加(append),並適時進行壓實(compaction)。書上提到LSM-tree可以用,但我有點想像不出來這東西在記憶體中的SSTables(sorted-string tables)要怎麼建。如果是跟一般情形相同的平衡樹,因為本質上還是以資料列為單位,會不會造成什麼困難?還是會針對之後以欄為基礎的序列化做什麼特化?這些細節可能要去看實作才能知道了。

到此第三章終於堂堂結束,接著第四章為「Encoding and Evolution」,乍看之下應該是在說實際將資料序列化到檔案的實作策略 … 吧?這次第三章真的讀很慢,希望這次可以快一些。

DDIA閱讀紀錄(9) – 第三章續:從OLTP到OLAP

(進度:loc 2353 – 2540)

又一個星期沒寫了 … 恐怖,專案死線太恐怖了 …

這次讀的段落雖然觸及的主題很多,但重點其實是要從前段以線上即時應用為主的線上交易處理(OLTP,Online Transaction Processing),過渡到本章後段的主題線上分析處理(OLAP,Online Analytical Processing)。就個人目前粗淺的印象,那個"OL"真的是挺雞肋的,OLTP出生的年代線上與否是件大事,但OLAP就不一樣了,一方面線上或線下並不是重點,另一方面以其探討的架構來看自然是跟大型的資料中心有關,那就一定是線上的。或許只是因為和OLTP對稱,只好硬是冠個OL上去吧?

中間的過渡主題包括fuzzy indexes,full-text search和in-memory database,但都只是蜻蜓點水式帶過,尤其前二者並沒有太多深究,只有指出為何fuzzy indexes和full-text search會需要不同的索引結構。至於in-memory database,很有趣的是因為今日從database engine乃至OS都有自己的caching機制,導致in-memory database真正有效益的地方不在於查詢與讀取,反而是因為在寫入時它不需要轉換成硬碟需要的格式,例如序列化。

過渡之後,本章堂堂進入analytical data的世界。在本章開頭,作者就有指出transaction data和analytical data由於目的和資料量級的差異,存儲策略會完全不同。書中的這個表格總結得不錯:

簡單來說,資料分析的應用大多是一次抽出大量資料出來作統計分析,而當服務規模夠大,直接在production database上做這件事很容易造成整個服務停擺,弄得operation team森七七,系統部門和資料分析部門間烏煙瘴氣。為了兩邊都能做好自己的工作,才衍生出透過ETL程序(extract-transform-load),把資料定期轉到另外的"data warehouse",讓資料分析師們可以有個地方愛怎麼搞就怎麼搞,operation team保有內心的祥和,從此和氣生財,大家都過著幸福快樂的生活。

WordPress.com的作法大致上與書中相符。內部有自己維護的ETL程序會把最新的production data輸入到一個Hadoop cluster中,再透過Hue、Looker、以及N種自幹的資料分析工具去找出需要的資料。至於production database上則有作一系列的保護措施,盡量避免OLAP量級的query被某個沒睡飽的工程師跑到,但並沒有很完美就是了。

下個段落開始要提到analytical datastore的存儲策略,標題是「column-oriented storage」,希望不會又是一週後才寫了。

DDIA閱讀紀錄(8) – 第三章續:從底層檔案結構到索引結構

(進度:loc 1668 – 2353)

爆忙了一陣,竟然已經整整一週沒繼續寫這個系列了。恐怖,在家上學太恐怖了 …

這個部分首先從兩種database engine底層常見的檔案結構開始提起:LSM-tree與B-tree。這讓我回想起了大學時代修檔案結構(file structure)的血淚史,期末作業就是實作一個最基本的B-tree,後來太多人卡住,大家還聯合起來去向教授求情,才得以寬限一週。總結來說,LSM-tree(log-structured merging tree)因為針對硬碟的sequential性質去特化的存儲策略,對側重寫入的應用會有較佳的表現;但B-tree則是四平八穩,因為就是棵平衡樹,在讀取上通常表現不錯,寫入上因為隨機存取多的關係會比前者弱一些,且容易有空間破碎的問題。雖然概念上是這樣,到底何者對自身的應用才是最適合的,還是要靠實驗分析才有辦法知道。

其實就像學資料結構(data structure)一樣,許多資料結構雖然不明講,但大致上是基於von Neumann架構來設計的東西,所以實作與應用上其實都有考量到硬體性質。B-tree和LSM-tree也不例外,整個實作策略上精密地考慮了傳統硬碟的特性:存取時間長、循序讀寫佳、隨機讀寫不行,以及一定要考慮到當機復原,因為寫到硬碟裡的東西不像記憶體裡的大不了重開機治百病。

段落的最後以索引結構作結,簡單說就是這個key-value pair裡,value到底要存在哪。它可以是直接inline或說in-place跟key存在一起成為所謂的clustered index,也可以是一個heap file,也有可能是介於兩者之間,一部分在heap一部分跟index在一起成為所謂的covering index。這裡也順便提到以R-tree為代表實作的spatial index,可用於做multi-dimensional的range queries,這部份我就沒什麼實務經驗了。

下一個段落要進入Full-test search和fuzzy indexes了,這個部分和analytics data storage是我最想了解的部分,好興奮啊!希望明天不要又忙到沒時間看了啊啊啊啊啊。

DDIA閱讀紀錄(7) – 第三章:令人臉紅心跳的Storage and Retrieval

(本日進度:loc 1900 – 2032)

天啊,今天第一次開始讀第三章,只能說太精彩了。繼第二章走訪各data model的性質後,本章進一步深入到database engine的存取實作概念。雖然我現在才剛讀完一開頭一點點,但真的是讀到忍不住啊啊啊喔喔喔又喘又叫的,旁人看到搞不好以為我在讀的是官能小說。哼哼,誰說讀技術書籍不能高⬤的?

本章以一個「世界上最簡單的資料庫」開始,因為實在太精簡了,值得在這邊照抄一下:

#!/bin/bash

db_set () {
    echo "$1, $2" >> database
}

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

這種append-only的讀寫策略很顯然寫入非常有效率,但讀取會是一場災難。從這裡,作者進一步帶出hash indexes的概念:透過一個在記憶體中的hash map去儲存從key到file offset的map來解決讀取效率問題,同時指出任何index都會增加寫入的overhead,這也是為什麼幾乎所有資料庫都不會預設index。這讓我想起以前年少不懂事,曾經搞出過index file比實際資料還龐大的烏龍。

由於是append-only,那代表任何對已存key的更新或刪除事實上是透過在檔案尾端新增一筆相同key的紀錄來完成。雖然概念上簡單,但書中指出這在實作上其實有很多挑戰,例如空間使用效率上需實作compaction來把所有相同key的records合為1個,以及把一個資料庫檔案切成多個"segment"等等。

既然有了這組map,那這代表我們可以直接in-place覆寫檔案來實作update嗎?作者在這裡回顧了上面的極簡資料庫,指出這種append-only的log structure其實出乎意料地有效,因為它是一種sequential operation,這在過去磁盤為主的硬碟尤其重要;上面提到的compaction若造成segment merge,也會是sequential operation。

實作以上hash indexes的代表性key-value store為Bitcask,稍微看了一下它的repo,似乎相關應用還不少。

段落的最後作者指出這種資料庫的兩大限制:

  1. 由於整組hash map必須都在記憶體中,如果鍵值太多塞不下就不適用
  2. Range queries不佳,例如找出kitty00000 – kitty99999間所有鍵值會需要把整個hash map巡覽一遍

以此為引,下一個段落要開始講沒有這兩項限制的SSTables與LSM-Trees了。

太興奮了啊啊啊啊啊啊啊啊!!

DDIA閱讀紀錄(6) – 第二章完:Datalog,總結

週末盡可能地找空閒時間讀,終於把剩下的最後一點點讀完了。

最後一段介紹Datalog,標題是「The Foundation: Datalog」,因為它是在1980年代從學術界開展出來的query language,盡管在當年並未在實務上獲得成功,作為QL的老前輩,其作為催生其他QL的基礎可謂功不可沒。

應該啦,書上這麼寫,我就這麼信了。

Datalog是一個類Prolog的logical language。大學時代在學Programming Languages時我就搞不懂,現在看了還是滿頭問號。所以請原諒我寫不出什麼像樣的心得,因為心得就只得一句花惹發

有意思的是學到有個叫Datomic的資料庫就是採用Datalog,看起來挺新穎的。這讓人聯想到因為Elixir重新讓世人認識的Erlang,又有點像超前時代太多而不受重視的藝術品,因緣際會等了數十年才得以重見天日。資訊科學的歷史中還有多少這樣靜待發掘知識珍寶呢?

下回第三章:「Storage and Retrieval」,要進入database engine的實作世界了,有種好硬好硬的預感 …

DDIA閱讀紀錄(5) – 第二章續:初探Graph Data Model大觀園

(進度:loc 1327 – 1668,昨天沒能抽空出來寫,因此這是兩天各讀個20分鐘左右的量。希望以後可以盡量避免這個情形)

從這個段落開始,本章堂堂從個人略懂得relational model與document-based model進入Graph data model。作者手先帶讀者認識上圖的範例,接著用PostgreSQL的語法示範這樣的資料在relational資料庫中可能會長什麼樣子,再引領讀者思考我們可以「問」這dataset的問題,例如:哪些人出生在英國但目前住在美國。透過這樣的思考練習,很快就會發現,雖然我們可以把這樣的資料在relational database裡表述出來,但query會非常難寫。以上例來說,透過「within」表現的從屬「美國」的「地區」關係很難預先說有多少層,這代表很難預先知道到底要寫幾個join,雖然有些資料庫現在有recursive join這種超魔幻的東西,但 … 就太魔幻了。在這基礎下,本章開始介紹Cypher QL與neo4jSPARQL與Triple-Stores,以及因為異曲同工之妙而常被放在一起討論的RDF和semantic web。

因為我過去從來沒接觸過這種database,整個段落讀來讓我覺得眼界大開。雖然沒有實際用過,但我還蠻喜歡triple stores的概念的:不刻意區分vertices與edges,而是把一切都編為"subject-predicate-object"的三元組。因此,Cypher QL在撰寫時會需要考量到條件式放的是vertices還是edge,SPARQL可以不用考慮這件事。當然,實用起來我會不會還持同樣意見就是未知數了。

段落的最後作者花了一整頁的篇幅解釋Graph data model與前面提過已經凋零的network model的不同。雖然概念上同樣都是表現graph,但兩者的實際資料結構差異使。總結起來個人覺得最關鍵的差異有二:其一,network model真的把資料存儲成巢狀結構,因此要存取entities的唯一方法就是真的去巡覽整個graph;但Graph data model並沒有這個限制,必要的時候甚至可以用直接的index來存取各entities。其二:network model因為這樣的設計,只能用imperative query language而非像graph data model有很好的declarative query language可以使用。對於QL方面的差異,我想network model如果活得夠久搞不好能獲得解決,但也有可能先天上的限制讓它無法這麼做就是了。

下一段的標題是「The foundation: Datalog」,又是一個完全沒看過的東東,令人期待。

DDIA閱讀紀錄(4) – 第二章續:天下大勢,分久必合,合久必分

(本次進度: loc 1065 – 1327)

今日讀的段落從data locality開始,declarative vs imperative的query language,再到map-reduce的基本介紹。這次幾乎每個段落都有具體的程式碼供參考,來更進一步使其論點更加具體。有趣的是,我們在這幾個段落可以一直看到乍看之下立場相對的解決方案從光譜的兩側出發,發展到一定程度後,卻又會在某些地方交匯。

例如data locality指的是document-based data model能一次就查詢出一個document的所有相關資料,但relational data model卻會需要進行多次的查詢來重建之。於是relational陣營便加入了可以在資料庫中直接存儲structured data(XML或JSON/BSON)的功能,甚至也可以直接對該structured data內的欄位進行檢索。但document-based陣營日子也不好過,一次就帶出整個document代表著不管你需不需要,一次噴出來的資料就是那麼大,如果只想更新一小部分也不是很有效率。後來就有些實作品開始加入了類似relational的query language和join,例如RethinkDB。

declarative vs imperative的部分,作者就「改變特定元素的背景色」一例,分別用CSS和JS來寫來呈現declarative language與imperative language的差別。雖然他強烈認為declarative language較適合資料庫應用,例如基於relational algebra的SQL query langauge,但仍有imperative language更加自然的情境,例如MongoDB的map-reduce query。但後者後來仍加入了aggregation pipeline以長得很像JSON的方式來引入類似的declarative query language。(題外話,這讓我聯想到ElasticSearch,這種長得很像data的語言我真的 … 不行啦啊啊啊 Q_O)

因此看完這幾個段落後,才讓我覺得「天下大勢,分久必合,合久必分」。作者認為綜合relational與document-based會是不錯的方向:

A hybrid of the relational and document models is a good route for databases to take in the future.

但最終這種集百家之長的東西常常都會變得過於複雜,然後又會有一群人根據自己的偏好取出「好的元素」,創造新的分支出來吧?看看那個C++,D,和Rust。

下一個段落要開始談的graph-based model就是我沒什麼經驗的部分了,令人期待。

DDIA閱讀紀錄(3) – 第二章續:歷久彌新的The Great Debate

(本次進度:location 907 ~ 1065)

上次提到多對一或多對多的資料關聯性對data model帶來的挑戰,接下來的段落更進一步深入了這個主題,揭露了我過去不知道的歷史:由IBM的Information management system為代表的hierarchical model,以及作者稱為「the great debate」,至今仍爭吵不休的relational model與network model之戰。

DDIA閱讀紀錄(2) – 第二章:從Relational model到Document-based model

(本次進度:從location 737到907,這本kindle版沒有與實體書對應的頁數,只好用location number)

首先看看那張精美的data model地圖,除了繪製功力相當高超外,仔細看會發現每個「地點」和「道路」似乎都是有它的道理的。

本章開頭幾個段落相當精彩,首先從relational model於1970年初次由Edgar Codd提出說起。它接下來數十年間奇蹟般地歷久不墜,甚至從企業級資料處理逐漸普及,如交易資料、物流資料、甚至批次處理的資料存儲,甚至現在移動裝置上也有SQLite了。

25 – 30 years –– an eternity in computing history.

我蠻喜歡作者這樣的形容,這確實是項不簡單的創舉。

DDIA閱讀紀錄(1) – 第一章:好的開始,但擔心理論多於實務

就像大部分的技術書籍一樣,第一章主要是在為整本書所涵蓋的內容立下框架:緣起、全書大綱、專有詞定義、哪些主題是著墨的重點,哪些是刻意不提的部分(例如安全性,因為安全性本身就夠寫一整本書了)。

可能出自作者的個人興趣,他會把該章節要講的內容用古歐洲航海圖的風格繪成一張資訊圖,例如本章的如下:

第二章的就更絕了,但那就等到寫第二章的時候再說 🙂

本章把data-intensive application的三大面向定義出來:可靠性(Reliability),擴增性(Scalability)與維護性(maintainability)。雖然書中已經有非常詳盡的定義了,這裡我還是嘗試用自己的話語盡可能精簡地闡述出來,個人經驗上這麼做對知識的內化非常有助益。

  • 可靠性:系統能在何種範圍的硬體、軟體、人為錯誤內維持可接受的服務品質。
  • 擴增性:給定一組負載參數(load parameters),系統的主要效能指標如何與之關聯?
  • 維護性:系統對於各種環境變遷因素的適應能力。例如:開發小組換人,運行小組換人,市場需求改變,抽換軟/硬體組件,等等等等。

雖然第一章整體讀來是非常優秀的總論,但整個基調感覺過於偏重理論,唯一貼近實務的僅有關於Twitter如何特化設計timeline的資料模型來有效發布推文(僅有幾十個跟隨者的用戶和有幾百萬跟隨者的用戶需要的策略大幅不同)。

希望後續的章節能逐漸把理論和實務的比例推到5:5,甚至4:6。