skip to content

A worker keeps one rate.Limiter per tenant in a map. Why does that map grow without bound, and what do you do about it?

level: seniorimportance: should knowfreq 40%

answer

  1. who ever deletes from that map?
  2. how many distinct keys will the process see?
  3. an idle bucket is a full bucket
  4. capacity over rate is the safe idle threshold
  5. each tenant bounded, the total unbounded

basics

~20 s

Limiters are created on first sight of a key and never removed, so the map keeps an entry for every tenant ever seen. Bound it: key on a set you control, and evict entries idle longer than the refill time.

solid answer

~50 s

The map is written on the miss path — look up the tenant, create a limiter if absent — and nothing ever deletes. In a long-running process the live entry count becomes the number of *distinct keys ever observed*, which for tenant or API-key cardinality only goes up, and for keys derived from caller-supplied input is effectively unbounded. Each entry is small, so it shows up as a slow heap climb rather than a crash, which is why it survives review. The fixes: key on something whose cardinality you control; guard the map with a mutex, since concurrent map access without one is a fatal runtime error; and evict entries idle longer than `burst/rate` seconds, past which the limiter has refilled completely, so recreating it grants exactly the tokens the old one held. Per-tenant limiters also leave your aggregate rate unbounded, so a global limiter usually sits alongside.

code

go · 31 lines
go
type slot[T any] struct {
	v T
	lastSeen time.Time
}

type keyed[T any] struct {
	mu sync.Mutex
	m map[string]*slot[T]
	idle time.Duration
	newT func() T
}

func (k *keyed[T]) get(key string, now time.Time) T {
	k.mu.Lock()
	defer k.mu.Unlock()
	if k.m == nil {
		k.m = map[string]*slot[T]{}
	}
	for other, s := range k.m { // O(n): sweep on a fraction of calls if the map is large
		if now.Sub(s.lastSeen) > k.idle {
			delete(k.m, other)
		}
	}
	s, ok := k.m[key]
	if !ok {
		s = &slot[T]{v: k.newT()}
		k.m[key] = s
	}
	s.lastSeen = now
	return s.v
}

go deeper

for a junior

Notice the missing delete: something inserts into the map on every new key and nothing ever removes. That observation alone is most of the answer at this level.

for a middle

Explain the get-or-create race and why the whole operation belongs under one lock, and describe eviction based on a last-used timestamp rather than a fixed lifetime.

for a senior

Reason about the idle threshold with the refill arithmetic, show how you would detect the growth in the first place, and point out that per-key limits leave the aggregate rate unbounded.

for a principal

Decide what may be a key at all. Allowing an unbounded, caller-influenced key space to allocate long-lived state is a design choice with a security dimension, and the bound belongs in the contract, not in a cleanup goroutine.

## How the leak appears The code is unremarkable, which is the problem: 1. a request or job arrives carrying a tenant identifier; 2. look the identifier up in a `map[string]*rate.Limiter`; 3. if absent, construct a limiter with the per-tenant rate and store it; 4. use it. Step 3 has no counterpart. Nothing removes an entry, so the map's size converges on the number of distinct identifiers the process has ever seen. In a service restarted weekly with fifty stable tenants, this is fine forever. In a process that lives for months, or whose key includes anything with real cardinality — an API key, a user, a URL path, a customer-supplied label — the map grows monotonically and the process's resident memory follows it. What makes it hard to spot is that it is *slow* and *cheap per entry*. Nothing crashes, nothing is obviously wrong in a load test, and the graph that would show it is a heap that climbs a little each day. The give-away in a heap profile is a large live allocation count attributable to the limiter construction site and to map bucket growth. ## Fix one: control the cardinality of the key Before reaching for eviction, ask what the key *is*. A limiter per tenant, where tenants are a known and slowly changing set from your own database, is a bounded map by construction. A limiter per arbitrary caller-supplied string is not bounded by anything, and no eviction policy makes an attacker-chosen key space safe to allocate against. Reject or bucket unknown keys before they reach the map. ## Fix two: make the map concurrency-safe The get-or-create is a read followed by a write from many goroutines. In Go, concurrent map access without synchronisation is not merely a data race, it is a fatal runtime error the program cannot recover from. A plain `sync.Mutex` around the get-or-create is correct and, since the critical section is a map lookup and occasionally a small allocation, cheap enough at almost any traffic level. Do the whole get-or-create under one lock rather than checking under a read lock and inserting under a write lock without re-checking; otherwise two goroutines create two limiters for one tenant and the tenant quietly gets double its rate. ## Fix three: evict on idleness, and pick the threshold with arithmetic The elegant part of eviction here is that for a token bucket it is provably harmless when the idle threshold is chosen correctly. A limiter that has gone untouched for longer than `burst/rate` seconds has refilled to capacity. A brand-new limiter also starts at capacity. So evicting a limiter idle for longer than its own refill time and recreating it on the next call gives that tenant *exactly* the allowance it already had — no bypass, no double-spend. Set the idle threshold comfortably above `burst/rate` and the eviction is free of policy consequences; set it below and you have handed idle tenants a way to reset a partially drained bucket by pausing. Mechanically, you can sweep opportunistically — when creating an entry, or every Nth operation — or from a dedicated maintenance goroutine. Opportunistic sweeping avoids a background goroutine and a shutdown path; scanning the whole map is O(n) under the lock, so for large maps do it on a fraction of operations or keep a coarse ordering of last-use so you only inspect the oldest. Record `lastSeen` on every use, and delete anything older than the threshold. A fixed-capacity structure with least-recently-used eviction is the other honest answer, and it is stronger when the key space genuinely is adversarial: it bounds memory by construction rather than by hoping the idle threshold keeps up. ## The thing per-key limiters do not do Even with eviction working perfectly, a map of per-tenant limiters enforces a per-tenant rate and says nothing about the total. A thousand tenants each politely under their own 5 per second is 5,000 per second at the far end. When the constraint you are respecting is a single shared quota — one vendor account, one database, one partner contract — you need a global limiter as well, checked in addition to the per-tenant one. Check the cheap per-tenant limiter first so a tenant already over its own rate never consumes global allowance. And, as always, per-key limiters bound the *rate* of calls, not how many are outstanding at once. A slow dependency will happily accumulate in-flight work under a limiter that is perfectly happy with the arrival rate. ## What to watch Export the map's size. It is a one-line gauge and it turns an invisible slow leak into a graph that either plateaus or does not. Alongside it, per-tenant allowed and denied counts tell you whether the limits are biting, and the upstream's own rejection rate tells you whether your model of the quota matches theirs.

  • How do you choose the idle threshold for evicting a per-tenant limiter?
    Longer than `burst/rate`, the time an empty bucket takes to refill completely. Past that point the stored limiter is full, and a freshly constructed one is also full, so eviction and recreation grant identical allowance. A shorter threshold lets a tenant reset a partially drained bucket by pausing, which is a real bypass.
  • What breaks if two goroutines run the get-or-create at the same time without a lock?
    Concurrent map read and write is a fatal runtime error in Go, not a recoverable panic, so the process dies. Even with a lock held only for the read, a check-then-insert without re-checking under the write lock creates two limiters for one tenant, and that tenant silently receives double its rate.
  • Your per-tenant limiters are all correctly configured. Why can the far end still see too much traffic?
    Because per-key limits compose additively. A thousand tenants each under 5 per second is 5,000 per second at a shared dependency. When the real constraint is one shared quota you need a global limiter checked alongside the per-tenant one — per-tenant first, so a tenant already over its own rate never spends global allowance.

saying these in an interview costs you the question

  • Says the entries are tiny so it does not matter
  • Evicts on a timer shorter than the refill time
  • Uses the map from many goroutines with no lock
  • Assumes per-tenant limits bound the total rate
  • Keys the map on unvalidated caller-supplied input