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

• US 20040111443A1
• Filed: 05/03/2002
• Published: 06/10/2004
• 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
• Granted Patent: US 7,269,608 B2
• Time in Patent Office: Days
• US Class Current: 707/202
• 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 in a 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 an object from an origin server; and

storing the object in a plurality of data structures, the data structures comprising;

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

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

a metadata buffer capable of storing information about the index buffer and the object buffer.

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

3. A method as in claim 1, further comprising the steps of:

determining whether a current disk data buffer is full, the current disk data buffer associated with a current disk; and

setting a current disk indicator to indicate a longest waiting disk if the current disk data buffer is full.

4. A method as in claim 1, wherein the step of storing objects further comprises the step of:

storing index blocks comprising;

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

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

5. A method as in claim 4, wherein the step of storing index blocks further comprises the step of storing 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 object; and

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

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

7. A method as in claim 1, wherein the cyclic data buffer further comprises:

cells comprising at least one data block.

8. A method as in claim 1, wherein the metadata buffer further comprises:

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

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

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

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

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

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

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

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

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

based on the identifier determining whether a cached copy of the object is stored in a plurality of data structures, the data structures comprising;

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

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

a metadata buffer capable of storing information about the index buffer and the object buffer.

10. A method as in claim 9, wherein the object is a web object.

11. A method as in claim 9, 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 a hash table using the hash value.

12. A method as in claim 11, wherein the identifier is a uniform resource locator.

13. A method as in claim 9, further comprising:

determining whether a 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.

14. Apparatus having main memory and persistent memory, the main memory containing at least one data buffer, the apparatus having an execution unit capable of executing program code, and the apparatus comprising:

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

an object writer for storing the object in a plurality of data structures, the data structures comprising;

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

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

a metadata buffer capable of storing information about the index buffer and the object buffer.

15. The apparatus according to claim 14, wherein the object is a web object.

16. The apparatus according to claim 14, further comprising:

a current disk determiner for determining whether a current disk data buffer is full, the current disk data buffer associated with a current disk; and

program code for setting a current disk indicator to indicate a longest waiting disk if the current disk data buffer is full.

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

an index block writer for storing 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 buffer.

18. The apparatus according to claim 17, wherein the index block writer further comprises an index element writer for writing 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 object; and

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

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

20. The apparatus according to claim 14, wherein the cyclic data buffer further comprises:

cells comprising at least one data block.

21. The apparatus according to claim 14, wherein the metadata buffer further comprises:

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

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

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

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

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

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

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

22. A computer system having main memory and persistent memory, the main memory containing at least one data buffer, the computer system having an execution unit capable of executing program code, and the computer system comprising:

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

a determiner for determining whether a cached copy of the object is stored in a plurality of data structures, based on the identifier, the data structures comprising;

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

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

a metadata buffer capable of storing information about the index buffer and the object buffer.

23. The computer system according to claim 22, wherein the determiner for determining whether a cached copy of the object is stored in a plurality of data structures further comprises:

program code for computing a hash value of the identifier; and

program code for accessing a hash table using the hash value.

24. The computer system according to claim 22, further comprising:

program code for determining whether a start of index pointer points to a valid index block; and

program code for 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.

25. A computer-readable 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 an object from an origin server; and

storing the object in a plurality of data structures, the data structures comprising;

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

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

a metadata buffer capable of storing information about the index buffer and the object buffer.

26. A computer-readable medium as in claim 25, wherein the object is a web object.

27. A computer-readable medium as in claim 25, further comprising the steps of:

determining whether a current disk data buffer is full, the current disk data buffer associated with a current disk; and

setting a current disk indicator to indicate a longest waiting disk if the current disk data buffer is full.

28. A computer-readable medium as in claim 25, wherein the step of storing objects further comprises the step of:

storing 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 buffer.

29. A computer-readable medium as in claim 28, wherein the step of storing index blocks further comprises the step of storing 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 object; and

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

30. A computer-readable medium as in claim 25, wherein the cyclic data buffer further comprises:

cells comprising at least one data block.

31. A computer-readable medium as in claim 25, wherein the metadata buffer further comprises:

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

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

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

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

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

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

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

32. A computer-readable 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

based on the identifier, determining whether a cached copy of the object is stored in a plurality of data structures, the data structures comprising;

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

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

a metadata buffer capable of storing information about the index buffer and the object buffer.

33. A computer-readable medium as in claim 32, 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 a hash table using the hash value.

34. A computer-readable medium as in claim 33, wherein the identifier is a uniform resource locator.

35. A computer-readable medium as in claim 32, the method further comprising:

determining whether a 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.