Tail Latencyについて

research.google

この論文では、大規模な分散システムでは、まれなパフォーマンスの低下であっても、全リクエストのかなりの部分に影響を与えるとあります。

つまり大規模な分散システムではテールレイテンシの影響が大きくなります。

テールレイテンシは大きなパーセンタイルのレスポンス値のことです。(大きいというのがp99なのかp99.9なのかは文脈次第です)

パーセンタイルの例としては、99 パーセンタイルのレスポンスタイムが 100 msとすると、平均して 100 リクエスト中の 99リクエストには 100 ms未満しかかからず、1 リクエストには 100 ms以上かかることを意味します。

例えば、各サーバが通常10msで応答し、99%のレイテンシーが1秒であるシステムを考えてみると、ユーザーのリクエストがそのようなサーバー1台だけで処理された場合、1/100の確率でユーザーのリクエストが遅く(1秒かかる)なります。

このサーバー群に対して、ユーザーのリクエストが100台のサーバーから並行してレスポンスを収集しなければならない場合、ユーザーのリクエストの63％が1秒以上かかることになります。

1台のサーバレベルで1秒以上の遅延が発生するのが1万件に1件のサービスであっても、そのようなサーバが2,000台あるサービスでは、5件に1件の割合（18%）で1秒以上の遅延が発生することになります。

これはテールレイテンシの増幅と呼ばれます。(データ指向アプリケーションデザインp 17のコラム参照)

Googleような大規模な分散システムではテールレイテンシが全体のパフォーマンスに大きく影響します。

マシンの共有リソースの競合( CPUとか )、バックグランド処理などいろいろな要因で高いテールレイテンシが発生します。

大規模システムにおいて、レイテンシの変動の要因をすべて排除することは現実的ではないですが、この論文では、突発的、一時的な遅延を隠蔽したり、回避するすることでテールレイテンシを改善する手法を紹介しています。

数十ミリ秒の時間スケールで動作するリクエスト内の即時応答での対応

多くのWebサービスでは、データアイテムの複数のレプリカを配置することで、スループットを向上させ、障害が発生しても可用性を維持しています。

この対応では、レプリカを使って、1つの高レベルのリクエスト内のレイテンシーの変動を抑えます。

Hedged Requests

遅延のばらつきを抑える簡単な方法は、同じリクエストを複数のレプリカに発行し、いずれかのレプリカが先に応答した結果を使用することです。

クライアントは、最初の結果を受け取ると、残りの未処理のリクエストをキャンセルします。

このようなリクエストは Hedged requests と呼ばれています。

en.wikipedia.org

(この Hedged は金融用語の意味での両掛けから引用していると思っています)

この技術をnaiveに実装すると、通常は許容できないほどの負荷が追加されますが、負荷の増加をわずかに抑えながら、ほとんどの遅延削減効果を得られる多くのバリエーションが存在します。

アプローチの1つに、最初のリクエストが、このクラスのリクエストに対する95パーセンタイルの予想待ち時間を超えて未処理になるまで、2番目のリクエストの送信を遅らせるというものがあります。

この方法では、追加の負荷を約5％に抑えつつ、レイテンシーテールを大幅に短縮することができます。

この技術が有効なのは、レイテンシーの原因が特定のリクエストに固有のものではなく、他のなんらかの形態の干渉によるものであることが多いためです。

論文内では、100台の異なるサーバに分散しているBigTableのテーブルに格納された 1000個のキーの値を読み取るGoogle ベンチマークが紹介されていました。

10msの遅延後にヘッジ付きリクエストを送信すると、わずか2%のリクエスト数の増加で、1000個の値をすべて取得する際の 99.9%タイルの遅延が 1,800ms から 74msに短縮されたとありました。

Hedged requestsのオーバーヘッドは，プライマリリクエストよりも優先度の低いリクエストとしてタグ付けすることで，さらに低減することができます。

Tied Request

Hedged requests には、複数のサーバが同じリクエストを不必要に実行してしまうという脆弱な側面があります。

この余分な作業はは上記で紹介したような方法で緩和はできますが、この方法ではメリットが得られるのはごく一部のリクエストに限られてしまいます。

適切なリソースの消費で Hedged requests のより積極的な利用を可能にするには、リクエストをより速くキャンセルする必要があります。

一般的なレイテンシの変動要因は、リクエストが実行を開始する前のサーバでのキューイングの遅延です。

多くのサービスでは、リクエストが実際にスケジューリングされ、実行がはじまれば、その実行の完了時間のばらつきは大幅に減少します。

そこでGoogleでは、同時に複数のサーバにリクエストのコピーをエンキューし、サーバがこれらのコピーのステータスに関する更新情報を相互に通信できるようにしました。

サーバがサーバ間でステータスの更新を行うリクエストのことは Tied request と呼ばれています。

Tied request の最も単純な形式は、クライアントが2つの異なるサーバーにリクエストを送信し、それぞれのサーバーにもう一方のサーバーがタグ付けされます（結びつけられた tied）。

あるリクエストが実行を開始すると、そのリクエストは相手にキャンセルメッセージを送ります。キャンセルメッセージに対応するリクエストは、もう一方のサーバーにまだキューが残っているときは、直ちに中止するか、大幅に優先順位を下げます。

Googleはこの手法をクラスタレベルの分散ファイルシステムに実装しており、中央値と末尾値の両方の遅延を減らすのに効果的であることを紹介しています。

その中では、サーバー間のキャンセルを行う Tied request は、レイテンシーの中央値(50パーセンタイル)を16%削減し、レイテンシー分布の末尾に向かうにしたがって効果が増していき、99.9パーセンタイルのレイテンシーで40%近い削減を達成したとありました。

数十秒から数分の時間スケールで実行され、より長期的な現象の影響を隠すことを目的としたリクエストを跨いだ長期的な適応

多くのシステムでは、各パーティションのコストが等しくなるようにデータを分割しようとしますが、各マシンに単一のパーティションを静的に割り当てることは、下記から実際には十分ではありません。

サーマルスロットリングや共有ワークロードの干渉などにより、ベースとなるマシンの性能は　時間軸上で均一でも一定でもありません。
分割したのアイテムの割り当てに外れ値があると、データによる負荷の不均衡が発生する可能性があります（特定のアイテムが注目され、そのパーティションの負荷が増加する、有名人対応みたいないこと）