Algorithm Evolution: 0 to 100M Users

Introduction: The Load Changes Everything

An algorithm that works perfectly for 100 users might crash your server at 1 million users. As traffic grows, the bottleneck shifts from Logic to I/O, then to Network, and finally to Coordination.

Here is how your algorithmic strategy should change as you scale.

Phase 1: The MVP (0 - 10k Users)

Goal: Speed to Market.

• Algorithms: Use whatever is built into your language. Array.sort(), HashMap, List.filter().
• Strategy: Don’t optimize yet. $O(N)$ is fine when $N$ is 1,000.
• Storage: One relational database. Let the DB handle the “Search” and “Sort” using simple B-Tree indexes.

Phase 2: The Growth (10k - 1M Users)

Goal: Response Time (Latency).

• The Problem: Linear scans ($O(N)$) are starting to show up in the “Slow Query Log.”
• Algorithms:
  • Caching: Introduce LRU Cache to avoid database hits.
  • Search: Move from LIKE %query% to Inverted Indexes (Elasticsearch).
  • Optimization: Replace heavy loops with specialized data structures like Prefix Trees (Trie) for search suggestions.

Phase 3: The Scale (1M - 10M Users)

Goal: Throughput & Memory Efficiency.

• The Problem: You can’t fit all data in one server’s RAM.
• Algorithms:
  • Probabilistic: Use Bloom Filters to check if a user exists before querying the DB.
  • Counting: Use HyperLogLog for unique visitor counts to save 99% of memory.
  • Sharding: Use Consistent Hashing to distribute users across multiple database nodes.

Phase 4: Global Scale (10M - 100M+ Users)

Goal: High Availability & Resilience.

• The Problem: Machines fail every day. The network is unreliable.
• Algorithms:
  • Consensus: Use Raft or Paxos to keep configurations consistent across data centers.
  • Traffic Control: Implement Token Bucket rate limiting and Circuit Breakers to prevent cascading failures.
  • Big Data: Use External Sort and MapReduce patterns to process data that is larger than any single disk.

Typical Business Scenarios

• ✅ Leaderboards: Start with SQL ORDER BY. At 1M users, use a Redis ZSet (Skip List). At 100M users, use Shard-based aggregation.
• ✅ Recommendation: Start with simple “Category” filters. Scale to Vector Search (ANN) using HNSW.

Summary

"Scaling is the process of trading simplicity for efficiency. Start simple, but keep the 'Logarithmic Map' in your head so you know when it's time to upgrade."