Systems and methods of increasing database access concurrency using granular timestamps

• US 9,747,310 B2
• Filed: 06/04/2013
• Issued: 08/29/2017
• Est. Priority Date: 06/04/2012
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Hsieh, Wilson Cheng-Yi, Lloyd, Alexander, Veach, Eric Hugh
• Primary Examiner(s): Beausoliel, Jr., Robert
• Assistant Examiner(s): Pham, Michael
• Application Number:
  US13/909,928
• Publication Number:
  US 20140006458A1
• Time in Patent Office: 1,547 Days
• Field of Search: 707758
• CPC Class Codes: G06F 16/211 Schema design and management
• CPC Class Codes: G06F 16/2322 using timestamps
• CPC Class Codes: G06F 16/2329 using versioning

Abstract

A method reads and writes data from a database table. Each row in the table has a primary key and multiple non-key columns. Each non-key column has one or more column values, and each column value has an associated timestamp that identifies when the column value was stored. The timestamps associated with the column values in each non-key column provide a unique order for the column values. A read transaction is initiated to read from a first non-key column of a first row. A write transaction is in progress that is updating a second non-key column of the first row, where the second non-key column is distinct from the first non-key column. The write transaction holds a lock on the second non-key column of the first row. The method concurrently reads the data from the first non-key column and writes a new column value to the second non-key column.

Claims

1. A method of reading and writing data from a database table comprising:

initiating a read transaction to read from a first non-key column of a first row in the database table, the database table having a plurality of rows, each row comprising a primary key and a plurality of non-key columns, wherein;

each non-key column comprises one or more column values,

each column value has a respective timestamp that identifies when the respective column value was stored, and

the respective timestamps of the column values in each non-key column provide a unique order for the column values that comprise the non-key column,

the initiating including;

determining that a write transaction is in progress that is updating a second non-key column of the first row in the database table, wherein the second non-key column is distinct from the first non-key column and the write transaction that is updating the second non-key column holds a lock on the second non-key column of the first row of the database table, and

determining that no lock is held on the first non-key column of the first row; and

in response to determining that no lock is held on the first non-key column of the first row, concurrently reading the data from the first non-key column and writing a new column value to the second non-key column;

wherein each non-key column further comprises a last-write timestamp that indicates when the last write occurred for the respective non-key column;

wherein initiating the read transaction further comprises selecting a read timestamp based in part on the last-write timestamp of the first non-key column; and

wherein reading the data from the first non-key column comprises selecting a column value from the first non-key column corresponding to the read timestamp.

2. The method of claim 1, wherein initiating the read transaction further comprises selecting a read timestamp that is:

greater than the last-write timestamp of the first non-key column; and

less than a value designated as the minimum next new write timestamp for the database table.

3. The method of claim 2, wherein the read transaction includes reading a plurality of non-key columns, with each of the plurality of non-key columns distinct from the second non-key column, and wherein the read timestamp is selected that is greater than the last-write timestamp for each of the plurality of non-key columns.

4. The method of claim 1, the method further comprising storing, for each non-key column of each row, the last-write timestamp.

5. The method of claim 4, wherein initiating the read transaction further comprises selecting a read timestamp that is:

greater than the last-write timestamp of the first non-key column; and

less than a value designated as the minimum next new write timestamp for the database table.

6. The method of claim 5, wherein the read transaction includes reading a plurality of non-key columns, with each of the plurality of non-key columns distinct from the second non-key column, and wherein the read timestamp is selected that is greater than the last-write timestamp for each of the plurality of non-key columns.

7. The method of claim 1, wherein each row of the database table comprises one or more shards, and the shards for each row form a partition of the non-key columns in the respective row.

8. The method of claim 7, wherein the first non-key column and second non-key column are in the same shard of the first row.

9. The method of claim 1, wherein:

one or more non-key columns of the first row in the database table comprise column values that are subtables;

each subtable comprises a plurality of subrows;

each subrow comprises a subkey and one or more non-key subcolumns;

each non-key subcolumn comprises one or more subcolumn values;

each subcolumn value has a respective subtimestamp that identifies when the respective subcolumn value was stored; and

the respective subtimestamps of the subcolumn values in each non-key subcolumn provide a unique order for the subcolumn values that comprise the non-key subcolumn.

10. A database management system, comprising one or more server computers, each server computer including:

one or more processors;

memory;

a database table stored in the memory, the database table having a plurality of rows, each row comprising a primary key and a plurality of non-key columns, wherein;

each non-key column comprises one or more column values,

each column value has a respective timestamp that identifies when the associated column value was stored, and

the respective timestamps of the column values in each non-key column provide a unique order for the column values that comprise the non-key column; and

one or more programs stored in the memory for execution by the one or more processors, the one or more programs comprising instructions for;

initiating a read transaction to read from a first non-key column of a first row in the database table, including;

determining that a write transaction is in progress that is updating a second non-key column of the first row in the database table, wherein the second non-key column is distinct from the first non-key column and the write transaction that is updating the second non-key column holds a lock on the second non-key column of the first row of the database table, and

determining that no lock is held on the first non-key column of the first row; and

in response to determining that no lock is held on the first non-key column of the first row, concurrently reading the data from the first non-key column and writing a new column value to the second non-key column;

wherein each non-key column further comprises a last-write timestamp that indicates when the last write occurred for the respective non-key column;

wherein initiating the read transaction further comprises selecting a read timestamp based in part on the last-write timestamp of the first non-key column; and

wherein reading the data from the first non-key column comprises selecting a column value from the first non-key column corresponding to the read timestamp.

11. The database management system of claim 10, wherein the instructions for initiating the read transaction further comprise instructions for selecting a read timestamp that is:

greater than the last-write timestamp of the first non-key column; and

less than a value designated as the minimum next new write timestamp for the database table.

12. The database management system of claim 10, the one or more programs further comprising instructions for storing, for each non-key column of each row, the last-write timestamp.

13. The database management system of claim 12, wherein the instructions for initiating the read transaction further comprise instructions for selecting a read timestamp that is:

greater than the last-write timestamp of the first non-key column; and

less than a value designated as the minimum next new write timestamp for the database table.

14. A non-transitory computer readable storage medium storing one or more programs configured for execution by one or more server computers, each server computer having one or more processors and memory storing one or more programs for execution by the one or more processors, the one or more programs comprising instructions for:

maintaining a database table, the database table having a plurality of rows, each row comprising a primary key and a plurality of non-key columns, wherein;

each non-key column comprises one or more column values,

each column value has a respective timestamp that identifies when the associated column value was stored, and

the respective timestamps of the column values in each non-key column provide a unique order for the column values that comprise the non-key column;

initiating a read transaction to read from a first non-key column of a first row in the database table, including;

determining that a write transaction is in progress that is updating a second non-key column of the first row in the database table, wherein the second non-key column is distinct from the first non-key column and the write transaction that is updating the second non-key column holds a lock on the second non-key column of the first row of the database table, and

determining that no lock is held on the first non-key column of the first row; and

in response to determining that no lock is held on the first non-key column of the first row, concurrently reading the data from the first non-key column and writing a new column value to the second non-key column;

wherein each non-key column further comprises a last-write timestamp that indicates when the last write occurred for the respective non-key column;

wherein initiating the read transaction further comprises selecting a read timestamp based in part on the last-write timestamp of the first non-key column; and

wherein reading the data from the first non-key column comprises selecting a column value from the first non-key column corresponding to the read timestamp.

15. The non-transitory computer readable storage medium of claim 14, wherein the instructions for initiating the read transaction further comprise instructions for selecting a read timestamp that is:

greater than the last-write timestamp of the first non-key column; and

less than a value designated as the minimum next new write timestamp for the database table.

16. The non-transitory computer readable storage medium of claim 14, the one or more programs further comprising instructions for storing, for each non-key column of each row, the last-write timestamp.

17. The non-transitory computer readable storage medium of claim 16, wherein the instructions for initiating the read transaction further comprise instructions for selecting a read timestamp that is:

greater than the last-write timestamp of the first non-key column; and

less than a value designated as the minimum next new write timestamp for the database table.