BYTE RANGE CACHING

• US 20100318632A1
• Filed: 06/16/2009
• Published: 12/16/2010
• Est. Priority Date: 06/16/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Patel, Himanshu, Ruia, Anil K., Pattekar, Chittaranjan, Lin, Ning, Yoo, Won Suk
• Granted Patent: US 9,807,468 B2
• Time in Patent Office: Days
• US Class Current: 709/219
• CPC Class Codes: H04L 65/65 Network streaming protocols, e.g. real-time transport protocol [RTP] or real-time control protocol [RTCP]
• CPC Class Codes: H04L 65/765 intermediate
• CPC Class Codes: H04L 65/80 Responding to QoS
• CPC Class Codes: H04L 67/564 Enhancement of application control based on intercepted application data
• CPC Class Codes: H04L 67/568 Storing data temporarily at an intermediate stage, e.g. caching
• CPC Class Codes: H04L 67/5682 Policies or rules for updating, deleting or replacing the stored data
• CPC Class Codes: H04N 21/23106 involving caching operations prefetching while addressing of a memory level in which the access to the desired data or data block requires associative addressing means within memory systems or architectures G06F12/0862; caching at an intermediate stage in a data network H04L67/568
• CPC Class Codes: H04N 21/6125 involving transmission via Internet transmission by internet of broadcast information H04H60/82
• CPC Class Codes: H04N 21/64322 IP

Abstract

A caching system segments content into multiple, individually cacheable chunks cached by a cache server that caches partial content and serves byte range requests with low latency and fewer duplicate requests to an origin server. The system receives a request from a client for a byte range of a content resource. The system determines the chunks overlapped by the specified byte range and sends a byte range request to the origin server for the overlapped chunks not already stored in a cache. The system stores the bytes of received responses as chunks in the cache and responds to the received request using the chunks stored in the cache. The system serves subsequent requests that overlap with previously requested ranges of bytes from the already retrieved chunks in the cache and makes requests to the origin server only for those chunks that a client has not previously requested.

Claims

1. A computer-implemented method for responding to client requests for portions of a content resource, the method comprising:

receiving a request for a range of bytes that represents a portion of a content resource stored on a server;

identifying one or more chunks that the requested range of bytes overlaps based on a configurable chunk size into which the caching system divides the content resource;

determining whether each overlapped chunk is currently stored in a cache;

upon determining that at least one overlapped chunk is not currently stored in the cache,

sending a byte range request to an origin server to download the overlapped chunks that are not stored in the cache;

receiving a response from the origin server that contains a byte range that includes the requested overlapped chunks; and

storing the received byte range in corresponding chunks in the cache; and

sending a response to the received request that includes the specified range of bytes retrieved from the cache,

wherein the preceding steps are performed by at least one processor.

2. The method of claim 1 wherein identifying one or more chunks comprises inspecting a starting offset and a size of the byte range request to determine the chunks into which the beginning and end of the byte range fall.

3. The method of claim 1 wherein determining whether each overlapped chunk is currently stored in the cache comprises using a data structure that indexes the chunks to determine whether each overlapped chunk is available in the cache.

4. The method of claim 1 wherein sending the byte range request to the origin server comprises rewriting a buffer of the received request to expand the range to chunk-sized boundaries.

5. The method of claim 1 wherein sending the byte range request to the origin server comprises sending a request for bytes in chunks in addition to those overlapped by the received request.

6. The method of claim 1 wherein the request to the origin server appears to the origin server like a client request but specifies a range of bytes sufficient for the response to fill whole chunks in the cache.

7. The method of claim 1 wherein storing the received byte range in corresponding chunks in the cache comprises updating an index of chunks available in the cache.

8. The method of claim 1 wherein subsequent requests for the same range of bytes or for ranges of bytes that overlap the requested range of bytes can be served from the cache.

9. The method of claim 1 further comprising, in response to determining that a request includes some bytes that are stored in the cache and some bytes that are not yet cached, sending an additional request to the origin server to download the bytes that are not yet cached.

10. The method of claim 1 wherein the received request includes multiple non-contiguous ranges of bytes and the response provides the specified multiple ranges of bytes.

11. A computer system for caching chunks of a content resource to respond to client requests for portions of the resource, the system comprising:

a processor and memory configured to execute software instructions;

a request receiving component configured to receive requests from clients to download a portion of the content resource;

a cache store configured to store cache chunks received from an origin server in response to a chunk request;

a chunk mapping component configured to map received client requests into resource chunks stored by the cache store;

an origin communication component configured to send requests to the origin server for chunks requested by clients that are not stored in the cache store;

a chunk caching component configured to store chunk request responses from the origin server in the cache store; and

a response mapping component configured to map the chunks available in the cache store to the byte range specified by a received client request.

12. The system of claim 11 wherein the request receiving component is further configured to receive Hypertext Transfer Protocol (HTTP) byte range requests that specify a portion of a file stored on a web server.

13. The system of claim 11 wherein the request receiving component operates on a cache server that sits between clients that send requests and origin servers that serve content.

14. The system of claim 11 wherein the chunk mapping component is further configured to create a data structure for each request that stores an original requested range, zero or more chunks that overlap the requested range that are available in the cache, and one or more chunks not in the cache that will be requested from the origin server.

15. The system of claim 11 wherein the cache store is further configured to use a naming scheme or metadata fields to describe a content resource to which each stored chunk is related.

16. The system of claim 11 wherein the origin communication component is further configured to create requests based on a configured chunk size such that a range of bytes in the created request overlaps bytes requested by a client.

17. The system of claim 11 wherein the chunk caching component is further configured to operate in parallel with other components of the system so that the system can provide a reply to a client before or while storing the chunk response from the origin server.

18. The system of claim 11 further comprising an administrative interface component configured to provide an interface through which an administrator can monitor and configure the system.

19. The system of claim 11 wherein the components are implemented as an extension of an existing web server within one or more custom built extension modules.

20. A computer-readable storage medium comprising instructions for controlling a computer system to configure a cache that caches chunks of a content resource, wherein the instructions, when executed, cause a processor to perform actions comprising:

receiving a request to set a chunk size that specifies an upper boundary on the size of a chunk of the content resource;

determining a previously set chunk size;

determining whether the request specifies purging an existing cache of chunks;

upon determining that the request specifies purging an existing cache of chunks, deleting the existing cache of chunks; and

upon determining that the request does not specify deleting an existing cache of chunks, converting the existing cache of chunks to chunks of the requested chunk size.