Rate Limiting Algorithms

viewof config = {
  function slider(min, max, value, step, label) {
    const id = `rl-${label.replace(/\W/g, '')}`;
    const el = html`<div style="display:flex;align-items:center;gap:4px;margin:1px 0;">
      <label for="${id}" style="font-size:10px;color:#666;min-width:55px;white-space:nowrap;">${label}</label>
      <input id="${id}" type="range" min="${min}" max="${max}" value="${value}" step="${step}"
        style="flex:1;height:12px;margin:0;cursor:pointer;">
      <span style="font-size:10px;color:#888;min-width:24px;text-align:right;">${value}</span>
    </div>`;
    const inp = el.querySelector("input");
    const out = el.querySelector("span");
    inp.addEventListener("input", () => { out.textContent = inp.value; });
    el._input = inp;
    return el;
  }

  const tb1 = slider(5, 80, 30, 1, "Fill Rate");
  const tb2 = slider(5, 100, 20, 1, "Capacity");
  const sw1 = slider(0.5, 10, 2, 0.5, "Window");
  const sw2 = slider(10, 200, 60, 5, "Max Reqs");
  const lb1 = slider(5, 80, 30, 1, "Drain Rate");

  const form = html`<div style="display:grid;grid-template-columns:1fr 1fr 1fr;gap:6px 12px;margin-bottom:4px;">
    <div>
      <div style="font-weight:600;color:#10b981;font-size:11px;margin-bottom:2px;">Token Bucket</div>
      ${tb1}${tb2}
    </div>
    <div>
      <div style="font-weight:600;color:#f59e0b;font-size:11px;margin-bottom:2px;">Sliding Window</div>
      ${sw1}${sw2}
    </div>
    <div>
      <div style="font-weight:600;color:#ef4444;font-size:11px;margin-bottom:2px;">Leaky Bucket</div>
      ${lb1}
    </div>
  </div>`;

  function update() {
    form.value = {
      tbFillRate: +tb1._input.value,
      tbCapacity: +tb2._input.value,
      swWindow: +sw1._input.value,
      swLimit: +sw2._input.value,
      lbDrainRate: +lb1._input.value,
    };
    form.dispatchEvent(new Event("input", {bubbles: true}));
  }

  for (const s of [tb1, tb2, sw1, sw2, lb1])
    s._input.addEventListener("input", update);
  update();
  return form;
}

{
  const dt = 0.05;
  const duration = 30;
  const steps = Math.floor(duration / dt);

  // Generate traffic: silence, a single burst, then silence
  let times = [], input = [];
  for (let i = 0; i < steps; i++) {
    let t = i * dt;
    times.push(t);
    let rate;
    if (t < 5) rate = 0;
    else if (t < 8) rate = 80;
    else rate = 0;
    input.push(rate);
  }

  // Token Bucket: refills tokens at constant rate, spends one per request.
  // Stored tokens allow short bursts through; excess is queued and
  // released as tokens refill — no traffic is dropped.
  let tbTokens = config.tbCapacity;
  let tbQueue = 0;
  let tbOut = [];
  for (let i = 0; i < steps; i++) {
    let arriving = input[i] * dt;
    tbTokens = Math.min(config.tbCapacity, tbTokens + config.tbFillRate * dt);
    let fromQueue = Math.min(tbQueue, tbTokens);
    tbQueue -= fromQueue;
    tbTokens -= fromQueue;
    let passed = Math.min(arriving, tbTokens);
    tbTokens -= passed;
    tbQueue += (arriving - passed);
    tbOut.push((fromQueue + passed) / dt);
  }

  // Sliding Window: counts served requests in a rolling time window.
  // Serves up to the limit per window; excess is queued and released
  // as the window slides — no traffic is dropped.
  let swServed = [];
  let swQueue = 0;
  let swOut = [];
  for (let i = 0; i < steps; i++) {
    let arriving = input[i] * dt;
    let windowSteps = Math.floor(config.swWindow / dt);
    let inWindow = 0;
    for (let j = Math.max(0, i - windowSteps); j < i; j++) {
      inWindow += swServed[j];
    }
    let canServe = Math.max(0, config.swLimit - inWindow);
    let fromQueue = Math.min(swQueue, canServe);
    swQueue -= fromQueue;
    canServe -= fromQueue;
    let passed = Math.min(arriving, canServe);
    swQueue += (arriving - passed);
    let totalServed = fromQueue + passed;
    swServed.push(totalServed);
    swOut.push(totalServed / dt);
  }

  // Leaky Bucket: all traffic enters an unbounded queue that drains at
  // a constant rate — no traffic is dropped.
  let lbQueue = 0;
  let lbOut = [];
  for (let i = 0; i < steps; i++) {
    let arriving = input[i] * dt;
    lbQueue += arriving;
    let drained = Math.min(lbQueue, config.lbDrainRate * dt);
    lbQueue -= drained;
    lbOut.push(drained / dt);
  }

  // All series on a single chart
  let data = [];
  for (let i = 0; i < steps; i++) {
    data.push({t: times[i], rate: input[i], type: "Input Rate"});
    data.push({t: times[i], rate: tbOut[i], type: "Token Bucket"});
    data.push({t: times[i], rate: swOut[i], type: "Sliding Window"});
    data.push({t: times[i], rate: lbOut[i], type: "Leaky Bucket"});
  }

  return Plot.plot({
    marks: [
      Plot.areaY(data.filter(d => d.type === "Input Rate"), {
        x: "t", y: "rate", fill: "#6366f1", fillOpacity: 0.08
      }),
      Plot.lineY(data.filter(d => d.type === "Input Rate"), {
        x: "t", y: "rate", stroke: "#6366f1", strokeWidth: 2
      }),
      Plot.lineY(data.filter(d => d.type !== "Input Rate"), {
        x: "t", y: "rate", stroke: "type", strokeWidth: 2,
        strokeOpacity: 0.6, strokeDasharray: "6 3"
      }),
      Plot.ruleY([0])
    ],
    color: {
      domain: ["Input Rate", "Token Bucket", "Sliding Window", "Leaky Bucket"],
      range: ["#6366f1", "#10b981", "#f59e0b", "#ef4444"],
      legend: true
    },
    x: {label: "Time (arbitrary unit)"},
    y: {label: "Rate (arbitrary unit)", domain: [0, 100]},
    width: width,
    height: 400,
    marginLeft: 50
  });
}