Line data    Source code

       1             : #pragma once
       2             : 
       3             : #include "envoy/common/pure.h"
       4             : #include "envoy/common/random_generator.h"
       5             : #include "envoy/config/cluster/v3/cluster.pb.h"
       6             : #include "envoy/extensions/load_balancing_policies/maglev/v3/maglev.pb.h"
       7             : #include "envoy/extensions/load_balancing_policies/maglev/v3/maglev.pb.validate.h"
       8             : #include "envoy/stats/scope.h"
       9             : #include "envoy/stats/stats_macros.h"
      10             : #include "envoy/upstream/load_balancer.h"
      11             : 
      12             : #include "source/common/common/bit_array.h"
      13             : #include "source/common/upstream/thread_aware_lb_impl.h"
      14             : 
      15             : namespace Envoy {
      16             : namespace Upstream {
      17             : 
      18             : using MaglevLbProto = envoy::extensions::load_balancing_policies::maglev::v3::Maglev;
      19             : using ClusterProto = envoy::config::cluster::v3::Cluster;
      20             : using LegacyMaglevLbProto = ClusterProto::MaglevLbConfig;
      21             : 
      22             : /**
      23             :  * Load balancer config that used to wrap legacy maglev config.
      24             :  */
      25             : class LegacyMaglevLbConfig : public Upstream::LoadBalancerConfig {
      26             : public:
      27             :   LegacyMaglevLbConfig(const ClusterProto& cluster);
      28             : 
      29           0 :   OptRef<const LegacyMaglevLbProto> lbConfig() const {
      30           0 :     if (lb_config_.has_value()) {
      31           0 :       return lb_config_.value();
      32           0 :     }
      33           0 :     return {};
      34           0 :   };
      35             : 
      36             : private:
      37             :   absl::optional<LegacyMaglevLbProto> lb_config_;
      38             : };
      39             : 
      40             : /**
      41             :  * Load balancer config that used to wrap typed maglev config.
      42             :  */
      43             : class TypedMaglevLbConfig : public Upstream::LoadBalancerConfig {
      44             : public:
      45             :   TypedMaglevLbConfig(const MaglevLbProto& config);
      46             : 
      47             :   const MaglevLbProto lb_config_;
      48             : };
      49             : 
      50             : /**
      51             :  * All Maglev load balancer stats. @see stats_macros.h
      52             :  */
      53             : #define ALL_MAGLEV_LOAD_BALANCER_STATS(GAUGE)                                                      \
      54           0 :   GAUGE(max_entries_per_host, Accumulate)                                                          \
      55           0 :   GAUGE(min_entries_per_host, Accumulate)
      56             : 
      57             : /**
      58             :  * Struct definition for all Maglev load balancer stats. @see stats_macros.h
      59             :  */
      60             : struct MaglevLoadBalancerStats {
      61             :   ALL_MAGLEV_LOAD_BALANCER_STATS(GENERATE_GAUGE_STRUCT)
      62             : };
      63             : 
      64             : class MaglevTable;
      65             : using MaglevTableSharedPtr = std::shared_ptr<MaglevTable>;
      66             : 
      67             : /**
      68             :  * This is an implementation of Maglev consistent hashing as described in:
      69             :  * https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/44824.pdf
      70             :  * section 3.4. Specifically, the algorithm shown in pseudocode listing 1 is implemented with a
      71             :  * fixed table size of 65537. This is the recommended table size in section 5.3.
      72             :  */
      73             : class MaglevTable : public ThreadAwareLoadBalancerBase::HashingLoadBalancer,
      74             :                     protected Logger::Loggable<Logger::Id::upstream> {
      75             : public:
      76             :   MaglevTable(uint64_t table_size, MaglevLoadBalancerStats& stats);
      77           0 :   ~MaglevTable() override = default;
      78             : 
      79             :   // Recommended table size in section 5.3 of the paper.
      80             :   static constexpr uint64_t DefaultTableSize = 65537;
      81             :   static constexpr uint64_t MaxNumberOfHostsForCompactMaglev = (static_cast<uint64_t>(1) << 32) - 1;
      82             : 
      83             : protected:
      84             :   struct TableBuildEntry {
      85             :     TableBuildEntry(const HostConstSharedPtr& host, uint64_t offset, uint64_t skip, double weight)
      86           0 :         : host_(host), offset_(offset), skip_(skip), weight_(weight) {}
      87             : 
      88             :     HostConstSharedPtr host_;
      89             :     const uint64_t offset_;
      90             :     const uint64_t skip_;
      91             :     const double weight_;
      92             :     double target_weight_{};
      93             :     uint64_t next_{};
      94             :     uint64_t count_{};
      95             :   };
      96             : 
      97             :   uint64_t permutation(const TableBuildEntry& entry);
      98             : 
      99             :   /**
     100             :    * Template method for constructing the Maglev table.
     101             :    */
     102             :   void constructMaglevTableInternal(const NormalizedHostWeightVector& normalized_host_weights,
     103             :                                     double max_normalized_weight, bool use_hostname_for_hashing);
     104             : 
     105             :   const uint64_t table_size_;
     106             :   MaglevLoadBalancerStats& stats_;
     107             : 
     108             : private:
     109             :   /**
     110             :    * Implementation specific construction of data structures to represent the
     111             :    * Maglev Table.
     112             :    */
     113             :   virtual void constructImplementationInternals(std::vector<TableBuildEntry>& table_build_entries,
     114             :                                                 double max_normalized_weight) PURE;
     115             : 
     116             :   /**
     117             :    * Log each entry of the maglev table (useful for debugging).
     118             :    */
     119             :   virtual void logMaglevTable(bool use_hostname_for_hashing) const PURE;
     120             : };
     121             : 
     122             : /**
     123             :  * This is an implementation of Maglev consistent hashing that directly holds
     124             :  * pointers.
     125             :  */
     126             : class OriginalMaglevTable : public MaglevTable {
     127             : public:
     128             :   OriginalMaglevTable(const NormalizedHostWeightVector& normalized_host_weights,
     129             :                       double max_normalized_weight, uint64_t table_size,
     130             :                       bool use_hostname_for_hashing, MaglevLoadBalancerStats& stats)
     131           0 :       : MaglevTable(table_size, stats) {
     132           0 :     constructMaglevTableInternal(normalized_host_weights, max_normalized_weight,
     133           0 :                                  use_hostname_for_hashing);
     134           0 :   }
     135           0 :   ~OriginalMaglevTable() override = default;
     136             : 
     137             :   // ThreadAwareLoadBalancerBase::HashingLoadBalancer
     138             :   HostConstSharedPtr chooseHost(uint64_t hash, uint32_t attempt) const override;
     139             : 
     140             : private:
     141             :   void constructImplementationInternals(std::vector<TableBuildEntry>& table_build_entries,
     142             :                                         double max_normalized_weight) override;
     143             : 
     144             :   void logMaglevTable(bool use_hostname_for_hashing) const override;
     145             :   std::vector<HostConstSharedPtr> table_;
     146             : };
     147             : 
     148             : /**
     149             :  * This maglev implementation leverages the number of hosts to more efficiently
     150             :  * populate the maglev table.
     151             :  * TODO(kbaichoo): Re-evaluate whether we should have the abstraction on the
     152             :  * table representation.
     153             :  */
     154             : class CompactMaglevTable : public MaglevTable {
     155             : public:
     156             :   CompactMaglevTable(const NormalizedHostWeightVector& normalized_host_weights,
     157             :                      double max_normalized_weight, uint64_t table_size,
     158             :                      bool use_hostname_for_hashing, MaglevLoadBalancerStats& stats);
     159           0 :   ~CompactMaglevTable() override = default;
     160             : 
     161             :   // ThreadAwareLoadBalancerBase::HashingLoadBalancer
     162             :   HostConstSharedPtr chooseHost(uint64_t hash, uint32_t attempt) const override;
     163             : 
     164             : private:
     165             :   void constructImplementationInternals(std::vector<TableBuildEntry>& table_build_entries,
     166             :                                         double max_normalized_weight) override;
     167             :   void logMaglevTable(bool use_hostname_for_hashing) const override;
     168             : 
     169             :   // Leverage a BitArray to more compactly fit represent the MaglevTable.
     170             :   // The BitArray will index into the host_table_ which will provide the given
     171             :   // host to load balance to.
     172             :   BitArray table_;
     173             :   std::vector<HostConstSharedPtr> host_table_;
     174             : };
     175             : 
     176             : /**
     177             :  * Thread aware load balancer implementation for Maglev.
     178             :  */
     179             : class MaglevLoadBalancer : public ThreadAwareLoadBalancerBase {
     180             : public:
     181             :   MaglevLoadBalancer(const PrioritySet& priority_set, ClusterLbStats& stats, Stats::Scope& scope,
     182             :                      Runtime::Loader& runtime, Random::RandomGenerator& random,
     183             :                      OptRef<const envoy::config::cluster::v3::Cluster::MaglevLbConfig> config,
     184             :                      const envoy::config::cluster::v3::Cluster::CommonLbConfig& common_config);
     185             : 
     186             :   MaglevLoadBalancer(const PrioritySet& priority_set, ClusterLbStats& stats, Stats::Scope& scope,
     187             :                      Runtime::Loader& runtime, Random::RandomGenerator& random,
     188             :                      uint32_t healthy_panic_threshold,
     189             :                      const envoy::extensions::load_balancing_policies::maglev::v3::Maglev& config);
     190             : 
     191           0 :   const MaglevLoadBalancerStats& stats() const { return stats_; }
     192           0 :   uint64_t tableSize() const { return table_size_; }
     193             : 
     194             : private:
     195             :   // ThreadAwareLoadBalancerBase
     196             :   HashingLoadBalancerSharedPtr
     197             :   createLoadBalancer(const NormalizedHostWeightVector& normalized_host_weights,
     198             :                      double /* min_normalized_weight */, double max_normalized_weight) override;
     199             :   static MaglevLoadBalancerStats generateStats(Stats::Scope& scope);
     200             : 
     201             :   Stats::ScopeSharedPtr scope_;
     202             :   MaglevLoadBalancerStats stats_;
     203             :   const uint64_t table_size_;
     204             :   const bool use_hostname_for_hashing_;
     205             :   const uint32_t hash_balance_factor_;
     206             : };
     207             : 
     208             : } // namespace Upstream
     209             : } // namespace Envoy