Re: Report on Unidirectional Streams in Minq

[Mikkel Fahnøe Jørgensen <[e-mail]>]

Can you explain why you think this would be different with unidirectional
versus bidirectional?


A stream needs to keep various data structures alive to recognise input on
the wire, and requests from the user to access read buffers. If it is
possible to receive data then those structures cannot be torn down before a
FIN or RST is received by peer. Some streams may be practically
uni-directional, but the transport cannot know without application protocol
saying so via the API surface. This means the state needs to stay online
for at least a roundtrip, plus any processing delays the peer may have. A
hostile peer could indefinitely delay closing a stream.

With uni-directional streams there is no peer to be waiting for. This means
all sender state can be taken down immediate after sending FIN or RST. This
in turn can lead to much higher through put rates if there is a limit on
the number of states to keep open. Because a peer cannot delay close, the
stream count limit may also be increased while also consuming less space
due to less complexity.

Uni-directional receiver state still has some work to do, but it can
immediately take state down once a RST or FIN is seen, without waiting for
the peer to close the other stream, and the receiver would (necessarily)
have to create a sender state, so overall less state to manage and fewer
vulnerabilities.

There is still a need to track state of recently received and closed
streams to handle late traffic and prevent reuse, but this is comparatively
light weight.

Simulated bi-directional streams on top of uni-directional streams may have
some of the contains of proper bi-directional streams depending on the
exact close semantics chosen, but in this case it is probably a desirable
feature.

In conclusion, uni-directional streams ought to support much higher
bandwidth messaging over independent streams - like if you have many
micro-services sending async messages through the same connection.

For a very basic QUIC implementation the difference might not be so drastic
since you can just allocate a map structure and garbage collect it when
done. For a high performance implementation it matters a lot more.


Kind Regards,
Mikkel Fahnøe Jørgensen


On 1 October 2017 at 23.04.03, Eric Rescorla ([e-mail]) wrote:

I'm not sure I have any useful insights on this, as my implementation
handles them more or less the same. Can you explain why you think this
would be different with unidirectional versus bidirectional?

-Ekr


On Sun, Oct 1, 2017 at 1:38 PM, Mikkel Fahnøe Jørgensen <[e-mail]>
wrote:

> Thanks,
>
> I only skimmed this superfast, but one the observations appear to not
> cover one of my key points:
>
> You can create and close uni-streams at at very high rate of many streams
> per packet, without waiting for peer response, assuming the ACK framework
> handles retransmission. Any insights on this?
>
> Kind Regards,
> Mikkel Fahnøe Jørgensen
>
>
> On 1 October 2017 at 22.32.02, Eric Rescorla ([e-mail]) wrote:
>
> Hi folks,
>
> As promised I spent a bunch of time hacking unidirectional streams
> into Minq and I'm here to report back [0]. Specifically, I
> implemented:
>
>   - PR#643 -- Unidirectional Streams
>   - PR#720 -- Add bidirectional streams on top of unidirectional
>   - A bidirectional stream API that mostly mimics Minq's original API
>     for -05.
>
> The following is kind of a wall of text, so you could also skip this
> and refer to my slides [1].
>
>
> MINQ'S -05 ARCHITECTURE
> API
> Minq's master object is the Connection, which has a list of Streams
> indexed by stream ID. Applications register a handler with the
> connection to be notified of new events.
>
>    type ConnectionHandler interface {
>     // The connection has changed state to state |s|
>     StateChanged(s State)
>
>     // A new stream has been created (by receiving a frame
>     // from the other side. |s| contains the stream.
>     NewStream(s *Stream)
>
>     // Stream |s| is now readable.
>     StreamReadable(s *Stream)
>    }
>
> Streams get created in two ways:
>
> - Locally via Connection.CreateStream()
> - Remotely, in which case the application is notified via a callback to
>   ConnectionHandler.NewStream().
>
> Streams themselves have the APIs you would expect, namely, Read(),
> Write(), Close(), Reset(), etc. You get notified of stream readability
> by a callback to ConnectionHandler.StreamReadable(), at which point
> you can do Stream.Read(). As expected, Stream.Read() returns
> WOULDBLOCK when no data ia available
>
>
> INTERNALS
> As noted above, we start with the Connection object (only relevant fields
> shown):
>
>    type Connection struct {
>     handler          ConnectionHandler
>     streams          []*Stream
>     maxStream        uint32
> outputClearQ     []frame // For stream 0
> outputProtectedQ []frame // For stream >= 0
>    }
>
> As you can see, streams are in an array slice, so they're contiguously
> indexed by stream ID. Right now, I have no provision for reclaiming
> the unused bottom part of the array, but it would be straightforward
> to index by |streamId| - |minStream|, which I think is consistent with
> the design implied by the requirement to create streams in sequence.
>
> Because Streams are bidirectional, each stream actually consists of a
> pair of half streams.
>
>    type streamHalf struct {
>     s             *stream           // pointer to parent
>     log           loggingFunction
>     dir           direction         // Sending or receiving
>     closed        bool              // Is the half-stream closed
>     offset        uint64            // The
>     chunks        []streamChunk
>     maxStreamData uint64
>    }
>
>    // Internal object to allow unit testing.
>    type stream struct {
>     id         uint32
>     log        loggingFunction
>     state      streamState
>     send, recv *streamHalf
>   blocked    bool // Have we returned blocked
>    }
>
>    // Public API object, which needs access to the Connection
>    type Stream struct {
>     c *Connection
>     stream
>    }
>
> Outgoing data is enqueued into |stream.chunks|, and then periodically
> the connection polls the stream for all the chunks which are permitted
> by stream-level flow control and enqueues them into
> |Connection.outputClearQ| or |Connection.outputProtectedQ|. At this
> point, the connection owns the data and is responsible for
> transmitting it, subject to connection-level flow control, and
> (presumably) congestion control once I have that implemented [2].
>
> Incoming data gets queued (sorted) into |stream.chunks| for later
> reassembly at the time when someone calls stream.read(). I'm not sure
> I love this, because it means I don't have a good view of the incoming
> queue size (which I'd need to account for separately), but it allowed
> me to share data structures between incoming and outgoing, which
> seemed kind of natural when I did it (this architecture is replicated
> in the unidirectional streams design, but it's probably less natural
> there).
>
>
> UNIDIRECTIONAL STREAMS ARCHITECTURE
> UNIDIRECTIONAL API
> With the unidirectional branch, Minq offers two APIs. The first is a
> straightforward mapping of PR#720, in which we have two objects:
>
>   SendStream -- used for writing
>   RecvStream -- used for reading
>
> As before, we have a handler object, but it's directional now:
>
>    type ConnectionHandler interface {
>     // The connection has changed state to state |s|
>     StateChanged(s State)
>
>     // A new receiving stream has been created (by receiving a frame
>     // from the other side. |s| contains the stream.
>     NewRecvStream(s *RecvStream)
>
>     // Stream |s| is now readable.
>     StreamReadable(s *RecvStream)
>    }
>
> Obviously SendStreams are locally created and RecvStreams are remotely
> created. SendStreams can be created using
> Connection.CreateSendStream() and you learn about remotely created
> RecvStreams by a callback to ConnectionHandler.NewRecvStream().
> Second-created streams can be marked as "related" to a single
> first-created stream, using Connection.CreateRelatedSendStream() with
> the appropriate RecvStream as the argument [3]. Streams have a
> Related() API to tell you if they are related to some other stream.
>
> The {Send,Recv}Stream APIs are about what you'd expect. You can
> Write() on SendStream and Read() on RecvStream(). Right now, you can
> Close() and Reset() SendStreams, but not do anything on RecvStreams()
> or than ignore them. Eventually I'll probably offer
> RecvStream().Mute() or something to let you send STOP_SENDING.
>
>
> BIDIRECTIONAL API
> Minq also includes a bidirectional API that's layered on top of
> unidirectional streams. I've created a Connection2 structure that's
> intended as a wrapper around Connection [4]:
>
>    type Connection2 struct {
>     Connection
>     shim    *connection2ShimHandler
>     streams []*Stream // Odd for client originated, even for server.
>    }
>
>    type Stream struct {
>     id   uint32
>     send *SendStream
>     recv *RecvStream
>    }
>
> Basically, Stream is just a pair of SendStream and RecvStream and
> Connection2 does the bookkeeping to keep them connected (I even do the
> odd/even ID thing that QUIC-05 has). Connection2 has the same handler
> API as Minq for QUIC-05, and the shim is responsible for translating
> unidirectional events into bidirectional events.
>
> Internally, what's going on here is that when you call CreateStream()
> Minq creates a Stream with a nil RecvStream. When a new remote stream
> is detected, we check RecvStream.Related(). If they are related to an
> existing SendStream then we will in the relevant |Stream.send| slot.
> Otherwise, we create a new SendStream that's related to the incoming
> stream and notify the application of the creation of the new
> bidirectional stream.
>
> Note that this all works fine if one side does the undirectional API
> and one does the bidirectional API. My test programs actually exercise
> this. Of course, there's an assumption that the peer conforms to a 1:1
> mapping. If we define unidirectional streams, we'll need some protocol
> mechanism to know if the other side is exercising this level of
> increased flexibility or not. I can imagine a number of options here
> (e.g., ALPN).  We could also forbid 1:N mappings but I think that
> would be a mistake as it's a cool feature/benefit of doing
> unidirectional.
>
> The entire bidirectional wrapper shim is < 150 lines of Go code.
> (https://github.com/ekr/minq/blob/unidirectional_streams/bidi.go).
> Converting my test application to this API was a matter of just
> changing class names, e.g., s/Connectionb/Connection2/.
>
> In my implementation, I assume that at the time Minq hears about a
> stream, you know if its related to a given existing stream.  That way
> you can immediately either associate it with that stream or make a new
> local stream. In my implementation, I always send Related Stream Id
> and assume that you never get an "unrelated" stream frame before a
> "related" one. The spec doesn't really require that right now, and
> offline MT suggested just sending related with offset=0 but I think
> that's a mistake, because it means that you need to hold stream frames
> in some provisional "undetermined" state until you get that frame. I
> would suggest instead that we require that you include the field until
> one of the frames is ACKed.
>
>
> INTERNALS
> Sending and receiving streams still share a lot of common components:
>
>     type baseStream struct {
>     state         streamState
>     id            uint32
>     log           loggingFunction
>     offset        uint64
>     chunks        []streamChunk
>     maxStreamData uint64
>     isRelated     bool
>     related       uint32
>     }
>
>     type sendStream struct {
>     baseStream
>     blocked bool
>     }
>
>     type recvStream struct {
>     baseStream
>     }
>
> Most of this is the same as with bidirectional streams.  As above,
> it's probably possible to make them more asymmetrical.
>
> The connection maintains separate lists of sending and receiving
> streams and it's straightforward to create and access them without
> worrying about the odd/even stuff.
>
>
> COMPARISON
> At the end of the day, I think this shows that these designs aren't
> really that disssimilar. I was able to convert Minq to unidirectional
> streams in about 16 total hours of work (basically a long plane flight
> plus the next morning). While I had to make a bunch of changes to the
> internal structures, basically none of them modified anything tricky,
> and in particular the flow control mechanics and the like are
> basically unchanged, except for a bunch of mechanical-type
> transformations like referring to |sendStream.chunks| instead of
> |stream.send.chunks|. The only really new protocol machinery is the
> new frame format for related streams.
>
> There are a few pros/cons that are worth noting about these designs.
>
> - Without a bidirectional API, having unidirectional streams is more
>   work for the programmer. However, with an API shim, the difference
>   is trivial.
>
> - Because undirectional streams are inherently more flexible, it's
>   possible for the sides to try to use different mappings, e.g., one
>   side expects paired and the other expects 1:N. We'll need some way
>   of making sure that doesn't happen, maybe ALPN?
>
> - The "Related Stream ID" frame indicator needs fleshing out a bit.
>   From the application's perspective, it should never hear about a
>   stream without knowing its related status. And as noted above, I
>   think it would be best if we required that all "first flight" stream
>   frames that are related include the fied
>
> - Undirectional streams kind of sharpen the confusion about exactly
>   what kinds of "closure" we want to allow. Specifically, what should
>   implementations be able to say about their willingness to receive?
>   Right now we have STOP_SENDING, but that doesn't influence the
>   sender's state. I don't think undirectional streams make this worse,
>   they just require us to think it through some more. They do simplify
>   the implementation of the closure state machine: in my QUIC-05 code,
>   whenever one side closes I have to have checks to see if I should be
>   transitioning to CLOSED or HALF-CLOSED, etc, which is odd because
>   the directions are basically independent.  It would probably be
>   easier even in QUIC-05 not to reify these states but just to
>   determine the state from the composition of the individual
>   sub-states
>
> - Unidirectional streams don't need the kind of annoying odd-even
>   mechanics, which was easier to code up (just having to create all
>   the lower-numbered streams of the same parity is kind of a pain).
>   One additional benefit here is that with QUIC-05 there are several
>   messages which involve implicit stream creation (e.g.,
>   STREAM_MAX_DATA, and RST_STREAM) and so you need to check whether
>   the stream is one that should have been created locally or
>   remotely. This just doesn't happen with bidirectional streams; I do
>   implement odd/even mechanics but because the other side has to have
>   its stream ids increment by one, I can make sure that they have the
>   right IDs by construction and just check to see if the stream exists
>   in these cases.  I'd like to see us get rid of odd/even no matter
>   what.
>
> - Unidirectional streams also helps avoid some of the corner cases around
>   bidirectional streams. Specifically, suppose I am the client and
>   I get MAX_STREAM_DATA as the first frame on stream 2. Am I allowed
>   to just start sending or not? You can sort of get into this situation
>   with unidirectional streams, but because it's explicit, one might
>   hope that the application semantics would require clear specification.
>
> - As noted above, bidirectional streams are more flexible because they
>   let you have mappings that you can't have with unidirectional
>   streams (unpaired, 1:N).
>
>
> Happy to answer more questions if people have them. Otherwise we can
> talk about this in Seattle.
>
> -Ekr
>
>
> [0] https://github.com/ekr/minq/tree/unidirectional_streams
> [1] https://github.com/ekr/wg-materials/blob/
> 404898fa2d2f0a9f9bd244d2c945e66ea88502a2/interim-17-10/
> Unidirectional%20Streams%20in%20Minq.pdf
> [2] Thanks to Patrick McManus for suggesting this design.
> [3] In C++, you would have a single function with a default argument of
>     |nullptr| but Go doesn't support that, hence two different arguments.
> [4] For implementation reasons, it's actually using Connection as a mixin,
>     which means it's simultaneously possible to use the unidirectional
>     and bidirectional APIs, but that's going to cause a lot of confusion.
>     A real implementation would probably have to either commit to one
>     or the other or do a real wrapper, so you could only use one set of
>     APIs, at the cost of having to do more forwarded methods.
>
>
>
>
>
>
>
>
>
>
>