Network Working Group M. Piatek Internet-Draft W. Chan Intended status: Standards Track Google Expires: July 10, 2014 January 6, 2014 HTTP/2 Stream Dependencies draft-chan-http2-stream-dependencies-00 Abstract The existing HTTP/2 prioritization scheme relies purely on integer values to indicate priorities. This simple scheme misses critical support for priority grouping, and does not support other features like resource ordering. This draft proposes using stream dependencies to solve the lack of priority grouping, as well as provide other features. Status of this Memo This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet- Drafts is at http://datatracker.ietf.org/drafts/current/. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." This Internet-Draft will expire on July 10, 2014. Copyright Notice Copyright (c) 2014 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as Piatek & Chan Expires July 10, 2014 [Page 1] Internet-Draft Stream Dependencies January 2014 described in the Simplified BSD License. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . 3 3. Protocol Changes . . . . . . . . . . . . . . . . . . . . . . . 4 3.1. HEADERS frame . . . . . . . . . . . . . . . . . . . . . . 4 3.2. PRIORITY frame . . . . . . . . . . . . . . . . . . . . . . 5 3.3. END_STREAM_ACK frame . . . . . . . . . . . . . . . . . . . 6 4. Protocol invariants and definitions . . . . . . . . . . . . . 6 5. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 5.1. Specifying an ordering of resource transfers and reacting to document parsing . . . . . . . . . . . . . . . 10 5.2. Servicing multiple tabs/users over a single HTTP/2 connection . . . . . . . . . . . . . . . . . . . . . . . . 13 5.3. Server Push . . . . . . . . . . . . . . . . . . . . . . . 13 6. Policy Considerations . . . . . . . . . . . . . . . . . . . . 13 6.1. Assigning and updating dependencies . . . . . . . . . . . 13 6.2. Server scheduling . . . . . . . . . . . . . . . . . . . . 14 6.3. Garbage collecting dependency information . . . . . . . . 14 7. Security Considerations . . . . . . . . . . . . . . . . . . . 15 8. Informative References . . . . . . . . . . . . . . . . . . . . 15 Appendix A. Acknowledgements . . . . . . . . . . . . . . . . . . 15 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 15 Piatek & Chan Expires July 10, 2014 [Page 2] Internet-Draft Stream Dependencies January 2014 1. Introduction This document proposes changes to HTTP/2 to support stream dependencies. During a pageload, the server uses dependencies to improve performance by allocating bandwidth capacity to the most important resource transfers first. The remainder of this document describes the motivation for dependencies, protocol changes to support them, and examples of how those mechanisms can be used by the browser. We conclude with a discussion of the client and server policies afforded by expressing dependency information in HTTP/2. (Note that flow control is the subject of a separate document and is out of scope here.) 2. Motivation Dependencies allow an HTTP/2 server to allocate bandwidth capacity efficiently in several common use-cases: Specifying an ordering of resource transfers Sharing bandwidth between resources transfer often degrades performance, e.g., when transferring two Javascript resources that cannot be executed until transfer is complete, or two video chunks that will be played back-to-back. In these circumstances, the browser may wish to specify an ordering --- HTML before script1.js before script2.js, for example, or video_chunk1 before video_chunk2. Reacting to document parsing Because the browser's document parser blocks while waiting for script and style resource transfers to complete, many resource requests will be issued by simply scanning the tokenized HTML. (For more background, see [PRELOADSCANNER]) As the document parser proceeds, it may learn of higher priority resources. For example, if a script a.js uses document.write to embed another script, b.js, the transfer of b.js should preempt other in-flight resource transfers since the receipt of b.js blocks page layout. Similarly, image transfers that will be styled with display: none should be deferred to prioritize visible content. Piatek & Chan Expires July 10, 2014 [Page 3] Internet-Draft Stream Dependencies January 2014 Reacting to user behavior In the case of HTTP/2 proxies, a single TCP connection may multiplex several sites in several tabs. Changing tabs may reorder the relative importance of outstanding streams, e.g., concurrent AJAX requests or page loads. Similarly, a proxy server may coalesce streams to a common origin onto a single connection. As the set of outstanding requests and users changes, the relative importance of each user's streams may change as well. Server Push Server push can improve performance by eliminating round trips, but it may degrade performance if a pushed stream preempts a more important transfer. For example, a Javascript transfer may block layout and be high priority, or it may be a low-priority async request. Dependencies provide a hint to the server about the relative importance of pushed resources. 3. Protocol Changes Dependencies are expressed using the existing optional priority field the HEADERS frames and in PRIORITY frames. To ensure clients and servers have consistent view of active streams, we propose the FIN_ACK frame. The section concludes with a set of invariants that clients and servers must maintain when using these frames. 3.1. HEADERS frame 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |P| PriOrDep (31) | +-+-------------------------------------------------------------+ | Header Block Fragment (*) ... +---------------------------------------------------------------+ HEADERS Frame Payload The HEADERS frame defines the following flags: ORDERED (0x10): Bit 5 being set indicates that the dependency specified by PriOrDep is ordered. If this flag is unset, any dependency is treated as unordered. Here, the 4 octets previously used by the unused bit and 31 bit Priority field in the HEADERS frame are reinterpreted. The unused bit is now known as the P bit, and the 31 bit Priority field is now Piatek & Chan Expires July 10, 2014 [Page 4] Internet-Draft Stream Dependencies January 2014 PriOrDep. P: A bit indicating whether the following PriOrDep bits specify a priority (P = 1) or a stream ID (P = 0) on which this new stream depends. PriOrDep: Depending on the value of P, either the priority of the new stream or a stream ID on which this new stream depends. The structure and semantics of the Header Block Fragment are unchanged. P is exclusive; a stream may be assigned a priority or a parent dependency upon creation, but not both. If P = 0 and PriOrDep indicates a dependency; the value MUST correspond to an active stream. Server push streams are assigned a priority or dependency id at the discretion of the server. 3.2. PRIORITY frame 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |P| PriOrDep (31) | +-+-------------------------------------------------------------+ PRIORITY Frame Payload The PRIORITY frame defines the following flags: ORDERED (0x10): Bit 5 being set indicates that the dependency specified by PriOrDep is ordered. If this flag is unset, any dependency is treated as unordered. As in HEADERS, the Priority field is changed to be a P/PriOrDep field indicating an update to the 31 bit Dependency Id specified in the header. We relabel the typical Stream Id here as Dependency Id to distinguish it as a referent. To support batched updates of dependencies, an optional list of DependencyPriOrDep pairs with identical semantics may follow. The number of such pairs is determined by examining the frame length. Piatek & Chan Expires July 10, 2014 [Page 5] Internet-Draft Stream Dependencies January 2014 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |X| Dependency Id (31) | +---------------------------------------------------------------+ |P| PriOrDep (31) | +-+-------------------------------------------------------------+ DependencyPriOrDep 3.3. END_STREAM_ACK frame The END_STREAM_ACK frame has no payload. It is sent by a client to a server after receiving a frame with the END_STREAM flag set. The frame is used to ensure a consistent set of active streams between the client and the server. Consistency is required to maintain the protocol invariants described below. 4. Protocol invariants and definitions Each stream has at most one dependency An update to a stream's dependent stream id replaces any existing dependency for the claimant. Specifying multiple dependency ids for a single stream in a PRIORITY frame is a protocol error. Each stream is depended on by at most one stream An update to a stream's dependent stream id replaces any existing dependency on the target. Repeating a single dependency id in a PRIORITY frame is a protocol error. Each dependency has a type: ordered or unordered Ordered dependencies indicate a sequential transfer preference with respect to the dependent stream id. Unordered dependencies indicate a concurrent transfer preference for the range of the dependency list with unordered dependency links. For example, where <- indicates an ordered dependency and - indicates an unordered dependency a.htm <- a.js <- 1.png - 2.png indicates that a.html should preempt a.js which itself should preempt 1.png and 2.png, each of which should transfer concurrently, sharing capacity. Piatek & Chan Expires July 10, 2014 [Page 6] Internet-Draft Stream Dependencies January 2014 All frames with the END_STREAM flag set MUST be explicitly acknowledged by clients To ensure that the client and server have an identical view of active stream ids when specifying dependencies, we require that clients explicitly acknowledge frames with the END_STREAM flag set by sending END_STREAM_ACK. Servers MUST retain dependency relationships for a stream until its END_STREAM_ACK is received (or the session is closed). Explicit acknowledgements obviate timeouts for garbage collecting dependency state and enable clients and servers to have a consistent view of dependency relationships. A dependency id MUST correspond to an active stream id An active stream id is one for which the client has not yet sent an END_STREAM_ACK frame. It is a protocol error to name a stream id as a dependency that is not active. If a server receives an END_STREAM_ACK for a stream X on which another stream Y depends, it SHOULD update the dependency pointer for Y to reflect the removal of X. The rules for updating dependencies are: 1. If X does not depend on another stream id, Y inherits the priority of X. 2. If X does depend on another stream id W, Y inherits the dependency pointer from X to W. For example, for dependencies a.htm <- a.js <- 1.png - 2.png where the server receives an END_STREAM_ACK for 1.png, the resulting dependencies would be a.htm <- a.js <- 2.png Of course, clients may reconfigure dependencies using whatever policy they wish by sending an explicit PRIORITY frame for stream Y before the END_STREAM_ACK for stream X. Updating dependencies when overwriting values is analogous to list insertion. If stream Y depends on X and a HEADERS or PRIORITY frame is received indicating a dependency on X for stream Z, Z replaces Y as X's dependent, and Y's dependency is updated to Z with the same ordering as it had to X. For example, if a.htm - 1.png Piatek & Chan Expires July 10, 2014 [Page 7] Internet-Draft Stream Dependencies January 2014 and the server receives a HEADERS frame for a.js with an ordered dependency on a.htm, the result is a.htm <- a.js - 1.png 5. Examples The combination of dependencies and priorities suffices to express serialized as well as concurrent transfer schedules. But, how should the browser choose dependencies and priorities when making requests? This question is best answered quantitatively. As a starting point, we consider the following policy in our examples: 1. Resource dependencies reflect parser-blocking order. Non- streaming resources are serialized; i.e., non-async scripts and styling. 2. Progressive resources (e.g., images) are transferred concurrently and configured to depend on parser-blocking resource transfers. 3. To ensure that the speculative parser can maintain enough in- flight requests to fill the pipe between the client and server, page HTML does not depend on other streams. (Although, a background tab should have lower priority.) Concretely, suppose a HTTP/2 connection is multiplexing multiple tabs from a user connected to a HTTP/2 proxy, with parent pointers and priorities as shown below. (P6, for example, indicates a priority of 6.) Piatek & Chan Expires July 10, 2014 [Page 8] Internet-Draft Stream Dependencies January 2014 +----------------+ +----------------+ | | | | | Tab1.html (P6) | | Tab2.html (P6) | | | | | +----------------+ +----------------+ ^ ^ | | + + +----------------+ +----------------+ | | | | | a.js | | a.jpg | | | | | +----------------+ +----------------+ ^ | | | + | +----------------+ +----------------+ | | | | | b.js | | b.jpg | | | | | +----------------+ +----------------+ Figure 1: Multiple Tab Example To color in this example, suppose that Tab 1 is the foreground tab, loading in parallel with Tab 2 in the background. Thus, its relatively higher weight. a.js and b.js are scripts required for the first tab and should be transferred serially (as scripts are executed in the order they are declared in the document, and are not parsed until transfer completes.) Thus, a.js depends on b.js depends on tab1.htm. In the background tab, two image transfers share capacity as both can be rendered progressively. Thus, the dependency between b.jpg and a.jpg is unordered, indicating that writes for the tab2.html stream should be scheduled first, but capacity may be shared between the streams for a.jpg and b.jpg. When scheduling transfers, we consider a server that treats dependencies conceptually as lists. Recall that streams depend on and are depended on by at most one other stream. These can be treated as predecessor and successor ids. Stream writes are scheduled in two steps: 1) choosing a dependency list with at least one stream ready to write and 2) then selecting the stream to write by traversing the list. (An implementation might maintain ready queues of streams for efficiency, but we consider a simplified setting for clarity.) Because the streams associated with the transfers of tab1 and tab2 have priorities rather than dependencies, they are always scheduled Piatek & Chan Expires July 10, 2014 [Page 9] Internet-Draft Stream Dependencies January 2014 before any dependent streams. But, bandwidth allocation between dependency lists remains proportional as defined by the relative priority of tab1 and tab2. For example, if the transfer of tab2.htm is in progress and tab1.htm (now complete) is ready and selected by the scheduler, a.js will be scheduled before tab2.htm completes. This process proceeds until all transfers in a list have completed. 5.1. Specifying an ordering of resource transfers and reacting to document parsing We illustrate the need for both serial dependencies, concurrency, and reprioritization in these cases with a simple example. Suppose site.com has index.htm: with a.js: document.write(''); and b.js: document.write('
blocker
'); How would this example page be transferred today? As the main HTML is received and parsed, a request for a.js will be issued and block the document parser. As the remaining HTML streams in, the speculative parser will issue requests for a.jpg and b.jpg in quick succession. Once a.js is received and executed, a request for b.js will be issued, which again blocks parsing until received. Visually: Piatek & Chan Expires July 10, 2014 [Page 10] Internet-Draft Stream Dependencies January 2014 Client Server + + |+ GET index.htm | |+------------------->| | index.htm +| |<-------------------+| |+ GET a.js | |+------------------->| |+ GET a.jpg | |+------------------->| |+ GET b.jpg | |+------------------->| | a.js +| |<-------------------+| |+ GET b.js | |+------------------->| | a.jpg +| |<-------------------+| | b.jpg +| |<-------------------+| | b.js +| |<-------------------+| | | v v This transfer schedule is suboptimal. Page rendering will complete only when once b.js has completed, but receiving b.js is slowed by competition for bandwidth capacity for a.jpg and b.jpg, which do not block rendering. Ideally, the order resources are transferred would reflect the document parse order with bandwidth sharing only for progressive resources. More specifically, we want to receive: 1) index.htm, 2) a.js, and 3) b.js sequentially. After those critical transfers have completed, a.jpg and b.jpg should be transferred concurrently since they may be displayed progressively. Folding in the protocol mechanisms described above: Piatek & Chan Expires July 10, 2014 [Page 11] Internet-Draft Stream Dependencies January 2014 Client Server | Scheduling + + | |+ 1: GET index.htm (P3) | | |+----------------------->| | index.htm (P3) | index.htm +| | |<-----------------------+| |==================================== |+ 3: GET a.js (S1) | | +--------------+ |+----------------------->| | |index.htm (P3)| |+ 5: GET a.jpg (S3) | | +--------------+ |+----------------------->| | ^ |+ 7: GET b.jpg (S5=) | | |---- a.js <- a.jpg - b.jpg |+----------------------->| |==================================== | a.js +| | |<-----------------------+| | |+ 9: GET b.js (S1) | | +--------------+ +----+ |+----------------------->| | |index.htm (P3)| <- |a.js| | b.js +| | +--------------+ +----+ |<-----------------------+| | ^ | a.jpg +| | |-------------------| |<-----------------------+| | | | b.jpg +| | |-b.js <- a.jpg - b.jpg |<-----------------------+| | | | | v v | In the figure, each resource request corresponds to a new HTTP/2 stream with the form ID: request (PriOrDep). In more detail: o The HEADERS for the index.htm request indicates a default priority (3) and a stream id of 1. o The document parser is blocked once the external script a.js is parsed. At this point, the speculative parser looks ahead and creates new streams for a.jpg and b.jpg in parse order. a.jpg and b.jpg can be progressively rendered, so their transfer is concurrent (a.jpg has an ordered dependency on a.js, and b.jpg has an unordered dependency on a.jpg). o Once a.js completes, the document parser continues by executing a.js and inserting b.js via document.write(), again blocking document parsing on the receipt of b.js. At this point, b.js should preempt all other transfers since it's a non-streaming resource that is blocking page rendering. To this end, the client creates the b.js stream which depends on a.js (or, equivalently, index.htm). This transfer schedule improves performance by serializing the transfer of resources on the critical path. The browser can ensure Piatek & Chan Expires July 10, 2014 [Page 12] Internet-Draft Stream Dependencies January 2014 that resources needed immediately do not compete for bandwidth capacity with less important transfers. The pipe remains full, as a queue of requests is maintained in the dependency list, filling any idle capacity with useful data. Where we cannot make an informed scheduling decision, we hedge our bets with concurrent transfers by hinting that they are unordered and letting the server decide what makes the most sense --- as in the case of two above the fold images that can be rendered progressively. 5.2. Servicing multiple tabs/users over a single HTTP/2 connection As an illustration of this case, recall the example (Figure 1) from our straw-man design. Suppose concurrent tabs are loading with the dependencies shown. When a user changes tabs, the browser sends a PRIORITY frame updating the stream associated with tab2.htm to, say, priority 8. (A batched message might also reduce the priority of tab1.htm to weight 3.) Because bandwidth is allocated among streams with priorities before considering their dependents, increasing the priority of tab2.htm effectively shifts capacity for all resource transfers depending on tab1.htm to tab2.htm. 5.3. Server Push Push streams are assigned a priority or dependency at the discretion of the server. Typically, the Promised-Stream-ID would depend on the stream id carrying the PUSH_PROMISE frame. As information about resources needed for parsing is learned, the browser may update the dependency relationship by sending a PRIORITY message. 6. Policy Considerations Both priorities and stream dependencies are advisory hints. Browsers may adopt sophisticated policies or leave dependencies entirely unspecified. Similarly, servers may incorporate dependency hints into very sophisticated schedulers or ignore them entirely. The protocol mechanisms for encoding dependencies are designed to be simple. But, these mechanisms afford a very flexible set of policies depending on how browsers and servers use them. This section expands on several policy considerations. 6.1. Assigning and updating dependencies In our examples, we consider a browser that configures dependencies to reflect parser-blocking order for resources, updated as parsing continues. We expect this to improve performance, but browsers are Piatek & Chan Expires July 10, 2014 [Page 13] Internet-Draft Stream Dependencies January 2014 free to deviate from this policy, and there may be good reasons to do so. For example, if the parser-blocking order is highly dynamic (e.g., in response to many JS events), the overhead of updating dependencies may not be worth the cost, particularly for small transfers. A sophisticated client may base dependency update decisions on content-length and/or RTT, restricting updates to only those streams likely to benefit from it. Quantitative implementation experience is needed to determine how best to assign and update dependencies. 6.2. Server scheduling A conformant server should respect the semantics of priorities and dependencies in its scheduling policy. Priorities indicate a preference for weighted scheduling (e.g., using a lottery scheduler [LOTTERYSCHEDULING]) among top-level streams; i.e., those created with a priority and not a dependency. Capacity should be shared among a sequence of streams with unordered dependencies. Server scheduling should reflect guidance from dependencies, but it need need not be strict. If all streams in a dependency tree have data available to write at the server, writes should be serviced first for top-level streams, then ordered dependents, with sharing among unordered streams. But, depedents that are ready to write should not starve to enforce a scheduling dependency. In other words, scheduling dependencies should not lead servers to waste capacity. If data is not available to continue writing the top-level stream, for example, a dependent ready to write should do so. Finally, we point out that servers may improve performance even if clients do not provide dependency information or priorities. For example, an intelligent server may inspect the content type of resources to make informed prioritization decisions on its own without client guidance. (However, respecting client-provided hints when available is likely to improve performance, as clients have detailed knowledge of parser dependencies.) 6.3. Garbage collecting dependency information HTTP/2 implementations must take care to protect themselves from the use of dependencies as a DoS vector. The protocol provides wide flexibility in this regard; servers are free to drop dependency or priority data at any time without sacrificing correctness. Typically, we envision servers will drop dependency information along with other stream state when an END_STREAM_ACK frame is received or the session is closed. Piatek & Chan Expires July 10, 2014 [Page 14] Internet-Draft Stream Dependencies January 2014 7. Security Considerations TODO 8. Informative References [LOTTERYSCHEDULING] Waldspurger, C. and W. Weihl, "Lottery scheduling: flexible proportional-share resource management", 1994, . [PRELOADSCANNER] Gentilcore, T., "The WebKit PreloadScanner", 2011, . Appendix A. Acknowledgements This document resulted from discussions amongst the SPDY team at Google. The authors merely took that discussion and edited this document. The individuals who contributed to those discussions include, but are not limited to: Roberto Peon, Hasan Khalil, Ryan Hamilton, Jim Roskind, Bryan McQuade, Chris Bentzel, Ilya Grigorik. Authors' Addresses Michael Piatek Google Email: piatek@chromium.org William Chan Google Email: willchan@chromium.org Piatek & Chan Expires July 10, 2014 [Page 15]