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