Embargo and message order guarantees?

[Ross Light]

I'm trying to address the last hurdle in Go RPC support: embargoes and call order guarantees. What I'm unclear on is this: is E-order guaranteeing if Alice calls foo then bar on Carol that:

a) the functions are started in that order, or
b) foo must complete before bar starts?

The document linked in the rpc.capnp protocol spec only states that "messages are delivered in the order sent", but that leaves me with the above ambiguity. Since Go lacks futures (by design), (a) is a much harder guarantee than (b).

Thanks,
-Ross (@zombiezen on GitHub)

(Forgive me if this double-posts, the first mail didn't seem to go through.)

[Ross Light]

[Ross Light]

Aha! I found the missing piece: the earlier chapter on Distributed Queuing.  (b) is indeed the correct interpretation.

I don't see any limits in the spec or the C++ implementation about how many calls can be queued.  Is there a DoS potential?

-Ross

[Kenton Varda]

Hi Ross,

Sorry, the constraint is definitely (a). By "messages" I meant "call messages", saying nothing about returns. We definitely don't want call/returns to be FIFO -- it's in fact a common pattern for a call to hang for a long period while other calls continue to be serviced.

The ordering of *starts* is important, though, in order to support interfaces like:

    interface Stream {

      write @0 (data :Data);

    }

Here, the caller might issue several write() calls, but they need to arrive in-order.

I am not very experienced with Go, but I would think that the best way to implement this in Go would be for all calls to a particular object to arrive on a channel. The object pulls calls from the channel and calls the appropriate method, passing it the parameters as well as a return channel. Returns would then be accomplished by writing to the return channel, which could happen immediately or in the future.

This way, by default there is one thread per object and the object implementation need not worry about synchronization. But, if the object wants to perform some task concurrently, it can start a goroutine which performs some long-running task then writes to the return channel.

Thoughts?

-Kenton

--
You received this message because you are subscribed to the Google Groups "Cap'n Proto" group.
To unsubscribe from this group and stop receiving emails from it, send an email to capnproto+...@googlegroups.com.
Visit this group at http://groups.google.com/group/capnproto.

[Geoffrey Romer]

Side note: a future is just a channel that's guaranteed to be used exactly once, so it's hard to see how the lack of futures in go could make anything fundamentally harder.

--

[Ross Light]

Geoffrey: understood.  My Go bindings do expose a future-like type (Answer) that is returned from each capability method call.  This is essential for pipelining.  My point is that idiomatic Go code is okay with blocking a goroutine, whereas most other languages aren't.  Futures in other languages use a .then() method; Go's future equivalent use a .get() method.

Comments for Kenton in-line below.

On Mon, Jul 27, 2015 at 9:41 PM Kenton Varda <ken...@sandstorm.io> wrote:

Hi Ross,

Sorry, the constraint is definitely (a). By "messages" I meant "call messages", saying nothing about returns. We definitely don't want call/returns to be FIFO -- it's in fact a common pattern for a call to hang for a long period while other calls continue to be serviced.

The ordering of *starts* is important, though, in order to support interfaces like:

    interface Stream {

      write @0 (data :Data);

    }

Here, the caller might issue several write() calls, but they need to arrive in-order.

This is the use-case I keep thinking about. However, "start write1 happens before start write2" doesn't seem useful to me, but "finish write1 happens before start write2" is useful.  I'd understand pushing that decision up to applications, but not the protocol.

The problem I'm envisioning is this (assuming "calling a write happens before performing the write happens before returning from write"):

1. write call 1 delivered
2. write call 2 delivered
3. write 2 is performed
4. write 1 is performed
5. write 1 returns
6. write 2 returns

This obeys your ordering, but is almost certainly not what you intended.  If I'm reading the E language docs correctly, they apply constraint (b) which adds the "returning from call N -1 happens before starting call N", which sidesteps the issue.

 

I am not very experienced with Go, but I would think that the best way to implement this in Go would be for all calls to a particular object to arrive on a channel. The object pulls calls from the channel and calls the appropriate method, passing it the parameters as well as a return channel. Returns would then be accomplished by writing to the return channel, which could happen immediately or in the future.

This way, by default there is one thread per object and the object implementation need not worry about synchronization. But, if the object wants to perform some task concurrently, it can start a goroutine which performs some long-running task then writes to the return channel.

Thoughts?

-Kenton

Here's what I had in mind: https://gist.github.com/zombiezen/2878a6085b48486d4ccf

The crux of the problem is when you say "a call is received" in C++, you mean that the function has actually started executing.  It may do something "blocking", in which case it returns a promise, which then signals that other messages can be received.  This makes for awkward code in Go, as you can see from the gist.

Does my concern make sense?

[David Renshaw]

On Tue, Jul 28, 2015 at 11:39 AM, Ross Light <ro...@zombiezen.com> wrote:

Here's what I had in mind: https://gist.github.com/zombiezen/2878a6085b48486d4ccf

I don't know much Go, but I think I can follow what's happening here.

Looks like for every RPC you are spawning a new goroutine. That is, you are doing goroutine-per-request. Have you considered goroutine-per-object? Each object object could be its own little event loop that waits on a channel for request messages and then dispatches them to the user-supplied implementation.

- David

[Kenton Varda]

Hi Ross,

When I say "a call is received", I mean by the application code, not just by the RPC infrastructure. The application code must have a chance to process the input and do some actions before new calls are allowed to be delivered. However, the application code must also have the option to unblock further calls before the first call has completed, as many protocols will not work in a purely FIFO framework.

In your example code, I see all three proposals appear to create a goroutine inside the RPC infrastructure for every call. IMO, it should be the app's responsibility to create a goroutine if it is performing a long-running operation. Most calls will complete quickly, so creating goroutines for each one would be a lot of overhead, in addition to losing ordering.

Technically you are only required to guarantee ordering for calls to the same object (therefore, there should be one goroutine per server object), although in practice I think there are cases where apps would really like ordering to be guaranteed over multiple objects that are known to be implemented in the same vat. Perhaps you could have a way for apps to explicitly opt in to sharing a goroutine between multiple objects, probably by specifying at object creation time "please run in the same event loop as this other existing object".

-Kenton

[Ross Light]

SGTM.  I'll definitely use a goroutine per capability and add the ability for the application to specify when it can unblock the message processing.  I'll defer the goroutine sharing, but I'll keep that in mind.

Thanks so much for the help!  This makes a lot more sense now.

-Ross