Garbage Collection of Multi-Version Concurrency Control (MVCC) Data Blocks

Patent metadata

Field	Value
Publication number	US-2016147449-A1
Application number	US-201414553901-A
Country	US
Kind code	A1
Filing date	Nov 25, 2014
Priority date	Nov 25, 2014
Publication date	May 26, 2016
Grant date	—

Abstract

Disclosed herein are system, method, and computer program product embodiments for performing garbage collection in a database management system with a multi-version concurrency control. An embodiment operate by qualifying a multi-version concurrency control (MVCC) block for garbage collection, where the MVCC block includes multiple cells, each cell corresponding to a row of a table that was acted on by a transaction. Determining that the MVCC block can be garbage collected based on MVCC information in the MVCC block, where the MVCC information includes information that determines whether changes made to rows in the multiple cells are visible in a database management system. Based on the determining, garbage collecting the MVCC block.

First claim

What is claimed is:

1 . A computer implemented method, comprising:
qualifying a multi-version concurrency control (MVCC) block for garbage collection, wherein the MVCC block includes multiple cells, each cell corresponding to a row of a table that was acted on by a transaction; determining that the MVCC block can be garbage collected based on MVCC information in a block header of the MVCC block, wherein the MVCC information includes information that determines whether changes made to rows corresponding to the multiple cells are visible in a database management system; and based on the determining, garbage collecting the MVCC block.

2 . The method of claim 1 , wherein the qualifying further comprises:
determining whether a read snapshot table that corresponds to a time the table was read by a reader thread is less than a block minimum timestamp in the MVCC block.

3 . The method of claim 1 , wherein the qualifying further comprises:
determining whether the multiple cells include a cell with a temporary timestamp.

4 . The method of claim 1 , further comprising:
subsequent to garbage collecting the MVCC block when there are no active entries in the MVCC block, replacing the MVCC block with a stub block that includes a range of rows that corresponds to row positions of the rows of the MVCC block.

5 . The method of claim 1 , wherein the determining further comprises:
determining a value of an active cell counter in the MVCC information of the MVCC block, wherein the active cell counter corresponds to a number of cells in the MVCC block that have not been garbage collected; and garbage collecting the MVCC block based on the value of the active cell counter.

6 . The method of claim 1 , wherein the determining further comprises:
for each cell in the multiple cells in the MVCC block:
determining a value of a commit timestamp;
determining when the value is less than or equal to a read snapshot timestamp; and
based on the determining that the value is less than or equal to the read snapshot timestamp:
updating row state information of a row corresponding to the cell as visible or invisible based on an action in the transaction; and
marking the cell for garbage collection.

7 . The method of claim 6 , further comprising:
determining a number of cells marked for garbage collection; subtracting the number of cells from the active cell counter in the MVCC information; and garbage collecting the MVCC block based on a value of the active cell counter.

8 . The method of claim 6 , wherein the action is an insert instruction or a delete instruction.

9 . The method of claim 1 , further comprising:
for each cell in the multiple cells of the MVCC block:
determining a value of a commit timestamp;
determining when the value is greater than a read snapshot timestamp associated with the table; and
based on the determining that the value is greater than the read snapshot timestamp, updating a block minimum timestamp of the MVCC block with the commit timestamp when the current value of block minimum timestamp is greater than the current commit timestamp.

10 . A system, comprising:
a memory; and at least one processor coupled to the memory and configured to:
qualify a multi-version concurrency control (MVCC) block for garbage collection, wherein the MVCC block includes multiple cells, each cell corresponding to a row of a table that was acted on by a transaction;
determine that the MVCC block can be garbage collected based on MVCC information in a block header of the MVCC block, wherein the MVCC information includes information that determines whether changes made to rows corresponding to the multiple cells are visible in a database management system; and
based on the determination, garbage collect the MVCC block.

11 . The system of claim 10 , wherein to qualify the MVCC block for garbage collection, the at least one processor is further configured to determine whether a read snapshot table that corresponds to a time the table was read by a reader thread is less than a block minimum timestamp in the MVCC block.

12 . The system of claim 10 , wherein to qualify the MVCC block for garbage collection, the at least one processor is further configured to determine whether the multiple cells include a cell with a temporary timestamp.

13 . The system of claim 10 , wherein subsequent to garbage collecting the MVCC block and when there are no active entries in the MVCC block, the at least one processor is configured to replace the MVCC block with a stub block that includes a range of rows that corresponds to row positions of the rows in the MVCC block.

14 . The system of claim 10 , wherein to determine whether the MVCC block can be garbage collected the at least one processor is configured to:
determine a value of an active cell counter in the MVCC information of the MVCC block, wherein the active cell counter corresponds to a number of cells in the MVCC block that have not been garbage collected; and garbage collect the MVCC block based on the value of the active cell counter.

15 . The system of claim 10 , wherein to determine whether the MVCC block can be garbage collected the at least one processor is configured to:
for each cell in the multiple cells in the MVCC block:
determine a value of a commit timestamp;
determine if the value is less than or equal to a read snapshot timestamp; and
based on the determination that the value is less than or equal to the read snapshot timestamp:
update row state information of a row corresponding to the cell as visible or invisible based on an action in the transaction; and
mark the cell for garbage collection.

16 . The system of claim 15 wherein the at least one processor is configured to:
determine a number of cells marked for garbage collection;
subtract the number of cells from an active cell counter in the MVCC information; and
garbage collect the MVCC block based on a value of the active cell counter.

17 . The system of claim 10 , wherein the at least one processor is configured to:
for each cell in the multiple cells of the MVCC block:
determine a value of a commit timestamp;
determine when the value is greater than a read snapshot timestamp associated with the table; and
based on the determination that the value is greater than the read snapshot timestamp, update a block minimum timestamp of the MVCC block with the commit timestamp.

18 . A tangible computer-readable device having instructions stored thereon that, when executed by at least one computing device, causes the at least one computing device to perform operations comprising:
qualifying a multi-version concurrency control (MVCC) block for garbage collection, wherein the MVCC block includes multiple cells, each cell corresponding to a row of a table that was acted on by a transaction; determining that the MVCC block can be garbage collected based on MVCC information in a block header of the MVCC block, wherein the MVCC information includes information that determines whether changes made to rows corresponding to the multiple cells are visible in a database management system; and based on the determining, garbage collecting the MVCC block.

19 . The computer-readable device of claim 18 , the operations further comprising:
determining whether a read snapshot table that corresponds to a time the table was read by a reader thread is less than a block minimum timestamp in the MVCC block.

20 . The computer-readable device of claim 18 , the

Assignees

• Andrei Mihnea
• Schreter Ivan
• Eluri Amarnadh Sai

Inventors

• Andrei Mihnea
• Schreter Ivan
• Eluri Amarnadh Sai

Classifications

• G06F16/2308 Primary

  Concurrency control (transaction processing G06F9/466) · CPC title

• G06F16/2322 Primary

  using timestamps · CPC title

• G06F3/0608

  Saving storage space on storage systems · CPC title

• G06F3/064 Primary

  Management of blocks · CPC title

• G06F3/0673

  Single storage device · CPC title