Database system with transactional commit protocol based on safe conjunction of majorities
A database system with a transactional commit protocol based on a safe conjunction of majorities is disclosed. In various embodiments, a directed acyclic graph comprises, for each of a plurality of transactions, data identifying the transaction, data indicating prior transaction(s) on which the transaction depends, and data indicating whether the transaction has been committed. A processor associated with a resource manager of a first database server included in a plurality of database servers each having a resource manager, determines a leading edge comprising a set of committed leaf nodes of the directed acyclic graph. The processor provides data representing a respective leading edge from each respective resource manager, and determines to commit a transaction based on a determination that a majority of the resource managers have indicated they agree on a consistent starting state and ending state for the transaction.
1. A system, comprising:
a memory or other storage device configured to store a directed acyclic graph comprising, for each of a plurality of transactions, data identifying the transaction, data indicating one or more prior transactions on which the transaction depends, and data indicating whether the transaction has been committed; and
a processor associated with a resource manager of a first database server included in a plurality of database servers each having a resource manager, the processor being coupled to the memory or other storage device and configured to:
determine, on behalf of the resource manager, based on the directed acyclic graph a leading edge comprising a set of committed leaf nodes of the directed acyclic graph;
provide data representing a respective leading edge from each respective resource manager of each of the plurality of database servers;
receive, via coordinator included in the processor, a respective leading edge from each respective resource manager of each of the plurality of database servers; and
determine to commit a transaction using the respective leading edges to determine to commit the transaction and based at least in part on a determination that a majority of the resource managers have indicated they agree on a consistent starting state and ending state for the transaction.
2. The system of claim 1 , wherein the plurality of database servers are associated with a database replicated across the plurality of database servers.
3. The system of claim 1 , wherein the plurality of database servers are associated with a database distributed across the plurality of database servers.
4. The system of claim 1 , wherein the coordinator is configured to determine to commit the transaction based at least in part on a determination that a majority of the resource managers have indicated they are prepared to commit the transaction.
5. The system of claim 1 , wherein the coordinator is configured to determine to commit the transaction based at least in part on a determination that a majority of the resource managers have indicated they are prepared to commit the transaction and have reported the same leading edge.
6. The system of claim 1 , wherein the coordinator is configured to determine to commit the transaction based at least in part on a determination that a majority of the resource managers have indicated they are prepared to commit the transaction and a majority have reported leading edges that are not identical but are compatible.
7. The system of claim 1 , wherein the processor is further configured to receive a message to commit the transaction and a leading edge data associated with the commit message; and to commit the transaction based at least in part on a determination that the received leading edge data matches a local leading edge of a local directed acyclic graph.
8. The system of claim 1 , wherein the processor is further configured to receive a message to commit the transaction and a leading edge data associated with the commit message; and to initiate a catch up procedure based at least in part on a determination that the received leading edge data does not match a local leading edge of a local directed acyclic graph.
9. The system of claim 8 , wherein the catch up procedure includes using data from a peer system having a directed acyclic graph with a leading edge that matches the leading edge data associated with the commit message.
10. The system of claim 9 , wherein the processor is further configured to send a committed message upon completing the catch up procedure successfully including by committing the transaction.
11. A system, comprising:
a memory or other storage device configured to store a directed acyclic graph comprising, for each of a plurality of transactions, data identifying the transaction, data indicating one or more prior transactions on which the transaction depends, and data indicating whether the transaction has been committed; and
a processor coupled to the memory or other storage device, wherein the processor is associated with a resource manager of a first database server included in a plurality of database servers each having a resource manager, and the plurality of database servers are (i) associated with a database distributed across the plurality of database servers, and (ii) the plurality of database servers are configured in a plurality of subgroups each storing an associated shard of the distributed database, the processor being configured to:
determine, on behalf of the resource manager, based on the directed acyclic graph a leading edge comprising a set of committed leaf nodes of the directed acyclic graph;
provide data representing a respective leading edge from each respective resource manager of each of the plurality of database servers;
determine to commit a transaction based at least in part on a determination that a majority of the resource managers have indicated they agree on a consistent starting state and ending state for the transaction;
receive from each database server participating in the transaction a response indicating whether the database server is prepared to commit the transaction and data representing a local leading edge of a local directed acyclic graph of the database server;
determine with respect to each shard implicated by the transaction whether a majority of database servers have indicated they are prepared to commit the transaction and have reported a leading edge that is compatible with committing the transaction; and
commit the transaction based at least in part on a determination, based on the shard-specific determinations, that all shards implicated by the transaction have a majority of participating database servers prepared to commit the transaction.
12. A method, comprising:
storing a directed acyclic graph comprising, for each of a plurality of database transactions, data identifying the transaction, data indicating one or more prior database transactions on which the transaction depends, and data indicating whether the transaction has been committed;
determining based on the directed acyclic graph a leading edge comprising a set of committed leaf nodes of the directed acyclic graph, wherein the determination of the leading edge is associated with a first database server included in a plurality of database servers;
providing data representing a respective leading edge from each respective resource manager of each of the plurality of database servers, wherein the respective leading edge is included in a set of leading edges provided by respective resource managers associated with a plurality of database servers;
receiving a respective leading edge from each respective resource manager of each of the plurality of database servers; and
determining to commit a transaction using the respective leading edges to determine to commit the transaction and based at least in part on a determination that a majority of the resource managers have indicated they agree on a consistent starting state and ending state for the transaction.
13. The method of claim 12 , wherein a coordinator is configured to receive a respective leading edge from each respective resource manager of each of a plurality of database servers and to use the respective leading edges to determine whether to commit the transaction.
14. The method of claim 13 , wherein the plurality of database servers are associated with a database replicated across the plurality of database servers.
15. The method of claim 13 , wherein the plurality of database servers are associated with a database distributed across the plurality of database servers.
16. The method of claim 13 , wherein the coordinator is configured to determine to commit the transaction based at least in part on a determination that a majority of the resource managers have indicated they are prepared to commit the transaction.
17. The method of claim 13 , wherein the coordinator is configured to determine to commit the transaction based at least in part on a determination that a majority of the resource managers have indicated they are prepared to commit the transaction and have reported the same leading edge.
18. The method of claim 13 , wherein the coordinator is configured to determine to commit the transaction based at least in part on a determination that a majority of the resource managers have indicated they are prepared to commit the transaction and a majority have reported leading edges that are not identical but are compatible.
19. A computer program product embodied in a non-transitory computer readable medium and comprising computer instructions for:
storing a directed acyclic graph comprising, for each of a plurality of database transactions, data identifying the transaction, data indicating one or more prior database transactions on which the transaction depends, and data indicating whether the transaction has been committed;
determining based on the directed acyclic graph a leading edge comprising a set of committed leaf nodes of the directed acyclic graph, wherein the determination of the leading edge is associated with a first database server included in a plurality of database servers;
providing data representing a respective leading edge from each respective resource manager of each of the plurality of database servers, wherein the respective leading edge is included in a set of leading edges provided by respective resource managers associated with a plurality of database servers;
receiving a respective leading edge from each respective resource manager of each of the plurality of database servers; and
determining to commit a transaction using the respective leading edges to determine to commit the transaction and based at least in part on a determination that a majority of the resource managers have indicated they agree on a consistent starting state and ending state for the transaction.