負荷を均すための『時間軸シャーディング』という考え方

ウェブアプリケーションを作っていると、負荷を分散させるために「タイミングをばらけさせる」場面に時々遭遇します。 データの更新、キャッシュのフラッシュ、バッチ処理など様々な問題で、同じ構造が見られます。

例えば、スマホアプリからバックグラウンドで1時間ごとに何らかの情報をサーバーに送りたいとします。 愚直に毎時0分に更新処理を行うようにすると、すべてのユーザーから同じタイミングでリクエストが来てしまいます。 ですから、リクエストのタイミングをユーザーごとにばらして負荷を均す必要があります。

他のケースを考えます。 5分ごとにジョブを投入して何らかの更新を行うタスクがあるとします。 本来ならデータベースに更新を行いたいのですが、データベースのハードウェアの限界が近いので、更新データをまずキャッシュに乗せるようにしました。 何らかのタイミングでキャッシュからデータベースにフラッシュする必要があります。 データベースに書き込むタイミングをジョブによってばらして負荷を均したいという要求が出るのは自然なことです。

負荷を均すときに考える基本的なことは、何が時間軸上でばらけるかということです。 例えばインストール時刻がばらけるならば、インストール時刻から1時間ごとに更新するという処理でユーザーごとにばらけるでしょう。 そんな都合のいいタイミングがない場合や、ストレージに情報を持てない場合には、id番号のようにすでにばらけているものから処理する時刻を決めるのが有効です。 例えば5分毎のジョブ投入のケースの場合、id番号のmod 12を取った値が分を5で割った値と同じになったタイミングで処理を行うようにすると、重い処理を1時間に一回にしてかつ負荷を分割することができます。

func shouldUpdate(job: Job) bool {
    return (job.ID % 12) == (time.Now().Minute() / 5)
}

idが文字列の場合は文字コードの和をとる、SHA-1を取って文字コード和をとる、CRCをとるなど、とにかくmodでばらけるような数字を作れたら成功です。

本来なら毎回行う更新処理を数回に一回にしてばらけさせる、あるいはリクエストの集中を避けるためにタイミングをばらけさせる。 このように、負荷を分割して均す目的で時間軸上でばらけさせる処理は、時間軸方向のシャーディングと言うことができます。

一般にシャーディングというと、データベースやストリームをスケールアウトさせて負荷を分散させる、空間軸方向のシャーディングを指します。 一つのデータベースに集中させていたものを、ハードウェアの限界などのためにデータベースを分割して負荷を軽減させるのがよくあるケースです。 何らかのハッシュ関数のmodからノードを決定してデータを書き込む。 ハッシュ値のmodが均等に分散すれば、各ノードの負荷は1/(ノード数)に軽減されます。

更新リクエストを時間軸上で分散させるときも、idから計算したハッシュ値のmod (単純なケースではidのmod) を取ります。 1時間を5分毎に分割するときは、ノード数が12ですからmod 12を取ってノードを決定します。 15ノードに分けても30ノードに分けても構いません。 一日一回の更新タスクを24分割するならmod 24を取って時刻と比較するとか、96分割してその日の経過した分を15で割った数字と比較するなど、分割方法はいくらでもあります。 ノードの分割方法は、タスクの投入の仕方、どれくらいの失敗が許容されるか、短い期間で同じ処理を行なっても大丈夫かなど、問題の性質によって変わってきます。 いずれにしても、idや名前などの固定値からハッシュ値を作ることが大切です。

もっと古典的なユースケースとして、重いバッチ処理をmodで分割するのも、時間軸のシャーディングと言えます。 偶数番号と奇数番号でバッチを分割するというのは最も単純なシャーディングです。

これまで「タイミングをばらけさせる」と言っていたものを「時間軸のシャーディング」という言葉で表現することで、空間軸のシャーディングの用語を類推して用いることができます。 例えば「シャードが偏る」という言葉がありますが、時間軸シャーディングの場合で偏る場合はだいたいハッシュ関数か元の値の選び方が悪いでしょう。 「シャードを分割する」場合は、特定の一つのシャードを分割するよりも、10分毎のノードを5分毎に分割するという風に時間軸上のノード数を増やすのが有効だと思います。 空間軸シャーディングとは違って、時間軸シャーディングの場合はデータ移行を考えなくて良いので、ハッシュ関数やノードの分割方法を変えて「リシャーディング」を行うことでうまくいく場合が多いと思います。

上記で書いた内容は、特に新しいことはやっていませんし、タイミングをいい具合にばらけさせるコードを書いたことがある人はたくさんいると思います。 そういう処理を時間軸のシャーディングと捉えることで、言葉を類推して用いることができるようになり、空間軸シャーディングと対比して利点と欠点を比較し、より良い方を選ぶことができるようになると思います。

「更新が多くてハードウェアの限界に来てますが、仕様としてもう少し更新回数減らしてよさそうですね。ただ、タイミングがばらばらになるとよさそう」のようなあやふやな言葉で伝えていたものを、「時間軸シャーディングするとよさそうですね。1時間を12ノードに分けましょう。1時間に一回の更新で仕様上は問題はありません。空間軸シャーディングはこれでだめになった時にまた考えましょう」のようにはっきりと伝えられるとかっこいいですね。

追記: ジョブキュー使いましょうというのは真っ当なご意見ですし、負荷のパターンと工数によってジョブキューを作るべき場面もあるでしょう。もともと時間軸シャーディングを考えたのは負荷が一定でスパイクのない系で工数をかけずにタイミングをバラすというものだったので、負荷を均す一つの解法にすぎないことは把握しております。