SNS網(wǎng)站數(shù)據(jù)庫(kù)技術(shù)分析
社交網(wǎng)
現(xiàn)在，傳統(tǒng)的互聯(lián)網(wǎng)正在邁向一個(gè)一個(gè)全新的時(shí)代 ---- 社交服務(wù)網(wǎng)時(shí)代（ Social Networking Service ），從“人與機(jī)器”的時(shí)代邁向“人與人”的時(shí)代?；ヂ?lián)網(wǎng)社交服務(wù)網(wǎng)站的發(fā)展驗(yàn)證了“六度分隔理論”（ Six Degrees of Separation ），即“人際關(guān)系脈絡(luò)方面你必然可以通過(guò)不超出六位中間人間接與世上任意先生女士相識(shí)”。個(gè)體的社交圈會(huì)不斷地?cái)U(kuò)大和重疊并在最終形成大的社交網(wǎng)絡(luò)。無(wú)論是國(guó)外的 Facebook 、 MySpace 、 Twitter ，還是國(guó)內(nèi)的開(kāi)心網(wǎng)、人人網(wǎng)等一頭扎進(jìn)社交網(wǎng)，他們認(rèn)定社交網(wǎng)必然掀起新一輪的互聯(lián)網(wǎng)革命。
社交網(wǎng)其中一個(gè)的顯著特點(diǎn)是支持巨大用戶數(shù)，例如 Facebook 支持超過(guò) 3 億的用戶， Facebook 數(shù)據(jù)中心運(yùn)行著超過(guò)萬(wàn)臺(tái)的服務(wù)器，為這些遍布全球的用戶提供信息通訊服務(wù)。另外，任何兩個(gè)社交網(wǎng)用戶都可能交互，也就是必須支持任何兩個(gè)數(shù)據(jù)庫(kù)用戶的數(shù)據(jù)關(guān)聯(lián)操作。這種情況下，對(duì)于服務(wù)端的數(shù)據(jù)庫(kù)管理提出了極大的挑戰(zhàn)。
關(guān)系數(shù)據(jù)庫(kù)與 NoSQL 數(shù)據(jù)庫(kù)
關(guān)系數(shù)據(jù)庫(kù)使用者遵循一些數(shù)據(jù)庫(kù)范式，這些范式是數(shù)據(jù)庫(kù)設(shè)計(jì)中的一系列原理和技術(shù)，其目的是為了減少數(shù)據(jù)庫(kù)中數(shù)據(jù)冗余，并增進(jìn)數(shù)據(jù)的一致性。結(jié)構(gòu)化查詢語(yǔ)言 SQL ，大量使用多表連接操作， SQL 的通用性為數(shù)據(jù)庫(kù)使用者帶來(lái)很多方便。
隨著越來(lái)越多如 Web 服務(wù)之類承受大規(guī)模工作負(fù)荷的應(yīng)用的發(fā)行，其對(duì)可伸縮性的需求，首先有可能會(huì)改變得非常迅速，其次會(huì)變得無(wú)比龐大。
關(guān)系數(shù)據(jù)庫(kù)的確能伸縮自如，但通常只能單臺(tái)服務(wù)器節(jié)點(diǎn)上進(jìn)行。 例如采用表分區(qū)技術(shù)，一個(gè)表格可以由多個(gè)物理文件組成，雖然表格的容量增大了，但該表格仍然只能由一數(shù)據(jù)庫(kù)引擎管理。
一旦單節(jié)點(diǎn)的能力抵達(dá)上限，你就得通過(guò)多服務(wù)器節(jié)點(diǎn)來(lái)往外擴(kuò)展來(lái)分發(fā)負(fù)載。這時(shí)候關(guān)系數(shù)據(jù)庫(kù)的復(fù)雜性就開(kāi)始影響其潛在的擴(kuò)展規(guī)模了。 RDBMS 支持分區(qū)視圖 (Partition View) 技術(shù)，也就是支持聯(lián)邦數(shù)據(jù)庫(kù) (Federated Databases) 概念【圖 1 】。一個(gè)分區(qū)視圖可以由多個(gè)分布在不同的數(shù)據(jù)庫(kù)節(jié)點(diǎn)服務(wù)器上的表格組合而成，數(shù)據(jù)庫(kù)用戶只看到是該視圖，不關(guān)心多個(gè)物理表格。通過(guò)數(shù)據(jù)水平分割技術(shù)，分區(qū)視圖把負(fù)載分擔(dān)到多個(gè)數(shù)據(jù)庫(kù)節(jié)點(diǎn)服務(wù)器上。擴(kuò)容時(shí)，該方法除了需改動(dòng)視圖定義外，分區(qū)視圖成為分布式數(shù)據(jù)庫(kù)系統(tǒng)的中心，存在單點(diǎn)故障問(wèn)題。另外，跨數(shù)據(jù)庫(kù)節(jié)點(diǎn)之間多表格間連接操作的支持出現(xiàn)極大困難。
圖 1. IBM 聯(lián)邦數(shù)據(jù)庫(kù)的體系結(jié)構(gòu)
當(dāng)試圖擴(kuò)展數(shù)據(jù)庫(kù)系統(tǒng)到成百上千個(gè)節(jié)點(diǎn)，而不是幾個(gè)，將導(dǎo)致不堪復(fù)雜性之重負(fù)，這一特點(diǎn)使得 RDBMS 在大型分布式系統(tǒng)平臺(tái)市場(chǎng)里的生存能力被大幅削減。
為了能向客戶提供的一個(gè)伸縮自如的空間去存放應(yīng)用數(shù)據(jù)，供應(yīng)商實(shí)際上只有一種真正的選擇。他們不得不實(shí)現(xiàn)一種新型的關(guān)注于可擴(kuò)性的數(shù)據(jù)庫(kù)系統(tǒng)，而犧牲掉關(guān)系數(shù)據(jù)庫(kù)所帶來(lái)的其他好處。 NoSQL 是非關(guān)系型數(shù)據(jù)存儲(chǔ)的廣義定義。它打破了長(zhǎng)久以來(lái)關(guān)系型數(shù)據(jù)庫(kù)與 ACID 理論大一統(tǒng)的局面。 NoSQL 數(shù)據(jù)存儲(chǔ)不需要固定的表結(jié)構(gòu)，通常也不存在連接操作。在超大型數(shù)據(jù)存取上具備關(guān)系型數(shù)據(jù)庫(kù)無(wú)法比擬的性能優(yōu)勢(shì)。該術(shù)語(yǔ)在 2009 年初得到了廣泛認(rèn)同。其中 key-value 數(shù)據(jù)模型是解決大型數(shù)據(jù)庫(kù)系統(tǒng)擴(kuò)充問(wèn)題的一種可行的解決方案。
Berkeley DB Key-Value數(shù)據(jù)模型
Berkeley DB 是一種支持 key-value 數(shù)據(jù)模型的嵌入式數(shù)據(jù)庫(kù)存儲(chǔ)引擎。不支持 Client/Server 網(wǎng)絡(luò)訪問(wèn)方式，程序通過(guò)進(jìn)程內(nèi)的 API 訪問(wèn)數(shù)據(jù)庫(kù)。不支持 SQL 或者其他的數(shù)據(jù)庫(kù)查詢語(yǔ)言，不支持表結(jié)構(gòu)和數(shù)據(jù)列。訪問(wèn)數(shù)據(jù)庫(kù)的程序自主決定數(shù)據(jù)如何儲(chǔ)存在記錄里，一條記錄由一個(gè)稱為鍵 key 的數(shù)據(jù)塊和一個(gè)稱為值 value 的數(shù)據(jù)塊組成。 Berkeley DB 不對(duì)記錄里的數(shù)據(jù)進(jìn)行任何包裝。應(yīng)用程序可通過(guò)一回調(diào)函數(shù)來(lái)定義不同鍵之間的大小關(guān)系。記錄和它的鍵都可以達(dá)到 4G 字節(jié)的長(zhǎng)度。盡管架構(gòu)很簡(jiǎn)單， Berkeley DB 卻支持很多高級(jí)的數(shù)據(jù)庫(kù)特性，比如 ACID 數(shù)據(jù)庫(kù)事務(wù)處理， 細(xì)粒度鎖， XA 接口，熱備份以及同步復(fù)制。 Berkley DB 為不同用戶提供多種功能集（ Feature Set ） : 支持單個(gè)寫(xiě)線程的數(shù)據(jù)存儲(chǔ)（ Data Store ）；支持多并發(fā)寫(xiě)線程的并發(fā)數(shù)據(jù)存儲(chǔ)（ Concurrent Data Store ） ; 支持 ACID 和災(zāi)難恢復(fù)的事務(wù)數(shù)據(jù)存儲(chǔ)（ Transactional Data Store ）；和通過(guò)復(fù)制支持容錯(cuò)的高可靠數(shù)據(jù)存儲(chǔ)（ High Availability ）。
實(shí)際上，一個(gè)關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)由兩個(gè)獨(dú)立的部分組成，一是存儲(chǔ)引擎，二是關(guān)系引擎。存儲(chǔ)引擎負(fù)責(zé)記錄存儲(chǔ)，索引和事務(wù)處理。關(guān)系引擎基于存儲(chǔ)引擎提供的服務(wù)，根據(jù)表格、視圖的數(shù)據(jù)結(jié)構(gòu) (Schema) 和已建立的索引等信息， 負(fù)責(zé)分析 SQL 查詢，制定查詢執(zhí)行計(jì)劃。 Berkeley DB 是一種存儲(chǔ)引擎。例如 MySQL 數(shù)據(jù)庫(kù)可采用 MyISAM 、 InnoDB 、 Berkeley DB 等存儲(chǔ)引擎【圖 2 】。
圖 2 ： MySQL 使用的多種存儲(chǔ)引擎
Berkeley DB 支持平衡樹(shù)（ BTree ）、哈希（ Hash ）、隊(duì)列（ Queue ）和記錄（ Record ）等數(shù)據(jù)集存儲(chǔ)、索引方式。 Berkeley DB 支持根據(jù) key-value 中的 key 創(chuàng)建集群索引（ Clustered Index ）。這樣記錄集的物理次序就根據(jù) key 的大小來(lái)排列。如果要查詢結(jié)果記錄集的鍵值為給定的一個(gè)范圍，該特性對(duì)于支持這種類型的快速查詢起了很大作用。 Berkeley DB 的一個(gè) key-value 記錄集稱為一個(gè)數(shù)據(jù)庫(kù)，一個(gè)數(shù)據(jù)庫(kù)存儲(chǔ)在一單獨(dú)文件中。 Berkeley DB 通過(guò)創(chuàng)建輔助數(shù)據(jù)庫(kù)（ Secondary Database ）允許對(duì)記錄集建立非集群索引（ Non-Clustered Index ）。非集群索引適用于結(jié)果為一條記錄的查詢，該記錄的鍵值為給定的一個(gè)值。例如社交網(wǎng)用戶數(shù)據(jù)集：
User
如果以 UID 作為主數(shù)據(jù)庫(kù)的鍵，其他字段作為主數(shù)據(jù)庫(kù)的值?？稍賱?chuàng)建一輔助數(shù)據(jù)庫(kù)，以 E-mail 作為輔助數(shù)據(jù)庫(kù)的鍵，輔助數(shù)據(jù)庫(kù)的值為 E-mail 所對(duì)應(yīng)的 UID ，也就是指向主數(shù)據(jù)庫(kù)記錄的指針。
若在一個(gè) key-value 數(shù)據(jù)庫(kù)查詢，一般可根據(jù)查詢條件創(chuàng)建成一鍵值，引擎返回一游標(biāo)（ Cursor ），該游標(biāo)指向等于或大于該鍵值的結(jié)果數(shù)據(jù)集。
不難看出 Berkeley DB 使用的索引技術(shù)與 SQL Server, Oracle 等高端數(shù)據(jù)庫(kù)系統(tǒng)是一樣的。
其中在 RDBMS 中經(jīng)常使用的表格連接操作，在 Berkeley DB 中不再支持，需要應(yīng)用程序去實(shí)現(xiàn)兩個(gè)數(shù)據(jù)集的連接操作。這是 key-value 數(shù)據(jù)模型與關(guān)系數(shù)據(jù)模型典型的區(qū)別。
基于 key-value 數(shù)據(jù)模型，可把一個(gè) value 數(shù)據(jù)塊擴(kuò)充成多個(gè)列，來(lái)支持列數(shù)據(jù)模型。
Berkeley DB 除了作為 MySQL 的存儲(chǔ)引擎之外，還應(yīng)用在 OpenLDAP 、 MemCache 等知名軟件。
與 Berkeley DB 類似的數(shù)據(jù)庫(kù)引擎還有 Tokyo Cabinet/ Tyrant 等。
社交網(wǎng)數(shù)據(jù)庫(kù)系統(tǒng) Cassandra DB
以 Facebook 用戶數(shù)據(jù)集為例子，不大可能把 3 億條這巨大的數(shù)據(jù)集存放在同一表格中、同一個(gè)文件或由同一臺(tái)計(jì)算機(jī)處理，這要求系統(tǒng)能支持?jǐn)?shù)據(jù)分區(qū)，把數(shù)據(jù)集分割在多臺(tái)節(jié)點(diǎn)計(jì)算機(jī)中，每臺(tái)計(jì)算機(jī)分擔(dān)一部分負(fù)載，當(dāng)用戶增加到一定程度時(shí)，系統(tǒng)能允許加入新的節(jié)點(diǎn)計(jì)算機(jī)，并且盡可能地減少數(shù)據(jù)遷移。
2007 年 10 月 30 日， Amazon 的 CTO Werner Vogels 發(fā)表了一文章，討論了一種基于 key-value 數(shù)據(jù)模型存儲(chǔ)系統(tǒng) Dynamo 。 Dynamo 系統(tǒng)支撐了不少 Amazon 自有的面向電子商務(wù)等關(guān)鍵性應(yīng)用。 Dynamo 上采用的存儲(chǔ)引擎是 Berkeley DB 事務(wù)數(shù)據(jù)存儲(chǔ)（ Transactional Data Store ）。 Dynamo 系統(tǒng)主要為存儲(chǔ) 1M 左右甚至更小的內(nèi)容，如購(gòu)物車、推薦列表等。 Dynamo 設(shè)計(jì)上有如下一些特點(diǎn)：
通過(guò)數(shù)據(jù)分區(qū)復(fù)制來(lái)支持高可靠性與高可伸縮性
始終可寫(xiě)
一致性與寫(xiě)入速度的折衷，不要求同步寫(xiě)入所有副本
對(duì)稱，完全去中心化，人工管理工作很小。
Cassandra DB 最初由 Facebook 開(kāi)發(fā)，后轉(zhuǎn)變成了開(kāi)源項(xiàng)目。它是一個(gè)為網(wǎng)絡(luò)社交云計(jì)算設(shè)計(jì)的數(shù)據(jù)庫(kù)。 Cassandra 的主要特點(diǎn)就是它不是一個(gè)數(shù)據(jù)庫(kù)，而是由一堆數(shù)據(jù)庫(kù)節(jié)點(diǎn)共同構(gòu)成的一個(gè)分布 式網(wǎng)絡(luò)服務(wù)，對(duì) Cassandra 的一個(gè)寫(xiě)操作，會(huì)被復(fù)制到其他節(jié)點(diǎn)上去，對(duì) Cassandra 的讀操作，也會(huì)被路由到某個(gè)節(jié)點(diǎn)上面去讀取。對(duì)于一個(gè) Cassandra 群集來(lái)說(shuō)，擴(kuò)展性能 是比較簡(jiǎn)單的事情，只管在群集里面添加節(jié)點(diǎn)就可以了。
Cassandra 的用戶包括 Facebook 、 Twitter 和 Digg 等。 Digg 工程副總裁 約翰 • 奎因 (John Quinn)說(shuō) ：“ Cassandra 采用了完全分散的模式，每個(gè)節(jié)點(diǎn)都一樣，不會(huì)出現(xiàn)單一點(diǎn)的故障。其容錯(cuò)率也非常高，數(shù)據(jù)可以被復(fù)制到數(shù)據(jù)中心的多個(gè)節(jié)點(diǎn)中。 Cassandra 還非常具有彈性，隨著新設(shè)備的加入，其讀寫(xiě)吞吐量將呈線性增加。”
Cassandra 以 Amazon 專有的完全分布式的 Dynamo 為基礎(chǔ)，結(jié)合了 Google BigTable 基于列族（ Column Family ）的數(shù)據(jù)模型。 P2P 去中心化的存儲(chǔ)。很多方面都可以稱之為 Dynamo 2.0 。
圖 3 為 Cassandra 、 Dynamo 、 key-value 之間的關(guān)系及在社交網(wǎng)上的應(yīng)用。箭頭表示依賴關(guān)系。
圖 3 ： Cassandra, Dynamo, key-value 關(guān)系圖
分布式存儲(chǔ)系統(tǒng) Amazon Dynamo 原理
Dynamo 采用 Consistent Hashing 算法來(lái)實(shí)現(xiàn)數(shù)據(jù)分區(qū)。
Consistent Hashing 基本原理是：首先求出服務(wù)器（節(jié)點(diǎn)）的哈希值，并將其配置到 0 ～ 2^32 的圓上。然后用同樣的方法求出存儲(chǔ)數(shù)據(jù)的鍵的哈希值，并映射到圓上。然后從數(shù)據(jù)映射到的位置開(kāi)始順時(shí)針查找，將數(shù)據(jù)保存到找到的第一個(gè)服務(wù)器上。如果超過(guò) 2^32 仍然找不到服務(wù)器，就會(huì)保存到第一臺(tái)服務(wù)器上?！緢D 4 】
圖 4 ：數(shù)據(jù)分割到 4 個(gè)節(jié)點(diǎn)數(shù)據(jù)庫(kù)
如果添加一臺(tái)服務(wù)器。只有在圈上，增加服務(wù)器的地點(diǎn)逆時(shí)針?lè)较虻牡谝慌_(tái)服務(wù)器上的部分?jǐn)?shù)據(jù)需要遷移到新的節(jié)點(diǎn)數(shù)據(jù)庫(kù)【圖 4 】。
圖 5 ：添加 Node5 后需要遷移的數(shù)據(jù)
數(shù)據(jù)分區(qū)后，數(shù)據(jù)塊被復(fù)制到 N 個(gè)節(jié)點(diǎn)上。復(fù)制時(shí)因?yàn)楦庐a(chǎn)生的一致性問(wèn)題的維護(hù)采取類似拜占庭容錯(cuò) Quorum 協(xié)議（ Byzantine Fault-tolerance Quorum ）的機(jī)制以及去中心化的復(fù)制同步協(xié)議。當(dāng)一個(gè)存儲(chǔ)節(jié)點(diǎn)被認(rèn)為是拜占庭節(jié)點(diǎn)時(shí) , 它的行為可能任意偏移 , 表現(xiàn)在 : 拒絕響應(yīng)請(qǐng)求、發(fā)送錯(cuò)誤消息、存儲(chǔ)錯(cuò)誤信息等。 Quorum 協(xié)議中除了 N 之外還有兩個(gè)關(guān)鍵參數(shù)： R 與 W 。 R 代表一次成功的讀取操作中最小參與節(jié)點(diǎn)數(shù)量， W 代表一次成功的寫(xiě)操作中最小參與節(jié)點(diǎn)數(shù)量。 R 和 W 直接影響性能、一致性。 R 和 W 值過(guò)小則影響一致性，過(guò)大則影響效率，這兩個(gè)值要平衡。如果 W 設(shè)置 為 1 ，則一個(gè)實(shí)例中只要有一個(gè)節(jié)點(diǎn)可寫(xiě)就寫(xiě)成功，不會(huì)影響寫(xiě)效率；如果 R 設(shè)置為 1 ，只要有一個(gè)節(jié)點(diǎn)可讀，就讀成功，不會(huì)影響讀效率。 (N,R,W) 的典型配置是 (3,2,2) ，同時(shí)考慮了一致性和效率。
Facebook 數(shù)據(jù)庫(kù)查詢語(yǔ)言 : FQL
Facebook 為開(kāi)發(fā)者提供一套和 SQL 風(fēng)格一致的數(shù)據(jù)庫(kù)查詢語(yǔ)言，稱為 Facebook Query Language (FQL) 。 FQL 是一種基于列的數(shù)據(jù)查詢語(yǔ)言。提供豐富的條件查詢，甚至包括子查詢。
例如，以下 FQL 查詢已安裝 Facebook 應(yīng)用程序的用戶 $app_user 的好友 ID 集合：
SELECT uid FROM user WHERE is_app_user = 1 AND uid IN (SELECT uid2 FROM friend WHERE uid1 = $app_user)
與 SQL 重要區(qū)別是 FQL 不支持
· 多表連接： JOIN 操作
· 結(jié)果集記錄個(gè)數(shù)限制： LIMIT
· 分組統(tǒng)計(jì)： GROUP BY 操作
· 排序： ORDER BY 操作
隨著技術(shù)發(fā)展，一部分基于列結(jié)構(gòu)的 NoSQL 數(shù)據(jù)庫(kù)開(kāi)始支持分組、排序等復(fù)雜數(shù)據(jù)統(tǒng)計(jì)分析功能。
例子：查詢好友信息
例如一個(gè) Facebook 應(yīng)用程序從以下兩個(gè)數(shù)據(jù)集中查找一用戶的好友數(shù)據(jù)集信息 :
User
Friend_List
注 Friend_UID 是一指向 User （ UID ）的外鍵。
RDBMS 應(yīng)用程序可使用數(shù)據(jù)集連接操作實(shí)現(xiàn)：
- SELECT f.UID, u.Friend_UID, u.First_Name, u.Last_Name, u.Icon
- FROM Friend_List f, User u
- WHERE f.Friend_UID = u.UID AND f.UID=@Input_UID
在社交網(wǎng)數(shù)據(jù)庫(kù)系統(tǒng)中，由于 User 數(shù)據(jù)分布在多臺(tái)服務(wù)器中，其連接操作和外鍵約束實(shí)際上不能支持。
在 Facebook 中查找一用戶的好友信息，得分 A)B) 兩步操作實(shí)現(xiàn)：
A)
- SELECT Friend_UID
- INTO @Out_Record_Set
- FROM Friend_List f
- WHERE f.UID=@Input_UID
B)
- FOR EACH (Friend_UID in @Out_Record_Set)
- SELECT u.Friend_UID, u.First_Name, u.Last_Name, u.Icon
- FROM User u
- WHERE u.UID = Friend_UID
No-SQL: Not Only SQL
對(duì)于那些關(guān)系復(fù)雜的數(shù)據(jù)處理和分析統(tǒng)計(jì)， SQL 值得花錢。但是當(dāng)數(shù)據(jù)庫(kù)結(jié)構(gòu)非常簡(jiǎn)單時(shí)， SQL 可能沒(méi)有太大用處。如果能用普通文件存儲(chǔ)代替數(shù)據(jù)庫(kù)系統(tǒng)部分功能的話，應(yīng)該優(yōu)選普通文件存儲(chǔ)。
考慮社交網(wǎng)，能夠不受限制的擴(kuò)展比更豐富的功能更加重要。建立大規(guī)模社交網(wǎng)成本的壓力讓很多社交網(wǎng)開(kāi)發(fā)人員努力去尋找更高性價(jià)比的解決方案。研究表明基于普通廉價(jià)硬件的分布式存儲(chǔ)解決方案甚至比現(xiàn)在的高端數(shù)據(jù)庫(kù)更加可靠。當(dāng)支持 SQL 的 RDBMS 不能解決所有問(wèn)題的時(shí)候， NoSQL 不是簡(jiǎn)單的 No SQL ，其本質(zhì)是 No Relational ，這時(shí)候 NoSQL 就成為 Not Only SQL 。
【編輯推薦】
