Apparatus and methods for caching objects using main memory and persistent memory

• US 7,269,608 B2
• Filed: 05/03/2002
• Issued: 09/11/2007
• Est. Priority Date: 05/30/2001
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Wong, Thomas K., Chawla, Rajeev, Tsirigotis, Panagiotis, Radia, Sanjay R., Ahmadian, Omid
• Primary Examiner(s): Corrielus; Jean M.
• Application Number:
  US10/137,443
• Publication Number:
  US 20040111443A1
• Time in Patent Office: 1,957 Days
• Field of Search: 707/3, 707/4, 707100-1041, 707/202, 707/1, 707/10, 707/200, 711/202, 711/209, 711/203, 711/110, 711/216, 711/113, 711/117
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1435 using file system or storage system metadata
• 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: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users

Abstract

An object cache stores objects in a cyclic buffer to provide highly efficient creation of cache entries. The cache efficiently manages storage of a large number of small objects because the cache does not write objects into a file system as individual files, rather the cache utilizes cyclical buffers in which to store objects as they are added to the cache. Because of the use of a cyclic buffer, the high-overhead process of purging cache entries never needs to be performed. Cache entries are automatically purged as they are overwritten when the cyclic buffer becomes full and the input pointer wraps around from the end of a cyclic buffer to the beginning of a cyclic buffer. Additionally, in the event of a system crash or disk subsystem malfunction, inspect and repair time is independent of the size of the cache, as opposed to conventional file systems in which the time is proportional to the size of the file system.

Claims

1. A method of caching an object in a computer system having:

persistent memory comprising multiple disks;

main memory containing a set of buffers associated with each of the multiple disks, each set of buffers comprising;

a cyclic object buffer configured to store and retrieve objects by logical block number;

a cyclic index buffer configured to store index entries corresponding to objects stored in the cyclic object buffer;

a metadata buffer configured to store information facilitating access to the cyclic object buffer and the cyclic index buffer;

wherein one of the multiple disks is a current disk and the set of buffers associated with the current disk is a current set of buffers;

the method comprising;

receiving an object from an origin server;

writing the object to the current cyclic object buffer if the current cyclic object buffer is not full;

if the current cyclic object buffer is full;

adopting a longest waiting disk as a new current disk;

adopting the set of buffers associated with the new current disk as a new current set of buffers;

storing the object in the new current cyclic object buffer;

writing an index entry regarding the object to the new current cyclic index buffer; and

updating the new current metadata buffer.

2. The method as in claim 1, wherein the object is a web object.

3. The method as in claim 1, wherein said writing an index entry comprises:

within a first index cell within the new current cyclic index buffer, writing a new index block comprising;

a time stamp capable of storing a time associated with the index entry; and

a cell number capable of identifying the first index cell.

4. The method as in claim 1, wherein said writing an index entry comprises writing the index entry to an index block within a first index cell of the cyclic index buffer, the index entry comprising:

an object identifier capable of identifying the object;

a hash value corresponding to the object identifier;

a cell number corresponding to a storage location of the object; and

a cell size.

5. The method as in claim 4, wherein the object is a web object and the object identifier is a uniform resource locator.

6. The method as in claim 1, wherein the cyclic object buffer comprises:

cells comprising at least one data block.

7. The method as in claim 1, wherein each metadata buffer is configured to store:

a timestamp capable of storing a time associated with information stored in the metadata buffer;

a start of index indicator capable on indicating a location of a beginning of the corresponding cyclic index buffer;

an index size capable of specifying a size of the corresponding cyclic index buffer;

an index pointer capable of pointing to a current position within the corresponding cyclic index buffer;

a start of data pointer capable of indicating a location of the beginning of data within the corresponding cyclic object buffer;

a data memory size capable of specifying a size of the corresponding cyclic object buffer; and

a data pointer capable of pointing to a current position within the corresponding cyclic object buffer.

8. In a computer system having main memory and persistent memory, the main memory containing at least one data buffer, the method comprising steps of:

receiving a request for an object, the request comprising an identifier of the object; and

accessing a hash index table containing an index of information stored in the main memory and the persistent memory to determine, from the identifier, whether a cached copy of the object is stored in a plurality of data structures, the data structures comprising;

a cyclic index memory capable of storing index entries comprising an index, the index having a beginning;

a cyclic object memory capable of storing and retrieving objects by logical block number, the object memory having a beginning; and

a metadata memory capable of storing information about the index memory and the object memory, the information including;

a timestamp capable of storing a time associated with information stored in the metadata memory;

a start of index indicator capable on indicating a location of the beginning of the index within the index memory;

an index memory size capable of specifying a size of the index memory;

an index pointer capable of pointing to a current position within the index memory;

a start of data pointer capable of indicating a location of the beginning of the data within the object memory;

a data memory size capable of specifying a size of the object memory;

a data pointer capable of pointing to a current position within the object memory, wherein determining whether a cached copy of the object is stored in a plurality of data structures further comprises the steps of;

computing a hash value of the identifier; and

accessing the hash index table using the hash value.

9. The system as in claim 8, wherein the object is a web object.

10. The system as in claim 8, wherein the identifier is a uniform resource locator.

11. The system as in claim 8, further comprising:

detecting a crash of the computer system;

determining whether the start of index pointer points to a valid index block;

if the start of index pointer does not point to a valid index block, scanning the index until a valid index block is found or the index is determined to be empty; and

if the start of index pointer does point to a valid index block, scanning the index until an invalid index block is found.

12. An apparatus comprising:

an execution unit capable of executing program code;

persistent memory comprising multiple disks and;

main memory containing a plurality of data structures associated with each of the multiple disks, including;

a cyclic index memory capable of storing index entries comprising an index, the index having a beginning;

a cyclic object memory capable of storing and retrieving objects by logical block number, the object memory having a beginning;

a metadata memory capable of storing information about the index memory and the object memory;

a receiver for receiving a first object from an origin server;

determining whether current data structures are full, wherein the current data structures are associated with a current disk among the multiple disks; and

adopting a longest waiting disk as a new current disk if the current data structures are full; and

an object writer for;

storing the first object in the current data structures if the current data structures are not full; and

storing the first object in new current data structures associated with the new current disk if the current data structures are full.

13. The apparatus according to claim 12, wherein the object is a web object.

14. The apparatus according to claim 12, wherein the object writer comprises:

an index block writer configured to store index blocks, the index blocks comprising;

a time stamp capable of storing a time associated with an index entry; and

a cell number capable of identifying a cell within the cyclic index memory.

15. The apparatus according to claim 14, wherein the index block writer comprises an index element writer configured to write index elements, the index elements including:

an object identifier capable of identifying an object;

a hash value corresponding to the object identifier;

a cell number corresponding to a storage location of the identified object; and

a cell size corresponding to the size of the cell within the index memory.

16. The apparatus according to claim 15, wherein the object is a web object is a web object and the identifier is a uniform resource locator.

17. The apparatus according to claim 12, wherein the cyclic object memory comprises:

cells comprising at least one data block.

18. The apparatus according to claim 12, wherein the metadata memory comprises:

a timestamp capable of storing a time associated with information stored in the metadata memory;

a start of index indicator capable of indicating a location of the beginning of the index within the index memory;

an index memory size capable of specifying a size of the index memory;

an index pointer capable of pointing to a current position within the index memory;

a start of data pointer capable of indicating a location of the beginning of the data within the object memory;

a data memory size capable of specifying a size of the object memory; and

a data pointer capable of pointing to a current position within the object memory.

19. A computer system comprising:

an execution unit capable of executing program code;

persistent memory; and

main memory containing a plurality of data structures, including;

a cyclic index memory capable of storing index entries comprising an index, the index having a beginning;

a cyclic object memory capable of storing and retrieving objects by logical block number, the object memory having a beginning; and

a metadata memory capable of storing information about the index memory and the object memory, the information including;

a timestamp capable of storing a time associated with information stored in the metadata memory;

a start of index indicator capable on indicating a location of the beginning of the index within the index memory;

an index memory size capable of specifying a size of the index memory;

an index pointer capable of pointing to a current position within the index memory;

a start of data pointer capable of indicating a location of the beginning of the data within the object memory;

a data memory size capable of specifying a size of the object memory;

a data pointer capable of pointing to a current position within the object memory;

a receiver for receiving a request for an object, the request comprising an identifier Of the object;

program code for accessing a hash index table containing an index of information stored in the main memory and the persistent memory to determine, from the identifier, whether a cached copy of the object is stored in the plurality of data structures, wherein determining whether a cached copy of the object is stored in a plurality of data structures further comprises the steps of;

computing a hash value of the identifier; and

accessing the hash index a—

hash table using the hash value.

20. The computer system according to claim 19, further comprising:

detecting a crash of the computer system;

determining whether the start of index pointer points to a valid index block; and

scanning the index until a valid index block is found or the index is determined to be empty, if the start of index pointer does not point to a valid index block;

or

scanning the index until an invalid index block is found, if the start of index pointer does point to a valid index block.

21. A computer readable storage medium causing a computer system to perform a method, the computer system having persistent memory comprising multiple disks;

and

main memory containing a set of buffers associated with each of the multiple disks, each set of buffers comprising;

a cyclic object buffer configured to store and retrieve objects by logical block number;

a cyclic index buffer configured to store index entries corresponding to objects stored in the cyclic object buffer; and

a metadata buffer configured to store information facilitating access to the cyclic object buffer and the cyclic index buffer;

wherein one of the multiple disks is a current disk and the set of buffers associated with the current disk is a current set of buffers, and the method comprising;

receiving an object from an origin server;

writing the object to the current cyclic object buffer if the current cyclic object buffer is not full;

if the current cyclic object buffer is full;

adopting a longest waiting disk as a new current disk;

adopting the set of buffers associated with the new current disk as a new current set of buffers;

storing the object in the new current cyclic object buffer;

writing an index entry regarding the object to the new current cyclic index buffer; and

updating the new current metadata buffer.

22. The computer readable storage medium as in claim 21, wherein the object is a web object.

23. The computer readable storage medium as in claim 21, wherein said writing an index entry comprises:

within a first index cell within the new current cyclic index buffer, writing a new index block comprising;

a time stamp capable of storing a time associated with an index entry; and

a cell number capable of identifying the first index cell within the cyclic index memory.

24. The computer readable storage medium as in claim 21, wherein said writing an index entry comprises writing the index entry to an index block within a first index cell of the cyclic index buffer, the index entry comprising:

an object identifier capable of identifying the object;

a hash value corresponding to the object identifier;

a cell number corresponding to a storage location of the object; and

a cell size.

25. A computer readable storage medium as in claim 21, wherein the cyclic object memory further comprises:

cells comprising at least one data block.

26. The computer readable storage medium as in claim 21, wherein the metadata memory comprises:

a timestamp capable of storing a time associated with information stored in the metadata memory;

a start of index indicator capable of indicating a location of the beginning of the index within the index memory;

an index memory size capable of specifying a size of the index memory;

an index pointer capable of pointing to a current position within the index memory;

a start of data pointer capable of indicating a location of the beginning of the data within the object memory;

a data memory size capable of specifying a size of the object memory; and

a data pointer capable of pointing to a current position within the object memory.

27. A computer-readable storage medium capable of causing a computer system to perform a method, the computer system having main memory and persistent memory, the main memory containing at least one data buffer, and the method comprising the steps of:

receiving a request for an object, the request comprising an identifier of the object; and

accessing a hash index table containing an index of information stored in the main memory and the persistent memory to determine, from the identifier whether a cached copy of the object is stored in a plurality of data structures, the data structures comprising;

a cyclic index memory capable, of storing index entries comprising an—

index, the index having a beginning;

a cyclic object memory capable of storing and retrieving objects by logical block number, the object memory having a beginning; and

a metadata memory capable of storing information about the index memory and the object memory, including;

a timestamp capable of storing a time associated with information stored in the metadata memory;

a start of index indicator capable on indicating a location of the beginning of the index within the index memory;

an index memory size capable of specifying a size of the index memory;

an index pointer capable of pointing to a current position within the index memory;

a start of data pointer capable of indicating a location of the beginning of the data within the object memory;

a data memory size capable of specifying a size of the object memory; and

a data pointer capable of pointing to a current position within the object memory, wherein determining whether a cached copy of the object is stored in a plurality of data structures further comprises the steps of;

computing a hash value of the identifier; and

accessing the hash index a—

hash table using the hash value.

28. The computer readable storage medium as in claim 27, wherein the identifier is a uniform resource locator.

29. The computer readable storage medium as in claim 27, the method further comprising:

detecting a crash of the computer system;

determining whether the start of index pointer points to a valid index block;

if the start of index pointer does not point to a valid index block, scanning the index until a valid index block is found or the index is determined to be empty; and

if the start of index pointer does point to a valid index block, scanning the index until an invalid index block is found.