Design a quota service

Source: https://www.hack2hire.com/question-bank/questions/system-design/69d850f4c4c1bc791ee230c5
Company: Snowflake, Microsoft, Google, Amazon
Difficulty: Medium

Problem statement

Track and enforce how much of each resource (API calls, storage, compute) every tenant may use, with fast checks and limits that stay accurate across regions.

Requirements

We are building a shared quota service: every product service (API gateway, object storage, compute scheduler) asks it before consuming a tenant's resource, and it says yes or no against that tenant's limit. Unlike a rate limiter, which caps a rate over a short window, a quota caps an amount: 10 TB of storage, 500 vCPUs running at once, 50M API calls per month. Operations that consume quota can take a while and can fail, so the core contract is reserve → commit or release, not a single increment.

Clarifying questions worth asking up front:

• Which resources? Some are allocated (storage bytes, running VMs: usage goes up and down), some are consumed (API calls per month: usage only goes up until the period resets). Both need support.
• Hard or soft limits? Hard limits reject; soft limits allow but alert and bill overage.
• How accurate across regions? Is a brief 1% overshoot on a monthly API-call quota fine? (Usually yes.) Is overshoot on a paid storage cap fine? (Usually small overshoot, yes; unbounded, no.)
• Who sets limits? Billing plans, plus admin overrides and support-granted increases.

Functional requirements

• Define limits per (tenant, resource, scope), where scope is global, a region, or a project inside the tenant.
• Reserve an amount before doing work; the reservation holds quota for a TTL.
• Commit a reservation when the work succeeds (quota becomes used) or Release it when the work fails.
• Adjust usage directly for decrements (a file deleted, a VM stopped) and for corrections from reconciliation.
• Read current usage, reserved amount, and limit for a tenant, for dashboards and pre-flight checks.
• Limits change when a tenant's billing plan changes, within about a minute.
• Notify tenants at 80% and 100% of a limit.

Non-functional requirements

• Reserve p99 under 10 ms in-region; it sits on the request path of create calls.
• Never over-commit hard quotas by more than a bounded amount (target: zero within a region, under 1% globally).
• No lost commits: once a commit is acknowledged, usage includes it, even if the reservation's TTL then fires.
• 99.99% availability; when the service is down, callers degrade predictably (see deep dives).
• Idempotent operations: callers retry on timeouts and must not double-count.
• Auditable: every change to usage is explained by a ledger entry.

Back-of-the-envelope estimation

• 5M tenants × ~20 metered resources ≈ 100M quota counters. Each counter row ~200 B → ~20 GB. Small; fits in a sharded relational store with room to spare.
• Reserve traffic: API-call quotas dominate. 2M requests/s through gateways, but gateways batch: they reserve blocks of 1,000 calls locally, so the service sees ~2,000 reserves/s for API calls.
• Allocation resources (storage writes, VM creates, job submits): ~50k reserves/s peak, plus the same number of commits/releases → ~100k writes/s.
• Reads (dashboards, pre-flight checks): ~200k/s, served from caches.
• Reservations live seconds to minutes; at 50k/s with a 60 s mean life, ~3M open reservations at any time, ~1 KB each → 3 GB.
• Ledger: 100k entries/s × 150 B ≈ 1.3 TB/day; keep 30 days hot, then roll into cold storage.
• Hot tenants: the largest tenant may do 5k reserves/s on one counter; a single row lock tops out around 1–3k updates/s, so hot counters need sharding (deep dive 1).

API design

gRPC, internal only, mTLS between services. All mutating calls take a caller-generated request_id for idempotency.

Reserve(request_id, tenant_id, resource, scope, amount, ttl_s=60)
  → {reservation_id, status: GRANTED | DENIED, remaining, limit, expires_at}
     DENIED carries reason: OVER_LIMIT | TENANT_SUSPENDED

Commit(request_id, reservation_id, actual_amount?)
  → {status: COMMITTED, used}
     actual_amount ≤ reserved; the difference is returned to the pool.
     Commit after expiry still succeeds if the work happened (see deep dive 2).

Release(request_id, reservation_id) → {status: RELEASED}

Extend(reservation_id, ttl_s) → {expires_at}        # long uploads, slow VM boots

Adjust(request_id, tenant_id, resource, scope, delta, reason)
  → {used}                                           # deletes, reconciliation fixes

GetUsage(tenant_id, resource?, scope?)
  → [{resource, scope, limit, used, reserved, period_end}]

SetLimit(tenant_id, resource, scope, limit, source: PLAN | OVERRIDE, version)
  → {effective_at}                                   # called by billing and admin tools

REST mirror for tenant consoles: GET /v1/tenants/{id}/quotas returns the GetUsage shape.

Data model

Store: a sharded, strongly consistent SQL database (Spanner, CockroachDB, or Postgres/Vitess sharded by tenant_id). We need row-level transactions across a counter and its reservation in one shard; a single tenant's rows never span shards.

quota_counters, primary key (tenant_id, resource, scope, shard_no)

reservations, primary key (tenant_id, reservation_id), secondary index (shard_bucket, expires_at) for the expiry sweeper

limits, primary key (tenant_id, resource, scope): plan_limit, override_limit, effective_limit, billing_version. Effective limit = override if present, else plan.

usage_ledger, append-only, partitioned by day, key (tenant_id, ts, entry_id): delta, kind (commit, release, expire, adjust, reconcile), reservation_id, actor. This is the audit trail and the input for billing.

Redis holds a read-through cache of GetUsage results (q:{tenant}:{resource}:{scope} with a 5 s TTL) for dashboard reads.

High-level design

flowchart LR
  SVC[Product services] --> CL[Quota client library]
  CL --> API[Quota API servers]
  API --> DB[(Sharded SQL counters and reservations)]
  API --> LED[(Usage ledger)]
  API --> RC[(Redis read cache)]
  SW[Expiry sweeper] --> DB
  BILL[Billing plans] --> LP[Limit propagator]
  LP --> DB
  REC[Reconciler] --> DB
  STO[Storage usage scans] --> REC
  LED --> BI[Billing and alerts]

1. Reserve. The client library (embedded in each product service) sends Reserve to an API server in the region. The server picks a counter shard for the tenant, then in one transaction: reads the counter, checks used + reserved + amount ≤ limit, increments reserved, and inserts the reservation row in PENDING. If request_id already exists, it returns the stored result instead.
2. Do the work. The product service writes the object, starts the VM, or runs the job.
3. Commit or release. On success, Commit moves the amount from reserved to used (and returns any unused portion), flips the reservation to COMMITTED, and appends a ledger entry, all in one transaction. On failure, Release subtracts from reserved and flips to RELEASED.
4. Lifecycle. PENDING → COMMITTED | RELEASED | EXPIRED. EXPIRED → COMMITTED is also legal (a late commit), and is the only transition out of a terminal-looking state. Every transition is a compare-and-set on state, so retries and races resolve to one winner.
5. Expiry. A sweeper per shard scans expires_at < now() and expires stale PENDING reservations in batches, returning their amount.
6. Reads at scale. GetUsage sums the counter shards and is cached in Redis for 5 s. Pre-flight checks in UIs tolerate that staleness; enforcement always goes through Reserve and never trusts the cache.
7. Limits. Billing emits plan-change events; the propagator writes limits and redistributes per-shard slices.

Deep dives

1. Preventing over-commitment under concurrent reservations. The invariant is used + reserved ≤ limit per counter. Doing the check and the increment in one serializable transaction (or UPDATE ... SET reserved = reserved + :amt WHERE used + reserved + :amt <= limit, checking affected rows) makes it hold under any concurrency. The cost is contention: one row serializes all reservations for a tenant-resource, about 1–3k/s. For hot tenants, split the counter into N shards, each owning limit / N of headroom. A reserve picks a random shard; if it is short, it tries one more, then falls back to a slow path that rebalances. A rebalancer moves unused headroom from idle shards to busy ones every few seconds, transactionally (decrease one shard's slice, increase another's). Sharding is driven by observed write rate: most tenants use 1 shard; the top 0.1% get 8–64.

Client-side blocks are how the API gateway handles 2M req/s: it reserves 1,000 calls, spends them locally, commits the count used, and reserves another block when 20% remain.

2. Reclaiming expired reservations without losing committed work. A reservation can expire while its work is still finishing: a 5 GB upload takes longer than the 60 s TTL. Rules that keep this safe:

• Long operations call Extend as a heartbeat (the client library does it at TTL/3).
• The sweeper expires with a compare-and-set: UPDATE reservations SET state='EXPIRED' WHERE id=? AND state='PENDING', then subtracts amount from reserved in the same transaction. A concurrent commit either wins first (sweeper sees 0 rows, does nothing) or loses (commit sees EXPIRED).
• A late commit on an EXPIRED reservation is accepted: the work happened, so usage must show it. It adds amount straight to used without checking the limit, logs a late_commit ledger entry, and raises a metric. This can push a tenant slightly over the limit; that is bounded by the TTL and is better than undercounting.
• Terminal states are kept for 7 days so retries of Commit/Release stay idempotent, then reservations are deleted.
• Sweeper sizing: 3M open reservations, ~50k expiring/s worst case, spread over 1,000 shard buckets → ~50 rows/s per sweeper. A crashed sweeper only delays reclaim; correctness does not depend on it.

3. Reconciling tracked quota with actual usage. Counters drift: a service commits then the write is rolled back, a delete event is lost, a bug double-releases. For allocated resources the source of truth is the resource itself (bytes in the object store, VMs in the fleet), so a reconciler compares them daily (hourly for paid storage tiers). Storage publishes per-tenant byte totals from its metadata scan; the reconciler computes actual − (used as of scan snapshot time), using the ledger to discount commits that landed after the snapshot, and writes an Adjust with kind reconcile when the difference exceeds 0.1% or 1 GB. Large corrections (over 5%) page a human instead of auto-applying, because they usually mean a bug, and a big downward correction can mask one. Consumable quotas (API calls) reconcile against request logs at period close, and billing uses the ledger, not the counter.

4. Limit propagation and graceful degradation. Billing is the source of plan limits. Plan changes go through an outbox to a stream; the propagator applies them with billing_version so an older event never overwrites a newer one, and redistributes shard slices. Lowering a limit below current usage does not delete anything: new reserves are denied until usage drops, and the tenant is notified. When the quota service is unreachable, the client library falls back per resource policy:

5. Multi-service fairness and multi-region. When several services share one tenant quota (e.g. compute used by batch jobs and interactive notebooks), a batch job can drain the pool. Allow sub-scopes with guaranteed minimums: notebooks reserve against min=20% that batch cannot touch, and borrow from the shared rest. For multiple regions, give each region a slice of a global limit, sized by its recent usage share, with a global rebalancer that moves headroom every 10–30 s through a small consistent store. Reserves stay region-local (fast, no cross-region hop); the maximum global overshoot is zero as long as slices sum to the limit. The cost: a region can reject while another has headroom, until the next rebalance. Region-scoped quotas (VMs in us-east-1) need no global coordination at all.

Trade-offs

• Reserve/commit instead of a single increment costs a second call and reservation state, but makes failed work return quota and keeps used honest.
• Strongly consistent SQL per counter gives exact enforcement at the cost of per-row throughput; counter sharding buys throughput but introduces rejections while headroom sits on another shard.
• Client-side blocks remove the service from the hot path for API calls but strand up to one block per gateway pod; with 200 pods × 1,000 calls that is 200k calls of slack on a monthly quota, negligible.
• Accepting late commits keeps billing correct but means hard limits can be exceeded by at most one TTL of in-flight work.
• Regional slices keep reserves local and bounded, but a region can deny while the tenant still has global headroom; a single global store would be exact but adds 50–150 ms cross-region latency.
• Failing open on outages protects customer traffic and risks short overspend; failing closed protects scarce capacity and risks outages spreading. The choice is per resource, not global.
• Auto-reconciliation fixes drift without humans, but capping automatic corrections means some drift waits for a person.

Interviewer expectations

Mid-level (L4)

• Separates limits, usage, and reservations, and stores counters per tenant and resource.
• Does the check and increment atomically, and can explain the race if they aren't.
• Gives a working reserve/commit/release API with idempotent request IDs.

Senior (L5)

• Defines the reservation state machine, TTL expiry with compare-and-set, and the late-commit rule.
• Handles hot tenants with counter shards or client-side blocks, with throughput numbers.
• Adds reconciliation against real storage usage and per-resource fail-open/fail-closed policies.

Staff (L6+)

• Separates allocated and consumable resources and states the accuracy bound each policy gives.
• Designs multi-region slices with rebalancing, limit propagation from billing with versioning, and fairness between services sharing a quota.
• Treats the ledger as the audit and billing source of truth, and plans operations: drift alerts, caps on auto-correction, sweeper lag metrics.