Re: QPACK and the Static Table
Roberto Peon <fenix@fb.com> Thu, 24 May 2018 18:40 UTC
Return-Path: <prvs=868201a72d=fenix@fb.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 947ED12E898 for <quic@ietfa.amsl.com>; Thu, 24 May 2018 11:40:18 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.709
X-Spam-Level:
X-Spam-Status: No, score=-2.709 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_LOW=-0.7, SPF_PASS=-0.001, T_DKIMWL_WL_HIGH=-0.01, T_DKIMWL_WL_MED=-0.01, T_KAM_HTML_FONT_INVALID=0.01, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=fb.com header.b=PTgh3dOd; dkim=pass (1024-bit key) header.d=fb.onmicrosoft.com header.b=Z45efed2
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 IFgDdEZf73S9 for <quic@ietfa.amsl.com>; Thu, 24 May 2018 11:40:14 -0700 (PDT)
Received: from mx0b-00082601.pphosted.com (mx0b-00082601.pphosted.com [67.231.153.30]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 0AB1A12EB00 for <quic@ietf.org>; Thu, 24 May 2018 11:40:13 -0700 (PDT)
Received: from pps.filterd (m0148460.ppops.net [127.0.0.1]) by mx0a-00082601.pphosted.com (8.16.0.22/8.16.0.22) with SMTP id w4OIck1Q031746; Thu, 24 May 2018 11:39:47 -0700
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=fb.com; h=from : to : cc : subject : date : message-id : references : in-reply-to : content-type : mime-version; s=facebook; bh=sItpZMGMPz212YUgJF7gc9rfUNo+SWqXomxYfreEq2M=; b=PTgh3dOdYL/oMtf0PSJFJjpI6ad9T60XVguh+XA+juNkCnWNGxwcoz0MvY/evly85zrQ bKkMqELgkdNAyIy8t3nWEUsX4EXvHcQE8+NWQndxmRgHl9hV2HE14SzAE3EGNghCrAhz 580JPimVwxcuP5UdfFmyrZuhJU1cBZUe6vg=
Received: from mail.thefacebook.com ([199.201.64.23]) by mx0a-00082601.pphosted.com with ESMTP id 2j61qpr81p-1 (version=TLSv1 cipher=ECDHE-RSA-AES256-SHA bits=256 verify=NOT); Thu, 24 May 2018 11:39:46 -0700
Received: from NAM02-CY1-obe.outbound.protection.outlook.com (192.168.54.28) by o365-in.thefacebook.com (192.168.16.17) with Microsoft SMTP Server (TLS) id 14.3.361.1; Thu, 24 May 2018 11:39:43 -0700
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=fb.onmicrosoft.com; s=selector1-fb-com; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=sItpZMGMPz212YUgJF7gc9rfUNo+SWqXomxYfreEq2M=; b=Z45efed2nyuzKqrizqv/l5kRSsQMsUfSt2RMgD3b+Ov0uTHiFORsS3HhTV/Fh8MRSNDGj/3A0UQgYZrdTMRM96EL1dBFv2t6qrNV2WSalVC4ec7AA5CyJH8YhMKjSb8TGcLPMp4UhPubN56p4UPkyFk7BSQwMQYU9cTBOm3Z6BA=
Received: from BYAPR15MB2312.namprd15.prod.outlook.com (52.135.197.146) by BYAPR15MB2406.namprd15.prod.outlook.com (52.135.198.143) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA384_P256) id 15.20.776.11; Thu, 24 May 2018 18:39:41 +0000
Received: from BYAPR15MB2312.namprd15.prod.outlook.com ([fe80::b434:da9b:6102:49eb]) by BYAPR15MB2312.namprd15.prod.outlook.com ([fe80::b434:da9b:6102:49eb%13]) with mapi id 15.20.0776.019; Thu, 24 May 2018 18:39:41 +0000
From: Roberto Peon <fenix@fb.com>
To: Mike Bishop <mbishop@evequefou.be>, Willy Tarreau <w@1wt.eu>
CC: "quic@ietf.org" <quic@ietf.org>, HTTP Working Group <ietf-http-wg@w3.org>
Subject: Re: QPACK and the Static Table
Thread-Topic: QPACK and the Static Table
Thread-Index: AdPy6/ObcVQE/1QBQB2X+UF0YtinwQALZGwAAAz5BYAAD2QCcP//kdoA
Date: Thu, 24 May 2018 18:39:41 +0000
Message-ID: <B0995EA8-A329-49F3-8B47-0F6042D38DFC@fb.com>
References: <SN1PR08MB1854395A2875541C4DC0673DDA6B0@SN1PR08MB1854.namprd08.prod.outlook.com> <20180524044146.GA5215@1wt.eu> <993659D9-8A3B-4375-AEC6-0B7706F96B42@fb.com> <SN1PR08MB185459B20E930B87BAE380EFDA6A0@SN1PR08MB1854.namprd08.prod.outlook.com>
In-Reply-To: <SN1PR08MB185459B20E930B87BAE380EFDA6A0@SN1PR08MB1854.namprd08.prod.outlook.com>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
user-agent: Microsoft-MacOutlook/10.d.0.180513
x-originating-ip: [2620:10d:c090:200::7:88c]
x-ms-publictraffictype: Email
x-microsoft-exchange-diagnostics: 1; BYAPR15MB2406; 7:jerfUeHZLTOQ858ASLPJ3iEE7UpUBWPoGiXCe8atfteh4ccv/IcQbSKWyjdl5i3OtygtGyY+VC6Ajxkjb2nK7EiYfhhqM+YnMiShc8l6YiVFhG+6r74VDTDJvVeRl/BUyq4z422kW9b/XQGOdXxaJgJtBt6Ekurcc9le4vfBf+LSzBA+03yVxUjTRWKRFZ/gQ7Ka+kphLasb7oi8om8G1l1f20RyIYVMlN/oroBIZTFzT68I3eJO9VmpuMJFloA8; 20:k4vroE5Rwl90+rV4gXWiHXqP2fXYcoY5+fhJ5N1sW+yN26JEQOW3tFbPMnBb0GlEzf3nKCVgWp26pALkj1siTNcsxqND0bs8g6db8kaE+Z7+TkfTDMvJpy5ANpaZGbbjfItc8hg7HWb0Dkxr88LuYj/gRn7H2rqMevVIxUEjIrk=
x-ms-exchange-antispam-srfa-diagnostics: SOS;
x-microsoft-antispam: UriScan:; BCL:0; PCL:0; RULEID:(7020095)(4652020)(5600026)(4534165)(4627221)(201703031133081)(201702281549075)(2017052603328)(7153060)(7193020); SRVR:BYAPR15MB2406;
x-ms-traffictypediagnostic: BYAPR15MB2406:
x-microsoft-antispam-prvs: <BYAPR15MB24063F33D8411F876D31CEE2CD6A0@BYAPR15MB2406.namprd15.prod.outlook.com>
x-exchange-antispam-report-test: UriScan:(28532068793085)(158342451672863)(166708455590820)(67672495146484)(21748063052155)(17755550239193);
x-ms-exchange-senderadcheck: 1
x-exchange-antispam-report-cfa-test: BCL:0; PCL:0; RULEID:(8211001083)(6040522)(2401047)(8121501046)(5005006)(93006095)(93001095)(3231254)(11241501184)(944501410)(52105095)(10201501046)(3002001)(149027)(150027)(6041310)(201703131423095)(201702281528075)(20161123555045)(201703061421075)(201703061406153)(20161123564045)(20161123562045)(20161123560045)(20161123558120)(6072148)(201708071742011)(7699016); SRVR:BYAPR15MB2406; BCL:0; PCL:0; RULEID:; SRVR:BYAPR15MB2406;
x-forefront-prvs: 0682FC00E8
x-forefront-antispam-report: SFV:NSPM; SFS:(10019020)(376002)(346002)(396003)(39380400002)(366004)(39860400002)(52314003)(51444003)(189003)(199004)(13464003)(68736007)(59450400001)(5250100002)(6246003)(76176011)(7736002)(53546011)(6506007)(6436002)(14454004)(102836004)(93886005)(316002)(81156014)(5660300001)(3660700001)(99286004)(3280700002)(2906002)(81166006)(8936002)(446003)(11346002)(606006)(46003)(4326008)(476003)(2616005)(53936002)(486006)(36756003)(6116002)(82746002)(54896002)(33656002)(83716003)(86362001)(6512007)(6306002)(236005)(54906003)(2900100001)(229853002)(6486002)(186003)(110136005)(58126008)(478600001)(25786009)(106356001)(97736004)(105586002)(8676002)(781001)(42262002); DIR:OUT; SFP:1102; SCL:1; SRVR:BYAPR15MB2406; H:BYAPR15MB2312.namprd15.prod.outlook.com; FPR:; SPF:None; LANG:en; PTR:InfoNoRecords; MX:1; A:1;
received-spf: None (protection.outlook.com: fb.com does not designate permitted sender hosts)
x-microsoft-antispam-message-info: Ka2u2HjA5Guui74Qw9bG7zXndVDafAk3EoKc8zWaB0YKgezQxUjbQDhZcyqhKn+BQLtR5kTxnA/4/HPJDjvreAo5CFRE0urKDtZr3ofvDUyn4dUWIo45niO2zoKQrhe0474P73DgVQg2sX25hUu/rH4gCMRBAyu4Q3ZCOfHhSbJDS5JhbktdD+v0J+udWLQ9
spamdiagnosticoutput: 1:99
spamdiagnosticmetadata: NSPM
Content-Type: multipart/alternative; boundary="_000_B0995EA8A32949F38B470F6042D38DFCfbcom_"
MIME-Version: 1.0
X-MS-Office365-Filtering-Correlation-Id: a98934ce-5320-48af-9fc5-08d5c1a5b671
X-MS-Exchange-CrossTenant-Network-Message-Id: a98934ce-5320-48af-9fc5-08d5c1a5b671
X-MS-Exchange-CrossTenant-originalarrivaltime: 24 May 2018 18:39:41.6207 (UTC)
X-MS-Exchange-CrossTenant-fromentityheader: Hosted
X-MS-Exchange-CrossTenant-id: 8ae927fe-1255-47a7-a2af-5f3a069daaa2
X-MS-Exchange-Transport-CrossTenantHeadersStamped: BYAPR15MB2406
X-OriginatorOrg: fb.com
X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10434:, , definitions=2018-05-24_06:, , signatures=0
X-Proofpoint-Spam-Reason: safe
X-FB-Internal: Safe
Archived-At: <https://mailarchive.ietf.org/arch/msg/quic/Vq5_rd_eeSuCRT0PxNGLrIPDIO0>
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: Thu, 24 May 2018 18:40:19 -0000
To be clear, I don’t believe that sorting the table in QPACK is necessary for CPU—I agree it should be sorted by things which improve (or are neutral to) on-the-wire efficiency. CPU-related costs for lookups can be improved (as Dmitri notes) by structuring the lookups differently in the implementation. For instance, there are fun ways one can use SSE (and successors) to select amongst the headers in the static table more quickly than one might achieve with a hash-map. -=R From: Mike Bishop <mbishop@evequefou.be> Date: Thursday, May 24, 2018 at 11:21 AM To: Roberto Peon <fenix@fb.com>, Willy Tarreau <w@1wt.eu> Cc: "quic@ietf.org" <quic@ietf.org>, HTTP Working Group <ietf-http-wg@w3.org> Subject: RE: QPACK and the Static Table Yes, I think you need the lookup table for indices. Alphabetical doesn't work as well, because there are two key barriers to deal with: * Only the first sixteen entries can be name-referenced in a single byte. We degraded performance in a previous draft of this table because :path wasn’t in the first sixteen entries, and the encoder that tried the updated table used two-byte name references for every request. * Only the first sixty-four entries can be index-referenced in a single byte. This implies that you want an ordering by likelihood of using the name at all, by likelihood of not indexing the value for repeat use, and by likelihood of using the name+value pair directly. While an alphabetically-sorted list isn’t impossible within each tier, it seems easier to maintain a static map of the indices than to alphabetically index into each tier to see if the header you want is present. I’d be open to additional sources of data to run the same query against. Any browsers up to running an experiment and sharing the telemetry? -----Original Message----- From: Roberto Peon <fenix@fb.com> Sent: Thursday, May 24, 2018 10:53 AM To: Willy Tarreau <w@1wt.eu>; Mike Bishop <mbishop@evequefou.be> Cc: quic@ietf.org; HTTP Working Group <ietf-http-wg@w3.org> Subject: Re: QPACK and the Static Table One could make the lookup (more) efficient by storing the index (a byte at most) with the key-value pair, where the key-value pair were sorted via whatever sorting you'd find most efficient. If reordering allows for some increased efficiency without increasing bits-on-wire, I'd think it seems reasonable to change. I would not trust the HTTP Archive to give a frequency analysis for real-world use. Remember that we gathered the freq data for HPACK from real-world use across a hopefully not-so-biased sample via browsers directly. If the world has changed since HPACK came out in terms of header freq (seems possible if not probable), then perhaps we should consider an update to HTTP2/HPACK as well? I agree that perfection here isn't really needed, but I'm not sure adding items to the table arbitrarily makes sense either. -=R On 5/23/18, 9:42 PM, "QUIC on behalf of Willy Tarreau" <quic-bounces@ietf.org on behalf of w@1wt.eu<mailto:quic-bounces@ietf.org%20on%20behalf%20of%20w@1wt.eu>> wrote: Hi Mike, On Wed, May 23, 2018 at 11:16:18PM +0000, Mike Bishop wrote: > Rather than indexing the tables together and having the static table at 1-61, > QPACK uses a bit to indicate static vs. dynamic. Since the field is seven > bits long, the performance is comparable for the dynamic table (you can > access 63 entries in one byte, 190 in two), but you can increase the size of > the static table without hurting the dynamic table. It will make the code look less "magic"! > As a result, we're > building a fresh static > table<https://github.com/quicwg/base-drafts/pull/1355> based on queries > against HTTPArchive data. > > The key question that has come up in a couple venues: What real-world > headers do we want to artificially remove from what the data shows, and what > headers not seen by HTTP Archive do we want to force in anyway? I agree with Mark that request really is what matters the most. > * Reordered to put headers you're likely to name-reference at the front, > especially if you're unlikely to add them to the dynamic table Well, some of us have been really bothered by the lack of ordering in the HPACK headers table, making it painful to perform efficient lookups. I'd suggest that they are sorted by (name,value) to make it possible to perform efficient dichotomic lookups. > The question is whether we should also backfill headers which HTTP Archive > wouldn't see, delete headers we wish people wouldn't use, and/or insert the > ones we hope they eventually will. Some candidates: That's indeed a good point. > * Add Alt-Svc entry for HTTP/QUIC with QUIC v1 > * Add X-Forwarded-For > * Don't add X-Forwarded-For, but do add Forwarded In practice, we can take both or none. After all, most QUIC requests going through proxies will be encrypted already thus the proxy will not be able to add these fields. For clear-text requests, the header field name is roughly as long as the value, so there's not *that* much to save by encoding them. And it will not change in most consecutive requests, so the dynamic compression will be more efficient than the static one. Thus I suggest that we only add them *if* we have enough unused slots at the end that we care to cover a very broad set. > * Remove Expires to incent the use of Cache-Control Expires is for responses only anyway, thus it matters much less. Cache-control can be used in both directions. I think that the technical focus on request may make Expires disappear from the table ;-) > * Collapse the "Content-Type: <thingey>" and "Content-Type: <thingey>; charset=utf-8" entries together > * ...but which one to keep? Probably just focus on the most reported ones and not try to collapse. I suspect that we see a lot of en-us alone, and utf-8 added to some other languages, but I could be wrong. > * Add Content-Encoding and/or Accept-Encoding entries for zstd Probably too early yet, and will not make a big difference overall (almost only response, 4 characters value). > There's an endless parade of bikesheds here. As Martin has pointed out, this > will never be perfect, so the goal is "good enough and keep going." Any > strong feelings about any of these before we merge it? No real strong feeling here except about the ability to perform fast lookups. > Also, there's been some discussion of a mechanism for selecting one of > several static tables at the start of a connection. In that case, the spec > would probably define three tables (client headers, server headers [for > servers that don't push], combined [for servers that push]) and enable future > RFCs to define others for targeted scenarios (proxies, video playback, IoT, > etc.). How much does that interest folks? I think it could be a good solution. We could also think about APIs and various datacenter-oriented use cases (eg: webservice etc) where very fast response and network efficiency matters. It could be a way to encourage QUIC adoption inside the DC. The risk however is that tables defined too late are never deployed due to interoperability concerns (unless there's a way to know that it will be supported before encoding). Thus if some participants are interested in optimizing for certain use cases, they should probably provide their own tables to be merged into the standard from day 1. Cheers, Willy
- QPACK and the Static Table Mike Bishop
- Re: QPACK and the Static Table Mark Nottingham
- RE: QPACK and the Static Table Mike Bishop
- Re: QPACK and the Static Table Patrick McManus
- Re: QPACK and the Static Table Martin Thomson
- Re: QPACK and the Static Table Martin Thomson
- Re: QPACK and the Static Table Patrick McManus
- Re: QPACK and the Static Table Martin Thomson
- Re: QPACK and the Static Table Willy Tarreau
- Re: QPACK and the Static Table Mikkel Fahnøe Jørgensen
- Re: QPACK and the Static Table Roberto Peon
- Re: QPACK and the Static Table Dmitri Tikhonov
- RE: QPACK and the Static Table Mike Bishop
- Re: QPACK and the Static Table Roberto Peon
- RE: QPACK and the Static Table Lucas Pardue