<commit_before>.. _arch_overview_load_balancing_types:

Supported load balancers
------------------------

When a filter needs to acquire a connection to a host in an upstream cluster, the cluster manager
uses a load balancing policy to determine which host is selected. The load balancing policies are
pluggable and are specified on a per upstream cluster basis in the :ref:`configuration
<envoy_api_msg_Cluster>`. Note that if no active health checking policy is :ref:`configured
<config_cluster_manager_cluster_hc>` for a cluster, all upstream cluster members are considered
healthy, unless otherwise specified through
:ref:`health_status <envoy_api_field_endpoint.LbEndpoint.health_status>`.

.. _arch_overview_load_balancing_types_round_robin:

Weighted round robin
^^^^^^^^^^^^^^^^^^^^

This is a simple policy in which each available upstream host is selected in round
robin order. If :ref:`weights
<envoy_api_field_endpoint.LbEndpoint.load_balancing_weight>` are assigned to
endpoints in a locality, then a weighted round robin schedule is used, where
higher weighted endpoints will appear more often in the rotation to achieve the
effective weighting.

.. _arch_overview_load_balancing_types_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
  :ref:`configuration <envoy_api_msg_Cluster.LeastRequestLbConfig>` (2 by default) and picks the
  host which has the fewest active requests (`Research
  <https://www.eecs.harvard.edu/~michaelm/postscripts/handbook2001.pdf>`_ 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
  (weight is divided by the current active request count. For example, a host with weight 2 and an
  active request count of 4 will have a synthetic weight of 2 / 4 = 0.5). 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.

.. _arch_overview_load_balancing_types_ring_hash:

Ring hash
^^^^^^^^^

The ring/modulo hash load balancer implements consistent hashing to upstream hosts. Each host is
mapped onto a circle (the "ring") by hashing its address; each request is then routed to a host by
hashing some property of the request, and finding the nearest corresponding host clockwise around
the ring. This technique is also commonly known as `"Ketama" <https://github.com/RJ/ketama>`_
hashing, and like all hash-based load balancers, it is only effective when protocol routing is used
that specifies a value to hash on.

Each host is hashed and placed on the ring some number of times proportional to its weight. For
example, if host A has a weight of 1 and host B has a weight of 2, then there might be three entries
on the ring: one for host A and two for host B. This doesn't actually provide the desired 2:1<commit_msg>docs: reword least request from N random load balancing link. (#9113)<commit_after>.. _arch_overview_load_balancing_types:

Supported load balancers
------------------------

When a filter needs to acquire a connection to a host in an upstream cluster, the cluster manager
uses a load balancing policy to determine which host is selected. The load balancing policies are
pluggable and are specified on a per upstream cluster basis in the :ref:`configuration
<envoy_api_msg_Cluster>`. Note that if no active health checking policy is :ref:`configured
<config_cluster_manager_cluster_hc>` for a cluster, all upstream cluster members are considered
healthy, unless otherwise specified through
:ref:`health_status <envoy_api_field_endpoint.LbEndpoint.health_status>`.

.. _arch_overview_load_balancing_types_round_robin:

Weighted round robin
^^^^^^^^^^^^^^^^^^^^

This is a simple policy in which each available upstream host is selected in round
robin order. If :ref:`weights
<envoy_api_field_endpoint.LbEndpoint.load_balancing_weight>` are assigned to
endpoints in a locality, then a weighted round robin schedule is used, where
higher weighted endpoints will appear more often in the rotation to achieve the
effective weighting.

.. _arch_overview_load_balancing_types_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
  :ref:`configuration <envoy_api_msg_Cluster.LeastRequestLbConfig>` (2 by default) and picks the
  host which has the fewest active requests (`Mitzenmacher et al.
  <https://www.eecs.harvard.edu/~michaelm/postscripts/handbook2001.pdf>`_ 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
  (weight is divided by the current active request count. For example, a host with weight 2 and an
  active request count of 4 will have a synthetic weight of 2 / 4 = 0.5). 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.

.. _arch_overview_load_balancing_types_ring_hash:

Ring hash
^^^^^^^^^

The ring/modulo hash load balancer implements consistent hashing to upstream hosts. Each host is
mapped onto a circle (the "ring") by hashing its address; each request is then routed to a host by
hashing some property of the request, and finding the nearest corresponding host clockwise around
the ring. This technique is also commonly known as `"Ketama" <https://github.com/RJ/ketama>`_
hashing, and like all hash-based load balancers, it is only effective when protocol routing is used
that specifies a value to hash on.

Each host is hashed and placed on the ring some number of times proportional to its weight. For
example, if host A has a weight of 1 and host B has a weight of 2, then there might be three entries
on the ring: one for host A and two for host B. This doesn't actually provide the desired 2:1
{'fraction_non_alphanumeric': 0.06068852905157164, 'fraction_numerical': 0.005715063273914818, 'mean_word_length': 4.66692367000771, 'pattern_counts': {'":': 0, '<': 17, '<?xml version=': 0, '>': 17, 'https://': 4, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3874232', 'n_tokens_mistral': 1949, 'n_tokens_neox': 1845, 'n_words': 1045}