Page History

Introduction

Partial object caching, or more accurately range caching, is the ability of Traffic Server to cache range responses. This has two parts

1. Cache the data from a 206 (range) response.
2. Serve, if possible, a range request from cached range responses.

Issues

The primary problem for range caching is tracking the ranges for the overall object. There are many well known data structures for storing such range information but it is considered critical for the Traffic Server cache that the memory footprint of the data be bounded.

It is also desirable to limit fragmentation of the stored data. If an object is scattered in a large number of small disk segments then performance will be suboptimal.

Performance requirements also mean that it should take a small fixed number (preferably 1) of disk reads to determine if a request can be satisfied with the current object range data.

Implementations

Two basic implementations have been discussed, both of them designed with the idea of bounding the range tracking data at the possible expense of discarding data. Both of them are monotonically increasing in that the amount of data stored for an object never decreases, even if not every byte that passes through ATS is cached.

Plan A is to use torrent style storage. Each segment of an object is divided in to chunks (fixed number of chunks per segment). Range data is stored in chunk units and only complete chunks. Data in partial chunks is not stored. A bitmap is kept along with the segment offset data indicating which chunks have data. This can then be easily checked against an incoming request to see if it can be served.

Plan B is to use a span per segment. Each segment stores a low and high water mark of valid data. If an incoming request overlaps or is adjacent to this span, it is added and the span marks adjusted. If there is no overlap, the larger of the existing span or the incoming data is kept and the other discarded.

For both plans, the extra data is a 64bit word per segment.

Which is better depends on how the range requests are expected to be distributed. If they are roughly random, plan A is probably better. If they are (roughly) sequential plan B would do better. It is possible, if unlikely, for plan A to fail to store any data for a full sequence of range requests for the object if every request spans two chunks but covers neither of them.

Radical Idea

Presuming the range information would be stored in the root segment, memory bounding may not be necessary. This data is rewritten frequently in normal operation, such as for a refresh or the addition of an alternate. If we are willing to do a rewrite for a range request then we can have much weaker space bounds on the memory consumed by the range tracking. This would require a read from disk on a cache hit but that is commonly done now. The key difference would be treating a cache "miss" differently, although the mechanism used for an alternate miss may work as well.

Plugin Implementation

An alternative to modifying the cache is to implement a partial object caching plugin on top of the existing cache. The fundamental idea here is that the plugin fetches fixed-size "chunks" from the origin and uses those to compose the range requested by the client. For each client request, the plugin

• determines the set of chunks that overlap the range
• issues a new set of origin requests (in parallel) to fetch the corresponding chunks
• rewrites the cache key for each chunk so they are all stored independently
• creates a transformed client response by composing the correct byte ranges from the chunks

This would be a fairly complex plugin, but it has the advantage of not changing the cache format and minimizes the risk of breaking other features.