Istio 1.14からラウンドロビンではなくLEAST_REQUESTがデフォルトになる(ロードバランシングのアルゴリズム)

Istio 1.14から、デフォルトのロードバランシングのアルゴリズムがLEAST_REQUESTに変わります。従来はラウンドロビンでした。

Istio 1.14 Change Notes

Updated Istio’s default load balancing algorithm from ROUND_ROBIN to LEAST_REQUEST.

LEAST REQUESTとは

Envoyの公式ドキュメントより、Supported load balancers の Weighted least request の部分を翻訳しました。当方の英語力不足により、何かしら間違っている可能性がありますのでご容赦ください。

原文(クリックして展開)

Weighted least request

The least request load balancer uses different algorithms depending on whether hosts have the same or different weights.

all weights equal: An O(1) algorithm which selects N random available hosts as specified in the configuration (2 by default) and picks the host which has the fewest active requests (Mitzenmacher et al. has shown that this approach is nearly as good as an O(N) full scan). This is also known as P2C (power of two choices). The P2C load balancer has the property that a host with the highest number of active requests in the cluster will never receive new requests. It will be allowed to drain until it is less than or equal to all of the other hosts.

all weights not equal: If two or more hosts in the cluster have different load balancing weights, the load balancer shifts into a mode where it uses a weighted round robin schedule in which weights are dynamically adjusted based on the host’s request load at the time of selection.

In this case the weights are calculated at the time a host is picked using the following formula:

weight = load_balancing_weight / (active_requests + 1)^active_request_bias.

active_request_bias can be configured via runtime and defaults to 1.0. It must be greater than or equal to 0.0.

The larger the active request bias is, the more aggressively active requests will lower the effective weight.

If active_request_bias is set to 0.0, the least request load balancer behaves like the round robin load balancer and ignores the active request count at the time of picking.

For example, if active_request_bias is 1.0, a host with weight 2 and an active request count of 4 will have an effective weight of 2 / (4 + 1)^1 = 0.4. This algorithm provides good balance at steady state but may not adapt to load imbalance as quickly. Additionally, unlike P2C, a host will never truly drain, though it will receive fewer requests over time.

least requestは、すべてのweightsが等しい値かどうかでアルゴリズムが異なります。

すべてのweightsが等しい場合

O(1)アルゴリズムを使います。利用可能なホストからN個をランダムに選び、その中でもっともactive requestsが少ないホストを選択します。Nはconfigurationで設定し、デフォルトは2です。

このアプローチは全てのホストを比較する O(N) full scan に近い結果を得られます¹。これはP2C (power of two choices)としても知られています。

P2Cロードバランサーは、active requestsが多いホストが新しいリクエストを受け取らないという性質があります。これによりそのホストのactice requestsを他のホストと同じかそれ以下になるまで下げることができます。

weightsがホストごとに異なる場合

加重ラウンドロビンスケジュールを使用します。weight(加重)はそのときのホストのrequestsを元にダイナミックに調整します。weightは次の式で計算されます。

weight = load_balancing_weight / (active_requests + 1)^active_request_bias

active_request_bias はランタイム経由で設定でき、デフォルトでは1.0で、0.0以上である必要があります。active_request_bias が大きいほど、active requestsが増えたときにweightがより小さくなります。もしactive_request_biasが0.0の場合、リクエスト数が最小のロードバランサーはラウンドロビンのように動作し、active requestsは無視されます。

例えば、もしactive_request_biasが1.0、weightが2、active requestが4の場合、weightは 2 / (4 + 1)^1 = 0.4 になります。

このアルゴリズムは安定状態のときは良いバランスになりますが、急に負荷のバランスが崩れたときには対応できない可能性があります。高負荷になったホストは時間が経てば受けるリクエストが減りますが、0にはなりません。この点がP2Cとは異なります。

ラウンドロビンとの比較 / 引き続きラウンドロビンを使うには

Istio 1.14 Change Notes に書かれています。そのまま翻訳します。

原文(クリックして展開)

A number of experiments (by both the Istio and Envoy teams) have shown that LEAST_REQUEST outperforms ROUND_ROBIN in virtually all cases, with little/no downsides. It’s generally considered a drop-in replacement for ROUND_ROBIN.

ROUND_ROBIN will continue to be supported if explicitly specified. To restore ROUND_ROBIN as the default, set the istiod environment variable ENABLE_LEGACY_LB_ALGORITHM_DEFAULT=true.

IstioとEnvoyの両チームによる多くの実験では、ほぼ全てのケースでLEAST_REQUESTはラウンドロビンよりも良いパフォーマンスを示し、デメリットは微小か無でした。また、LEAST_REQUESTはラウンドロビンから drop-in replacement できると一般には考えられます。

※ drop-in replacement = 他の箇所を変更せずに、悪影響なくリプレースできること

ラウンドロビンは明示的に指定することで引き続き使えます。デフォルトのアルゴリズムをラウンドロビンに戻すには、istiodの環境変数に ENABLE_LEGACY_LB_ALGORITHM_DEFAULT=true を設定します。

所感

デメリットがなくそのまま移行できるとのことで、これからは LEAST_REQUEST を使おうと思います。

1. Mitzenmacher et al. The Power of Two Random Choices: A Survey of Techniques and Results ↩