Database system with transactional commit protocol based on safe conjunction of majorities
AssigneeNeo4j Sweden AB
InventorsMats Tobias Lindaaker, James Webber
Life of this patent
Estimating the term…
Abstract
A database system with a transactional commit protocol based on a safe conjunction of majorities is disclosed. In various embodiments, 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 database transaction depends, and data indicating whether the transaction has been committed is stored. A leading edge comprising a set of committed leaf nodes of the directed acyclic graph is determined. Data representing the leading edge is provided to a transaction coordinator configured to use the leading edge to determine based at least in part on the leading edge to commit a transaction.
Claims14
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 database server, wherein the database server is included in a plurality of database servers each having a resource manager and a coordinator, 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, wherein at least one leaf node of the set of committed leaf nodes represents a transaction with respect to the database server;
- provide, to the coordinator on behalf of the resource manager, data representing a respective leading edge from each respective resource manager of each of the plurality of database servers;
- and
- determine, on behalf of the coordinator, to commit a 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.
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 database 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 at least one leaf node of the set of committed leaf nodes represents a transaction with respect to a database server, wherein the database server is included in a plurality of database servers each having a resource manager and a coordinator;
- providing data representing a respective leading edge from each respective resource manager of each of the plurality of database servers;
- and
- determining to commit a 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.
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 database 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 at least one leaf node of the set of committed leaf nodes represents a transaction with respect to a database server, wherein the database server is included in a plurality of database servers each having a resource manager and a coordinator;
- providing data representing a respective leading edge from each respective resource manager of each of the plurality of database servers;
- and
- determining to commit a 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.
Dependencies are inferred from the claim text.