{"title":"Fairness Pattern in System Design","description":null,"content":"# Fairness Pattern in System Design\n\nHow does Ticketmaster prevent bots from grabbing all the concert tickets before real fans have a chance? How does AWS ensure one customer's traffic spike doesn't affect other customers? How does TikTok give new creators a fair shot at going viral instead of only promoting established accounts?\n\nThe answer is **fairness**, a critical pattern for ensuring equitable access to resources, opportunities, and outcomes in distributed systems. Without fairness mechanisms, systems devolve into \"winner takes all\" scenarios where power users, bots, or noisy neighbors dominate at everyone else's expense.\n\nThis pattern appears in many system design interviews: **rate limiting, load balancing, multi-tenant systems, ticket sales, content distribution, auction systems, resource allocation, and queue management**. The interviewer expects you to understand fair scheduling algorithms, how to prevent abuse, and the trade-offs between fairness, throughput, and latency.\n\nIn this article, we will explore the fairness pattern in depth, understand different fairness algorithms, and learn how to design equitable systems for various use cases.\n\n---\n\nIf you're enjoying this newsletter and want to get even more value, consider becoming a **[paid subscriber](https://blog.algomaster.io/subscribe)**.\n\nAs a paid subscriber, you'll unlock all **premium articles** and gain full access to all **[premium courses](https://algomaster.io/newsletter/paid/resources)** on **[algomaster.io](https://algomaster.io)**.\n\n[Unlock Full Access](https://blog.algomaster.io/subscribe)\n\n---\n\n## What is Fairness?\n\n**Fairness** in system design means ensuring that resources, access, or opportunities are distributed equitably among users or tenants according to defined policies.\n\n\n```mermaid\nflowchart TD\n subgraph Without[\"Without Fairness\"]\n R1[\"Resources\"]:::primary\n U1[\"Power User
Takes 90%\"]:::red\n U2[\"Normal User
Gets 5%\"]:::orange\n U3[\"Normal User
Gets 5%\"]:::orange\n end\n\n subgraph With[\"With Fairness\"]\n R2[\"Resources\"]:::primary\n F1[\"User A
Gets 33%\"]:::green\n F2[\"User B
Gets 33%\"]:::green\n F3[\"User C
Gets 33%\"]:::green\n end\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef red fill:#ff8787,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n```\n\n\nFairness is not always about equal distribution. It's about **appropriate** distribution based on policies:\n\n\n| ##### Fairness Type | ##### Description | ##### Example |\n| --- | --- | --- |\n| **Equal** | Everyone gets the same share | Public API rate limits |\n| **Proportional** | Share based on entitlement | Paid tier gets 10x free tier |\n| **Weighted** | Priority-based allocation | Premium customers first |\n| **Max-min** | Maximize the minimum share | Ensure everyone gets something |\n| **Work-conserving** | Unused quota goes to others | Burst capacity |\n\n\n---\n\n## Where Fairness Is Used\n\n\n| ##### Domain | ##### Use Case | ##### Fairness Goal |\n| --- | --- | --- |\n| **Rate Limiting** | API access control | Prevent abuse, ensure availability |\n| **Multi-Tenant Cloud** | AWS, Azure, GCP | Noisy neighbor isolation |\n| **Load Balancing** | Request distribution | Even server utilization |\n| **Ticket Sales** | Ticketmaster, concerts | Fair access during high demand |\n| **Content Platforms** | TikTok, YouTube | Creator exposure fairness |\n| **Auctions** | Ad bidding, eBay | Fair competition |\n| **Job Scheduling** | Kubernetes, Hadoop | Fair CPU/memory allocation |\n| **Network QoS** | Bandwidth allocation | Fair throughput per flow |\n| **Gaming** | Matchmaking, loot | Fair matches, fair rewards |\n| **Queues** | Customer support, rides | Fair wait times |\n\n\n---\n\n## Core Challenges\n\n### 1. The Noisy Neighbor Problem\n\nOne tenant's excessive usage degrades performance for others sharing the same infrastructure.\n\n\n```mermaid\nflowchart TD\n subgraph Shared[\"Shared Infrastructure\"]\n Tenant1[\"Tenant A
Normal load\"]:::green\n Tenant2[\"Tenant B
Traffic spike!\"]:::red\n Tenant3[\"Tenant C
Normal load\"]:::green\n end\n\n Resource[\"Shared Resource
(CPU, Network, DB)\"]:::primary\n\n Impact[\"Tenant B exhausts resources
Tenants A and C suffer\"]:::orange\n\n Shared --> Resource\n Resource --> Impact\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n classDef red fill:#ff8787,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n```\n\n\n**Solutions:**\n\n- Per-tenant resource quotas\n- Isolation boundaries (separate pools)\n- Throttling and admission control\n- Fair queuing algorithms\n\n---\n\n### 2. The Thundering Herd Problem\n\nMany users simultaneously compete for limited resources (concert tickets, flash sales, new product launches).\n\n\n```mermaid\nflowchart LR\n subgraph Users[\"10,000 Users\"]\n U1[\"User\"]:::rose\n U2[\"User\"]:::rose\n U3[\"User\"]:::rose\n U4[\"...\"]:::rose\n end\n\n subgraph Resource[\"Limited Resource\"]\n Tickets[\"100 Tickets\"]:::primary\n end\n\n Problem[\"First-come-first-served
= Bots and fast connections win\"]:::red\n\n Users --> Resource\n Resource --> Problem\n\n classDef rose fill:#f783ac,stroke:#000,color:#000\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef red fill:#ff8787,stroke:#000,color:#000\n```\n\n\n**Solutions:**\n\n- Queuing with random selection\n- Lottery/raffle systems\n- Verified fan programs\n- Rate limiting + virtual waiting rooms\n\n---\n\n### 3. The Starvation Problem\n\nSome users or requests never get served because others continuously take priority.\n\n\n```mermaid\nflowchart TD\n subgraph Queue[\"Request Queue\"]\n High[\"High Priority
Keeps arriving\"]:::red\n Low[\"Low Priority
Waiting forever\"]:::orange\n end\n\n Server[\"Server\"]:::primary\n\n Starved[\"Low priority starves
Never gets processed\"]:::red\n\n High --> Server\n Low -.->|\"Never served\"| Starved\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef red fill:#ff8787,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n```\n\n\n**Solutions:**\n\n- Aging (priority increases over time)\n- Guaranteed minimum allocation\n- Fair share scheduling\n- Weighted round-robin\n\n---\n\n### 4. The Gaming/Abuse Problem\n\nUsers try to exploit fairness mechanisms to gain unfair advantage.\n\n\n```mermaid\nflowchart TD\n subgraph Attacks[\"Gaming Attempts\"]\n Multi[\"Multiple accounts\"]:::red\n Bots[\"Automated bots\"]:::red\n Timing[\"Timing attacks\"]:::red\n Sybil[\"Sybil attacks\"]:::red\n end\n\n Fairness[\"Fairness System\"]:::orange\n\n subgraph Defense[\"Defenses\"]\n Identity[\"Identity verification\"]:::green\n Captcha[\"CAPTCHA/challenges\"]:::green\n Anomaly[\"Anomaly detection\"]:::green\n Limits[\"Account limits\"]:::green\n end\n\n Attacks --> Fairness\n Fairness --> Defense\n\n classDef red fill:#ff8787,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n```\n\n\n---\n\n### 5. Fairness vs Efficiency Trade-off\n\nStrict fairness can reduce overall system throughput.\n\n\n```mermaid\nflowchart LR\n subgraph Spectrum[\"The Trade-off\"]\n Efficient[\"Max Efficiency
No fairness
Power users win\"]:::red\n Balanced[\"Balanced
Weighted fairness
Good throughput\"]:::green\n Fair[\"Strict Fairness
Equal shares
Lower throughput\"]:::orange\n end\n\n Efficient -.-> Balanced\n Balanced -.-> Fair\n\n classDef red fill:#ff8787,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n```\n\n\nExample: Strict fairness might give resources to idle users while active users wait.\n\n---\n\n## Fairness Algorithms\n\n### Algorithm 1: Token Bucket\n\nControl the rate at which requests are processed with burst capability.\n\n\n```mermaid\nflowchart LR\n subgraph Bucket[\"Token Bucket\"]\n Tokens[\"Tokens
Refill: 10/sec
Capacity: 100\"]:::primary\n end\n\n Request[\"Request\"]:::secondary\n\n Check{\"Has token?\"}:::orange\n\n Allow[\"Allow
Remove token\"]:::green\n Deny[\"Deny
Rate limited\"]:::red\n\n Request --> Check\n Check -->|\"Yes\"| Allow\n Check -->|\"No\"| Deny\n Bucket --> Check\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef secondary fill:#38d9a9,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n classDef red fill:#ff8787,stroke:#000,color:#000\n```\n\n\n**How It Works:**\n\n1. Bucket starts with N tokens (capacity)\n2. Tokens are added at rate R per second\n3. Each request consumes one token\n4. If no tokens available, request is rejected\n5. Bucket never exceeds capacity (allows bursts up to capacity)\n\n**Parameters:**\n\n\n| ##### Parameter | ##### Purpose | ##### Example |\n| --- | --- | --- |\n| **Rate** | Sustained throughput | 100 requests/second |\n| **Capacity** | Burst size | 500 tokens |\n\n\n\n```shell\nExample: Rate=10/sec, Capacity=100\n\nTime 0: Bucket has 100 tokens\nUser sends 50 requests: 50 allowed, 50 tokens remain\nTime 1s: 10 tokens added, now 60 tokens\nUser sends 100 requests: 60 allowed, 40 rejected\n```\n\n\n\n| ##### Pros | ##### Cons |\n| --- | --- |\n| Allows bursts (good UX) | Memory per user |\n| Simple to implement | Bursts can still cause spikes |\n| Configurable | Bucket synchronization at scale |\n\n\n**Best for:** API rate limiting, per-user quotas\n\n---\n\n### Algorithm 2: Leaky Bucket\n\nSmooth out bursts by processing at a constant rate.\n\n\n```mermaid\nflowchart TD\n Requests[\"Incoming Requests
(Variable rate)\"]:::primary\n\n subgraph Bucket[\"Leaky Bucket (Queue)\"]\n Queue[\"Fixed-size queue\"]:::orange\n end\n\n Output[\"Processed Requests
(Constant rate)\"]:::green\n\n Overflow[\"Overflow
(Rejected)\"]:::red\n\n Requests --> Bucket\n Bucket --> Output\n Requests -.->|\"If full\"| Overflow\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n classDef red fill:#ff8787,stroke:#000,color:#000\n```\n\n\n**How It Works:**\n\n1. Requests enter a fixed-size queue (bucket)\n2. Requests are processed (leak) at constant rate\n3. If bucket is full, new requests are dropped\n4. Output is always smooth, regardless of input pattern\n\n**Comparison with Token Bucket:**\n\n\n| ##### Aspect | ##### Token Bucket | ##### Leaky Bucket |\n| --- | --- | --- |\n| Bursts | Allowed up to capacity | Smoothed out |\n| Output rate | Variable | Constant |\n| Use case | User-facing APIs | Backend processing |\n| Latency | Lower (immediate) | Higher (queued) |\n\n\n**Best for:** Traffic shaping, smoothing request patterns\n\n---\n\n### Algorithm 3: Weighted Fair Queuing (WFQ)\n\nAllocate bandwidth proportionally to weights.\n\n\n```mermaid\nflowchart TD\n subgraph Queues[\"Per-User Queues\"]\n Q1[\"User A Queue
Weight: 2\"]:::primary\n Q2[\"User B Queue
Weight: 1\"]:::secondary\n Q3[\"User C Queue
Weight: 1\"]:::purple\n end\n\n Scheduler[\"WFQ Scheduler\"]:::orange\n\n Output[\"Output
A gets 50%
B gets 25%
C gets 25%\"]:::green\n\n Q1 --> Scheduler\n Q2 --> Scheduler\n Q3 --> Scheduler\n Scheduler --> Output\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef secondary fill:#38d9a9,stroke:#000,color:#000\n classDef purple fill:#9775fa,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n```\n\n\n**How It Works:**\n\n1. Each user/flow has a separate queue\n2. Each queue has a weight (entitlement)\n3. Scheduler serves queues proportionally to weights\n4. Empty queues' share redistributed to active queues\n\n**Virtual Time Calculation:**\n\n\n```shell\nFor each packet, calculate finish time:\nFinish_time = Start_time + (Packet_size / Weight)\n\nScheduler always serves packet with lowest finish time\n\nExample (3 users, weights 2:1:1):\n- User A sends 100 bytes: finish_time = 0 + 100/2 = 50\n- User B sends 100 bytes: finish_time = 0 + 100/1 = 100\n- User C sends 100 bytes: finish_time = 0 + 100/1 = 100\n\nOrder: A first (finish=50), then B or C (finish=100)\n```\n\n\n\n| ##### Pros | ##### Cons |\n| --- | --- |\n| Proportional fairness | O(log N) per packet |\n| No starvation | Requires per-flow state |\n| Work-conserving | Complex implementation |\n\n\n**Best for:** Network bandwidth allocation, multi-tenant APIs\n\n---\n\n### Algorithm 4: Deficit Round Robin (DRR)\n\nSimpler alternative to WFQ with O(1) complexity.\n\n\n```mermaid\nflowchart LR\n subgraph Queues[\"Queues with Deficits\"]\n Q1[\"Queue A
Quantum: 500
Deficit: 0\"]:::primary\n Q2[\"Queue B
Quantum: 500
Deficit: 0\"]:::secondary\n Q3[\"Queue C
Quantum: 500
Deficit: 0\"]:::purple\n end\n\n RR[\"Round Robin
Scheduler\"]:::orange\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef secondary fill:#38d9a9,stroke:#000,color:#000\n classDef purple fill:#9775fa,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n```\n\n\n**How It Works:**\n\n1. Each queue has a \"quantum\" (bytes allowed per round)\n2. Each queue tracks a \"deficit counter\"\n3. In each round, add quantum to deficit\n4. Send packets while deficit >= packet size\n5. Subtract packet size from deficit\n6. Leftover deficit carries to next round\n\n\n```shell\nRound 1:\n- Queue A: deficit=500, packet=300, send it, deficit=200\n- Queue A: deficit=200, packet=300, can't send, keep deficit\n- Queue B: deficit=500, packet=100, send it, deficit=400\n- Queue B: deficit=400, packet=100, send it, deficit=300\n...\n\nQueue A's 200 deficit carries over, compensating next round\n```\n\n\n\n| ##### Pros | ##### Cons |\n| --- | --- |\n| O(1) per packet | Less precise than WFQ |\n| Simple implementation | Fairness at round granularity |\n| Low memory | Not ideal for variable packet sizes |\n\n\n**Best for:** High-speed networking, simple fair scheduling\n\n---\n\n### Algorithm 5: Lottery Scheduling\n\nRandomized fairness through probabilistic ticket allocation.\n\n\n```mermaid\nflowchart TD\n subgraph Tickets[\"Ticket Allocation\"]\n U1[\"User A
50 tickets\"]:::primary\n U2[\"User B
30 tickets\"]:::secondary\n U3[\"User C
20 tickets\"]:::purple\n end\n\n Lottery[\"Random Draw
Total: 100 tickets\"]:::orange\n\n subgraph Probability[\"Win Probability\"]\n P1[\"A: 50%\"]:::primary\n P2[\"B: 30%\"]:::secondary\n P3[\"C: 20%\"]:::purple\n end\n\n Tickets --> Lottery\n Lottery --> Probability\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef secondary fill:#38d9a9,stroke:#000,color:#000\n classDef purple fill:#9775fa,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n```\n\n\n**How It Works:**\n\n1. Each user holds tickets proportional to their share\n2. On each scheduling decision, draw a random ticket\n3. Ticket holder wins that round\n4. Over time, wins converge to ticket proportions\n\n**Ticket Operations:**\n\n\n| ##### Operation | ##### Use Case |\n| --- | --- |\n| **Ticket transfer** | Donate priority to child process |\n| **Ticket inflation** | Trusted users can create tickets |\n| **Ticket currencies** | Hierarchical resource allocation |\n\n\n\n| ##### Pros | ##### Cons |\n| --- | --- |\n| Probabilistically fair | Short-term variance |\n| Flexible ticket operations | Not deterministic |\n| Simple implementation | May need many draws to converge |\n\n\n**Best for:** CPU scheduling, resource allocation, flash sale access\n\n---\n\n### Algorithm 6: Max-Min Fairness\n\nMaximize the minimum allocation across all users.\n\n\n```mermaid\nflowchart TD\n subgraph Demands[\"User Demands\"]\n D1[\"User A wants 10\"]:::primary\n D2[\"User B wants 30\"]:::primary\n D3[\"User C wants 100\"]:::primary\n end\n\n Total[\"Total Available: 60\"]:::orange\n\n subgraph MaxMin[\"Max-Min Allocation\"]\n A1[\"A gets 10
(fully satisfied)\"]:::green\n A2[\"B gets 25
(shares remainder)\"]:::secondary\n A3[\"C gets 25
(shares remainder)\"]:::secondary\n end\n\n Demands --> Total\n Total --> MaxMin\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n classDef secondary fill:#38d9a9,stroke:#000,color:#000\n```\n\n\n**How It Works:**\n\n1. Start with equal allocation to all users\n2. If a user needs less, give them what they need\n3. Redistribute surplus to users who need more\n4. Repeat until no more redistribution possible\n\n\n```shell\nExample: 60 units, 3 users want [10, 30, 100]\n\nRound 1: Equal split = 20 each\n- User A wants 10, gets 10, surplus = 10\n- Redistribute 10 to B and C\n\nRound 2: B and C split 50\n- B wants 30, gets 25\n- C wants 100, gets 25\n\nFinal: A=10, B=25, C=25\n```\n\n\n\n| ##### Pros | ##### Cons |\n| --- | --- |\n| No user gets less than fair share | Complex computation |\n| Maximizes minimum allocation | May not maximize utilization |\n| Pareto optimal | Requires global knowledge |\n\n\n**Best for:** Bandwidth allocation, cluster resource scheduling\n\n---\n\n## System Architecture\n\n### Multi-Tenant Rate Limiting\n\n\n```mermaid\nflowchart TB\n subgraph Clients[\"Tenants\"]\n T1[\"Tenant A\"]:::rose\n T2[\"Tenant B\"]:::rose\n T3[\"Tenant C\"]:::rose\n end\n\n subgraph Gateway[\"API Gateway\"]\n Auth[\"Authentication\"]:::secondary\n RL[\"Rate Limiter\"]:::orange\n Quota[\"Quota Manager\"]:::orange\n end\n\n subgraph RateLimitStore[\"Rate Limit State\"]\n Redis[(Redis Cluster
Token buckets)]:::purple\n end\n\n subgraph Backend[\"Backend Services\"]\n API[\"API Servers\"]:::primary\n end\n\n T1 --> Auth\n T2 --> Auth\n T3 --> Auth\n Auth --> RL\n RL --> Quota\n RL <--> Redis\n Quota --> API\n\n classDef rose fill:#f783ac,stroke:#000,color:#000\n classDef secondary fill:#38d9a9,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef purple fill:#9775fa,stroke:#000,color:#000\n classDef primary fill:#00ceff,stroke:#000,color:#000\n```\n\n\n### Hierarchical Rate Limiting\n\n\n```mermaid\nflowchart TD\n subgraph Global[\"Global Limit: 100K/sec\"]\n subgraph Org[\"Org Limit: 10K/sec\"]\n subgraph Team[\"Team Limit: 1K/sec\"]\n User[\"User Limit: 100/sec\"]:::green\n end\n end\n end\n\n Request[\"Request\"]:::primary\n\n Check[\"Check all levels
Must pass all\"]:::orange\n\n Request --> Global\n Global --> Check\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n```\n\n\nA request must pass rate limits at every level of the hierarchy.\n\n### Distributed Rate Limiting\n\n\n```mermaid\nflowchart TD\n subgraph Nodes[\"API Gateway Nodes\"]\n N1[\"Node 1\"]:::primary\n N2[\"Node 2\"]:::primary\n N3[\"Node 3\"]:::primary\n end\n\n subgraph Approaches[\"Synchronization Approaches\"]\n Local[\"Local Only
Inaccurate but fast\"]:::secondary\n Central[\"Central Store
Accurate but latency\"]:::secondary\n Gossip[\"Gossip Sync
Eventually accurate\"]:::secondary\n end\n\n Nodes --> Approaches\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef secondary fill:#38d9a9,stroke:#000,color:#000\n```\n\n\n\n| ##### Approach | ##### Accuracy | ##### Latency | ##### Complexity |\n| --- | --- | --- | --- |\n| **Local only** | Poor (N× actual limit) | Lowest | Simple |\n| **Central Redis** | Exact | +1-5ms per request | Medium |\n| **Sliding window log** | Exact | +1-5ms | Medium |\n| **Gossip/eventual** | Good enough | Low | Complex |\n\n\n---\n\n### Fair Queue System (Ticket Sales)\n\n\n```mermaid\nflowchart TB\n subgraph Users[\"Incoming Users\"]\n U1[\"User 1\"]:::rose\n U2[\"User 2\"]:::rose\n U3[\"User N\"]:::rose\n end\n\n subgraph WaitingRoom[\"Virtual Waiting Room\"]\n Queue[\"Fair Queue
Random position assignment\"]:::orange\n Timer[\"Position + ETA display\"]:::secondary\n end\n\n subgraph Admission[\"Admission Control\"]\n Admit[\"Admit N users/minute
Based on capacity\"]:::primary\n end\n\n subgraph Purchase[\"Purchase Flow\"]\n Buy[\"Complete purchase
Time-limited session\"]:::green\n end\n\n Users --> WaitingRoom\n WaitingRoom --> Admission\n Admission --> Purchase\n\n classDef rose fill:#f783ac,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef secondary fill:#38d9a9,stroke:#000,color:#000\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n```\n\n\n**Fairness Mechanisms:**\n\n\n| ##### Mechanism | ##### Purpose |\n| --- | --- |\n| **Random queue position** | Arrival time doesn't determine success |\n| **Verified fan program** | Priority for proven fans |\n| **Purchase limits** | Max tickets per person |\n| **Bot detection** | CAPTCHA, device fingerprinting |\n| **Time-limited sessions** | Can't hold spot indefinitely |\n\n\n---\n\n## Domain-Specific Deep Dives\n\n### Cloud Multi-Tenancy (AWS-style)\n\n\n```mermaid\nflowchart TD\n subgraph Tenants[\"Tenants on Shared Infrastructure\"]\n T1[\"Tenant A
Light usage\"]:::green\n T2[\"Tenant B
Spike!\"]:::red\n T3[\"Tenant C
Normal\"]:::green\n end\n\n subgraph Isolation[\"Fairness Layers\"]\n Compute[\"Compute Isolation
CPU credits, throttling\"]:::primary\n Network[\"Network Isolation
Bandwidth limits\"]:::primary\n Storage[\"Storage Isolation
IOPS limits\"]:::primary\n API[\"API Isolation
Request rate limits\"]:::primary\n end\n\n Tenants --> Isolation\n\n classDef green fill:#69db7c,stroke:#000,color:#000\n classDef red fill:#ff8787,stroke:#000,color:#000\n classDef primary fill:#00ceff,stroke:#000,color:#000\n```\n\n\n**AWS Fairness Mechanisms:**\n\n\n| ##### Resource | ##### Fairness Mechanism |\n| --- | --- |\n| **EC2 CPU** | CPU credits (burstable), dedicated instances |\n| **EBS IOPS** | Provisioned IOPS, burst balance |\n| **Network** | Baseline + burst bandwidth per instance |\n| **API calls** | Token bucket per service per account |\n| **Lambda** | Concurrency limits per account |\n\n\n**Credit-Based CPU Fairness:**\n\n\n```shell\nT2/T3 Burstable Instances:\n\nBaseline: 20% CPU (earns credits when below)\nCredits: Earned when idle, spent when bursting\nMax credits: 576 (24 hours of earning)\n\nFair behavior:\n- Light user: Accumulates credits, can burst when needed\n- Heavy user: Burns credits, throttled to baseline\n- All users get fair baseline, burst is earned\n```\n\n\n---\n\n### Content Platform Fairness (TikTok-style)\n\n\n```mermaid\nflowchart TD\n subgraph Creators[\"Creator Pool\"]\n Big[\"Big Creator
1M followers\"]:::primary\n Medium[\"Medium Creator
10K followers\"]:::secondary\n New[\"New Creator
0 followers\"]:::purple\n end\n\n subgraph Fairness[\"Fairness Mechanisms\"]\n Explore[\"Exploration Pool
Test new content\"]:::orange\n Quality[\"Quality Signals
Watch time, shares\"]:::orange\n Diversity[\"Diversity Rules
Mix of creators\"]:::orange\n end\n\n subgraph Feed[\"User Feed\"]\n Mix[\"Balanced Mix
Popular + New + Diverse\"]:::green\n end\n\n Creators --> Fairness\n Fairness --> Feed\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef secondary fill:#38d9a9,stroke:#000,color:#000\n classDef purple fill:#9775fa,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n```\n\n\n**Creator Fairness Strategies:**\n\n\n| ##### Strategy | ##### How It Works |\n| --- | --- |\n| **Initial boost** | New content gets baseline impressions |\n| **Quality-based scaling** | Good engagement = more distribution |\n| **Diversity injection** | Mix of creator sizes in every feed |\n| **Topic fairness** | Don't let one topic dominate |\n| **Time decay** | Older content gets less priority |\n\n\n**Exploration vs Exploitation:**\n\n\n```shell\nEvery feed should contain:\n- 70% Exploitation: Content likely to engage user\n- 20% Exploration: Test new/unfamiliar content\n- 10% Diversity: Ensure variety\n\nThis gives new creators a fair shot at discovery\nwhile still optimizing for user engagement.\n```\n\n\n---\n\n### Auction Fairness (Ad Bidding)\n\n\n```mermaid\nflowchart TD\n subgraph Bidders[\"Advertisers\"]\n Big[\"Big Advertiser
$10 bid\"]:::primary\n Small[\"Small Advertiser
$2 bid\"]:::secondary\n end\n\n subgraph Auction[\"Auction Mechanism\"]\n GSP[\"Generalized Second Price
Winner pays 2nd price + $0.01\"]:::orange\n Quality[\"Quality Score
Relevance matters\"]:::orange\n Reserve[\"Reserve Price
Minimum threshold\"]:::orange\n end\n\n subgraph Result[\"Fair Outcomes\"]\n Win[\"Higher bid wins
but overpaying prevented\"]:::green\n Chance[\"Quality can beat budget\"]:::green\n end\n\n Bidders --> Auction\n Auction --> Result\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef secondary fill:#38d9a9,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n```\n\n\n**Ad Rank Formula:**\n\n\n```shell\nAd Rank = Bid × Quality Score\n\nExample:\n- Big advertiser: $10 × 0.5 quality = 5.0 rank\n- Small advertiser: $2 × 3.0 quality = 6.0 rank\n\nSmall advertiser wins with better quality!\n```\n\n\n**Fairness Mechanisms:**\n\n\n| ##### Mechanism | ##### Purpose |\n| --- | --- |\n| **Second-price auction** | Winners don't overpay |\n| **Quality score** | Relevance matters, not just budget |\n| **Budget pacing** | Spread spend evenly over time |\n| **Frequency caps** | Limit how often same user sees ad |\n| **Auction diversity** | Don't always show same advertiser |\n\n\n---\n\n### Job Scheduling Fairness (Kubernetes/YARN)\n\n\n```mermaid\nflowchart TD\n subgraph Cluster[\"Cluster Resources\"]\n CPU[\"1000 CPU cores\"]:::primary\n Mem[\"4 TB Memory\"]:::primary\n end\n\n subgraph Queues[\"Hierarchical Queues\"]\n Root[\"Root Queue
100%\"]:::secondary\n\n Prod[\"Production
60%\"]:::orange\n Dev[\"Development
30%\"]:::purple\n Test[\"Testing
10%\"]:::rose\n end\n\n subgraph Scheduler[\"Fair Scheduler\"]\n DRF[\"Dominant Resource Fairness\"]:::green\n end\n\n Cluster --> Queues\n Queues --> Scheduler\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef secondary fill:#38d9a9,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef purple fill:#9775fa,stroke:#000,color:#000\n classDef rose fill:#f783ac,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n```\n\n\n**Dominant Resource Fairness (DRF):**\n\nWhen jobs need multiple resources (CPU + memory), which dimension determines fairness?\n\n\n```shell\nCluster: 100 CPUs, 100 GB RAM\nUser A job needs: 1 CPU, 4 GB RAM (memory-heavy)\nUser B job needs: 3 CPU, 1 GB RAM (CPU-heavy)\n\nTraditional: Who gets more jobs?\n\nDRF approach:\n- User A's dominant resource: RAM (4% per job)\n- User B's dominant resource: CPU (3% per job)\n- Equalize dominant resource usage\n\nResult: A runs 25 jobs (100% RAM), B runs 33 jobs (99% CPU)\nBoth users consume equal share of their dominant resource.\n```\n\n\n---\n\n### Network QoS Fairness\n\n\n```mermaid\nflowchart LR\n subgraph Traffic[\"Traffic Classes\"]\n Voice[\"Voice
Low latency required\"]:::red\n Video[\"Video
High bandwidth\"]:::orange\n Data[\"Data
Best effort\"]:::secondary\n end\n\n subgraph QoS[\"QoS Mechanisms\"]\n Priority[\"Priority Queuing\"]:::primary\n Shaping[\"Traffic Shaping\"]:::primary\n Reserve[\"Bandwidth Reservation\"]:::primary\n end\n\n subgraph Output[\"Fair Allocation\"]\n V1[\"Voice: Guaranteed 10%\"]:::red\n V2[\"Video: Guaranteed 50%\"]:::orange\n V3[\"Data: Remaining 40%\"]:::secondary\n end\n\n Traffic --> QoS\n QoS --> Output\n\n classDef red fill:#ff8787,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef secondary fill:#38d9a9,stroke:#000,color:#000\n classDef primary fill:#00ceff,stroke:#000,color:#000\n```\n\n\n**Weighted Fair Queuing in Networks:**\n\n\n| ##### Traffic Class | ##### Weight | ##### Guaranteed Bandwidth |\n| --- | --- | --- |\n| Voice (EF) | 1 | 10 Mbps |\n| Video (AF) | 5 | 50 Mbps |\n| Best Effort | 4 | 40 Mbps |\n\n\nWhen congested, each class gets proportional share. When not congested, unused bandwidth redistributed.\n\n---\n\n## Comparison of Algorithms\n\n\n| ##### Algorithm | ##### Fairness Type | ##### Complexity | ##### Best For |\n| --- | --- | --- | --- |\n| **Token Bucket** | Per-user limits | O(1) | API rate limiting |\n| **Leaky Bucket** | Smoothing | O(1) | Traffic shaping |\n| **WFQ** | Weighted proportional | O(log N) | Network bandwidth |\n| **DRR** | Weighted proportional | O(1) | High-speed networking |\n| **Lottery** | Probabilistic | O(1) | CPU scheduling |\n| **Max-Min** | Maximize minimum | O(N²) | Resource allocation |\n| **DRF** | Multi-resource | O(N) | Cluster scheduling |\n\n\n---\n\n## Metrics and Monitoring\n\n### Key Fairness Metrics\n\n\n| ##### Metric | ##### Description | ##### Target |\n| --- | --- | --- |\n| **Jain's Fairness Index** | 0-1 measure of allocation fairness | > 0.9 |\n| **Max/Min Ratio** | Ratio of largest to smallest share | < 2x |\n| **Starvation Rate** | % of users getting 0 service | 0% |\n| **Wait Time Variance** | Consistency of wait times | Low |\n| **Quota Utilization** | How much of quota is used | Track distribution |\n\n\n**Jain's Fairness Index:**\n\n\n```shell\nJ(x) = (Σxi)² / (n × Σxi²)\n\nWhere xi is the allocation to user i, n is number of users\n\nJ = 1.0: Perfect fairness (all equal)\nJ = 1/n: Worst case (one user gets everything)\n\nExample:\n- [25, 25, 25, 25]: J = 1.0 (perfect)\n- [10, 20, 30, 40]: J = 0.9 (good)\n- [0, 0, 0, 100]: J = 0.25 (unfair)\n```\n\n\n### Monitoring Dashboard\n\n\n```mermaid\nflowchart LR\n subgraph Metrics[\"Real-time Metrics\"]\n Rate[\"Request rates
per tenant\"]:::primary\n Reject[\"Rejection rates
per tenant\"]:::primary\n Wait[\"Wait times
distribution\"]:::primary\n Usage[\"Quota usage
per tenant\"]:::primary\n end\n\n subgraph Alerts[\"Alerting\"]\n Starve[\"Starvation detected\"]:::red\n Abuse[\"Abuse pattern\"]:::red\n Unfair[\"Fairness index drop\"]:::orange\n end\n\n Metrics --> Alerts\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef red fill:#ff8787,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n```\n\n\n---\n\n## System Design Interview Tips\n\n### 1. Clarify Requirements\n\n\n| ##### Question | ##### Why It Matters |\n| --- | --- |\n| What resource needs fair allocation? | Determines algorithm choice |\n| What is \"fair\" in this context? | Equal vs proportional vs weighted |\n| What is the tenant/user model? | Per-user, per-org, hierarchical |\n| What is the request pattern? | Bursty vs steady affects algorithm |\n| What is acceptable overhead? | Latency budget for fairness checks |\n\n\n### 2. Start with the Problem\n\nAlways describe what unfairness you're preventing:\n\n\n> **INFO**\n>\n> \"Without fairness controls, a single tenant could consume all our API capacity, causing latency spikes for everyone else. We need per-tenant rate limiting with fair queuing to ensure equitable access.\"\n\n\n### 3. Design for Tiers\n\n\n```mermaid\nflowchart LR\n Free[\"Free Tier
100 req/min\"]:::secondary\n Pro[\"Pro Tier
1000 req/min\"]:::primary\n Enterprise[\"Enterprise
10000 req/min\"]:::purple\n\n Free --> Pro --> Enterprise\n\n classDef secondary fill:#38d9a9,stroke:#000,color:#000\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef purple fill:#9775fa,stroke:#000,color:#000\n```\n\n\n### 4. Mention Trade-offs\n\n\n| ##### Trade-off | ##### Considerations |\n| --- | --- |\n| Fairness vs Throughput | Strict fairness may reduce total capacity |\n| Accuracy vs Latency | Distributed rate limiting adds latency |\n| Simplicity vs Precision | Token bucket is simpler than WFQ |\n| Memory vs Fairness | Per-user state scales with users |\n\n\n### 5. Reference Real Systems\n\n- \"AWS uses token buckets for API rate limiting with per-account quotas\"\n- \"Linux uses Completely Fair Scheduler (CFS) for CPU time\"\n- \"Kubernetes uses Dominant Resource Fairness for pod scheduling\"\n- \"Ticketmaster uses virtual waiting rooms with randomized queues\"\n\n---\n\n## Summary\n\n\n```mermaid\nflowchart TD\n Start[\"Fairness Pattern\"]:::primary\n\n subgraph Algorithms[\"Key Algorithms\"]\n Token[\"Token Bucket\"]:::secondary\n WFQ[\"Weighted Fair Queuing\"]:::secondary\n Lottery[\"Lottery Scheduling\"]:::secondary\n MaxMin[\"Max-Min Fairness\"]:::secondary\n DRF[\"Dominant Resource Fairness\"]:::secondary\n end\n\n subgraph Principles[\"Key Principles\"]\n NoStarve[\"No Starvation\"]:::orange\n Proportional[\"Proportional Shares\"]:::orange\n WorkConserve[\"Work Conservation\"]:::orange\n Abuse[\"Abuse Prevention\"]:::orange\n end\n\n subgraph UseCases[\"Use Cases\"]\n RateLimit[\"Rate Limiting\"]:::green\n MultiTenant[\"Multi-Tenant\"]:::green\n Scheduling[\"Job Scheduling\"]:::green\n Network[\"Network QoS\"]:::green\n Tickets[\"Ticket Sales\"]:::green\n end\n\n Start --> Algorithms\n Algorithms --> Principles\n Principles --> UseCases\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef secondary fill:#38d9a9,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n```\n\n\n**Key Takeaways:**\n\n1. **Fairness is policy-driven.** Equal, proportional, weighted, or max-min depends on business requirements.\n\n1. **Token bucket is your default.** For most rate limiting scenarios, token bucket with per-user buckets is the right choice.\n\n1. **Prevent starvation.** Any fairness mechanism must ensure no user gets zero service indefinitely.\n\n1. **Work conservation matters.** Unused quota should benefit others, not go to waste.\n\n1. **Abuse is inevitable.** Design for bad actors: multi-account abuse, bots, gaming the system.\n\n1. **Measure fairness.** Use Jain's Fairness Index, max/min ratios, and starvation rates to quantify.\n\n---\n\n## References\n\n- [Token Bucket and Leaky Bucket Algorithms](https://www.rfc-editor.org/rfc/rfc2697.html) - IETF RFC on traffic metering\n- [Weighted Fair Queuing](https://www2.cs.duke.edu/courses/fall13/cps296.5/papers/wfq.pdf) - Original WFQ paper by Demers, Keshav, Shenker\n- [Dominant Resource Fairness](https://cs.stanford.edu/~matei/papers/2011/nsdi_drf.pdf) - Berkeley paper on multi-resource fairness\n- [Lottery Scheduling](https://www.usenix.org/legacy/publications/library/proceedings/osdi/full_papers/waldspurger.pdf) - Waldspurger and Weihl's randomized scheduling\n- [Completely Fair Scheduler](https://www.kernel.org/doc/html/latest/scheduler/sched-design-CFS.html) - Linux kernel CFS documentation\n- [AWS Service Quotas](https://docs.aws.amazon.com/general/latest/gr/aws_service_limits.html) - How AWS implements rate limiting\n\n---\n\nThank you for reading!\n\nIf you found it valuable, hit a like and consider subscribing for more such content every week.\n\nIf you have any questions or suggestions, leave a comment.\n\nThis post is public so feel free to share it.\n\n[Share](https://blog.algomaster.io/)\n\n---\n\n**P.S.** If you're enjoying this newsletter and want to get even more value, consider becoming a **[paid subscriber](https://blog.algomaster.io/subscribe)**.\n\nAs a paid subscriber, you'll unlock all **premium articles** and gain full access to all **[premium courses](https://algomaster.io/newsletter/paid/resources)** on **[algomaster.io](https://algomaster.io)**.\n\n[Unlock Full Access](https://blog.algomaster.io/subscribe)\n\n**There are [group discounts](https://blog.algomaster.io/subscribe?group=true), [gift options](https://blog.algomaster.io/subscribe?gift=true), and [referral bonuses](https://blog.algomaster.io/leaderboard) available.**\n\n---\n\nCheckout my **[Youtube channel](https://www.youtube.com/@ashishps_1/videos)** for more in-depth content.\n\nFollow me on **[LinkedIn](https://www.linkedin.com/in/ashishps1/)** and **[X](https://twitter.com/ashishps_1)** to stay updated.\n\nCheckout my **[GitHub repositories](https://github.com/ashishps1)** for free interview preparation resources.\n\nI hope you have a lovely day!\n\nSee you soon,\n\nAshish\n\n---\n\n# Quiz","pageType":"system-design-interviews"}

Fairness Pattern in System Design

Ashish Pratap Singh

Get Premium