/Projects

Client-side token bucket rate limiter

Allow bursts, then a steady rate, so your app cannot DDoS your own API.

PracticeMachine codingTier 2 · MechanismsCreate25 minMobile systems

You will be able to: build client-side token bucket rate limiter in 25 minutes, edge cases included.

Source: Tested in tests/mobile/MobileTests.kt

Mobile engineeringAll mobile pages

All those retrying phones have to be stopped somewhere. A token bucket stops one broken client from taking the service down for everyone. Start from the basics in Day 6 →

Study with AI

25-minute round · MediumKotlin · coroutines · tested Watch as reels
Part 1 of 5

Basics

The concepts this component is built on. With these in mind, every line of the solution has a reason.

1.1Key concepts

One idea per card, in the order the solution uses them.

01Rate limiting

Capping how often something may happen, for example at most one refresh call per second.

02Token bucket

A bucket holds tokens; each call spends one; tokens refill at a steady rate up to a maximum. A full bucket allows a short burst.

03Monotonic clock

A clock that only moves forward and ignores changes to the device time. Elapsed-time maths must use it.

04Wait or reject

A limiter can make callers wait for a token or refuse them at once. User actions usually wait; background work can be dropped.

Part 2 of 5

Question

What exactly you are asked to build, what must be true when you are done, and what to ask before you start.

2.1Prompt

The question as the interviewer asks it, and the requirements to check your solution against.

Interviewer

A bug made the app call /refresh in a tight loop on a million devices. Add a client-side limiter: allow small bursts, then at most one call per second, and make callers wait instead of failing.

Requirements

  • Burst up to a capacity
  • Steady refill rate
  • Know how long to wait
  • Shared safely across callers
  • Testable with a fake clock

2.2Clarify first

Questions worth asking, and the answers this interviewer gives.

You askInterviewer answers
Per endpoint or global?Per endpoint group; create one limiter each.
Wait or fail?User-initiated calls wait; background calls can drop.
Part 3 of 5

Detailed answer

The design decisions, the complete Kotlin solution, and a walk through it one block at a time.

3.1Design decisions

Settle these before writing code; each one shows up in the solution.

Lazy refill

No timers: compute tokens from elapsed time whenever someone asks.

Injectable monotonic clock

TimeSource.Monotonic ignores changes to the device time; tests pass a TestTimeSource and move it by hand.

Plain class + Mutex

The bucket is simple and easy to test; RateLimiter shares one behind a Mutex and sleeps outside the lock.

3.2Solution

Complete, compiling Kotlin with coroutines, built with warnings as errors and covered by tests/mobile/MobileTests.kt. The Java and TypeScript tabs do the same job with each language's own tools: Java compiled and run in our tests, TypeScript run in our tests.

RateLimiter.ktKotlin
1import kotlin.time.Duration2import kotlin.time.Duration.Companion.seconds3import kotlin.time.DurationUnit4import kotlin.time.TimeSource5import kotlinx.coroutines.delay6import kotlinx.coroutines.sync.Mutex7import kotlinx.coroutines.sync.withLock8 9/**10 * Token bucket: allows short bursts up to [capacity], then a steady [refillPerSecond].11 * Protects your own API from your own app (pull-to-refresh spam, retry storms).12 * Not thread-safe on its own: share it through [RateLimiter].13 */14class TokenBucket(15  val capacity: Double,16  val refillPerSecond: Double,17  private val clock: TimeSource.WithComparableMarks = TimeSource.Monotonic,18) {19  private var tokens = capacity20  private var lastRefill = clock.markNow()21 22  fun tryConsume(cost: Double = 1.0): Boolean {23    refill()24    if (tokens < cost) return false25    tokens -= cost26    return true27  }28 29  /** How long until [cost] tokens will be available. */30  fun waitTime(cost: Double = 1.0): Duration {31    refill()32    val missing = maxOf(0.0, cost - tokens)33    return (missing / refillPerSecond).seconds34  }35 36  private fun refill() {37    val now = clock.markNow()38    val elapsed = (now - lastRefill).toDouble(DurationUnit.SECONDS).coerceAtLeast(0.0)39    tokens = minOf(capacity, tokens + elapsed * refillPerSecond)40    lastRefill = now41  }42}43 44/** Shared limiter for every caller in the app: callers wait their turn instead of failing. */45class RateLimiter(capacity: Double, refillPerSecond: Double) {46  private val bucket = TokenBucket(capacity, refillPerSecond)47  private val lock = Mutex()48 49  suspend fun acquire(cost: Double = 1.0) {50    require(cost <= bucket.capacity) { "cost can never be satisfied" }51    while (true) {52      val wait = lock.withLock {53        if (bucket.tryConsume(cost)) return54        bucket.waitTime(cost)55      }56      delay(wait)                                      // sleep outside the lock57    }58  }59}
59 linesUTF-8Kotlin

3.3Line-by-line walkthrough

The same code in the order you would explain it in the room. The line numbers follow the Kotlin file; the Java and TypeScript tabs above have the same steps in the same order.

1

Start full

Tokens start at capacity, which allows an initial burst.

RateLimiter.ktKotlin
19  private var tokens = capacity20  private var lastRefill = clock.markNow()
lines 19–20UTF-8Kotlin
2

Consume if available

Refill first, then take tokens or refuse.

RateLimiter.ktKotlin
22  fun tryConsume(cost: Double = 1.0): Boolean {23    refill()24    if (tokens < cost) return false25    tokens -= cost26    return true27  }
lines 22–27UTF-8Kotlin
3

How long to wait

Missing tokens divided by the refill rate, as a Duration.

RateLimiter.ktKotlin
30  fun waitTime(cost: Double = 1.0): Duration {31    refill()32    val missing = maxOf(0.0, cost - tokens)33    return (missing / refillPerSecond).seconds34  }
lines 30–34UTF-8Kotlin
4

Lazy refill

Add elapsed × rate, capped at capacity. A monotonic clock avoids time-change bugs.

RateLimiter.ktKotlin
36  private fun refill() {37    val now = clock.markNow()38    val elapsed = (now - lastRefill).toDouble(DurationUnit.SECONDS).coerceAtLeast(0.0)39    tokens = minOf(capacity, tokens + elapsed * refillPerSecond)40    lastRefill = now41  }
lines 36–41UTF-8Kotlin
5

Callers wait their turn

Check under the lock; if tokens run short, delay exactly as long as needed outside the lock, then try again.

RateLimiter.ktKotlin
49  suspend fun acquire(cost: Double = 1.0) {50    require(cost <= bucket.capacity) { "cost can never be satisfied" }51    while (true) {52      val wait = lock.withLock {53        if (bucket.tryConsume(cost)) return54        bucket.waitTime(cost)55      }56      delay(wait)                                      // sleep outside the lock57    }58  }
lines 49–58UTF-8Kotlin

Complexity: O(1) per call, no background timers

Part 4 of 5

Q&A

The questions interviewers ask after the code works. Answer out loud, then open.

4.1Follow-up questions

Leaky bucket vs token bucket?
Leaky bucket smooths output to a constant rate; token bucket allows bursts, which suits user actions.
Server-side too?
Always. The client limiter protects against your own bugs; the server enforces the contract.
Part 5 of 5

Extra depth

The cases that break naive solutions, how the same design looks on iOS, and what to practise next.

5.1Edge cases

Say these before the interviewer does.

Show detailsHide details
  • Cost bigger than capacity never succeeds (rejected up front)
  • Clock going backwards (clamped to zero)
  • Many waiters wake together (they retry and most wait again)

5.2On iOS

The same design in Swift and Apple's frameworks.

Show detailsHide details
ApproachSwift / iOS
SwiftThe same bucket as a struct (value type, easy to test) shared through an actor.
ClockContinuousClock, which is monotonic and injectable for tests.
AI Engineer · Client-side token bucket rate limiter