Redisを使ったID生成は本当にReliableなのか？　LINEアプリにおけるID生成の問題と解決法

メッセージングアプリのシステム図

井出真広氏：こんにちは。LINE Platform Development Center1のチームで、メッセージング機能の開発、ストレージの運用を行っている井出と言います。本日は、LINEアプリにおいて、ID生成をどのように行っているのかを紹介します。

はじめに、この発表の対象となる我々のLINEアプリについて、簡単に紹介します。我々のLINEアプリは、現在約2億人のアクティブユーザーがいて、1日にこれらのユーザー間で、40億ほどのメッセージが送られています。実際にどのようなメッセージがどのように送られているのかは、想像しにくいと思うので、LINEのシステムの簡単な図を書いてみました。

LINEのアプリは、非常にオーソドックスなクライアントサーバーモデルとなっていて、ユーザーがメッセージを送る際には、いったんバックエンドのサーバーにメッセージが送られ、そのメッセージを、バックエンドがデリバリーするかたちになっています。

メッセージを受信したクライアントは、バックエンドを経由して、「自分がこのメッセージを送ったよ」という通知を送信元に返します。1日に40億メッセージなので、だいたい秒間4万から5万メッセージほどが、このやりとりを行っていることになります。

さてこのメッセージですが、お互いを認識するために、Message IDというIDが振られています。このIDをどのようなフォーマットにするのか、どのように割り当てるのかはさまざまな方法があると思いますが、我々はグローバルにユニークで、かつモノトニックに増加するようなIDを採用しています。そしてこのIDですが、バックエンドのサーバーですべて採番する方式をとっています。

どのようなタイミングでIDが生成されるかというと、メッセージが送信者から送られるとバックエンドのほうでIDを割り当て、送信者・受信者それぞれに対して配信するかたちになっています。

このIDをどのように生成するかですが、生成器にはメッセージングのボトルネックになってはいけないので、十分に速いこと、そして（スライドの）右に書いてあるCのコードくらいに単純であること、そしてメンテナンスコストが低いことが要求としてあげられます。

我々はこの要求を満たすため、そしてすでに多くのRedis Clusterを我々がマネージしていたこともあり、ID生成をRedisを使って実装することにしました。

Redisを使ってID生成をしようとすると、1つのRedisマスター、レプリカのペアを使ったセットアップが一番単純で、かつID生成が速くできるかと思います。実際、我々のバックエンドで必要としていたパフォーマンスを、十分に発揮してくれました。

このセットアップは本当にReliableなのか？

しかし、数年運用しているうちにあることに気づきます。このセットアップは、本当にReliableでしょうか？　なにかトラブルがあった時にAvailableなのか、そして、Scalableなのかという問題が出てきました。実際にこの疑問が本当に問題となりうるのか、試行実験をしてみましょう。

1つ目のケースは、突然Redisホストが死んでしまうケースです。この問題は、我々がすでに数千台もRedisのインスタンスを運用している観点からすると、日常的に起こっている問題です。

仮にマスターだけが死んだ場合には、レプリカへフォールバックすることが1番シンプルな解決方法かもしれません。しかし、ここで気をつけなければいけないのは、Redisが非同期的にレプリケーションを行っている点です。

もし、レプリケーションが完了する前にRedisが死んだ場合には、誰も最後に生成したIDを知りません。また、マスターとレプリカが同時に死んだ場合はどうでしょうか。この場合も同じで、また、どうやって復旧すればいいのかもわかりません。

もし復旧の際に誤って生成済みのIDから採番を再開すれば、IDの重複が発生し、さらに復旧完了まで時間がかかってしまうでしょう。復旧中はユーザーは会話ができないので、サーバーの運用する立場としては絶対に回避する必要がある問題です。

2つ目のケースは、複数のネットワークにまたがってサービスを行っている我々のアプリでは、たびたび発生する問題です。マスター、レプリカとバックエンドのネットワーク間が分断されてしまうと、ID生成が行えず、最終的にメッセージの送信ができなくなってしまいます。

解決方法は、ネットワークのパーティションが解決するまでを待つ方法ですが、このパーティションは、1秒で解決される問題なのか、10分で解決されるのか、はたまた1日かかるのか、それはわかりません。解決されるまでユーザーの会話をブロックしてしまうことになるので、これも発生させたくない問題の1つです。

実験・調査を経て、行き着いたSnowflake

ではどのように解決していけばいいでしょうか。一度、要求を整理してみましょう。

まず、「グローバルにユニークで、モノトニックに増加するIDである」という要求があります。これはメッセージングの既読の機能だったり、順番を並べるためにこのIDが使われていたり、バックエンドのストレージの最適化だったり、いろいろな機能が依存しているため、今から変えることは現実的ではありません。

また、ネットワークのパーティションやハードウェア障害に耐性を持つためには、ID生成器がScalableな必要があります。また、メッセージングのIDは、APIやストレージのスキーマなどですでに使われているので、ブレイキングチェンジなしに変更を加える必要があります。

このブレイキングチェンジについて考えなければ、UUIDとかGUIDとか、別の方式も考えられるわけです。64bit integerでグローバルにユニーク、かつモノトニックに増加するIDの生成をScalableに実現する方法はないか、いろいろと実験・調査を繰り返すと、TwitterがツイートのIDとして採用した、SnowflakeというIDフォーマットに行き着きます。

このSnowflakeというIDフォーマットは、3つの要素から構成されています。1つ目、Timestampは、1ミリセカンドごとに更新されるフィールドです。このフィールドによって、モノトニックにIDが増加するという性質を提供します。

（2つ目の）WorkerIdでは、どのマシンがIDを生成したのか。そして（3つ目の）Sequenceでは、同じタイムスタンプ、同じWorkerIdで生成されたID同士でユニークになるように利用されています。

このSnowflakeを我々のシステムにそのまま適用することも考えましたが、少しフォーマットを変更して利用することにしました。そして我々はこのID、ID生成器をMIG（Message ID Generator）と名付け、システムに適用することにしました。

MIGのIDフォーマットとSnowflakeの違い

MIGのIDフォーマットは、Snowflakeのものと2点だけ違っています。1つはTimestampのresolutionが、1ミリセカンドから10ミリセカンドに変更している点です。つまり、Timestampの部分が10ミリセカンドに1回しか変更されなくなったわけです。

もともと69年ぐらいしか使えなかったTimestampのフィールドですが、resolutionを落とすことにより、200年ほど利用できるようになりました。

そして、Sequenceの部分が12bitから18bitに増えています。これは、1つのWorkerが10ミリセカンドの間に生成できるIDを増やすことによって、突然のメッセージ増加に対応できるようにしたものです。

「このような形式のID、ID生成器がこのような振る舞いをしますよ」と言われても、頭の中で想像することは難しいかもしれないので、実際の動きについて次のスライドで紹介します。

先ほどまでの1つのRedisマスター、レプリカを使ったセットアップとは異なり、MIGでは複数のMIGを並べてロードバランスできるようになりました。

各MIGではIDの生成リクエストが来る度に、その時点でのTimestamp、自分のWokerId、そしてSequenceを組み合わせることで1つのIDを作り、バックエンドに返せるようになりました。

それぞれのIDは、生成された時刻が異なれば、異なるTimestampを生成する特性から、ID同士を並べた時に、すべてのホスト間で必ずモノトニックに増加する保証ができるようになりました。

そして仮にいくつかのホストが死んでも、引き続きほかのインスタンスがそのID生成を肩代わりすることになったので、ステートをホスト間で共有することもなく、簡単にホスト追加できるようになったわけです。

そして、1つのデータセンターだけにあったID生成器は、気軽に複数のデータセンターにも配置できるようになりました。これにより、先ほど挙げていたScalabilityやAvailabilityに関する問題が解決されました。すごくハッピーですよね。

このように、MIGを適用すればすべてが解決すると思っていましたが、実はそう単純ではありませんでした。MIGを導入することによって、クライアント・バックエンド間でIDの重複や、IDが必ずモノトニックに増加するという仮定が壊れてしまうような現象が発生したのです。今日は、テスト中に発見された事例について2つ紹介したいと思います。

テスト中に発生した問題の2つの事例

1つ目の問題は、モノトニックにIDが増加しなくなってしまう問題です。

実はTimestampベースのIDでは、うるう秒やNTP（Network Time Protocol）による時刻調整が入ると、IDの単調増加ができなくなる問題があります。例えば複数生成されたIDの中で、2つ目と3つ目のIDが取得される間にクロックのドリフトが発生して、時刻が5秒戻ってしまったとします。このケースでは、クロックドリフトの結果、確かにIDがモノトニックに増加できなくなったことが確認できます。

では、どのように修正すればこの問題解決できるでしょうか。このケースでは、NTPサーバーでよく知られている方法で解決できます。

この問題は、クロックドリフトが発生した際に（スライドの）グレーの線で書かれている実際のTimestampを、青い線で書かれているMIGのIDのTimestampがいきなり追従することで、修正されたTimestampに変更されてしまう問題になっています。

そのため、NTPサーバーで使われているSlewモードなどの、オレンジの線で書かれているように、徐々にTimestampを正しいTimestampに修正する方法をとりました。

これを使えば問題が発生することも、モノトニックに増加するルールを破ることなく、Timestampの修正ができるようになりました。

次の問題は、我々のバックエンドストレージで起きた問題です。我々は、Apache HBaseやほかのストレージ以外に、複数のRedis Clusterをストレージとして利用しています。そして、複数のRedisコマンドをまとめてアトミックに、そしてコマンドを処理するために必要なRound Trip Timeを削減するために、RedisのLuaスクリプトを使って実際のストレージの運用をしています。

RedisにおけるLuaスクリプトの機能がどんな機能かと言うと、例えば複数のgetコマンドを1つのLuaスクリプトで書くと、1つのRedisコマンドとして実行されるといった具合です。

このサンプルでは、ユーザーIDのラストメッセージIDをgetし、そのIDを使って実際にRedis上に保存されているメッセージオブジェクトを取得するようなスクリプトを書いています。このコマンドをLuaスクリプトを書いて、1つのevalのコマンドで実現すると、スライドのような感じになります。

このLuaスクリプト、一見すると、うまく動いているように見えますが、実際に動かしてみるとなにかがおかしいです。

上の2つのgetでは、実際にメッセージオブジェクトが返ってきましたが、実際のLuaスクリプトでは何も返ってきません。つまり、メッセージが見つからないという結果が得られました。

このサンプルではメッセージのロストが発生しましたが、実際に起きた現象としては、IDに関するデータがランダムにロストしたり、IDに紐づいたデータが重複してしまうといった問題があったり、調査にはかなりの時間がとられました。

いろいろと原因を調べていくうちに、Luaスクリプトの内部で、例えばtonumber()のように文字列から数字にデータを変換すると、まったく違う結果が得られることがわかってきました。

そうです。特にRedisに組み込まれているLuaのバージョンでは、Integerや浮動小数点数、あるいはすべてが浮動小数点数を使って表現されているため、MIGで生成されたIDを正しく表現できないのです。

Lua 5.3のバージョンからは整数型も導入されているので、これは解決できていますが、バージョン間の互換性がないので、Redis serverではまだ古いバージョンが使われています。

この解決方法の詳細は時間に収まらないので話せませんが、なかなかに大変なものでした。

今回紹介したスクリプトは非常に単純なもので、手書きでもなんとかなる問題でしたが、実際にはBigintをLuaスクリプト上で実装してみたり、数値に変換せずに直接値を比較する方法を試したり、ケースバイケースでLuaの世界でデータ変換が回避できるような試みを行い、実際の問題解決としました。

まだまだ興味深い問題はありますが、時間なので私の話は以上となります。

新機能の導入時には、内部実装の確認も大切

LINEでは、ライフライン・プラットフォームとしての信頼性を高めるために、サービス開始初期から10年間、分散システムの技術に力を入れてきました。これからの先の10年間は、さらにその分散システムを、データセンターレベルの制限を超えて拡張する上で必要な、信頼性の開発やエンジニアリングを取り組んできています。

このセッションではその1つとして、ID生成をどのように実装しているのか紹介をしました。TimestampベースのIDに転換することで、速くてマルチデータセンターレベルで、ScalableなID生成を手に入れられました。

また、マイグレーションをする際に発見したバグについても紹介しました。今回は、クロックドリフトや浮動小数点数の表現などを話しましたが、みなさんも自分のサービスに新しい機能を導入する時には、クライアント、サーバーだけではなく、それぞれの実装について、どのような内部実装になっているのか注意深く確認することで、実装する時には気づかなかった問題も気づけるかもしれません。

以上で発表を終わりにします。ありがとうございました。