Sliding Window Rate Limiting with Deno KV

The following post was originally published on my omg.lol Weblog on February 7th, 2024. The app that it refers to as Fissure is now known as Cistern, and a WIP version is usable at https://cistern.app. I've corrected a couple typos and tweaked the code example, which was bugged 🤪

I'm building out an ingestion API for Obsidian called Fissure, and since I want to offer it for free to a small extent, I was looking into adding a rate limiter to reduce abuse. I'm deploying on Deno Deploy, and my storage backend is Deno KV, so I felt that a sliding window rate limiter was a good choice.

There are more detailed articles on the subject, but to my understanding the algorithm works something like this:

• Define a fixed interval of time as the window period—e.g. 1 hour, 1 day
• When a request comes in, get the number of requests made in the current period and the previous period

If the time is 3:45pm and your window period is 1 hour, get the number of requests made between 2–3pm and 3–4pm.

• Calculate the percentage overlap of the previous period with the current sliding window

If, again, the time is 3:45pm and your window period is 1 hour, your current window is 2:45pm–3:45pm—from an hour ago until the current moment. Therefore, the percentage overlap of the previous period with the current window is 0.25, or 25%.

• With all that information, use the following equation to get the number of requests n with the following values:
• x is the number of requests made in current period
• y is the number of requests in the previous period
• z is the percentage overlap of the previous period with the current window

n = x + y * z

If n is greater than or equal to your maximum number of periodic requests, drop it. Here's roughly the implementation that I settled on:

import { eachHourOfInterval, subHours } from 'npm:date-fns'

const kv = await Deno.openKv()
const MAXIMUM_HOURLY_REQUESTS = 50
const HOUR_IN_MILLISECONDS = 3_600_000

async function shouldDropRequest(userId: string): Promise<boolean> {
  const windowEnd = new Date();
  const windowStart = subHours(windowEnd, 1);
  const [lastHour, currentHour] = eachHourOfInterval({
    start: windowStart,
    end: windowEnd,
  });
  const [lastPeriod, currentPeriod] = await kv.getMany<
    [Deno.KvU64, Deno.KvU64]
  >([
    ["user", userId, "period", lastHour.getTime().toString()],
    ["user", userId, "period", currentHour.getTime().toString()],
  ]);

  const currentRequests = Number(currentPeriod.value?.value ?? 0n);
  const previousRequests = Number(lastPeriod.value?.value ?? 0n);
  const previousWeight = (currentHour.getTime() - windowStart.getTime()) /
    3_600_000;

  if (currentPeriod.value === null) {
    await kv.atomic()
      .set(currentPeriod.key, new Deno.KvU64(1n), {
        expireIn: HOUR_IN_MILLISECONDS * 2,
      })
      .commit();
  } else {
    await kv.atomic()
      .sum(currentPeriod.key, 1n)
      .commit();
  }

  return Math.floor(currentRequests + (previousRequests * previousWeight)) >=
    MAXIMUM_HOURLY_REQUESTS
}