We’ve been experimenting lately with methods of scaling Orbited horizontally. Orbited is a cross-platform/cross-language distributed Comet server written with libevent and Python. Some time ago we locked down how to do this for a statically-sized cluster: you use a distributed hash function that reliably assigns particular users to particular nodes. Then the application layer can always dispatch a Comet message to the correct user.
The next hurdle is dynamically scaling an Orbited cluster. The root of the problem is that the hashing algorithm will be unreliable in the face of a dynamically resizing cluster. Every time a node joins or leaves the cluster, all users will have to reconnect to the cluster. This is an unacceptable spike in traffic as it represents a self-inflicted DDOS attack.
Some time ago I proposed a project called HaloD with the intent of solving this problem. The basic idea is to pre-allocate a cluster as having an inordinately large size, such as 1024 nodes. Then, using a custom, software-based router, dynamically assign real Orbited nodes to be responsible for a whole range in the table. So if we have a single actual Orbited node, no matter if a user attempts to connect to node 995 or 2, both connections are sent to our single node. When a second node is added, half of those routes are re-assigned to the new node. And half the users are told to reconnect. This method is known as stuffing.
This works out such that 1/N of the total user base must reconnect when a node joins or leaves the cluster, where N is the number of nodes before the change. In theory this works quite well, except that in practice we need to build that custom router. Below is what a HaloD deployment would look like.
Enter DynDNS, a service for providing DNS lookup with a very small TTL (time to live.) Their service costs $27.50 a year for a single domain — a very reasonable price. With DynDNS I can set my TTL literally to one second such that if I make a DNS request for my domain, change the DynDNS configuration, and then immediately make another DNS request, then I’ll have gotten two different IP addresses. This means that we can create 1024 sub-domains that all point at our first node. As more nodes join, we can use the HaloD routing algorithm to change DynDNS configuration so that all users will always be correctly located with the distributed hash function.
This discussion wouldn’t be complete without thinking about executing this whole setup on Amazon’s EC2 service. This service allows you to create virtualized instances of a Linux disk image. In a minute you could start up a hundred Linux machines, and you pay only for what you use ($0.10 per instance-hour.) Our goal with the Orbited project is to provide a clustering option that will run on pay-as-you-go hosting services such as EC2. With this kind of setup, a developer could start an Orbited cluster with a single node, and never worry again about scaling. As demand increased, the cluster would dynamically enlarge. If there was a slack in demand, the cluster would shutdown nodes as needed to avoid unneeded cost.
So this solution isn’t perfect yet. We still need to find a good way to move users from one Orbited node to another. The easiest solution would be to just ask them to reconnect, which would happen automatically with most transports anyway. But if the app reconnects first, then messages will be dispatched to the new destination node before the user moves. I think ultimately the solution will be to use a Comet protocol that supports delivery guarantees, because then the client would just re-request any messages it missed.
Overall, this setup is very compelling for developers who just want to program a Comet app and not worry about deployment or scalability. This would lower the barrier to entry substantially for many existing applications that need to be able to scale to enormous user load right away due to an existing user base. Without a similar setup it’s hard to imagine Facebook or Myspace adding real-time, Comet-based chat, and that needs to be changed.