LINE

- 日本語
  - English
  - 日本語
  - 한국어
  - 繁體中文
  - ภาษาไทย
  - Tiếng Việt

LINE Engineering
Blog

レイテンシーを計算する技術の話

Do Xuanhuy 2017.12.20

こんにちは、LINEメッセンジャーのサーバーサイドとモニタリングプラットフォームの開発を担当しているフィ（@dxhuy）です。この記事はLINE Advent Calendar 2017の20日目の記事です。

今日は、モニタリングシステムでよく使うレイテンシーやその計算方法などについて紹介したいと思います。LINEでは、日々ユーザが楽しくメッセージを送れるように、システムの安定性を第一に考えています。安定したシステムを保つためにたくさんの指標を見守る必要がありますが、その指標の1つが「レイテンシー」です。

ウィキペディアでは、レイテンシーは以下のように定義されています。

デバイスに対してデータ転送などを要求してから、その結果が返送されるまでの不顕性の高い遅延時間のこと

インターネットサービスにおいては、レイテンシーは基本的に「レスポンスタイム」のことです。つまり、リクエストを受けてからレスポンスを返すまでにかかる時間がレイテンシーです。

レイテンシーは、以下のようなコードを使ってとても簡単に計算できます。

long startTime = System.nanoTime(); // Javaではmonotonicクロックを使うため、nanoTime()を使います。
try {
   // 何か重い処理
} finally {
    long lateny = startTime - System.nanoTime();
    reporter.Report(latency);
}

簡単なコードですが、reporter.Reportをどのように実装すれば良いでしょうか。reporter.Report(latency)をどこかのデータストレージにそのまま貯めたら良いのでは、と考える方もいるかもしれません。ただほとんどの場合、レイテンシーの計算対象はサービスへのリクエストのように非常に件数が多いものなので、リクエスト毎のレイテンシーを記録するのは現実的ではありません。したがって、レイテンシー情報をまとめる形式が必要です。どのようにまとめて計算すべきかは、対象サービスのSLA（Service Level Agreement）によって変わることも多いです。たとえば、以下のようなさまざまな要求が存在します。

99.9%のリクエストに100ms以内にレスポンスする。
最大でも500ms以内にレスポンスする。
平均で250ms以内にレスポンスする。

ウェブサービスの運用では、全体のレイテンシーを把握するうえで、平均値や最大値にはほとんど意味がありません。ユーザに対する悪影響を把握するには「ヒストグラム」という形式がよく使われています。

ヒストグラム計算について

ヒストグラムには「バケット」という概念が存在します。「枠」や「箱」のようなものをイメージすると分かりやすいかもしれません。観測されたデータを決められたバケットに蓄積した後で、バケット配列の形でデータの全体像を把握できます。たとえば、0ms〜1000msのリクエストを10バケット（0〜100ms、100ms〜200ms、...）に分けて、その後で、レイテンシーの範囲毎のリクエスト数を簡単に把握できます。

バケットは線形的にも指数的にも分けることができ、以下のような簡単なコードで実現できます（PrometheusのHistogramを参考にしたコードです）。

線形バケット

linearBuckets(double start, double width, int count) {
  buckets = new double[count];
  for (int i = 0; i < count; i++){
    buckets[i] = start + i*width;
  }
  return this;
}

指数バケット

exponentialBuckets(double start, double factor, int count) {
  buckets = new double[count];
  for (int i = 0; i < count; i++) {
    buckets[i] = start * Math.pow(factor, i);
  }
  return this;
}

1つのレイテンシーを記録するには、該当するバケットをインクリメントします。

record(long val) { 
   buckets[(int) (val/bucketSize)]++; 
}

「よっしゃこの数行のコードでちゃんとサービスを監視できる！」と思われますか。小さいアプリケーションではこの実装で十分です。しかし、大規模なアプリケーションで使おうとすると、観測範囲が大きくなり、必要なメモリが線形に増えてしまいます。たとえば1000nsから100,000,000,000nsまでの範囲のレイテンシーの計算をする場合、100µsのバケットを使うとヒストグラムのサイズが4MBにもなってしまいます。1つのエンドポイントを監視するために4MBを使うのは現実的ではありません。ではもっと良いヒストグラムの計算方法は存在するでしょうか。

ここでは、その一例としてHdrHistogram（High Dynamic Range Histogram）を紹介します。これはJVMを開発しているAzul Systemsという会社が作ったライブラリで、以下のような特長があります。

少ないメモリフットプリントで広範囲のヒストグラムを作れる。
最初に設定した最大値を超えると自動的にリサイズできる。
メモリ・CPUセンシティブなアプリに優しい（新しい値を記録するときのゼロアロケーションなど）。
きちんとロックフリーに実装されている。

少ないメモリでどうやって広範囲のヒストグラムを作れるのか、疑問に感じる方もいると思います。GitHub上のREADME.mdに以下の説明があるのですが、ちょっと難しいですね。

Internally, data in HdrHistogram variants is maintained using a concept somewhat similar to that of floating point number representation: Using an exponent a (non-normalized) mantissa to support a wide dynamic range at a high but varying (by exponent value) resolution. AbstractHistogram uses exponentially increasing bucket value ranges (the parallel of the exponent portion of a floating point number) with each bucket containing a fixed number (per bucket) set of linear sub-buckets (the parallel of a non-normalized mantissa portion of a floating point number). Both dynamic range and resolution are configurable, with highestTrackableValue controlling dynamic range, and numberOfSignificantValueDigits controlling resolution

実際にコードを読む方が早いと思いますので、HdrHistogramの内部実装の解説は省略します。ですが、アイディアとしては、HdrHistogramは1つの値をそのままバケットに保存するのではなく、Floatのような表現に変換してからバケットに保存します。HdrHistogramのソースコードの以下の部分を読むと、このアイディアを理解できると思います。

値Xを表現するには、X1*2^X2のような形に変換して、X1とX2を別々のバケットを管理します。X1もX2も小さい値になるので、バケット数もそれなりに小さくできる、というアイディアです。使い方の詳細については、GitHubを見ると十分に理解できると思います。

では、HdrHistogramだけでアプリの監視は完璧でしょうか。実際に使うには、もう1つの問題を考慮する必要があります。たとえば、1つのエンドポイントのレイテンシーを1つのヒストグラムで表すと、「アプリが起動した瞬間」から「現在まで」が全部まとめられてしまいます。これではあまり意味のない数字になりますよね。

実際には、「直近1分間」や「直近1時間」などの数字の方が、運用には役に立つ数字です。そのようなメトリクスを取るため、異なる期間を対象とする複数のヒストグラムに1つの監視項目を同時に記録して、古いヒストグラムを自動的に消す、という方法がよく使われています。PrometheusのTimeWindowQuantilesの実装では、以下のように、ringBufferを用いて一定の期間で複数のHistogramがローテーションされています。

public void insert(double value) {
  rotate();
  for (Histogram histograms : ringBuffer) {
    histograms.insert(value);
  }
}

private synchronized Histogram rotate() {
  long timeSinceLastRotateMillis = System.currentTimeMillis() - lastRotateTimestampMillis;
  while (timeSinceLastRotateMillis > durationBetweenRotatesMillis) {
    ringBuffer[currentBucket] = new Histogram(quantiles);
    if (++currentBucket >= ringBuffer.length) {
      currentBucket = 0;
    }
    timeSinceLastRotateMillis -= durationBetweenRotatesMillis;
    lastRotateTimestampMillis += durationBetweenRotatesMillis;
  }
  return ringBuffer[currentBucket];
}

以下の図に示すように、ある瞬間に観測されたデータが記録されるのは、ローテーションできる複数のヒストグラムのうち、観測時刻が記録期間に含まれるものだけです。そして、記録期間が経過したヒストグラムは削除されます。

これで、本当に完璧でしょうか。はい、アプリのレイテンシー監視には、ここまでのコードで十分だと思います。実は、上のような処理（ヒストグラムの計算＋ヒストグラムのローテーション）を自前で実装することは結構大変で（特に、ローテーションロジックはスレッドセーフで実装しないといけません）、普通は既存のライブラリを使うことが多いです。LINEではPrometheusクライアントやDropwizardがよく使われていましたが、最近は、近い将来Springの標準メトリクスライブラリになる予定のMicrometerが広く使われています。

Micrometerの内部ではHdrHistogramが使われているため、十分な速度とパーフォマンスを保証できます。また、LINEが開発したRPCライブラリArmeriaも、Micrometerのモニタリングライブラリとして最近正式にサポートされるようになりました。みなさんも、ぜひMicrometerを試してみてください。

ここまで、レイテンシーを計測するためのヒストグラムの実装などについて紹介しました。ただ、ヒストグラム以外にレイテンシーを把握する方法はないかと思っている方がたくさんいるでしょう。

パーセンタイル計算について

実際にはヒストグラムがなくても、以下のようなクエリを取得する方法が存在します。

すべてのリクエストのうち、99.9%のレイテンシーが100ms〜110msであったかどうか
すべてのリクエストのうち、90.0%のレイテンシーが200ms〜210msであったかどうか
すべてのリクエストのうち、50.0%のレイテンシーが500ms〜510msであったかどうか

このようなクエリの「XX%の値」の部分は、パーセンタイルと呼ばれます（0.99、0.90、0.50を表現する「クォンタイル」という言葉もよく使われています）。パーセンタイル値の範囲は、もちろんヒストグラムからも計算できます。ただ、ヒストグラムはあくまでもある範囲の「すべて」を表現するものなので、99.9、90.0、50.0などの、偏った（バイアスを持つ）パーセンタイルを計算するだけなら不要な情報がたくさん入っています。実は、ヒストグラムを使わずにパーセンタイルを計算する方法が存在します。

Prometheusを使ったことがあればご存知かもしれませんが、Prometheusには「Summary」というデータ構造が存在します。このデータ構造を使うと、観測データのパーセンタイル情報を少ないメモリフットプリントで計算できます。Summaryの内容は「CKMSアルゴリズム」に基づいて実装されています。CKMSのアイディアは大きく2つに分けられます。

バイアスが高いクォンタイル（0.99、0.95など）の方が意味を持つ。
バイアスが高いクォンタイルで、小さいエラーバウンドを許可できれば、もっとコンパクトなデータ構造でデータの分布を表すことができる。

つまり、CKMSで計算されるp-クォンタイルは、e-approximate p-Quantileと呼ばれるp-クォンタイルから少しだけ離れたクォンタイルとなります。

これを実現するために、観測データに対し、各パーセンタイル（クォンタイル）の「あり得るレンジ（Possible Rank）」を同時に保存します。実装について詳しくは、https://github.com/prometheus/client_java/blob/master/simpleclient/src/main/java/io/prometheus/client/CKMSQuantiles.java の中のItemクラスを参考にしてください。観測されたItemオブジェクトをクォンタイルに変換するために、CKMSアルゴリズムでは以下の3つのオペレーションがサポートされます。

Insert
Delete
Compress

Compressにより、小さいメモリフットプリントで広範囲のクォンタイルを監視できます。CKMSの原理と実装について詳しくは、「Effective Computation of Biased Quantiles over Data Streams」またはソースコードを参照してください。

CKMS以外にも、クォンタイルを計算するアルゴリズムはFrugalやGKなど、たくさん存在します。ただ現時点では、エラー率が低くパフォーマンスが良いCKMSが一番よく使われています。

クォンタイル推測アルゴリズムについては、「Quantiles and Equidepth Histograms over Streams」によくまとめられています。

クォンタイル推測アルゴリズム（Quantile Estimation）にはヒストグラムの場合のようなバケットの指定などが不要なため、運用の負荷が低く使用メモリも減りますが、以下のデメリットもあります。

ヒストグラムは該当するバケットを単純にインクリメントするだけである一方、クォンタイルは範囲の計算や推測にさらに計算コストがかかる。
ホストを横断する数字（ある特定のデータセンターのクラスタのクォンタイルなど）の場合は、正確な計算ができない。

おまけ：Coordinated Omissionについて

前の節では、レイテンシーを計測するために{try, finally}のようなコードを書きました。

long startTime = System.nanoTime(); 
try {
   // 何か重い処理
} finally {
    long lateny = startTime - System.nanoTime();
    reporter.Report(latency);
}

このコードには実はもう1つ問題があります。もしfinallyのブロックの後に非常に大きなGC（ガベージコレクション）が発生したら、それは監視されないでしょう。この問題は「Coordinated Omission」と呼ばれています。このような想定外のレイテンシーなどが原因で正確な数字を計測できない問題は、LatencyUtilsというライブラリを使って解決できます。

LatencyUtilsの内部ではHdrHistogramが使われているので、パフォーマンスなどを気にせず使ってもよいでしょう。LatencyUtilsはGC問題などを意識してレイテンシーを計算してくれるので、特に何もしなくても正確な数字が取れてとても便利です（ちなみに、前に述べたMicrometerでもLatencyUtilsでCoordinated Omission問題を解決してくれます。みなさんもぜひMicrometerをお試しください）。そのライブラリの実装では、バックグラウンドのスレッドで無限ループで定期的に時間を計測して、いつGCが止まるかを時間の差で判断します。

まとめ

この記事では、レイテンシーの計算は一筋縄ではいかないこと、そしてヒストグラムやクォンタイルの違いを理解して、サービス監視などに正しく適用する方法について説明しました。レイテンシーをもっと理解するための参考資料として、HdrHistogram作者のスライドを挙げておきます。とてもよくできているので、ぜひ見てみてください。

Understanding Latency: Some Key Lessons & Tools

Micrometerは今後Springの標準モニタリングライブラリになりますので、みんなさんも試してみてはどうでしょう。ただ、現時点ではまだ不安定の部分もありますので、ちゃんと正式リリースがでてからプロダクション導入したほうがベストです。

LINEのサービスの安定性をもっと向上するために、今後もモニタリングやそのためのツールなどに注力していきたいと思っています。仲間も積極的に募集していますので、ご興味をお持ちの方は、ぜひ以下のポジションにご応募ください。

ソフトウェアエンジニア（Software Engineer、Engineering Efficiency）【LINEプラットフォーム】

明日の記事は、砂金さんによる「Qiitaで人気のLINE関連投稿紹介（保存版）」です。お楽しみに！

AdventCalendar

Do Xuanhuy 2017.12.20

リストへ戻る