grpc · donnadionne · Mar 17, 2021 · Mar 16, 2021
diff --git a/BUILD b/BUILD
@@ -1610,6 +1610,22 @@ grpc_cc_library(
     ],
 )
 
+grpc_cc_library(
+    name = "grpc_lb_policy_ring_hash",
+    srcs = [
+        "src/core/ext/filters/client_channel/lb_policy/ring_hash/ring_hash.cc",
+    ],
+    hdrs = [
+        "src/core/ext/filters/client_channel/lb_policy/ring_hash/ring_hash.h",
+    ],
+    language = "c++",
+    deps = [
+        "grpc_base",
+        "grpc_client_channel",
+        "grpc_lb_subchannel_list",
+    ],
+)
+
 grpc_cc_library(
     name = "grpc_lb_policy_round_robin",
     srcs = [
@@ -1869,6 +1885,7 @@ grpc_cc_library(
     deps = [
         "grpc_base",
         "grpc_client_channel",
+        "grpc_lb_policy_ring_hash",
         "grpc_xds_client",
     ],
 )

diff --git a/BUILD.gn b/BUILD.gn
@@ -255,6 +255,8 @@ config("grpc_config") {
         "src/core/ext/filters/client_channel/lb_policy/grpclb/load_balancer_api.h",
         "src/core/ext/filters/client_channel/lb_policy/pick_first/pick_first.cc",
         "src/core/ext/filters/client_channel/lb_policy/priority/priority.cc",
+        "src/core/ext/filters/client_channel/lb_policy/ring_hash/ring_hash.cc",
+        "src/core/ext/filters/client_channel/lb_policy/ring_hash/ring_hash.h",
         "src/core/ext/filters/client_channel/lb_policy/round_robin/round_robin.cc",
         "src/core/ext/filters/client_channel/lb_policy/subchannel_list.h",
         "src/core/ext/filters/client_channel/lb_policy/weighted_target/weighted_target.cc",

diff --git a/CMakeLists.txt b/CMakeLists.txt
@@ -1491,6 +1491,7 @@ add_library(grpc
   src/core/ext/filters/client_channel/lb_policy/grpclb/load_balancer_api.cc
   src/core/ext/filters/client_channel/lb_policy/pick_first/pick_first.cc
   src/core/ext/filters/client_channel/lb_policy/priority/priority.cc
+  src/core/ext/filters/client_channel/lb_policy/ring_hash/ring_hash.cc
   src/core/ext/filters/client_channel/lb_policy/round_robin/round_robin.cc
   src/core/ext/filters/client_channel/lb_policy/weighted_target/weighted_target.cc
   src/core/ext/filters/client_channel/lb_policy/xds/cds.cc

diff --git a/Makefile b/Makefile
@@ -1059,6 +1059,7 @@ LIBGRPC_SRC = \
     src/core/ext/filters/client_channel/lb_policy/grpclb/load_balancer_api.cc \
     src/core/ext/filters/client_channel/lb_policy/pick_first/pick_first.cc \
     src/core/ext/filters/client_channel/lb_policy/priority/priority.cc \
+    src/core/ext/filters/client_channel/lb_policy/ring_hash/ring_hash.cc \
     src/core/ext/filters/client_channel/lb_policy/round_robin/round_robin.cc \
     src/core/ext/filters/client_channel/lb_policy/weighted_target/weighted_target.cc \
     src/core/ext/filters/client_channel/lb_policy/xds/cds.cc \
@@ -2664,6 +2665,7 @@ ifneq ($(OPENSSL_DEP),)
 # installing headers to their final destination on the drive. We need this
 # otherwise parallel compilation will fail if a source is compiled first.
 src/core/ext/filters/client_channel/lb_policy/grpclb/grpclb_channel_secure.cc: $(OPENSSL_DEP)
+src/core/ext/filters/client_channel/lb_policy/ring_hash/ring_hash.cc: $(OPENSSL_DEP)
 src/core/ext/filters/client_channel/lb_policy/xds/cds.cc: $(OPENSSL_DEP)
 src/core/ext/filters/client_channel/lb_policy/xds/xds_cluster_impl.cc: $(OPENSSL_DEP)
 src/core/ext/filters/client_channel/lb_policy/xds/xds_cluster_manager.cc: $(OPENSSL_DEP)

diff --git a/build_autogenerated.yaml b/build_autogenerated.yaml
@@ -404,6 +404,7 @@ libs:
   - src/core/ext/filters/client_channel/lb_policy/grpclb/grpclb_channel.h
   - src/core/ext/filters/client_channel/lb_policy/grpclb/grpclb_client_stats.h
   - src/core/ext/filters/client_channel/lb_policy/grpclb/load_balancer_api.h
+  - src/core/ext/filters/client_channel/lb_policy/ring_hash/ring_hash.h
   - src/core/ext/filters/client_channel/lb_policy/subchannel_list.h
   - src/core/ext/filters/client_channel/lb_policy/xds/xds.h
   - src/core/ext/filters/client_channel/lb_policy/xds/xds_channel_args.h
@@ -896,6 +897,7 @@ libs:
   - src/core/ext/filters/client_channel/lb_policy/grpclb/load_balancer_api.cc
   - src/core/ext/filters/client_channel/lb_policy/pick_first/pick_first.cc
   - src/core/ext/filters/client_channel/lb_policy/priority/priority.cc
+  - src/core/ext/filters/client_channel/lb_policy/ring_hash/ring_hash.cc
   - src/core/ext/filters/client_channel/lb_policy/round_robin/round_robin.cc
   - src/core/ext/filters/client_channel/lb_policy/weighted_target/weighted_target.cc
   - src/core/ext/filters/client_channel/lb_policy/xds/cds.cc

diff --git a/config.m4 b/config.m4
@@ -65,6 +65,7 @@ if test "$PHP_GRPC" != "no"; then
     src/core/ext/filters/client_channel/lb_policy/grpclb/load_balancer_api.cc \
     src/core/ext/filters/client_channel/lb_policy/pick_first/pick_first.cc \
     src/core/ext/filters/client_channel/lb_policy/priority/priority.cc \
+    src/core/ext/filters/client_channel/lb_policy/ring_hash/ring_hash.cc \
     src/core/ext/filters/client_channel/lb_policy/round_robin/round_robin.cc \
     src/core/ext/filters/client_channel/lb_policy/weighted_target/weighted_target.cc \
     src/core/ext/filters/client_channel/lb_policy/xds/cds.cc \
@@ -1026,6 +1027,7 @@ if test "$PHP_GRPC" != "no"; then
   PHP_ADD_BUILD_DIR($ext_builddir/src/core/ext/filters/client_channel/lb_policy/grpclb)
   PHP_ADD_BUILD_DIR($ext_builddir/src/core/ext/filters/client_channel/lb_policy/pick_first)
   PHP_ADD_BUILD_DIR($ext_builddir/src/core/ext/filters/client_channel/lb_policy/priority)
+  PHP_ADD_BUILD_DIR($ext_builddir/src/core/ext/filters/client_channel/lb_policy/ring_hash)
   PHP_ADD_BUILD_DIR($ext_builddir/src/core/ext/filters/client_channel/lb_policy/round_robin)
   PHP_ADD_BUILD_DIR($ext_builddir/src/core/ext/filters/client_channel/lb_policy/weighted_target)
   PHP_ADD_BUILD_DIR($ext_builddir/src/core/ext/filters/client_channel/lb_policy/xds)

diff --git a/config.w32 b/config.w32
@@ -31,6 +31,7 @@ if (PHP_GRPC != "no") {
     "src\\core\\ext\\filters\\client_channel\\lb_policy\\grpclb\\load_balancer_api.cc " +
     "src\\core\\ext\\filters\\client_channel\\lb_policy\\pick_first\\pick_first.cc " +
     "src\\core\\ext\\filters\\client_channel\\lb_policy\\priority\\priority.cc " +
+    "src\\core\\ext\\filters\\client_channel\\lb_policy\\ring_hash\\ring_hash.cc " +
     "src\\core\\ext\\filters\\client_channel\\lb_policy\\round_robin\\round_robin.cc " +
     "src\\core\\ext\\filters\\client_channel\\lb_policy\\weighted_target\\weighted_target.cc " +
     "src\\core\\ext\\filters\\client_channel\\lb_policy\\xds\\cds.cc " +
@@ -1025,6 +1026,7 @@ if (PHP_GRPC != "no") {
   FSO.CreateFolder(base_dir+"\\ext\\grpc\\src\\core\\ext\\filters\\client_channel\\lb_policy\\grpclb");
   FSO.CreateFolder(base_dir+"\\ext\\grpc\\src\\core\\ext\\filters\\client_channel\\lb_policy\\pick_first");
   FSO.CreateFolder(base_dir+"\\ext\\grpc\\src\\core\\ext\\filters\\client_channel\\lb_policy\\priority");
+  FSO.CreateFolder(base_dir+"\\ext\\grpc\\src\\core\\ext\\filters\\client_channel\\lb_policy\\ring_hash");
   FSO.CreateFolder(base_dir+"\\ext\\grpc\\src\\core\\ext\\filters\\client_channel\\lb_policy\\round_robin");
   FSO.CreateFolder(base_dir+"\\ext\\grpc\\src\\core\\ext\\filters\\client_channel\\lb_policy\\weighted_target");
   FSO.CreateFolder(base_dir+"\\ext\\grpc\\src\\core\\ext\\filters\\client_channel\\lb_policy\\xds");

diff --git a/gRPC-C++.podspec b/gRPC-C++.podspec
@@ -221,6 +221,7 @@ Pod::Spec.new do |s|
                       'src/core/ext/filters/client_channel/lb_policy/grpclb/grpclb_channel.h',
                       'src/core/ext/filters/client_channel/lb_policy/grpclb/grpclb_client_stats.h',
                       'src/core/ext/filters/client_channel/lb_policy/grpclb/load_balancer_api.h',
+                      'src/core/ext/filters/client_channel/lb_policy/ring_hash/ring_hash.h',
                       'src/core/ext/filters/client_channel/lb_policy/subchannel_list.h',
                       'src/core/ext/filters/client_channel/lb_policy/xds/xds.h',
                       'src/core/ext/filters/client_channel/lb_policy/xds/xds_channel_args.h',
@@ -847,6 +848,7 @@ Pod::Spec.new do |s|
                               'src/core/ext/filters/client_channel/lb_policy/grpclb/grpclb_channel.h',
                               'src/core/ext/filters/client_channel/lb_policy/grpclb/grpclb_client_stats.h',
                               'src/core/ext/filters/client_channel/lb_policy/grpclb/load_balancer_api.h',
+                              'src/core/ext/filters/client_channel/lb_policy/ring_hash/ring_hash.h',
                               'src/core/ext/filters/client_channel/lb_policy/subchannel_list.h',
                               'src/core/ext/filters/client_channel/lb_policy/xds/xds.h',
                               'src/core/ext/filters/client_channel/lb_policy/xds/xds_channel_args.h',

diff --git a/gRPC-Core.podspec b/gRPC-Core.podspec
@@ -234,6 +234,8 @@ Pod::Spec.new do |s|
                       'src/core/ext/filters/client_channel/lb_policy/grpclb/load_balancer_api.h',
                       'src/core/ext/filters/client_channel/lb_policy/pick_first/pick_first.cc',
                       'src/core/ext/filters/client_channel/lb_policy/priority/priority.cc',
+                      'src/core/ext/filters/client_channel/lb_policy/ring_hash/ring_hash.cc',
+                      'src/core/ext/filters/client_channel/lb_policy/ring_hash/ring_hash.h',
                       'src/core/ext/filters/client_channel/lb_policy/round_robin/round_robin.cc',
                       'src/core/ext/filters/client_channel/lb_policy/subchannel_list.h',
                       'src/core/ext/filters/client_channel/lb_policy/weighted_target/weighted_target.cc',
@@ -1392,6 +1394,7 @@ Pod::Spec.new do |s|
                               'src/core/ext/filters/client_channel/lb_policy/grpclb/grpclb_channel.h',
                               'src/core/ext/filters/client_channel/lb_policy/grpclb/grpclb_client_stats.h',
                               'src/core/ext/filters/client_channel/lb_policy/grpclb/load_balancer_api.h',
+                              'src/core/ext/filters/client_channel/lb_policy/ring_hash/ring_hash.h',
                               'src/core/ext/filters/client_channel/lb_policy/subchannel_list.h',
                               'src/core/ext/filters/client_channel/lb_policy/xds/xds.h',
                               'src/core/ext/filters/client_channel/lb_policy/xds/xds_channel_args.h',

diff --git a/grpc.gemspec b/grpc.gemspec
@@ -150,6 +150,8 @@ Gem::Specification.new do |s|
   s.files += %w( src/core/ext/filters/client_channel/lb_policy/grpclb/load_balancer_api.h )
   s.files += %w( src/core/ext/filters/client_channel/lb_policy/pick_first/pick_first.cc )
   s.files += %w( src/core/ext/filters/client_channel/lb_policy/priority/priority.cc )
+  s.files += %w( src/core/ext/filters/client_channel/lb_policy/ring_hash/ring_hash.cc )
+  s.files += %w( src/core/ext/filters/client_channel/lb_policy/ring_hash/ring_hash.h )
   s.files += %w( src/core/ext/filters/client_channel/lb_policy/round_robin/round_robin.cc )
   s.files += %w( src/core/ext/filters/client_channel/lb_policy/subchannel_list.h )
   s.files += %w( src/core/ext/filters/client_channel/lb_policy/weighted_target/weighted_target.cc )

diff --git a/grpc.gyp b/grpc.gyp
@@ -480,6 +480,7 @@
         'src/core/ext/filters/client_channel/lb_policy/grpclb/load_balancer_api.cc',
         'src/core/ext/filters/client_channel/lb_policy/pick_first/pick_first.cc',
         'src/core/ext/filters/client_channel/lb_policy/priority/priority.cc',
+        'src/core/ext/filters/client_channel/lb_policy/ring_hash/ring_hash.cc',
         'src/core/ext/filters/client_channel/lb_policy/round_robin/round_robin.cc',
         'src/core/ext/filters/client_channel/lb_policy/weighted_target/weighted_target.cc',
         'src/core/ext/filters/client_channel/lb_policy/xds/cds.cc',

diff --git a/package.xml b/package.xml
@@ -130,6 +130,8 @@
     <file baseinstalldir="/" name="src/core/ext/filters/client_channel/lb_policy/grpclb/load_balancer_api.h" role="src" />
     <file baseinstalldir="/" name="src/core/ext/filters/client_channel/lb_policy/pick_first/pick_first.cc" role="src" />
     <file baseinstalldir="/" name="src/core/ext/filters/client_channel/lb_policy/priority/priority.cc" role="src" />
+    <file baseinstalldir="/" name="src/core/ext/filters/client_channel/lb_policy/ring_hash/ring_hash.cc" role="src" />
+    <file baseinstalldir="/" name="src/core/ext/filters/client_channel/lb_policy/ring_hash/ring_hash.h" role="src" />
     <file baseinstalldir="/" name="src/core/ext/filters/client_channel/lb_policy/round_robin/round_robin.cc" role="src" />
     <file baseinstalldir="/" name="src/core/ext/filters/client_channel/lb_policy/subchannel_list.h" role="src" />
     <file baseinstalldir="/" name="src/core/ext/filters/client_channel/lb_policy/weighted_target/weighted_target.cc" role="src" />

diff --git a/src/core/ext/filters/client_channel/lb_policy/ring_hash/ring_hash.cc b/src/core/ext/filters/client_channel/lb_policy/ring_hash/ring_hash.cc
@@ -0,0 +1,23 @@
+//
+// Copyright 2018 gRPC authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+//
+
+#include <grpc/support/port_platform.h>
+
+namespace grpc_core {
+
+const char* kRequestRingHashAttribute = "request_ring_hash";
+
+}  // namespace grpc_core
diff --git a/src/core/ext/filters/client_channel/lb_policy/ring_hash/ring_hash.h b/src/core/ext/filters/client_channel/lb_policy/ring_hash/ring_hash.h
@@ -0,0 +1,27 @@
+//
+// Copyright 2018 gRPC authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+//
+
+#ifndef GRPC_CORE_EXT_FILTERS_CLIENT_CHANNEL_LB_POLICY_RING_HASH_RING_HASH_H
+#define GRPC_CORE_EXT_FILTERS_CLIENT_CHANNEL_LB_POLICY_RING_HASH_RING_HASH_H
+
+#include <grpc/support/port_platform.h>
+
+namespace grpc_core {
+extern const char* kRequestRingHashAttribute;
+
+}  // namespace grpc_core
+
+#endif  // GRPC_CORE_EXT_FILTERS_CLIENT_CHANNEL_LB_POLICY_RING_HASH_RING_HASH_H
diff --git a/src/core/ext/filters/client_channel/resolver/xds/xds_resolver.cc b/src/core/ext/filters/client_channel/resolver/xds/xds_resolver.cc
@@ -26,6 +26,7 @@
 #include "xxhash.h"
 
 #include "src/core/ext/filters/client_channel/config_selector.h"
+#include "src/core/ext/filters/client_channel/lb_policy/ring_hash/ring_hash.h"
 #include "src/core/ext/filters/client_channel/resolver_registry.h"
 #include "src/core/ext/xds/xds_client.h"
 #include "src/core/ext/xds/xds_http_filters.h"
@@ -524,33 +525,52 @@ void XdsResolver::XdsConfigSelector::MaybeAddCluster(const std::string& name) {
   }
 }
 
-bool HeaderMatchHelper(const HeaderMatcher& header_matcher,
-                       grpc_metadata_batch* initial_metadata) {
-  std::string concatenated_value;
-  absl::optional<absl::string_view> value;
+absl::optional<absl::string_view> GetHeaderValue(
+    grpc_metadata_batch* initial_metadata, absl::string_view header_name,
+    std::string* concatenated_value) {
   // Note: If we ever allow binary headers here, we still need to
   // special-case ignore "grpc-tags-bin" and "grpc-trace-bin", since
   // they are not visible to the LB policy in grpc-go.
-  if (absl::EndsWith(header_matcher.name(), "-bin") ||
-      header_matcher.name() == "grpc-previous-rpc-attempts") {
-    value = absl::nullopt;
-  } else if (header_matcher.name() == "content-type") {
-    value = "application/grpc";
-  } else {
-    value = grpc_metadata_batch_get_value(
-        initial_metadata, header_matcher.name(), &concatenated_value);
+  if (absl::EndsWith(header_name, "-bin")) {
+    return absl::nullopt;
+  } else if (header_name == "content-type") {
+    return "application/grpc";
   }
-  return header_matcher.Match(value);
+  return grpc_metadata_batch_get_value(initial_metadata, header_name,
+                                       concatenated_value);
 }
 
 bool HeadersMatch(const std::vector<HeaderMatcher>& header_matchers,
                   grpc_metadata_batch* initial_metadata) {
   for (const auto& header_matcher : header_matchers) {
-    if (!HeaderMatchHelper(header_matcher, initial_metadata)) return false;
+    std::string concatenated_value;
+    if (!header_matcher.Match(GetHeaderValue(
+            initial_metadata, header_matcher.name(), &concatenated_value))) {
+      return false;
+    }
   }
   return true;
 }
 
+absl::optional<uint64_t> HeaderHashHelper(
+    const XdsApi::Route::HashPolicy& policy,
+    grpc_metadata_batch* initial_metadata) {
+  GPR_ASSERT(policy.type == XdsApi::Route::HashPolicy::HEADER);
+  std::string value_buffer;
+  absl::optional<absl::string_view> header_value =
+      GetHeaderValue(initial_metadata, policy.header_name, &value_buffer);
+  if (policy.regex != nullptr) {
+    // If GetHeaderValue() did not already store the value in
+    // value_buffer, copy it there now, so we can modify it.
+    if (header_value->data() != value_buffer.data()) {
+      value_buffer = std::string(*header_value);
+    }
+    RE2::GlobalReplace(&value_buffer, *policy.regex, policy.regex_substitution);
+    header_value = value_buffer;
+  }
+  return XXH64(header_value->data(), header_value->size(), 0);
+}
+
 bool UnderFraction(const uint32_t fraction_per_million) {
   // Generate a random number in [0, 1000000).
   const uint32_t random_number = rand() % 1000000;
@@ -612,13 +632,47 @@ ConfigSelector::CallConfig XdsResolver::XdsConfigSelector::GetCallConfig(
     XdsResolver* resolver =
         static_cast<XdsResolver*>(resolver_->Ref().release());
     ClusterState* cluster_state = it->second->Ref().release();
+    // Generate a hash
+    absl::optional<uint64_t> hash;
+    for (const auto& hash_policy : entry.route.hash_policies) {
+      absl::optional<uint64_t> new_hash;
+      switch (hash_policy.type) {
+        case XdsApi::Route::HashPolicy::HEADER:
+          new_hash = HeaderHashHelper(hash_policy, args.initial_metadata);
+          break;
+        case XdsApi::Route::HashPolicy::CHANNEL_ID:
+          new_hash =
+              static_cast<uint64_t>(reinterpret_cast<uintptr_t>(resolver));
+          break;
+        default:
+          GPR_ASSERT(0);
+      }
+      if (new_hash.has_value()) {
+        // Rotating the old value prevents duplicate hash rules from cancelling
+        // each other out and preserves all of the entropy
+        const uint64_t old_value =
+            hash.has_value() ? ((hash.value() << 1) | (hash.value() >> 63)) : 0;
+        hash = old_value ^ new_hash.value();
+      }
+      // If the policy is a terminal policy and a hash has been generated,
+      // ignore the rest of the hash policies.
+      if (hash_policy.terminal && hash.has_value()) {
+        break;
+      }
+    }
+    if (!hash.has_value()) {
+      // If there is no hash, we just choose a random value as a default.
+      hash = rand();
+    }
     CallConfig call_config;
     if (method_config != nullptr) {
       call_config.method_configs =
           method_config->GetMethodParsedConfigVector(grpc_empty_slice());
       call_config.service_config = std::move(method_config);
     }
     call_config.call_attributes[kXdsClusterAttribute] = it->first;
+    call_config.call_attributes[kRequestRingHashAttribute] =
+        absl::StrFormat("%" PRIu64, hash.value());
     call_config.on_call_committed = [resolver, cluster_state]() {
       cluster_state->Unref();
       ExecCtx::Run(