概述

Facebook TAO[1] ，即 The Associations and Objects 的縮寫，點(diǎn)(對(duì)象，Object)和邊(聯(lián)結(jié)，Associations)是”圖“中最基本的抽象，用來做 Facebook 圖存儲(chǔ)名字倒是恰如其分。

概括來說，TAO 是 Facebook 為了解決社交場(chǎng)景下，超大數(shù)據(jù)的更新與關(guān)聯(lián)讀取問題，其核心特點(diǎn)如下：

• 提供面向 Facebook 社交信息流場(chǎng)景特化的圖 API ，比如點(diǎn)查、一度關(guān)聯(lián)查詢、按時(shí)間的范圍查詢。
• 兩層架構(gòu)，MySQL 做存儲(chǔ)層，MemeCache 做緩存層;緩存層又可細(xì)分為主從兩層。
• 可多機(jī)房擴(kuò)展，高度面向讀性能優(yōu)化，只提供最終一致性保證。

歷史沿革

Facebook 早期沉淀的數(shù)據(jù)就在 MySQL 上[2]，MySQL 扛不住后，在 2005 年時(shí)，扎克伯格便引入了 MemCache 做緩存層，應(yīng)對(duì)更高頻的讀請(qǐng)求。自此之后，MySQL 和 MemCache 便成為了 Facebook 存儲(chǔ)層技術(shù)棧的一部分。

Facebook 數(shù)據(jù)請(qǐng)求負(fù)載通常符合時(shí)間局部性(即最近更新的數(shù)據(jù)最容易被訪問)，而非空間局部性。但 MySQL 中的數(shù)據(jù)通常不是按照時(shí)間有序存儲(chǔ)的，因此 MySQL InnoDB 引擎自帶的 block cache 并不匹配這一特點(diǎn)。另外，MemCache 本身只提供基于內(nèi)存的 KV 訪問模型，為了更高效的利用這些內(nèi)存，F(xiàn)acebook 需要針對(duì)社交場(chǎng)景自己定制緩存策略，以盡可能多的讓讀請(qǐng)求命中。

將這些工程細(xì)節(jié)，包括兩層存儲(chǔ)集群，包括自行組織緩存，都暴露給應(yīng)用層工程師，帶來了很大的工程復(fù)雜度，引發(fā)了更多的 bug，降低了產(chǎn)品迭代速率。為了解決這個(gè)問題，F(xiàn)acebook 在 2007 年使用 PHP 在服務(wù)端做了一個(gè)抽象層，基于圖存儲(chǔ)模型，圍繞點(diǎn)(對(duì)象)和邊(聯(lián)結(jié))提供 API。由于社交場(chǎng)景中的喜歡、事件、頁面等都可以通過圖模型來方便表達(dá)，這一抽象層極大的降低了應(yīng)用層工程師的心智負(fù)擔(dān)。

但隨著所需 API 越來越多，將圖模型層(在 webserver 上)和數(shù)據(jù)層(在 MySQL和MemCache 集群)分離實(shí)現(xiàn)的缺點(diǎn)逐漸暴露了出來：

從邊集合的微小更新，會(huì)導(dǎo)致整個(gè)邊集合失效，從而降低緩存命中率。

請(qǐng)求邊列表的一個(gè)微小子集也需要將整個(gè)邊列表從存儲(chǔ)端拉到服務(wù)端。

緩存一致性很難維持。

當(dāng)時(shí)的 MemCache 集群很難協(xié)同支持實(shí)現(xiàn)一個(gè)純客戶端側(cè)的驚群避免策略。

所有這些問題，都可以通過重新設(shè)計(jì)統(tǒng)一的、基于圖模型的存儲(chǔ)層來實(shí)現(xiàn)。從 2009 年開始，TAO 便在 Facebook 內(nèi)部的一個(gè)團(tuán)隊(duì)開始醞釀。再之后，TAO 逐漸發(fā)展成了支撐每秒數(shù)十億次讀取、數(shù)百萬次寫入，部署于跨地區(qū)海量機(jī)器上的分布式服務(wù)。

圖模型 & API

圖的最基本組成就是點(diǎn)和邊，對(duì)應(yīng)到 TAO 里就是，對(duì)象(Objects)和聯(lián)結(jié)(Associations)。對(duì)象和聯(lián)結(jié)都可以包含一系列由鍵值對(duì)表示的屬性。

Object: (id) → (otype, (key  value)*) 
Assoc.: (id1, atype, id2) → (time, (key  value)*) 

注：TAO 中的邊都是有向邊。

以社交網(wǎng)絡(luò)為例，對(duì)象可以是用戶、打卡、地點(diǎn)、評(píng)論，聯(lián)結(jié)可以是朋友關(guān)系、發(fā)表評(píng)論、進(jìn)行打卡、打卡于某地等等。

如下圖 a)，假設(shè)在 Facebook 上有這么一事件：Alice 和 Bob 在金門大橋打了個(gè)卡，Cathy 評(píng)論：真希望我也在那。David 喜歡了這條評(píng)論。

用圖模型表示后，如下圖 b)：

一個(gè)栗子

可以看到，所有的數(shù)據(jù)條目如用戶、地點(diǎn)、打卡、評(píng)論都被表示成了帶類型的對(duì)象(typed objec)，而對(duì)象間的關(guān)系如被誰喜歡(LIKED_BY)、是誰的朋友(FRIEND)、被誰評(píng)論(COMMENT)，則被表示成了帶類型的聯(lián)結(jié)(typed associations)。

另外，盡管 TAO 中聯(lián)結(jié)都是單向的，但實(shí)際中大部分關(guān)系是雙向的。這時(shí)，可以增加一個(gè)反向邊(inverse edges)來表示此種雙向關(guān)系。

最后，由于聯(lián)結(jié)是三元組，因此兩個(gè)對(duì)象間可以有多條不同類型的邊，但是同一類型的邊，只能有一條。但在有些非社交場(chǎng)景中，可能需要相同類型的邊也有多條。

Object API

圍繞 Object 的操作，是常見的增刪改查(create / delete / set-fields / get )。

同一對(duì)象類型(object type)的對(duì)象具有同樣的屬性集(fields，即上面提到的 (key value)*)，也就是說，一個(gè)對(duì)象類型對(duì)應(yīng)固定的屬性集。可以通過修改對(duì)象類型的 Schema 來對(duì)其所含屬性進(jìn)行增刪。

Association API

圍繞 Association 的基本操作，也是增刪改查。其中增刪改如下：

assoc_add(id1, atype, id2, time, (k→v)*) – 新增或者覆蓋 
assoc_delete(id1, atype, id2) – 刪除 
assoc_change_type(id1, atype, id2, newtype) - 修改 

值得一說的是，如果其反向邊((id1, inv(atype), id2))存在，則上述 API 會(huì)同時(shí)作用于其反向邊。由于多數(shù)場(chǎng)景下的聯(lián)結(jié)是雙向的，因此 Facebook 將其邊的 API 默認(rèn)行為同時(shí)作用于兩條邊。

另外，每個(gè) Association 都會(huì)自動(dòng)打上一個(gè)重要的特殊屬性：聯(lián)結(jié)時(shí)間(association time)。由于 Facebook 負(fù)載具有時(shí)間局部性，利用此時(shí)間戳可以對(duì)緩存數(shù)據(jù)集進(jìn)行優(yōu)化，以提高緩存命中率。

Association Query API

圍繞 Association 的查詢 API，是 TAO 的核心 API，流量最大。這負(fù)載類型包括：

1. 指定 (id1, type, id2) 的點(diǎn)查，通常用來確定兩個(gè)對(duì)象間是否存在對(duì)應(yīng)聯(lián)結(jié)，或者獲取對(duì)應(yīng)聯(lián)結(jié)的屬性。
2. 指定 (id1, type) 的范圍查詢，要求結(jié)果集按時(shí)間降序排列。比如一個(gè)常見場(chǎng)景：該條內(nèi)容最新的 50 條評(píng)論是什么?。此外，最好能提供迭代器形式的訪問。
3. 指定 (id1, type) 出邊數(shù)查詢。比如查詢*某條評(píng)論的喜歡數(shù)是多少?*此種查詢很常見，因此最好將其直接存下來，以能夠在常數(shù)時(shí)間內(nèi)返回結(jié)果。

盡管聯(lián)結(jié)千千萬，但最近的范圍是重點(diǎn)查詢對(duì)象(時(shí)間局部性)，因此聯(lián)結(jié)的查詢 API 主要圍繞時(shí)間的范圍查詢展開。

為此，TAO 將最基本的聯(lián)結(jié)集定義為 Association List。一個(gè) Association List 是以 id1 為起點(diǎn)，出邊類型為 atype 的所有聯(lián)結(jié)的集合，按時(shí)間降序排列。

Association List: (id1, atyle) -> [a_new, ..., a_old] 

基于此，定義更細(xì)粒度的幾個(gè)接口：

// 返回以 id1 為起點(diǎn)，以 id2set 集合所包含點(diǎn)為終點(diǎn) 
// 創(chuàng)建時(shí)間 time 滿足 low <= time <= high 
// 的聯(lián)結(jié)集合。 
assoc_get(id1, atype, id2set, high?, low?)  
 
// 返回聯(lián)結(jié)集合的數(shù)量 
assoc_count(id1, atype) 
 
// 返回下標(biāo)滿足 [pos, pos+limit) 的聯(lián)結(jié)集合子集 
// pos 即 Association List 中的下標(biāo) 
assoc_range(id1, atype, pos, limit)  
 
// 返回創(chuàng)建時(shí)間 time 滿足，從 time <= high **倒序**起始， 
// 到 time >= low 終止，不超過 limit 條聯(lián)結(jié) 
assoc_time_range(id1, atype, high, low, limit) 

為什么結(jié)果集按時(shí)間降序排列呢?因?yàn)樵?Facebook 頁面信息流展示時(shí)，總是先展示最新的，然后隨著不斷下拉，依次加載較舊的數(shù)據(jù)。

舉個(gè)栗子：

• “50 most recent comments on Alice’s checkin” ⇒ assoc_range(632, COMMENT, 0, 50) 
• “How many checkins at the GG Bridge?” ⇒ assoc_count(534, CHECKIN) 

架構(gòu)

TAO 架構(gòu)

TAO 架構(gòu)整體分兩層，緩存層(caching layer)和存儲(chǔ)層(storage layer)。

存儲(chǔ)層

由于前面所說的歷史原因，TAO 使用 MySQL 作為存儲(chǔ)層。

因此，TAO 對(duì)外的 API 最終會(huì)被轉(zhuǎn)化成 MySQL 語句作用于存儲(chǔ)層，但對(duì) MySQL 的查詢語句都相對(duì)簡(jiǎn)單。當(dāng)然，存儲(chǔ)層也可以使用 LevelDB 這種 NoSQL 存儲(chǔ)引擎，這樣查詢語句就會(huì)對(duì)應(yīng)翻譯為前綴遍歷。當(dāng)然，選擇存儲(chǔ)引擎不止要看 API 翻譯方便與否，還要看數(shù)據(jù)備份、批量導(dǎo)入導(dǎo)出、多副本同步等非 API 因素。

單個(gè) MySQL 服務(wù)肯定存不下所有 TAO 數(shù)據(jù)，因此 TAO 使用了 MySQL 集群支撐存儲(chǔ)層。為了將數(shù)據(jù)均勻的分到多個(gè) MySQL 機(jī)器上，TAO 使用一致性哈希算法將數(shù)據(jù)在邏輯上進(jìn)行了切片(shard)。每個(gè)切片存到一個(gè) MySQL db 中。每個(gè) Object 在創(chuàng)建時(shí)會(huì)關(guān)聯(lián)一個(gè) shard，并將 shard_id 做到 object_id 中，因此在 Object 整個(gè)生命周期中其 shard 都不會(huì)再改變。

具體來說，MySQL 中所存數(shù)據(jù)主要包括兩張表，一個(gè)點(diǎn)表，一個(gè)是邊表。其中，點(diǎn)和其出邊會(huì)存在同一個(gè) MySQL db 中，以最小化關(guān)聯(lián)查詢代價(jià)。所有的點(diǎn)屬性在保存時(shí)，會(huì)被序列化到一個(gè)叫做 data 的列。如此，可以將具有不同類型的 Object 保存到一張表中。邊和點(diǎn)保存時(shí)類似，但是會(huì)額外在 id1,atype,andtime 字段上做索引，以方便基于某個(gè)點(diǎn)的出邊的范圍查詢。此外，為了避免對(duì)邊的數(shù)量的查詢所帶來的高昂開銷，會(huì)額外用一張表來保存 associations 的數(shù)量。

緩存層

讀寫穿透。TAO 的存儲(chǔ)層實(shí)現(xiàn)了所有對(duì)外 API，對(duì)客戶端( Client )完全屏蔽了存儲(chǔ)層。即，Clients 只和緩存層進(jìn)行交互，緩存層負(fù)責(zé)將數(shù)據(jù)同步到存儲(chǔ)層。緩存層也是由多個(gè)緩存服務(wù)器構(gòu)成，能夠 Serve 任意 TAO 請(qǐng)求的一組緩存服務(wù)器稱為一個(gè) Tier。單個(gè)請(qǐng)求會(huì)路由到單個(gè)緩存服務(wù)器，不會(huì)跨多個(gè)服務(wù)器。

緩存策略使用經(jīng)典的 LRU。值得一提的是，由于 TAO 的邊默認(rèn)是雙向的，在 Client 寫入邊時(shí)，由緩存層變成負(fù)責(zé)將其變?yōu)閷懭ミ吅突剡叺膬蓚€(gè)有向邊，但 TAO 并不保證其原子性。失敗了會(huì)通過垃圾回收來刪除中間結(jié)果。

兩層架構(gòu)。TAO 中的每個(gè)邏輯分片(Shard)基本是同構(gòu)的。每個(gè)邏輯分片的緩存層包括一組緩存服務(wù)器，由單個(gè) Leader 緩存服務(wù)器和一組 Follower 緩存服務(wù)器構(gòu)成。

其中，F(xiàn)ollowers 緩存服務(wù)器是外層，Leader 服務(wù)器是內(nèi)層。所有客戶端只和 Followers 打交道，F(xiàn)ollowers 緩存服務(wù)器本身只負(fù)責(zé)讀請(qǐng)求，如果發(fā)現(xiàn)讀未命中或者有寫請(qǐng)求，就將其轉(zhuǎn)發(fā)給所對(duì)應(yīng) Leader 緩存服務(wù)器。

如果讀請(qǐng)求負(fù)載持續(xù)增加，對(duì) Follower 緩存服務(wù)器擴(kuò)容即可。

如果對(duì)某些 object 訪問顯著高于其他，TAO 會(huì)通過記錄訪問頻次對(duì)其識(shí)別，然后進(jìn)行客戶端側(cè)的緩存，并通過版本號(hào)來維持一致性。

一致性。Leader 收到多個(gè) Follower 的并行寫請(qǐng)求后會(huì)將其進(jìn)行定序，序列化后到存儲(chǔ)層進(jìn)行同步讀寫后返回;對(duì)于寫請(qǐng)求來說，還會(huì)異步的通知其他 Follower 服務(wù)進(jìn)行對(duì)應(yīng)數(shù)據(jù)的更新，因此 TAO 最終只能提供最終一致性保證。這樣做的好處是換來了讀請(qǐng)求的高吞吐。

多地?cái)U(kuò)展。由于 TAO 的讀請(qǐng)求頻次約為寫頻次的 25 倍，而單地?cái)?shù)據(jù)中心(datacenter)又不能滿足 Facebook 全球場(chǎng)景。因此 TAO 整體上使用了主從架構(gòu)，兩個(gè) datacenter 都部署一套存儲(chǔ)層+緩存層作為主從(Primary-Secondary)，所有寫請(qǐng)求都要由從數(shù)據(jù)中心的 Leader Cache 路由到主數(shù)據(jù)中心(見上圖)，然后由主數(shù)據(jù)中心存儲(chǔ)層異步傳回從數(shù)據(jù)中心。但從數(shù)據(jù)中心的 Leader Cache 并不等本地存儲(chǔ)層同步回?cái)?shù)據(jù)，即進(jìn)行更新，并通知 Followers 到自己這 Refill。TAO 的這種設(shè)計(jì)，能夠最大化的保證一個(gè)讀取請(qǐng)求在一個(gè) DataCenter 內(nèi)被滿足，代價(jià)是客戶端可能會(huì)讀到過時(shí)數(shù)據(jù)。即犧牲一致性，來降請(qǐng)求低延遲，提高吞吐。

一致性

TAO 在一致性和可用性取舍方面時(shí)，選擇了后者。為了高可用性和極致的性能，選擇了弱化的一致性模型——最終一致性。因?yàn)樵?Facebook 的大部分場(chǎng)景下，不可用要比不正確更加糟糕。在大部分常見場(chǎng)景下，TAO 能做到更強(qiáng)的寫后讀一致性(read after write consistency)。

TAO 中同一份數(shù)據(jù)，首先，會(huì)進(jìn)行 Master-Slave Region 進(jìn)行主從備份;其次，在同一 Region 中，會(huì)使用 Leader-Follower Cache 做兩層緩存。更新時(shí)，不同位置的數(shù)據(jù)不同步，便會(huì)造成數(shù)據(jù)的不一致。在 TAO 中，在更新后給足夠時(shí)間間隔，所有的數(shù)據(jù)副本都會(huì)趨向一致，并且體現(xiàn)最新更新。而通常，這個(gè)時(shí)間間隔不會(huì)超過 1s 。這在 Facebook 中大多數(shù)場(chǎng)景是沒有問題的。

對(duì)于那些對(duì)一致性有特殊要求的場(chǎng)景，應(yīng)用層可以將請(qǐng)求標(biāo)記為 critical。TAO 在接到有此標(biāo)記的請(qǐng)求時(shí)，會(huì)將其轉(zhuǎn)發(fā)到 Master Region 進(jìn)行處理，進(jìn)而獲取強(qiáng)一致性。

參考

[1] TAO 論文：https://www.usenix.org/system/files/conference/atc13/atc13-bronson.pdf

[2] Facebook 技術(shù)博客，TAO——圖的威力：https://engineering.fb.com/2013/06/25/core-data/tao-the-power-of-the-graph/

[3] meetup TAO：https://www.notion.so/Meetup-1-Facebook-TAO-28e88836a3f649ba9b3e3ea83858c593 

[4] stanford 6.S897 課件：https://cs.stanford.edu/~matei/courses/2015/6.S897/slides/tao.pdf