Mechanisms for efficient cleaning of unneeded row-versions of a database

1 . A method for cleaning unneeded row-versions in a distributed database system including a plurality of nodes, comprising:

receiving, by a node of the plurality of nodes of the distributed database system, a stream of at least Point-in-Time (PiT) creation events and PiT removal events, wherein a PiT removal event is created when a PiT is removed and PiT removal events are in order in the stream by their respective PiT removal timestamp, and wherein a node of the plurality of nodes includes at least a storage storing row-versions;

maintaining, by the node, a PiT collection data structure storing PiT information indicated by the received PiT creation events and PiT removal event, and a current certainty timestamp that monotonically increases based on the received streams;

receiving a list of committed transaction identifiers (IDs) of committed transactions executed by the distributed database system;

maintaining, by the node, an inspection-pending transaction collector identifying committed transactions having at least one inspection-pending row-version in an associated write vector;

selecting, from a write vector associated with an inspection-pending committed transaction, at least one inspection-pending row-version having a commitment timestamp (CMTS) less than or equal to the current certainty timestamp;

determining that a candidate row-version is unneeded by checking the PIT collection data structure to confirm an absence of any PiT timestamp in a range between a CMTS of the candidate row-version and a CMTS of an adjacent located row-version; and

deleting, from a Multi-Version Concurrency Control (MVCC) data-layout in the storage, each row-version determined to be unneeded, including updating at least one of the write vector and the inspection-pending transaction collector based on the deletion.

2 . The method of claim 1 , wherein an unneeded row-version is at least a first committed row-version with a row having a second committed row-version and is indicated by an absence, in the PIT collection data structure, of any PiT timestamp between the commitment timestamps of the first and second committed row-versions, wherein the second committed row-version has been committed after the first committed row-version.

3 . The method of claim 1 , wherein the PiT creation events and PiT removal events are streamed by a sequencer server (SEQ-Server) asynchronously to the plurality of nodes, wherein the SEQ-Server streams the events from a PiT event list in an order that monotonically advances the certainty timestamp at each node.

4 . The method of claim 3 , further comprising:

upon creating a PiT, inserting, by the SEQ-Server, a PIT creation event to a tail of a PiT event list;

upon removing of a PiT, inserting, by the SEQ-Server, a PiT removal event to the tail of a PiT event list;

upon receiving a streaming trigger, streaming events in the PiT event list to the plurality of nodes;

upon reception of an event by the plurality of nodes,

updating, at the node, the PiT collection data structure and the current certainty timestamp based on the received event; and

removing the event from the PiT event list.

5 . The method of claim 4 , further comprising:

upon detecting a quiet period, increasing a logical time counter (LTC), wherein the quiet period is a predefined time window during which no events are added to the PIT event list; and

adding a progress certainty timestamp event to the PiT event list for causing each node to update the current certainty timestamp in the absence of PiT creation events or PiT removal events.

6 . The method of claim 4 , further comprising:

communicating a removal of PiTs from each node of the plurality of nodes to the SEQ-Server based on an SEQ-agent-side usage counter maintained for an enjoyed unified PiT.

7 . The method of claim 6 , wherein a PiT being removed is a unified PiT, and wherein communicating a removal of a unified PiT occurs when no transaction enjoys the unified PiT as indicated by the SEQ-agent-side usage counter reaching zero.

8 . The method of claim 1 , wherein inspecting the row-versions further comprises:

identifying at least one eligible row-version for inspection;

inspecting each identified eligible row-version to:

locate a backward-row-version for removal in each eligible row-version;

determine if a located backward-row-version can be removed;

locate a forward-row-version for removal in each eligible row-version;

determine if a currently-inspected row-version can be removed based on the located forward-row-version and the currently-inspected row-version; and

marking as approved for removal any row-version determined that can be removed, wherein locating the backward-row-version and the forward-row-version comprises issuing one or more requests to the MVCC data-layout in the storage, and wherein determining whether a row-version can be removed comprises checking the PIT collection data structure for an absence of a PiT timestamp in a range defined by the relevant commitment timestamps.

9 . The method of claim 8 , wherein identifying eligible row-version further comprises:

identifying a row-version that is inspection-pending and having a commitment timestamp (CMTS) smaller than or equal to a current certainty timestamp maintained at the node based on the stream.

10 . The method of claim 8 , wherein the backward-row-version is a latest committed row-version of a row whose CMTS is earlier than a CMTS of a currently inspected row-version; and

wherein a forward-row-version is an earliest committed row-version of a row whose CMTS is later than a CMTS of the currently inspected row-version, and is smaller than a certainty timestamp maintained at the node.

11 . The method of claim 1 , wherein a PiT provides a state and content of committed data in the distributed database system.

12 . The method of claim 1 , wherein the distributed database system comprises: one SEQ-server and a plurality of SEQ-agents executed on the plurality of nodes, wherein each of the plurality of nodes includes a storage implementing a persistent data-layout that allows storing row-versions.

13 . The method of claim 1 , wherein a row-version stores a historical version of a row in a table in the distributed database system, wherein row-versions allow managing concurrency and provide the ability to restore or read previous versions of data.

14 . A system for cleaning unneeded row-versions in a distributed database system including a plurality of nodes comprising:

a processing circuitry; and

a memory, the memory containing instructions that, when executed by the processing circuitry, configure the system to:

receive, by a node of the plurality of nodes of the distributed database system, a stream of at least Point-in-Time (PiT) creation events and PiT removal events, wherein a PiT removal event is created when a PiT is removed and PiT removal events are in order in the stream by their respective PiT removal timestamp, and wherein a node of the plurality of nodes includes at least a storage storing row-versions;

maintain, by the node, a PiT collection data structure storing PiT information indicated by the received PiT creation events and PiT removal event, and a current certainty timestamp that monotonically increases based on the received streams;

receive a list of committed transaction identifiers (IDs) of committed transactions executed by the distributed database system;

maintain, by the node, an inspection-pending transaction collector identifying committed transactions having at least one inspection-pending row-version in an associated write vector;

select, from a write vector associated with an inspection-pending committed transaction, at least one inspection-pending row-version having a commitment timestamp (CMTS) less than or equal to the current certainty timestamp;

determine that a candidate row-version is unneeded by checking the PiT collection data structure to confirm an absence of any PiT timestamp in a range between a CMTS of the candidate row-version and a CMTS of an adjacent located row-version; and

delete, from a Multi-Version Concurrency Control (MVCC) data-layout in the storage, each row-version determined to be unneeded, including updating at least one of the write vector and the inspection-pending transaction collector based on the deletion.

15 . The system of claim 14 , wherein an unneeded row-version is at least a first committed row-version with a row having a second committed row-version and is indicated by an absence, in the PIT collection data structure, of any PiT timestamp between the commitment timestamps of the first and second committed row-versions, wherein the second committed row-version has been committed after the first committed row-version.

16 . The system of claim 14 , wherein the PiT creation events and PiT removal events are streamed by a sequencer server (SEQ-Server) asynchronously to the plurality of nodes, wherein the SEQ-Server streams the events from a PiT event list in an order that monotonically advances the certainty timestamp at each node.

17 . The system of claim 16 , wherein the memory contains further instructions which when executed by the processing circuitry further configure the system to:

upon creating a PiT, insert, by the SEQ-Server, a PiT creation event to a tail of a PiT event list

upon removing of a PiT, insert, by the SEQ-Server, a PiT removal event to the tail of a PiT event list

upon receiving a streaming trigger, stream events in the PiT event list to the plurality of nodes;

upon reception of an event by the plurality of nodes,

update, at the node, the PiT collection data structure and the current certainty timestamp based on the received event; and

remove the event from the PiT event list.

18 . The system of claim 17 , wherein the memory contains further instructions which when executed by the processing circuitry further configure the system to:

upon detecting a quiet period, increase a logical time counter (LTC), wherein the quiet period is a predefined time window during which no events are added to the PiT event list; and

add a progress certainty timestamp event to the PiT event list for causing each node to update the current certainty timestamp in the absence of PiT creation events or PiT removal events.

19 . The system of claim 17 , wherein the memory contains further instructions which when executed by the processing circuitry further configure the system to:

communicate a removal of PiTs from each node of the plurality of nodes to the SEQ-Server based on an SEQ-agent-side usage counter maintained for an enjoyed unified PiT.

20 . The system of claim 19 , wherein a PiT being removed is a unified PiT, and wherein communicating a removal of a unified PiT occurs when no transaction enjoys the unified PiT as indicated by the SEQ-agent-side usage counter reaching zero.

21 . The system of claim 14 , wherein the memory contains further instructions which when executed by the processing circuitry for inspecting the row-versions further configure the system to:

identify at least one eligible row-version for inspection

inspect each identified eligible row-version to:

locate at least one a backward-row-version for removal in each eligible row-version

determine if a located backward-row-version can be removed

locate at least one a forward-row-version for removal in each eligible row-version

determine if a currently-inspected row-version located forward-row-version can be removed based on the located forward-row-version and the currently-inspected row-version; and

marking as approved for removal any row-version determined that can be removed wherein locating the backward-row-version and the forward-row-version comprises issuing one or more requests to the MVCC data-layout in the storage, and wherein determining whether a row-version can be removed comprises checking the PiT collection data structure for an absence of a PiT timestamp in a range defined by the relevant commitment timestamps.

22 . The system of claim 21 , wherein the memory contains further instructions which when executed by the processing circuitry for identifying eligible row-version further configure the system to:

identify a row-version that is inspection-pending and having a commitment timestamp (CMTS) smaller than or equal to a current certainty timestamp maintained at the node based on the stream.

23 . The system of claim 21 , wherein the backward-row-version is a latest committed row-version of a row whose CMTS is earlier than a CMTS of a currently inspected row-version; and wherein a forward-row-version is an earliest committed row-version of a row whose CMTS is later than a CMTS of the currently inspected row-version, and is smaller than a certainty timestamp maintained at the node.

24 . The system of claim 14 , wherein a PiT provides a state and content of committed data in the distributed database system.

25 . The system of claim 14 , wherein the distributed database system comprises:

one SEQ-server and a plurality of SEQ-agents executed on the plurality of nodes, wherein each of the plurality of nodes incudes includes a storage implementing a persistent data-layout that allows storing row-versions.

26 . The system of claim 14 , wherein a row-version stores a historical version of a row in a table in the distributed database system, wherein row-versions allow managing concurrency and provide the ability to restore or read previous versions of data.

27 . A non-transitory computer-readable medium storing a set of instructions for cleaning unneeded row-versions in a distributed database system including a plurality of nodes, the set of instructions comprising:

one or more instructions that, when executed by one or more processors of a device, cause the device to:

receive, by one a node of the plurality of nodes of the distributed database system, a stream of at least Point-in-Time (PiT) creation events and PiT removal events, wherein a PiT removal event is created when a PiT is removed and PiT removal events are in order in the stream by their respective PiT removal timestamp, and wherein a node of the plurality of nodes includes at least a storage storing row-versions;

maintain, by the node, a PiT collection data structure storing PiT information indicated by the received PiT creation events and PiT removal event, and a current certainty timestamp that monotonically increases based on the received streams;

receive a list of committed transaction identifiers (IDs) of committed transactions executed by the distributed database system;

maintain, by the node, an inspection-pending transaction collector identifying committed transactions having at least one inspection-pending row-version in an associated write vector;

select, from a write vector associated with an inspection-pending committed transaction, at least one inspection-pending row-version having a commitment timestamp (CMTS) less than or equal to the current certainty timestamp;

determine that a candidate row-version is unneeded by checking the PIT collection data structure to confirm an absence of any PiT timestamp in a range between a CMTS of the candidate row-version and a CMTS of an adjacent located row-version; and

delete, from a Multi-Version Concurrency Control (MVCC) data-layout in the storage, each row-version determined to be unneeded, including updating at least one of the write vector and the inspection-pending transaction collector based on the deletion.