Maintaining a shared cache that has partitions allocated among multiple nodes and a data-to-partition mapping

• US 7,120,651 B2
• Filed: 04/23/2004
• Issued: 10/10/2006
• Est. Priority Date: 08/01/2003
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Chandrasekaran, Sashikanth, Pruscino, Angelo, Bamford, Roger J.
• Primary Examiner(s): KIM, HONG CHONG
• Application Number:
  US10/831,248
• Publication Number:
  US 20040215883A1
• Time in Patent Office: 900 Days
• Field of Search: 714/13, 714/15, 714/16, 711/129, 711/135, 711/141, 711/143, 711/144, 711/145, 711/152, 711/153, 711/170, 711/173, 711/202, 711/206, 711/216, 711/217, 711/112, 710/200, 710/240, 707/201, 709/217
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0871 Allocation or management of cache space
• CPC Class Codes: G06F 12/0893 Caches characterised by their organisation or structure
• CPC Class Codes: G06F 16/24552 Database cache management
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users

Abstract

Various techniques are described for improving the performance of a multiple node system by allocating, in two or more nodes of the system, partitions of a shared cache. A mapping is established between the data items managed by the system, and the various partitions of the shared cache. When a node requires a data item, the node first determines which partition of the shared cache corresponds to the required data item. If the data item does not currently reside in the corresponding partition, the data item is loaded into the corresponding partition even if the partition does not reside on the same node that requires the data item. The node then reads the data item from the corresponding partition of the shared cache.

Claims

1. A method for managing data, the method comprising the steps of:

allocating a plurality of partitions of a shared cache, wherein said plurality of partitions include a partition in each of a set of two or more nodes of a multiple node system;

establishing a mapping between the plurality of partitions and a plurality of data items; and

in response to a request for a particular data item by a first node of said multiple node system, performing the steps of

determining which partition of said plurality of partitions corresponds to the particular data item based on said mapping;

determining whether the particular data item currently resides in said corresponding partition;

if the particular data item does not currently reside in said corresponding partition, then loading a copy of the particular data item into the corresponding partition; and

providing the particular data item from the corresponding partition to the first node;

wherein a dirty version of the particular data item resides in a second node of the multiple node system; and

wherein the step of loading a copy of the particular data item into the corresponding partition includes loading the dirty version of the particular data item from the second node into the corresponding partition.

2. The method of claim 1 wherein the step of providing the particular data item includes the first node reading the data item from the corresponding partition.

3. The method of claim 1 wherein the step of providing the particular data item includes the particular data item being sent from the corresponding partition to the first node.

4. The method of claim 1 wherein the corresponding partition resides on a second node of said multiple node system that is different than said first node.

5. The method of claim 1, wherein the multiple node system includes one or more nodes that use said shared cache but do not themselves have any partition of said shared cache.

7. A tangible computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 1.

8. The method of claim 1 wherein the step of establishing a mapping includes:

establishing the mapping by performing a hash operation on hash keys to produce hash values; and

establishing the mapping based on the hash values.

9. The method of claim 8 wherein at least a portion of the hash keys are identifiers associated with data items.

19. A tangible computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 2.

20. A tangible computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 3.

21. A tangible computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 4.

22. A tangible computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 5.

25. A tangible computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 8.

26. A tangible computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 9.

6. A method for managing data, the method comprising the steps of:

allocating a plurality of partitions of a shared cache, wherein said plurality of partitions include a partition in each of a set of two or more nodes of a multiple node system;

establishing a mapping between the plurality of partitions and a plurality of data items; and

in response to a request for a particular data item by a first node of said multiple node system, performing the steps of

determining which partition of said plurality of partitions corresponds to the particular data item based on said mapping;

determining whether the particular data item currently resides in said corresponding partition;

if the particular data item does not currently reside in said corresponding partition, then loading a copy of the particular data item into the corresponding partition; and

providing the particular data item from the corresponding partition to the first node;

wherein each partition of said plurality of partitions maintains lock structures for data items that correspond to the partition based on the mapping; and

wherein the method includes gathering information from each partition of the plurality of partitions to construct wait-for-graphs to perform deadlock detection.

17. The method of claim 6 further comprising:

in response to a change made by a node to a data item, generating redo information associated with the change; and

preventing the node from sending a data item to another node until the redo information is flushed to persistent storage.

18. A tangible computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 17.

23. A tangible computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 6.

10. A method for managing data, the method comprising the steps of:

allocating a plurality of partitions of a shared cache, wherein said plurality of partitions include a partition in each of a set of two or more nodes of a multiple node system;

establishing a mapping between the plurality of partitions and a plurality of data items by performing a hash operation on hash keys to produce hash values, wherein at least a portion of the hash keys are identifiers associated with persistent storage devices and the mapping is based on the hash values; and

in response to a request for a particular data item by a first node of said multiple node system, performing the steps of

determining which partition of said plurality of partitions corresponds to the particular data item based on said mapping;

determining whether the particular data item currently resides in said corresponding partition;

if the particular data item does not currently reside in said corresponding partition, then loading a copy of the particular data item into the corresponding partition; and

providing the particular data item from the corresponding partition to the first node.

11. The method of claim 10 wherein the step of establishing a mapping includes mapping each partition to only data items that persistently reside on storage devices that can be directly accessed by the node on which the partition resides.

27. A tangible computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 10.

28. A tangible computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 11.

12. A method for managing data, the method comprising the steps of:

allocating a plurality of partitions of a shared cache, wherein said plurality of partitions include a partition in each of a set of two or more nodes of a multiple node system;

establishing a mapping between the plurality of partitions and a plurality of data items; and

in response to a request for a particular data item by a first node of said multiple node system, performing the steps of

determining which partition of said plurality of partitions corresponds to the particular data item based on said mapping;

determining whether the particular data item currently resides in said corresponding partition;

if the particular data item does not currently reside in said corresponding partition, then loading a copy of the particular data item into the corresponding partition; and

providing the particular data item from the corresponding partition to the first node;

wherein recovery from failure of a particular partition of said plurality of partitions includes recovering a data item that resided in said particular partition based on a current version of the data item from a node-private cache of a surviving node of said multiple node system.

13. The method of claim 12 further comprising:

in response to a change made by the surviving node to the data item, generating redo information associated with the change; and

preventing the surviving node from sending the data item for recovery until the redo information is flushed to persistent storage.

29. A tangible computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 12.

30. A tangible computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 13.

14. A method for managing data, the method comprising the steps of:

allocating a plurality of partitions of a shared cache, wherein said plurality of partitions include a partition in each of a set of two or more nodes of a multiple node system;

establishing a mapping between the plurality of partitions and a plurality of data items; and

in response to a request for a particular data item by a first node of said multiple node system, performing the steps of

determining which partition of said plurality of partitions corresponds to the particular data item based on said mapping;

determining whether the particular data item currently resides in said corresponding partition;

if the particular data item does not currently reside in said corresponding partition, then loading a copy of the particular data item into the corresponding partition; and

providing the particular data item from the corresponding partition to the first node

wherein;

the multiple node system includes a plurality of nodes;

a node of said plurality of nodes includes a checkpoint associated with a redo log; and

the method further comprises preventing the node from advancing the checkpoint past a position in the redo log associated with a particular data item until the partition, of said plurality of partitions, that is associated with the particular data item has written the particular data item to persistent storage.

31. A tangible computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 14.

15. A method for managing data, the method comprising the steps of:

allocating a plurality of partitions of a shared cache, wherein said plurality of partitions include a partition in each of a set of two or more nodes of a multiple node system;

establishing a mapping between the plurality of partitions and a plurality of data items; and

in response to a request for a particular data item by a first node of said multiple node system, performing the steps of

determining which partition of said plurality of partitions corresponds to the particular data item based on said mapping;

determining whether the particular data item currently resides in said corresponding partition;

if the particular data item does not currently reside in said corresponding partition, then loading a copy of the particular data item into the corresponding partition; and

providing the particular data item from the corresponding partition to the first node;

wherein recovery from failure of a particular partition of said plurality of partitions includes merging redo information from a plurality of nodes in said multiple node system.

16. The method of claim 15 wherein recovery from failure of a particular partition of said plurality of partitions includes

recovering a first subset of data items that map to said failed partition based on current versions of data items that reside in node-private caches of nodes, in said multiple node system, that have not failed;

and

recovering a second subset of data items that map to said failed partition based on redo information created by merging redo from a plurality of nodes in said multiple node system.

24. A tangible computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 16.

32. A tangible computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 15.