System Design Internals
Resource Allocation Algorithms
Black Friday hits: checkout, search, and batch analytics all want the same CPU cores and database connections. Without a deliberate policy, the loudest client wins and interactive traffic dies under a fair-looking free-for-all.
This note covers fairness algorithms, rate buckets, multi-resource shares, placement packing, and —the pieces interviewers expect when you say “we isolate tenants.”
Allocation stack
Refuse work before queues explode.
Raise the poorest tenant first.
Bound long-run rate; allow bursts.
Fit tasks onto machines with headroom.
What actually happens
Every scarce thing—CPU time slices, memory bytes, disk IOPS, network bandwidth, connection pool slots—needs a decision rule when many tenants compete. is that rule plus meters that make it real.
Network and storage often start from or . APIs add a so a bursty client cannot sustain overload. Clusters use shares, , and when jobs ask for CPU and memory together.
Placement is a separate allocator: packs pods onto nodes while leaving room for failover. Without , a perfect fair scheduler still queues forever and burns SLOs.
How to choose an allocator
1. One resource or many? Single-link bandwidth → max-min / WFQ. CPU+memory jobs → DRF or multi-dimensional packing.
2. Isolation or utilization? Hard reservations waste idle capacity. Soft shares with steal raise utilization but blur guarantees.
3. Can you preempt? Batch can die; user RPCs need with care (or priority queues that never start low work during overload).
Simple rule of thumb
Admit first, fair-share second, pack third. Give interactive traffic a floor, let batch fill leftovers, meter every dimension you sell, and leave spare capacity for failover—not just for average load.
The allocation pipeline
Read the diagram definition
flowchart TD
Arr[Arriving work] --> Adm{Admission control}
Adm -->|Reject / retry-later| Out[Caller sees pushback]
Adm -->|Admit| Q[Per-tenant or priority queues]
Q --> Sch[Scheduler / WFQ / shares]
Sch --> Enf[Enforcement: cgroups, tokens, IO sched]
Enf --> Run[Running capacity]
Run --> Meter[Meters and quotas]
Meter -->|Over quota| Throttle[Throttle / preempt]
Throttle --> Q
Meter -->|Under quota| RunLayers (typical web stack):
1. Edge / API gateway: token buckets + concurrency caps per tenant
2. Service: thread pools / semaphores / bulkheads per dependency
3. OS: CFS shares, cgroup CPU/memory, ionice
4. Cluster: requests/limits, DRF or fair-share queues, bin packing
Failure if you skip a layer:
Perfect WFQ at the NIC + unbounded app threads = still dead
Perfect app pools + no tenant quota = one customer starves others
Perfect quotas + no admission = infinite queue latencyMax-min fairness
Read the diagram definition
flowchart LR
Cap[Link capacity 30] --> A[User A wants 5]
Cap --> B[User B wants 15]
Cap --> C[User C wants 20]
A --> R1[Round 1: give 10 each]
R1 --> R2[A done: leftover 5]
R2 --> R3[Split 5 to B and C]
R3 --> Out[A=5, B=12.5, C=12.5]Classic water-filling: sort demands, raise a water level until capacity is exhausted. Users below the level get all they asked; users above get the level. The outcome is Pareto-efficient among equal-priority peers and is the usual fairness target for TCP-like sharing stories.
Weights generalize it: a weight-2 user gets twice the water level of weight-1. That is the fairness story behind and many “CPU shares” knobs.
Pseudocode (equal weights):
remaining = capacity
unsatisfied = all users with demand > 0
while unsatisfied and remaining > 0:
share = remaining / |unsatisfied|
for u in unsatisfied:
give min(share, u.remaining_demand)
remove satisfied users; update remaining
Properties:
- strategy-proof in the idealized fluid model (asking for more does not help)
- not the same as proportional to instantaneous demand (which rewards greed)Weighted fair queuing and approximations
Fluid max-min assumes infinitely small bits. Packets are discrete. assigns each queue a virtual finish time and serves the earliest finish time next, approximating GPS (generalized processor sharing). Exact WFQ is expensive; production uses Deficit Round Robin (DRR), Stochastic Fair Queuing, or hierarchical token buckets.
| Mechanism | Good for | Watch |
|---|---|---|
| WFQ / WF2Q+ | Strict per-flow fairness, delay bounds | CPU cost; many flows |
| DRR | Cheap approximate fairness | Quantum sizing; latency variance |
| Strict priority | Control plane over data plane | Starvation without aging |
| Lottery / stride | Probabilistic proportional share | Short-term unfairness |
Token buckets and leaky buckets
Token bucket:
tokens = min(capacity, tokens + rate * dt)
if tokens >= cost: tokens -= cost; allow
else: delay or 429
Leaky bucket (as queue):
enqueue if queue not full
drain at constant rate r
Interview numbers:
rate = 100 rps, burst = 200 → ~2s of burst at full throttle
without concurrency limit, 200 parallel 5s RPCs = 1000 in-flight
Compose:
gateway bucket (tenant) × service semaphore (global) × DB pool (shard)
measure which layer rejects; do not stack three silent 429sA bucket alone is not fairness among many tenants: each tenant needs its own bucket (or a hierarchical scheme). Global rate limits protect the dependency; per-tenant buckets protect noisy-neighbor isolation.
Dominant Resource Fairness
Read the diagram definition
sequenceDiagram
autonumber
participant S as Scheduler
participant J1 as Job CPU-heavy
participant J2 as Job mem-heavy
participant N as Node pool
Note over S,N: Capacities: 100 CPU, 100 GB
J1->>S: ask 20 CPU, 5 GB
J2->>S: ask 5 CPU, 20 GB
S->>S: dominant share J1=0.20 CPU, J2=0.20 mem
S->>N: allocate next slice to lower dominant share
Note over S: DRF equalizes max resource fractionsgeneralizes max-min to vectors. A CPU-heavy job’s dominant share is its CPU fraction; a memory-heavy job’s is memory. The scheduler always prefers the user with the smaller dominant share, subject to fitting on a node.
DRF is strategy-proof in the fluid model and beats naive “pick random free slot” for multi-tenant analytics clusters. It does not replace placement constraints: GPUs, locality, and anti-affinity still bind.
Example capacities: 100 CPU, 100 GB RAM
Job A task: 4 CPU, 1 GB → dominant resource = CPU (per task)
Job B task: 1 CPU, 4 GB → dominant resource = memory
If A runs 10 tasks: uses 40 CPU, 10 GB → dominant share = 0.40
If B runs 10 tasks: uses 10 CPU, 40 GB → dominant share = 0.40
DRF keeps allocating to whichever side would stay lower after the next task.
Contrast:
pure CPU fair-share would let memory hogs starve CPU jobs on memory
pure first-come packing can strand resources (fragmentation)Requests, limits, and CFS shares
Container platforms expose two knobs that people conflate. Requests (or shares) drive scheduling and relative weight when the node is contended. Limits (or quotas) cap absolute use. A pod with request 100m and limit 2000m can burst until the node is busy, then falls back toward its share. Setting limit == request is reservation-like isolation; setting limit much higher raises utilization and noisy-neighbor risk.
Linux CFS intuition:
weight(share) ≈ relative CPU when all runnable
cpu.cfs_quota_us hard-caps burst (Throttling)
Memory:
request ≈ scheduling guarantee / QoS class
limit ≈ cgroup max; over = OOMKill that container
Design mistakes:
- all pods request 0 → scheduler packs denser than reality
- limits far above requests on every pod → thundering contention
- memory limit without request → Burstable surprises under pressureBin packing and spare capacity
First-fit decreasing and best-fit heuristics reduce stranded CPU/memory. Worst-fit spreads load and can help tail latency. Production schedulers add scoring: prefer already-warm images, respect pod anti-affinity, avoid single-rack concentration.
Always reserve headroom for the largest failed domain you tolerate (one node, one AZ). A cluster at 95% packing looks cheap until a node dies and nothing can reschedule.
Placement sketch:
filter nodes that fit (CPU, mem, GPU, taints)
score: packing density vs spread vs locality
bind; if fail, retry with wider filters
Failover math:
N nodes, want survive 1 node loss
usable ≈ (N-1)/N of capacity for steady state
plus per-node disk/network not fungible across nodesAdmission control and preemption
decides whether new work enters. decides whether running work must leave. Together they keep latency-critical paths inside SLO when load spikes.
Admit when
- Concurrency and queue depth under target
- Tenant under quota and retry budget healthy
- Downstream circuit breakers closed
- Predicted finish fits the deadline
Preempt when
- Higher priority work cannot schedule
- Best-effort batch holds warm capacity
- You can checkpoint or cheaply restart
- Policy forbids starving interactive traffic
SD use cases
Multi-tenant API
Retry-After rather than infinite buffering. Sell tiers as weights, not as “unlimited.”Batch vs online on one cluster
Egress / CDN bandwidth
Database connection pools
Worked example: noisy neighbor
Tenant A suddenly sends 10× traffic. Shared thread pool saturates; Tenant B p99 jumps from 40 ms to 2 s even though B’s QPS is flat.
Before:
one pool of 200 workers
A takes 180, B waits → B latency is queueing, not business logic
Repair ladder:
1. Per-tenant concurrency caps (bulkhead) — B cannot lose all workers
2. Per-tenant token buckets — A gets 429s instead of infinite queue
3. Weighted fair queue into the pool — A and B progress proportionally
4. Separate pools / nodes for enterprise tier if isolation is contractual
Verify:
B p99 stable while A is rejected or slowed
A’s useful throughput near its paid weight, not zero
no retry storm: 429s include backoff guidanceTrade-offs
| Choice | Gain | Cost |
|---|---|---|
| Hard reservations | Predictable isolation | Idle waste; harder packing |
| Soft shares + work-conserving | High utilization | Noisy neighbor under contention |
| Max-min / WFQ | Principled fairness | Implementation and tuning cost |
| Token bucket | Simple rate + burst | Not multi-resource; needs concurrency cap |
| DRF | Fair multi-dimensional clusters | Ignores locality unless extended |
| Dense bin packing | Fewer machines | Painful failover; hot nodes |
| Preemption | Protects high priority | Wasted work; checkpoint complexity |
Choosing and explaining resource allocation
A complete explanation connects the mechanism to a requirement. Describe what improves when you introduce it, which new failure cases become possible, and how you would know that the trade-off is worthwhile.
Explain the core idea
Name the scarce resource, the fairness goal, and the enforcement point (gateway, cgroup, scheduler).
Separate admission (should work enter?) from scheduling (who runs next?) from packing (where does it run?).
Max-min and WFQ for single resources; DRF when jobs ask for CPU and memory together.
When it belongs
Multi-tenant APIs, shared databases, or mixed batch/online clusters.
Noisy-neighbor incidents or “unlimited” tier promises.
Sizing Kubernetes requests/limits or connection pools.
How it fails
Fair scheduler behind an unbounded queue → infinite latency.
Token bucket without concurrency cap → burst melts the backend.
Over-packing nodes → cannot reschedule after a failure.
Priority without aging → permanent starvation.
Trade-offs to weigh
Isolation versus utilization.
Exact fairness versus cheap approximations (DRR).
Burst friendliness versus overload protection.
Dense packing versus failover headroom.
Common misunderstandings
Calling rate limiting “fairness” without per-tenant queues.
Setting every limit equal to the node capacity.
Ignoring memory when talking only about CPU shares.
Assuming work-conserving shares equal hard SLOs.
Wrap-up
Allocation is policy you can meter. Pick fairness, enforce it in more than one layer, and admit only what you can finish.
Exercises
- Max-min. Capacity 100. Demands 10, 40, 80. Compute allocations.
- Bucket. 50 rps, burst 150. How long can a client run at 150 rps before throttling, starting from a full bucket?
- DRF. Capacities 60 CPU / 60 GB. Tasks A=(6,1), B=(1,6). Who gets the next task when both have 5 tasks running?
Primary sources
Key takeaway
Admit early, share fairly, pack with failover headroom. Token buckets bound rate; WFQ/DRF bound relative progress; quotas and preemption make the policy real when someone cheats or a batch job overstays.