FriendFeedにおけるMySQLへの大規模データ格納

非RDBだのKey-Valueだのと騒がしい今日この頃ですが皆様いかがお過ごしでしょうか。私は元気です。先日、ベイエリアクラウド勉強会で教えてもらったHow FriendFeed uses MySQL to store schema-less data(FriendFeed流・スキーマレスデータのMySQLへの格納)を適当に翻訳してみますよ。(原文はCreative Commonsライセンス)

背景

FriendFeedではすべてのデータをMySQLに格納している。利用者の増加に伴い、FriendFeedのデータベースも拡大してきた。現時点では2億5000万件以上の記事が登録されており、これにコメントやお友達一覧のお気に入りなどのデータが加わる。

データベースの急成長に伴ない、規模に関する課題にも段階的に対処してきた。基本的な対処はおこなってきたつもりだ。具体的には、読み取り専用スレーブの設置やmemcache設置による読出し性能の向上および水平分割(sharding)による書き込み性能の向上だ。だが、FriendFeedの成長に伴ない、すでに存在するフィーチャを大規模対応させることよりも、新しいフィーチャの追加で頭を痛めることになってきた。

特に大変だったのは、1000万〜2000万件のデータを持つデータベースのスキーマ変更やインデックス追加であった。こういった作業は場合によっては数時間データベースをロックしてしまう。古くなったインデックスの削除も同様に時間がかかったし、古いインデックスを削除しなければシステムの性能を悪化させることにつながった。データベースエンジンはデータ挿入が発生する度に(本来不要な)インデックスのブロックを参照してしまい、メモリに常駐させたいブロックをメモリ外に追い出してしまう。この問題に対処する手段がないことはない。(新しいインデックスを読み出し用スレーブ上で作成し、インデックス作成が官僚したらマスターとスレーブを切り替える、など)　だが、こういう手順は面倒だし、作業を間違えるとややこしいことになる。 こういう理由で、技術者達はスキーマ変更やインデックス追加削除が伴うようなフィーチャ変更に対してなんとなく消極的になってしまった。データベースは激しく水平分割されていたので、JOINのような処理はもはや使い物にならなくなっていた。こういった背景があって、FriendFeedはRDB以外の領域に活路を見出そうと考えた。

スキーマ変更がひんぱんに発生するデータを格納したり、新しいインデックスを必要に応じて作成できるようなデータベースプロジェクトは数多く存在した。(例: CouchDB)　だが、どのプロジェクトも大規模サイトで安心して使えるレベルには到達していなかった。FriendFeed以外でのテスト報告や、我々自身がテストした結果からは、いずれのプロジェクトも安定度が足らないか、現場での揉まれ方が不足していた。(CouchDBに関するやや古い報告がこちらにある。) だが、MySQLはしっかりと動作する。MySQLのリプリケーションもちゃんと動く。MySQLの制約もわかっている。MySQLはデータ格納先としては好ましい。MySQLをRDBとして使うから問題が生じるのだ。

色々考えた結果、新しいデータ格納の仕組を使うよりは、既存のMySQLの上に「スキーマレス」のデータ格納機構を構築するべきと判断した。本資料では、その方式の概要について解説して行く。FriendFeedは他の大規模サイトが同様の問題にどう対処したか興味を持っている一方で、我々のやり方が他の開発者の参考になれば幸いだと思っている。

概要

FriendFeedのデータベースは、スキーマレスのプロパティバッグ(JSONオブジェクトやPythonのDictionary等)を格納する。格納される実体が唯一備える必要がある属性はidであり、ここには16バイトのUUIDが入る。それ以外の属性をデータベースが気に掛けることは一切ない。格納物のプロパティを増やせば、即「スキーマ」が変更されたことになる。

これらの格納物のインデックスは、個別のMySQLテーブルに納められる。格納物の属性3つにインデックスを張りたければ、インデックス用に3つのテーブルを持つことになる。ひとつのインデックスに対し、1テーブル、である。インデックスが不要になったら、そのインデックス用テーブルへの書き込みを止めれば良いし、さらにそのテーブルを削除しても良い。新しいインデックスが必要になったら、そのインデックス用のテーブルを作成し、そのテーブルにデータを格納する非同期処理のプロセスを走らせれば良い。こうすることで、本番環境の性能を落とさずに新しいインデックスを構築できる。

結果的には従来の方法よりも多くの数のテーブルを相手に擦る必要が出てくるが、インデックスの追加削除は簡単になる。FriendFeedでは新インデックス作成のために最適化されたプロセス(内部ではCleanerと呼ばれる)を開発しており、高速にインデックスを追加できるようになった。以前は週という時間単位で考えていた作業が、一日以内で終わるようになったのである。また、MySQLのマスターとスレーブを入れ替えるような恐ろしい手順ともおさらばできた。

詳細

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がプライマリーキー(PK)になっているが、これはInnoDBの物理データ格納順位がPK順であることを応用する技だ。PKをAUTO_INCREMENT指定することで、データは古い順に格納されることが保証される。こうすることで、新しいデータから順に表示されるFriendFeedの性能が改善される。データ本体はzlibで圧縮され、シリアライズされたPython Dictionaryである。

インデックスは個別のテーブルに格納される。まずインデックスを作成したい属性を全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;

前述のFriendFeed典型エンティティをデータベースに格納する部分を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クラスはindex_user_idテーブル群から、与えられたuser_idにひもづけられたidを取ってくる。データベースは水平分割(shard)されているので、shard_on引数を使ってどのshardを見に行くかを決定する。(entity["user_id"] % num_shardsで決まる)

indexインスタンスを使って、indexに対する検索が可能になる。上の例ではuser_id_index.get_all()。　datastore部分がindex_user_idテーブルとentitiesテーブルの「join」に相当する処理を行う。まずindex_user_idテーブルに対する問い合わせを行いID一覧を取得した後に、entitiesテーブルからIDでentity本体を引っ張ってくるのである。

新しいインデックスを追加するには、例えば上記例の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;

とテーブルを作成した上で、datastoreの初期化コードに新しいインデックスを含めるようにすれば良い:

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

一貫性と原子性

データベースが水平分割されており、あるデータのインデックスはそのデータが格納されたテーブルとは別のテーブル上に構築されることから、一貫性の確保が課題となる。データ本体が書かれてからインデックスが作成される間にシステムがクラッシュしたらどうなるだろうか？

FriendFeedの技術者達はトランザクション保証がされるようなプロトコルで処理することも考えた。だが、我々はこの部分を出来る限り簡素にしておこうと決断した。その為には一貫性確保が緩いものとなる。例えば

• 書き込み基準はデータエンティティ本体テーブルにあるものとする。
• 従って、データエンティティ本体にデータはあるが、インデックスには登録されていない、という事態も発生する。

データベースに新しいエンティティを登録するには次のような順番になる:

1. エンティティ本体テーブルにはInnoDBのACID属性を生かしたトランザクション処理で書き込み。
2. 全Shard上の全インデックス用テーブルに書き込み。

インデックステーブルから読み出す時には、その内容が必ずしも正しくないことを覚悟しておく必要がある。(上記Step2が正しく終わってなければ、インデックスは古い属性値を指しているかもしれない) 古いインデックス値を参照して間違ったエンティティを返さないように、以下のフィルタ手順を実施する。

1. インデックステーブルからentity_id一覧を取得
2. そのid一覧からエンティティ本体一覧を取得
3. そのエンティティ本体一覧から検索条件外のuser_idを持つものを削除

不正なインデックスが残らないように、前述の「cleaner」プロセスは常時データベースを巡回している。インデックスの抜けや古い値の参照を見つけたら、それらを修正するのである。cleanerプロセスは新しいデータから順次検査して行くため、エンティティ本体とインデックスとの不整合は比較的早い段階で検知される。通常は数秒以内で修正される。

• あとは性能に関する考察があるけど、略。
• この方式は「データ格納に水平分割したMySQL」「インデックスも水平分割したMySQL」
• データ格納については、Key-Valueも使えるのではないか？　MemcacheDBとか。

Python入門[2&3対応]

実践ハイパフォーマンスMySQL 第2版