論文メモ TAO: Facebook's Distributed Data Store for the Social Graph

February 4, 2021

TAOは、Facebookで開発されたソーシャルグラフのためのマルチリージョンの分散システムで、秒間10億件の読み込みと数百万件の書き込みの性能を発揮する。 Facebookは、もともとソーシャルグラフを、MySQLに保存し、memcacheでキャッシュし、PHPで問いあわせるシステムで構成していた。 TAOは、そのシステムの現状を引きつぎ、MySQLをストレージに採用している。

ソーシャルグラフのノードをobject, 辺をassociationとよぶ。 objectは、64ビットの整数値のidで一意に特定できる。 associationは、32ビットで時間をあらわすtimeと値をもつ。 objectとassociationには連想配列をもたせることができる。以下のid1, id2はobjectのIDであり、otype, atypeは、ユーザやフォローなど、objectやassociationがあらわすソーシャルグラフ上の意味にあたる。

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

TAOは、associationのクエリAPIを提供する。ユーザは、たとえば、id1, atypeでassociationの件数をかぞえたり、associationを検索できたりする。ソーシャルグラフの多くのデータは古く、一方で、クエリの対象になるデータは新しいものが多い。この時間の局所性をいかすために、内部では、idとatypeが同じassociationは時間順に並べて管理される。この配列はassociation listとよばれ、次の構造をとる。

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

TAOには永続層とキャッシュ層がある。永続層にシャーディング化されたMySQLがあり、キャッシュ層にはLeader, Followerの2種類のキャッシュサーバがある。また、TAOは複数のデータセンタ上に展開されており、データセンタのまとまりをregionといい、regionはMasterとSlaveで区別される。以下の図は、TAOの全体像をしめす。 tao

objectを格納するシャードはobject idで、assiciationはid1できまる。これらのIDは、保存先のシャードを特定するID shard_idをふくむ。

複数のキャッシュサーバのまとまりをtierという。全てのキャッシュサーバが互いに通信するとホットスポットができるため、キャッシュ層は、一つのleader tierと複数のfollower tierに分割されている。 leader tierは、永続層への読み込み、書き込みを担当する。 followerは読み込みミスや書き込みリクエストをleaderに送る。 followerは、ほかのtierに問いあわせなくても、どんなリクエストであっても応答できる。クライアントは、follower tierと通信し、leaderには直接リクエストを送らない。

各シャードはひとつのleaderに対応し、書き込みは対応するleaderからしか送られない。 leaderがobjectを更新すると、キャッシュを無効にするメッセージ(invalidation message)をfollwerに送る。メッセージにはバージョン番号がふくまれており、followerは、番号からメッセージの新しさを調べ、古いものを無視する。更新によって、followerにキャッシュされた大量のassociationが無効になることがある。そのため、leaderは、refillメッセージをfollowerにおくり、association listを再キャッシュするようfollowerに伝える。

巨大なソーシャルグラフのホスティングするために、TAOは複数のデータセンタをまたいで展開されている。複数のデータセンタのまとまりをregionとよばれ、少数のregionが存在する。各regionは、ソーシャルグラフ全体の複製をホスティングしている。ネットワークのレイテンシを抑えるために、masterのregionとslaveのregionのmaster/slave構成をとり、どんな読み込みリクエストも単一のregion内で完結される。 masterとslaveにあるfollowerはどちらも同じ動きをするが、slaveのleaderは、read missが生じても、ローカルのfollowerに古いデータを返す。データの新しさを犠牲にすることで、master regionへのリクエストにかかる時間を省いている。 slaveのleaderは書き込みリクエストをmasterのleaderに伝達する。前述のinvalidationやrefillメッセージは、MySQLのレプリケーションストリームにふくまれ、トランザクションが複製された直後に伝達される。

論文をこちらからダウンロードできます。また、図はすべて論文から引用されています。