#pragma once

#include "source/extensions/load_balancing_policies/common/load_balancer_impl.h"

namespace Envoy {

namespace Upstream {

/**

 * Weighted Least Request load balancer.

 *

 * In a normal setup when all hosts have the same weight it randomly picks up N healthy hosts

 * (where N is specified in the LB configuration) and compares number of active requests. Technique

 * is based on http://www.eecs.harvard.edu/~michaelm/postscripts/mythesis.pdf and is known as P2C

 * (power of two choices).

 *

 * When hosts have different weights, an RR EDF schedule is used. Host weight is scaled

 * by the number of active requests at pick/insert time. Thus, hosts will never fully drain as

 * they would in normal P2C, though they will get picked less and less often. In the future, we

 * can consider two alternate algorithms:

 * 1) Expand out all hosts by weight (using more memory) and do standard P2C.

 * 2) Use a weighted Maglev table, and perform P2C on two random hosts selected from the table.

 *    The benefit of the Maglev table is at the expense of resolution, memory usage is capped.

 *    Additionally, the Maglev table can be shared amongst all threads.

 */

class LeastRequestLoadBalancer : public EdfLoadBalancerBase {

public:

  LeastRequestLoadBalancer(

      const PrioritySet& priority_set, const PrioritySet* local_priority_set, ClusterLbStats& stats,

      Runtime::Loader& runtime, Random::RandomGenerator& random, uint32_t healthy_panic_threshold,

      const envoy::extensions::load_balancing_policies::least_request::v3::LeastRequest&

          least_request_config,

      TimeSource& time_source)

        active_request_bias_runtime_(

protected:

private:

  double hostWeight(const Host& host) const override;

  HostConstSharedPtr unweightedHostPeek(const HostVector& hosts_to_use,

                                        const HostsSource& source) override;

  HostConstSharedPtr unweightedHostPick(const HostVector& hosts_to_use,

                                        const HostsSource& source) override;

  HostSharedPtr unweightedHostPickFullScan(const HostVector& hosts_to_use);

  HostSharedPtr unweightedHostPickNChoices(const HostVector& hosts_to_use);

  const uint32_t choice_count_;

  // The exponent used to calculate host weights can be configured via runtime. We cache it for

  // performance reasons and refresh it in `LeastRequestLoadBalancer::refresh(uint32_t priority)`

  // whenever a `HostSet` is updated.

  double active_request_bias_{};

  const absl::optional<Runtime::Double> active_request_bias_runtime_;

  const envoy::extensions::load_balancing_policies::least_request::v3::LeastRequest::SelectionMethod

      selection_method_{};

};

} // namespace Upstream

} // namespace Envoy