支持的负载均衡器

当一个过滤器需要获取到上游集群中的主机的连接时，集群管理器会使用负载均衡策略来确定选择哪个主机。负载均衡策略是可插拔的，并在配置中对每个上游集群进行指定。请注意，如果集群没有配置任何活动的健康检查策略，则所有上游集群成员都被认为是健康的，除非通过配置或 health_status 指定了其他情况。

加权轮询

这是一种简单的策略，其中每个可用的上游主机都按轮询顺序进行选择。如果在位置中为端点分配了权重，那么将使用加权轮询调度，其中权重较高的端点将在旋转中更频繁地出现，以实现有效的权重。

加权最少请求

最少请求负载均衡器会根据主机权重是否相同使用不同的算法。

所有权重相等：O(1) 算法，它会从配置中指定的可用主机中选择 N 个随机主机（默认值为 2 个），然后选择具有最少活动请求的主机 (Mitzenmacher 等人已经证明，这种方法几乎与 O(N) 全扫描一样好)。这也称为 P2C（二元选择能力）。P2C 负载均衡器具有以下特性：当主机上的活动请求数量增加时，主机权重会降低。P2C 选择对于负载均衡器实现特别有用，因为它可以抵抗集群行为。
所有权重不相等：如果集群中的两个或多个主机具有不同的负载均衡权重，则负载均衡器会切换到使用加权轮询调度模式，其中权重会根据主机在选择时当时的请求负载动态调整。

在这种情况下，权重是使用以下公式在选择主机时计算的

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

active_request_bias 可以通过运行时进行配置，默认值为 1.0。它必须大于或等于 0.0。

active_request_bias 越大，活动请求降低有效权重越积极。

如果 active_request_bias 设置为 0.0，则最少请求负载均衡器会像轮询负载均衡器一样工作，并忽略选择时的活动请求计数。

例如，如果 active_request_bias 为 1.0，则权重为 2 且活动请求计数为 4 的主机将具有 2 / (4 + 1)^1 = 0.4 的有效权重。此算法在稳定状态下提供了良好的平衡，但可能无法快速适应负载不平衡。此外，与 P2C 不同，主机永远不会真正耗尽，尽管随着时间的推移，它会接收到的请求更少。

环形哈希

环形/模哈希负载均衡器对上游主机实现一致性哈希。每个主机通过对其地址进行哈希而映射到一个圆圈（“环”）上；然后，每个请求通过对请求的某些属性进行哈希，并找到环形中顺时针方向上最近的对应主机来路由到一个主机。这种技术也通常称为 “Ketama” 哈希，并且与所有基于哈希的负载均衡器一样，它只有在使用协议路由来指定要对其进行哈希的值时才有效。如果你想要使用除主机地址之外的任何其他值作为哈希键（例如，Kubernetes StatefulSet 中主机的语义名称），那么你可以在 "envoy.lb" LbEndpoint.Metadata 中指定它，例如

  filter_metadata:
    envoy.lb:
      hash_key: "YOUR HASH KEY"

这将覆盖 use_hostname_for_hashing。

每个主机都被哈希并以与其权重成比例的次数放置在环形上。例如，如果主机 A 的权重为 1 且主机 B 的权重为 2，则环形上可能会有三个条目：一个用于主机 A，两个用于主机 B。然而，这实际上并不能提供所需的 2:1 分区，因为计算出的哈希可能恰好非常接近彼此；因此，有必要将每个主机上的哈希次数乘以一个系数，例如在环形上插入 100 个用于主机 A 的条目和 200 个用于主机 B 的条目，以更好地近似所需的分布。最佳实践是明确设置 minimum_ring_size 和 maximum_ring_size，并监控 min_hashes_per_host 和 max_hashes_per_host 计量器以确保良好的分布。如果环形被适当地分区，则从 N 个主机集中添加或删除一个主机将只影响 1/N 的请求。

当使用基于优先级的负载均衡时，优先级级别也是通过哈希选择的，因此，当后端集稳定时，选择到的端点仍然是一致的。

Maglev

Maglev 负载均衡器对上游主机实现一致性哈希。它使用本文第 3.4 节中描述的算法，并使用固定的表大小 65537（参见同一篇文章的第 5.3 节）。Maglev 可以作为环形哈希负载均衡器的直接替换，在需要一致性哈希的任何地方都可以使用它。与环形哈希负载均衡器类似，一致性哈希负载均衡器只有在使用协议路由来指定要对其进行哈希的值时才有效。如果你想要使用除主机地址之外的任何其他值作为哈希键（例如，Kubernetes StatefulSet 中主机的语义名称），那么你可以在 "envoy.lb" LbEndpoint.Metadata 中指定它，例如

  filter_metadata:
    envoy.lb:
      hash_key: "YOUR HASH KEY"

这将覆盖 use_hostname_for_hashing。

表构建算法将每个主机放置在表中与其权重成比例的次数，直到表完全填充。例如，如果主机 A 的权重为 1 且主机 B 的权重为 2，则主机 A 将有 21,846 个条目，而主机 B 将有 43,691 个条目（总共 65,537 个条目）。该算法尝试将每个主机至少放置一次，无论配置的主机和位置权重如何，因此在某些极端情况下，实际比例可能与配置的权重不同。例如，如果主机总数大于固定的表大小，则某些主机将获得 1 个条目，其余的将获得 0 个条目，无论权重如何。最佳实践是监控 min_entries_per_host 和 max_entries_per_host 计量器以确保没有主机被低估或丢失。

总的来说，与环形哈希（“ketama”）算法相比，Maglev 的表查找构建时间和主机选择时间要快得多（使用 256K 条目的大型环形尺寸时，分别大约快 10 倍和 5 倍）。虽然 Maglev 旨在最大程度地减少中断，但它不如环形哈希在发生上游主机变化时稳定。当主机被删除时，会有更多键移动位置（模拟显示大约两倍的键会移动）。通过增加 table_size 可以最大程度地减少中断量。也就是说，对于许多应用程序（包括 Redis），Maglev 很可能是环形哈希的优越直接替换。高级读者可以使用此基准来比较使用不同参数的环形哈希与 Maglev。

随机

随机负载均衡器会选择一个随机可用的主机。如果未配置任何健康检查策略，则随机负载均衡器通常比轮询效果更好。随机选择可以避免对失败主机之后的集合中的主机产生偏差。