Fairness Pattern in System Design
Fairness Pattern in System Design
How 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?
The 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.
This 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.
In 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.
If you're enjoying this newsletter and want to get even more value, consider becoming a [paid subscriber](https://blog.algomaster.io/subscribe).
As 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).
What is Fairness?
Fairness in system design means ensuring that resources, access, or opportunities are distributed equitably among users or tenants according to defined policies.
Fairness is not always about equal distribution. It's about appropriate distribution based on policies:
Where Fairness Is Used
Core Challenges
1. The Noisy Neighbor Problem
One tenant's excessive usage degrades performance for others sharing the same infrastructure.
Solutions:
- Per-tenant resource quotas
- Isolation boundaries (separate pools)
- Throttling and admission control
- Fair queuing algorithms
2. The Thundering Herd Problem
Many users simultaneously compete for limited resources (concert tickets, flash sales, new product launches).
Solutions:
- Queuing with random selection
- Lottery/raffle systems
- Verified fan programs
- Rate limiting + virtual waiting rooms
3. The Starvation Problem
Some users or requests never get served because others continuously take priority.
Solutions:
- Aging (priority increases over time)
- Guaranteed minimum allocation
- Fair share scheduling
- Weighted round-robin
4. The Gaming/Abuse Problem
Users try to exploit fairness mechanisms to gain unfair advantage.
5. Fairness vs Efficiency Trade-off
Strict fairness can reduce overall system throughput.
Example: Strict fairness might give resources to idle users while active users wait.
Fairness Algorithms
Algorithm 1: Token Bucket
Control the rate at which requests are processed with burst capability.
How It Works:
- Bucket starts with N tokens (capacity)
- Tokens are added at rate R per second
- Each request consumes one token
- If no tokens available, request is rejected
- Bucket never exceeds capacity (allows bursts up to capacity)
Parameters:
Best for: API rate limiting, per-user quotas
Algorithm 2: Leaky Bucket
Smooth out bursts by processing at a constant rate.
How It Works:
- Requests enter a fixed-size queue (bucket)
- Requests are processed (leak) at constant rate
- If bucket is full, new requests are dropped
- Output is always smooth, regardless of input pattern
Comparison with Token Bucket:
Best for: Traffic shaping, smoothing request patterns
Algorithm 3: Weighted Fair Queuing (WFQ)
Allocate bandwidth proportionally to weights.
How It Works:
- Each user/flow has a separate queue
- Each queue has a weight (entitlement)
- Scheduler serves queues proportionally to weights
- Empty queues' share redistributed to active queues
Virtual Time Calculation:
Best for: Network bandwidth allocation, multi-tenant APIs
Algorithm 4: Deficit Round Robin (DRR)
Simpler alternative to WFQ with O(1) complexity.
How It Works:
- Each queue has a "quantum" (bytes allowed per round)
- Each queue tracks a "deficit counter"
- In each round, add quantum to deficit
- Send packets while deficit >= packet size
- Subtract packet size from deficit
- Leftover deficit carries to next round
Best for: High-speed networking, simple fair scheduling
Algorithm 5: Lottery Scheduling
Randomized fairness through probabilistic ticket allocation.
How It Works:
- Each user holds tickets proportional to their share
- On each scheduling decision, draw a random ticket
- Ticket holder wins that round
- Over time, wins converge to ticket proportions
Ticket Operations:
Best for: CPU scheduling, resource allocation, flash sale access
Algorithm 6: Max-Min Fairness
Maximize the minimum allocation across all users.
How It Works:
- Start with equal allocation to all users
- If a user needs less, give them what they need
- Redistribute surplus to users who need more
- Repeat until no more redistribution possible
Best for: Bandwidth allocation, cluster resource scheduling
System Architecture
Multi-Tenant Rate Limiting
Hierarchical Rate Limiting
A request must pass rate limits at every level of the hierarchy.
Distributed Rate Limiting
Fair Queue System (Ticket Sales)
Fairness Mechanisms:
Domain-Specific Deep Dives
Cloud Multi-Tenancy (AWS-style)
AWS Fairness Mechanisms:
Credit-Based CPU Fairness:
Content Platform Fairness (TikTok-style)
Creator Fairness Strategies:
Exploration vs Exploitation:
Auction Fairness (Ad Bidding)
Ad Rank Formula:
Fairness Mechanisms:
Job Scheduling Fairness (Kubernetes/YARN)
Dominant Resource Fairness (DRF):
When jobs need multiple resources (CPU + memory), which dimension determines fairness?
Network QoS Fairness
Weighted Fair Queuing in Networks:
When congested, each class gets proportional share. When not congested, unused bandwidth redistributed.
Comparison of Algorithms
Metrics and Monitoring
Key Fairness Metrics
Jain's Fairness Index:
Monitoring Dashboard
System Design Interview Tips
1. Clarify Requirements
2. Start with the Problem
Always describe what unfairness you're preventing:
"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."
3. Design for Tiers
4. Mention Trade-offs
5. Reference Real Systems
- "AWS uses token buckets for API rate limiting with per-account quotas"
- "Linux uses Completely Fair Scheduler (CFS) for CPU time"
- "Kubernetes uses Dominant Resource Fairness for pod scheduling"
- "Ticketmaster uses virtual waiting rooms with randomized queues"
Summary
Key Takeaways:
- Fairness is policy-driven. Equal, proportional, weighted, or max-min depends on business requirements.
- Token bucket is your default. For most rate limiting scenarios, token bucket with per-user buckets is the right choice.
- Prevent starvation. Any fairness mechanism must ensure no user gets zero service indefinitely.
- Work conservation matters. Unused quota should benefit others, not go to waste.
- Abuse is inevitable. Design for bad actors: multi-account abuse, bots, gaming the system.
- Measure fairness. Use Jain's Fairness Index, max/min ratios, and starvation rates to quantify.
References
- Token Bucket and Leaky Bucket Algorithms - IETF RFC on traffic metering
- Weighted Fair Queuing - Original WFQ paper by Demers, Keshav, Shenker
- Dominant Resource Fairness - Berkeley paper on multi-resource fairness
- Lottery Scheduling - Waldspurger and Weihl's randomized scheduling
- Completely Fair Scheduler - Linux kernel CFS documentation
- AWS Service Quotas - How AWS implements rate limiting
Thank you for reading!
If you found it valuable, hit a like and consider subscribing for more such content every week.
If you have any questions or suggestions, leave a comment.
This post is public so feel free to share it.
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).
As 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).
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.
Checkout my [Youtube channel](https://www.youtube.com/@ashishps_1/videos) for more in-depth content.
Follow me on [LinkedIn](https://www.linkedin.com/in/ashishps1/) and [X](https://twitter.com/ashishps_1) to stay updated.
Checkout my [GitHub repositories](https://github.com/ashishps1) for free interview preparation resources.
I hope you have a lovely day!
See you soon,
Ashish
Quiz
Fairness Quiz
20 quizzes