最高のサービスを提供するには内部を理解する必要がある　LINEアプリの大規模トラフィックを支えるストレージのしくみ

テスト環境を使った最近の事例

ルカデテナハビエルアキラ氏：それでは、このテスト環境を使った最近の事例を紹介します。パフォーマンスのスパイクを減らして、クラスタの信頼性の改善を試みました。スパイクの原因としては、ディスクは時々パフォーマンスが急上昇することがあります。メモリアクセスに比べてディスクアクセスは予測することが難しいです。またはネットワークが不安定になって、遅延が増えるということが挙げられます。

この問題は、Hedged Readsという機能で低減できます。では、Hedged Readsとは何でしょうか？　HBaseがデータノードを活用してデータを読み込みますが、データノードはディスクからデータを読み込もうとすると、多くのことが起こります。ネットワークが遅くなってしまうかもしれないし、ハードの問題でまたオペレーションが重くなり、IOが増加してディスクが遅くなるということもあります。

Hedged Readsを使うと、HBaseリージョンサーバーは、同じデータを他のデータノードからリクエストしようと試みます。これは実現可能です。各データブロックは、複数のデータノードに複製されているからです。

ではこれをどうやってテストするのでしょうか？　通常の状態ではフレーク上の問題や遅延の問題などはないので、このシナリオをシミュレーションで作る必要があります。そのため、LD_PRELOADという機能を使いました。これはUnixダイナミックリンカーに対して、ほかのライブラリよりも先に自分のコードをロードするように指令します。

この小さなC言語のコードを作り、実際のリードディスクの前に小さなスリープを発生させます。これで、フレーク上のディスクレプリケートすることができ、レスポンスタイムが1～3秒くらい遅くできました。遅いリスクを再現したあと、Hedged Readsをオンにすると、レスポンスタイムのスパイクがなくなりました。

テストは成功したものの……

このように、Hedged Readsのテストが成功しました。これは有用のようです。しかし何日か使うと、HBase リクエストを処理するスレッドが増加し、減る様子がなく、クラスタでそれ以上のリクエストが処理できなくなり、どうしたのかと思いました。

そこでスレッドダンプを見ますと、HBaseがなんらかのロックを取得して、Hedged Readsの部分がブロッキングキューからなにかを取ろうとしているところで、スタッキングしているようでした。コードを読み、デバッグすると、次のことがわかりました。

HBaseはReadロックを取得し、ReadのデータノードからReadするタスクをサブミットしましたが、データノードが故障した、またはハードウェアに問題などがあり、結果がデータノードから戻ってこなかったのです。Readの結果を待つブロッキングキューは、来ない結果を待ってブロックされていたので、HBaseでのReadロックは開放されませんでした。Readがスタックしているからです。その後、新しいReadリクエストを送っても、Readロックのリリースを待ち、スタックしました。

この調査のあと、我々はHadoopのオープンソースのコミュニティが、すでにReadロックの問題を解決済みであるとわかり、内部のHadoop LINEブランチにバックポートすると、このエラーは発生しなくなりました。

我々は、このロッキングの問題をHBaseのオープンソースコミュニティに報告し、その過程で、そのほかのHedged Readsのメトリクスも修正。テスト環境でリクエストを再現するテクニックを使って、機能とバージョンを評価し、このクラスタを非常に堅牢にしました。実際に、オープンソースコミュニティにも複数回コントリビュートしました。

パフォーマンスの問題

これで、我々のクラスタは非常に堅牢で信頼性が高いものになりました。でも準備万端でしょうか？　いいえ。クラスタは信頼性が高いかもしれません。速いかもしれません。でも、まだパフォーマンスが悪くなる可能性があります。どのテクノロジーでもそうですが、使い方次第でパフォーマンスを出すことができます。HBaseも例外ではありません。

テーブルスキーマデザイン、またデータのモデリングは、データのアクセス方次第で重要な役割を果たします。優れたデータスキーマをデザインするには、HBaseの内部的な仕組みを理解する必要があります。では、優れたテーブルスキーマデザインのお話をしますが、その前にHBaseの内部的な仕組みを見てみましょう。

まず、HBaseのデータのまとめ方を見てみましょう。データはまずローと行になっていて。ローにはキーがあります。キーにはキーバリューストアのように値、バリューがあります。ローキーは、複数のカラムと列をもち、それはカラムファミリーにグループ化されていて、カラムは複数のバリューをもつことができます。

重要なのは、データはセルに格納されていて、セルはバージョンが付けられてイミュータブル、変えられないということです。ですから、値を更新するために、実際は新しいバリューとバージョンの付いたセルを追加しているのです。そしてほとんどの場合、最新のバージョンを読み込むので、バリューを更新したという印象を受けるのです。

HBaseにバリューを書き込むとき、直接ディスクに書き込まず、まずインメモリストアのMemStoreに書き込み、そして時々メモリの内容をディスクにフラッシュします。Hadoop Distribution Systemの中にあるイミュータブルなファイルシステムのHFileに書き込みます。

HFileは、変更不可のイミュータブルなので、MemStoreを何回もフラッシュすると、複数のHFileができます。HBaseは、バックグラウンドでこれを圧縮して数を減らします。

セルは、MemStoreとHFileの両方の中でローキーになっていて、カラムとバージョンでソートされたあとで、簡単にデータの場所が特定できるようにしています。これはとても重要なのでぜひ覚えておいてください。というのは、これらが残りのセッションの内容を理解するためにも重要だからです。

想像がつくと思いますが、HBaseからデータを読み込む際は、MemStoreとHFileの両方から読み込み、結果をマージする必要があります。

問題のケーススタディ

ではHBaseが内部的にどう動くか少し理解したところで、ケーススタディを見てみましょう。メッセージIDのリストを格納するテーブルがあり、トーク前になっています。このテーブルを使って、未読メッセージの量を計算したり、既読メッセージをマーキングします。

例えば、ユーザーAにはメッセージID7と11がトークに未読であり、最新のメッセージは11です。ユーザーAがトークを開き、メッセージ7から11へと読んでいきます。そのあとで、こちらで未読メッセージの数をアップデートし、ユーザーBのためにメッセージを「既読」とマーキングします。

そのためには、LINEのメッセージアプリのmessageIdsが数値でグローバルにインクリメントされることを考慮して、messageIdsを範囲ごとにスキャンする必要があります。

我々の最初のアプローチは、トーク前のメッセージIDリストを1つのローに格納することでした。我々は、チャット参加者の両方のユーザーのIDを使ってローキーを構築し、トークを特定しようとしました。

ユーザーIDは数字なので、低い数字の値のほうを使い、それをハッシュしました。それで、クラスタの異なるノードにローを分散させました。そして、メッセージIDをカラム名をバージョンとして付けました。こうすることにより、レンジスキャンによるスキャンを、バージョンに対して容易にかけられます。例えば、バージョン123からバージョン245までをスキャンする、というように使えます。カラムをレンジスキャンに使わなかったのは、ユーザーはほとんどの場合、最新のデータのみを読むので、MemStoreのみ、または最新のHFileを読むだけでスキャンは十分だからです。

バージョンに対してレンジスキャンをすることで、古いHFileを読むことを回避し、IOを節約し、ブロックキャッシュをよりよく使えるようにしました。また、どのユーザーIDがメッセージ送信者なのかも、セルのバリューとして格納しました。

このテーブルスキーマを本番にデプロイしたあと、深刻なパフォーマンスのスパイクが見られました。これは、ユーザーエクスペリエンスに悪影響を与えかねるので修正が必要です。ただ、1つヒントがありました。HBaseがMemStoreをディスクにフラッシュしたあとは、パフォーマンスのスパイクは消えてしまったのです。

MemStoreの内部的な仕組み

なので、問題はおそらくMemStoreにあるだろうということになりました。状況を理解するために、MemStoreの内部的な仕組みを見てみましょう。MemStoreはインメモリのソートされたストアなので、シンプルなSortedLinkedListとして実装できます。

でもそれでは効率がよくありません。なぜかと言うと、ほしいエレメントが見つかるまでリストを順番に移動していく必要があるからです。それは時間計算量Nです。それでHBaseはMemStoreをスキップリストに入れています。

スキップリストは、リンクリストをもともとのソートされたリンクリストの上に作ります。この新しいリンクリストは、追い越しレーンのようなものです。素早くデータの場所を計算量Log N時間で特定でき、ずっと拡張性が高くなるのす。こうすることで、MemStoreにローキー、カラム、バージョンでソートされているセルを格納できます。

では、メッセージIDリストテーブルに戻りましょう。これはMemStoreのスキップリストで、データはローキー、カラム、バージョンでソートされています。各メッセージIDに対しカラムがあり、メッセージIDがバージョンとして格納されています。

我々はユーザー333とユーザー555の間のメッセージIDリストをスキャンしたいので、まず最初にトークのローキーの場所を特定しました。MemStoreの中でローの始まりを探します。これはスキップリストなので、計算量時間はLog Nです。

ローの場所を特定したら、最初のカラムとバージョンをチェックします。でも、求めるバージョンはありませんでした。探しているのは、バージョン1000から1010の間です。するとMemStoreは、じゃあ次のカラムを探せばあるのではないか？　と言ってきます。

我々は、このMemStoreが、スキップリストの次のエレメントだけを見ていくと思いました。しかし実際は、毎回スキップリスト全体を横断的に見ていたのです。その計算量時間はLog N。これはHBaseが使っている実装がJava ConcurrentSkipListMapだからです。

実装の詳細には踏み込みませんが、これはtailMapというメソッドをコールし、内部にイミュータブルなサブリストを作るのです。それを反復処理するには、もともとのスキップリストを横断的に見ていく必要があるのです。

MemStoreの中の各セルから、求めているバージョンである1000から1010が入っているカラムを探します。何回も次のカラムを探していきます。そして、MemStoreが次のカラムを探せと言ってくるたびに、計算量時間がLog N発生してしまいます。

想像してみてください。こうなると、たくさんのカラムをフィルターしていく必要があります。例えばM個のカラムをフィルターアウトする。何千個よりももっと多い数をフィルターアウトします。結局M * Log Nがかかるので、あのような遅いパフォーマンスだったわけです。

MemStoreの挙動を修正しようとしましたが、いろいろなトレードオフを考えると、そのフィックスはマージされませんでした。しかし、パッチはありますので、よかったらチェックしてみてください。

MemStoreからディスクにフラッシュされるとスパイクが消えるのはなぜ？

前に言ったように、データがMemStoreからディスクにフラッシュされると、スパイクは消えました。なぜ？　と思う人もいるかもしれません。理由を見てみましょう。私たちがHFileからデータを読み込むとき、データブロックをまずロードしますが、HBaseは、内部的にByteBufferを使います。

求めているカラムを探すとき、HBaseはByteBufferの最初から始めます。求めるデータが見つかるまで、シークエンシャルにByteBufferを横断的にトラバースしていきます。この計算量時間はNで、そんなによくはありませんが、MemStoreのM * N Logよりマシです。

メッセージIDリストスキーマに戻りますが、メッセージIDをバージョンとしてもつのはベストな考えではないため、私たちはメッセージIDをローキーに移動させました。それで、1つのローキーに全部のIDリストが入っている代わりに、メッセージIDリストを複数のローに分散させました。

私たちは、レンジクエリをバージョンに対してではなく、ローに対してかけたのです。これで、MemStoreは求めているメッセージIDが入っているローを直接探せます。それにより、私たちは1回だけ探すので、計算量時間はLog Nだけになり問題解決です。

最高のサービスを提供するには内部を理解する必要がある

ではまとめに入ります。まず要件の話をしました。ストレージの要件です。そしてできる最高のサービスを提供し、不要なコストを回避することがいかに重要かお話しました。私たちのストレージはパフォーマンスもよく、信頼性に優れ、可用性と拡張性が高い必要があり、データの一貫性を担保する必要があります。

これらの要件は、HBaseをプライマリーストレージにすることで満たしても、クラスタの信頼性も必要で、またパフォーマンスも重要です。それは、すべてのバージョンやフィーチャーを、本番環境と条件やトラフィックが近い、安全なテスト環境で注意深くテストすることで、実現しています。

またHBaseのパフォーマンスのためには、よいデータスキーマが重要であり、そのためには内部を理解する必要があります。このことは、HBaseやHadoopだけではなく、どんなテクノロジーでもそうだと思います。

今後の課題

最後に少し、今後の課題についてお話いたします。まずキーバリューストレージの限界を克服する必要があります。よりよいトランザクションとセカンダリーインデックスのような機能が必要です。

また我々のマルチデータセンターのアーキテクチャの向上も必要です。現在バックエンドとストレージは2ヶ所のデータセンターにあり、DR対応しています。

ただほとんどの場合、マシンの中には利用が不十分なものもあります。それはすべてのトラフィックが、どちらかのデータセンター単独で処理できる必要があるという考えなので、リソースを増やす必要があるからです。

また、現在のメッセージアプリケーションのビジネスロジックでは、データはいつでもどこでも一貫性があるという前提に立っています。しかし、HBaseは異なるデータセンター間でデータのレプリケートができますが、これは非同期なので、一貫性が保てないという問題が残ります。

またデータセンター間の遅延の問題も忘れてはいけません。地理的に離れた場所にあるからです。物理的な遅延が回避できない状態です。それが事態をさらに困難にしています。ですので、このような高いパフォーマンス要件がなく、追加の遅延が許容される可能性があるプロジェクトや場所があることを考慮して、複数のデータセンターにわたって、データの一貫したビューを提供できる可能性のある、他のストレージやソリューションを検討し調査してきました。