Transactional version sets

Patent metadata

Field	Value
Publication number	US-11599514-B1
Application number	US-202117216326-A
Country	US
Kind code	B1
Filing date	Mar 29, 2021
Priority date	Mar 29, 2021
Publication date	Mar 7, 2023
Grant date	Mar 7, 2023

Abstract

Techniques for implementing systems using transactional version sets are described. Transactional version sets or t-sets include a collection of elements, each having a collection of metadata. A t-set is transactional in that a sequence of updates to one or more t-sets are made within an atomic transaction. A t-set is versioned since each committed transaction that updates it produces a new timestamped version that can be accessed via time-travel queries.

First claim

What is claimed is:

1. A computer-implemented method comprising:
receiving, at a transactional access manager within a multi-tenant cloud provider network, a command to begin an atomic transaction involving one or more tables of a data catalog for a data warehouse backed at least in part by an object storage service of the cloud provider network;
generating, based on the command to begin the atomic transaction, a new version node in a version history data structure of a transactional version set corresponding to a table of the data catalog, the version history data structure including at least one other version node corresponding to a previous version of the table, the new version node storing a transaction identifier and an identifier of the other version node, wherein the transactional version set further includes set data structures each being identified by one of the version nodes and each having a collection of elements corresponding to data objects existing in the table;
receiving, at a first server of the transactional access manager, a command to add an element to the transactional version set as part of the transaction, wherein the element comprises metadata associated with a data object stored by the object storage service;
inserting, by the first server based on the command to add the element, the element within a set data structure identified by the new version node in the version history data structure;
receiving, at a second server of the transactional access manager, a command to commit the transaction;
determining, by the second server, that a conflict does not exist for the transaction based at least in part on an analysis of metadata stored by the version history data structure;
generating a commit time for the transaction based on identifying a first commit time of a most recent transaction that wrote to the table and identifying a start time of another most recent transaction that has read data from the table, wherein the generating comprises selecting the commit time to be larger than both the first commit time and the start time; and
atomically committing the transaction by the second server, wherein the committing includes updating the version history data structure based at least in part on use of the commit time, and wherein the first server and second server are unsynchronized with each other.

2. The computer-implemented method of claim 1 , wherein determining that the conflict does not exist includes:
comparing a current commit time associated with the transaction to one or more commit times from the metadata associated with the version history data structure, wherein the one or more commit times includes at least one of:
a set commit time comprising a time of a latest commit that added an element to or removed an element from the transactional version set; or
a membership commit time comprising a time of a latest commit that updated the transactional version set in a manner different than adding or removing an element.

3. The computer-implemented method of claim 1 , further comprising:
receiving a query to be executed using the transactional version set, wherein the query includes or is associated with a time value indicating a point in time of the transactional version set that the query is to be executed using;
identifying, based on the time value, a second version node within the version history data structure as being associated with a second set data structure that represents the point in time of the transactional version set; and
executing the query using a second set data structure identified by the second version node.

4. A computer-implemented method comprising:
receiving a command to begin an atomic transaction involving a catalog for a table of a data lake as represented by a transactional version set, the transactional version set including a version history data structure storing version nodes that each point to a corresponding set data structure;
generating, based on the receiving of the command to begin the transaction, a new version node in the version history data structure, wherein the new version node includes references to a new set data structure and to a previous version node corresponding to a previous version of the transactional version set;
receiving, at a first server, a command to add an element to the transactional version set as part of the transaction;
inserting, by the first server based on the receiving of the command to add the element, the element within the new set data structure referenced by the new version node;
receiving, at a second server, a command to commit the transaction;
determining, by the second server based on the receiving of the command to commit the transaction, that a conflict does not exist for the transaction based at least in part on an analysis of metadata stored by the version history data structure;
generating a commit time for the transaction based on identifying a first commit time of a most recent transaction that wrote to the transactional version set and identifying a start time of another most recent transaction that has read data from the transactional version set, wherein the generating comprises selecting the commit time to be larger than both the first commit time and the start time; and
atomically committing the transaction by the second server, wherein the committing includes updating the version history data structure based at least in part on use of the commit time, and wherein the first server and second server are unsynchronized with each other.

5. The computer-implemented method of claim 4 , wherein the first commit time and the start time are recorded in a head version node of the version history data structure.

6. The computer-implemented method of claim 4 , wherein
determining that the conflict does not exist includes:
comparing a current commit time associated with the transaction to one or more commit times from the metadata of the version history data structure, wherein the one or more commit times include at least one of:
a set commit time comprising a time of a latest commit that added an element to or removed an element from the transactional version set; or
a membership commit time comprising a time of a latest commit that updated the transactional version set in a manner different than adding or removing an element.

7. The computer-implemented method of claim 4 , wherein:
generating the new version node in the version history data structure associated with the transactional version set includes marking the new version node as an uncommitted version within the version history data structure; and
committing the transaction includes updating the new version node from being marked as the uncommitted version into being a committed version within the version history data structure.

8. The computer-implemented method of claim 4 , further comprising:
receiving a query to be executed using the transactional version set, wherein the query includes or is associated with a time value indicating a point in time of the transactional version set that the query is to be executed using;
identifying, based on the time value, a second version node within the version history data structure as being associated with a second set data structure that represents the point in time of the transactional version set; and
executing the query using a second set data structure identified by the second version node.

9. The computer-implemented method of claim 4 , wherein the first server and the second server are implemented by different computing devices and utilize independent clocks that are not synchronized with each other.

10. The computer-implemented method of claim 4 , wherein the transactio

Assignees

• Amazon Tech Inc

Inventors

• Agrawal Vinay
• Li Bohou
• Malik Vikas
• Poddar Tushar
• Prabhakaran Vijayan
• Punhani Mukesh
• Shah Mehul A
• Sowell Benjamin
• Terry Douglas Brian

Classifications

• G06F16/2379

  Updates performed during online database operations; commit processing · CPC title

• G06F16/2365 Primary

  Ensuring data consistency and integrity · CPC title

• G06F16/219 Primary

  Managing data history or versioning (querying versioned data G06F16/2474; querying temporal data G06F16/2477) · CPC title

• G06F16/2477

  Temporal data queries · CPC title

• G06F16/2282

  Tablespace storage structures; Management thereof · CPC title