Snapshots of a column store

Patent metadata

Field	Value
Publication number	US-12373411-B2
Application number	US-202117314911-A
Country	US
Kind code	B2
Filing date	May 7, 2021
Priority date	May 7, 2015
Publication date	Jul 29, 2025
Grant date	Jul 29, 2025

Abstract

Columnar storage provides many performance and space saving benefits for analytic workloads, but previous mechanisms for handling single row update transactions in column stores suffer from poor performance. A columnar data layout facilitates both low-latency random access capabilities together with high-throughput analytical access capabilities, simplifying Hadoop architectures for use cases involving real-time data. In disclosed embodiments, systems may perform read and scan features through which users may have consistent reads of the columnar storage at any given point in time. These scans (e.g., snapshots) allow for analytics to be performed on the data, consistent backups of the data, for incremental backups, perform cross-cluster synchronization, and/or for offline audit analysis.

First claim

I claim:

1. A method for implementing read or scan in a distributed database system that supports multi-version concurrency control (MVCC), the method comprising:
instantiating a scanner at a particular timepoint, the scanner being configured to provide a point-in-time snapshot of a dataset associated with the particular timepoint, wherein the dataset includes a row stored in an on-disk store via (i) a base data module for storing a column data for the row and (ii) a delta module for storing a set of REDO delta records each indicating a later state of the column data stored in the base data module and a set of UNDO delta records each indicating an earlier state of the column data, wherein each of the set of REDO delta records and the set of UNDO delta records is associated with a unique transaction identifier;
performing a delta compaction that causes the column data stored in the base data module to be updated to a particular later state based on applying one or more of the set of REDO delta records, wherein the delta compaction removes the one or more of the set of REDO delta records from the delta module to create a decreased set of REDO delta records and adds one or more new UNDO delta records that correspond to the one or more of the set of REDO delta records to create an increased set of UNDO delta records; and
using the scanner to provide the point-in-time snapshot of the dataset associated with the particular timepoint, wherein the point-in-time snapshot is configured to include at least the row, and wherein the scanner is configured to provide the point-in-time snapshot by:
selecting a subset of the increased set of UNDO delta records or the decreased set of REDO delta records according to a state of a MVCC manager instance captured by the scanner when instantiated at the particular timepoint, the state of the MVCC manager instance associating a particular transaction identifier with the particular timepoint;
copying the updated column data for the row from the base data module of the on-disk store into an output buffer of the scanner;
iteratively applying, to the output buffer, mutations indicated by the selected subset of the increased set of UNDO delta records or the decreased set of REDO delta records to change the updated column data to a particular committed state associated with the particular timepoint; and
providing the point-in-time snapshot via the output buffer of the scanner.

2. The method of claim 1 , wherein iteratively applying the mutations comprises:
upon determining that a given one of the selected subset of the increased set of UNDO delta records or the decreased set of REDO delta records indicates a delete operation, marking the row as deleted in the output buffer.

3. The method of claim 1 ,
wherein the set of UNDO delta records and the set of REDO delta records each correspond to an update operation, delete operation, or reinsert operation to which the row is subjected,
wherein unique transaction identifiers for the set of UNDO delta records and the set of REDO delta records are monotonically increasing.

4. The method of claim 1 , further comprising:
storing one or more versions of the row in the database, wherein each of the one or more versions has at least one of the mutations applied to the row.

5. The method of claim 4 , further comprising:
determining which of the one or more versions of the row to garbage collect based on a retention period.

6. The method of claim 1 , wherein the set of UNDO delta records and the set of REDO delta records are implemented as a singly linked list.

7. The method of claim 6 , wherein the singly linked list includes a mutation head that points to a given mutation node corresponding to a first mutation of the set of UNDO delta records or the set of REDO delta records, and a next mutation pointer in the given mutation node points to a subsequent mutation node corresponding to a second mutation of the set of UNDO delta records and the set of REDO delta records.

8. The method of claim 6 , wherein each mutation node of the singly linked list includes a change record field indicating the data of the row to be mutated.

9. A computing system comprising:
one or more processors; and
one or more memories storing instructions that, when executed by the one or more processors, cause the computing system to perform a process for implementing read or scan in a distributed database system that supports multi-version concurrency control (MVCC), the process comprising:
instantiating a scanner at a particular timepoint, the scanner being configured to provide a point-in-time snapshot of a dataset associated with the particular timepoint, wherein the dataset includes a row stored in a persistent storage via (i) a base data module for storing a column data for the row, and (ii) a delta module for storing a set of REDO delta records each indicating a later state of the column data stored in the base data module and a set of UNDO delta records each indicating an earlier state of the column data, wherein each of the set of REDO delta records and the set of UNDO delta records is associated with a unique transaction identifier;
performing a delta compaction that causes the column data stored in the base data module to be updated to a particular later state based on applying one or more of the set of REDO delta records, wherein the delta compaction removes the one or more of the set of REDO delta records from the delta module to create a decreased set of REDO delta records and adds one or more new UNDO delta records that correspond to the one or more of the set of REDO delta records to create an increased set of UNDO delta records; and
using the scanner to provide the point-in-time snapshot of the dataset associated with the particular timepoint, wherein the point-in-time snapshot is configured to include at least the row, and wherein the scanner is configured to provide the point-in-time snapshot by:
selecting a subset of the increased set of UNDO delta records or the decreased set of REDO delta records according to a state of a MVCC manager instance captured by the scanner when instantiated at the particular timepoint, the state of the MVCC manager instance associating a particular transaction identifier with the particular timepoint;
copying the updated column data for the row from the base data module of the persistent storage into an output buffer of the scanner;
iteratively applying, to the output buffer, mutations indicated by the selected subset of the increased set of UNDO delta records or the decreased set of REDO delta records to change the updated column data to a particular committed state associated with the particular timepoint; and
providing the point-in-time snapshot via the output buffer of the scanner.

10. The computing system of claim 9 , wherein the process further comprises:
flushing the row to the persistent storage.

11. The computing system of claim 9 , wherein the UNDO delta records are inverse operations of one or more mutations applied to the column data.

12. The computing system of claim 11 , wherein the one or more mutations with reinsert operations are associated with the UNDO delta records with delete operations.

13. The computing system of claim 9 , wherein the one or more mutations with delete operations are associated with the UNDO delta records with insert operations.

14. The computing system of claim 9 , wherein the set of UNDO delta records are sorted by decreasing transaction timestamp.

15. A non-transitory computer-readable medium storing instructions that, when executed by a computing system, cause the computing syst

Assignees

• Cloudera Inc

Inventors

• Lipcon Todd

Classifications

• G06F16/23 Primary

  Updating · CPC title

• G06F16/2282

  Tablespace storage structures; Management thereof · CPC title

• G06F16/2246

  Trees, e.g. B+trees · CPC title

• G06F16/221 Primary

  Column-oriented storage; Management thereof · CPC title