[erlang-questions] question re. message delivery

[Miles Fidelman]

On 9/27/17 4:08 AM, Joe Armstrong wrote:

> On Wed, Sep 27, 2017 at 2:16 AM, Miles Fidelman
> <mfidelman@REDACTED> wrote:
>> Hi Joe,
>>
>> Hmmm....
>>
>> Joe Armstrong wrote:
>>
>> What I said was "message passing is assumed to be reliable"
>>
>>
>> The key word here is *assumed* my assumption is that if I open a TCP socket
>> and send it five messages numbered 1 to 5 then If I successfully read
>> message
>> 5 and have seen no error indicators then I can *assume* that messages 1 to
>> 4 also arrived in order.
>>
>>
>> Well yes, but with TCP one has sequence numbers, buffering, and
>> retransmission - and GUARANTEES, by design, that if you (say a socket
>> connection) receive packet 5, then you've also received packets 1-4, in
>> order.
>>
>> My understanding is that Erlang does NOT make that guarantee.  As stated:
>>
>> - message delivery is assumed to be UNRELIABLE
> That was the short version - Here's the long version.
>
> Actually there is no such thing as "delivering a message" in Erlang.
>
> What "delivering a message means" is "putting the message in the
> mailbox of the receiver and scheduling the process for execution"

Understood.  What's less clear are the details of exactly how the 
message is copied, and the step by step flow of control.  There are a 
lot of details spelled out (in the BEAM book) about how this happens on 
a single node, but no details at all about how messages are sent between 
nodes.
>
> So all sorts of things can go wrong - the message is put in the mailbox
> but an earlier message in the mailbox causes the process to crash
> before the process reaches your message.

Exactly.  I'm trying to understand the implementation details. (Call it 
an itch I feel compelled to scratch, from a systems engineer who's 
worked on a lot of distributed systems, and at one time was involved in 
designing & implementing network protocols.)

>
> There *is* a guarantee that if create a link to a process and the process
> dies you get sent a message.
>
> So we can can make the statement "in the absence of errors message passing
> order is preserved"

But, is that true between nodes?  There are lots of ways to implement 
message passing that don't preserve ordering.  Hence my interest in details.

One can imagine all kinds of mechanisms, and failure mode, including 
ones where both the sending and receiving processes continue to run just 
fine.

- on a single node, sending a message is implemented by spawning a 
process that copies the message from the sender's memory space to the 
receiver's - easy enough for such a process to die and lose a message, 
or for scheduling to lead messages to be delivered out of order

- across nodes, even if TCP is used to move messages, a connection can 
fail and be restarted - losing data in the process - again both 
processes remain alive and well

The BEAM book details how a message is moved between processes on the 
same node (but doesn't actually about who's doing the moving). There's 
no description about how messages are moved between nodes. Again, my 
interest in details.

>
> What does this mean? If you are linked to a message receiver and see no
> error message then it is alive. If you send a sequences of messages
> to the receiver and see no error messages then the messages have been
> placed in the mailbox in order. This is guarantee (if the code is correct).

Assumes facts not in evidence.  Depending on implementation, the 
"postman" could die (to use the postal mail analogy).

>
> Note that there is no guarantee that the process will ever read the mailbox.
>
> It's like the postal service - the letters get put in the mailbox but
> there's no guarantee they get taken out, but you get to know if the
> owner of the mailbox dies.

Not a really great analogy.  First off, you don't know if the owner of 
the mailbox dies (I'm dealing with that right now, still receiving mail 
for a dead relative, forwarded from an older address, courtesy of the 
post office).  Beyond that, you never if a piece of mail falls behind a 
piece of sorting equipment.  And.. there are plenty of cases of lost 
mail showing up days, or even years later.

Now, some forms of mail delivery come with a tracking number - so you 
can determine where a piece of mail is.  And you can send mail with a 
return receipt, and resend if the receipt isn't received in a timely 
fashion (which adds the potential for duplicate delivery if the mail is 
just delayed, or the receipt gets lost).

>
> The bit that should be reliable is putting the messages in the mailbox in order
> if nothing has crashed (we assume this to be correctly coded)

Which mailbox?  The sender's outbox (or the local postbox) - agreed.  
The receiver's inbox - now that's the question on the table.

>
> The bit that is unreliable is the guarantee that the message is removed
> from the mailbox and correctly processed.

Also unreliable:
- that a message gets from the sender's outbox to the receiver's inbox
- that messages get placed in the receiver's inbox in order of transmission


>
> I'm not sure where you quoted me from - but there should be some small
> print nearby with the an extended explanation.

The quotes are from your thesis.  There is no extended explanation that 
I could find, other than that the guarantee of order is a "design decision."

>
> The world "unreliable" means different things to different people.
> TCP might well be reliable by design - but is it correctly implemented?
> I have seen many good designs with bad implementations.

Sure, so let's stick with two very specific uses of the word:

i. the protocol sense:  UDP is defined as an unreliable service, TCP is 
defined as a reliable one
ii. failure to execute a function, or provide a service, as specified

For the purposes of this discussion, I'm trying to get very clear about 
what, exactly is specified, how it's implemented, and what failure modes 
might be there.


>
> I've helped design fault-tolerant systems for years - so I'm a trust
> as little as
> possible sort of person. Assume things will crash and clean up later.

Well... me too.  But with the focus of how to build distributed systems 
that continue to function in the face of "challenged" networks.  So my 
focus tends to be on what kinds of things might fail, how to detect 
those failures, and how to clean up afterwards.

(Side note:  I first discovered Erlang while working on distributed 
simulation systems, and the protocols used for updating distributed state.)

>
> I was told years ago not to trust processes, a wise man said "if you
> want to know
> if a process has done something, get it to send you a reply message,
> if you don't get the reply message then you can't assume anything about
> the receiving process. So generating unique tags which we send in
> round trips become important ...

Absolutely!


>
> Aside: Telecoms protocols make great use of tags, and timeouts
> you send a request with a tag, wait a relative long time (the timeout) -
> much longer than the operation should take. Then on a timeout
> assume the worse - crash everything and restart.

Well, I assume you mean telephony when you say "telecoms" - in the data 
network world we use sequence numbers, and include those numbers in 
acknowledgement messages.  On the sending end, you resend if you don't 
receive and ACK within a timeout window; on the receiving end, you use 
sequence numbers to order delivery - and sometimes you request a 
retransmission if you detect a missing sequence number.

Where it gets trickier is if a connection (more accurately, an 
"association") drops.  Things get sort of interesting if you want to run 
a reliable telnet or ssh connection from a cell phone in a moving 
vehicle - your IP address tends to change as you roam from tower to 
tower, so you need something "above" TCP to re-establish connections, 
and retransmit packets lost in transit.  (Well, my personal experience 
is with tactical mesh networks.  Cellular data protocols are somewhat 
odder than basic TCP/IP).

>
> Works very well in practise - theory wise it's very dodgy - millions of lines
> of code doing this stuff is way to complex to prove anything about.
>
> Since I basically don't trust any of the underlying layers - you have
> to ask what to
> I trust.
>
> Well nothing really - but I have higher levels of trust for some
> things than other.
>
> Round trip confirmations including SHA1 checksums seems pretty good
> to me.
>
> If I say to a server "get me a file called 'foo'" and get something back
> It may of may not be correct.
>
> If I say "get me some data that has the sha1 checksum 34ad34..."
> and get some data back I can check the data and see if it has the correct
> checksum. I don't even need secure sockets. I do need a secure way to
> know the checksum - but that is an entirely different problem.
>
> This boils down to system design - in the latter case I need to place no
> trust in the layers (I need to trust SHA1 so it's not absolute)

Which  brings me back to my interest in details of Erlang's message 
passing implementation (well actually, the design - let's stay away from 
the question of correct implementation).

Cheers,

Miles

-- 
In theory, there is no difference between theory and practice.
In practice, there is.  .... Yogi Berra