Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Aeron: High-Performance Open Source Message Transport [video]

infoq.com

Post reply on HN
Print view View original

11–20 of 27 posts

Re: Aeron: High-Performance Open Source Message Transport [video]

#11

Post by danbruc »

mjpt777 wrote: post #8
danbruc wrote: post #7

Earlier quoted context omitted.

This is the very definition of wait-free including the case that some concurrent operations never complete. »A wait-free implementation of a concurrent data object is one that guarantees that any process can complete any operation in a finite number of steps, regardless of the execution speeds of the other processes.« (Wait-Free Synchronization, Maurice Herlihy, 1991) [1] As far as I can tell - I am definitely not an…

Thanks for the link. If you look at the implementation no thread is ever stopped from completing. If a producing thread was killed mid operation by another malicious thread then the stream is broken. Other threads are never blocked. Other writers can add via a finite number of steps and the stream will back pressure when flow control kicks in. The consumer is never blocked - it simply never sees more messages. The al…

Two threads want to send a single block message. Writer one advances the tail pointer by 100 bytes and then dies. Writer two then advances the tail pointer by another 100 bytes, copies its message into the buffer and writes its header. The reader will see the tail pointer 200 bytes past the last processed message but no valid header and this looks exactly like a writer currently in the process of placing a 200 byte message - including the header - into the buffer. Looks to me like thread one blocked thread two indefinitely because the message of thread two is never added to the buffer. Yes, the bytes are in the buffer, but only physically. The reader can not see them, i.e. the write operation did not logically complete.

Re: Aeron: High-Performance Open Source Message Transport [video]

#12

Post by danbruc »

mjpt777 wrote: post #9
danbruc wrote: post #7

Earlier quoted context omitted.

This is the very definition of wait-free including the case that some concurrent operations never complete. »A wait-free implementation of a concurrent data object is one that guarantees that any process can complete any operation in a finite number of steps, regardless of the execution speeds of the other processes.« (Wait-Free Synchronization, Maurice Herlihy, 1991) [1] As far as I can tell - I am definitely not an…

I understand the point that we need to make software robust. No single algorithm can cope with every possible failure mode. That is why we need multiple instances run on multiple nodes to be resilient. This is independent from if this is a wait-free algorithm.

It is not wait-free if it can not handle a dying process, that is the whole point of being wait-free. The reason - again as far as I can tell as a non-expert - that wait-free algorithms are not widely used is that many of the best currently known implementations have such a large overhead that they perform worse than a good locking or lock-free implementation.

Re: Aeron: High-Performance Open Source Message Transport [video]

#13

Post by mjpt777 »

saurik wrote: post #10
mjpt777 wrote: post #8

Earlier quoted context omitted.

Thanks for the link. If you look at the implementation no thread is ever stopped from completing. If a producing thread was killed mid operation by another malicious thread then the stream is broken. Other threads are never blocked. Other writers can add via a finite number of steps and the stream will back pressure when flow control kicks in. The consumer is never blocked - it simply never sees more messages. The al…

What if, instead of being killed, the thread runs arbitrarily slowly (at glacial speeds) between the two critical steps? Do other threads have to wait during that time, (Note: I haven't slept in days, not did I read the algorithm as my brain isn't working well enough to understand it, but I did seem to get the gist of this back/forth, and this seemed like an important detail.)

Please read the algorithm in code. No threads ever wait. :-)

Re: Aeron: High-Performance Open Source Message Transport [video]

#14

Post by mjpt777 »

danbruc wrote: post #11
mjpt777 wrote: post #8

Earlier quoted context omitted.

Thanks for the link. If you look at the implementation no thread is ever stopped from completing. If a producing thread was killed mid operation by another malicious thread then the stream is broken. Other threads are never blocked. Other writers can add via a finite number of steps and the stream will back pressure when flow control kicks in. The consumer is never blocked - it simply never sees more messages. The al…

Two threads want to send a single block message. Writer one advances the tail pointer by 100 bytes and then dies. Writer two then advances the tail pointer by another 100 bytes, copies its message into the buffer and writes its header. The reader will see the tail pointer 200 bytes past the last processed message but no valid header and this looks exactly like a writer currently in the process of placing a 200 byte m…

If you look at the code the reader does not read the tail. It skips forward reading the length fields. It would never see the writer two message and it never blocks. It just thinks there are no new messages.

Re: Aeron: High-Performance Open Source Message Transport [video]

#15

Post by danbruc »

mjpt777 wrote: post #14
danbruc wrote: post #11

Earlier quoted context omitted.

Two threads want to send a single block message. Writer one advances the tail pointer by 100 bytes and then dies. Writer two then advances the tail pointer by another 100 bytes, copies its message into the buffer and writes its header. The reader will see the tail pointer 200 bytes past the last processed message but no valid header and this looks exactly like a writer currently in the process of placing a 200 byte m…

If you look at the code the reader does not read the tail. It skips forward reading the length fields. It would never see the writer two message and it never blocks. It just thinks there are no new messages.

Writer two is blocked, not the reader. Writer two wants to add a message to the buffer but never succeeds because writer one fails to make the message of writer two visible to the reader.

Re: Aeron: High-Performance Open Source Message Transport [video]

#16

Post by mjpt777 »

danbruc wrote: post #12
mjpt777 wrote: post #9

Earlier quoted context omitted.

I understand the point that we need to make software robust. No single algorithm can cope with every possible failure mode. That is why we need multiple instances run on multiple nodes to be resilient. This is independent from if this is a wait-free algorithm.

It is not wait-free if it can not handle a dying process, that is the whole point of being wait-free. The reason - again as far as I can tell as a non-expert - that wait-free algorithms are not widely used is that many of the best currently known implementations have such a large overhead that they perform worse than a good locking or lock-free implementation.

You keep saying you are not an expert but keep pushing the point :-)

Try this. A process could have a rogue thread scribbling on memory and thus corrupting it. Such a process then that has this thread, by your definition, cannot be wait-free because any data structure can be corrupted and cause algorithms to fail. This is not how the concurrency community look at this.

*added below

Even a simple LOCK XADD instruction could have its results corrupted by this rogue thread after it writes before a consumer reads it.

Re: Aeron: High-Performance Open Source Message Transport [video]

#17

Post by danbruc »

mjpt777 wrote: post #16
danbruc wrote: post #12

Earlier quoted context omitted.

It is not wait-free if it can not handle a dying process, that is the whole point of being wait-free. The reason - again as far as I can tell as a non-expert - that wait-free algorithms are not widely used is that many of the best currently known implementations have such a large overhead that they perform worse than a good locking or lock-free implementation.

You keep saying you are not an expert but keep pushing the point :-) Try this. A process could have a rogue thread scribbling on memory and thus corrupting it. Such a process then that has this thread, by your definition, cannot be wait-free because any data structure can be corrupted and cause algorithms to fail. This is not how the concurrency community look at this. *added below Even a simple LOCK XADD instruction…

Agreed, corrupting the content of the address space was pushing the reasons for a failing thread a bit to far. But I only wanted to point out that any process can fail, i.e. make no further progress, at any time independent of the code it is executing. But lets just stick with killing or pausing the thread.

And I obviously don't have to be an expert in the field to know that wait-free means that the algorithm must be able to handle processes making no progress because that is, as mentioned before, the definition.

Re: Aeron: High-Performance Open Source Message Transport [video]

#18

Post by mjpt777 »

danbruc wrote: post #15
mjpt777 wrote: post #14

Earlier quoted context omitted.

If you look at the code the reader does not read the tail. It skips forward reading the length fields. It would never see the writer two message and it never blocks. It just thinks there are no new messages.

Writer two is blocked, not the reader. Writer two wants to add a message to the buffer but never succeeds because writer one fails to make the message of writer two visible to the reader.

Writer two is not blocked, it is not waiting, it is not being obstructed. It is wait-free. It returns and can do whatever work it wishes.

However the data structure would be corrupt if writer one never completed. This is corruption and not the definition of wait-free.

Re: Aeron: High-Performance Open Source Message Transport [video]

#19

Post by wflfof »

mjpt777 wrote: post #8
danbruc wrote: post #7

Earlier quoted context omitted.

This is the very definition of wait-free including the case that some concurrent operations never complete. »A wait-free implementation of a concurrent data object is one that guarantees that any process can complete any operation in a finite number of steps, regardless of the execution speeds of the other processes.« (Wait-Free Synchronization, Maurice Herlihy, 1991) [1] As far as I can tell - I am definitely not an…

Thanks for the link. If you look at the implementation no thread is ever stopped from completing. If a producing thread was killed mid operation by another malicious thread then the stream is broken. Other threads are never blocked. Other writers can add via a finite number of steps and the stream will back pressure when flow control kicks in. The consumer is never blocked - it simply never sees more messages. The al…

Regarding applying the wait/lock/obstruction freedom definition to Vyukov's MPSC implementation you reference.

It's clear that the MPSC design is not wait-free, nor is it lock-free. Dmitry identifies this fact in his initial postings about that design: https://groups.google.com/forum/#!topic/lock-free/Vd9xuHrLgg...

""" Push function is blocking wrt consumer. I.e. if producer blocked in (*), then consumer is blocked too. """

Between the XCHG and the update of next. If the producing thread completes the XCHG but fails to update next, all threads will fail to make progress. "Progress" in this case being the producers transferring data to the consumer. Put another way, in this algorithm a single misbehaving thread can prevent all threads from making progress.

Regarding the idea of "maliciousness", specifically if a participant thread is "killed mid-operation". That idea is the very definition of wait-freedom: that all participants complete the algorithm in a bounded number of their own steps, irrespective of the activities of other threads.

The definitions of wait/lock/obstruction freedom are well specified. I suggest the first half of _The Art of Multiprocessor Programming_ (the revised edition!) by Herlihy and Shavit for a deep dive.

Re: Aeron: High-Performance Open Source Message Transport [video]

#20

Post by danbruc »

mjpt777 wrote: post #18
danbruc wrote: post #15

Earlier quoted context omitted.

Writer two is blocked, not the reader. Writer two wants to add a message to the buffer but never succeeds because writer one fails to make the message of writer two visible to the reader.

Writer two is not blocked, it is not waiting, it is not being obstructed. It is wait-free. It returns and can do whatever work it wishes. However the data structure would be corrupt if writer one never completed. This is corruption and not the definition of wait-free.

No, it is not wait-free. The operation of writer two does not even succeed. Some bytes get written to the buffer but the message is never really added to the log because to call a write a success it should at least become visible to the reader. Writer two returns from the write operation without noticing that the operation failed. To make sure that the write succeeded writer two would have to wait and verify that its message actually becomes visible to the reader.

You can even go a step further and make writer two block. Just assume that the next thing it does is waiting for a response from the receiver of its message. Now because writer one failed the message never reaches the receiver, the receiver never sends a response and the writer waits indefinitely for the response, i.e. is blocked. Now the failed writer one is really and the only reason writer two is blocked, even though only indirectly.

And you can not really call it a corruption of the data structure because it is the exact same stated that occurs during normal operation. If writer one would resume execution after two weeks suddenly the corruption would be gone.

Post reply on HN