Implement exponential back-off mechanism and enforce it at the URLRequestHttpJob level.

net/url_request/request_throttler_entry.cc

+// Copyright (c) 2010 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "net/url_request/request_throttler_entry.h"
+
+#include <cmath>
+
+#include "base/logging.h"
+#include "base/rand_util.h"
+#include "base/string_number_conversions.h"
+#include "net/url_request/request_throttler_header_interface.h"
+
+const int RequestThrottlerEntry::kDefaultSlidingWindowPeriodMs = 2000;
+const int RequestThrottlerEntry::kDefaultMaxSendThreshold = 20;
+const int RequestThrottlerEntry::kDefaultInitialBackoffMs = 700;
+const int RequestThrottlerEntry::kDefaultAdditionalConstantMs = 100;
+const double RequestThrottlerEntry::kDefaultMultiplyFactor = 2.0;
+const double RequestThrottlerEntry::kDefaultJitterFactor = 0.4;
+const int RequestThrottlerEntry::kDefaultMaximumBackoffMs = 24 * 60 * 60 * 1000;
+const int RequestThrottlerEntry::kDefaultEntryLifetimeMs = 120000;
+const char RequestThrottlerEntry::kRetryHeaderName[] = "X-Retry-After";
+
+RequestThrottlerEntry::RequestThrottlerEntry()
+    : sliding_window_period_ms_(kDefaultSlidingWindowPeriodMs),
+      max_send_threshold_(kDefaultMaxSendThreshold),
+      initial_backoff_ms_(kDefaultInitialBackoffMs),
+      additional_constant_ms_(kDefaultAdditionalConstantMs),
+      multiply_factor_(kDefaultMultiplyFactor),
+      jitter_factor_(kDefaultJitterFactor),
+      maximum_backoff_ms_(kDefaultMaximumBackoffMs),
+      entry_lifetime_ms_(kDefaultEntryLifetimeMs) {
+  Initialize();
+}
+
+RequestThrottlerEntry::RequestThrottlerEntry(
+    int sliding_window_period_ms,
+    int max_send_threshold,
+    int initial_backoff_ms,
+    int additional_constant_ms,
+    double multiply_factor,
+    double jitter_factor,
+    int maximum_backoff_ms)
+    : sliding_window_period_ms_(sliding_window_period_ms),
+      max_send_threshold_(max_send_threshold),
+      initial_backoff_ms_(initial_backoff_ms),
+      additional_constant_ms_(additional_constant_ms),
+      multiply_factor_(multiply_factor),
+      jitter_factor_(jitter_factor),
+      maximum_backoff_ms_(maximum_backoff_ms),
+      entry_lifetime_ms_(-1) {
+  DCHECK(sliding_window_period_ms_ > 0 &&
+         max_send_threshold_ > 0 &&
+         initial_backoff_ms_ >= 0 &&
+         additional_constant_ms_ >= 0 &&
+         multiply_factor_ > 0 &&
+         jitter_factor_ >= 0 &&
+         maximum_backoff_ms_ >= 0);
+
+  Initialize();
+}
+
+RequestThrottlerEntry::~RequestThrottlerEntry() {
+}
+
+void RequestThrottlerEntry::Initialize() {
+  // Since this method is called by the constructors, GetTimeNow() (a virtual
+  // method) is not used.
+  exponential_backoff_release_time_ = base::TimeTicks::Now();
+  failure_count_ = 0;
+  tracking_exponential_backoff_ = false;
+
+  old_values_.exponential_backoff_release_time =
+      exponential_backoff_release_time_;
+  old_values_.failure_count = failure_count_;
+
+  sliding_window_release_time_ = base::TimeTicks::Now();
+}
+
+bool RequestThrottlerEntry::IsDuringExponentialBackoff() const {
+  AutoLock auto_lock(lock_);
+  return exponential_backoff_release_time_ > GetTimeNow();
+}
+
+int64 RequestThrottlerEntry::GetRecommendedDelayForNextRequest() {
+  AutoLock auto_lock(lock_);
+
+  base::TimeTicks now = GetTimeNow();
+  sliding_window_release_time_ =
+      std::max(now, std::max(exponential_backoff_release_time_,

[Jói, 2010/11/12 19:14:24]

It would help the readability of the code to explain in which case the
sliding_window_release_time_ might become different (greater) than
exponential_backoff_release_time_.

Also, I wonder if there is really a need to differentiate? Should we just use
the exponential_backoff_release_time_ for both?

[yzshen, 2010/11/12 21:28:33]

If a lot of requests are successfully made in the recent time,
sliding_window_release_time_ may be greater than
exponential_backoff_release_time_.

I have added a comment.
Yes, we need the two separate variables.
Please consider the following situation:
If recently there are a lot of (successful) requests, the
sliding_window_release_time_ is pushed forward and probably greater than
exponential_backoff_release_time_.
If we merge sliding_window_release_time_ into exponential_backoff_release_time_.
Since the network level will reject requests based on
exponential_backoff_release_time_, we actually enforce the sliding window rule
at the network level.

+                             sliding_window_release_time_));
+
+  int64 result = (sliding_window_release_time_ - now).InMillisecondsRoundedUp();
+
+  DCHECK(send_log_.empty() ||
+         sliding_window_release_time_ >= send_log_.back());
+
+  // Log the new send event.
+  send_log_.push(sliding_window_release_time_);

[Jói, 2010/11/12 19:14:24]

It seems strange that send_log_ is only updated in
GetRecommendedDelayForNextRequest, instead of updating it on every
UpdateWithResponse, it seems the latter would give you much better coverage?

[yzshen, 2010/11/12 21:28:33]

I thought about this problem before I did it this way.

If we update the send_log_ by UpdateWithResponse (or as my previous patch, by
NotifyRequestStart on the network level), it has better coverage, but it is too
late. Consider the following scenario:
1) [time_1] we know from UpdateWithResponse that according to the sliding window
rule, it is better to make request after time_3.
2) [time_2] 100 upper layer modules would like to make request to the same URL,
and thus call GetRecommendedDelayForNextRequest, they all get time_3.
As a result, 100 tasks are posted to start at time_3.
3) [time_3] a lot of requests are started around this time.

To avoid this problem, we need to reserve a sending time for each request at
time_2, and spread the requests over time properly.

+
+  base::TimeDelta sliding_window_period = base::TimeDelta::FromMilliseconds(

[Jói, 2010/11/12 19:14:24]

can we make the constant a base::TimeDelta instead of an integer number of
milliseconds, to avoid the calculation every time?

[yzshen, 2010/11/17 07:31:43]

Thanks! Done.

+      sliding_window_period_ms_);
+
+  // Drop the out-of-date events in the event list.
+  // We don't need to worry that the queue may become empty during this
+  // operation, since the last element is sliding_window_release_time_.
+  while ((send_log_.front() + sliding_window_period <=
+          sliding_window_release_time_) ||
+         send_log_.size() > static_cast<unsigned>(max_send_threshold_)) {
+    send_log_.pop();
+  }
+
+  // Check if there are too many send events in recent time.
+  if (send_log_.size() == static_cast<unsigned>(max_send_threshold_))
+    sliding_window_release_time_ = send_log_.front() + sliding_window_period;
+
+  return result;
+}
+
+void RequestThrottlerEntry::UpdateWithResponse(
+    const RequestThrottlerHeaderInterface* response) {
+  AutoLock auto_lock(lock_);
+
+  SaveState();
+  if (response->GetResponseCode() >= 500) {
+    failure_count_++;
+    exponential_backoff_release_time_ =
+        CalculateExponentialBackoffReleaseTime();
+    tracking_exponential_backoff_ = true;
+  } else {
+    // We slowly decay the number of times delayed instead of resetting it to 0
+    // in order to stay stable if we received lots of requests with
+    // malformed bodies at the same time.
+    if (failure_count_ > 0)
+      failure_count_--;
+
+    tracking_exponential_backoff_ = false;
+
+    // The reason why we are not just cutting the release time to GetTimeNow()
+    // is on the one hand, it would unset delay put by our custom retry-after
+    // header and on the other we would like to push every request up to our
+    // "horizon" when dealing with multiple in-flight requests. Ex: If we send
+    // three requests and we receive 2 failures and 1 success. The success that
+    // follows those failures will not reset the release time, further requests
+    // will then need to wait the delay caused by the 2 failures.
+    exponential_backoff_release_time_ = std::max(
+        GetTimeNow(), exponential_backoff_release_time_);
+
+    std::string retry_header = response->GetNormalizedValue(kRetryHeaderName);
+    if (!retry_header.empty())
+      HandleCustomRetryAfter(retry_header);
+  }
+}
+
+bool RequestThrottlerEntry::IsEntryOutdated() const {
+  AutoLock auto_lock(lock_);
+
+  if (entry_lifetime_ms_ == -1)
+    return false;
+
+  base::TimeTicks now = GetTimeNow();
+
+  // If there are send events in the sliding window period, we still need this
+  // entry.
+  base::TimeDelta sliding_window_period = base::TimeDelta::FromMilliseconds(
+      sliding_window_period_ms_);
+  if (send_log_.size() > 0 &&
+      send_log_.back() + sliding_window_period > now) {
+    return false;
+  }
+
+  int64 unused_since_ms =
+      (now - exponential_backoff_release_time_).InMilliseconds();
+
+  // Release time is further than now, we are managing it.
+  if (unused_since_ms < 0)
+    return false;
+
+  // tracking_exponential_backoff_ is true indicates that the latest one or
+  // more requests encountered server errors or had malformed response bodies.
+  // In that case, we are doing exponential back-off and should not collect the
+  // entry unless it hasn't been used for longer than the maximum allowed
+  // back-off.
+  if (tracking_exponential_backoff_)
+    return unused_since_ms > std::max(maximum_backoff_ms_, entry_lifetime_ms_);
+
+  // Otherwise, consider the entry is outdated if it hasn't been used for the
+  // specified lifetime period.
+  return unused_since_ms > entry_lifetime_ms_;
+}
+
+void RequestThrottlerEntry::ReceivedContentWasMalformed() {
+  AutoLock auto_lock(lock_);
+
+  // We should never revert to less back-off or else an attacker could put a
+  // malformed body in cache and replay it to decrease delay.
+  failure_count_ =
+      std::max(old_values_.failure_count, failure_count_);
+  failure_count_++;
+  tracking_exponential_backoff_ = true;
+  exponential_backoff_release_time_ =
+      std::max(CalculateExponentialBackoffReleaseTime(),
+               old_values_.exponential_backoff_release_time);
+}
+
+base::TimeTicks
+    RequestThrottlerEntry::CalculateExponentialBackoffReleaseTime() {
+  lock_.AssertAcquired();
+
+  double delay = initial_backoff_ms_;
+  delay *= pow(multiply_factor_, failure_count_);
+  delay += additional_constant_ms_;
+  delay -= base::RandDouble() * jitter_factor_ * delay;
+
+  // Ensure that we do not exceed maximum delay.
+  int64 delay_int = static_cast<int64>(delay + 0.5);
+  delay_int = std::min(delay_int, static_cast<int64>(maximum_backoff_ms_));
+
+  return std::max(GetTimeNow() + base::TimeDelta::FromMilliseconds(delay_int),
+                  exponential_backoff_release_time_);
+}
+
+base::TimeTicks RequestThrottlerEntry::GetTimeNow() const {
+  return base::TimeTicks::Now();
+}
+
+void RequestThrottlerEntry::HandleCustomRetryAfter(
+    const std::string& header_value) {
+  lock_.AssertAcquired();
+
+  // Input parameter is the number of seconds to wait in a floating point value.
+  double time_in_sec = 0;
+  bool conversion_is_ok = base::StringToDouble(header_value, &time_in_sec);
+
+  // Conversion of custom retry-after header value failed.
+  if (!conversion_is_ok)
+    return;
+
+  // We must use an int value later so we transform this in milliseconds.
+  int64 value_ms = static_cast<int64>(0.5 + time_in_sec * 1000);
+
+  if (maximum_backoff_ms_ < value_ms || value_ms < 0)
+    return;
+
+  exponential_backoff_release_time_ = std::max(
+      (GetTimeNow() + base::TimeDelta::FromMilliseconds(value_ms)),
+      exponential_backoff_release_time_);
+}
+
+void RequestThrottlerEntry::SaveState() {
+  lock_.AssertAcquired();
+
+  old_values_.exponential_backoff_release_time =
+      exponential_backoff_release_time_;
+  old_values_.failure_count = failure_count_;
+}