【しばらく編集不可モードで運営します】 編集(管理者用) | 差分 | 新規作成 | 一覧 | RSS | FrontPage | 検索 | 更新履歴

HowFriendFeedUsesMySqlToStoreSchemaLessData - FriendFeed では MySQL を使いどのようにスキーマレスのデータを保存しているのか

目次

FriendFeed? では MySQL を使いどのようにスキーマレスのデータを保存しているのか

この記事について

FriendFeed? では MySQL を使いどのようにスキーマレスのデータを保存しているのか

2009 年 2/27 日

背景

私たち FriendFeed は, 全てのデータを保存するのに MySQL を利用している. ユーザ数が増えるに従い, データベースはとても大きくなった. 今や 2 億 5 千万ものエントリーと, 他にも コメントや "like", フレンドリストなど, 多くのデータを保存している.

データベースが巨大化するのに合わせ, 私たちは急速な成長によっておこるスケール上の問題に何度も取り組んできた. read slave や memcached を使って読み出しのスループットを改善したり, データベースを shard にして書き込み性能を改善するなど, お決まりの手は打った. しかし既存機能を成長に伴うトラフィックに応えてスケールする作業のせいで, 新機能の追加は減ってしまった.

特にスキーマ変更に伴うインデクスの追加は, 1-2 千万行もあるデータベースだと一度に数時間ものロックがおきてしまう. 古いインデクスを削除するにも同じくらい時間がかかる. かといって消さずに置くのも性能を損ねる. データベースは INSERT のたびに使いもしないブロックを読み書きし, 大事なデータをメモリから追い出してしまうからだ. このような問題を避けようとすると, 複雑な運用手順が必要になる (新しいインデクスを slave につくってから slave と master を入れ替える, とか.) こうした運用手順は間違いやすくヘビーなものであるため, 暗にスキーマやインデクスの変更を要する機能の追加を妨げてしまう. 私たちのデータベースは激しく shard されているため, MySQL の JOIN のようなリレーショナル機能はまったく役に立っていない. そこで RDBMS 領域の外にも目をやることにした.

柔軟なスキーマを保存し, インデクスをオンザフライに作成するという問題に挑むプロジェクトは多い. (例: CouchDB) しかし大きなサイトで十分に広く利用され, これなら大丈夫という確信が持てるものはなかった. 資料を読み, 実際に自分達で動かしてもみたが, どれも私たちの要求に答えるだけの安定性を持っていたり, しこたまテストされているものはなかった. (たとえば CouchDB に関するこのやや古い記事を読んで欲しい. ) MySQL はちゃんと動く. データを壊したりしない. 複製もできる. その限界について私たちは既に理解している. 私たちはストレージとしての MySQL が気に入っている. ただし使い方は RDBMS じゃない.

討議を重ねた末, 私たちはまったく新しいストレージシステムを使うのではなく, MySQL の上に "スキーマレス" なストレージシステムを実装することにした. この記事ではシステムの高レベルな仕組みを紹介したいとおもう. 私たちは他の巨大サイトがどのように問題に取り組んでいるのか興味があるから, 私たちの設計も他の開発者にとって少しは立つかもしれない.

概観

私たちのデータストアは, スキーマレスなプロパティの集合だ. (JSON や Python のディクショナリのようなもの.) 保存する実体(entity)に唯一必要なプロパティは id で, これは 16 バイトの UUID の値である. 実体の他の部分は, データストアの視点からは見えない(opaque). "スキーマ" を変更するには, 単に新しいプロパティを保存すればいい.

こうした実体に付けるインデクスは, MySQL の別のテーブルに保存する. ある実体の三つのプロパティにインデクスを付けたいなら, テーブルは三つできる ... プロパティごとにテーブルを一つ作る. インデクスの利用をやめたいときは, まずコードからインデクス用テーブルへ書き込むのを止め, それからテーブルを MySQL から drop する. 新しいインデクスが欲しくなったらそのインデクス用に新しいテーブルを作り, そのインデクスを作るプロセスを非同期に動かす. このプロセスは稼働中のサービスの邪魔はしない.

結果として以前より多くのテーブルができる. けれどインデクスの追加や削除は簡単になった. 新しいインデクスの構築を高速に, かつサイトの稼動を妨げないよう行うため, インデクスを作るプロセス (内輪で "The Cleaner" と呼んでいる.) は激しく最適化してある. 新しいプロパティを追加してインデクスを作るのは, 週単位ではなく日単位の作業になった. そしてもともと必要だった, MySQL の master と slave の入れ替えその他の 怖い作業もなくなった.

詳細

MySQL 上では, 実体は次のようなテーブルに保存される:

 CREATE TABLE entities (
     added_id INT NOT NULL AUTO_INCREMENT PRIMARY KEY,
     id BINARY(16) NOT NULL,
     updated TIMESTAMP NOT NULL,
     body MEDIUMBLOB,
     UNIQUE KEY (id),
     KEY (updated)
 ) ENGINE=InnoDB;

added_id の列があるのは, InnoDB が物理的には主キーの順でデータ行を保存するからだ. AUTO_INCREMENT の主キーがあることで, 新しい実体が古い実体に続いてシーケンシャルに書き込まれることを保証できる. これは書き込みや読み出しの局所性に寄与する. (FriendFeed? のページは時系列と反対の順に表示されるため, 新しい実体は古い実体より頻繁に読み書きされる.) 実体の中身は Python のディクショナリを pickle し, zlib で圧縮したものだ.

インデクスは独立したテーブルに保存される. 新しいインデクスを作るときは, インデクスをつけたい属性の値を全ベータベースの shard から保存するテーブルを作る. たとえば FriendFeed? での典型的な実体は次のようなかんじになるだろう:

 {
     "id": "71f0c4d2291844cca2df6f486e96e37c",
     "user_id": "f48b0440ca0c4f66991c4d5f6a078eaf",
     "feed_id": "f48b0440ca0c4f66991c4d5f6a078eaf",
     "title": "We just launched a new backend system for FriendFeed!",
     "link": "http://friendfeed.com/e/71f0c4d2-2918-44cc-a2df-6f486e96e37c",
     "published": 1235697046,
     "updated": 1235697046,
 }

あるユーザが投稿した実体をページに出すため, 実体の user_id 属性にインデクスをつけたいとする. インデクスのテーブルは次のようになる:

 CREATE TABLE index_user_id (
     user_id BINARY(16) NOT NULL,
     entity_id BINARY(16) NOT NULL UNIQUE,
     PRIMARY KEY (user_id, entity_id)
 ) ENGINE=InnoDB;

データストアはよきに振舞い, インデクスを自動で管理してくれる. データストアのインスタンスに上記のような構造を持つ実体を インデクス付きで保存したいときは, 次のようなコードを(python で)書けばいい:

 user_id_index = friendfeed.datastore.Index(
     table="index_user_id", properties=["user_id"], shard_on="user_id")
 datastore = friendfeed.datastore.DataStore(
     mysql_shards=["127.0.0.1:3306", "127.0.0.1:3307"],
     indexes=[user_id_index])
 
 new_entity = {
     "id": binascii.a2b_hex("71f0c4d2291844cca2df6f486e96e37c"),
     "user_id": binascii.a2b_hex("f48b0440ca0c4f66991c4d5f6a078eaf"),
     "feed_id": binascii.a2b_hex("f48b0440ca0c4f66991c4d5f6a078eaf"),
     "title": u"We just launched a new backend system for FriendFeed!",
     "link": u"http://friendfeed.com/e/71f0c4d2-2918-44cc-a2df-6f486e96e37c",
     "published": 1235697046,
     "updated": 1235697046,
 }
 
 datastore.put(new_entity)
 entity = datastore.get(binascii.a2b_hex("71f0c4d2291844cca2df6f486e96e37c"))
 entity = user_id_index.get_all(datastore, user_id=binascii.a2b_hex("f48b0440ca0c4f66991c4d5f6a078eaf"))

上の Index クラスは全ての実体から user_id プロパティを検出し, index_user_id テーブルのインデクスを自動で保守する. データベースは shard 化されているから, インデクスを保存する shard を決めるために shard_on 引数がある. (上の例では entity["user_id"] % num_shards で決まる.)

インデクスを使って問い合わせをするには, インデクスのインスタンスを使う. (上の例にある user_id_index.get_all を参照.) データストアのコードは python の中で index_user_id と 実体のテーブルの間の "join" を行う. まず 全 shard の index_user_id テーブルに問い合わせて実体の ID リストを取得し, 次にその 実体 ID で実体のテーブルを引く.

新しいインデクスを追加するには, たとえば link プロパティに追加するときは, 新しいテーブルを作る:

 CREATE TABLE index_link (
     link VARCHAR(735) NOT NULL,
     entity_id BINARY(16) NOT NULL UNIQUE,
     PRIMARY KEY (link, entity_id)
 ) ENGINE=InnoDB DEFAULT CHARSET=utf8;

データストアの初期化コードも新しいインデクスを含むよう書き直す:

 user_id_index = friendfeed.datastore.Index(
     table="index_user_id", properties=["user_id"], shard_on="user_id")
 link_index = friendfeed.datastore.Index(
     table="index_link", properties=["link"], shard_on="link")
 datastore = friendfeed.datastore.DataStore(
     mysql_shards=["127.0.0.1:3306", "127.0.0.1:3307"],
     indexes=[user_id_index, link_index])

それから (稼動中であっても) 以下のように非同期でインデクスを構築する:

 ./rundatastorecleaner.py --index=index_link

一貫性と原子性

データベースは shard 化されており, インデクスは実体に含まれるのではなく別の shard に保存されているため, 一貫性には問題がある. インデクスのテーブルを書き終える前にプロセスがクラッシュしたらどうなるだろうか?

野心溢るる FriendFeed? エンジニアの大半にとってトランザクションプロトコルの実装は ぐっとくるものだったが, 私たちはシステムをできるかぎり単純にしたかった. そこで以下のとおり制約を緩めることにした:

結果として, データベースへの新しい実体の書き込みは次のような手順をとる:

 1. 実体を実体テーブルに書き込む. InnoDB の ACID 特性を利用する
 2. インデクスを全ての shard のインデクステーブル群に書き込む
 3. - &link(online essay,http://essay-for.me/) 

インデクステーブルを読む際, そのテーブルの中身が正確でないかもしれない (つまり step2 が終わっておらず古いプロパティの値を見えているかもしれない)のが 事前にわかっている. この制限のせいで無効な実体を返したりしないよう, 読みだす実体を絞るのにインデクステーブルを使いつつ, 実体自身に対しても問合せのフィルタを適用しなおす. インデクスの一貫性はあてにしない.

 1. 問合せに基き, 全てのインデクステーブルから実体 ID を取得する.
 2. その ID に紐づく実体を実体テーブルから取得する.
 3. (Python 上で) 全ての実体をフィルタし, 実際のプロパティの値が問合せの条件に一致しないものを除外する.  

インデクスが永遠に欠落したままだったり, 最終的には矛盾を解決するため, 前述の "Cleaner" プロセスを実体テーブルに対してずっと動かしておく. プロセスは欠落したインデクスを補い, 古い無効なインデクスを削除する. 落穂拾いは更新が一番新しい実体から行う. おかげで実運用でのインデクスの矛盾はいたって迅速に (1,2 秒以内に) 解消される.

性能

この新しいシステムでは主キーを重点的に最適化しており, 満足のいく結果が得られた. 以下のグラフは FriendFeed? ページの表示にかかる遅延を過去一ヶ月にわたり記録したものだ. (数日前に新しいバックエンドを投入したので, そこで激しく下がっている.)

日中のピーク数時間でもシステムの遅延が極めて安定したのは特筆すべきことだ. 過去 24 時間の FriendFeed? ページの遅延グラフは以下のとおり:

一週間前と比較してほしい:

今のところ, システムは本当に扱いやすいものになっている. このシステムをデプロイしてからインデクスの変更を既に数回行った. またシステム内の MySQL テーブルをこの新しい手法に乗り換え始めている. そうすれば構造をより自由に変更し, 前に進むことができるようになるだろう.