View mode: basic / threaded / horizontal-split · Log in · Help
December 07, 2012
the Disruptor framework vs The Complexities of Concurrency
> [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
December 07, 2012
Re: the Disruptor framework vs The Complexities of Concurrency
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".
December 07, 2012
Re: the Disruptor framework vs The Complexities of Concurrency
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.
December 07, 2012
Re: the Disruptor framework vs The Complexities of Concurrency
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
December 08, 2012
Re: the Disruptor framework vs The Complexities of Concurrency
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.
December 08, 2012
Re: the Disruptor framework vs The Complexities of Concurrency
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
December 08, 2012
Re: the Disruptor framework vs The Complexities of Concurrency
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
December 10, 2012
Re: the Disruptor framework vs The Complexities of Concurrency
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  ??
December 10, 2012
Re: the Disruptor framework vs The Complexities of Concurrency
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
December 10, 2012
Re: the Disruptor framework vs The Complexities of Concurrency
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
« First   ‹ Prev
1 2 3
Top | Discussion index | About this forum | D home