[轉]Distributed Key-Value Database

http://blog.gslin.org/page/2/


這篇是因為在 PIXNET 內講了 n 次，決定寫成文字，至少之後新人進來可以說「就看這篇」，避免整套系統都需要重新講一次。
對了，補充一下，PIXNET 還是有缺人，參考「缺人找人」這篇的內容，如果有想問的細節，可以寫信問我。
資料庫
在 RDBMS 提供了很多而且很豐富的操作方式，但當資料量愈來愈大時，會遇到單台機器的網路頻寬有限以及空間有限。這時候一定得走向多台的架構。
Replication
最容易解決的情況是「讀取的 query 比寫入的 query 多」，可以用 database replication 解決，這也是 Web 1.0 網站常見的解法之一 (另外一種常見的解法是使用靜態檔案，或是 reverse proxy cache)，同步將資料複製到多台。
Memcached
接下來會發現當 slave 過多時會造成每台記憶體內重複 cache 相同的元素，也就是說，有二十台 slave，每台都有 SELECT * FROM `user` WHERE `name` = 'gslin' 的結果其實很浪費資源。不過這個問題可以用memcached 或是 hash selection 解決。
Sharding
在 Web 2.0 的環境裡，User generated content 成為主流，當寫入的 query 超過單台可以負荷的量時，replication 的架構就不是很適合了，因為每個寫入的 query 在其他台 slave 上也會被執行。在商用資料庫的領域通常是使用 cluster 架構，在 open source 領域的 MySQL cluster 也是 cluster-based solution，不過用的單位還不是很多，而且 overhead 還蠻重的。
比較常見的解法是 sharding：依照 id，把資料拆散到各台。像是 Flickr 就是這樣使用。
但 sharding 就會少了很多 RDBMS 可以用的特性 (JOIN 與 transaction)，在寫 application server 或是 library 的時候得花功夫多下幾次 query，並且注意資料的正確性。
上面這些方法在 2005 年 Brad Fitzpatrick (LiveJournal founder、memcached 作者) 的投影片「LiveJournal’s Backend: A history of scaling」都有提到。
Sharding 是一個解法，但有不少缺點：
需要 application server 或是 library，否則 3rd party 程式得清楚知道 sharding 的架構，才會知道資料要到哪個 cluster 找。
無法隨意使用 JOIN 及 transaction。如果真的要 JOIN，設計時要想辦法把需要 JOIN 的資料放在同一台 database server。如果要跨機器 transaction 得透過 2PC 甚至 3PC (看需求)，或是類似的 distributed transaction protocol，效能會比起同一台機器差很多。
設計 schema 時必須注意當一個 cluster 愈來愈大時要 rebalance，或是更進一步，在一開始設計時就考慮到資料搬移的問題。
Key-Value Database
後來就有不少人注意到，Web 2.0 網站很多時候不需要 transaction，而 JOIN 也會儘量避免。透過多次 SELECT 拉資料，或是 denormalize 以提高效能的方式還蠻常見。(JOIN 保證 atomic，而且會因為 query analyzer enginer 在沒有正確分析的情況下會有大量的 random access，比多次 SELECT 耗資源)
另外一個是財務層面上的問題，一開始寫的時候通常也都只有一組 database server，不太可能一次就買兩組 database server。當成長到需要 sharding 時通常寫 code 的人已經不只一個人，一定有人偷懶使用 JOIN 或是其他無法 sharding 的程式。這時候會發現需要「重寫」而非「改寫」。
於是就有人開始思考，如果我放棄 RDBMS 的 JOIN 與 transaction，放棄到只剩下 key-value 的架構，是不是有辦法可以發展一套 distributed database system 可以取得 “incremental scalibility” 的特性 (白話的說就是「加機器就可以增加承載量」)，再想辦法看看在這個系統上還可以加什麼功能。
也就是說，這樣的系統一開始可能只有兩台小台的機器 (為了 HA)，同時跑 Web 與 Database，當網站愈來愈大的時候我把這些小機器拉到前端跑 Web，或是轉為開發機使用，本來的 Database 買 15KRPM SAS (為了 cache miss 的 seek time 與 latency) 與 64GB RAM (還是為了 cache hit 降低 latency)。
所以在 distributed key-value database 先有基本的功能：
GET(key)
SET(key, value)
DELETE(key)
有了這三個功能，至少你可以把本來在 RDBMS 裡很大一部份放到 Key-Value Database 裡。以 Blog 來說，可以把所有的標題及內文部份放到 Key-Value Database 內，大幅減少 RDBMS 的 cache 負擔。
或者，key 是 path + filename，value 是檔案內容，當作一個 filesystem 在用。(也就是 Amazon S3)
這樣對於前端寫程式的人就會簡單許多。整個 Key-Value Database 是一朵可以無限擴充的雲，前端程式不需要設計或是修改程式碼就可以一直發展。如果當作 Filesystem 就不用擔心 disk 滿了之後加機器需要停機。
在這個想法下，就有許多單位投入資源往 distributed key-value system 發展。經過這些年的發展，分散式資料庫主要有三個問題要解決，而且也被證明這三個問題無法同時解決 (被稱為 CAP theorem，參考 Brewer’s Conjecture and the Feasibility of Consistent Available Partition-Tolerant Web Services, 2002 這篇原始論文，或是參考比較簡單易懂的說明「Brewer’s CAP Theorem」)：
Consistent
Availibility
Partition Tolerance
所以分散式資料庫得在這三個條件內取捨。目前比較熱門的 Distributed Key-Value Database 主要都是把 Consistent 放寬到 “Eventally Consistent“，只保證資料「遲早會一致」，這些 Database 包括了HBase (Yahoo!)、Cassandra (Facebook) 這兩套 Java-based 分散式資料庫。
要瞭解這兩套系統的架構，一般建議從「Amazon’s Dynamo」這篇開始看，看完後再看這兩套系統的系統架構介紹，以及 mailing list 的討論。
這兩套除了基本的 Key-Value 外，還多了 Column 的觀念，彈性會比 Key-Value 好一些。Yahoo! 與 Facebook 都拿這個系統當 Search Engine 使用。
另外有一些比較單純的分散式系統，只有 Key-Value 而沒有 Column 的，在「My Thoughts on NoSQL」這篇文章裡對 CouchDB、Redis 自稱 distributed 的嘴炮批評了不少。另外「Anti-RDBMS: A list of distributed key-value stores」介紹了很多。
大致上是這樣。