Report on Unidirectional Streams in Minq

[Eric Rescorla <[e-mail]>]

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.