What is HTTP Delta Encoding? | 6 | WebReference

What is HTTP Delta Encoding? | 6

What is HTTP Delta Encoding?

Jeffrey C. Mogul ([email protected])
Compaq Computer Corporation Western Research Laboratory
250 University Avenue, Palo Alto, CA 94301

Web caching is successful because many Web pages don't change between references. But some resources do change, which forces the re-retrieval of modified resources. However, the modifications are often minimal; if one could encode just the differences between the cached (older) page and the new page, in many cases that would require sending very few bytes. This approach is called delta encoding. Several research studies have shown that it can improve Web performance, and a standardization effort is now underway.

1. What is delta encoding?

Most Web clients and proxies have the ability to cache the responses they receive. If the user of a browser, or a client of a proxy, requests a URL that is already in the cache, then the cache can return the stored response and avoid a network transfer from the origin server. This "reuse the entire response" form of caching is simple, and effective. However, it doesn't always work, and various research studies [5, 6] have found that the upper limit on full-response caching, even for infinitely large caches, appears to be in the range of 30% to 50%. It's even lower when cache hit rates are weighted by the size of the responses.

A Web request can cause a cache miss because the resource has changed since the cache entry was created. For example, a page showing the stock price of internet.com might be different each time it is retrieved from the stock quote server. Or a page showing a weather forecast for San Francisco might change every hour or two. In either example, any change in content between requests would (or, at least, should) cause a cache miss.

However, these content changes often affect only a small fraction of the bytes in a Web response. For example, on a stock quote page, except for the actual stock price and daily volume, perhaps nothing else changes very often. So why should we have to retrieve an entire copy of the new page?

In fact, the cost of a Web cache miss could be greatly reduced, using delta encoding. In this technique, the origin server sends the difference (or delta) between the old and new instances of the resource, rather than the entire new instance. (I prefer the term "instance" to "version," since the latter often means different things to different people.) If the delta is much smaller than the entire page, this saves a lot of bandwidth.

A Web request might also cause a cache miss because the cache has never seen this URL before. Delta encoding can help here, too. In many cases, two pages with different URLs have very similar content (for example, the quote pages for two different stocks might share a lot of HTML boilerplate). A technique called delta clustering can be used to retrieve the difference between two pages from different URLs. However, this variation is more complex and less mature than basic delta encoding, so I won't cover it further in this article.

Although the idea of transmitting just the differences between successive pieces of information is an old one (for example, SCCS, RCS, and similar revision-control systems store older revisions as differences), the first use of delta encoding in the Web was developed by Housel and Lindquist at IBM [8].

2. How much will it help?

Delta encoding would only be useful if resources change relatively often, In fact, several studies have confirmed that many Web resources do change frequently. For example, Douglis et al. [4] reported on a large trace in which 16.5% of the resources changed every time they were accessed, and about 15% of the responses reflected changes in resources that had been accessed previously.

Delta encoding also makes sense only if the differences between instances are much smaller than the full content of a resource. Again, studies have shown that this happens fairly often. The potential savings vary by Content-type, because some Web content, such as images and continuous media, tends to change more radically than HTML text. The savings also depend on the efficiency of the format used to encode the differences (see 6). One trace-based study [12] showed potential overall bandwidth savings of 8.5% and latency savings of 5.6%, over and above the savings of a traditional cache. For HTML content, the study showed significantly greater improvements, reducing bandwidth requirements by 19%-24%.

Since basic delta encoding can only pay off if the resource being referenced has already been cached before (many URLs are never referenced more than once), and isn't of interest if the resource hasn't been modified (in which case traditional caching works fine), only a modest fraction of requests (about 10% of all requests, and 25% of requests for HTML files) are eligible for delta encoding. For such "delta-eligible" requests, the average savings are a lot higher: about 56% bandwidth savings overall, and 62%-65% savings for HTML files. In other words, when delta encoding can be used at all, it usually pays off quite handsomely.

3. The connection between delta encoding and caching

There is an interesting connection between delta encoding and caching. In traditional, full-reuse caching, the bits in a cache entry are either all useful (i.e., with a cache hit) or not useful at all (i.e., for a cache miss). With a successful delta encoding, however, while not all of the bits in a cache entry are useful, most of them are. In effect, delta encoding lets us extract utility out of more of the bits that are kept in a cache.

4. The connection between delta encoding and compression

While the term delta compression is sometimes used instead of delta encoding, it is somewhat misleading. Delta encoding and compression are related, but delta encoding is not really a form of compression analogous to traditional compression algorithms (such as gzip). Most traditional compression formats are self-contained; that is, you can convert between X and the compressed form of X without any other information. Delta encoding, in contrast, is not self-contained; both the sender and receiver need access to something like X but different from it.

5. Delta encoding and rsync compared

In order to create a delta-encoded representation of an instance, the server needs both that current instance and some previous instance (hopefully, one already cached at the client) in order to compute the difference. This means that a server that supports delta encoding needs to store and manage a set of older instances. Another approach, called rsync [13], avoids the need for the server to have both instances available.

In rsync, the client starts by segmenting its cache entry into a set of fixed-sized blocks, and then computes a special kind of checksum for each such block. It then sends the list of checksums to the server in its request. The server can then search the current instance for blocks that have matching checksums; it then sends an encoding of the current instance that does not include any block already held by the client. The special checksum allows the server to match blocks that appear at arbitrary offsets in the new instance, so the rsync encoding can be very compact if the change is a small insertion.

However, rsync requires sending an entire block if the value of just one byte changes. One can reduce the impact by using smaller block sizes, but then this requires the client to send a longer list of block checksums. Therefore, while rsync can be easier to implement than delta encoding, it might not be as efficient for transferring small differences.

6. Delta encoding algorithms and formats

The key to success with delta encoding is to generate a very compact representation of the difference between two similar files. A naive approach would be to use a simple text-based format such as the output of the UNIX "diff -e" command, but this doesn't work for non-text inputs, and works relatively poorly for text files. Compressing the output can help a little, but because "diff" outputs the entire line that has changed, it cannot produce compact results for single-byte changes.

Several formats have been developed specifically for representing deltas, for any content type. The best known algorithm (in terms of output compactness, not necessarily coding or decoding speed) is vcdiff [9, 10].

7. Standardization efforts

Delta encoding will be most useful when it is widely supported by Web servers, proxies, and clients. This depends on the adoption of a standard for the extension of HTTP to support delta encoding. Over the past several years, a group of people have been developing such a standard. While this is not an official IETF working group, we have been following the IETF standards process and hope to eventually create a formal IETF standard.

The current specification for basic delta encoding [11] has been submitted as a "Proposed Standard," but it has not yet (as of this writing) been accepted. This would only be the first of several steps on the IETF standardization process [2], and the design could change again.

There is also a document describing the vcdiff encoding format [10], but it, too, is not yet finished.

We have some hope that the framework that we have developed for delta encoding in HTTP can be further extended, both to support delta clustering (see section 1) and perhaps to support rsync (section 5).

8. An example HTTP exchange

The proposed specification for HTTP delta encoding introduces a new concept called an "instance manipulation." A delta encoding format is one example of an instance manipulation. We discovered that we needed this new concept after trying to define delta encoding as a form of HTTP Content-encoding; that approach turned out to create insurmountable bugs, although it took us a long time to figure that out.

In our design, a client that supports delta encoding sends its request using the standard HTTP/1.1 "If-None-Match" header to list the entity tags of its cache entry (or entries) for the requested URL. (If you're not familiar with entity tags, please refer to the HTTP/1.1 specification [7].) It also sends an "A-IM" header listing the instance manipulation(s) that it can accept, including one or more delta encoding formats. So, for example, a request might look like

GET /foo.html HTTP/1.1
Host: bar.example.net
If-None-Match: "123xyz"
A-IM: vcdiff

Suppose that the entity tag for the current instance of this URL (https://bar.example.net/foo.html) is "489uhw". The origin server (which is never required to use a delta encoding!) could then locate its stored copy of the "123xyz" instance of the resource (which must be in the client's cache, or it would not have been listed in the If-None-Match header) and could compute the delta, using the vcdiff format.

If the result of this encoding is smaller than the current instance, the server would reply:

HTTP/1.1 226 IM Used
ETag: "489uhw"
IM: vcdiff
Date: Tue, 25 Nov 1997 18:30:05 GMT
<body containing delta encoding result, which
     is a binary format>
The only differences between this response and a normal one are the new 226 status code, which tells the client that some instance manipulation has been applied (and which precludes inappropriate caching by proxies that do not understand this extension!), and the "IM" header, which tells the client which instance manipulation has been applied. (Note that the 226 status code value has not yet been formally allocated for this purpose.)

There are many other details to consider, which are discussed in the proposed specification.

9. Delta encoding and proxies

Throughout most of this article, I have avoided referring to "browsers" or "proxies," since delta encoding can be used by any HTTP client with a cache. (The term "client" refers to anything that can receive an HTTP response, and so includes "proxies.")

There are situations where the difference between a proxy cache and the ultimate end-client can affect the use of delta encoding. For example, even if the end-client does not support delta encoding, if it sends its requests through a proxy, the proxy could request delta encoding and then decode the response before forwarding it to the client. (In fact, several research projects into delta encoding [1, 3] used proxy-based implementations to avoid having to modify browser code.)

Trace-based research suggests that a caching proxy server, if shared by multiple users, can obtain more benefit from delta encoding than if only the individual browsers used delta encoding. This is because the proxy, which sees many more requests, is more likely to have cached a previous response for a given URL. Since delta encoding (in its basic form) only works when the cache already contains an entry for the requested URL, a multi-user proxy cache is more likely to be able to request a delta.

10. Implementations and deployment status

If you are thinking about deploying an implementation based on the current proposed specification, don't. This would be a very bad idea.

The existing specification is definitely subject to change, and premature deployment could result in a standards mess.

However, it would be useful to have some experimental implementations of delta encoding, in order to verify that the proposed specification actually works. I know of no such implementations, except for one that conforms only to a much older, different version of the spec. Several research projects have produced code that does delta encoding, but they were not based on this specification.

Once the design progresses through "Proposed Standard" status to "Draft Standard" status, the design is less likely to change, and at that point we will be actively seeking the selective deployment of implementations for wide-scale testing. That won't happen very soon, though. The IETF process requires at least 6 months between a Proposed Standard and the subsequent Draft Standard.

We hope that people will start working on test-only implementations as soon as the Proposed Standard is available, because the IETF requires evidence of interoperability between independently-developed implementations before it will accept a Draft Standard.

References

[1] Gaurav Banga, Fred Douglis, and Michael Rabinovich. Optimistic Deltas for WWW Latency Reduction. In Proc. 1997 USENIX Technical Conference, pp. 289-303. Anaheim, CA, January, 1997. https://www.usenix.org/publications/library/proceedings/ana97/banga.html.

[2] S. Bradner. The Internet Standards Process -- Revision 3. RFC 2026, IETF, October, 1996. https://www.ietf.org/rfc/rfc2026.txt.

[3] Matthew Delco and Mihut Ionescu. xProxy: A Transparent Caching and Delta Transfer System for Web Objects. 2000. https://www.cs.berkeley.edu/~mihut/cs268/xproxy.ps.gz.

[4] Fred Douglis, Anja Feldmann, Balachander Krishnamurthy, and Jeffrey Mogul. Rate of Change and Other Metrics: a Live Study of the World Wide Web. In Proc. Symposium on Internet Technologies and Systems, pp. 147-158. USENIX, Monterey, CA, December, 1997. www.usenix.org/publications/library/proceedings/usits97/douglis_rate.html.

[5] Bradley M. Duska, David Marwood, and Michael J. Feeley. The Measured Access Characteristics of World-Wide-Web Proxy Caches. In Proc. Symposium on Internet Technologies and Systems, pp. 23-35. USENIX, Monterey, CA, December, 1997. https://www.usenix.org/publications/library/proceedings/usits97/duska.html.

[6] Li Fan, Pei Cao, Jussara Almeida and Andrei Broder. Summary Cache: A Scalable Wide-Area Web Cache Sharing Protocol. In Proc. SIGCOMM '98, pp. 254-265. Vancouver, September, 1998. https://www.acm.org/sigcomm/sigcomm98/tp/abs_21.html.

[7] Roy T. Fielding, Jim Gettys, Jeffrey C. Mogul, Henrik Frystyk Nielsen, and Tim Berners-Lee. Hypertext Transfer Protocol -- HTTP/1.1. RFC 2068, HTTP Working Group, January, 1997. https://www.ietf.org/rfc/rfc2068.txt.

[8] Barron C. Housel and David B. Lindquist. WebExpress: A System for Optimizing Web Browsing in a Wireless Environment. In Proc. 2nd Annual Intl. Conf. on Mobile Computing and Networking, pp. 108-116. ACM, Rye, New York, November, 1996.

[9] David G. Korn and Kiem-Phong Vo. A Generic Differencing and Compression Data Format. Technical Report HA1630000-021899-02TM, AT&T Labs - Research, February, 1999.

[10] David G. Korn and Kiem-Phong Vo. The VCDIFF Generic Differencing and Compression Data Format. Internet-Draft draft-korn-vcdiff-02 (this is a work in progress), IETF, November, 2000. https://www.ietf.org/internet-drafts/draft-korn-vcdiff-02.txt.

[11] Jeffrey C. Mogul, Balachander Krishnamurthy, Fred Douglis, Anja Feldmann, Yaron Goland, and Arthur van Hoff. Delta encoding in HTTP. Internet-Draft draft-mogul-http-delta-07 (this is a work in progress), IETF, October, 2000. https://www.ietf.org/internet-drafts/draft-mogul-http-delta-07.txt.

[12] Jeffrey C. Mogul, Fred Douglis, Anja Feldmann, and Balachander Krishnamurthy. Potential benefits of delta encoding and data compression for HTTP. In Proc. SIGCOMM '97, pp. 181-194. Cannes, France, September, 1997. https://www.acm.org/sigcomm/sigcomm97/program.html#ab156.

[13] Andrew Tridgell and Paul Mackerras. The rsync algorithm. Technical Report TR-CS-96-05, Dept. of Computer Science, Australian National University, June, 1996. https://cs.anu.edu.au/techreports/1996/TR-CS-96-05.html.

Biography

Jeffrey C. Mogul received an S.B. from the Massachusetts Institute of Technology in 1979, an M.S. from Stanford University in 1980, and his PhD from the Stanford University Computer Science Department in 1986. Jeff has been an active participant in the Internet community, and is the author or co-author of several Internet Standards. He is a co-author of the HTTP/1.1 specification. Since 1986, he has been a researcher at the Compaq (formerly Digital) Western Research Laboratory, working on network and operating systems issues for high-performance computer systems, and on improving performance of the Internet and the World Wide Web. He is a member of ACM, Sigma Xi, and CPSR, and was Program Committee Chair for the Winter 1994 USENIX Technical Conference, and for the IEEE TCOS Sixth Workshop on Hot Topics in Operating Systems.