Systems and methods for data caching

• US 7,284,096 B2
• Filed: 08/05/2004
• Issued: 10/16/2007
• Est. Priority Date: 08/05/2003
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP AG (SAP SE)
• Inventors: Schreter, Ivan
• Primary Examiner(s): Sparks; Donald
• Assistant Examiner(s): Thammavong; Prasith
• Application Number:
  US10/911,716
• Publication Number:
  US 20050055511A1
• Time in Patent Office: 1,167 Days
• Field of Search: 711/134, 711/136
• US Class Current: 711/136
• 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
• CPC Class Codes: G06F 2212/465 Structured object, e.g. database record

Abstract

Systems and methods are provided for data caching. An exemplary method for data caching may include establishing a FIFO queue and a LRU queue in a cache memory. The method may further include establishing an auxiliary FIFO queue for addresses of cache lines that have been swapped-out to an external memory. The method may further include determining, if there is a cache miss for the requested data, if there is a hit for requested data in the auxiliary FIFO queue and, if so, swapping-in the requested data into the LRU queue, otherwise swapping-in the requested data into the FIFO queue.

Claims

1. A method of data caching, comprising:

establishing a FIFO queue and a LRU queue in a cache memory;

establishing an auxiliary FIFO queue for addresses of cache lines which have been swapped-out to an external memory;

when there is a cache miss for an address for requested data;

determining if there is a hit for the address for the requested data in the auxiliary FIFO queue, and if there is a hit for the address for the reguested data in the auxiliary FIFO queue, swapping-in the requested data into the LRU queue from the external memory, and

when there is a cache miss for the address for the requested data in the auxiliary FIFO queue, swapping-in the requested data into the FIFO queue; and

when there is a cache hit for the address for the requested data, returning the requested data.

2. The method of claim 1, wherein the FIFO queue has a first predefined maximum size and the LRU queue has a second predefined maximum size, and further wherein the first predefined maximum size is below the second predefined maximum size.

3. The method of claim 1, wherein the following steps are carried out if there is a miss in the auxiliary FIFO queue:

swapping-in the requested data from the external memory;

adding the swapped-in data to the FIFO queue; and

swapping-out an address for an element from the FIFO queue into the auxiliary FIFO queue if the FIFO queue has reached a pre-defined maximum size.

4. The method of claim 1, wherein a predefined maximum size of the FIFO queue is between 5% and 25% of the size of the cache memory.

5. The method of claim 4, wherein the predefined maximum size of the FIFO queue is 10% of the size of the cache memory.

6. The method of claim 1, wherein a predefined maximum size of the LRU queue is between 75% and 95% of the size of the cache memory.

7. The method of claim 6, wherein the predefined maximum size of the LRU queue is 90% of the size of the cache memory.

18. The method of claim 1, wherein the external memory is a disk-based storage device.

19. The method of claim 1, wherein the external memory is main memory associated with at least one processor.

20. The method of claim 1, wherein the cache memory is set-associative.

8. A cache memory storing computer-readable instructions for performing a method of data caching, the method comprising:

establishing a FIFO queue and a LRU queue;

establishing an auxiliary FIFO queue for addresses of cache lines which have been swapped-out to an external memory;

determining if there is a hit corresponding to an address for requested data in the auxiliary FIFO queue and when there is a hit corresponding to the address for the requested data in the auxiliary FIFO queue, swapping-in the requested data into the LRU queue from the external memory in case of the hit; and

determining if there is a hit for the requested data in the auxiliary FIFO queue when there is a cache miss for the address for the requested data.

9. The cache memory of claim 8, wherein the FIFO queue has a first predefined maximum size and the LRU queue has a second predefined maximum size, and further wherein the first predefined maximum size is below the second predefined maximum size.

10. The cache memory of claim 8, the method further comprising:

swapping-in the requested data from the external memory if there is a miss corresponding to the requested data in the auxiliary FIFO queue;

adding the swapped-in data to the FIFO queue; and

swapping-out an element from the FIFO queue into the external memory and putting the element'"'"'s address into the auxiliary FIFO queue, if the FIFO queue has reached a predefined maximum size.

11. The cache memory of claim 8, wherein a predefined maximum size of the FIFO queue is between 5% and 25% of the size of the cache memory.

12. The cache memory of claim 11, wherein the predefined maximum size of the FIFO queue is 10% of the size of the cache memory.

13. The cache memory of claim 8, wherein a predefined maximum size of the LRU queue is between 75% and 95% of the size of the cache memory.

14. The cache memory of claim 13, wherein the predefined maximum size of the LRU queue is 90% of the size of the cache memory.

15. A data processing system comprising:

at least one processor for running an application program;

an external memory; and

a cache memory coupled to the processor and the external memory, the cache memory storing computer-readable instructions for performing a method of data caching, the method comprising;

establishing a FIFO queue and a LRU queue;

establishing an auxiliary FIFO queue for cache line addresses which have been swapped-out to an external memory;

determining if there is a hit corresponding to an address for requested data in the auxiliary FIFO queue and when there is a hit corresponding to the address for the requested data in the auxiliary FIFO queue, swapping-in the requested data into the LRU queue from the external memory in case of the hit; and

determining if there is a hit for the requested data in the auxiliary FIFO queue when there is a cache miss for the address for the requested data.

16. The data processing system of claim 15, wherein the external memory is at least one of a main memory and a disk-based storage device.

17. The data processing system of claim 16, wherein the cache lines are at least one of equally-sized pages and blocks of data from a database.