Method for transaction within a distributed database

• US 6,216,126 B1
• Filed: 05/27/1998
• Issued: 04/10/2001
• Est. Priority Date: 05/28/1997
• Status: Expired due to Term

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: Ronström, Ulf Mikael
• Primary Examiner(s): Amsbury, Wayne
• Assistant Examiner(s): PARDO, THUY N
• Application Number:
  US09/084,502
• Time in Patent Office: 1,049 Days
• Field of Search: 707/10, 707/201, 707/202, 707/205, 707/102, 707/203, 707/103, 714/16, 705/8, 709/101, 395/182.18
• US Class Current: 1/1
• CPC Class Codes: G06F 9/466 Transaction processing
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

The present invention relates to a method of performing a transaction that affects several nodes within a system of nodes in which information belonging to a distributed data-base is stored. The transaction originates from a transaction coordinator (1) and affects at least one group of nodes which comprises a first node (n1), a second node (n2) separate from the first node (n1) and possible intermediate nodes (n3) which comprise further nodes that are separated from one another and from the first and the second node. The transaction is opened with a first phase in which the transaction coordinator sends a “prepare ”-message (a) to the first node (n1), the first node then sends a request (b) for preparation or an “unprepared”-message to the second node (n2) either directly or via one or more intermediate nodes (n3), whereafter the second node sends a “prepared”-message or an “unprepared”-message (c) directly to the transaction coordinator (1), which concludes the first phase. In a second phase, the transaction coordinator (1) sends to the second node (n2) a message (d) regarding measures to be taken and the second node then sends the message (e) regarding measures to be taken to the first node (n1), either directly or via one or more intermediate nodes. The first node then sends a concluding message (f) to the transaction coordinator (1), which concludes the second phase. The message (d) regarding measures to be taken is either a “commit”-message or an “abort”-message and the concluding message (f) is either a “committed”-message or an “aborted”-message, depending on whether the first phase was concluded with “prepared” or “unprepared”.

Claims

1. A method of performing a transaction that affects a plurality of nodes within a system of nodes in which information belonging to a distributed data base is stored, wherein said information is divided into tables and said transaction originates from a transaction coordinator, wherein said transaction affects at least one group of parts of at least one first table of said number of tables, wherein said group includes at least a first and a second part and possibly one or more further parts, wherein said first table part is stored in a first node and said second table part is stored in a second node that is separate from said first node, wherein possible other table parts in said group are stored in intermediate nodes comprised of further nodes that are separate from each other and from said first and said second node, and wherein said transaction is a two-safe transaction, characterized by opening said transaction with a first phase in which:

said transaction coordinator sends a “

prepare”

-message, by which is meant a request asking the first node to prepare for said transaction;

when said first node is able to undertake said transaction, said first node sends a prepare request to said second node either directly or via one or more intermediate nodes, or

when said first node is unable to carry out said transaction, said first node sends an “

unprepared”

-message to said second node, either directly or via one or more intermediate nodes;

when said second node is able to undertake said transaction, said second node sends a “

prepared”

-message directly to said transaction coordinator, i.e. a message indicating that all affected nodes are prepared to undertake said transaction;

or

when said second node is unable to carry out said transaction or when said second node has received an “

unprepared”

-message, said second node sends an “

unprepared”

-message directly to said transaction coordinator,

which concludes said first phase, wherein said first phase is followed by a second phase in which;

said transaction coordinator sends directly to said second node a message regarding measures to be carried out;

said second node then sends said message regarding said measures to said first node, either directly or via one or more intermediate nodes; and

in which

said first node then sends a concluding message to said transaction coordinator;

therewith concluding said second phase, where said message regarding said measures is a “

commit”

-message, i.e. a message to carry out the measures in accordance with said transaction, and said concluding message is a “

committed”

-message i.e. a message stating that the measures have been carried out in accordance with the transaction, provided that the first phase is concluded with a “

prepared”

-message, or when said message regarding said measures is an “

abort”

-message, i.e. a message to abort said transaction and said concluding message is an “

aborted”

-message, i.e. the transaction is aborted, when said first phase is concluded with an “

unprepared”

-message,

wherein said transaction affects further groups of table parts where respective groups include parts belonging to said first table or parts belonging to some other table within said data base but separate from said first table;

wherein said table parts are stored in first and second nodes and possibly in one or more intermediate nodes, each being separate from the other within respective groups of parts;

wherein said first phase is opened with said preparatory request from said transaction coordinator to respective first nodes and is concluded with a “

prepared”

-message or an “

unprepared”

-message from respective second nodes to said transaction coordinator;

wherein said second phase is opened with said message regarding measures to be carried out from said transaction coordinator to respective second nodes and concluded with said concluding message from respective first nodes to said transaction coordinator, said message regarding measures to be carried out is a “

commit”

-message, i.e. a message to carry out measures in accordance with said transaction, and said concluding message is a “

committed”

message, i.e. a message stating that the measures have been carried out in accordance with the transaction, when said first phase is concluded with a “

prepared”

-message from all second nodes, or when said message regarding said measures is an “

abort”

-message, i.e. a message to abort said transaction and said concluding message is a transaction aborted message, when said first phase is concluded with an “

unprepared”

message from any second node.

2. A method according to claim 1, characterized by allocating said first part a higher priority than other parts in respective groups.

3. A method according to claim 2, characterized in that respective groups comprise a fragment of a table included in said database, said fragment including said first part, said second part, and a further part;

in that said further part is stored in a third node; and

in that said higher priority exists in said first part constituting a primary copy of a part of said table;

in that said further part forms a secondary copy of said primary copy; and

in that said second part forms a stand-by copy of said primary copy.

4. A method according to claim 3, characterized in that preparation of said first node in said first phase includes said first node generating and applying a lock on all copies belonging to said fragment.

5. A method according to claim 2, characterized in that respective groups include a first and a second part;

in that said second higher priority consists in said first part consisting in a primary copy of a part of said table; and

in that said second part consists in a secondary copy of said primary copy.

6. A method according to claim 1, characterized in that respective groups include one or more further parts which are stored within said intermediate node/nodes;

in that messages in said first phase are sent serially from said first node to said intermediate node/nodes and from there to said second node; and

in that messages in said second phase are sent serially from said second node to said intermediate node/nodes and from there to said first node.

7. A method according to claim 6, characterized in that respective groups comprise a fragment of a table included in said database, said fragment including said first part, said second part, and a further part;

in that said further part is stored in a third node; and

in that said higher priority exists in said first part constituting a primary copy of a part of said table;

in that said further part forms a secondary copy of said primary copy; and

in that said second part forms a stand-by copy of said primary copy.

8. A method according to claim 1, characterized by allocating said first part a higher priority than other parts in respective groups.

9. A method according to claim 1, characterized in that respective groups include one or more further parts which are stored within said intermediate node/nodes;

in that messages in said first phase are sent serially from said first node to said intermediate node/nodes and from there to said second node; and

in that messages in said second phase are sent serially from said second node to said intermediate node/nodes and from there to said first node.

10. A method according to claim 3, in that preparation of said first node in said first phase includes said first node generating and applying a lock on all copies belonging to said fragment.

11. A method according to claim 10, characterized in that the first node generates the release of said lock in respect of all copies belonging to said fragment only after said first node has received said message regarding measures to be carried out and has sent said concluding message.

12. A method according to claim 11, characterized in that said lock is applied in accordance with an appropriate method, for instance such as to render unavailable solely those parts of respective copies that are affected by said transaction while leaving remaining parts available for other transactions.

13. A method according to claim 11 wherein said system is supplemented with a secondary system, characterized in that updating of said secondary system in accordance with said transaction is requested before said lock is released.

14. A method according to claim 10, characterized in that said lock is applied in accordance with an appropriate method, for instance such as to render unavailable solely those parts of respective copies that are affected by said transaction while leaving remaining parts available for other transactions.

15. A method according to claim 14, wherein said system is supplemented with a secondary system, characterized in that updating of said secondary system in accordance with said transaction is requested before said lock is released.

16. A method according to claim 10, wherein said system is supplemented with a secondary system, characterized in that updating of said secondary system in accordance with said transaction is requested before said lock is released.

17. A method according to claim 16, wherein respective transactions are followed by different attributes that control the performance of the transaction concerned, characterized in that when all of said attributes indicate that said secondary system shall be updated by means of a one-safe transmission, said updating is effected by means of a one-safe transmission;

and in that if any of said attributes indicates that said secondary system shall be updated by means of a limited two-safe transmission, said secondary system is updated by means of a limited two-safe transmission.

18. A method according to claim 17, characterized in that a one-safe transmission includes respective first nodes affected by said transaction sending a “

commit”

-message to corresponding nodes within said secondary system regarding those measures to be carried out, whereafter the transaction continues.

19. A method according to claim 17, characterized in that a limited two-safe transmission includes a respective first node affected by said transaction sending a “

commit”

-message to corresponding nodes within said secondary system regarding which measures shall be performed, whereafter said corresponding nodes within said secondary system respond by sending to said first node a “

committed”

-message indicating to said first node that said measures will be performed and that the secondary system will thus be updated in accordance with said transaction, or with a message “

abort”

, indicating to said first node that said measures will not be performed and that said secondary system will thus not be updated in accordance with said transaction.

20. A method according to claim 16, characterized in that a one-safe transmission includes respective first nodes affected by said transaction sending a “

commit”

-message to corresponding nodes within said secondary system regarding those measures to be carried out, whereafter the transaction continues.

21. A method according to claim 15, characterized by generating an indication that a requested measure cannot be carried out and sending this indication from said secondary system to said primary system in a separate transaction or as a part of another transaction between said secondary and said primary systems.

22. A method according to claim 21, characterized in that said secondary system is re-started so as to correctly comprise a copy of said system, when it is indicated that said secondary system will not be updated in accordance with said transaction.

23. A method according to claim 15, characterized in that the information that is sent to respective nodes within said secondary system in conjunction with updating said secondary system includes the information necessary for creating a logical transaction coordinator within said secondary system;

and in that a physical transaction coordinator is selected within said secondary system on the basis of said information and on the basis of momentary loading of nodes belonging to said secondary system.

24. A method according to claim 23, characterized in that a mapping table is stored in or available to all nodes belonging to said secondary system;

in that said mapping table is a table which enables mapping from a logical transaction coordinator to a physical node within said secondary system to be achieved;

in that said information from said primary system includes a choice of logical transaction coordinator within said secondary system;

in that a system coordinator in said secondary system ensures that all logical transaction coordinators can be mapped to a physical node within said secondary system; and

in that the mapping table includes solely nodes that are available to act as a transaction coordinator in the event of a transaction.

25. A method according to claim 16, characterized in that a limited two-safe transmission includes a respective first node affected by said transaction sending a “

commit”

-message to corresponding nodes within said secondary system regarding which measures shall be performed, whereafter said corresponding nodes within said secondary system respond by sending to said first node a “

committed”

-message indicating to said first node that said measures will be performed and that the secondary system will thus be updated in accordance with said transaction, or with a message “

abort”

, indicating to said first node that said measures will not be performed and that said secondary system will thus not be updated in accordance with said transaction.

26. A method according to claim 25, characterized in that said secondary system is re-started so as to correctly comprise a copy of said system, when it is indicated that said secondary system will not be updated in accordance with said transaction.

27. A method according to claim 25, characterized in that the information that is sent to respective nodes within said secondary system in conjunction with updating said secondary system includes the information necessary for creating a logical transaction coordinator within said secondary system;

and in that a physical transaction coordinator is selected within said secondary system on the basis of said information and on the basis of momentary loading of nodes belonging to said secondary system.

28. A method of performing a transaction that affects a plurality of nodes within a system of nodes in which information belonging to a distributed data base is stored, wherein said information is divided into tables and said transaction originates from a transaction coordinator, wherein said transaction affects at least one group of parts of at least one first table of said number of tables, wherein said group includes at least a first and a second part and possibly one or more further parts, wherein said first table part is stored in a first node and said second table part is stored in a second node that is separate from said first node, wherein possible other table parts in said group are stored in intermediate nodes comprised of further nodes that are separate from each other and from said first and said second node, and wherein said transaction is a two-safe transaction, characterized by opening said transaction with a first phase in which:

said transaction coordinator sends a “

prepare”

-message, by which is meant a request asking the first node to prepare for said transaction;

when said first node is able to undertake said transaction, said first node sends a prepare request to said second node either directly or via one or more intermediate nodes, or

when said first node is unable to carry out said transaction, said first node sends an “

unprepared”

-message to said second node, either directly or via one or more intermediate nodes;

when said second node is able to undertake said transaction, said second node sends a “

prepared”

-message directly to said transaction coordinator, i.e. a message indicating that all affected nodes are prepared to undertake said transaction;

or

when said second node is unable to carry out said transaction or when said second node has received an “

unprepared”

-message, said second node sends an “

unprepared”

-message directly to said transaction coordinator,

which concludes said first phase, wherein said first phase is followed by a second phase in which;

said transaction coordinator sends directly to said second node a message regarding measures to be carried out;

said second node then sends said message regarding said measures to said first node, either directly or via one or more intermediate nodes; and

in which

said first node then sends a concluding message to said transaction coordinator;

therewith concluding said second phase, where said message regarding said measures is a “

commit”

-message, i.e. a message to carry out the measures in accordance with said transaction, and said concluding message is a “

committed”

-message, i.e. a message stating that the measures have been carried out in accordance with the transaction, provided that the first phase is concluded with a “

prepared”

-message, or when said message regarding said measures is an “

abort”

-message, i.e. a message to abort said transaction, and said concluding message is an “

aborted”

-message, i.e. the transaction is aborted, when said first phase is concluded with an “

unprepared”

-message,

wherein one of said nodes affected by said transaction crashes during the performance of said transaction, characterized in that

said transaction coordinator checks all ongoing message transmissions;

the transaction phase that has been halted is re-started from the beginning;

the messages are sent in accordance with said phase but with the exclusion of the crashed node; and

if a node receives an earlier received message, the node ignores said message and forwards the same.

29. A method according to claim 28, characterized in that the transaction is aborted when said crashed node is a first node within a fragment that is affected by said transaction and when the crash occurs during the preparatory phase of said transaction.

30. A method of performing a transaction that affects a plurality of nodes within a system of nodes in which information belonging to a distributed data base is stored, wherein said information is divided into tables and said transaction originates from a transaction coordinator, wherein said transaction affects at least one group of parts of at least one first table of said number of tables, wherein said group includes at least a first and a second part and possibly one or more further parts, wherein said first table part is stored in a first node and said second table part is stored in a second node that is separate from said first node, wherein possible other table parts in said group are stored in intermediate nodes comprised of further nodes that are separate from each other and from said first and said second node, and wherein said transaction is a two-safe transaction, characterized by opening said transaction with a first phase in which:

said transaction coordinator sends a “

prepare”

-message, by which is meant a request asking the first node to prepare for said transaction;

when said first node is able to undertake said transaction, said first node sends a prepare request to said second node either directly or via one or more intermediate nodes, or

when said first node is unable to carry out said transaction, said first node sends an “

unprepared”

-message to said second node, either directly or via one or more intermediate nodes;

when said second node is able to undertake said transaction, said second node sends a “

prepared”

-message directly to said transaction coordinator, i.e. a message indicating that all affected nodes are prepared to undertake said transaction;

or

when said second node is unable to carry out said transaction or when said second node has received an “

unprepared”

-message, said second node sends an “

unprepared”

-message directly to said transaction coordinator,

which concludes said first phase, wherein said first phase is followed by a second phase in which;

said transaction coordinator sends directly to said second node a message regarding measures to be carried out;

said second node then sends said message regarding said measures to said first node, either directly or via one or more intermediate nodes; and

in which

said first node then sends a concluding message to said transaction coordinator;

therewith concluding said second phase, where said message regarding said measures is a “

commit”

-message, i.e. a message to carry out the measures in accordance with said transaction, and said concluding message is a “

committed”

-message, i.e. a message stating that the measures have been carried out in accordance with the transaction, provided that the first phase is concluded with a “

prepared”

-message, or when said message regarding said measures is an “

abort”

-message, i.e. a message to abort said transaction, and said concluding message is an “

aborted”

-message, i.e. the transaction is aborted, when said first phase is concluded with an “

unprepared”

-message,

wherein the transaction coordinator crashes during the performance of said transaction and wherein a system coordinator is adapted to detect the crash of a node in the system, characterized in that

the system coordinator sends a general query to all nodes in said system asking whether or not a node is a participant in a transaction where said crashed node is a transaction coordinator;

a new node is allocated the role of transaction coordinator;

all respective nodes affected by said transaction compile a status report which is sent to the new transaction coordinator, and in that

said new transaction coordinator determines on the basis of said status reports whether said transaction shall continue or be aborted.