Granted Patent B2

US 12,306,810 · App. 18/175,590 · Granted May 20, 2025

Inventor: Angela Lin (Ottawa, CA)

G06F16/215G06F16/219

Abstract

Claims (83)

1. A computer-implemented method for distributed version reclaim in a database cluster comprising a plurality of database nodes, the method comprising:

sending, by each database node in response to each of said database node having decreased a respective reference count associated with a respective version to a minimum threshold, a release event to an event log, thereby producing a plurality of release events in the event log, the release event comprising a version number of the respective version and a database node identifier of the respective database node, wherein each of the respective reference count of each of the respective database node is private to the respective database node;

continuously consuming, by a version reclaim-leader, the plurality of release events from the event log;

determining, by the version reclaim-leader, whether a version has been released by each database node of the plurality of database nodes;

generating, by the version reclaim-leader, one or more cleanup transactions for the version when the version reclaim-leader determines that the version has been released by each database node;

committing, by the version reclaim-leader, the one or more cleanup transactions to a transaction log;

continuously replicating, by each database node, the one or more cleanup transactions from the transaction log; and

applying, by each database node, the one or more cleanup transactions for the version.

2. The computer-implemented method of claim 1 , wherein continuously consuming the plurality of release events by the version reclaim-leader comprises:

obtaining, by the version reclaim-leader, an unprocessed event from the event log; and

obtaining, by the version reclaim-leader, the respective version from a payload of the unprocessed event.

3. The computer-implemented method of claim 1 , wherein determining whether the version has been released by each database node of the plurality of database nodes, comprises:

obtaining, by the version reclaim-leader, a set of database nodes associated with the version from a received events map;

determining, by the version reclaim-leader, if the set of database nodes contains every database node in a cluster node list;

determining, by the version reclaim-leader, that the version has been released by each database node when the set of database nodes contains every database node in the cluster node list; and

determining, by the version reclaim-leader, that the version has not been released by each database node when the set of database nodes does not contain every database node in the cluster node list, followed by:

updating, by the version reclaim-leader, the received events map.

4. A computer-implemented method comprising:

transmitting, by a database node to a version reclaim-leader, a departure of the database node from a cluster;

decreasing, at the database node for each respective version of the database node, a corresponding reference count to a minimum threshold, the corresponding reference count being associated with a corresponding respective version of the database node;

sending, by the database node and in response to decreasing the corresponding reference count to the minimum threshold, a corresponding release event to an event log for each of the respective version of the database node;

consuming, by the version reclaim-leader, the corresponding release event from the event log for each of the respective version of the database node;

removing, by the version reclaim-leader and in response to consuming the corresponding release event for each of the respective version of the database node, the database node from a received events map and a cluster node list;

determining, by the version reclaim-leader, one or more reclaimed versions;

generating, by the version reclaim-leader, one or more cleanup transactions for the one or more reclaimed versions;

committing, by the version reclaim-leader, the one or more cleanup transactions to a transaction log; and

replicating, by one or more remaining database nodes in the cluster, the one or more cleanup transactions.

5. A system for distributed version reclaim in a database cluster comprising a plurality of database nodes, the system comprising:

a processor; and

a memory storing instructions that, when executed by the processor, configure the system to:

send, by each database node in response to each of said database node having decreased a respective reference count associated with a respective version to a minimum threshold, a release event to an event log, thereby producing a plurality of release events in the event log, the release event comprising a version number of the respective version and a database node identifier of the respective database node, wherein each of the respective reference count of each of the respective database node is private to the respective database node;

continuously consume, by a version reclaim-leader, the plurality of release events from the event log;

determine, by the version reclaim-leader, whether a version has been released by each database node of the plurality of database nodes;

generate, by the version reclaim-leader, one or more cleanup transactions for the version when the version reclaim-leader determines that the version has been released by each database node;

commit, by the version reclaim-leader, the one or more cleanup transactions to a transaction log;

continuously replicate, by each database node, the one or more cleanup transactions from the transaction log; and

apply, by each database node, the one or more cleanup transactions for the version.

6. The system of claim 5 , wherein when continuously consuming the plurality of release events by the version reclaim-leader, the system is further configured to:

obtain, by the version reclaim-leader, an unprocessed event from the event log; and

obtain, by the version reclaim-leader, the version from a payload of the unprocessed event.

7. The system of claim 5 , wherein when determining whether the version has been released by each database node of the plurality of database nodes, the system is further configured to:

obtain, by the version reclaim-leader, a set of database nodes associated with the version from a received events map;

determine, by the version reclaim-leader, if the set of database nodes contains every database node in a cluster node list;

determine, by the version reclaim-leader, that the version has been released by each database node when the set of database nodes contains every database node in the cluster node list; and

determine, by the version reclaim-leader, that the version has not been released by each database node when the set of database nodes does not contain every database node in the cluster node list, and update, by the version reclaim-leader, the received events map.

8. A system comprising:

a processor; and

a memory storing instructions that, when executed by the processor, configure the system to:

transmit, by a database node to a version reclaim-leader, a departure of the database node from a cluster;

decrease, at the database node for each respective version of the database node, a corresponding reference count to a minimum threshold, the corresponding reference count being associated with a corresponding respective version of the database node;

send, by the database node and in response to decreasing the corresponding reference count to the minimum threshold, a corresponding release event to an event log for each of the respective version of the database node;

consume, by the version reclaim-leader, the corresponding release event from the event log for each of the respective version of the database node;

remove, by the version reclaim-leader and in response to consuming the corresponding release event for each of the respective version of the database node, the database node from a received events map and a cluster node list;

determine, by the version reclaim-leader, one or more reclaimed versions;

generate, by the version reclaim-leader, one or more cleanup transactions for the one or more reclaimed versions;

commit, by the version reclaim-leader, the one or more cleanup transactions to a transaction log; and

replicate, by one or more remaining database nodes in the cluster, the one or more cleanup transactions.

9. A non-transitory computer-readable storage medium for distributed version reclaim in a database cluster comprising a plurality of database nodes, the computer-readable storage medium including instructions that when executed by a computer, cause the computer to:

send, by each database node in response to each of said database node having decreased a respective reference count associated with a respective version to a minimum threshold, a release event to an event log, thereby producing a plurality of release events in the event log, the release event comprising a version number of the respective version and a database node identifier of the respective database node, wherein each of the respective reference count of each of the respective database node is private to the respective database node;

continuously consume, by a version reclaim-leader, the plurality of release events from the event log;

determine, by the version reclaim-leader, whether a version has been released by each database node of the plurality of database nodes;

generate, by the version reclaim-leader, one or more cleanup transactions for the version when the version reclaim-leader determines that the version has been released by each database node;

commit, by the version reclaim-leader, the one or more cleanup transactions to a transaction log;

continuously replicate, by each database node, the one or more cleanup transactions from the transaction log; and

apply, by each database node, the one or more cleanup transactions for the version.

10. The non-transitory computer-readable storage medium of claim 9 , wherein when continuously consuming the plurality of release events by the version reclaim-leader, the computer-readable storage medium including instructions that when executed by the computer, further cause the computer to:

obtain, by the version reclaim-leader, an unprocessed event from the event log; and

obtain, by the version reclaim-leader, the version from a payload of the unprocessed event.

11. The non-transitory computer-readable storage medium of claim 9 , wherein when determining whether the version has been released by each database node of the plurality of database nodes, the computer-readable storage medium including instructions that when executed by the computer, further cause the computer to:

obtain, by the version reclaim-leader, a set of database nodes associated with the version from a received events map; and

determine, by the version reclaim-leader, if the set of database nodes contains every database node in a cluster node list;

determine, by the version reclaim-leader, that the version has been released by each database node when the set of database nodes contains every database node in the cluster node list; and

determine, by the version reclaim-leader, that the version has not been released by each database node when the set of database nodes does not contain every database node in the cluster node list, and update, by the version reclaim-leader, the received events map.

12. A non-transitory computer-readable storage medium, the computer-readable storage medium including instructions that when executed by a computer, cause the computer to:

transmit, by a database node to a version reclaim-leader, a departure of the database node from a cluster;

decrease, at the database node for each respective version of the database node, a corresponding reference count to a minimum threshold, the corresponding reference count being associated with a corresponding respective version of the database node;

send, by the database node and in response to decreasing the corresponding reference count to the minimum threshold, a corresponding release event to an event log for each of the respective version of the database node;

consume, by the version reclaim-leader, the corresponding release event from the event log for each of the respective version of the database node;

remove, by the version reclaim-leader and in response to consuming the corresponding release event for each of the respective version of the database node, the database node from a received events map and a cluster node list;

determine, by the version reclaim-leader, one or more reclaimed versions;

generate, by the version reclaim-leader, one or more cleanup transactions for the one or more reclaimed versions;

commit, by the version reclaim-leader, the one or more cleanup transactions to a transaction log; and

replicate, by one or more remaining database nodes in the cluster, the one or more cleanup transactions.

Assignments (1)

Continuity (2)

References Cited (16)