Methods and apparatus for efficiently implementing a fast-copyable database

• US 10,489,385 B2
• Filed: 10/31/2018
• Issued: 11/26/2019
• Est. Priority Date: 11/01/2017
• Status: Active Grant

• Current Assignee: Hedera Hashgraph LLC
• Original Assignee: Swirlds, Inc.
• Inventors: Baird, III, Leemon C., Harmon, Mance
• Primary Examiner(s): Peng, Huawen A
• Application Number:
  US16/176,125
• Publication Number:
  US 20190129893A1
• Time in Patent Office: 391 Days
• CPC Class Codes: G06F 16/1873 Versioning file systems, temporal file systems, e.g. file system supporting different historic versions of files
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 16/2471 Distributed queries
• CPC Class Codes: G06F 16/2474 Sequence data queries, e.g. querying versioned data
• CPC Class Codes: G06F 16/90335 Query processing
• CPC Class Codes: H04L 9/30 Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy

Abstract

A fast-copyable database apparatus includes a processor and a memory in electronic communication with the processor. The memory stores a database table with multiple records each having a compound key including a version identifier. The memory also stores instructions executable to cause the processor to generate a first virtual clone of the database table and a second virtual clone of the database table, receive a query at the first virtual clone, and modify the query so that it includes a version identifier of the first virtual clone. The processor can query the database table using the modified query to generate a response based in part on each record from the set of records having a version identifier associated with an ancestral path of the version identifier of the first virtual clone, and send the response. Each compound key includes a version identifier and a data portion.

Claims

1. An apparatus, comprising:

a processor; and

a memory in electronic communication with the processor, the memory storing a database table including a plurality of records, each record from the plurality of records having a compound key including a version identifier,

the memory including instructions executable to cause the processor to;

generate a first virtual clone of the database table and a second virtual clone of the database table;

receive a query at the first virtual clone, the query not including a version identifier associated with the first virtual clone;

modify the query, based on receiving the query at the first virtual clone, by adding the version identifier associated with the first virtual clone to the query to define a modified query;

query the database table using the modified query to generate a response including a set of records from the plurality of records based on;

(1) each record from the set of records satisfying the query; and

(2) each record from the set of records having a version identifier associated with an ancestral path of the version identifier associated with the first virtual clone;

send the response including the set of records as a response to the query;

the compound key for each record from the plurality of records including the version identifier for that compound key and a data portion, the plurality of records configured such that only one of;

(1) a compound key including a value of the data portion and the version identifier associated with the first virtual clone;

or (2) a compound key including the value of the data portion and the version identifier associated with the second virtual clone, is present in the database table at any given time.

2. The apparatus of claim 1, wherein the memory further includes instructions executable to cause the processor to:

add, in response to an insert instruction received via the first virtual clone, a record to the database table, the record including data and a compound key having the version identifier associated with the first virtual clone such that;

(1) a query subsequently received at the first virtual clone and referencing the data returns the record; and

(2) a query subsequently received at a third virtual clone for the data does not return the record.

3. The apparatus of claim 1, wherein the instructions are further executable to cause the processor to:

add, in response to an instruction to update a value of a field of a first record of the database table from a first value to a second value and received via a third virtual clone, a second record to the database table, the second record including the second value and a compound key having a version identifier associated with the third virtual clone; and

modify, in response to the instruction to update the value of the field of the first record, a compound key of the first record to not include the version identifier associated with the third virtual clone such that;

a query subsequently received at the third virtual clone and referencing the field returns the second record, and

a query received at the first virtual clone and referencing the field returns the first record.

4. The apparatus of claim 1, wherein the instructions are further executable to cause the processor to:

modify, in response to an instruction to delete a record from the plurality of records and received via a third virtual clone, the version identifier of the compound key of the record to not include a version identifier associated with the third virtual clone such that;

a query for the record, subsequently received at the third virtual clone, does not return the record, and

a query for the record, subsequently received at the first virtual clone, returns the record.

5. The apparatus of claim 1, wherein the response is a first response, and the modified query is a first modified query, the instructions further executable to cause the processor to:

generate a second modified query including a version identifier of the second virtual clone if the first response is null, the second virtual clone being an ancestor to the first virtual clone;

query the database table using the second modified query to generate a second response including a set of records from the plurality of records based on;

(1) each record from the set of records of the second response satisfying the second modified query; and

(2) each record from the set of records of the second response having a version identifier associated with an ancestral path of the version identifier of the second virtual clone; and

send the second response including the set of records as a response to the query.

6. The apparatus of claim 1, wherein the instructions are further executable to cause the processor to store, in the memory, an indication that the first virtual clone is a descendant of the second virtual clone.

7. The apparatus of claim 1, wherein the instructions are further executable to cause the processor to generate a third virtual clone of the database table, the third virtual clone being neither an ancestor nor a descendant of the first virtual clone, the plurality of records including a record having a compound key including the value of the data portion and a version identifier associated with the third virtual clone.

8. A method, comprising:

generating, via a processor, a first virtual clone of a database table and a second virtual clone of the database table, the database table including a plurality of records, each record from the plurality of records having a compound key including a version identifier;

receiving, via the processor, a query at the first virtual clone, the query not including a version identifier associated with the first virtual clone;

modifying the query, via the processor and based on receiving the query at the first virtual clone, by adding the version identifier associated with the first virtual clone to the query to define a modified query;

querying, via the processor, the database table using the modified query to generate a response including a set of records from the plurality of records based on;

(1) each record from the set of records satisfying the query; and

(2) each record from the set of records having a version identifier associated with an ancestral path of the version identifier associated with the first virtual clone; and

sending, via the processor, the response including the set of records as a response to the query,

the compound key for each record from the plurality of records including the version identifier for that compound key and a data portion, the plurality of records configured such that only one of;

(1) a compound key including a value of the data portion and the version identifier associated with the first virtual clone;

or (2) a compound key including the value of the data portion and the version identifier associated with the second virtual clone, is present in the database table at any given time.

9. The method of claim 8, further comprising:

adding, in response to an insert instruction received via the first virtual clone, a record to the database table, the record including data and a compound key having the version identifier associated with the first virtual clone such that;

(1) a query subsequently received at the first virtual clone and referencing the data returns the record; and

(2) a query subsequently received at a third virtual clone for the data does not return the record.

10. The method of claim 8, further comprising:

adding, in response to an instruction to update a value of a field of a first record of the database table from a first value to a second value and received via a third virtual clone, a second record to the database table, the second record including the second value and a compound key having a version identifier associated with the third virtual clone; and

modifying, in response to the instruction to update the value of the field of the first record, a compound key of the first record to not include the version identifier associated with the third virtual clone such that;

a query subsequently received at the third virtual clone and referencing the field returns the second record, and

a query received at the first virtual clone and referencing the field returns the first record.

11. The method of claim 8, further comprising:

modifying, in response to an instruction to delete a record from the plurality of records and received via a third virtual clone, the version identifier of the compound key of the record to not include a version identifier associated with the third virtual clone such that;

a query for the record, subsequently received at the third virtual clone, does not return the record, and

a query for the record, subsequently received at the first virtual clone, returns the record.

12. The method of claim 8, wherein the response is a first response, and the modified query is a first modified query, the method further comprising:

generating a second modified query including a version identifier of the second virtual clone if the first response is null, the second virtual clone being an ancestor to the first virtual clone;

querying the database table using the second modified query to generate a second response including a set of records from the plurality of records based on;

(1) each record from the set of records of the second response satisfying the second modified query; and

(2) each record from the set of records of the second response having a version identifier associated with an ancestral path of the version identifier of the second virtual clone; and

sending the second response including the set of records as a response to the query.

13. The method of claim 8, further comprising storing an indication that the first virtual clone is a descendant of the second virtual clone.

14. The method of claim 8, further comprising generating a third virtual clone of the database table, the third virtual clone being neither an ancestor nor a descendant of the first virtual clone, the plurality of records including a record having a compound key including the value of the data portion and a version identifier associated with the third virtual clone.

15. A non-transitory, tangible processor-readable medium comprising processor-executable instructions for:

generating, via a processor, a first virtual clone of a database table and a second virtual clone of the database table, the database table including a plurality of records, each record from the plurality of records having a compound key including a version identifier;

receiving, via the processor, a query at the first virtual clone, the query not including a version identifier associated with the first virtual clone;

modifying the query, via the processor and based on receiving the query at the first virtual clone, by adding the version identifier associated with the first virtual clone to the query to define a modified query;

querying, via the processor, the database table using the modified query to generate a response including a set of records from the plurality of records based on;

(1) each record from the set of records satisfying the query; and

(2) each record from the set of records having a version identifier associated with an ancestral path of the version identifier associated with the first virtual clone; and

sending, via the processor, the response including the set of records as a response to the query,

the compound key for each record from the plurality of records including the version identifier for that compound key and a data portion, the plurality of records configured such that only one of;

(1) a compound key including a value of the data portion and the version identifier associated with the first virtual clone;

or (2) a compound key including the value of the data portion and the version identifier associated with the second virtual clone, is present in the database table at any given time.

16. The non-transitory, tangible processor-readable medium of claim 15, further comprising processor-executable instructions for:

adding, in response to an insert instruction received via the first virtual clone, a record to the database table, the record including data and a compound key having a version identifier associated with the first virtual clone such that;

(1) a query subsequently received at the first virtual clone and referencing the data returns the record; and

(2) a query subsequently received at a third virtual clone for the data does not return the record.

17. The non-transitory, tangible processor-readable medium of claim 15, further comprising processor-executable instructions for:

adding, in response to an instruction to update a value of a field of a first record of the database table from a first value to a second value and received via a third virtual clone, a second record to the database table, the second record including the second value and a compound key having a version identifier associated with the third virtual clone; and

modifying, in response to the instruction to update the value of the field of the first record, a compound key of the first record to not include the version identifier associated with the third virtual clone such that;

a query subsequently received at the third virtual clone and referencing the field returns the second record, and

a query received at the first virtual clone and referencing the field returns the first record.

18. The non-transitory, tangible processor-readable medium of claim 15, further comprising processor-executable instructions for:

modifying, in response to an instruction to delete a record from the plurality of records and received via a third virtual clone, the version identifier of the compound key of the record to not include a version identifier associated with the third virtual clone such that;

a query for the record, subsequently received at the third virtual clone, does not return the record, and

a query for the record, subsequently received at the first virtual clone, returns the record.

19. The non-transitory, tangible processor-readable medium of claim 15, wherein the response is a first response, and the modified query is a first modified query, the processor-readable medium further comprising processor-executable instructions for:

generating a second modified query including a version identifier of the second virtual clone if the first response is null, the second virtual clone being an ancestor to the first virtual clone;

querying the database table using the second modified query to generate a second response including a set of records from the plurality of records based on;

(1) each record from the set of records of the second response satisfying the second modified query; and

(2) each record from the set of records of the second response having a version identifier associated with an ancestral path of the version identifier of the second virtual clone; and

sending the second response including the set of records as a response to the query.

20. The non-transitory, tangible processor-readable medium of claim 15, further comprising processor-executable instructions for storing an indication that the first virtual clone is a descendant of the second virtual clone.

21. The non-transitory, tangible processor-readable medium of claim 15, further comprising processor-executable instructions for:

generating a third virtual clone of the database table, the third virtual clone being neither an ancestor nor a descendant of the first virtual clone, the plurality of records including a record having a compound key including the value of the data portion and a he version identifier associated with the third virtual clone.