> [Andrei's comment ] Cross-pollination is a good thing indeed.

I came across this while searching the programme of the conference that Walter is attending in Australia.


This gentleman, Martin Thompson

http://www.yowconference.com.au/general/details.html?speakerId=2962


The main idea, is in this paper (11 pages, pdf):

http://disruptor.googlecode.com/files/Disruptor-1.0.pdf


and here is a review of the architecure by Martin Fowler:

http://martinfowler.com/articles/lmax.html



My questions are:

1.  Is this pattern worth porting to the standard library ?

2.  Is this pattern a replacement for the 'Complexity of Concurrency' ?


cheers
Nick B

On Friday, 7 December 2012 at 09:00:48 UTC, Nick B wrote:
>
>> [Andrei's comment ] Cross-pollination is a good thing indeed.
>
> I came across this while searching the programme of the conference that Walter is attending in Australia.
>
>
> This gentleman, Martin Thompson
>
> http://www.yowconference.com.au/general/details.html?speakerId=2962
>
>
> The main idea, is in this paper (11 pages, pdf):
>
> http://disruptor.googlecode.com/files/Disruptor-1.0.pdf
>
>
> and here is a review of the architecure by Martin Fowler:
>
> http://martinfowler.com/articles/lmax.html
>
>
>
> My questions are:
>
> 1.  Is this pattern worth porting to the standard library ?
>
> 2.  Is this pattern a replacement for the 'Complexity of Concurrency' ?
>
>
> cheers
> Nick B

You can find few presentation from LMAX guys on InfoQ. Pretty neat stuff if you ask me. I think someone already worked on Disruptor-like project in D.
I would not like to have the whole thing in Phobos, just some "basic blocks".

On Friday, 7 December 2012 at 09:03:58 UTC, Dejan Lekic wrote:
> On Friday, 7 December 2012 at 09:00:48 UTC, Nick B wrote:
>>
>>> [Andrei's comment ] Cross-pollination is a good thing indeed.
>>
>> I came across this while searching the programme of the conference that Walter is attending in Australia.
>>
>>
>> This gentleman, Martin Thompson
>>
>> http://www.yowconference.com.au/general/details.html?speakerId=2962
>>
>>
>> The main idea, is in this paper (11 pages, pdf):
>>
>> http://disruptor.googlecode.com/files/Disruptor-1.0.pdf
>>
>>
>> and here is a review of the architecure by Martin Fowler:
>>
>> http://martinfowler.com/articles/lmax.html
>>
>>
>>
>> My questions are:
>>
>> 1.  Is this pattern worth porting to the standard library ?
>>
>> 2.  Is this pattern a replacement for the 'Complexity of Concurrency' ?
>>
>>
>> cheers
>> Nick B
>
> You can find few presentation from LMAX guys on InfoQ. Pretty neat stuff if you ask me. I think someone already worked on Disruptor-like project in D.
> I would not like to have the whole thing in Phobos, just some "basic blocks".

Actually, this is what should be behind message passing in phobos IMO. Much better than what we currently have.

I wanted to do that at the time, but it wasn't possible without asm. You'll find post about that if you dig deep engough in that newsgroup.

12/7/2012 1:43 PM, deadalnix пишет:
> On Friday, 7 December 2012 at 09:03:58 UTC, Dejan Lekic wrote:
>> On Friday, 7 December 2012 at 09:00:48 UTC, Nick B wrote:
>>>
>>>> [Andrei's comment ] Cross-pollination is a good thing indeed.
>>>
>>> I came across this while searching the programme of the conference
>>> that Walter is attending in Australia.
>>>
>>>
>>> This gentleman, Martin Thompson
>>>
>>> http://www.yowconference.com.au/general/details.html?speakerId=2962
>>>
>>>
>>> The main idea, is in this paper (11 pages, pdf):
>>>
>>> http://disruptor.googlecode.com/files/Disruptor-1.0.pdf
>>>
>>>
>>> and here is a review of the architecure by Martin Fowler:
>>>
>>> http://martinfowler.com/articles/lmax.html
>>>
>>>
>>>
>>> My questions are:
>>>
>>> 1.  Is this pattern worth porting to the standard library ?
>>>
>>> 2.  Is this pattern a replacement for the 'Complexity of Concurrency' ?
>>>
>>>
>>> cheers
>>> Nick B
>>
>> You can find few presentation from LMAX guys on InfoQ. Pretty neat
>> stuff if you ask me. I think someone already worked on Disruptor-like
>> project in D.
>> I would not like to have the whole thing in Phobos, just some "basic
>> blocks".
>
> Actually, this is what should be behind message passing in phobos IMO.
> Much better than what we currently have.
>
> I wanted to do that at the time, but it wasn't possible without asm.
> You'll find post about that if you dig deep engough in that newsgroup.

The stuff is an amazingly cool pattern.

TI just think there are some limitations of applicability though.

Producer has to read all of sequence counters of its final consumers so as to not to stomp on their slots. And indeed 1P-3C is the least shiny column. I suspect if one ups the number of "sink"-kind consumers  it starts to give in.

Thus I think it's not fit to arbitrary graphs of actors that are constructed & destroyed at run-time like in std.concurrency. Keep in mind that in model we currently have relations between actors are not fixed anywhere and more importantly not every message have to be seen by every consumer even eventually.

And it's not a producer-_consumers_ either. I mean that 'consumer' implies it consumes the item and that other consumers won't see it.

Looking at the graphs in:

http://martinfowler.com/articles/lmax.html

It's obvious what the thing truly models - a hierarchical pipeline where each direct "consumer" visits each of the requests once. Then dependent consumers (further down the hierarchy) can visit it and so forth till the bottom. The last ones are the "sink" that effectively consumes item. The terms multi-pass and multi-stage is more to the point here.

To compare these two different views:

Producer-consumer is a kind of a workflow where worker grubs material from input "gate" and does everything on it alone then passes it to the next "gate". The scalability is achieved by having a lot of workers that each does the whole work independently (and able to do so!).

The advantage is that you never have a half-baked work unit: it either waits, in process or done. There is no stage of "semi-done". Also it's trivially balanced:
 - queue accumulates too fast - grow consumers pool, shrink producer pool
- queue is near empty - grow more producers, shrink consumers pool

So there is a world of tuning but the levers are easy to understand.
In a sense this scheme scales nicely with the amount of messages just not with the number of *independent* *parallel* processing steps per each message.

The pipeline described in Disrupter is more like a factory pipeline where you have a large rotating transporter and workers are standing around it. It's just that in this case it's workers moving around it instead of central rotation (and its better as speeds of different stages goes up and down).

Then there is one (or many) that puts material and goes forward, other workers are doing their own passes and advance until they have to wait on the producer (or the worker of the previous stage).

Indeed emulating the second concept with queues that can only take/put is embarrassing as you'd have to split queues on each stage and put copies of references to items into them (in Java it's always the case).

So the last problem is I don't see how it cleanly scales with the number of messages: there is only one instance of a specific consumer type on each stage. How do these get scaled if one core working on each is not enough?

-- 
Dmitry Olshansky

On Fri, 07 Dec 2012 19:55:50 +0400
Dmitry Olshansky <dmitry.olsh@gmail.com> wrote:

> 12/7/2012 1:43 PM, deadalnix пишет:
> > On Friday, 7 December 2012 at 09:03:58 UTC, Dejan Lekic wrote:
> >> On Friday, 7 December 2012 at 09:00:48 UTC, Nick B wrote:
> >>>
> >>>> [Andrei's comment ] Cross-pollination is a good thing indeed.
> >>>
> >>> I came across this while searching the programme of the conference that Walter is attending in Australia.
> >>>
> >>>
> >>> This gentleman, Martin Thompson
> >>>
> >>> http://www.yowconference.com.au/general/details.html?speakerId=2962
> >>>
> >>>
> >>> The main idea, is in this paper (11 pages, pdf):
> >>>
> >>> http://disruptor.googlecode.com/files/Disruptor-1.0.pdf
> >>>
> >>>
> >>> and here is a review of the architecure by Martin Fowler:
> >>>
> >>> http://martinfowler.com/articles/lmax.html
> >>>

Fascinating.

> 
> So the last problem is I don't see how it cleanly scales with the number of messages: there is only one instance of a specific consumer type on each stage. How do these get scaled if one core working on each is not enough?
> 

As Fowler's articles mentions at one point, you can have multiple consumers of the same type working concurrently on the same ring by just simply having each of them skip every N-1 items (for N consumers of the same type. Ie, if you have two consumers of the same type, one operates on the even #'d items, the other on the odd.

On Saturday, 8 December 2012 at 17:08:55 UTC, Nick Sabalausky wrote:
>
> Fascinating.
>
>> 
>> So the last problem is I don't see how it cleanly scales with the
>> number of messages: there is only one instance of a specific consumer
>> type on each stage. How do these get scaled if one core working on
>> each is not enough?
>> 
>
> As Fowler's articles mentions at one point, you can have multiple
> consumers of the same type working concurrently on the same ring by
> just simply having each of them skip every N-1 items (for N consumers
> of the same type. Ie, if you have two consumers of the same type, one
> operates on the even #'d items, the other on the odd.

Yes I was getting the sense of that while quickly reading through it. If my understanding is correct, it seems that you can have levels of rings and consumers operating like a pipelining system from one stage to another to scale up to multiple cpus.

I need to sit down and read this in detail, it's very interesting. Of particular interest to me, is the part where they store in non-volatile memory the messages coming in, so that when the system goes down, it can be brought back up to the previous state by replaying the messages. They also use that system to replicate multiple redundant copies so that should the live service goes down, one of the redundant copies can immediately go live in a very short period of time.

One concern I have though, is how generalized the approach is, or if it is suitable only for certain specialized situations. Also how scalable it is in terms of complexity with being able to manage the scaling.

Note too the mention of issues with the GC, which forced certain design decisions, although even without a GC, the design choices may still be the best ones to use.

--rt

12/8/2012 9:08 PM, Nick Sabalausky пишет:
> On Fri, 07 Dec 2012 19:55:50 +0400
> Dmitry Olshansky <dmitry.olsh@gmail.com> wrote:
>
>> 12/7/2012 1:43 PM, deadalnix пишет:
>>> On Friday, 7 December 2012 at 09:03:58 UTC, Dejan Lekic wrote:
>>>> On Friday, 7 December 2012 at 09:00:48 UTC, Nick B wrote:
>>>>>
>>>>>> [Andrei's comment ] Cross-pollination is a good thing indeed.
>>>>>
>>>>> I came across this while searching the programme of the conference
>>>>> that Walter is attending in Australia.
>>>>>
>>>>>
>>>>> This gentleman, Martin Thompson
>>>>>
>>>>> http://www.yowconference.com.au/general/details.html?speakerId=2962
>>>>>
>>>>>
>>>>> The main idea, is in this paper (11 pages, pdf):
>>>>>
>>>>> http://disruptor.googlecode.com/files/Disruptor-1.0.pdf
>>>>>
>>>>>
>>>>> and here is a review of the architecure by Martin Fowler:
>>>>>
>>>>> http://martinfowler.com/articles/lmax.html
>>>>>
>
> Fascinating.
>
>>
>> So the last problem is I don't see how it cleanly scales with the
>> number of messages: there is only one instance of a specific consumer
>> type on each stage. How do these get scaled if one core working on
>> each is not enough?
>>
>
> As Fowler's articles mentions at one point, you can have multiple
> consumers of the same type working concurrently on the same ring by
> just simply having each of them skip every N-1 items (for N consumers
> of the same type. Ie, if you have two consumers of the same type, one
> operates on the even #'d items, the other on the odd.
>
I thought about that even-odd style but it muddies waters a bit.
Now producers or however comes next the "circle" have to track all of the split-counters (since they could outpace each other at different times). The other way is to have them contend on a single counter with CAS but again not as nice.

The other moment is that system becomes that more dependent on a single component failure and they get around this be running multiple copies of the whole system in sync. A wise move to ensure stability of a complex system (and keeping in mind the stack exchange reliability requirements).


-- 
Dmitry Olshansky

On Saturday, 8 December 2012 at 19:54:29 UTC, Dmitry Olshansky wrote:
> 12/8/2012 9:08 PM, Nick Sabalausky пишет:
>> On Fri, 07 Dec 2012 19:55:50 +0400
>> Dmitry Olshansky <dmitry.olsh@gmail.com> wrote:
>>
>>> 12/7/2012 1:43 PM, deadalnix пишет:
>>>> On Friday, 7 December 2012 at 09:03:58 UTC, Dejan Lekic wrote:
>>>>> On Friday, 7 December 2012 at 09:00:48 UTC, Nick B wrote:
>>>>>>
>>>>>>> [Andrei's comment ] Cross-pollination is a good thing indeed.
>>>>>>
>>>>>> I came across this while searching the programme of the conference
>>>>>> that Walter is attending in Australia.
>>>>>>
>>>>>>
>>>>>> This gentleman, Martin Thompson
>>>>>>
>>>>>> http://www.yowconference.com.au/general/details.html?speakerId=2962
>>>>>>
>>>>>>
>>>>>> The main idea, is in this paper (11 pages, pdf):
>>>>>>
>>>>>> http://disruptor.googlecode.com/files/Disruptor-1.0.pdf
>>>>>>
>>>>>>
>>>>>> and here is a review of the architecure by Martin Fowler:
>>>>>>
>>>>>> http://martinfowler.com/articles/lmax.html
>>>>>>
>>
>> Fascinating.
>>
>>>
>>> So the last problem is I don't see how it cleanly scales with the
>>> number of messages: there is only one instance of a specific consumer
>>> type on each stage. How do these get scaled if one core working on
>>> each is not enough?
>>>
>>
>> As Fowler's articles mentions at one point, you can have multiple
>> consumers of the same type working concurrently on the same ring by
>> just simply having each of them skip every N-1 items (for N consumers
>> of the same type. Ie, if you have two consumers of the same type, one
>> operates on the even #'d items, the other on the odd.
>>
> I thought about that even-odd style but it muddies waters a bit.
> Now producers or however comes next the "circle" have to track all of the split-counters (since they could outpace each other at different times). The other way is to have them contend on a single counter with CAS but again not as nice.
>
> The other moment is that system becomes that more dependent on a single component failure and they get around this be running multiple copies of the whole system in sync. A wise move to ensure stability of a complex system (and keeping in mind the stack exchange reliability requirements).

Would Andrei like to comment on any of the comments so far  ??

On 12/9/12 10:58 PM, Nick B wrote:
[about the Disruptor framework]
> Would Andrei like to comment on any of the comments so far ??

Sorry, I'd need to acquire expertise in Disruptor before discussing it. I found http://disruptor.googlecode.com/files/Disruptor-1.0.pdf quite difficult to get into because it spends the first page stating how good Disruptor is, then the next 3 pages discussing unrelated generalities, to then start discussing implementation details still without really defining the pattern. I had to stop there.

Is there a more concise description of the pattern?


Andrei

On Monday, 10 December 2012 at 20:08:32 UTC, Andrei Alexandrescu wrote:
> On 12/9/12 10:58 PM, Nick B wrote:
> [about the Disruptor framework]
>> Would Andrei like to comment on any of the comments so far ??
>
> Sorry, I'd need to acquire expertise in Disruptor before discussing it. I found http://disruptor.googlecode.com/files/Disruptor-1.0.pdf quite difficult to get into because it spends the first page stating how good Disruptor is, then the next 3 pages discussing unrelated generalities, to then start discussing implementation details still without really defining the pattern. I had to stop there.
>
> Is there a more concise description of the pattern?
>

Indeed, I felt the same with that paper. I suggest you read :
http://blog.codeaholics.org/2011/the-disruptor-lock-free-publishing/
http://mechanitis.blogspot.com/2011/06/dissecting-disruptor-how-do-i-read-from.html
http://mechanitis.blogspot.com/2011/06/dissecting-disruptor-whats-so-special.html
http://mechanitis.blogspot.com/2011/07/dissecting-disruptor-writing-to-ring.html