[rabbitmq-discuss] [Q] best way to add a sequencer to the broker

[Ben Hood]

Chuck,

On Tue, Dec 30, 2008 at 3:00 PM, Chuck Remes <cremes.devlist at mac.com> wrote:
> I took a look but my lack of knowledge regarding Erlang made the code
> look like line noise. :)

Yes, well it's only an optimization over the dequeue/enqueue relay.

>> You still have the problem of how to maintain the global counter
>> though.
>
> I don't understand this issue. Do you say this because the deliver/5
> function may be called from many Erlang threads thereby requiring the
> counter to be protected by a mutex? I thought Erlang serialized all
> accesses via messaging to "mailboxes" so these kinds of race
> conditions did not exist.
>
> What is the problem with doing (the Erlang equivalent of):
> global_counter++;

The issue is not thread safety - what you are suggesting is perfectly doable.

The issue is that you have serialized access to a global counter,
which just causes scalability and performance issues.

So will not run into problems because of concurrency, rather you will
run into problems through lack of concurrency because of the big
global lock.

> I am only concerned about the replay order.
>
>> If your application could tolerate some perceived re-ordering, but
>> still replays in the same order, you could request batches of ordering
>> keys from your globally visible state. The effect of this would allow
>> a degree of parallelization at the cost of some stuff *appearing* to
>> have arrived out of the *true* global order. But you could replay in
>> the same order and the things were stamped.
>
> This sounds reasonable.
>
> But let me make sure I am understanding you clearly. You are saying
> that it is possible for messages to be stamped in a different order
> than they were received by the Exchange. Is that the case? Or are you
> saying they may be delivered to queues in a different order than they
> were received by the Exchange?

There's really no such thing as an single instance of an exchange - an
exchange is just the application of a routing rule based an exchange
name and a routing key. Hence this can be evaluated in parallel by
different processes or on different nodes. In contrast to queues,
exchanges are not endpoints where messages land, they are just a
convention to provide coherent routing functionality.

> Off-list I received a message from Alexis who highlighted this issue.
> Apparently the 0-8 AMQP spec does not address any ordering constraints
> except in the case of Queues

This is true and this ties in with what I just said above - there is
no notion of inbound queueing in 0-8 AMQP, just outbound queueing. So
you will get strict ordering by queues but in order (pardon the pun)
to get global inbound ordering, you are going to need to impose a
barrier that each message has to pass through (as indicated above with
the global lock).

Consider the scenario where you have 2 queues bound to one exchange.
If you send 2 messages to the exchange, then each queue instance will
deliver 2 messages to a consumer in the order that they arrived at the
queue. But on the input side, those 2 messages could have been
published on a different channels (or on different nodes). There is no
guarantee that 2 messages sent to the same exchange on different
channels will not get re-ordered - to do so you would have to have
some kind of barrier.

>> Having said that, you might find using plain jane timestamps easier,
>> if you can relax this true global ordering constraint a bit.
>
> Why is a timestamp better? Is it because it pushes the access to a
> "global counter" (in this case the system clock) outside of Erlang?
> Your answer to the earlier ordering questions will likely answer this
> one too.

Yes, there might be some mileage in re-reading the entire thread,
because I think that the conversation does not read entirely linearly.

> I am not opposed to using a timestamp. I thought it would be *simpler*
> (and faster) to use an integer.

Not if this integer has to be atomically incremented across a cluster
(or even between two different channels). This is effectively a global
compare and swap operation which constitutes a very coarse grained
lock.

Using timestamps is cheaper because you don't have any contented
locks. but you get this with a certain degree of inaccuracy. The same
trade-off applies for the bulk counter fetch method I proposed in my
previous post.

At the end of the day I think you have to make the decision to either

a) opt for true ordering and accept the cost (this would be perfectly valid);
b) try to exploit a natural partition in your use case that allows you
to break the global lock down into finer locks;
c) redesign your application to be able to cope with eventual
consistency rather than absolute consistency.

HTH,

Ben