Day 49: Consistent Hashing Ring with Binary Search Lookup

Building Discord: From Socket to Scale - Phase 4, The Gateway

Part 1: Understanding the Problem

The Spring Boot Trap

Imagine you’re building the next Discord. You have 10 million users connected via WebSocket, and you need to route their connections across multiple server nodes. A junior developer might reach for Spring Cloud LoadBalancer:

@LoadBalanced
@Bean
public WebClient.Builder loadBalancedWebClientBuilder() {
    return WebClient.builder();
}

This code looks clean and simple. It handles load balancing automatically. But it hides a critical flaw that will crash your system at scale.

Here’s what happens: Every time you add or remove a server node (which happens frequently as you scale), Spring’s default load balancer picks a different node for each user’s reconnection. User user_12394875 might connect to server-3 initially, but when they reconnect 10 seconds later, they get routed to server-7.

Why is this a problem? Because your session data (what channels they’re in, their settings, their permissions) is stored on server-3. Now server-7 has to make a database call to fetch that session data. When you have 1 million concurrent users, this creates a 30-second reconnection storm that completely saturates your database with millions of queries.

The real Discord and WhatsApp architectures don’t route connections randomly. They use Consistent Hashing to guarantee that the same user always lands on the same Gateway node (unless that node crashes). This is called session locality, and it reduces database lookups by 95%.

---

Part 2: Why Naive Solutions Fail at Scale

Before we build the right solution, let’s understand why the obvious approaches collapse when you have millions of users.

Approach 1: Simple Modulo-Based Routing

int nodeIndex = Math.abs(userId.hashCode()) % nodeList.size();
Node target = nodeList.get(nodeIndex);

This seems logical: hash the user ID and use modulo to pick a server. But watch what happens when you add one more server:

• With 10 nodes: user_12345 routes to node 5 (12345 % 10 = 5)

• Add an 11th node: user_12345 now routes to node 1 (12345 % 11 = 1)

Adding just one node causes approximately 50% of all your connections to relocate to different servers. Your 5 million active sessions suddenly need to migrate, triggering a cascading failure as nodes frantically swap session state.

Approach 2: Sorting Nodes for Each Request

List<Node> sortedNodes = nodes.stream()
    .sorted(Comparator.comparing(n -> hash(userId + n.id)))
    .toList();
return sortedNodes.get(0); // Pick first

This approach has three fatal problems:

1. O(n log n) sort on every routing decision. At 100,000 requests per second, this burns 40% of your CPU just sorting lists.

2. String concatenation (userId + n.id) allocates new memory on every call. With 100k requests/sec, that’s 1.6 GB per second of garbage being created.

3. Object creation overhead: Java’s hashCode() returns an Integer object (not a primitive), causing even more memory allocations.

The result? Your JVM’s garbage collector triggers a Stop-The-World pause every 2 seconds to clean up this mess. During these pauses, your entire server freezes and can’t process any WebSocket messages.

---