"Resequencing" messages after processing them out-of-order
<p>I'm working on what's basically a highly-available distributed message-passing system. The system receives messages from someplace over HTTP or TCP, perform various transformations on it, and then sends it to one or more destinations (also using TCP/HTTP).</p>

<p>The system has a requirement that all messages sent to a given destination are in-order, because some messages build on the content of previous ones. This limits us to processing the messages sequentially, which takes about 750ms per message. So if someone sends us, for example, one message every 250ms, we're forced to queue the messages behind each other. This eventually introduces intolerable delay in message processing under high load, as each message may have to wait for hundreds of other messages to be processed before it gets its turn.</p>

<p>In order to solve this problem, I want to be able to parallelize our message processing without breaking the requirement that we send them in-order.</p>

<p>We can easily scale our processing horizontally. The missing piece is a way to ensure that, even if messages are processed out-of-order, they are "resequenced" and sent to the destinations in the order in which they were received. I'm trying to find the best way to achieve that.</p>

<p>Apache Camel has <a href="http://camel.apache.org/resequencer.html" rel="noreferrer">a thing called a Resequencer</a> that does this, and it includes a nice diagram (which I don't have enough rep to embed directly). This is exactly what I want: something that takes out-of-order messages and puts them in-order.</p>

<p>But, I don't want it to be written in Java, and I need the solution to be highly available (i.e. resistant to typical system failures like crashes or system restarts) which I don't think Apache Camel offers.</p>

<p>Our application is written in Node.js, with Redis and Postgresql for data persistence. We use the <a href="https://github.com/Automattic/kue" rel="noreferrer">Kue</a> library for our message queues. Although Kue offers priority queueing, the featureset is too limited for the use-case described above, so I think we need an alternative technology to work in tandem with Kue to resequence our messages.</p>

<p>I was trying to research this topic online, and I can't find as much information as I expected. It seems like the type of distributed architecture pattern that would have articles and implementations galore, but I don't see that many. Searching for things like "message resequencing", "out of order processing", "parallelizing message processing", etc. turn up solutions that mostly just relax the "in-order" requirements based on partitions or topics or whatnot. Alternatively, they talk about parallelization on a single machine. I need a solution that:</p>

<ul>
<li>Can handle processing on multiple messages simultaneously in any order.</li>
<li>Will always send messages in the order in which they arrived in the system, no matter what order they were processed in.</li>
<li>Is usable from Node.js</li>
<li>Can operate in a HA environment (i.e. multiple instances of it running on the same message queue at once w/o inconsistencies.)</li>
</ul>

<p>Our current plan, which makes sense to me but which I cannot find described anywhere online, is to use Redis to maintain sets of in-progress and ready-to-send messages, sorted by their arrival time. Roughly, it works like this:</p>

<ol>
<li>When a message is received, that message is put on the in-progress set.</li>
<li>When message processing is finished, that message is put on the ready-to-send set.</li>
<li>Whenever there's the same message at the front of both the in-progress and ready-to-send sets, that message can be sent and it will be in order.</li>
</ol>

<p>I would write a small Node library that implements this behavior with a priority-queue-esque API using atomic Redis transactions. But this is just something I came up with myself, so I am wondering: Are there other technologies (ideally using the Node/Redis stack we're already on) that are out there for solving the problem of resequencing out-of-order messages? Or is there some other term for this problem that I can use as a keyword for research? Thanks for your help!</p>