ElasticSearch はどのようにして TDigest アルゴリズムを使用して数十億のデータのパーセンタイルを計算するのでしょうか?

[[393929]]

この記事はWeChatの公開アカウント「プログラマー李小冰」から転載したもので、著者は李小冰です。この記事を転載する場合は、プログラマー Li Xiaobing の公式アカウントまでご連絡ください。

みなさんこんにちは。私は李小兵です。分散型オープンソース検索および分析エンジンである ElasticSearch は、全文一致検索だけでなく、集計分析も実行できます。

今日は、集計分析でよく使われるパーセンタイル分析について見てみましょう。 n 個のデータは数値に従って並べられ、p% の位置にある値は p パーセンタイルと呼ばれます。

たとえば、ElasticSearch は各 Web サイトへのアクセス要求にかかる時間を記録し、合計要求の 99% にかかる最長時間である TP99 を計算する必要があります。

近似アルゴリズム

データサイズが小さい場合や、データが同じ場所に集中的に保存されている場合は、TP99 のようなパーセンタイル分析を簡単に実行できます。

しかし、データ量が増え続けるにつれて、データの集計分析では、データ量、精度、リアルタイムパフォーマンスの間でトレードオフが必要になり、そのうち 2 つしか満たせなくなります。

上の図に示すように、3 つのオプションがあります。

限られたデータコンピューティング: 高精度とリアルタイムのパフォーマンスを選択すると、単一マシンデータの MySQL 統計分析など、大量のデータを処理できなくなります。
オフラインコンピューティング: 大量のデータと高精度を選択すると、リアルタイムパフォーマンスが低下します。たとえば、Hadoop は PB レベルのデータに対して正確な分析を提供できますが、時間がかかる場合があります。
概算計算：大容量データとリアルタイム性能を選択しますが、0.5% など、ある程度の精度は失われますが、比較的正確な分析結果が得られます。

Elasticsearch は現在、カーディナリティとパーセンタイルの 2 つの近似アルゴリズムをサポートしています。

カーディナリティは、フィールドのカーディナリティ、つまりフィールドの個別または一意の値の数を計算するために使用されます。カーディナリティは、HyperLogLog (HLL) アルゴリズムに基づいて実装されます。

HLL はまずデータに対してハッシュ演算を実行し、次にハッシュ演算結果のビット数に基づいて確率を推定して基数を取得します。 HLL アルゴリズムの詳細については、「Redis HyperLogLog 詳細説明」の記事をご覧ください。

そして、パーセンタイルこそがこの記事の焦点です。

パーセンタイル

ElasticSearch は、パーセンタイルを使用して、指定されたフィールドのパーセンタイルを分析できます。具体的なリクエストは次のとおりです。ログインデックスの下のレイテンシフィールドのパーセンタイルを分析します。つまり、Web サイトリクエストのレイテンシパーセンタイルを計算します。

デフォルトでは、パーセンタイルは [1、5、25、50、75、95、99] という事前に設定されたパーセンタイル値のセットを返します。これらは、人々が関心を持つ一般的なパーセンタイル値を表し、範囲のどちらかの側に極端なパーセンタイルがあり、中間に他のパーセンタイルがあります。

具体的な戻り値は以下の図の通りです。最小遅延は約 75 ミリ秒ですが、最大遅延はほぼ 600 ミリ秒であることがわかります。対照的に、平均レイテンシは約 200 ミリ秒です。

前述の基数と同様に、パーセンタイルを計算するには近似アルゴリズムが必要です。

データ量が少ない場合、すべての値の順序付きリストをメモリ内に保持することで、さまざまなパーセンタイルを計算できますが、数十億のデータポイントが数十のノードに分散されている場合、このようなアルゴリズムは非現実的です。

したがって、パーセンタイルでは、さまざまな精度でさまざまなパーセンタイルを計算する近似アルゴリズムである TDigest アルゴリズムが使用されます。パーセンタイルの範囲が極端に広いほど、精度が高くなります。たとえば、1% または 99% のパーセンタイルは、50% のパーセンタイルよりも精度が高くなります。ほとんどの人は極端なパーセンタイルだけを気にするので、これは良い機能です。

TDigestアルゴリズム

TDigest は、ElastichSearch、Spark、Kylin などのシステムで使用される、シンプルで高速、高精度、並列化可能な近似パーセンタイルアルゴリズムです。 TDigest には 2 つの主要な実装アルゴリズムがあります。1 つはバッファアンドマージアルゴリズム、もう 1 つは AV L ツリークラスタリングアルゴリズムです。

TDigest が使用するアイデアは、近似アルゴリズムでよく使用されるスケッチです。これは、私たちが日常的に描くスケッチのように、データの一部を使用してデータセット全体の特性を特徴付けます。実際のオブジェクトとの間にはギャップがありますが、実際のオブジェクトと非常によく似ており、実際のオブジェクトの特徴を示すことができます。

次に、TDigest の原理を紹介します。たとえば、-30 から 30 の間に 500 個の数字がある場合、確率密度関数 (PDF) を使用してこのデータセットを表すことができます。

関数上の点の y 値は、その x 値がデータセット全体に現れる確率です。関数全体の面積の合計はちょうど 1 です。これは、データセット内のデータの分布を表していると言えます (誰もがよく知っている正規分布図は、この関数を示しています)。

データセットに対応した PDF 関数を使用すると、データセットのパーセンタイルも PDF 関数の領域で表現できます。下の図に示すように、75% パーセンタイルは、領域の 75% に対応する x 座標です。

PDF 関数曲線の点はデータセット内のデータに対応していることがわかっています。データ量が少ない場合は、データセット内のすべての点を使用して関数を計算できますが、データ量が多い場合は、少量のデータを使用してデータセット内のすべてのデータを置き換えることしかできません。

ここでは、データセットをグループにグループ化し、平均と重みを使用してグループ番号を置き換える必要があります。これら 2 つの数値は総称して Centroid (重心数) と呼ばれ、この重心数を使用して PDF を計算します。これが TDigest アルゴリズムの核となる考え方です。

上図に示すように、重心数の平均値が x 値として使用され、重心の数が y 値として使用されます。このデータセットの PDF 関数は、この重心数のセットを介して大まかにプロットできます。

同様に、パーセンタイルを計算するには、これらの重心数から対応する位置の重心数を見つけるだけでよく、その平均値がパーセンタイル値になります。

当然のことながら、重心の値が大きいほど、表すデータが多くなり、失われる情報が多くなり、精度が低下します。上図に示すように、重心の数が多すぎると精度が低下し、重心の数が少なすぎるとメモリなどのリソースを大量に消費し、近似アルゴリズムの高いリアルタイム効果が得られません。

そのため、TDigest は、圧縮率に基づいて、各重心数で表されるデータ量をパーセンタイルに従って制御します (圧縮率が高いほど、重心数が表すデータが多くなります)。両側の重心数は小さく、より正確ですが、中央の重心数は大きくなります。これにより、1% または 99% パーセンタイルが 50% パーセンタイルよりも正確であるという上記の効果が得られます。

ソースコード分析

ElasticSearch は、TDigest のオープンソース実装である t-digest を直接使用します。この github アドレスは https://github.com/tdunning/t-digest です。ElasticSearch の TDigestState クラスで t-digest 実装のカプセル化を確認できます。

t-digest は、TDigest アルゴリズムの 2 つの実装を提供します。

MergingDigestは、上記のバッファとマージのアルゴリズムに対応します。
AVLGroupTree は、AVL ツリーのクラスタリングアルゴリズムに対応します。

MergingDigest は、データセットがソートされ、圧縮率に基づいて重心の数を直接計算できるシナリオで使用されますが、AVLGroupTree では、AVL ツリーを使用して、データの「近さ」に基づいて自信を持ってデータを判断し、重心の数を計算する必要があります。

MergingDigest の実装は比較的簡単です。名前が示すように、このアルゴリズムはバッファアンドマージと呼ばれ、実装では tempWeight と tempMean という 2 つの配列を使用して重心配列を表します。データは保存された重心とマージされます。重量制限を超えると、新しい重心が作成されます。それ以外の場合は、現在の重心の平均値と数が変更されます。

MergingDigest と比較すると、AVLGroupTree には、AVL バイナリバランスツリーを通じて重心に最も近いデータを検索するという追加のステップがあります。最も近い重心を見つけた後、2 つがマージされ、重量制限を超えているかどうかが判断され、変更または作成操作が実行されます。

次に、AVLGroupTree の add メソッドを直接見てみましょう。

ElasticSearch はデータセットを処理するときに、add 関数を呼び出してデータセット内のデータを継続的に重心に追加し、統計が完了したら、その分位点を呼び出してパーセンタイルを計算します。