Stack Apps is a question and answer site for apps, scripts, and development with the Stack Exchange API. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question

C# sliding window throttle implementation

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.

Soapi.Net.RequestThrottle

//  
//  Project: SOAPI
//  http://soapics.codeplex.com
//  http://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: http://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


    }
}

Demo

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; }
    }
}
share|improve this answer

JavaScript

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:

  • maximum throughput for isolated bursts
  • reliable execution for mass requests.

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;
    }
};
share|improve this answer

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .