System and method for managing storage space of a cache

• US 20020174302A1
• Filed: 05/15/2001
• Published: 11/21/2002
• Est. Priority Date: 05/15/2001
• Status: Active Grant

• Current Assignee: Zhigu Holdings Limited
• Original Assignee: Microsoft Corporation
• Inventors: Frank, Alexander
• Granted Patent: US 6,654,856 B2
• Time in Patent Office: Days
• US Class Current: 711/130
• CPC Class Codes: G06F 12/023 Free address space management
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache
• CPC Class Codes: G06F 12/123 with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list
• CPC Class Codes: G06F 12/127 using additional replacement algorithms

Abstract

A system and method for managing a cache space employs a space allocation and recycling scheme that has very low complexity for each data caching transaction regardless of the size of the data set, is virtually fragmentation free, and does not depend on garbage collection. The cache space is treated as a linear space with its two ends connected in the manner of a cyclic queue. The reclaiming and allocation of cache space for writing new objects proceeds as an “allocation wave” that sweeps in a pre-selected direction over the “circular” cache space. As the allocation wave moves along the circular space, the space used by existing objects are reclaimed for writing new objects except for those existing objects that for some reason are not to be written over. Those existing objects to be passed over by the allocation wave are viewed as “interruptions” to the generally first-in-first-out (FIFO) allocation scheme for writing new objects into the circular cache space.

Claims

1. A computer-readable medium having computer-executable instructions for performing steps for managing usage of storage space of a cache, comprising:

connecting two ends of the storage space of the cache for read and write operations;

setting an allocation pointer indicating a point in the cache up to which storage space has been reclaimed and allocated for writing new data objects into the cache;

receiving a new data object to be written into the cache;

reclaiming storage space occupied by one or more existing cached objects located adjacent and downstream from the allocation pointer until sufficient storage space is reclaimed for writing the new object, the reclaiming including determining whether said one or more existing cached objects are not to be overwritten and passing over any of the one or more existing cached objects if said any of the one or more existing cached objects is not to be overwritten;

allocating the reclaimed space to the new object; and

updating the allocation pointer to indicate a new point in the cache up to which storage space is reclaimed and allocated for writing the new data object.

2. A computer-readable medium as claim 1, wherein the storage space of the cache resides on a mass storage device of a computer.

3. A computer-readable medium as in claim 2, having further computer-executable instructions for performing the steps of:

storing the new data object in a buffer in a main memory of the computer; and

copying the new data object from the buffer into the storage space of the cache on the mass storage area.

4. A computer-readable medium as in claim 1, wherein the storage space of the cache resides in a main memory of a computer.

5. A computer-readable medium as in claim 1, wherein the new data object is a data object downloaded from the Internet.

6. A computer-readable medium as in claim 1, wherein the step of determining determines that said any of the one or more existing cached objects is not to be overwritten when said any of the one or more existing cached objects is recently or frequently accessed.

7. A computer-readable medium as in claim 1, wherein the storage space of the cache is divided into blocks, and wherein the computer-readable medium has further computer-executable instructions for performing the steps of maintaining a plurality of descriptors each corresponding to a block in the cache, and updating the descriptors in connection with the steps of reclaiming and allocating.

8. A computer-readable medium as in claim 7, wherein the blocks in the cache are of variable sizes.

9. A computer-readable medium as in claim 8, wherein the step of reclaiming includes splitting an existing block into a first portion for writing the new data object and a second portion forming a free block.

10. A computer-readable medium having a computer-readable data structure comprising:

a plurality of descriptors containing data describing blocks in a storage space of a cache for storing data objects, each descriptor corresponding to a block in the storage space, the descriptors being linked to form a linked list in accordance with orders of their respective blocks in the storage space, a first descriptor and a last descriptor being linked so that the linked list forms a loop;

an allocation pointer field containing data representing a point in the storage space of the cache up to which storage space has been reclaimed and allocated for writing new objects, the allocation pointer field being updated such that said point is moved in a pre-selected direction in the storage space over consecutive blocks containing existing cached objects from which storage space is reclaimed and allocated for writing the new objects.

11. A computer-readable medium as in claim 10, wherein the storage space of the cache is on a mass storage device.

12. A computer-readable medium as in claim 10, wherein the blocks are of variable sizes.

13. A computer-readable medium as in claim 12, wherein the each descriptor contains data representing a size of the corresponding block.

14. A computer-readable medium as in claim 10, wherein each descriptor contains data indicating whether the corresponding block is not to be reclaimed for writing new data objects.

15. A computer-readable medium as in claim 10, wherein the data objects stored in the cache includes multi-block data objects each occupying multiple blocks, and wherein each descriptor corresponding to a block of a multi-block data object includes data indicating a position of the said corresponding block in the multi-block data object.

17. A computer-readable medium as in claim 16, wherein the first cache space resides in a main memory of a computer, and the second cache space resides in a mass storage device of the computer.

18. A computer-readable medium as in claim 17, wherein the new data object is a data object downloaded from the Internet.

19. A computer-readable medium in claim 18, having further computer-executable instructions for maintaining a plurality of descriptors each containing data describing a corresponding block in the second cache space, the descriptors are linked to form a linked list in accordance with orders of their respective blocks in the second cache space.

20. A computer-readable medium as in claim 19, having further computer-executable instructions for maintaining a second plurality of descriptors each containing data describing a corresponding block in the first cache space, the second plurality of descriptors are linked to form a linked list in accordance with orders of their respective blocks in the first cache space.

16. A computer-readable medium having computer-executable instructions for performing steps to manage a cache system, comprising:

(1) providing a first cache space and a second cache space;

(2) writing new objects to be buffered into the first cache space, including;

(a) setting a first allocation pointer indicating a point in the first cache space up to which storage space has been reclaimed and allocated for buffering new objects in the first cache space;

(b) receiving a new object to be buffered in the first cache space;

(c) reclaiming storage space occupied by one or more existing buffered objects located adjacent and downstream from the first allocation pointer until sufficient storage space is reclaimed for writing the new object, the reclaiming including determining whether the one or more existing cached objects are not to be overwritten and passing over any of the one or more existing buffered objects if said any of the one or more existing buffered objects is not to be overwritten;

(d) allocating the reclaimed space for buffering the new object;

(e) updating the first allocation pointer to indicate a new point in the first cache up to which the reclaimed space is allocated for buffering the new object, and

(3) copying buffered objects from the first cache space into the second cache space, including;

(a) setting a copy pointer indicating a point in the first cache space up to which buffered objects are being copied to the second cache space;

(b) setting a second allocation pointer indicating a point in the second cache space up to which storage space has been reclaimed and allocated for copying buffered data objects from the first cache space;

(c) determining whether a target buffered object in the first cache space adjacent and downstream of the copy pointer is to be copied to the second cache space;

(d) if the target buffered object is to be copied,

(i) reclaiming storage space occupied by one or more existing cached objects in the second cache space located adjacent and downstream from the second allocation pointer until sufficient storage space is reclaimed for copying the target buffered object, the reclaiming including determining whether the one or more existing cached objects are not to be overwritten and passing over any of the one or more existing cached objects if said any of the one or more existing cached objects is not to be overwritten;

(ii) allocating the reclaimed storage space for copying the target buffered object;

(iii) updating the second allocation pointer to indicate a new point in the second cache space up to which the reclaimed storage space is allocated for copying the target buffered object; and

(iv) updating the copy pointer by moving copy pointer over the target buffered object.

21. A computer-readable medium having computer-executable instructions for performing steps to manage a cache system, comprising:

buffering new objects in a first cache space, including, for each new object, moving a first allocation pointer in a first pre-selected direction over at least one existing buffered object in the first cache space and reclaiming storage space from the at least one existing buffered object if the at least one existing buffered object is allowed to be overwritten; and

copying buffered objects from the first cache space into a second cache space, including;

moving a copy pointer in said first pre-selected direction over a target buffered object;

determining whether the target buffered object is to be copied into the second cache,

if the target buffered object is to be copied, moving a second allocation pointer in a second preselected direction over at least one existing cached object in the second cache space and reclaiming storage space from the at least one existing cached object if the at least one existing cached object is allowed to be overwritten; and

copying the target buffered object into the storage space reclaimed from the at least one existing cached object.

22. A computer-readable medium as in claim 21, wherein the first cache space resides in a main memory of a computer and the second cache space resides on a mass storage device of the computer.

23. A computer-readable medium as in claim 22, wherein the new data objects are data objects downloaded from the Internet.