1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
|
// Copyright 2008, Google Inc.
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
// * Redistributions of source code must retain the above copyright
// notice, this list of conditions and the following disclaimer.
// * Redistributions in binary form must reproduce the above
// copyright notice, this list of conditions and the following disclaimer
// in the documentation and/or other materials provided with the
// distribution.
// * Neither the name of Google Inc. nor the names of its
// contributors may be used to endorse or promote products derived from
// this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
//
// This file implements backoff in the suggest system so that we don't
// DOS the Suggest servers when using URLFetcher.
#ifndef CHROME_BROWSER_URL_FETCHER_PROTECT_H__
#define CHROME_BROWSER_URL_FETCHER_PROTECT_H__
#include <map>
#include <queue>
#include <string>
#include "base/lock.h"
#include "base/logging.h"
#include "base/scoped_ptr.h"
#include "base/time.h"
// This class is used to manage one service's rate protection. It maintains
// a queue of connection successes and failures and analyzes the requests
// over some period of time, in order to deduce the backoff time of every
// request.
// The backoff algorithm consists of two parts. Firstly, avoid too many
// send events in a sliding window. That will prevent traffic overload.
// Secondly, exponential backoff is used when receiving an error message
// from server. Exponential backoff period is calculated using the following
// formula:
//
// initial backoff time (the first time to receive error)
// backoff = k * current_backoff + c (the second, third, ... error)
// maximum backoff time (when backoff > maximum backoff time)
//
// where |k| is the multiplier, and |c| is the constant factor.
class ProtectEntry {
public:
enum EventType {
SEND, // request will be sent out
SUCCESS, // successful response
FAILURE // no response or error
};
ProtectEntry();
ProtectEntry(int sliding_window_period, int max_send_threshold,
int max_retries, int initial_timeout,
double multiplier, int constant_factor,
int maximum_timeout);
virtual ~ProtectEntry() { }
// When a connection event happens, log it to the queue, and recalculate
// the timeout period. It returns the backoff time, in milliseconds, that
// indicates to the sender how long should it wait before sending the request.
// If the request is allowed to be sent immediately, the backoff time is 0.
int UpdateBackoff(EventType event_type);
// Returns the max retries allowed.
int max_retries() const {
return max_retries_;
}
private:
// When a request comes, calculate the release time for it.
// Returns the backoff time before sending.
TimeDelta AntiOverload();
// Resets backoff when service is ok.
// Returns the backoff time before sending.
TimeDelta ResetBackoff();
// Calculates new backoff when encountering a failure.
// Returns the backoff time before sending.
TimeDelta IncreaseBackoff();
// Default parameters. Time is in milliseconds.
static const int kDefaultSlidingWindowPeriod;
static const int kDefaultMaxSendThreshold;
static const int kDefaultMaxRetries;
static const int kDefaultInitialTimeout;
static const double kDefaultMultiplier;
static const int kDefaultConstantFactor;
static const int kDefaultMaximumTimeout;
// time to consider events when checking backoff
int sliding_window_period_;
// maximum number of requests allowed in sliding window period
int max_send_threshold_;
// maximum retris allowed
int max_retries_;
// initial timeout on first failure
int initial_timeout_;
// factor by which to multiply on exponential backoff (e.g., 2.0)
double multiplier_;
// constant time term to add to each attempt
int constant_factor_;
// maximum amount of time between requests
int maximum_timeout_;
// current exponential backoff period
int timeout_period_;
// time that protection is scheduled to end
TimeTicks release_time_;
// Sets up a lock to ensure thread safe.
Lock lock_;
// A list of the recent send events. We ues them to decide whether
// there are too many requests sent in sliding window.
std::queue<TimeTicks> send_log_;
DISALLOW_EVIL_CONSTRUCTORS(ProtectEntry);
};
// This singleton class is used to manage all protect entries.
// Now we use the host name as service id.
class ProtectManager {
public:
~ProtectManager();
// Returns the global instance of this class.
static ProtectManager* GetInstance();
// Registers a new entry in this service. If the entry already exists,
// just returns it.
ProtectEntry* Register(std::string id);
// Always registers the entry even when it exists.
ProtectEntry* Register(std::string id, ProtectEntry* entry);
private:
ProtectManager() { }
typedef std::map<const std::string, ProtectEntry*> ProtectService;
static Lock lock_;
static scoped_ptr<ProtectManager> protect_manager_;
ProtectService services_;
DISALLOW_EVIL_CONSTRUCTORS(ProtectManager);
};
#endif // CHROME_BROWSER_URL_FETCHER_PROTECT_H__
|
