Balancing compliance with Request Throttling Limits with maximum allowable throughput in our applications and libraries with any reliability requires self-throttling.
This post is meant to be a repo for Stack Exchange API compliant request throttle implementations.
This is the throttle implementation used by Soapi.CS. It is compatible with all .net platforms (desktop/silverlight/phone/mono)
It has proven to provide maximum practical API throughput while complying both with the letter of the law as well as compensating for incidental vagaries. I would go so far as to characterize it as bullet-proof.
As a demonstration, I pulled all of Jon Skeet's, questions/answers/rep changes/timelines, on all Stack Exchange sites, in less than 3 minutes (560 requests), using the simple code listed after the throttle. Here is the log.
//
// Project: SOAPI
// http://soapics.codeplex.com
// https://stackapps.com/questions/386
//
// Copyright 2010, Sky Sanders
// Licensed under the GPL Version 2 license.
// http://soapi.codeplex.com/license
//
#region
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Net;
using System.Threading;
#endregion
namespace Soapi.Net
{
/// <summary>
/// This is a fully configurable, thread-safe web request throttle that fully complies with the
/// published usage guidelines. In addition to compliance with the letter of the law, testing
/// has exposed further limitations that are compensated. See code comments for more detail.
///
/// Simply route all WebRequest.Create calls through RequestThrottle.Instance.Create();
///
/// Upon completion of an issued request, regardless of status, you must call
/// RequestThrottle.Instance.Complete() to decrement the outstanding request count.
///
/// NOTE: you can use this as a global throttle using WebRequest.RegisterPrefix
/// http://msdn.microsoft.com/en-us/library/system.net.webrequest.registerprefix.aspx
/// but this is not a viable option for silverlight so in Soapi, where requests
/// are created in one place, we just call it explicitly.
/// </summary>
/// <remarks>
/// Throttling conversation here: https://stackapps.com/questions/1143/request-throttling-limits
/// </remarks>
public sealed class RequestThrottle // : IWebRequestCreate
{
#region Fields
private int _outstandingRequests;
private readonly Queue<DateTime> _requestTimes = new Queue<DateTime>();
#endregion
#region Constructors
private RequestThrottle()
{
ThrottleWindowTime = new TimeSpan(0, 0, 0, 5);
ThrottleWindowCount = 30;
MaxPendingRequests = 15;
}
#endregion
#region Properties
public static RequestThrottle Instance
{
get { return Nested.instance; }
}
/// <summary>
/// The maximum number of allowed pending request.
///
/// The throttle window will keep us in compliance with the
/// letter of the law, but testing has shown that a large
/// number of outstanding requests result in a cascade of
/// (500) errors that does not stop.
///
/// So we will block while there are > MaxPendingRequests
/// regardless of throttle window.
///
/// Defaults to 15 which has proven to be reliable.
/// </summary>
public int MaxPendingRequests { get; set; }
/// <summary>
/// If you are interested in monitoring
/// </summary>
public int OutstandingRequests
{
get { return _outstandingRequests; }
}
/// <summary>
/// The quantitive portion (xxx) of the of 30 requests per 5 seconds
/// Defaults to published guidelines of 5 seconds
/// </summary>
public int ThrottleWindowCount { get; set; }
/// <summary>
/// The temporal portion (yyy) of the of 30 requests per 5 seconds
/// Defaults to the published guidelines of 30
/// </summary>
public TimeSpan ThrottleWindowTime { get; set; }
#endregion
#region Public Methods
/// <summary>
/// This decrements the outstanding request count.
///
/// This MUST MUST MUST be called when a request has
/// completed regardless of status.
///
/// If a request fails, it may be wise to delay calling
/// this, e.g. cool down, for a few seconds, before
/// reissuing the request.
/// </summary>
public void Complete()
{
_outstandingRequests--;
}
/// <summary>
/// Create a WebRequest. This method will block if too many
/// outstanding requests are pending or the throttle window
/// threshold has been reached.
/// </summary>
/// <param name = "uri"></param>
/// <returns></returns>
public WebRequest Create(Uri uri)
{
lock (typeof(ThrottleLock))
{
// note: we could use a list of WeakReferences and
// may do so at a later date, but for now, this
// works just fine as long as you call .Complete
_outstandingRequests++;
while (_outstandingRequests > MaxPendingRequests)
{
using (var throttleGate = new AutoResetEvent(false))
{
throttleGate.WaitOne(100);
}
}
if (_requestTimes.Count == ThrottleWindowCount)
{
// pull the earliest request of the bottom
DateTime tail = _requestTimes.Dequeue();
// calculate the interval between now (head) and tail
// to determine if we need to chill out for a few millisecons
TimeSpan waitTime = (ThrottleWindowTime - (DateTime.Now - tail));
if (waitTime.TotalMilliseconds > 0)
{
#if !SILVERLIGHT
Trace.WriteLine("waiting:\t" + waitTime + "\t" + uri.AbsoluteUri);
#endif
using (var throttleGate = new AutoResetEvent(false))
{
throttleGate.WaitOne(waitTime);
}
}
}
// good to go.
_requestTimes.Enqueue(DateTime.Now);
return WebRequest.Create(uri);
}
}
/// <summary>
/// Create a WebRequest. This method will block if too many
/// outstanding requests are pending or the throttle window
/// threshold has been reached.
/// </summary>
/// <param name = "url"></param>
/// <returns></returns>
public WebRequest Create(string url)
{
return Create(new Uri(url));
}
#endregion
/// <summary>
/// lock handle
/// </summary>
private class ThrottleLock
{
}
#region Singleton Plubming
// the skeet singleton implementation
// http://www.yoda.arachsys.com/csharp/singleton.html
// ReSharper disable ClassNeverInstantiated.Local
class Nested
// ReSharper restore ClassNeverInstantiated.Local
{
// ReSharper disable EmptyConstructor
// Explicit static constructor to tell C# compiler
// not to mark type as beforefieldinit
static Nested()
// ReSharper restore EmptyConstructor
{
}
internal static readonly RequestThrottle instance = new RequestThrottle();
}
#endregion
}
}
Simple app, using Soapi.CS that will gather all data for a user on all SE API sites. Simply supply an endpoint and user id to use as reference.
Useful as a throttle test.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Threading;
using Soapi;
using Soapi.Domain;
namespace Samples
{
public class AllMyStuff
{
private const string ApiKey = "your-key-here";
private readonly ApiContext Context;
private readonly List<UserData> Users;
public AllMyStuff(string endpoint, int userId)
{
Context = new ApiContext(ApiKey);
Context.Options.LazyLoadingEnabled(true);
Context.Initialize(false);
Users = Context.Sites.First(s => s.ApiEndpoint.StartsWith(endpoint))
.User(userId).Associated.Select(u => new UserData(u)).ToList();
var initEvent = new AutoResetEvent(false);
foreach (var item in Users)
{
UserData userData = item;
ThreadPool.QueueUserWorkItem(o =>
{
User account = userData.User;
userData.Questions = account.Questions
.PageCount(-1)
.FromDate(new DateTime(1980, 1, 1))
.ToDate(new DateTime(2020, 1, 1))
.ToList();
userData.Answers = account.Answers
.PageCount(-1)
.FromDate(new DateTime(1980, 1, 1))
.ToDate(new DateTime(2020, 1, 1))
.ToList();
userData.Reputation = account
.RepChanges
.PageCount(-1)
.FromDate(new DateTime(1980, 1, 1))
.ToDate(new DateTime(2020, 1, 1))
.ToList();
userData.Timeline = account
.Timeline
.PageCount(-1)
.FromDate(new DateTime(1980, 1, 1))
.ToDate(new DateTime(2020,1, 1))
.ToList();
userData.Initialized = true;
lock (Users)
if (Users.All(u => u.Initialized))
initEvent.Set();
});
}
initEvent.WaitOne();
}
}
public class UserData
{
public UserData(User user)
{
User = user;
ApiEndpoint = user.Site.ApiEndpoint;
}
public List<Answer> Answers { get; set; }
public string ApiEndpoint { get; set; }
public bool Initialized { get; set; }
public List<Question> Questions { get; set; }
public List<RepChange> Reputation { get; set; }
public List<UserTimeline> Timeline { get; set; }
public User User { get; set; }
}
}
This is a governed sliding window throttled queue that conforms to the published usage guidelines regarding request rate.
It works by executing queued callbacks at a nominal rate.
Similar to the C# version, but without threading.
It provides:
Usage:
// create a common Throttle
window.RequestThrottle = new Throttle(5000,30,15);
// route every request through the throttle
RequestThrottle.enqueue(function(){
/* do something*/
// but NO MATTER WHAT you need to signal when complete
// regardless of state, so get your exception handling hat on.
RequestThrottle.signal();
});
Throttle.js
Throttle = function(throttleWindowTime, throttleWindowCount, maxActiveRequests) {
/// <summary>
/// The purpose of Throttle is to queue requests in the interest of
/// preventing inadvertant DOS attacks.
///
/// This throttle is intended to work with a sliding window and a governor.
///
/// The criteria are - X requests per Y seconds while < z requests are pending.
/// where X: throttleWindowCount
/// Y: throttleWindowTime
/// X: maxActiveRequests
///
/// </summary>
/// <param name="throttleWindowTime" type="Number">The amount of time, in ms,
/// that defines the throttle window.<param>
/// <param name="throttleWindowCount" type="Number">The number of requests
/// allowed in any throttle window<param>
/// <param name="maxActiveRequests" type="Number">The maximum allowed number
/// of active request<param>
/// <remarks>
/// Not sure why I care anymore, but it just seems the thing to do.
///
/// If you have another idea, better or otherwise, please share.
/// </remarks>
var times = new Queue(),
requests = new Queue(),
active = 0,
windowTime = throttleWindowTime,
windowCount = throttleWindowCount,
maxActive = maxActiveRequests,
timer = false,
that = this;
var lastRequestTime = 0; // for debugging
this.processQueue = function() {
/// <summary>
/// there are several criteria that need to be met in order
/// for a request to be executed:
///
/// 1 - that the active request count < max allowed active count
///
/// 2 - that the difference in time between Now and the
/// throttleWindowCount-nth request is greater than
/// throttleWindowTime.
/// </summary>
if (requests.count() === 0 || (active === maxActive)) {
return;
};
var head = new Date().getTime();
var queueCount = times.count()
if (queueCount >= windowCount) {
// check the difference
var tail = times.peek() || 0;
if (head - tail < windowTime) {
// not time yet
return;
};
// we are a go, snap the tail off
times.dequeue();
}
// Metrics: the interval since last request
//var interval = head - lastRequestTime;
lastRequestTime = head;
var request = requests.dequeue();
if (typeof request == 'function') {
active++;
times.enqueue(head);
request();
}
};
this.signal = function() {
/// <summary>
/// This method simply decrements the active request count.
/// It simply MUST be called once for each request issued
/// regardless of the final status of the request.
/// This means that you MUST NOT swallow execution errors.
/// </summary>
active = active - 1;
if (active < 0) {
throw "Request count negative.";
};
};
this.enqueue = function(callback) {
/// <summary>
/// Adds a callback to the throttle queue.
/// </summary>
/// <param name="callback" type="Function">The function to be executed in due time.<param>
requests.enqueue(callback);
};
this.clear = function() {
/// <summary>
/// Suspends processing and clears queues and counts.
/// </summary>
that.suspend();
times = new Queue();
requests = new Queue();
active = 0;
};
this.start = function(pollingInterval) {
/// <summary>
/// Resumes processing of the throttle queue at the specified
/// polling interval;
///
/// If the throttle is running, calls to this method are ignored.
/// </summary>
/// <param name="" type="Number">The desired polling interval in ms</param>
if (!timer) {
timer = window
.setInterval(that.processQueue, pollingInterval);
};
};
this.suspend = function() {
/// <summary>
/// Suspends processing of the throttle queue.
///
/// If the throttle is not running, calls to this method are ignored.
/// </summary>
if (timer) {
window.clearInterval(timer);
timer = false;
};
};
this.start(75);
};
function Queue() {
this._queue = [];
this._queueSpace = 0;
}
Queue.prototype = {
enqueue: function(element) {
this._queue.push(element);
},
dequeue: function() {
var element = undefined;
if (this._queue.length) {
element = this._queue[this._queueSpace];
if (++this._queueSpace * 2 >= this._queue.length) {
this._queue = this._queue.slice(this._queueSpace);
this._queueSpace = 0;
}
}
return element;
},
count: function() {
return this._queue.length - this._queueSpace;
},
peek: function() {
var element = undefined;
if (this._queue.length) element = this._queue[this._queueSpace];
return element;
}
};