CAジャーナルクラブ TAO: Facebook’s Distributed Data Store for the Social Graph
3 likes1,496 views
社内勉強会の資料です。 Facebookでソーシャルグラフをクエリするのに使われているTAOというデータストアについての論文をサマリー形式で紹介しています。
More Related Content
More from Naoyuki Yamada (12)
CAジャーナルクラブ TAO: Facebook’s Distributed Data Store for the Social Graph
- 1. CAジャーナルクラブ TAO: Facebook s Distributed Data Store for the Social Graph 2014/12/19 山田 直行
- 2. 今回取り上げる論文?資料 TAO: Facebook's Distributed Data Store for the Social Graph ? Publications ? Research at Facebook? https://research.facebook.com/publications/ 161988287341248/tao-facebook-s-distributed-data- store-for-the-social-graph/ TAO: The power of the graph? https://www.facebook.com/notes/facebook-engineering/ tao-the-power-of-the-graph/10151525983993920 TAO: Facebook s Distributed Data Store for the Social Graph ? USENIX? https://www.usenix.org/conference/atc13/technical- sessions/presentation/bronson
- 4. 目次 - Abstract - 1. Introduction - 2. Background - 3. TAO Data Model and API - 4. TAO Architecture - 5. Implementation - 6. Consistency and Fault Tolerance - 7. Production Workload - 8. Performance - 9. Related Work - 10. Conclusion
- 6. 1. Introduction TAOができる以前は、MySQLをデータストアとして memcacheをキャッシュとして使う一般的な構成に していた( lookaside cache ) TAOはMySQLを永続化データストアとして使いつつ、 memcacheのレイヤーがグラフデータベースとして 機能するのが特徴 必要最小限のAPIを持つ AvailabilityとPer-machine E?ciencyを重視して、 Strong Consistencyを妥協している
- 8. 2.1 Serving the Graph from Memcache Memcacheをlookasideキャッシュとして使うことの問題 点について? - PHPコードがキャッシュの一部 Ine?cient edge lists? - 単純なKey-ValueストアはEdgeを扱うのに非効率 Distributed control logic? - client side(PHP側)にロジックがある Expensive read-after-write consistency? - MySQLのmaster/slave構成を前提にするとコストが高い?
- 9. 2.2 TAO s Goal TAOは複数のリージョンにまたがったデータベース として、絶えず変化するグラフデータのnodeとedge を高いパフォーマンスで取得することができる READにパフォーマンス最適化 基本的にはデータは最新のものを取得できるが、古い データを読んでしまうことも一部許容する これはFacebookをはじめとしたソーシャルネット ワークサービスの要件に適合する
- 10. 3. TAO Data Model and API people , action , relationships をnode とedgeで表現 右図のような、 Facebookでよくあるよ うなフィードの生成と表 示について考える
- 11. 3.1 Objects and Associations Object = node? - ユーザー、場所、チェックイン、コメントなど Assoc. (Association) = edge? - 友だち関係、「いいね！」、タグ付けなど
- 12. 3.2 Object API idをキーにしたCRUD(Create, Read, Update, Delete)機能 Field（Value）の一部に対してのみUpdateをかける ことも可能
- 13. 3.3 Association API edgeの多くは双方向? - 友だち関係のように、相互に対称なもの? - 許可している←→されているのように非対称なもの atypeはinverse-typeを持ち、対になっている Associationを1つの操作で扱えるようにしている
- 14. 3.4 Association Query API Association List という単位 でデータをクエリする AliceのCheckinに関するコメ ント最新50件? →assoc_range GG Bridgeに対するChekin数? → assoc_count GG BridgeのCheckIn履歴を 取得? →assoc_get
- 16. 4. TAO Architecture TAOの、複数のレイヤーの集計からなる構造について 説明し、それをどうスケールさせているのか説明する TAOは2つのCaching Layerと1つのStorage Layer から構成される
- 19. 4.3 Client Communication Stack 1つのFacebookページを表示するのに、数百の Object/Associationをクエリするのは珍しくない Client Stackとしては Scaling Memcache at Facebook で述べられているシステムと共用してい る ただしTAOのほうはデータベースを参照しにいくケー スがあるため、レイテンシは高い。そのため順序関係 なくレスポンスしていくプロトコルにしている
- 20. 4.4 Leaders and Followers Tierは、Leader Tier（各リージョンに1つだけ存在） とFollower Tier（複数存在）の2つに分けられる Follower Tierは、クライアントからのリクエストを 受け付ける。自身で結果を戻せない場合には、Leader にリクエストをフォワードして結果を取得してクライ アントに返す Leader Tierは各Followerからのリクエストを受けて Read/Writeを行う。Leaderが直接クライアントのリ クエストを受けることはない
- 22. 4.5 Scaling Geographically Readは同一Region内で完結する WriteはMaster 搁别驳颈辞苍の尝别补诲别谤に集约される
- 24. 5.1 Caching Servers TAOのキャッシュサーバーは Scaling Memcache at Facebook で述べられている仕組みをベースに、 memcacheのslab allocatorの仕組みを用いて管理して いる さらに、Object/Associationごとの生存期間を個別に 最適化するため、RAM全体をarenaといわれるゾーン 別に分けて管理している（例えばCheckinのキャッシュ は短くてよいがFriendのキャッシュは長め、など） Countなどの固定長のアイテムは、ポインタを持つのが オーバーヘッドなので直接データを持つようにしている
- 25. 5.2 MySQL Mapping データはシャードという単位に分割されている シャード＝MySQLの1データベース Objectテーブル、Associationテーブルの2つのテー ブルがあり、各データはシリアライズされて data カ ラムに格納される Association Countの結果を格納するテーブルなど、 いくつかのカスタムテーブルがある
- 26. 5.3 Cache Sharding and Hot Spots ShardはTier内にConsistent Hashingにもとづいて 配置されるが、それだけだと使われる頻度の高いデー タとそうでないものでLoadの偏りが生じる ShardはCloneしてさらに分散配置して偏りを解消さ せている 特によく参照されるデータについては、クライアント サイドに小さなキャッシュを持ち、キャッシュサーバー へのアクセスを不要にして高速化を図っている
- 27. 5.4 High-Degree Objects Objectによっては6000以上のAssociationを持つた め、全てをキャッシュはしていない。そのままクエリ をしたのではMySQLを参照しにいくリクエストが増 えてしまう それに対応するため、? - assoc_countを用いて逆のedgeをたどることによ りキャッシュにヒットさせる? - 逆のedgeも同様に多くのAssociationがある場合、? Association create time > Object create time と いう条件をつけてクエリする
- 28. 6. Consistency and Fault Tolerance TAOの最重要な要件は可用性とパフォーマンス 仮に一部のリクエストがFailしてもページの表示はし なければならない 本章では、TAOの平常時の一貫性モデルと、Failした 場合に一貫性をどのように犠牲にしているかを説明す る
- 30. 6.2 Failure Detection and Handling Database failures? - masterダウン時にはslave昇格? - slaveダウン時にはLeaderにフォワード Leader failures? - Leaderの一貫性を復旧しようと試みる、復活するまでは古いデー タを返す Re?ll and invalidation failures? - ディスクのキューに保存 Follower failures? - バックアップのFollowerが対応 等々
- 34. 9. Related Work Eventual Consistency(結果整合性)? - read-after-write consistencyは結果整合性の一種 地理的に分散したデータストア? - Coda ?le system? - Megastore? - Spanner(Google) 分散ハッシュテーブルとKey-Valueシステム? - Amazon Dynamo? - Voldemort(LinkedIn)
- 35. 階層構造のネットワーク接続(Leader and Follower)? - Akamaiのコンテンツキャッシュ 構造化ストレージ(RelationalDBでないもの)? - Bigtable(Google)? - PNUTS(Yahoo!)? - SimpleDB(Amazon)? - HBase(Apache)? - Redis
- 36. グラフDB? - Neo4J? - FlockDB(Twitter) より進んだグラフDBの操作API? - PEGASUS? - Pig Latin(Yahoo!)? - Pregel(Google)?