Re: Report on Unidirectional Streams in Minq

Eric Rescorla <ekr@rtfm.com> Sun, 01 October 2017 21:04 UTC

Return-Path: <ekr@rtfm.com>
X-Original-To: quic@ietfa.amsl.com
Delivered-To: quic@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id D3E20134B1E for <quic@ietfa.amsl.com>; Sun, 1 Oct 2017 14:04:07 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.599
X-Spam-Level:
X-Spam-Status: No, score=-2.599 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_LOW=-0.7] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=rtfm-com.20150623.gappssmtp.com
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id DxU1mIED8ZHs for <quic@ietfa.amsl.com>; Sun, 1 Oct 2017 14:04:03 -0700 (PDT)
Received: from mail-yw0-x236.google.com (mail-yw0-x236.google.com [IPv6:2607:f8b0:4002:c05::236]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 49FD0134B22 for <quic@ietf.org>; Sun, 1 Oct 2017 14:04:03 -0700 (PDT)
Received: by mail-yw0-x236.google.com with SMTP id i83so691001ywb.7 for <quic@ietf.org>; Sun, 01 Oct 2017 14:04:03 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=rtfm-com.20150623.gappssmtp.com; s=20150623; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=uYa1UPf1uTXLsFpjPOCcQAVJ76F66WpE/KeGjp8wQVc=; b=EJ6ithkRooMJDxACezhSpgVxIlNEWggcpNYoyDsKPZrx+nGLtzWcOh61aNCiBd55X0 rdsJRipRlsNpLlyJgCuepSe9uBoLvKslUPco8X96HTydCdGpUuRqYDlaj4xL9ZkvzWUL 3EcaDCAAUILDE2nCqTRigetzJyyikBewdJ3kRgg/ol0zeDQFclOcBydIdHUi7thj42rV INr0atqccxP2p2qxM1DuUMrT5CrwUOE2sasT5KSTgBEXaZnASdUoOaTvrZ13rFsB5vh9 kodMj4rYEWSekw+Bt5KwVn72z1kZavXCh5+SmDx5k+gANqsPa/W5JdmJC0qMo5598NRP bO3w==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=uYa1UPf1uTXLsFpjPOCcQAVJ76F66WpE/KeGjp8wQVc=; b=c639+hHaxaI+cV+SpbE1Qzds7aimvKHSY/V49aKEsSUFZEu7maye/Y8X45M7rzuQnz 17Gmbvi1Y9+N6MQFsK9eihUuI9meiX/HzsHGYxtLHmdRK8UQ9mthbTNLfaA6SBo8RCu9 HYzCNIcMU2AD6rJ5OGfdcBa/KUeQX7XEHAKCNSfseL3GC2IJShbGYk8uZZyeBU7Lpprp 7Xr80MF8ty8BQhktJAKpr7GdHgPffHR4cXmnJTWE8lGCSgVe7ARIT3xd+3Bs+qDf6oyL hV/UW8xVHbH8+4vpc+C7ui9wdZM9mQwO4zjOYZkl1s8PAfCT7bnoMoG+PO5HAtOZ6onH m5BA==
X-Gm-Message-State: AMCzsaXylIE8+osxM4ITijPS8blcx8yw/Lj+wyJjD2NjOsEJV3NDcrzm e497oodcFsIRUtvnhY0EobtlbGEX9L6CCQ+nMoBxwA==
X-Google-Smtp-Source: AOwi7QBZBgoUykzuKnCfbyoSx8ttxzjWTAfI5fKezItTXOJDDyul7iBy+8BXhrejggtwy8xfxa8e818W178pDU1AMnU=
X-Received: by 10.37.189.76 with SMTP id p12mr282320ybm.462.1506891842354; Sun, 01 Oct 2017 14:04:02 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.129.75.194 with HTTP; Sun, 1 Oct 2017 14:03:21 -0700 (PDT)
In-Reply-To: <CAN1APdfaGmHUHSVOWOSaiM5TB7-tNn22EHt46_5t4RByM_QFXw@mail.gmail.com>
References: <CABcZeBMS5U6u=O+K_rx=JPXoN8cwNAo-raQLSrf=g9A7z6SE9A@mail.gmail.com> <CAN1APdfaGmHUHSVOWOSaiM5TB7-tNn22EHt46_5t4RByM_QFXw@mail.gmail.com>
From: Eric Rescorla <ekr@rtfm.com>
Date: Sun, 1 Oct 2017 14:03:21 -0700
Message-ID: <CABcZeBM73ikZrszEBoLxbqtoOcc5WQpwM541ii0Jvu5wmywKOw@mail.gmail.com>
Subject: Re: Report on Unidirectional Streams in Minq
To: =?UTF-8?Q?Mikkel_Fahn=C3=B8e_J=C3=B8rgensen?= <mikkelfj@gmail.com>
Cc: IETF QUIC WG <quic@ietf.org>
Content-Type: multipart/alternative; boundary="089e0828b4f0fa9630055a8298be"
Archived-At: <https://mailarchive.ietf.org/arch/msg/quic/fBAGQZYB4lXsCpFo1UIsJ9OTls4>
X-BeenThere: quic@ietf.org
X-Mailman-Version: 2.1.22
Precedence: list
List-Id: Main mailing list of the IETF QUIC working group <quic.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/quic>, <mailto:quic-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/quic/>
List-Post: <mailto:quic@ietf.org>
List-Help: <mailto:quic-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/quic>, <mailto:quic-request@ietf.org?subject=subscribe>
X-List-Received-Date: Sun, 01 Oct 2017 21:04:08 -0000

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 <mikkelfj@gmail.com>
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 (ekr@rtfm.com) 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.
>
>
>
>
>
>
>
>
>
>
>