Skip to content

Instantly share code, notes, and snippets.

@vprasanth
Last active June 27, 2024 01:07

Revisions

  1. vprasanth revised this gist Jun 27, 2024. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion ratelimter.js
    Original file line number Diff line number Diff line change
    @@ -2,7 +2,7 @@
    We want to build a rate limiter system for a frontend which receives requests
    at whole seconds. Assume we have all the requests over an interval of time
    represented as an array, e.g., requests = [0,0,1,1,1,2,2] The index is the
    reauest ID and the value is the time stamo.
    reauest ID and the value is the time stamp.
    Design a rate limiter that can enforce a limit of Q requests per T seconds.
    The output should return the timestamp of dropped requests as well as the
  2. vprasanth revised this gist Jun 19, 2024. 1 changed file with 1 addition and 0 deletions.
    1 change: 1 addition & 0 deletions ratelimter.js
    Original file line number Diff line number Diff line change
    @@ -40,6 +40,7 @@ function processRequests(q, t, requests) {
    if (buckets[b]) {
    buckets[b]++;
    if (buckets[b] > q) {
    // check if bucket has exceeded limit
    droppedTimes.add(requests[i]);
    droppedRequests.push(i);
    }
  3. vprasanth created this gist Jun 19, 2024.
    65 changes: 65 additions & 0 deletions ratelimter.js
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,65 @@
    /*
    We want to build a rate limiter system for a frontend which receives requests
    at whole seconds. Assume we have all the requests over an interval of time
    represented as an array, e.g., requests = [0,0,1,1,1,2,2] The index is the
    reauest ID and the value is the time stamo.
    Design a rate limiter that can enforce a limit of Q requests per T seconds.
    The output should return the timestamp of dropped requests as well as the
    request IDS.
    eg 1
    Requests = [0, 0, 1, 1, 1, 2, 2];
    For Q = 2 and T = 1 we get
    Dropped times = [1]
    Dropped requests = [4]
    eg 2
    Requests = [0, 0, 0, 1, 1, 2, 2, 2]
    For Q = 2, T = 2, we get
    Dropped times = [0, 1, 2]
    Dropped requests = [2, 3, 4, 7]
    */

    const example1 = [0, 0, 1, 1, 1, 2, 2];
    const example2 = [0, 0, 0, 1, 1, 2, 2, 2];

    function getBucket(r, t) {
    return Math.floor(r / t);
    }

    function processRequests(q, t, requests) {
    const droppedRequests = [];
    const droppedTimes = new Set();
    const buckets = {};

    for (let i = 0; i < requests.length; i++) {
    let b = getBucket(requests[i], t);
    if (buckets[b]) {
    buckets[b]++;
    if (buckets[b] > q) {
    droppedTimes.add(requests[i]);
    droppedRequests.push(i);
    }
    } else {
    buckets[b] = 1;
    }
    }

    return {
    buckets,
    droppedTimes: Array.from(droppedTimes),
    droppedRequests,
    requests,
    q,
    t,
    };
    }

    const eg1 = processRequests(2, 1, example1);
    const eg2 = processRequests(2, 2, example2);

    console.log(eg1);
    console.log(eg2);