Tail Latencyに関する論文読み

Misreading ChatのPodcastでTail Latencyに関する論文の紹介がされていて非常に興味深かったので、自分でも紹介されている論文を読んでみたという話。Misreading Chat Podcastのほうが的確な要約になっているので興味があればまず視聴するのがおすすめ。

• Episode 54 – Tales of the Tail – Misreading Chat

The Tail at Scale

米国計算機学会の機関紙Communications of the ACMの Feb/2013に掲載された記事。

• The Tail at Scale | February 2013 | Communications of the ACM ACM会員でないと全文参照できないかも。
• The Tail at Scale 同じ記事のPDF版。全文参照可能。

要点

• 大規模で複雑な分散システムでは、稀なパフォーマンスの低下が全体のパフォーマンス低下に繋がる事がある。
• 大規模システムではレイテンシ低下の原因を完全に除去することは難しい。
• 障害許容(フォールトトレラント)設計と同様に、テールレイテンシー許容設計をすることで、全体のパフォーマンス低下を対策することができる。

テールレイテンシーのよくある原因

• マシン上の共有リソース(CPUコア、キャッシュ、メモリ、ネットワーク)
• バックグラウンドデーモン
• グローバルリソース(ネットワークスイッチや共有ファイルシステム)
• メンテナンスのバックグラウンドアクティビティ(分散ファイルシステムでのデータ再構築、定期的なログ圧縮、ガベージコレクション)
• 中間サーバやネットワークスイッチにおけるキューイング
• ハードウェアによる制限（パワーリミット、電源管理、SSDのガベージコレクション等）

並列処理によってテールレイテンシーの問題は増幅される

• ユーザ要求を100台、1000台といった規模で分散処理する場合、1%, 0.1%の処理遅延が全体のパフォーマンスを悪化させる。

対策

• Hedged requests。同じ要求を複数のレプリカに連携、最速の応答を採用する。その後未処理の要求は取消す。
• Tied-Request。Hedged requestsで発生する無駄な処理を減らすためにキューに入れて処理をする。
• Micro-partitions。細分化する。
• Selective replication。 負荷の高い処理を優先的にレプリケーションする。
• Latency-induced probation。遅いマシンを隔離する。
• 最良の結果を返すのではなく、十分に良い結果で応答する。
• カナリア要求。いくつかの要求の応答時間が短いことを確認してから、残処理を実施する。

Tales of the Tail: Hardware, OS, and Application-level Sources of Tail Latency

• Tales of the Tail: Hardware, OS, and Application-level Sources of Tail Latency(PDF)

要点

• マルチコアマシンで実行されているハイスループットサーバーで、ハードウェア、OS、およびアプリケーションレベルでテールレイテンシが悪化する原因を探る。
• 予め作成した処理時間予想モデルに対して、Linuxサーバ（null RPCサービス、Memcached、およびNginx）で実測した上で検知されたテールレイテンシの原因を調査する。
• テールレイテンシの主要な原因は以下の通り
  • バックグラウンドプロセスからの干渉
  • 不適切なスケジューリング
  • 割り込みルーティング
  • CPUの省電力機能
  • NUMAの影響
• これらの要因を排除するとテールレイテンシの改善が図れる
• スループット、エネルギー、テールレイテンシの間にトレードオフがある

テールレイテンシーの原因

原因	理想値との乖離の理由	対策例	関係するトレードオフ
バックグラウンドプロセス	干渉によるスケジュール遅延	優先順位をRTにするか、専用コアに割当	RT化は他タスクの割当を阻害する可能性。専用コアはタスクアイドル時にシステム利用率を下げる可能性がある
Non-FIFO Scheduling	スレッドが順序どおりにスケジュールされていない	RTなどのFIFOスケジューラを使う	スケジューラの変更は全体の優先順位に影響する
並列アーキテクチャ	TCP接続を静的に分解するとワーカー別にキューが生成される	UDPイベント駆動型、またはスレッド毎のTCP接続アーキテクチャに変更する	UDP化は信頼性低下、スレッド毎のTCP接続はスループット低下となる
割込処理	コンテキストスイッチと、FIFO順序喪失	割込処理専用のコアを持つ	割込用コアの稼働率が低いとスループットが低下する可能性がある
NUMA Effects	NUMAノード間のメモリアクセスとキャッシュコヒーレンシプロトコルによる処理時間の増加	NUMAノードごとにプロセスを実行	複数キューによるレイテンシの発生、インスタンス間の負荷分散の問題が発生する可能性がある
Power Saving	CPUアイドル状態からの復帰時間	CPUの低電力制御をOFFにする	電力使用量の増加

ここまで読んでちょっと調べていて気づいたんだけど、論文ではなくてプレゼンテーションスライドも公開されているようだ。

• Tales of the Tail: Hardware, OS, and Application-level Sources of Tail Latency(Slides/PDF)

こっちを見たほうが断然わかりやすい印象。

もうちょっと関連論文を見てみようかと思い始めたところ。