Re: [RFC v1 06/14] bus1: util - queue utility library

[Tom Gundersen]

On Fri, Oct 28, 2016 at 3:33 PM, Peter Zijlstra <peterz@xxxxxxxxxxxxx> wrote:
> On Fri, Oct 28, 2016 at 01:33:25PM +0200, Tom Gundersen wrote:
>> On Thu, Oct 27, 2016 at 6:43 PM, Peter Zijlstra <peterz@xxxxxxxxxxxxx> wrote:
>> > On Wed, Oct 26, 2016 at 09:18:02PM +0200, David Herrmann wrote:
>> >
>> >> A bus1 message queue is a FIFO, i.e., messages are linearly ordered by
>> >> the time they were sent. Moreover, atomic delivery of messages to
>> >> multiple queues are supported, without any global synchronization, i.e.,
>> >> the order of message delivery is consistent across queues.
>> >>
>> >> Messages can be destined for multiple queues, hence, we need to be
>> >> careful that all queues get a consistent order of incoming messages.
>> >
>> > So I read that to mean that if A and B both send a multi-cast message to
>> > C and D, the messages will appear in the same order for both C and D.
>>
>> That is one of the ordering guarantees, yes.
>>
>> > Why is this important? It seem that this multi-cast ordering generates
>> > much of the complexity of this patch while this Changelog fails to
>> > explain why this is a desired property.
>>
>> I don't think this is the case. The most important guarantee we give
>> is causal ordering.
>
> C and D not observing the message in the same order is consistent with
> causality (and actual physics). The cause is A sending something the
> effect is C receiving something. These two events must be ordered (which
> yields the partial order). But there is no guarantee that different
> observers would observe the same order. Esp. since A and B do not share
> a clock and these events are not in fact ordered themselves.
>
> When we go back to the example of special relativity, as per the paper,
> this is trivially observable if we put A and C together in a frame of
> reference and B and D in a different frame and have the two frames move
> (at a significant fraction of the speed of light) relative to one
> another. The signal, being an emission of light, would not arrive at
> both observers in the same order (if the signal was given sufficiently
> 'simultaneous')
>
>> To make this work with multicast, we must stage messages first, then
>> commit on a second round. That is, we must find some way to iterate
>> over all clocks before committing, but at the same time preventing any
>> races. The multicast-stability as you just described we get for free
>> by introducing the second-level ordering via sender-address.
>
> And this, precisely, is what generates all the complexity found in this
> patch.  You want to strictly provide more than causality, which does
> not, as per the argument above, provide this at all.
>
> You're providing a semi-global ordering of things that are themselves
> not actually ordered.

We are providing two things: causality (as in your physics example
above), and consistency (which, I agree, is cute, but not necessarily
crucial). However, the complexity comes from causality. Consistency is
trivial. The only thing needed for consistency is to tag each message
by its sender and use this to resolve conflicts in the ordering. The
alternative would be to just let these entries order arbitrarily
instead, but conceptually it would not be simpler and it would only
save us a few lines of code.

>> Stability in multicasts without causal order is not necessarily a crucial
>> feature. However, note that if this ordering is given, it allows reducing
>> the number of round-trips in dependent systems. Imagine a daemon
>> reacting to a set of events from different sources. If the actions of that
>> daemon are solely defined by incoming events, someone else can
>> deduce the actions the daemon took without requiring the daemon to
>> send out events by itself. That is, you can just watch the events on the
>> system, and validly deduce the state of such daemon.
>>
>> Example: There is a configuration daemon that sends events when
>> configuration is changed. And there is a hotplug daemon that sends
>> events when devices are hotplugged. You get an event that the "default
>> mute-state" for audio devices was changed, after it you get a
>> hotplugged audio device. You can now rely on the audio daemon to get
>> the events in the same order, and hence apply the new "default
>> mute-state" to the new device. No need to query the audio daemon
>> whether the new device is muted.
>
> Which is cute; but is it worth the pain?
>
>> But as I said, the causal ordering is what we really want.
>> Multicast-stability is just a nice side-effect.
>
> I'm saying they're not the same thing and multi-cast stability isn't at
> all implied.

Yeah, we agree. These are orthogonal concepts. What I meant is that
once we have causality, getting consistency as a side-effect is
virtually free.