CSE Roadmap

Core tier · about 4 hours · 6 parts

Part 1 of 6 · 1 min read

Why this page comes second in Level 7

In this module you will

  • Say what a rate limiter must do and what it must return to the caller.
  • Code the token bucket, fixed window, sliding window log and sliding window counter.
  • Show the burst at the edge of a fixed window, and how the sliding methods fix it.
  • Keep one limiter per client key, and make each limiter thread-safe.
  • Choose an algorithm for a stated need, and say what changes when the limiter is shared by many servers.

A rate limiter is a favourite in both high-level and low-level rounds. The high-level version asks where to put it and how to share state between servers. This page is the low-level version: the classes and the algorithms. It is the code that the high-level answer assumes. The source for the algorithms is the "System Design Interview" book, chapter 4. The class design and tests follow the method of Level 0, module 4. The Java code was compiled and run before it was written here. Numbers marked "made up" only show the idea.