Ownership reassignment in a shared-nothing database system

• US 7,139,772 B2
• Filed: 09/17/2003
• Issued: 11/21/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: Pruscino, Angelo, Bamford, Roger J., Chandrasekaran, Sashikanth
• Primary Examiner(s): Mizrahi, Diane D.
• Application Number:
  US10/665,062
• Publication Number:
  US 20040117345A1
• Time in Patent Office: 1,161 Days
• Field of Search: 707 1- 10, 707100-1041, 707200-206
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2386 Bulk updating operations data conversion details G06F16/258
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

Various techniques are described for improving the performance of a shared-nothing database system in which at least two of the nodes that are running the shared-nothing database system have shared access to a disk. Specifically, techniques are provided for changing the ownership of data in a shared-nothing database without changing the location of the data on persistent storage. Because the persistent storage location for the data is not changed during a transfer of ownership of the data, ownership can be transferred more freely and with less of a performance penalty than would otherwise be incurred by a physical relocation of the data. Various techniques are also described for providing fast run-time reassignment of ownership. Because the reassignment can be performed during run-time, the shared-nothing system does not have to be taken offline to perform the reassignment. Further, the techniques describe how the reassignment can be performed with relatively fine granularity, avoiding the need to perform bulk reassignment of large amounts of data across all nodes merely to reassign ownership of a few data items on one of the nodes.

Claims

1. A method for managing data, comprising:

maintaining a plurality of persistent data items on persistent storage accessible to a plurality of nodes, the persistent data items including a particular data item stored at a particular location on said persistent storage;

assigning exclusive ownership of each of the persistent data items to one of the nodes, wherein a particular node of said plurality of nodes is assigned exclusive ownership of said particular data item;

when any node wants an operation performed that involves said particular data item, the node that desires the operation to be performed ships the operation to the particular node for the particular node to perform the operation on the particular data item while said particular data item continues to reside at said particular location;

reassigning ownership of the particular data item from the particular node to another node without moving the particular data item from said particular location on said persistent storage;

after the reassignment, when any node wants an operation performed that involves said particular data item, the node that desires the operation to be performed ships the operation to said other node for the other node to perform the operation on the particular data item while said particular data item continues to reside at said particular location,

wherein;

said persistent storage is a first persistent storage of a plurality of persistent storages used by a multi-node database system,

the method further comprises reassigning ownership of a second data item from a first node that has access to said first persistent storage to a second node that has access to a second persistent storage but does not have access to said first persistent storage, and

the method further comprises reassigning ownership of the second data item by moving the second data item from said first persistent storage to said second persistent storage.

2. The method of claim 1 wherein the step of reassigning ownership of the particular data item from the particular node to another node includes updating an ownership map that is shared among the plurality of nodes.

14. The method of claim 1 wherein:

at the time said particular data item is to be reassigned to said other node, the particular node stores a dirty version of said particular data item in volatile memory; and

the step of reassigning ownership of the particular data item from the particular node to another node includes writing said dirty version of said particular data item to said persistent storage.

22. The method of claim 1 further comprising the steps of:

in response to transferring ownership of said particular data item to said other node, aborting an in-progress operation that involves said particular data item;

after ownership of the particular data item has been transferred to said other node, re-executing the in-progress operation.

23. The method of claim 1 wherein:

an operation that involves said particular data item is in-progress at the time the transfer of ownership of said particular data item is to be performed;

the method further includes the step of determining whether to wait for said in-progress operation to complete based on a set of one or more factors; and

if it is determined to not wait for said in-progress operation to complete, aborting said in-progress operation.

24. The method of claim 23 wherein said set of one of more factors includes how much work has already been performed by said in-progress operation.

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

33. A 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.

45. A 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.

53. A 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 22.

54. A 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 23.

55. A 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 24.

3. A method for managing data, comprising:

maintaining a plurality of persistent data items on persistent storage accessible to a plurality of nodes, the persistent data items including a particular data item stored at a particular location on said persistent storage;

assigning exclusive ownership of each of the persistent data items to one of the nodes, wherein a particular node of said plurality of nodes is assigned exclusive ownership of said particular data item;

when any node wants an operation performed that involves said particular data item, the node that desires the operation to be performed ships the operation to the particular node for the particular node to perform the operation on the particular data item;

while the particular node continues to operate, reassigning ownership of the particular data item from the particular node to another node;

after the reassignment, when any node wants an operation performed that involves said particular data item, the node that desires the operation to be performed ships the operation to said other node for the other node to perform the operation on the particular data item,

wherein;

said persistent storage is a first persistent storage of a plurality of persistent storages used by said multi-node database system; and

the method further comprises reassigning ownership of a second data item from a first node that has access to said first persistent storage to a second node that has access to a second persistent storage but does not have access to said first persistent storage; and

wherein the step of reassigning ownership of the second data item includes moving the second data item from said first persistent storage to said second persistent storage.

4. The method of claim 3, wherein the plurality of nodes are nodes of a multi-node database system.

5. The method of claim 4 wherein the multi-node database system includes nodes that do not have access to said first persistent storage.

6. The method of claim 5 wherein the step of reassigning ownership of the particular data item from the particular node to another node is performed in response to the addition of said other node to said multi-node database system.

7. The method of claim 5 wherein:

the step of reassigning ownership of the particular data item from the particular node to another node is performed in anticipation of the removal of said particular node from said multi-node database system; and

the method further comprises the step of, in anticipation of the removal of said particular node from said multi-node database system, physically moving from said persistent storage to another persistent storage a second data item that is reassigned from said particular node to a node of said multi-node database system that does not have access to said persistent storage.

8. The method of claim 5 wherein the step of reassigning ownership of the particular data item from the particular node to another node is performed as part of a gradual transfer of ownership from said particular node to one or more other nodes.

9. The method of claim 8 wherein the gradual transfer is initiated in response to detecting that said particular node is overworked relative to one or more other nodes in said multi-node database system.

34. A 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.

35. A 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.

36. A 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.

37. A 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.

38. A 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 7.

39. A 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.

40. A 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.

10. A method for managing data, comprising:

maintaining a plurality of persistent data items on persistent storage accessible to a plurality of nodes, the persistent data items including a particular data item stored at a particular location on said persistent storage,

wherein the plurality of nodes are nodes of a multi-node database system;

assigning exclusive ownership of each of the persistent data items to one of the nodes, wherein a particular node of said plurality of nodes is assigned exclusive ownership of said particular data item;

when any node wants an operation performed that involves said particular data item, the node that desires the operation to be performed ships the operation to the particular node for the particular node to perform the operation on the particular data item;

while the particular node continues to operate, reassigning ownership of the particular data item from the particular node to another node;

wherein the step of reassigning ownership of the particular data item from the particular node to said other node is performed as part of a gradual transfer of ownership from said particular node to one or more other nodes in said multi-node database system,

wherein the gradual transfer is initiated in response to detecting that said particular node is overworked relative to the one or more other nodes,

wherein the gradual transfer is terminated in response to detecting that said particular node is now longer overworked relative to the one or more other nodes; and

after the reassignment, when any node wants an operation performed that involves said particular data item, the node that desires the operation to be performed ships the operation to said other node for the other node to perform the operation on the particular data item.

41. A 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.

11. A method for managing data, comprising:

maintaining a plurality of persistent data items on persistent storage accessible to a plurality of nodes, the persistent data items including a particular data item stored at a particular location on said persistent storage,

wherein the plurality of nodes are nodes of a multi-node database system;

assigning exclusive ownership of each of the persistent data items to one of the nodes, wherein a particular node of said plurality of nodes is assigned exclusive ownership of said particular data item;

when any node wants an operation performed that involves said particular data item, the node that desires the operation to be performed ships the operation to the particular node for the particular node to perform the operation on the particular data item;

while the particular node continues to operate, reassigning ownership of the particular data item from the particular node to another node;

wherein the step of reassigning ownership of the particular data item from the particular node to another node is performed as part of a gradual transfer of ownership to said other node by one or more other nodes, wherein said gradual transfer is initiated in response to detecting that said other node is underworked relative to the one or more other nodes in said multi-node database system;

after the reassignment, when any node wants an operation performed that involves said particular data item, the node that desires the operation to be performed ships the operation to said other node for the other node to perform the operation on the particular data item.

42. A 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, comprising:

maintaining a plurality of persistent data items on persistent storage accessible to a plurality of nodes, the persistent data items including a particular data item stored at a particular location on said persistent storage;

assigning exclusive ownership of each of the persistent data items to one of the nodes, wherein a particular node of said plurality of nodes is assigned exclusive ownership of said particular data item;

when any node wants an operation performed that involves said particular data item, the node that desires the operation to be performed ships the operation to the particular node for the particular node to perform the operation on the particular data;

while the particular node continues to operate, reassigning ownership of the particular data item from the particular node to another node;

after the reassignment, when any node wants an operation performed that involves said particular data item, the node that desires the operation to be performed ships the operation to said other node for the other node to perform the operation on the particular data item; and

after a first node has been removed from the multi-node system, continuing to have a set of data items owned by the first node.

13. The method of claim 12, further comprising:

reassigning ownership of a data item from the first node to a second node in response to detecting that the workload of said second node has fallen below a predetermined threshold.

43. A 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.

44. A 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.

65. The method of claim 12, further comprising:

reassigning ownership of data items from the first node to one or more other nodes in response to detecting requests for operations that involve said data items.

66. A 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 65.

15. A method for managing data, comprising:

maintaining a plurality of persistent data items on persistent storage accessible to a plurality of nodes, the persistent data items including a particular data item stored at a particular location on said persistent storage;

assigning exclusive ownership of each of the persistent data items to one of the nodes, wherein a particular node of said plurality of nodes is assigned exclusive ownership of said particular data item;

when any node wants an operation performed that involves said particular data item, the node that desires the operation to be performed ships the operation to the particular node for the particular node to perform the operation on the particular data item;

while the particular node continues to operate, reassigning ownership of the particular data item from the particular node to another node,

wherein;

at the time said particular data item is to be reassigned to said other node, the particular node stores a dirty version of said particular data item in volatile memory; and

the step of reassigning ownership of the particular data item from the particular node to another node includes forcing to persistent storage one or more redo records associated with said dirty version, and purging said dirty version from said volatile memory without writing said dirty version of said particular data item to said persistent storage; and

said other node reconstructs said dirty version by applying said one or more redo records to the version of the particular data item that resides on said persistent storage.

46. A 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.

16. A method for managing data, comprising:

maintaining a plurality of persistent data items on persistent storage accessible to a plurality of nodes, the persistent data items including a particular data item stored at a particular location on said persistent storage;

assigning exclusive ownership of each of the persistent data items to one of the nodes, wherein a particular node of said plurality of nodes is assigned exclusive ownership of said particular data item;

when any node wants an operation performed that involves said particular data item, the node that desires the operation to be performed ships the operation to the particular node for the particular node to perform the operation on the particular data item;

while the particular node continues to operate, reassigning ownership of the particular data item from the particular node to another node,

wherein;

at the time said particular data item is to be reassigned to said other node, the particular node stores a dirty version of said particular data item in volatile memory; and

the method further includes the step of transferring the dirty version of said particular data item from volatile memory associated with said particular node to volatile memory associated with said other node.

17. The method of claim 16 wherein the step of transferring the dirty version is performed proactively by the particular node without the other node requesting the dirty version.

18. The method of claim 16 wherein the step of transferring the dirty version is performed by the particular node in response to a request for the dirty version from said other node.

47. A 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.

48. A 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.

49. A 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 18.

19. A method for managing data, comprising:

maintaining a plurality of persistent data items on persistent storage accessible to a plurality of nodes, the persistent data items including a particular data item stored at a particular location on said persistent storage;

assigning exclusive ownership of each of the persistent data items to one of the nodes, wherein a particular node of said plurality of nodes is assigned exclusive ownership of said particular data item;

when any node wants an operation performed that involves said particular data item, the node that desires the operation to be performed ships the operation to the particular node for the particular node to perform the operation on the particular data item;

reassigning ownership of the particular data item from the particular node to another node,

wherein;

the step of reassigning ownership of the particular data item from the particular node to another node is performed without waiting for a transaction that is modifying the data item to commit;

the transaction makes a first set of modifications while the particular data item is owned by the particular node; and

the transaction makes a second set of modifications while the particular data item is owned by said other node.

20. The method of claim 19 further comprising rolling back changes made by said transaction by rolling back the second set of modifications based on undo records in an undo log associated with said other node, and rolling back the first set of modifications based on undo records in an undo log associated with said particular node.

50. A 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 19.

51. A 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 20.

21. A method for managing data, comprising:

maintaining a plurality of persistent data items on persistent storage accessible to a plurality of nodes, the persistent data items including a particular data item stored at a particular location on said persistent storage;

assigning exclusive ownership of each of the persistent data items to one of the nodes, wherein a particular node of said plurality of nodes is assigned exclusive ownership of said particular data item;

when any node wants an operation performed that involves said particular data item, the node that desires the operation to be performed ships the operation to the particular node for the particular node to perform the operation on the particular data item;

while the particular node continues to operate, reassigning ownership of the particular data item from the particular node to another node;

the other node receiving a request to update said data item;

determining whether the particular node held exclusive-mode or shared-mode access to the data item; and

if the particular node did not hold exclusive-mode or shared-mode access to the data item, then the other node updating the particular data item without waiting for the particular node to flush any dirty version of the data item, or redo for the dirty version, to persistent storage.

52. A 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 21.

25. A method of managing data, the method comprising the steps of:

maintaining a plurality of persistent data items on persistent storage accessible to a plurality of nodes;

assigning ownership of each of the persistent data items to one of the nodes by assigning each data item to one of a plurality of buckets by enumerating individual data-item-to-bucket relationships; and

assigning each bucket to one of the plurality of nodes by enumerating individual bucket-to-node relationships;

wherein the node to which a bucket is assigned is established to be owner of all data items assigned to the bucket;

when a first node wants an operation performed that involves a data item owned by a second node, the first node ships the operation to the second node for the second node to perform the operation.

26. The method of claim 25 wherein the step of assigning each data item to one of a plurality of buckets is performed by applying a hash function to a name associated with each data item.

27. The method of claim 25 wherein the step of assigning each bucket to one of the plurality of nodes is performed by applying a hash function to an identifier associated with each bucket.

28. The method of claim 25 wherein the step of assigning each data item to one of a plurality of buckets is performed using range-based partitioning.

29. The method of claim 25 wherein the step of assigning each bucket to one of the plurality of nodes is performed using range-based partitioning.

30. The method of claim 25 wherein the number of buckets is greater than the number of nodes, and the bucket-to-node relationship is a many-to-one relationship.

31. The method of claim 25 further comprising the step of reassigning from a first node to a second node ownership of all data items that are mapped to a bucket by modifying a bucket-to-node mapping without modifying a data-item-to-bucket mapping.

56. A 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 25.

57. A 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 26.

58. A 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 27.

59. A 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 28.

60. A 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 29.

61. A 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 30.

62. A 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 31.

63. A method for use in a multi-node shared-nothing database system, the method comprising the steps of:

a first node of said multi-node shared-nothing database system initially functioning as exclusive owner of a first data item and a second data item, wherein said first data item and said second data item are persistently stored data items within a database managed by the multi-node shared-nothing database system;

without changing the location of a first data item on persistent storage or shutting down said first node, reassigning ownership of the first data item from the first node to a second node of said multi-node shared-nothing database system; and

after reassigning ownership, the first node continuing to operate as the owner of the second data item, and to handle all requests for operations on said second data item.

64. A 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 63.