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

net/request_throttler/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/request_throttler/request_throttler_entry.h"
+
+#include <cmath>
+
+#include "base/logging.h"
+#include "base/rand_util.h"
+#include "base/string_number_conversions.h"
+#include "net/request_throttler/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() {
+  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_,
+                             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_);
+
+  base::TimeDelta sliding_window_period = base::TimeDelta::FromMilliseconds(
+      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_);

[eroman, 2010/11/11 17:54:21]

There is a lot of locking in this CL; I guess that is because the "request
throttling manager" is a global.

We really try to avoid globals/singletons. Rather, can you put this dependency
into the URLRequestContext, and then it does not need to be threadsafe (since by
definition URLRequestContexts are only used one thread).

[yzshen, 2010/11/11 22:17:05]

One thing that asks for all the locking is that upper layer modules (say,
URLFetcher) need to call methods such as RegisterRequestUrl() or
GetRecommendedDelayForNextRequest() on other threads:

scoped_refptr<RequestThrottlerEntryInterface> entry =
request_throttler_manager_->RegisterRequestUrl(original_url_);
io_message_loop_proxy_->PostDelayedTask(
      FROM_HERE,
      NewRunnableMethod(this, &Core::StartURLRequest),
      entry->GetRecommendedDelayForNextRequest());

What do you think?

[eroman, 2010/11/11 23:57:14]

I see. Is URLFetcher the only such consumer? If so, we could still support it by
having it only access the throttling entry from the IO thread. URLFetcher is
already posting tasks to the IO loop in order to call URLRequest, so we would
just need to shift the backoff checks there as well.

+
+  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;
+
+  // There are two cases. First one, when the entry is currently being managed
+  // and should not be collected unless it is older than the maximum allowed
+  // back-off. The other one, when the entry is outdated, unmanaged and should
+  // be collected.
+  if (tracking_exponential_backoff_)
+    return unused_since_ms > std::max(maximum_backoff_ms_, entry_lifetime_ms_);
+
+  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_;
+}