5

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.

2 Answers 2

2

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
//  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


    }
}

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; }
    }
}
1

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;
    }
};

You must log in to answer this question.

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