1 // 2 // Copyright 2022 gRPC authors. 3 // 4 // Licensed under the Apache License, Version 2.0 (the "License"); 5 // you may not use this file except in compliance with the License. 6 // You may obtain a copy of the License at 7 // 8 // http://www.apache.org/licenses/LICENSE-2.0 9 // 10 // Unless required by applicable law or agreed to in writing, software 11 // distributed under the License is distributed on an "AS IS" BASIS, 12 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 // See the License for the specific language governing permissions and 14 // limitations under the License. 15 // 16 17 #ifndef GRPC_SRC_CORE_LOAD_BALANCING_WEIGHTED_ROUND_ROBIN_STATIC_STRIDE_SCHEDULER_H 18 #define GRPC_SRC_CORE_LOAD_BALANCING_WEIGHTED_ROUND_ROBIN_STATIC_STRIDE_SCHEDULER_H 19 20 #include <grpc/support/port_platform.h> 21 22 #include <stddef.h> 23 #include <stdint.h> 24 25 #include <vector> 26 27 #include "absl/functional/any_invocable.h" 28 #include "absl/types/optional.h" 29 #include "absl/types/span.h" 30 31 namespace grpc_core { 32 33 // StaticStrideScheduler implements a stride scheduler without the ability to 34 // add, remove, or modify elements after construction. In exchange, not only is 35 // it cheaper to construct and batch-update weights than a traditional dynamic 36 // stride scheduler, it can also be used to make concurrent picks without any 37 // locking. 38 // 39 // Construction is O(|weights|). Picking is O(1) if weights are similar, or 40 // O(|weights|) if the mean of the non-zero weights is a small fraction of the 41 // max. Stores two bytes per weight. 42 class StaticStrideScheduler final { 43 public: 44 // Constructs and returns a new StaticStrideScheduler, or nullopt if all 45 // wieghts are zero or |weights| <= 1. All weights must be >=0. 46 // `next_sequence_func` should return a rate monotonically increasing sequence 47 // number, which may wrap. `float_weights` does not need to live beyond the 48 // function. Caller is responsible for ensuring `next_sequence_func` remains 49 // valid for all calls to `Pick()`. 50 static absl::optional<StaticStrideScheduler> Make( 51 absl::Span<const float> float_weights, 52 absl::AnyInvocable<uint32_t()> next_sequence_func); 53 54 // Returns the index of the next pick. May invoke `next_sequence_func` 55 // multiple times. The returned value is guaranteed to be in [0, |weights|). 56 // Can be called concurrently iff `next_sequence_func` can. 57 size_t Pick() const; 58 59 private: 60 StaticStrideScheduler(std::vector<uint16_t> weights, 61 absl::AnyInvocable<uint32_t()> next_sequence_func); 62 63 mutable absl::AnyInvocable<uint32_t()> next_sequence_func_; 64 65 // List of backend weights scaled such that the max(weights_) == kMaxWeight. 66 std::vector<uint16_t> weights_; 67 }; 68 69 } // namespace grpc_core 70 71 #endif // GRPC_SRC_CORE_LOAD_BALANCING_WEIGHTED_ROUND_ROBIN_STATIC_STRIDE_SCHEDULER_H 72