System Design: 系統架構基礎 — 資料模型
如何選擇應用程式該用何種資料庫,此篇文章向你介紹三個主流資料模型,文檔(Document)、關聯(Relation)和圖(Graph)。
什麼是資料模型 (Data Model)
大部分的應用程式都是透過抽象介面掌控資料模型(Data Model)之上,而循序漸進的每一層資料模型,其下一層都有其它資料模型再運作,比如
- 工程師將實際的商業邏輯(像是將貨運、保險或是票務)轉化為資料結構(Data Structure)
- 當工程師要儲存這些資料結構時就必須思考,要使用文檔資料庫(Document Database)的JSON(Tree Model)、關聯式資料庫(Relation Database)的表(Table Model)或是直接使用圖資料庫(Graph Model),將資料儲存永久儲存
- 而資料庫(DBMS)工程師們,除了設計方便查詢、寫入和管理的介面讓開發者使用,還需要設計要如何將這些資料模型寫入到硬碟之中
- 硬體工程師則是思考如何將這些byte透過電流或磁力寫到真實物體上
資料模型主要就是簡化上一層的開發者使用資料的難度,但是提到系統設計,開發者就需要深度的理解每一層資料模型如何運作以及如何表現,這樣才能選出最適合系統的資料模型。
本篇文章主要關注文檔(JSON)、關聯和圖資料模型的使用與抽象表現。
IMS古老的文檔資料庫系統
IMS(Inormation Management System)是IBM在1970年代為了阿波羅計畫商業發行的資料系統,有趣的是它儲存的資料模型跟現在火熱的NoSQL JSON文檔儲存非常相似,是以層次模型(hierarchical model)像是樹狀一樣的資料模型結構,它可以非常簡單的表現一對多關聯的資料,但一到了多對多關聯就束手無策(與現代的Document Database相似),後來的解決方案中最出色的就是現在常用的關聯模型(Relational model)和圖資料庫的前身網路模型(Network model)。
網路模型(Network Model)
網路模型如同字面定義,每筆資料會像是網路節點互相關聯,可以輕鬆地呈現多對多關聯的資料,但受限於當時的硬碟技術無法像現在可以快速的Random Access(隨機存取),而且也沒有提出簡單好使用的抽象介面讓開發者使用,所以在1970年代落了下風。
關聯模型(Relational Model)
關聯模型就是目前眾所皆知的關聯式資料庫,每張表(table)都是每一行(rows)的集合,在由表來表示資料間的關聯,它不需像網路模型般每筆資料都需要透過複雜的訪問路徑(access path)才能到達,而在呈現方面也完美符合人類熟悉的表格資料,操作簡單易懂,需要加資料時在表中插入一行即可。
網路模型與關聯模型都是為了表達多對多關係才由文檔模型衍生。或許當時關聯模型獲得勝利,稱霸了商業領域數十年,但在現在儲存機器高效而且容量可以接受大量冗於的情況下,三種模型都可以有各自的表現空間,這也是近十年NoSQL崛起的原因。
Document and Relation Model
文檔數據庫以MongoDb為例,用Key-Value的方式操作資料再以變動的格式JSON存儲。這通常被稱為無模式(schemaless),但DDIA提到更精準的用詞應該為讀時模式(shema-on-read),也就是在資料儲存的時候可靈活變動,拿出來時才定義資料中每個屬性的意義。這代表可以在應用程式中改寫資料格式與結構,應用時較為靈活與方便。但其中靈活度的trade off就是程式碼會充滿許多特定的程式碼,需要檢查每個拿出來資料的意義,尤其要更動格式還需要額外的程式碼在每次讀取時做檢查。
而關聯資料庫則稱為寫時模式(shema-on-write),在初始化時就需要設計DDL(Database Define Language)強制定義資料模型的外貌,在修改格式時需要很大的開銷,但相對而言當資料模型逐漸穩定不在更動後,程式碼對比於文檔資料庫更加簡潔,因為可以直接使用SQL查詢資料。
開始以DDIA中Bill Gates Linkedin履歷一對多資料模型做討論。Linkedin的功能主要呈現個人履歷,包含簡介、經驗、學歷和聯絡資訊。
如果以關聯式資料模型設計,如下圖。經過正規畫每個會重複的資料都會個別存在不同的Table中,如果資料要傳送給前端,就需要經過這些Table數量的Primary key Index查詢(就此案例為六次),在打包成JSON格式傳送。
如果以文檔資料模型,文檔格式如下。
{
"user_id": 251,
"first_name": "Bill",
"last_name": "Gates",
"summary": "Co-chair of the Bill & Melinda Gates... Active blogger.",
"region_id": "us:91",
"industry_id": 131,
"photo_url": "/p/7/000/253/05b/308dd6e.jpg",
"positions": [
{
"job_title": "Co-chair",
"organization": "Bill & Melinda Gates Foundation"
},
{
"job_title": "Co-founder, Chairman",
"organization": "Microsoft"
}
],
"education": [
{
"school_name": "Harvard University",
"start": 1973,
"end": 1975
},
{
"school_name": "Lakeside School, Seattle",
"start": null,
"end": null
}
],
"contact_info": {
"blog": "http://thegatesnotes.com",
"twitter": "http://twitter.com/BillGates"
}
}
JSON是現在文檔資料庫儲存的通用格式,資料模型會以樹狀的方式呈現,對於此案例如果要抓出Bill Gates的履歷只需要一次的查詢,抓出文檔直接將JSON傳送到前端。
以此案例,關聯與文檔對比,文檔資料模型會有較好的局部性(locality),locality代表著資料存取或是寫入時都是聚集在一片連續的區域中,不需再做其他跳轉搜尋。而關聯資料庫因為正規化(normalization)的關係會將資料切割成不同Table,硬碟需要做多次跳轉查詢。
將此案例再次升級,如果未來此頁面除了單純文本呈現履歷,還需要做公司學校介紹,如下圖。
這樣就會發生如果公司更新資料(簡介、網址、地址),文檔資料庫每個包含此公司的JSON檔案都需要重新寫入,這樣關聯的資料散落在不同JSON文件的定義稱為副本(duplicatoin),每一個JSON文檔都有一份相同定義的資料。而關聯模型如果要作的這樣的功能,保持原狀更改關聯Table資料即可。當然文檔資料模型可以如下圖做文檔間的關聯,這也稱為多對多模型(除了本身持有的個別資料還包含關聯文檔ID)。
透過上面這張圖,可以發現當關聯資料增加,文檔模型會與關聯模型逐漸重疊。這也會回到一開始提到1970年代IMS系統引發的關聯模型討論。不過現在和1970相比資料不再只是讓商業人員用表格的方式查看還包含了網頁呈現,況且文檔模型可以針對重複資料做關聯(減少副本冗於,關聯模型則可以將一些不大會修改的資料作反正規劃處理(減少跳轉查詢),文檔與關聯正在逐步的融合。所以現在並沒有哪種資料模型優於誰的問題,只會有目前的公司的商業應用適合哪種資料模型,當然也可以一起使用。
Relation and Graph Model
上文提到文檔與關聯資料模型,最大的差異在於關聯,若關聯數量上升文檔資料模型要減少副本的話,會逐漸的趨近關聯資料模型,相反的如果要減少關聯跳轉也可以透過將關聯資料模型反正規化。
但如果整個資料幾乎全部都是關聯資料,那圖數據模型可能是最好的選擇。一開始文章提到網路模型與關聯模型,是由IBM的IMS系統衍生出來解決關聯資料問題。但是因為1970年代硬碟隨機讀取效率非常低效,所以關聯資料庫獲得了接下來數十年的勝利,但在現在硬碟隨機讀取成本逐漸降低(未來如果SSD全面取代傳統硬碟,那就更有趣了),所以網路模型的進階圖資料模型也開始逐漸出現在市面上,目前最著名的應該就是Neo4j了(只要逛過一次官網,各種Google ads就會瘋狂打廣告)。
Graph Model基本定義
什麼是圖形資料庫,講白了每一個資料都是一個節點(node)透過邊(edge)去做彼此關聯,將模型攤開就會像是網路的路由圖一樣。
一個Graph Model如上所說會有許多Node和Edge組成。
Node包含了
- 唯一判別(如同Primay Key)
- 出邊 (outgoing edges)
- 入邊 (ingoing edges)
- 屬性 (key — value)
Edge
- 唯一判別(如同Primay Key)
- edge的起點 (tail vertex)
- edge的終點 (head vertex)
- 描述此關聯的標籤
- 屬性 (key-value)
其中Edge的tail和head需要以箭頭來理解, -> 箭頭的尾巴代表著來源,頭則代表目標,所以英文才會以tail=source/head=destination。
如果將圖攤開來看會如下,此範例為人居住的資料關聯。
以Relational Model表示圖
如果以關聯資料庫來表示圖資料模型,需要設計類似下方的DDL(Data Define Language)
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);
下方是Immanuel Trummer教授的設計車站的路線圖資料範例,由關聯模型表達圖資料。
(https://www.youtube.com/watch?v=672Nn0seoIg&list=PLXPbT_PYOiRipfX8zrv_9EpnSOpK9P__j&index=32)
首先需要設計DDL,大致與上面所提的框架相同。
CREATE TABLE Stations(StationID int primary key, name text);
CREATE TABLE Connected(
StationID1 int, StationID2 int,
primary key (StationID1, StationID2),
foreign key (StationID1) references Stations(StationID1),
foreign key (StationID2) references Stations(StationID2)
)
如果要查找P Statoin 到 N Station的路徑,那整個Query語法就會變得很冗長,甚至是有一點複雜不好理解。
SELECT * from Connected C1
join Connected C2 on (C1.stationid2 = C2.stationid1)
join Connected C3 on (C2.stationid2 = C3.stationid1)
... join Connected Cn ...
WHERE C1.name = 'Port Authority'
and Cn.name = 'NYU'
此範例可以看到,關聯資料庫也可以完全表達圖資料模型,只是在搜尋時會非常麻煩,因為圖的搜尋大多是以遞迴(DFS/BFS)的方式搜索,SQL要表達遞迴需要關聯大量table,當然可以設計function取代,但如果使用圖資料庫的搜尋語言就會變得非常優雅與直觀。
Cypher (Neo4j的搜尋語言)
Cypher之於Neo4j等同於SQL之於關聯式資料庫,使用起來跟使用SQL類似,但主要操作圖資料模型,所以表達圖資料會比較直觀,讓開發者比較容易上手。
使用Cypher設計人口居住資料模型,DDL (Data Define Language)如下
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)
而DQL(Query Language)如下,要找到從美國移民到歐洲的人口。
MATCH
(person) -[:BORN_IN]-> () -[:WITHIN*0..]-> (us:Location {name:'United States'}),
(person) -[:LIVES_IN]-> () -[:WITHIN*0..]-> (eu:Location {name:'Europe'})
RETURN person.name
對比於透過SQL查照圖資料模型,Cypher更加直觀與方便。
總結
資料模型是現在應用程式的基礎,因為都需要永久儲存資料,和資料結構相比資料結構注重資料再記憶體中和CPU的互動,而資料模型則是如何從硬碟拿出資料。
文中提到了三種資料模型
文檔資料模型
- 與1970年代的IMS相似
- Key-Value行為,以JSON格是儲存
- 讀時模式(shema-on-read),資料拿出資料庫後才定義每個屬性的意義
- 如果資料的locality局部性高的話,文檔模型是最好的選擇
- 如果關聯資料逐漸上升,為了消除副本(Duplicatoin)會逐漸演變成關聯資料模型,如果選擇不消除副本則在讀取時要透過程式碼做多次檢查
關聯資料模型
- 再1970關聯大戰中戰勝網路模型
- 由Row集合成Table,再由Table互相做關聯
- 寫時模式(shema-on-write),創建時就需要定義每個col的意義與資料格式
- 如果完全正規化,在查找簡單的資料時可能要做多次的硬碟跳轉搜尋
- 如果反正規化,可以使用現在資料庫中的JSON格式做到與文檔資料庫相同的讀時模式(shema-on-read)
圖資料模型
- 改良版的網路模型,因為硬碟隨機存取效率上升,所以逐漸被重視
- 關聯資料模型也可以表達圖資料模型,但SQL的使用會顯得有點彆手彆腳
- 現在較常見的是Neo4j與它的Cypher
- 圖資料模型常用來呈現應用中的,好友關係/地理位址表達/路線搜尋。
最後,有時候網路上常常爭論哪種資料庫更好,但是深度了解每個資料特性就會知道沒有最好的資料庫,只有最適合的場景。況且資料庫廠商他們也都是要靠這賺錢的,常常用過於華麗的行銷話術誤導開發者,如果知道每個資料模型的原理與場景那就可以世界越快心則慢,不被影響了。