Tomu's Blog
0%

讀書筆記｜DDIA｜Chapter 2. Data Models and Query Languages

Posted on In

只要提到 System design 的推薦書籍，總是會看到 Designing Data-Intensive Applications 這本書。實際上閱讀後覺得雖然偶爾會有點偏向理論，但內容的確非常廣泛，且介紹概念的情境、案例非常豐富，目前已經閱讀的前半本，每個章節都讓我收益良多，也因此想挑選這本書來整理摘要與筆記。

本書的第一章節主要在討論一個好的 Software service，其背後的 Data system (如 Database, message queue, cache, search indexes 等 tool) 該如何設計、建構。書中以三個面向: Reliability, scalability, maintainablity 來探討，非常值得一讀。不過由於並未涉及太多實際應用的技術，建議直接閱讀即可，關於本書的讀書筆記也將從第二章，也就是這篇文章開始做。

本文的圖片和程式碼都來自原書內容。

Data Model

Application 常常建立在分為多層 (Layer) 的 Data model，對於每層的開發者來說，只需關注如何用下一層的 Interface 來表現本層 (建模) ，如此透過抽象化底層實作來降低開發的複雜度。

graph TD;
    api[API]-->struct[Data Structures]
    struct-->store[Data Storage: JSON/XML/relational/graph data]
    store-->bytes[Bytes in memory, on disk, or on a network]
    bytes-->signal[Electrical currents, pulses of light, magnetic fields]

世界上存在很多 Data models，各自有其特性與適用情境。接下來的小節會介紹上圖 Data storage 那層的 Relational, document 以及一些 Graph data model。

Relational Model Versus Document Model

SQL and NoSQL

SQL (Relational model) 是至今最為盛行的一種 Data model，本節帶過其歷史，並繼續介紹到 NoSQL 的誕生（Non-SQL, Not Only SQL)，其相對於 Relational database 的優勢為：

  • Scalability: 可以達到更大的 Dataset 與更高的 throughput。
  • 通常為 Open source。
  • Relational model 對部分 Queries 支援性不佳。
  • Relational schema 限制太多，彈性與表意能力太差。

當然不同 Applications 有不同 use case，不同需求下最適合的 Model 也不同，因此這兩者的關係並非互斥而是共存，即 Polyglot persistence。

The Object-Relational Mismatch

為了配合 Application 開發常用的 OO 語言 (請參考 讀書筆記｜Clean Architecture｜Part 2. Programming Paradigms 的介紹)，Relational model 常常需要有一層 Object-relational mapping (ORM) 的 Translation layer 來解決 Object (Application code) 和 Relational data 間的 impedance mismatch。

note-ddia-02-cv

不過 ORM 無法完全消除 Object 和 Relational data 的不同。例如 one-to-many relationship，如上圖一個 user 可能有多個工作經歷 (positions)，多個教育背景 (educations)，其 Relational schema 設計可能有以下幾種：

  1. 較傳統的方式是正規化將工作經歷、教育背景等資訊各自存在獨立的 Table positions, educations，再透過 Foreign key referernce 建立與 users 的聯繫。
  2. 較新的 SQL standard 有支援 Structured datatypes，如 XML, JSON document，可以讓 users 的一個 Column 就能存多個工作經歷、教育背景 (muti-value data)，並支援對這些 Document 的 Query 與 Index。。
  3. 可以自行 encode 多個工作經歷、教育背景為 XML, JSON document，並儲存於 Text column，由 Application 拿到後自行 decode。不過這種方式就沒有辦法直接透過 Database 查詢到其中的值，也無法 Index。

如果 Relational model 設計成第一種 multi-table schema，則需要透過多個 Query 或將不同表格透過join 結合，才能查詢到想要的結果。而如果後兩者較不會遇到這樣的問題，也可以說 Document model 較適合處理 one-to-many relationship data。

工作在開發時常用 soci 這個 LIbrary 來實作 ORM，由於在 Schema 設計上還是比較常使用第一種，也的確會遇到上文提到的問題。發多個 Query 很容易遇到 N + 1 queries 的效能問題，因此是不能接受的，因此目前常用的解法是針對每個需要 Join 的場合先建好 View，或是直接放棄ORM 改用 Raw query。

Many-to-One and Many-to-Many Relationships

在上圖的履歷可以看到 user 的 region, industry 資訊是存為 id 而非有意義的文字，其實就是我們常說的正規化 (normalization) 去重複，能讓這些資訊更好維護。不過這樣的正規化會導致 many-to-one, many-to-many relationship 的產生，即 多個 user 可能都居住於 一個 地區，或 多個 user 各自的 多個 工作經歷可能都含有某公司。

  • Relational model：和 one-to-many relationship 相同都可以用 join 結合後查詢。

  • Document model：支援性較差。

  • 以前出現過和 Document model 有類似特性的 Hierarchical model 與 Network model，當時就有討論 Many-to-xxx relationship 在不同模型下的支援。

    • Network model 主要是由 Application developer 決定 Query 的 access path，這和這篇文章開頭 Data model 的分層相違背。

    • 相對而言 Relational database 通常由 Query optimizer 決定 access path，雖然 Query optimizer 的實作難度很高非常複雜，但一勞永逸，從長遠角度來說是較好的選擇。

    • 為了避免步上這些歷史上的 Model 的後塵，現行的 Document model 有 Document reference，類似於 Relational model 的 Foreign key，用來支援 join 等 Query。

Relational Versus Document Databases Today

從 Data model 的角度來說這兩種 Database 各有優勢：

  • Relational：對 many-to-one, many-to-many relationship data, join 的支援較好。
  • Document：schema flexibility, locality。

不過對於高度關聯的資料，雖然 Relational model 是優於 Document model 的選擇，但後文將介紹的 Graph model 是更適用的選擇。

本小節雖然在比較 Document 和 Relational model，但這兩者並不是互斥的：

  • 如前文提到有些 Relational database system 有支援 Structured datatypes，如 XML, JSON document。
  • 有些 Document database 有支援 Relational-like joins。

如果將來有更多 Database 同時支援這兩種 Model 的特性，對於 Application 來說也更便於挑選適合他們需求的功能。

Schema Flexibility in the Document Model

前文提到 Document model 具有 Schema flexibility 的優勢，相對於 Relational model 必須嚴格根據 schema 進行寫入 (schema-on-write)，Doucment model 通常不具有這樣的限制，Document 如 JSON 可以寫入任意 key-value pair，自由度較高，但也因此在讀取時不保證資料存在 (schema-on-write)。詳細比較兩者的差異：

schema-on-write schema-on-read
static (compile-time) type checking dynamic (runtime) type checking
強型別 弱型別 (record 可以是不同結構的, heterogeneous)
性能較佳 讀取時動態解析，因此性能較差

舉例來說，如果新版本想要對 schema 進行改動，如果是 schema-on-read 的 JSON，則對於未更新的既有資料 Application 可以直接在 code 中處理：

1
2
3
4
if (user && user.name && !user.first_name) {
	// Documents written before Dec 8, 2013 don't have first_name
	user.first_name = user.name.split(" ")[0];
}

而 schema-on-write 的 Relational schema 則需要 downtime 進行 Migration / Upgrade：

1
2
ALTER TABLE users ADD COLUMN first_name text;
UPDATE users SET first_name = split_part(name, ' ', 1);

以上面用來 Migrate 的 SQL 來說，ALTER 通常不會造成太大的開銷，不過 UPDATE 在資料量大時會很慢不太適合，通常會建議用 ALTER ... WITH DEFAULT，或類似 Document model 的做法，一開始給 default 值 NULL，讀取時發現是 NULL 時再 UPDATE。

Data Locality for Queries

  • Document model 通常存於 encoded 為 JSON, XML 的 string，或其 Binary 格式。
    • 存取整個 Document，則會有 storage locality 的效能優勢。
    • 但由於通常都需要將整個 Document load 進來才能操作，因此會建議控管每個 Document 的大小。
  • 其他 Data model 也有類似的將資料 grouping 以達到 Locality 的優勢，例如 Oracle 的 multi-table index cluster tables。

Query Languages for Data

這個小節前半部分主要在介紹 Imperative 和 Declarative 兩種 Programming language，以 Query language 來說，Imperative language 像是一步步下指令來取得資料 (Traverse 全部資料並將符合條件的資料加入結果)；Declarative language 則是直接宣告欲取得的資料的特徵 (需滿足什麼條件、怎麼呈現)。後者通常更簡潔，且隱藏了 Database engine 的實作細節，讓 Database system 有機會決定要用怎麼樣的 Algorithm 查詢，例如是否要平行運算。

後半部分則介紹了 MapReduce，由於其在第十章節才會詳細介紹，這個小節只簡單介紹 MongoDB 中的 MapReduce。以統整每個月觀察到的鯊魚數量報告為例，以 PostgreSQL 的 Declarative SQL 和 MongoDB 中的 MapReduce 比較：

1
2
3
4
# PostgreSQL
SELECT date_trunc('month', observation_timestamp) AS observation_month, sum(num_animals) AS total_animals
FROM observations
WHERE family = 'Sharks' GROUP BY observation_month;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// MongoDB
db.observations.mapReduce(
  function map() {
    var year = this.observationTimestamp.getFullYear();
    var month = this.observationTimestamp.getMonth() + 1;
    emit(year + "-" + month, this.numAnimals);
  },
  function reduce(key, values) {
		return Array.sum(values);
  },
  {
    query: { family: "Sharks" },
    out: "monthlySharkReport"	
  }
);

SQL 的範例較好理解因此這邊略過說明，MapReduce 的部分處理步驟如下：

  1. 只要是符合 #12 Query 條件的 Record，就會對其呼叫 #3 實作的 map function，每個 Record 最後需回傳 (emits) 一個 key-value pair，以 Record 如下為例會回傳 {1995-12, 3}。

    1
    2
    3
    4
    5
    6
    {
      observationTimestamp: Date.parse("Mon, 25 Dec 1995 12:34:56 GMT"),
      family:     "Sharks",
      species:    "Carcharodon carcharias",
      numAnimals: 3
    }

  2. 對所有 key-value pairs 根據 Key 分組，對每一組有相同 Key 的 key-value pairs 呼叫 #8 實作的 reduce function，加總所有 Value。

  3. 將結果寫至 #13 的 output 中。

MapReduce 這個 Programming model 還有一些特性如下：

  • map, reduce 在 Functional programming language 中常被使用，這兩隻 Function 常對實作有所限制，以利於背後平行分派，如限制其為 pure function (同樣 Input 就會得到同樣 Output、不能有 Side effects)。
  • 是 Low-level programming model，即有可能是 SQL 這個高階宣告式查詢語言背後的實作。
  • 這邊的範例使用到 Javascript，不過這並非是 MapReduce 的專利。

另外也可以利用 MongoDB 2.2 開始支援的 aggregate pipeline 來讓其更貼近 Declarative query language 的特性：Query optimizer 有更高的自由度去改善此 Query 的效能。

1
2
3
4
5
6
7
8
9
db.observations.aggregate([
  { $match: { family: "Sharks" } },
  { $group: {
    _id: {
      year:  { $year:  "$observationTimestamp" },
      month: { $month: "$observationTimestamp" }
	},
	totalAnimals: { $sum: "$numAnimals" } }}
]);

Graph-Like Data Models

前文提到對於高度關聯的資料 (Social graph, web graph, road networks)，Graph model 是更適用的選擇，包含：

  • Property graph model
  • Triple-store model

相關的 Query languarge 則有

  • Cypher
  • SPARQL
  • Datalog

不過這篇文章只打算介紹其中 Property graphs 和 Cypher 的部分來大致了解 Graph model 的 Use case，其餘就等有碰到再回去書中查詢。以下圖中一對夫妻的 Social graph 為例 ：

note-ddia-02-graph

Property Graphs

Property graph model 包含 Vertex 和 Edge，我們用 Relational schema 來表示這兩者的組成：

1
2
3
4
5
6
7
8
9
10
11
12
13
CREATE TABLE vertices (
  vertex_id integer PRIMARY KEY,
  properties json
);
CREATE TABLE edges (
  edge_id integer PRIMARY KEY,
  tail_vertex integer REFERENCES vertices (vertex_id),
  head_vertex integer REFERENCES vertices (vertex_id),
  label text,
  properties json
);
CREATE INDEX edges_tails ON edges (tail_vertex);
CREATE INDEX edges_heads ON edges (head_vertex);

  • 和 #12, #13 建立的 Index 類似，Property graph model 可以快速找到和各個 Vertex 的 Outgoing / Ingoing edges。

  • label 可以用來表達不同的關係，如上圖 Social graph 的 born_in, lives_in, within, married。

  • 有很多關係是傳統 Relational schema 難以表達的，例如不同國家對於行政區的劃分個有規則、Lucy 現在住在 City 但出生於 State。

  • Graphs are good for evolvability.

The Cypher Query Language

Cypher 是用來查詢 Property graphs 的 Declarative query language。

  • Cypher query to add data:

    1
    2
    3
    4
    5
    6
    7
    CREATE
      (NAmerica:Location {name:'North America', type:'continent'}),
      (USA:Location {name:'United States', type:'country'}),
      (Idaho:Location {name:'Idaho', type:'state'}),
      (Lucy:Person {name:'Lucy'}),
      (Idaho) -[:WITHIN]->  (USA)  -[:WITHIN]-> (NAmerica),
      (Lucy)  -[:BORN_IN]-> (Idaho)

  • Cypher query to get data matching conditions:

    1
    2
    3
    4
    MATCH
      (person) -[:BORN_IN]->  () -[:WITHIN*0..]-> (us:Location {name:'United States'}),
      (person) -[:LIVES_IN]-> () -[:WITHIN*0..]-> (eu:Location {name:'Europe'})
      RETURN person.name
    • 用類似 Regular expersion 的方式 Match (WITHIN 出現 0 或多次)。

  • 和一般的 Declarative language 相同，我們不需要擔心執行的實作細節。

Graph Queries in SQL

之前有用 Relational schema 來表示 Graph data 的 Vertex 和 Edge，換言之我們可以將 Graph data 以 Relational model 儲存，對於前面 Cypher 的 :WITHIN*0..，SQL 可以用 recursive common table expressions (WITH RECURSIVE) 來實現：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
WITH RECURSIVE
  -- in_usa is the set of vertex IDs of all locations within the United States
  in_usa(vertex_id) AS (
      SELECT vertex_id FROM vertices WHERE properties->>'name' = 'United States'
    UNION
      SELECT edges.tail_vertex FROM edges
        JOIN in_usa ON edges.head_vertex = in_usa.vertex_id
        WHERE edges.label = 'within'
  ),
  -- in_europe is the set of vertex IDs of all locations within Europe
  in_europe(vertex_id) AS (
      SELECT vertex_id FROM vertices WHERE properties->>'name' = 'Europe'
    UNION
      SELECT edges.tail_vertex FROM edges
        JOIN in_europe ON edges.head_vertex = in_europe.vertex_id
        WHERE edges.label = 'within'
  ),
  -- born_in_usa is the set of vertex IDs of all people born in the US
  born_in_usa(vertex_id) AS (
    SELECT edges.tail_vertex FROM edges
      JOIN in_usa ON edges.head_vertex = in_usa.vertex_id
      WHERE edges.label = 'born_in'
  ),
	-- lives_in_europe is the set of vertex IDs of all people living in Europe
  lives_in_europe(vertex_id) AS (
    SELECT edges.tail_vertex FROM edges
      JOIN in_europe ON edges.head_vertex = in_europe.vertex_id
      WHERE edges.label = 'lives_in'
  )

SELECT vertices.properties->>'name'
FROM vertices
-- join to find those people who were both born in the US *and* live in Europe JOIN born_in_usa ON vertices.vertex_id = born_in_usa.vertex_id
JOIN lives_in_europe ON vertices.vertex_id = lives_in_europe.vertex_id;

Cypher 只需要 4 行即可完成的 Query 以 SQL 實現需要 30 行左右，只能說不同的 Data model 真的各有 Use case，Application 需要根據需求挑選適合的 Data model。

Summary

We have different systems for different purposes, not a single one-size-fits-all solution:

  • Relational model

    • Targeting use case: many-to-many relationships (while graph maybe more suitable when data is highly connected).
    • Explicit schema, which enforces the structure during write operations.

  • NoSQL

    • Document model:
      • Targeting use case: data comes in self-contained document.
    • Graph model:
      • Targeting use case: anything is potentially related to everything.
    • Typically implicit schema, where the structure is handled during read operations.
      • Easier to adapt applications to changing requirements.

  • Full-text search

    • Unmentioned in this chapter. Search indexes would be touched in Chapter 3 and Part III.

Each data model comes with its own query language or framework:

  • SQL, MapReduce, MongoDB’s aggregation pipeline, Cypher, SPARQL, and Datalog.