net/url_request/url_request_throttler_entry.cc

   1 // Copyright (c) 2010 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "net/url_request/url_request_throttler_entry.h"
   6
   7 #include <cmath>
   8
   9 #include "base/logging.h"
  10 #include "base/rand_util.h"
  11 #include "base/string_number_conversions.h"
  12 #include "net/url_request/url_request_throttler_header_interface.h"
  13
  14 namespace net {
  15
  16 const int URLRequestThrottlerEntry::kDefaultSlidingWindowPeriodMs = 2000;
  17 const int URLRequestThrottlerEntry::kDefaultMaxSendThreshold = 20;
  18 const int URLRequestThrottlerEntry::kDefaultInitialBackoffMs = 700;
  19 const int URLRequestThrottlerEntry::kDefaultAdditionalConstantMs = 100;
  20 const double URLRequestThrottlerEntry::kDefaultMultiplyFactor = 1.4;
  21 const double URLRequestThrottlerEntry::kDefaultJitterFactor = 0.4;
  22 const int URLRequestThrottlerEntry::kDefaultMaximumBackoffMs = 60 * 60 * 1000;
  23 const int URLRequestThrottlerEntry::kDefaultEntryLifetimeMs = 120000;
  24 const char URLRequestThrottlerEntry::kRetryHeaderName[] = "X-Retry-After";
  25
  26 URLRequestThrottlerEntry::URLRequestThrottlerEntry()
  27     : sliding_window_period_(
  28           base::TimeDelta::FromMilliseconds(kDefaultSlidingWindowPeriodMs)),
  29       max_send_threshold_(kDefaultMaxSendThreshold),
  30       initial_backoff_ms_(kDefaultInitialBackoffMs),
  31       additional_constant_ms_(kDefaultAdditionalConstantMs),
  32       multiply_factor_(kDefaultMultiplyFactor),
  33       jitter_factor_(kDefaultJitterFactor),
  34       maximum_backoff_ms_(kDefaultMaximumBackoffMs),
  35       entry_lifetime_ms_(kDefaultEntryLifetimeMs) {
  36   Initialize();
  37 }
  38
  39 URLRequestThrottlerEntry::URLRequestThrottlerEntry(
  40     int sliding_window_period_ms,
  41     int max_send_threshold,
  42     int initial_backoff_ms,
  43     int additional_constant_ms,
  44     double multiply_factor,
  45     double jitter_factor,
  46     int maximum_backoff_ms)
  47     : sliding_window_period_(
  48           base::TimeDelta::FromMilliseconds(sliding_window_period_ms)),
  49       max_send_threshold_(max_send_threshold),
  50       initial_backoff_ms_(initial_backoff_ms),
  51       additional_constant_ms_(additional_constant_ms),
  52       multiply_factor_(multiply_factor),
  53       jitter_factor_(jitter_factor),
  54       maximum_backoff_ms_(maximum_backoff_ms),
  55       entry_lifetime_ms_(-1) {
  56   DCHECK_GT(sliding_window_period_ms, 0);
  57   DCHECK_GT(max_send_threshold_, 0);
  58   DCHECK_GE(initial_backoff_ms_, 0);
  59   DCHECK_GE(additional_constant_ms_, 0);
  60   DCHECK_GT(multiply_factor_, 0);
  61   DCHECK_GE(jitter_factor_, 0);
  62   DCHECK_LT(jitter_factor_, 1);
  63   DCHECK_GE(maximum_backoff_ms_, 0);
  64
  65   Initialize();
  66 }
  67
  68 bool URLRequestThrottlerEntry::IsEntryOutdated() const {
  69   if (entry_lifetime_ms_ == -1)
  70     return false;
  71
  72   base::TimeTicks now = GetTimeNow();
  73
  74   // If there are send events in the sliding window period, we still need this
  75   // entry.
  76   if (send_log_.size() > 0 &&
  77       send_log_.back() + sliding_window_period_ > now) {
  78     return false;
  79   }
  80
  81   int64 unused_since_ms =
  82       (now - exponential_backoff_release_time_).InMilliseconds();
  83
  84   // Release time is further than now, we are managing it.
  85   if (unused_since_ms < 0)
  86     return false;
  87
  88   // latest_response_was_failure_ is true indicates that the latest one or
  89   // more requests encountered server errors or had malformed response bodies.
  90   // In that case, we don't want to collect the entry unless it hasn't been used
  91   // for longer than the maximum allowed back-off.
  92   if (latest_response_was_failure_)
  93     return unused_since_ms > std::max(maximum_backoff_ms_, entry_lifetime_ms_);
  94
  95   // Otherwise, consider the entry is outdated if it hasn't been used for the
  96   // specified lifetime period.
  97   return unused_since_ms > entry_lifetime_ms_;
  98 }
  99
 100 bool URLRequestThrottlerEntry::IsDuringExponentialBackoff() const {
 101   return exponential_backoff_release_time_ > GetTimeNow();
 102 }
 103
 104 int64 URLRequestThrottlerEntry::ReserveSendingTimeForNextRequest(
 105     const base::TimeTicks& earliest_time) {
 106   base::TimeTicks now = GetTimeNow();
 107   // If a lot of requests were successfully made recently,
 108   // sliding_window_release_time_ may be greater than
 109   // exponential_backoff_release_time_.
 110   base::TimeTicks recommended_sending_time =
 111       std::max(std::max(now, earliest_time),
 112                std::max(exponential_backoff_release_time_,
 113                         sliding_window_release_time_));
 114
 115   DCHECK(send_log_.empty() ||
 116          recommended_sending_time >= send_log_.back());
 117   // Log the new send event.
 118   send_log_.push(recommended_sending_time);
 119
 120   sliding_window_release_time_ = recommended_sending_time;
 121
 122   // Drop the out-of-date events in the event list.
 123   // We don't need to worry that the queue may become empty during this
 124   // operation, since the last element is sliding_window_release_time_.
 125   while ((send_log_.front() + sliding_window_period_ <=
 126           sliding_window_release_time_) ||
 127          send_log_.size() > static_cast<unsigned>(max_send_threshold_)) {
 128     send_log_.pop();
 129   }
 130
 131   // Check if there are too many send events in recent time.
 132   if (send_log_.size() == static_cast<unsigned>(max_send_threshold_))
 133     sliding_window_release_time_ = send_log_.front() + sliding_window_period_;
 134
 135   return (recommended_sending_time - now).InMillisecondsRoundedUp();
 136 }
 137
 138 base::TimeTicks
 139     URLRequestThrottlerEntry::GetExponentialBackoffReleaseTime() const {
 140   return exponential_backoff_release_time_;
 141 }
 142
 143 void URLRequestThrottlerEntry::UpdateWithResponse(
 144     const URLRequestThrottlerHeaderInterface* response) {
 145   if (response->GetResponseCode() >= 500) {
 146     failure_count_++;
 147     latest_response_was_failure_ = true;
 148     exponential_backoff_release_time_ =
 149         CalculateExponentialBackoffReleaseTime();
 150   } else {
 151     // We slowly decay the number of times delayed instead of resetting it to 0
 152     // in order to stay stable if we received lots of requests with
 153     // malformed bodies at the same time.
 154     if (failure_count_ > 0)
 155       failure_count_--;
 156
 157     latest_response_was_failure_ = false;
 158
 159     // The reason why we are not just cutting the release time to GetTimeNow()
 160     // is on the one hand, it would unset delay put by our custom retry-after
 161     // header and on the other we would like to push every request up to our
 162     // "horizon" when dealing with multiple in-flight requests. Ex: If we send
 163     // three requests and we receive 2 failures and 1 success. The success that
 164     // follows those failures will not reset the release time, further requests
 165     // will then need to wait the delay caused by the 2 failures.
 166     exponential_backoff_release_time_ = std::max(
 167         GetTimeNow(), exponential_backoff_release_time_);
 168
 169     std::string retry_header = response->GetNormalizedValue(kRetryHeaderName);
 170     if (!retry_header.empty())
 171       HandleCustomRetryAfter(retry_header);
 172   }
 173 }
 174
 175 void URLRequestThrottlerEntry::ReceivedContentWasMalformed() {
 176   // For any response that is marked as malformed now, we have probably
 177   // considered it as a success when receiving it and decreased the failure
 178   // count by 1. As a result, we increase the failure count by 2 here to undo
 179   // the effect and record a failure.
 180   //
 181   // Please note that this may lead to a larger failure count than expected,
 182   // because we don't decrease the failure count for successful responses when
 183   // it has already reached 0.
 184   failure_count_ += 2;
 185   latest_response_was_failure_ = true;
 186   exponential_backoff_release_time_ = CalculateExponentialBackoffReleaseTime();
 187 }
 188
 189 URLRequestThrottlerEntry::~URLRequestThrottlerEntry() {
 190 }
 191
 192 void URLRequestThrottlerEntry::Initialize() {
 193   // Since this method is called by the constructors, GetTimeNow() (a virtual
 194   // method) is not used.
 195   exponential_backoff_release_time_ = base::TimeTicks::Now();
 196   failure_count_ = 0;
 197   latest_response_was_failure_ = false;
 198
 199   sliding_window_release_time_ = base::TimeTicks::Now();
 200 }
 201
 202 base::TimeTicks
 203     URLRequestThrottlerEntry::CalculateExponentialBackoffReleaseTime() {
 204   double delay = initial_backoff_ms_;
 205   delay *= pow(multiply_factor_, failure_count_);
 206   delay += additional_constant_ms_;
 207   delay -= base::RandDouble() * jitter_factor_ * delay;
 208
 209   // Ensure that we do not exceed maximum delay.
 210   int64 delay_int = static_cast<int64>(delay + 0.5);
 211   delay_int = std::min(delay_int, static_cast<int64>(maximum_backoff_ms_));
 212
 213   return std::max(GetTimeNow() + base::TimeDelta::FromMilliseconds(delay_int),
 214                   exponential_backoff_release_time_);
 215 }
 216
 217 base::TimeTicks URLRequestThrottlerEntry::GetTimeNow() const {
 218   return base::TimeTicks::Now();
 219 }
 220
 221 void URLRequestThrottlerEntry::HandleCustomRetryAfter(
 222     const std::string& header_value) {
 223   // Input parameter is the number of seconds to wait in a floating point value.
 224   double time_in_sec = 0;
 225   bool conversion_is_ok = base::StringToDouble(header_value, &time_in_sec);
 226
 227   // Conversion of custom retry-after header value failed.
 228   if (!conversion_is_ok)
 229     return;
 230
 231   // We must use an int value later so we transform this in milliseconds.
 232   int64 value_ms = static_cast<int64>(0.5 + time_in_sec * 1000);
 233
 234   if (maximum_backoff_ms_ < value_ms || value_ms < 0)
 235     return;
 236
 237   exponential_backoff_release_time_ = std::max(
 238       (GetTimeNow() + base::TimeDelta::FromMilliseconds(value_ms)),
 239       exponential_backoff_release_time_);
 240 }
 241
 242 }  // namespace net