1、社交網(wǎng)絡(luò)數(shù)據(jù)庫(kù)技術(shù)分析傳統(tǒng)互聯(lián)網(wǎng)正在邁向一個(gè)全新的時(shí)代社交服務(wù)網(wǎng)(Social Networking Service)時(shí)代，從人與機(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)，因?yàn)樗麄冋J(rèn)定社交網(wǎng)必然掀起新一輪的互聯(lián)網(wǎng)革命。社交網(wǎng)的一個(gè)顯著特點(diǎn)是支持巨大用戶(hù)數(shù)，例如Facebo

2、ok支持超過(guò)3億的用戶(hù)，其數(shù)據(jù) 中心運(yùn)行著超過(guò)萬(wàn)臺(tái)的服務(wù)器，為遍布全球的用戶(hù)提供信息通訊服務(wù)。另外，任何兩個(gè)社交網(wǎng) 用戶(hù)都可能交互，也就是必須支持任何兩個(gè)數(shù)據(jù)庫(kù)用戶(hù)的數(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)化查詢(xún)語(yǔ)言SQL大量使用多表連 接操作，SQL的通用性可以為使用者帶來(lái)很多方便。隨著越來(lái)越多大規(guī)模工作負(fù)荷應(yīng)用的發(fā)行，對(duì)可伸縮性的需求，可能會(huì)變得非常迅速和無(wú) 比龐大。關(guān)系數(shù)據(jù)庫(kù)的確能伸縮自如，但通常只能在單臺(tái)服務(wù)

3、器節(jié)點(diǎn)上進(jìn)行。例如采用表分區(qū)技術(shù)， 一個(gè)表格可以由多個(gè)物理文件組成，雖然表格的容量增大了，但該表格仍然只能由一數(shù)據(jù)庫(kù)引 擎管理;另外增加一物理文件時(shí)，表格Schema得做改動(dòng)，也就是還不能支持動(dòng)態(tài)擴(kuò)容。一旦單節(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 Database)(如圖1)。一個(gè)分區(qū)視圖可以由多個(gè)分布在不同 數(shù)據(jù)庫(kù)節(jié)點(diǎn)服務(wù)器上的表格組合而成，數(shù)據(jù)庫(kù)用戶(hù)看到的只是該視圖，不必關(guān)心物理表格。通 過(guò)數(shù)據(jù)水平分割技術(shù)，分區(qū)視圖

4、把負(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)時(shí)，將導(dǎo)致不堪復(fù)雜性之重負(fù)，這一特點(diǎn)使得 RDBMS在大型分布式系統(tǒng)平臺(tái)市場(chǎng)里的生存能力被大幅削減。為了能向客戶(hù)提供一個(gè)伸縮自如的空間存放應(yīng)用數(shù)據(jù)，供應(yīng)商實(shí)際上只有一種真正的選擇 實(shí)現(xiàn)一種新型的專(zhuā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理論大

5、一 統(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ù)查詢(xún)語(yǔ)言，不支持表結(jié)構(gòu)和數(shù)據(jù)列。訪問(wèn)數(shù)據(jù)庫(kù)的程序自主決定數(shù)據(jù)如何儲(chǔ)存在記錄里，一 條記錄由一個(gè)稱(chēng)為鍵(Key

6、)的數(shù)據(jù)塊和一個(gè)稱(chēng)為值(Value)的數(shù)據(jù)塊組成。Berkeley DB不對(duì) 記錄里的數(shù)據(jù)進(jìn)行任何包裝。應(yīng)用程序可通過(guò)回調(diào)函數(shù)來(lái)定義不同鍵之間的大小關(guān)系，記錄和 它的鍵都可以達(dá)到4GB的長(zhǎng)度。盡管架構(gòu)簡(jiǎn)單，Berkeley DB卻支持很多高級(jí)的數(shù)據(jù)庫(kù)特性， 比如ACID數(shù)據(jù)庫(kù)事務(wù)處理、細(xì)粒度鎖、XA接口、熱備份以及同步復(fù)制。Berkley DB為不 同用戶(hù)提供多種功能集(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 D

7、ata Store);通過(guò)復(fù)制支持容錯(cuò)的高可靠數(shù)據(jù)存儲(chǔ)(High Availability)。關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)由存儲(chǔ)引擎和關(guān)系引擎兩個(gè)獨(dú)立部分組成。存儲(chǔ)引擎負(fù)責(zé)記錄存儲(chǔ)、索引 和事務(wù)處理，關(guān)系引擎負(fù)責(zé)基于存儲(chǔ)引擎提供的服務(wù)，分析SQL、制定查詢(xún)執(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ǔ)和索引方式，還支持根據(jù)Key-Value中的K

8、ey創(chuàng)建集群索引(Clustered Index)。這 樣記錄集的物理次序就根據(jù)Key值大小來(lái)排列。如果要查詢(xún)結(jié)果記錄集的鍵值為給定的一個(gè)范 圍，該特性對(duì)于支持這種類(lèi)型的快速查詢(xún)起了很大作用。Berkeley DB的一個(gè)Key-Value記 錄集稱(chēng)為一個(gè)數(shù)據(jù)庫(kù)，會(huì)存儲(chǔ)在一個(gè)單獨(dú)文件中。Berkeley DB通過(guò)創(chuàng)建輔助數(shù)據(jù)庫(kù) (Secondary Database)，允許對(duì)記錄集建立非集群索引(Non-Clustered Index)。非集群索 引適用于快速查詢(xún)結(jié)果為一條記錄，該記錄的鍵值為給定的一個(gè)值。例如社交網(wǎng)用戶(hù)數(shù)據(jù)集：User 如果以UID作為主數(shù)據(jù)庫(kù)的鍵，其他字段作為主數(shù)據(jù)庫(kù)的值，可

9、再創(chuàng)建一個(gè)輔助數(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ù)查詢(xún)，一般可根據(jù)查詢(xún)條件創(chuàng)建成一個(gè)鍵值，引擎 返回一個(gè)游標(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ū)別。Berkeley DB除了作為MySQL

10、的存儲(chǔ)引擎之外，還應(yīng)用在OpenLDAP、MemCache 等知名軟件。與Berkeley DB類(lèi)似的數(shù)據(jù)庫(kù)引擎還有Tokyo Cabinet/ Tyrant等。社交網(wǎng)數(shù)據(jù)庫(kù)系統(tǒng)Cassandra以Facebook用戶(hù)數(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)用戶(hù)增加到一定程度時(shí)，系統(tǒng)能允許加入新的節(jié)點(diǎn)計(jì)算機(jī)，并且盡可能地 減少數(shù)據(jù)遷移。2007年10月30日，Amazon的CTO Werner Vogels發(fā)表了一篇文章，討論了一種 基于Key-Value數(shù)據(jù)模型的存儲(chǔ)

11、系統(tǒng)Dynamo。該系統(tǒng)支撐了不少Amazon的面向電子商務(wù) 等關(guān)鍵性應(yīng)用，它采用的存儲(chǔ)引擎是Berkeley DB事務(wù)數(shù)據(jù)存儲(chǔ)(Transactional Data Store)o Dynamo系統(tǒng)主要為存儲(chǔ)1M左右甚至更小的內(nèi)容，如購(gòu)物車(chē)、推薦列表等。Dynamo 設(shè)計(jì)上有下面一些特點(diǎn)。通過(guò)數(shù)據(jù)分區(qū)復(fù)制來(lái)支持高可靠性與高可伸縮性。始終可寫(xiě)。一致性與寫(xiě)入速度的折中，不要求同步寫(xiě)入所有副本。對(duì)稱(chēng)，完全去中心化，人工管理工作很小。Cassandra DB最初由Facebook開(kāi)發(fā)，后來(lái)轉(zhuǎn)變成為開(kāi)源項(xiàng)目。它是一個(gè)為網(wǎng)絡(luò)社交云 計(jì)算設(shè)計(jì)的數(shù)據(jù)庫(kù)，主要特點(diǎn)是它不再是一個(gè)數(shù)據(jù)庫(kù)，而是由一堆數(shù)據(jù)庫(kù)節(jié)點(diǎn)共同

12、構(gòu)成的一個(gè) 分布式網(wǎng)絡(luò)服務(wù)，對(duì)Cassandra的一個(gè)寫(xiě)操作會(huì)被復(fù)制到其他節(jié)點(diǎn)上去，對(duì)Cassandra的 讀操作也會(huì)被路由到某個(gè)節(jié)點(diǎn)上面去讀取。對(duì)于Cassandra群集來(lái)說(shuō)，擴(kuò)展性能是比較簡(jiǎn)單 的事情，只管在群集里面添加節(jié)點(diǎn)就可以了。Cassandra 的用戶(hù)包括 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)中。它還非常具有彈性，隨著新設(shè)備的加入， 其讀寫(xiě)吞吐量將呈線性增加。Cassandra以Amazon

13、專(zhuān)有的完全分布式的Dynamo為基礎(chǔ)，結(jié)合了 Google BigTable 基于列族(Column Family)的數(shù)據(jù)模型。P2P去中心化的存儲(chǔ)。很多方面都可以稱(chēng)之為 Dynamo 2.0。圖3為Cassandra、Dynamo、Key-Value之間的關(guān)系及在社交網(wǎng)上的應(yīng)用。箭頭表示 依賴(lài)關(guān)系。圖 3 Cassandra、Dynamo、Key-Value 關(guān)系圖分布式存儲(chǔ)系統(tǒng)DynamoDynamo采用Consistent Hashing算法來(lái)實(shí)現(xiàn)數(shù)據(jù)分區(qū)。Consistent Hashing基本原理是：首先求出服務(wù)器節(jié)點(diǎn)的哈希值，并將其配置到0 2人32的圓上。然后用同樣的方法求出存儲(chǔ)

14、數(shù)據(jù)的鍵的哈希值，并映射到圓上。再?gòu)臄?shù)據(jù)映射 到的位置開(kāi)始順時(shí)針查找，將數(shù)據(jù)保存到找到的第一個(gè)服務(wù)器上。如果超過(guò)2人32仍然找不到 服務(wù)器，就會(huì)保存到第一臺(tái)服務(wù)器上。如圖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ù)。如圖5所示。圖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ù)采取 類(lèi)似拜占庭容錯(cuò)Quorum協(xié)議(Byzantine Fault-tolerance Quorum)的機(jī)制以及去中心化 的復(fù)制同步協(xié)議。當(dāng)一個(gè)存儲(chǔ)節(jié)點(diǎn)被認(rèn)為是

15、拜占庭節(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ì)影響讀效率。Facebook數(shù)據(jù)庫(kù)查詢(xún)語(yǔ)言：FQLFacebook為開(kāi)發(fā)者提供一套和SQL風(fēng)格一致的數(shù)據(jù)庫(kù)查詢(xún)語(yǔ)言，稱(chēng)為Facebook Query La

16、nguage (FQL)。FQL是一種基于列的數(shù)據(jù)查詢(xún)語(yǔ)言。提供豐富的條件查詢(xún)，甚至包括子查 詢(xún)。例如，以下FQL查詢(xún)已安裝Facebook應(yīng)用程序的用戶(hù)$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操作分組：GROUP BY操作排序：ORDER BY操作隨著技術(shù)發(fā)展，一部分基于列結(jié)構(gòu)的NoSQL數(shù)據(jù)庫(kù)開(kāi)始支持分租、排序等復(fù)雜數(shù)據(jù)統(tǒng)計(jì) 分析功能。舉例：查詢(xún)

17、好友信息Facebook應(yīng)用程序從以下兩個(gè)數(shù)據(jù)集中查找一用戶(hù)的好友數(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.IconFROM Friend_List f, User uWHERE f.Friend_UID = u.UID ANDf.UID = Input_UID在社交網(wǎng)數(shù)據(jù)庫(kù)系統(tǒng)中，由于User數(shù)據(jù)分布在多臺(tái)服務(wù)器中，其連接操作和外鍵約束實(shí) 際上不能支持。在Facebook中查找一用戶(hù)的好友信息，得分A、B兩步操作實(shí)現(xiàn)：A步SELECT Friend_UIDINTO Out_Record_SetFROM FriendList fWHERE f.UID = Input_UIDBl匕步FOR EACH (Friend_UID in Out_Record_Set)SELECT u.Friend_UID, u.First_Name, u.Last_Name, u.IconFROM User uWHERE u.UID = Friend_UIDNo-SQL: No