follower-maze: Follower Maze: Total Ordering at the Speed of Sockets

The Total Ordering Nightmare

The Follower Maze is a legendary rite of passage in backend engineering. Originating as a recruitment challenge for SoundCloud, it presents a deceptively simple premise. You have two TCP ports. One receives a chaotic stream of 10 million social events. The other connects to thousands of user clients.

The catch is strict total ordering. Events arrive completely out of sequence, but they must be delivered to clients in perfect numerical order. Most developers reach for heavy-duty frameworks like Akka or Netty to handle the concurrency. The galando/follower-maze project takes a different path.

It is a clean-room Scala implementation that ignores the easy route of actor systems. Instead, it builds a high-performance TCP engine using only standard Java and Scala networking primitives. It treats the JVM like a traffic controller, managing millions of out-of-order events through a custom sliding window buffer.

Architecture of the Sliding Window

The heart of the system is the EventRepository. This component acts as a temporary holding pen for out-of-order packets. When an event arrives out of sequence, it cannot be processed immediately.

The system uses a timed buffer approach. A background ScheduledService wakes up every two seconds. It flushes the repository, sorts the buffered events by their sequence number, and checks if the next expected sequence ID is present.

If the missing piece has arrived, the system processes it and recursively checks for subsequent events. This sliding window prevents the JVM heap from blowing up while ensuring strict adherence to the required sequence.

The Thread-Safe Social Graph

While events are ephemeral, the social graph is persistent. The system must know exactly who follows whom at any given millisecond to route broadcast and status update events correctly.

The UserRepository handles this state. It maps user IDs to active TCP sockets and maintains a graph of followers. To ensure thread safety without choking performance, it relies on Scala's TrieMap.

This concurrent, lock-free hash array mapped trie provides high throughput for the constant reads and writes of user connections. By keeping the entire follower graph in memory, the system avoids the latency penalty of external database lookups.

Preventing the Slow-Client Deadlock

A classic pitfall in socket programming is the slow client. If one user is on a terrible network connection, a naive broadcast loop will block the entire system waiting for that single socket to acknowledge receipt.

The SendEventService sidesteps this trap using Scala's Parallel Collections. When a status update needs to reach thousands of followers, the service uses a ParVector to fan out the socket write operations.

This parallel execution ensures that a single sluggish TCP client does not back up the entire event stream. The main processing loop remains unblocked and ready for the next batch of events.

Bare Metal vs. The Actor Model

How does this manual concurrency approach compare to the standard alternatives? High-level abstractions like Akka offer safety, but they introduce overhead. Building directly on JVM sockets requires more care but yields predictable performance characteristics.