Grcov report - least_request

1

#include "source/extensions/load_balancing_policies/least_request/least_request_lb.h"

2

3

namespace Envoy {

4

namespace Upstream {

5

6

600352

double LeastRequestLoadBalancer::hostWeight(const Host& host) const {

7

  // This method is called to calculate the dynamic weight as following when all load balancing

8

  // weights are not equal:

9

//

10

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

11

//

12

  // `active_request_bias` can be configured via runtime and its value is cached in

13

  // `active_request_bias_` to avoid having to do a runtime lookup each time a host weight is

14

  // calculated.

15

//

16

  // When `active_request_bias == 0.0` we behave like `RoundRobinLoadBalancer` and return the

17

  // host weight without considering the number of active requests at the time we do the pick.

18

//

19

  // When `active_request_bias > 0.0` we scale the host weight by the number of active

20

  // requests at the time we do the pick. We always add 1 to avoid division by 0.

21

//

22

  // It might be possible to do better by picking two hosts off of the schedule, and selecting the

23

  // one with fewer active requests at the time of selection.

24

25

600352

  double host_weight = static_cast<double>(host.weight());

26

27

  // If the value of active requests is the max value, adding +1 will overflow

28

  // it and cause a divide by zero. This won't happen in normal cases but stops

29

  // failing fuzz tests

30

600352

  const uint64_t active_request_value =

31

600352

      host.stats().rq_active_.value() != std::numeric_limits<uint64_t>::max()

32

600352

          ? host.stats().rq_active_.value() + 1

33

600352

          : host.stats().rq_active_.value();

34

35

600352

  if (active_request_bias_ == 1.0) {

36

600260

    host_weight = static_cast<double>(host.weight()) / active_request_value;

37

600260

  } else if (active_request_bias_ != 0.0) {

38

72

    host_weight =

39

72

        static_cast<double>(host.weight()) / std::pow(active_request_value, active_request_bias_);

40

72

41

42

600352

  if (!noHostsAreInSlowStart()) {

43

138

    return applySlowStartFactor(host_weight, host);

44

600214

  } else {

45

600214

    return host_weight;

46

600214

47

600352

48

49

HostConstSharedPtr LeastRequestLoadBalancer::unweightedHostPeek(const HostVector&,

50

2

                                                                const HostsSource&) {

51

  // LeastRequestLoadBalancer can not do deterministic preconnecting, because

52

  // any other thread might select the least-requested-host between preconnect and

53

  // host-pick, and change the rq_active checks.

54

2

  return nullptr;

55

2

56

57

HostConstSharedPtr LeastRequestLoadBalancer::unweightedHostPick(const HostVector& hosts_to_use,

58

2600245

                                                                const HostsSource&) {

59

2600245

  HostSharedPtr candidate_host = nullptr;

60

61

2600245

  switch (selection_method_) {

62

2000002

  case envoy::extensions::load_balancing_policies::least_request::v3::LeastRequest::FULL_SCAN:

63

2000002

    candidate_host = unweightedHostPickFullScan(hosts_to_use);

64

2000002

    break;

65

600243

  case envoy::extensions::load_balancing_policies::least_request::v3::LeastRequest::N_CHOICES:

66

600243

    candidate_host = unweightedHostPickNChoices(hosts_to_use);

67

600243

    break;

68

  default:

69

    IS_ENVOY_BUG("unknown selection method specified for least request load balancer");

70

2600245

71

72

2600245

  return candidate_host;

73

2600245

74

75

2000002

HostSharedPtr LeastRequestLoadBalancer::unweightedHostPickFullScan(const HostVector& hosts_to_use) {

76

2000002

  HostSharedPtr candidate_host = nullptr;

77

78

2000002

  size_t num_hosts_known_tied_for_least = 0;

79

80

2000002

  const size_t num_hosts = hosts_to_use.size();

81

82

12000012

  for (size_t i = 0; i < num_hosts; ++i) {

83

10000010

    const HostSharedPtr& sampled_host = hosts_to_use[i];

84

85

10000010

    if (candidate_host == nullptr) {

86

      // Make a first choice to start the comparisons.

87

2000002

      num_hosts_known_tied_for_least = 1;

88

2000002

      candidate_host = sampled_host;

89

2000002

      continue;

90

2000002

91

92

8000008

    const auto candidate_active_rq = candidate_host->stats().rq_active_.value();

93

8000008

    const auto sampled_active_rq = sampled_host->stats().rq_active_.value();

94

95

8000008

    if (sampled_active_rq < candidate_active_rq) {

96

      // Reset the count of known tied hosts.

97

2000006

      num_hosts_known_tied_for_least = 1;

98

2000006

      candidate_host = sampled_host;

99

6000002

    } else if (sampled_active_rq == candidate_active_rq) {

100

6000000

      ++num_hosts_known_tied_for_least;

101

102

      // Use reservoir sampling to select 1 unique sample from the total number of hosts N

103

      // that will tie for least requests after processing the full hosts array.

104

//

105

      // Upon each new tie encountered, replace candidate_host with sampled_host

106

      // with probability (1 / num_hosts_known_tied_for_least percent).

107

      // The end result is that each tied host has an equal 1 / N chance of being the

108

      // candidate_host returned by this function.

109

6000000

      const size_t random_tied_host_index = random_.random() % num_hosts_known_tied_for_least;

110

6000000

      if (random_tied_host_index == 0) {

111

2666405

        candidate_host = sampled_host;

112

2666405

113

6000000

114

8000008

115

116

2000002

  return candidate_host;

117

2000002

118

119

600243

HostSharedPtr LeastRequestLoadBalancer::unweightedHostPickNChoices(const HostVector& hosts_to_use) {

120

600243

  HostSharedPtr candidate_host = nullptr;

121

122

1800741

  for (uint32_t choice_idx = 0; choice_idx < choice_count_; ++choice_idx) {

123

1200498

    const int rand_idx = random_.random() % hosts_to_use.size();

124

1200498

    const HostSharedPtr& sampled_host = hosts_to_use[rand_idx];

125

126

1200498

    if (candidate_host == nullptr) {

127

      // Make a first choice to start the comparisons.

128

600243

      candidate_host = sampled_host;

129

600243

      continue;

130

600243

131

132

600255

    const auto candidate_active_rq = candidate_host->stats().rq_active_.value();

133

600255

    const auto sampled_active_rq = sampled_host->stats().rq_active_.value();

134

135

600255

    if (sampled_active_rq < candidate_active_rq) {

136

94294

      candidate_host = sampled_host;

137

94294

138

600255

139

140

600243

  return candidate_host;

141

600243

142

143

} // namespace Upstream

144

} // namespace Envoy