シンプルで移行しやすいデータベースシャーディング

技術部の小野(taiki45)です。クックパッドではこれまで様々なデータベースの負荷対策を行ってきましたが、シャーディングは行われていませんでした。しかし先日クックパッドの認可サーバーが利用している MySQL サーバーの負荷分散のためにクックパッドで初めてのシャーディングを行ったので、Rails アプリケーションでのシャーディングの事例のひとつとしてその際の手法をご紹介したいとおもいます。


構成

Before

データベースは1マスター、1ホットスタンバイ、バッチ用の1リードレプリカで構成されています。Read オペレーションのほとんどはキャッシュ層に逃しています。

f:id:aladhi:20150622102704p:plain

After

データベースの各ロールにつきそれぞれ1台ずつマシンが増えています。

f:id:aladhi:20150622102711p:plain

シャーディングが必要になった背景

認可サーバーのアクセストークンの作成・削除時の Write オペレーションが急増し、レコード数自体も急増していて、データベースサーバーサーバーの IO 性能が限界に近くなったので Write オペレーションの負荷分散をする必要がありました。

負荷の増加の仕方が急だったので、素早く負荷分散をする必要がありました。そのため、変更が少なく検証量が少なくすむシャーディングを選択することにしました。

考慮したこと

変更を少なくする

検証やテストの量を減らし素早く移行するために、なるべく既存の構成を変えないこととアプリケーションの変更が少ないことを目指しました。

シンプルに保つ

対象アプリケーションは開発が活発で、単純なクエリが多いという特徴があったため、メンテナンス性をなるべく維持できるシンプルなシャーディングの導入が適切だと考えました。

オンラインで移行できる

対象が認可サーバーなのでダウンタイムがあると広範囲のサービスに影響します。なので、オンラインで移行できることを優先度を高く設定しました。また、レコード数が増加し続ける可能性が高く、物理ノードの追加がある程度頻繁に行われることを想定していたので、ノード追加時もダウンタイムが発生しない方法を検討しました。

ロールバックできる

クックパッドのサービスの性質上リードが大半を占めていてキャッシュ層を追加することで解決したり、また適材適所のデータベース選択によって今まではシャーディングの必要がありませんでした。今回は初めて行うシャーディングだったので未知数なことが多く、移行自体もロールバックできる方法を検討しました。

シャーディング手法

分散モデル

キー分散モデルを採用します。具体的には、値域が正の整数であるようなハッシュ関数を利用して hash(v) mod N の結果でノードを決定します。単純に N = ノードの数 とした場合、ノード追加時に計算結果が大きく変わってしまい大規模なデータの移動が必要となるので、仮想ノードとしてハッシュスロットを導入します。ハッシュスロットの総数が変わってしまうと大規模なデータ移動が必要となるので、ハッシュスロットの総数は十分大きい数に設定します。ノード追加時は旧ノードから新ノードへとハッシュスロットの割り当ての一部を移すことで必要なデータ移動を最小限にします。

ハッシュ関数はパフォーマンスが良くて(今回のようなデータで良くバラけて生成コストが低い)、標準ライブラリに入ってる CRC32 を利用しました。

ノード管理

ノード数を2の冪に固定することでレプリケーションを利用してデータ移動を事前に準備しておくことができます。(101) -> (101,201) という1ノードから2ノードの移行時には 101のデータを201にレプリケーションしておくことで移行期のデータの移動が不要になります。(101,201) -> (101,201,301,401) という2ノードから4ノードへの移行時には101のデータを301に、201のデータを401にレプリケーションしておきます。

f:id:aladhi:20150622104653p:plain

非一貫性とロールバック可能性

この2つの問題を解決するために、マルチマスターレプリケーションを利用します。

データの非一貫性の問題とは、物理ノードを追加してハッシュスロットの割り当て設定を更新する際に発生する問題です。 ハッシュスロットの割り当て設定をすべてのアプリケーションサーバーで同時に更新することは難しく、あるアプリケーションサーバー A では設定が更新され、別のアプリケーションサーバー B では更新されていない状況が発生します。 このとき、A が新規に追加された物理ノードでデータを変更しても、B ではその物理サーバーをまだ参照していないので、A から行われたデータ変更の一部が B からは見えません。事前にマルチマスターレプリケーションを動作させておくことで、レプリケーション遅延によるデータの非一貫性は依然として存在しますが、この問題をある程度軽減できます。

f:id:aladhi:20150622130232p:plain

物理ノードを追加した段階でも マルチマスターレプリケーションをしている間は旧ノードにも新ノードに入るデータが同期されるので、問題発生時などにロールバックできます。

Rails way に乗っている場合は auto increment な id カラムがあると思うのですが、ALTER TABLE できないほど巨大なテーブルに育ってしまった場合は id カラムを残したままシャーディングを実施する必要があります。その場合は、マルチマスターレプリケーション時に id が衝突してしまいますので、衝突しないように auto_increment_increment, auto_increment_offset を事前に変更します。

移行オペレーション

  1. レプリケーションを利用して、元のノード(101)の完全コピーとなる新ノード(201)を作成します。
  2. 新旧ノードで id がぶつからないように auto_increment_increment, auto_increment_offset を設定します。その上で、マルチマスターレプリケーションを開始します。
    • note: MySQL のバージョンによっては auto_increment_increment の設定が異なるコネクションが並行に INSERT を行うと duplicate key エラーになることがありました。対策として、プライマリーキーの duplicate key エラーが発生すると AR のコネクションをリセットしてリトライすることをしました。似たような現象のバグが報告されていました
  3. アプリケーション側でシャーディングを有効にし、新ノード(201)にもクエリーするようにします。
  4. 様子を見て 101, 201 のマルチマスターレプリケーションを解除します。

f:id:aladhi:20150622105447p:plain

実装

上述のような仕組みをサポートする gem は見つからなかったので、新しく実装することにしました。ActiveRecord の接続周りで各シャードを参照するような機能は octopus にあったのですが、今回はハッシュスロットの管理や各シャードへのルーティングが必要な機能で、コードベースが大きい octopus を利用するメリットが少ないと判断しました。なので、新しく mixed_gauge という gem を作りました。やってることに見合うようにコードベースを小さく保ち、ActiveRecord の変更に追従しやすいようモンキーパッチを極力しない方針で作成しました。

結果

特に問題なく移行し運用できています。

今回のシャーディング手法は求めていたものにハマりうまくいきましたが、逆にどういう時には導入すべきではないかも簡単にですが書いておこうと思います。

今回は MySQL を利用したシンプルなものなので、Expiration やキャッシュ層が必要な場合は自前で用意する必要があります。導入に時間的余裕があり、それらの仕組みをあわせて構築する必要がある場合は、最初からそういった機構を備えている分散データベースを利用するほうが良いかもしれません。

複雑な関連があるアプリケーションは今回のようなシャーディング手法をそのまま適用するのが難しいと思います。その場合は他のシャーディング手法を採用したり、データを再設計し分散データベースを利用してしまうのが良いと思います。

まとめ

今回はシンプルで移行がしやすいデータベースシャーディングの手法についてご紹介しました。

キー分散モデルとハッシュスロットを採用し、レプリケーションを活用できるノード管理の規約を導入しました。このような手法をサポートする mixed_gauge という gem を作成しました。

この記事がご参考になりましたら幸いです。