大數(shù)據(jù)圖數(shù)據(jù)庫之TAO數(shù)據(jù)庫

節(jié)選自《大數(shù)據(jù)日知錄：架構(gòu)與算法》十四章 14.1.2 TAO圖數(shù)據(jù)庫 Facebook是目前世界上最著名的社交網(wǎng)站，如果從數(shù)據(jù)抽象的角度來看，F(xiàn)acebook的社交圖不僅包括好友之間的關(guān)系，還包括人與實體以及實體與實體之間的關(guān)系，每個用戶、每個頁面、每張圖片、每個

節(jié)選自《大數(shù)據(jù)日知錄：架構(gòu)與算法》十四章

14.1.2 TAO圖數(shù)據(jù)庫

Facebook是目前世界上最著名的社交網(wǎng)站，如果從數(shù)據(jù)抽象的角度來看，F(xiàn)acebook的社交圖不僅包括好友之間的關(guān)系，還包括人與實體以及實體與實體之間的關(guān)系，每個用戶、每個頁面、每張圖片、每個應(yīng)用、每個地點以及每個評論都可以作為獨立的實體，用戶喜歡某個頁面則建立了用戶和頁面之間的關(guān)系，用戶在某個地點簽到則建立了用戶和地點之間的關(guān)系……如果將每個實體看作是圖中的節(jié)點，實體之間的關(guān)系看作是圖中的有向邊，則Facebook的所有數(shù)據(jù)會構(gòu)成超過千億條邊的巨型實體圖（Entity Graph）。實體圖中的關(guān)系有些是雙向的，比如，朋友關(guān)系；有些則是單向的，比如用戶在某個地點簽到。同時，實體還具有自己的屬性，比如某個用戶畢業(yè)于斯坦福大學(xué)，出生于1988年等，這些都是用戶實體的屬性。圖14-2是Facebook實體圖的一個示意片段。

圖14-2 Facebook實體圖（Fbid是Facebook內(nèi)部唯一的ID編號）

Facebook將所有的實體及其屬性、實體關(guān)系數(shù)據(jù)保存在TAO圖數(shù)據(jù)庫中，網(wǎng)站頁面的數(shù)據(jù)讀寫請求都由TAO來提供服務(wù)。TAO是一個采用數(shù)據(jù)“最終一致性”的跨數(shù)據(jù)中心分布式圖數(shù)據(jù)庫，由分布在多個數(shù)據(jù)中心的數(shù)千臺服務(wù)器構(gòu)成，為了能夠?qū)崟r響應(yīng)應(yīng)用請求，TAO以犧牲強一致性作為代價，系統(tǒng)架構(gòu)更重視高可用性和低延時，尤其是對讀操作做了很多優(yōu)化，以此保證在極高負載的情況下生成網(wǎng)站頁面時的高效率。

TAO為客戶端封裝了圖操作相關(guān)的數(shù)據(jù)訪問API，使得客戶端不僅可以訪問實體及其屬性，也可以方便地訪問各種實體關(guān)系數(shù)據(jù)。比如，對于關(guān)系數(shù)據(jù)的訪問可以提供如下關(guān)系列表方式的查詢接口：

(ID, aType)->[a_new,…, a_old]

其中，ID代表某個實體的唯一標記，aType指出關(guān)系類型（朋友關(guān)系等），關(guān)系列表則按照時間先后順序列出ID指向的其他滿足aType類型關(guān)系的實體ID列表。例如，（i，COMMENT）就可以列出關(guān)于i的所有評論信息。

1．TAO的整體架構(gòu)

TAO是跨越多個數(shù)據(jù)中心的準實時圖數(shù)據(jù)庫，其整體架構(gòu)如圖14-3所示。首先，TAO將多個近距離的數(shù)據(jù)中心組合成一個分區(qū)（Region），這樣形成多個分區(qū)，每個分區(qū)內(nèi)的緩存負責(zé)存儲所有的實體和關(guān)系數(shù)據(jù)。其中，在一個主分區(qū)的數(shù)據(jù)庫和緩存中集中存儲原始數(shù)據(jù)，其他多個從分區(qū)存儲數(shù)據(jù)副本（這是一種比較獨特的設(shè)計方式，建議讀者在此處先花些時間考慮一下其設(shè)計的出發(fā)點，然后閱讀后續(xù)內(nèi)容）。

之所以如此設(shè)計架構(gòu)，是出于如下考慮：緩存結(jié)構(gòu)是TAO中非常重要的一部分，對于快速響應(yīng)用戶讀請求有巨大的幫助作用，而緩存需要放在內(nèi)存中，如果內(nèi)存資源成本低且足夠大，那么理想的情況是每個數(shù)據(jù)中心都存放完整的數(shù)據(jù)副本以快速響應(yīng)用戶的讀操作，避免用戶跨數(shù)據(jù)中心讀取數(shù)據(jù)這種耗時操作。但是考慮到要存儲的數(shù)據(jù)量太大（PB級），每個數(shù)據(jù)中心都分別存儲一份完整的備份數(shù)據(jù)成本過高，所以退而求其次，將在地域上比較接近的多個數(shù)據(jù)中心作為一個整體來完整地存儲所有的備份數(shù)據(jù)，因為數(shù)據(jù)中心地域接近，所以通信效率也較高，這樣就在成本和效率之間做了一種權(quán)衡和折中。

在每個分區(qū)會存儲完整的實體及其關(guān)系數(shù)據(jù)，TAO在分區(qū)內(nèi)的存儲架構(gòu)可劃分為三層（見圖14-3），底層是MySQL數(shù)據(jù)庫層，因為數(shù)據(jù)量太多，將數(shù)據(jù)分表后形成若干數(shù)據(jù)切片（Shard），一個數(shù)據(jù)切片由一個邏輯關(guān)系數(shù)據(jù)庫存儲，一臺服務(wù)器可存儲多份數(shù)據(jù)切片。第二層是與底層數(shù)據(jù)切片一一對應(yīng)的緩存層，稱之為主Cache層（Leader Cache），主Cache負責(zé)緩存對應(yīng)的邏輯數(shù)據(jù)庫內(nèi)容，并和數(shù)據(jù)庫進行讀寫通信，最上層是從Cache層（Follower Cache），多個從Cache對應(yīng)一個主Cache，負責(zé)緩存主Cache中的內(nèi)容。TAO將緩存設(shè)計成二級結(jié)構(gòu)降低了緩存之間的耦合程度，有利于整個系統(tǒng)的可擴展性，當(dāng)系統(tǒng)負載增加時，只要添加存儲從Cache的服務(wù)器就能很方便地進行系統(tǒng)擴容。

2．TAO的讀寫操作

客戶端程序只能與最外層的從Cache層進行交互，不能直接和主Cache通信（見圖14-4）?？蛻舳擞袛?shù)據(jù)請求時，和最近的從Cache建立聯(lián)系，如果是讀取操作且從Cache中緩存了該數(shù)據(jù)，則直接返回即可，對于互聯(lián)網(wǎng)應(yīng)用來說，讀操作比例遠遠大于寫操作，所以從Cache可以響應(yīng)大部分網(wǎng)站負載。

如果從Cache沒有命中用戶請求（Cache Miss），則將其轉(zhuǎn)發(fā)給對應(yīng)的主Cache，如果主Cache也沒有命中，則由主Cache從數(shù)據(jù)庫中讀取，并更新主Cache（圖14-4中標A和D的位置展示了這一邏輯），然后發(fā)消息給對應(yīng)的從Cache要求其從主Cache加載新數(shù)據(jù)。

對于讀取操作，所有的分區(qū)不論主從都遵循上述邏輯，但是對于客戶端發(fā)出的寫操作，主分區(qū)和從分區(qū)的行為有所不同。對于主分區(qū)來說，當(dāng)從Cache接收到寫操作請求，將其轉(zhuǎn)給對應(yīng)的主Cache，主Cache負責(zé)將其寫入對應(yīng)的邏輯數(shù)據(jù)庫，數(shù)據(jù)庫寫操作成功后，主Cache向?qū)?yīng)的從Cache發(fā)出消息告知原信息失效或者要求其重新加載。對于從分區(qū)來說，當(dāng)從Cache接收到寫請求時，將其轉(zhuǎn)給本分區(qū)對應(yīng)的主Cache，此時主Cache并不直接寫入本地數(shù)據(jù)庫，而是將這個請求轉(zhuǎn)發(fā)到主分區(qū)的主Cache（圖14-4中標C的位置說明了此種情況），由其對主數(shù)據(jù)庫進行寫入。

也就是說，對于寫操作，不論是主分區(qū)還是從分區(qū)，一定會交由主分區(qū)的主Cache來更新主數(shù)據(jù)庫。在主數(shù)據(jù)庫更新成功后，主數(shù)據(jù)庫會通過消息將這一變化通知從分區(qū)的從數(shù)據(jù)庫以保持數(shù)據(jù)一致性，也會通知從分區(qū)的主Cache這一變化，并觸發(fā)主Cache通知從分區(qū)的從Cache更新緩存內(nèi)容（見圖14-4標B的位置）。

請思考：為何從分區(qū)的主Cache在讀操作未命中時從本地數(shù)據(jù)庫讀取，而不是像寫操作一樣轉(zhuǎn)發(fā)到主分區(qū)？由本地數(shù)據(jù)庫讀取的缺點是很明顯的，會帶來數(shù)據(jù)的不一致，因為從數(shù)據(jù)庫可能此時是過期數(shù)據(jù)，那么這么做的目的何在或者說有何好處？

答案：因為讀取數(shù)據(jù)在Cache中無法命中的概率遠遠大于寫操作的數(shù)量（在Facebook中，大約相差20倍），所以跨分區(qū)操作對寫操作來說，整體效率影響不大，但是如果很多讀操作采取跨分區(qū)的方法，讀取操作效率會大幅降低。TAO犧牲數(shù)據(jù)一致性是為了保證讀取操作的低延遲。

3．TAO的數(shù)據(jù)一致性

TAO為了優(yōu)先考慮讀操作的效率，在數(shù)據(jù)一致性方面做出了犧牲，采取了最終一致性而非強一致性。在主數(shù)據(jù)庫有數(shù)據(jù)變化通知從數(shù)據(jù)庫時，采取了異步通知而非同步通知，即無須從數(shù)據(jù)庫確認更新完成，即可返回客戶端對應(yīng)的請求。所以主數(shù)據(jù)庫和從數(shù)據(jù)庫的數(shù)據(jù)達到一致有一個時間差，在此期間，可能會導(dǎo)致從分區(qū)的客戶端讀出過期數(shù)據(jù)，但是經(jīng)過較小的時延，這種數(shù)據(jù)變化一定能夠體現(xiàn)到所有的從數(shù)據(jù)庫，所以遵循最終一致性。

具體而言，在大多數(shù)情況下，TAO保證了數(shù)據(jù)的“讀你所寫”一致性。即發(fā)出寫操作的客戶端一定能夠讀到更新后的新數(shù)值而非過期數(shù)據(jù)，這在很多情況下是很有必要的，比如，用戶刪除了某位好友，但如果還能在消息流看到這位好友發(fā)出的信息，這是不能容忍的。

TAO是如何做到這一點的？首先，如果數(shù)據(jù)更新操作發(fā)生在主分區(qū)，由上述寫入過程可知，一定可以保證“讀你所寫”一致性，比較棘手的情形是從分區(qū)的客戶端發(fā)出寫請求。在這種情形下，從Cache將請求轉(zhuǎn)發(fā)給主Cache，主Cache將寫請求再次轉(zhuǎn)發(fā)給主分區(qū)的主Cache，由其寫入主數(shù)據(jù)庫，在寫入成功后，從分區(qū)的主Cache通知本分區(qū)的從Cache更新緩存值，以上操作是同步完成的，盡管此時從分區(qū)的數(shù)據(jù)庫可能還未接收到主數(shù)據(jù)庫的更新消息，但是從分區(qū)的各級Cache已經(jīng)同步更新了，之后在這個從分區(qū)發(fā)出的讀請求一定可以從各級Cache中讀到新寫入的內(nèi)容。通過這種手段就可以保證從分區(qū)的“讀你所寫”一致性。

聲明：本網(wǎng)頁內(nèi)容旨在傳播知識，若有侵權(quán)等問題請及時與本網(wǎng)聯(lián)系，我們將在第一時間刪除處理。TEL:177 7030 7066 E-MAIL:11247931@qq.com