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

分類 碼農噥噥在 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

分類 碼農噥噥DDIA閱讀紀錄(7) – 第三章：令人臉紅心跳的Storage and Retrieval 有 2 則迴響

(本日進度：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，總結

分類 碼農噥噥在 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大觀園

分類 碼農噥噥在 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與neo4j，SPARQL與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) – 第二章續：天下大勢，分久必合，合久必分

分類 碼農噥噥在 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

分類 碼農噥噥在 DDIA閱讀紀錄(3) – 第二章續：歷久彌新的The Great Debate 發表留言

(本次進度：location 907 ~ 1065)

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

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

DDIA閱讀紀錄(2) – 第二章：從Relational model到Document-based 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.

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

Continue reading ➞ DDIA閱讀紀錄(2) – 第二章：從Relational model到Document-based model

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

分類 隨筆雜談在 DDIA閱讀紀錄(1) – 第一章：好的開始，但擔心理論多於實務 發表留言

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

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

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

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

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

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

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

DDIA讀書會開始啦！

分類 碼農噥噥DDIA讀書會開始啦！ 有 2 則迴響
Book cover of Designing Data-Intensive Applications

從本週開始，公司內部新一波讀書會正式啟動。過去個人參加過無數讀書會、技術分享會，最後都會在緊迫的專案壓力下不了了之。這次又有新的一批人熱血充腦聚在一起，何不再嘗試一次？

這次的讀書會叫「Automattic Salon」，這裡的salon可不是造型沙龍，指的是「gathering」：一群人聚集起來，透過對話進行知識交流或娛樂。這次的讀書會主辦人想必也是經歷過不少失敗的讀書會，他收集大家半途放棄的閱讀經驗後，總結出幾個要點當這次讀書會的指導原則：

  • 不要求快，要慢而深入
  • 要為自己而讀，只是聽取他人的讀書心得意義不大
  • 需鼓勵同儕交流

在這樣的方針下，我們開了一個新的內部p2，訂立以下進行方式：

  • 目標每週讀一章
  • 在每週一，主持人會張貼新的章節討論串，以及兩個提問
  • 每個人在讀完後在該討論串張貼自己的讀後心得，以及對提問的回答

以及一個新的slack channel方便較即時、隨興的交流。

因應上次的30天跳繩挑戰成功，我不禁想，如果每天都把自己讀的份寫個總結，會發生什麼事呢？於是決定開啟這個新的每日洗版系列來實驗看看。

寫這篇文章的當下其實我已經讀到第二章了，看能不能利用這個週末先補上。

每日跳繩1000下–第三十日

分類 生活日常每日跳繩1000下–第三十日 有 2 則迴響

終於到了總結的日子啦！再怎麼說也是最後一天了，時機再歹也是很輕快就完成了。

總結一下本次與過去幾次的數據：

4/194/265/35/105/18總結變化
體重83.284.383.384.483.5+0.3
體脂25.5%25.7%25.2%25.3%24.4%-1.1%
骨骼肌肉率–31.6%31.9%31.8%32.3%+0.7%
基礎代謝率18071823181118281820+13
內臟脂肪等級1212121212–
體年齡4949484949–

數字上幾乎沒有太大變化啊，不過體脂應該是確實下降了一滴滴吧？

本來打算寫一篇詳細的心得文來總結，因為還要去忙著因應許多新宣布的疫情措施，這裡就簡單列表帶過了：

  • 網路上可以找到很多人進行一個月後減肥成果顯著，甚至有人10天就看到成果的。我想那可能是他們之前運動量就不高？因為我本來就不是完全沒運動，如果不搭配飲食調整，單靠增加這每天20分鐘左右的運動量，並不會有太顯著的成效。
  • 雖然數字上沒有太大變化，體力、活力和跳繩技術確實有感提升了，心理素質上也產生了些正向的變化。即使游泳圈還在，這次挑戰仍是相當成功。
  • 每天一篇隨性的文章紀錄搭配固定的檢查點，這樣簡單的動作卻構築了完成這次挑戰所需要的動量。是不是可以把這個方法應用到其他地方呢？例如從來沒讀完的書或是實作一直睡在筆記本裡的點子。

接下來我打算繼續維持這個習慣，或許還會增加一些強度，只是不會再每天紀錄。少了這個動作，一個月後會是什麼樣子呢？