aaa.txt : Introducing FlockDB (1)

またTwitter engineering Blogで興味のある記事があったので、適当に訳しながらメモ。

Introducing FlockDB


Twitterは人間関係のグラフをたくさん持っている。
例えば、あなたがFollowしている人全員とか、
あなたをfollowしている人全員とか。
あなたが誰からのphone notificationを受けているとか。

こういうグラフのいくつかの特徴は我々が成長する
ごとに、スケーラブルに保管するすることが難しい課題に
なってきた。たとえば、お互いのfriendship構築にリクエストと
確認を必要とするのではなく、あなたは他の誰かをfollowする
単に１方向の関係のみ構築する。またそこにはあなたを何人が
followする人数の制限がない、そのため（@apluskのような)
あるひとは100万人にfollowされたりするが、多くはほんの数人である。

Tweetを届けるために、我々はある人のfollowerが誰であるかを
素早くルックアップできなくてはならない。しかし、我々は同時に
我々は頻繁な書き込みのトラフィックをハンドリングできなくては
ならない、それはFollowerがが追加されたり除かれたり、または
スパマーが捕まって凍結されたりといった事も含む。さらに
他の操作例えば@mentionによる配達では、我々は「これらのユーザをの
両方をFollowしているのは誰？」といった集合演算を要する。
こういった特徴は伝統的なRDBでは実装するのが難しい。

奮闘

我々は初期の日々、RDBの酷使から非正規化したkey&vaklueストアを含む
ストレージレイヤーを調査した。それぞれ書き込み操作のハンドリングや
巨大な結果セットの表示のどちらかは得意だったが、両方が得意では
なかった。

数年後我々は新しいことを試す必要があることがわかってきた。
我々のゴールは以下のとおり。
・書き込みは可能な限り単純にする。
・すぐ手に入るMySQLをストレージエンジンに使う、なぜなら
　我々は通常使用や、酷使した場合や、通常起こらない事故の条件下
　におけるそれの振る舞いをよく理解していたから。
・水平分割を可能にする。つまり我々のcorpusが成長するにつれ
　データベースのハードウェアを追加できるように
・書き込みの順番が前後することを許す、または複数回繰り返して
　書き込みをすることを許す。(つまり作業が失われるよりは冗長な
　書きこみが行われる失敗の法を許す)

FlockDBがその結果だ。我々はだいたい9ヶ月前にマイグレーションを
完了し、その後前進を続けてきた。

さらなる奮闘

FlockDBはグラフデータを保管するデータベースであるが、グラフの
巡回操作には最適化されていない。その代わり巨大な隣接リスト
に最適化され読み取り書き込みが高速で、集合演算問い合わせが
取り扱える。

FlockDBはグラフを64bit整数でIDを振られたノード間の辺として保存する。
ソーシャルグラフではノードのIDはユーザIDであるが、"お気に入り"
を保管するグラフでは宛先ノードはTweetIDになる。それぞれの辺も
ソートのために64bitのpositionでマークされる。(Twitterは
"following"グラフでもタイムスタンプを用いているので、
あなたのfollowerリストは最新順に表示される。)

辺が削除された場合、実際にMySQLのレコードが削除されるわけではない。
単にstateが削除済みにマークされ、これはプライマリキーを変化させる効果が
ある(複合キーはソースID、state、position)。同様に削除されたアカウントが
あった場合はアーカイブ状態になり、後でリストアするが可能である。
(だがこれは限られた期間である、我々のterms of serviceによれば)
我々は複合主キーと各行へのインデックスを両方持っているので
すべてのクエリにひとつのインデックスで応答できる。この種の
スキーマ最適化はMySQLを輝かしくそして予測可能なパフォーマンスを
我々に与える。

「オバマ大統領をFollowしている人と、私のFollowしている人との積集合は？」
などの複雑なクエりも、単一ユーザ(「オバマ大統領をFollowしている人はだれ？」
)のクエリに分解し高速に応答することができる。データはノードにより
パーティションニングされ、クエリはインデックス化された範囲クエリを使って
それぞれ単一パーティションで応答可能である。同様に巨大な結果セットを
Limit/Offsetを使ってページングするときにもクエリはインデックスを使って
高速に応答できる。

。。。今日はここまで。