論文メモ TAO: Facebook's Distributed Data Store for the Social Graph
February 4, 2021TAOは、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の全体像をしめす。
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のレプリケーションストリームにふくまれ、トランザクションが複製された直後に伝達される。
論文をこちらからダウンロードできます。 また、図はすべて論文から引用されています。