envoyproxy · snowp · May 24, 2019 · Feb 27, 2019 · Mar 9, 2019 · Mar 11, 2019
diff --git a/api/envoy/api/v2/route/route.proto b/api/envoy/api/v2/route/route.proto
@@ -148,7 +148,6 @@ message VirtualHost {
   // Indicates the hedge policy for all routes in this virtual host. Note that setting a
   // route level entry will take precedence over this config and it'll be treated
   // independently (e.g.: values are not inherited).
-  // [#not-implemented-hide:]
   HedgePolicy hedge_policy = 17;
 }
 
@@ -803,7 +802,6 @@ message RouteAction {
   // Indicates that the route has a hedge policy. Note that if this is set,
   // it'll take precedence over the virtual host level hedge policy entirely
   // (e.g.: policies are not merged, most internal one becomes the enforced policy).
-  // [#not-implemented-hide:]
   HedgePolicy hedge_policy = 27;
 }
 
@@ -899,22 +897,28 @@ message RetryPolicy {
   RetryBackOff retry_back_off = 8;
 }
 
-// HTTP request hedging TODO(mpuncel) docs
-// [#not-implemented-hide:]
+// HTTP request hedging :ref:`architecture overview <arch_overview_http_routing_hedging>`.
 message HedgePolicy {
   // Specifies the number of initial requests that should be sent upstream.
   // Must be at least 1.
   // Defaults to 1.
+  // [#not-implemented-hide:]
   google.protobuf.UInt32Value initial_requests = 1 [(validate.rules).uint32.gte = 1];
 
   // Specifies a probability that an additional upstream request should be sent
   // on top of what is specified by initial_requests.
   // Defaults to 0.
+  // [#not-implemented-hide:]
   envoy.type.FractionalPercent additional_request_chance = 2;
 
   // Indicates that a hedged request should be sent when the per-try timeout
   // is hit. This will only occur if the retry policy also indicates that a
-  // timed out request should be retried. Defaults to false.
+  // timed out request should be retried.
+  // Once a timed out request is retried due to per try timeout, the router
+  // filter will ensure that it is not retried again even if the returned
+  // response headers would otherwise be retried according the specified
+  // :ref:`RetryPolicy <envoy_api_msg_route.RetryPolicy>`.
+  // Defaults to false.
   bool hedge_on_per_try_timeout = 3;
 }
 

diff --git a/docs/root/configuration/http_filters/router_filter.rst b/docs/root/configuration/http_filters/router_filter.rst
@@ -217,6 +217,18 @@ requests. This timeout must be <= the global route timeout (see
 caller to set a tight per try timeout to allow for retries while maintaining a reasonable overall
 timeout.
 
+x-envoy-hedge-on-per-try-timeout
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+Setting this header on egress requests will cause Envoy to use a request
+hedging strategy in the case of a per try timeout. This overrides the value set
+in the :ref:`route configuration
+<envoy_api_field_route.HedgePolicy.hedge_on_per_try_timeout>`. This means that a retry
+will be issued without resetting the original request, leaving multiple upstream requests
+in flight.
+
+The value of the header should be "true" or "false", and is ignored if invalid.
+
 .. _config_http_filters_router_x-envoy-immediate-health-check-fail:
 
 x-envoy-immediate-health-check-fail

diff --git a/docs/root/intro/arch_overview/http_routing.rst b/docs/root/intro/arch_overview/http_routing.rst
@@ -35,6 +35,7 @@ request. The router filter supports the following features:
 * Request timeout specified either via :ref:`HTTP
   header <config_http_filters_router_headers_consumed>` or via :ref:`route configuration
   <envoy_api_field_route.RouteAction.timeout>`.
+* :ref:`Request hedging <arch_overview_http_routing_hedging>` for retries in response to a request (per try) timeout.
 * Traffic shifting from one upstream cluster to another via :ref:`runtime values
   <envoy_api_field_route.RouteMatch.runtime_fraction>` (see :ref:`traffic shifting/splitting
   <config_http_conn_man_route_table_traffic_splitting>`).
@@ -87,6 +88,27 @@ headers <config_http_filters_router_headers_consumed>`. The following configurat
 Note that retries may be disabled depending on the contents of the :ref:`x-envoy-overloaded
 <config_http_filters_router_x-envoy-overloaded_consumed>`.
 
+.. _arch_overview_http_routing_hedging:
+
+Request Hedging
+---------------
+
+Envoy supports request hedging which can be enabled by specifying a :ref:`hedge
+policy <envoy_api_msg_route.HedgePolicy>`. This means that Envoy will race
+multiple simultaneous upstream requests and return the response associated with
+the first acceptable response headers to the downstream. The retry policy is
+used to determine whether a response should be returned or whether more
+responses should be awaited.
+
+Currently hedging can only be performed in response to a request timeout. This
+means that a retry request will be issued without canceling the initial
+timed-out request and a late response will be awaited. The first "good"
+response according to retry policy will be returned downstream.
+
+The implementation ensures that the same upstream request is not retried twice.
+This might otherwise occur if a request times out and then results in a 5xx
+response, creating two retriable events.
+
 .. _arch_overview_http_routing_priority:
 
 Priority routing

diff --git a/docs/root/intro/version_history.rst b/docs/root/intro/version_history.rst
@@ -33,6 +33,7 @@ Version history
   :ref:`buffer_flush_timeout <envoy_api_field_config.filter.network.redis_proxy.v2.RedisProxy.ConnPoolSettings.buffer_flush_timeout>` to control how quickly the buffer is flushed if it is not full.
 * router: add support for configuring a :ref:`grpc timeout offset <envoy_api_field_route.RouteAction.grpc_timeout_offset>` on incoming requests.
 * router: added ability to control retry back-off intervals via :ref:`retry policy <envoy_api_msg_route.RetryPolicy.RetryBackOff>`.
+* router: added ability to issue a hedged retry in response to a per try timeout via a :ref:`hedge policy <envoy_api_msg_route.HedgePolicy>`.
 * router: added a route name field to each http route in route.Route list 
 * router: per try timeouts will no longer start before the downstream request has been received
   in full by the router. This ensures that the per try timeout does not account for slow

diff --git a/include/envoy/http/header_map.h b/include/envoy/http/header_map.h
@@ -289,6 +289,7 @@ class HeaderEntry {
   HEADER_FUNC(EnvoyExpectedRequestTimeoutMs)                                                       \
   HEADER_FUNC(EnvoyExternalAddress)                                                                \
   HEADER_FUNC(EnvoyForceTrace)                                                                     \
+  HEADER_FUNC(EnvoyHedgeOnPerTryTimeout)                                                           \
   HEADER_FUNC(EnvoyImmediateHealthCheckFail)                                                       \
   HEADER_FUNC(EnvoyInternalRequest)                                                                \
   HEADER_FUNC(EnvoyIpTags)                                                                         \

diff --git a/include/envoy/router/router.h b/include/envoy/router/router.h
@@ -255,6 +255,16 @@ class RetryState {
   virtual RetryStatus shouldRetryHeaders(const Http::HeaderMap& response_headers,
                                          DoRetryCallback callback) PURE;
 
+  /**
+   * Determines whether given response headers would be retried by the retry policy, assuming
+   * sufficient retry budget and circuit breaker headroom. This is useful in cases where
+   * the information about whether a response is "good" or not is useful, but a retry should
+   * not be attempted for other reasons.
+   * @param response_headers supplies the response headers.
+   * @return bool true if a retry would be warranted based on the retry policy.
+   */
+  virtual bool wouldRetryFromHeaders(const Http::HeaderMap& response_headers) PURE;
+
   /**
    * Determine whether a request should be retried after a reset based on the reason for the reset.
    * @param reset_reason supplies the reset reason.
@@ -268,6 +278,19 @@ class RetryState {
   virtual RetryStatus shouldRetryReset(const Http::StreamResetReason reset_reason,
                                        DoRetryCallback callback) PURE;
 
+  /**
+   * Determine whether a "hedged" retry should be sent after the per try
+   * timeout expires. This means the original request is not canceled, but a
+   * new one is sent to hedge against the original request taking even longer.
+   * @param callback supplies the callback that will be invoked when the retry should take place.
+   *                 This is used to add timed backoff, etc. The callback will never be called
+   *                 inline.
+   * @return RetryStatus if a retry should take place. @param callback will be called at some point
+   *         in the future. Otherwise a retry should not take place and the callback will never be
+   *         called. Calling code should proceed with error handling.
+   */
+  virtual RetryStatus shouldHedgeRetryPerTryTimeout(DoRetryCallback callback) PURE;
+
   /**
    * Called when a host was attempted but the request failed and is eligible for another retry.
    * Should be used to update whatever internal state depends on previously attempted hosts.

diff --git a/source/common/http/conn_manager_utility.cc b/source/common/http/conn_manager_utility.cc
@@ -170,6 +170,7 @@ Network::Address::InstanceConstSharedPtr ConnectionManagerUtility::mutateRequest
     request_headers.removeEnvoyForceTrace();
     request_headers.removeEnvoyIpTags();
     request_headers.removeEnvoyOriginalUrl();
+    request_headers.removeEnvoyHedgeOnPerTryTimeout();
 
     for (const LowerCaseString& header : route_config.internalOnlyHeaders()) {
       request_headers.remove(header);

diff --git a/source/common/http/headers.h b/source/common/http/headers.h
@@ -42,6 +42,7 @@ class HeaderValues {
   const LowerCaseString EnvoyDownstreamServiceNode{"x-envoy-downstream-service-node"};
   const LowerCaseString EnvoyExternalAddress{"x-envoy-external-address"};
   const LowerCaseString EnvoyForceTrace{"x-envoy-force-trace"};
+  const LowerCaseString EnvoyHedgeOnPerTryTimeout{"x-envoy-hedge-on-per-try-timeout"};
   const LowerCaseString EnvoyImmediateHealthCheckFail{"x-envoy-immediate-health-check-fail"};
   const LowerCaseString EnvoyOriginalUrl{"x-envoy-original-url"};
   const LowerCaseString EnvoyInternalRequest{"x-envoy-internal"};

diff --git a/source/common/router/retry_state_impl.cc b/source/common/router/retry_state_impl.cc
@@ -207,6 +207,17 @@ RetryStatus RetryStateImpl::shouldRetryReset(Http::StreamResetReason reset_reaso
   return shouldRetry(wouldRetryFromReset(reset_reason), callback);
 }
 
+RetryStatus RetryStateImpl::shouldHedgeRetryPerTryTimeout(DoRetryCallback callback) {
+  // A hedged retry on per try timeout is always retried if there are retries
+  // left. NOTE: this is a bit different than non-hedged per try timeouts which
+  // are only retried if the applicable retry policy specifies either
+  // RETRY_ON_5XX or RETRY_ON_GATEWAY_ERROR. This is because these types of
+  // retries are associated with a stream reset which is analogous to a gateway
+  // error. When hedging on per try timeout is enabled, however, there is no
+  // stream reset.
+  return shouldRetry([]() -> bool { return true; }, callback);
+}
+
 bool RetryStateImpl::wouldRetryFromHeaders(const Http::HeaderMap& response_headers) {
   if (response_headers.EnvoyOverloaded() != nullptr) {
     return false;

diff --git a/source/common/router/retry_state_impl.h b/source/common/router/retry_state_impl.h
@@ -38,8 +38,12 @@ class RetryStateImpl : public RetryState {
   bool enabled() override { return retry_on_ != 0; }
   RetryStatus shouldRetryHeaders(const Http::HeaderMap& response_headers,
                                  DoRetryCallback callback) override;
+  // Returns true if the retry policy would retry the passed headers. Does not
+  // take into account circuit breaking or remaining tries.
+  bool wouldRetryFromHeaders(const Http::HeaderMap& response_headers) override;
   RetryStatus shouldRetryReset(const Http::StreamResetReason reset_reason,
                                DoRetryCallback callback) override;
+  RetryStatus shouldHedgeRetryPerTryTimeout(DoRetryCallback callback) override;
 
   void onHostAttempted(Upstream::HostDescriptionConstSharedPtr host) override {
     std::for_each(retry_host_predicates_.begin(), retry_host_predicates_.end(),
@@ -75,7 +79,6 @@ class RetryStateImpl : public RetryState {
   void enableBackoffTimer();
   void resetRetry();
   bool wouldRetryFromReset(const Http::StreamResetReason reset_reason);
-  bool wouldRetryFromHeaders(const Http::HeaderMap& response_headers);
   RetryStatus shouldRetry(bool would_retry, DoRetryCallback callback);
 
   const Upstream::ClusterInfo& cluster_;