Local, low-volume message passing for massively distributed cellular automata

Question

I'm working on developing a simulation using massively distributed cellular automata. Cell simulations are distributed across nodes and coordinated using ZooKeeper. Persistent data is stored in Riak. The cellular automata themselves are written in Python.

It would be very convenient for my simulation if a cell could pass a low volume (between several and tens per second, say) of messages (probably key-value pairs) to its immediate neighbors (Manhattan neighborhood). However, for a simulation of millions of cells, the naïve approach ends up with millions of little mailboxes, one for each cell, and a slow trickle of messages into each box. This brings ZooKeeper or RabbitMQ to its knees! I've been recommended DDS, but it appears to be very Enterprise, and no Python bindings that I can find.

I'm new to distributed systems development--this is really just a hobby project to see how far I can get. I can't help but feel that I'm going about this the wrong way, turning to a monolithic message bus for each little cell's mailbox. It's easy for a cell to determine its neighbors and its place in the world, so it seems like the message passing ought to be susceptible to some kind of chunking. The design of this regional actor and how it would communicate with the individual cells escapes me, however. I see how the cells could pass messages to the chunk via a message bus, but how would the chunk pass messages back to the cell?

Am I heading anywhere near a real solution to this problem? What's the proper way for distributed nodes to pass low-volume messages to its neighbors?

Answer 1

I'm not sure how durable you need these messages; and by your description it doesn't appear you have any ordering constraints for messages from different cells. I would think that you do want a total ordering for all messages sent from the same cell a to the same cell b.

ZooKeeper gets swamped because it provides a global total ordering on all messages. I'm unsure exactly what type of coordination your system needs via Zookeeper, but it works best with course-grained coordination rather than fine-grained coordination. (Where I work, we call this role locking and resource locking respectively to clarify the intent. A worker takes on a role instead of locking a resource.)

So, here are a few ideas with what information I have.

If the messages don't need to be durable, the best approach would be to keep a connection to your neighbors and send the messages directly to them. I'm assuming 2D or 3D, so number of (Manhattan) neighbors is small.

The rest of this will assume you need durability.

A single message queue-system should be able to handle millions of messages; but they get better performance if they are partitioned somewhat.

Far starters, try sending all the messages to the same queue. Have a few workers (chosen by ZooKeeper) pull the messages off the queue and send them to their destination cell (requiring an ack from the cell before acking to the queue). You could also a have set of workers receive the messages from the cells to put in the queue. Basically, this is helping with the contention on the queue.

[  Router ]--->[ Queue ]--->[  Router  ]
 ^   ^   ^                   |   |   |
 |   |   |                   V   V   V
[A] [B] [C]                 [D] [E] [F]

Now you can generalize this a bit and have a queue per region. (Queues work better when they have less messages to work through.) Have one or more routers per region.

        ,----->[ QueueA ]<------.
        |                       |   (Note which arrows are bi-directional)
        V                       |
[ RouterA ]--->[ QueueB ]<--->[ RouterB ]
 ^   ^   ^                     ^   ^   ^
 |   |   |                     |   |   |
 V   V   V                     V   V   V
[A] [B] [C]                   [D] [E] [F]

If the messaging system is still swamped, you could replace the queue in the diagram above with an entire message-queue system.

These are some simple ideas, not knowing the actual domain, to hopefully point you in a good direction.

By the way, you might want to research Twitter's architecture (past and present) because they have basically millions of mailboxes, one for each cellular automaton (aka person).

Answer 2

One idea I'm toying around with:

I've read in several places of folks using ZooKeeper as an alternative to DNS for internal systems. As simulation worker processes already register with ZooKeeper which cell simulations they are responsible for, I imagine it shouldn't be too far afield to also register an IP and port they will respond to, then use ZeroMQ to set up P2P message passing between cells. This is still a rough sketch.