Data storage method and system

Patent metadata

Field	Value
Publication number	US-11169987-B2
Application number	US-201916402700-A
Country	US
Kind code	B2
Filing date	May 3, 2019
Priority date	Oct 16, 2018
Publication date	Nov 9, 2021
Grant date	Nov 9, 2021

Abstract

An apparatus and method are disclosed. The method, which may be performed by one or more processors, may comprise receiving timestamp data representing a plurality of database transactions and dividing the timestamp data into a plurality of partitioning quanta (nPQ), each partitioning quantum (PQ) of the plurality of partitioning quanta representing a range of timestamps. Further, for each partitioning quantum (PQ) of the plurality of partitioning quanta (nPQ), the method may comprise allocating the timestamp data, such that sequentially adjacent timestamps are allocated to different partitions of a physical storage system for subsequent storage at the allocated partitions.

First claim

The invention claimed is:

1. A method, performed by one or more processors, the method comprising:
receiving timestamp data representing transaction start times of each of a plurality of database transactions;
dividing the timestamp data into a plurality of partitioning quanta (nPQ), each partitioning quantum (PQ) of the plurality of partitioning quanta representing a range of sequential start timestamps;
for each partitioning quantum (PQ) of the plurality of partitioning quanta (nPQ), allocating the timestamp data, such that sequentially adjacent start timestamps are allocated to different partitions of a plurality of partitions of one or more physical storage system for subsequent storage at the allocated partitions, wherein the different partitions are physically distinct partitions on a hard drive or solid state memory or physically different memory devices; and
storing values representing the timestamp data, or data associated with the timestamp data, in the allocated partitions of one or more physical storage systems, wherein the allocating comprises generating a data structure for each partitioning quantum (PQ) comprising N rows and M columns, each of the N rows corresponding to a respective one of the partitions (NP) and each of the M columns corresponding to a subset range of timestamps within each partitioning quantum (PQ), each of the N rows and M columns having respective row and column keys to enable access to the timestamp data, the row keys provided as:
LITTLE ENDIAN((Ts/PQ)*NP+(Ts % PQ) % NP),

where LITTLE ENDIAN means little endian binary format, Ts is a timestamp value and % means modulus.

2. The method of claim 1 , further comprising wherein the row and column keys enable access to the timestamp data, or data derived from the timestamp data, for access by means of a database management system.

3. The method of claim 2 , wherein the values allocated to the respective partitions of the one or more physical storage media represent a difference between database transaction commit time (Tc) and the database transaction start time (Ts).

4. The method of claim 2 , wherein the values allocated to the respective partitions of the one or more physical storage media represent database transaction commit times (Tc) corresponding to the same transaction as the database transaction start times (Ts).

5. The method of claim 4 , wherein the values are encoded using variable-length encoding.

6. The method of claim 1 , wherein timestamps within the range of timestamps are sequential timestamps.

7. The method of claim 1 , wherein the allocating further comprises defining one or more partitions of the plurality of partitions (NP) over which the timestamp data for each partitioning quantum (PQ) is to be allocated, wherein a number of partitions is less than a number of timestamps within each partitioning quantum (PQ).

8. The method of claim 1 , wherein the row keys are represented using little endian binary format.

9. The method of claim 1 , wherein the column keys are provided as:
((Ts % PQ)/NP),
where Ts is a timestamp value and % means modulus.

10. The method of claim 1 , wherein the row or column keys are encoded using variable-length encoding.

11. The method of claim 1 , wherein the timestamp data represents database transaction start times (Ts).

12. A computer program, optionally stored on a non-transitory computer readable medium program which, when executed by one or more processors of a data processing apparatus, causes the data processing apparatus to carry out a method comprising:
receiving timestamp data representing transaction start times of each of a plurality of database transactions;
dividing the timestamp data into a plurality of partitioning quanta (nPQ), each partitioning quantum (PQ) of the plurality of partitioning quanta representing a range of sequential start timestamps; and
for each partitioning quantum (PQ) of the plurality of partitioning quanta (nPQ), allocating the timestamp data, such that sequentially adjacent start timestamps are allocated to different partitions of one or more physical storage system for subsequent storage at the allocated partitions, wherein the different partitions are physically distinct partitions on a hard drive or solid state memory or physically different memory devices; and
storing values representing the timestamp data, or data associated with the timestamp data, in the allocated partitions of one or more physical storage media, wherein the allocating comprises generating a data structure for each partitioning quantum (PQ) comprising N rows and M columns, each of the N rows corresponding to a respective one of the partitions (NP) and each of the M columns corresponding to a subset range of timestamps within each partitioning quantum (PQ), each of the N rows and M columns having respective row and column keys to enable access to the timestamp data, the row keys are provided as:
LITTLE ENDIAN((Ts/PQ)*NP+(Ts % PQ) % NP),

where LITTLE ENDIAN means little endian binary format, Ts is a timestamp value and % means modulus.

13. The computer program of claim 12 , wherein the row and column keys enable access to the timestamp data, or data derived from the timestamp data, for access by means of a database management system.

14. The computer program of claim 13 , wherein the values allocated to the respective partitions of the one or more physical storage media represent a difference between database transaction commit time (Tc) and the database transaction start time (Ts).

15. The computer program of claim 12 , wherein the values allocated to the respective partitions of the one or more physical storage media represent database transaction commit times (Tc) corresponding to the same transaction as the database transaction start times (Ts).

16. Apparatus comprising one or more processors or special-purpose computing hardware, the apparatus configured to carry out a method comprising:
receiving timestamp data representing transaction start times of each of a plurality of database transactions;
dividing the timestamp data into a plurality of partitioning quanta (nPQ), each partitioning quantum (PQ) of the plurality of partitioning quanta representing a range of sequential start timestamps;
for each partitioning quantum (PQ) of the plurality of partitioning quanta (nPQ), allocating the timestamp data, such that sequentially adjacent start timestamps are allocated to different partitions of one or more physical storage system for subsequent storage at the allocated partitions, wherein the different partitions are physically distinct partitions on a hard drive or solid state memory or physically different memory devices; and
storing values representing the timestamp data, or data associated with the timestamp data, in the allocated partitions of one or more physical storage media, wherein the allocating comprises generating a data structure for each partitioning quantum (PQ) comprising N rows and M columns, each of the N rows corresponding to a respective one of the partitions (NP) and each of the M columns corresponding to a subset range of timestamps within each partitioning quantum (PQ), each of the N rows and M columns having respective row and column keys to enable access to the timestamp data, the column keys are provided as:
((Ts % PQ)/NP),

where Ts is a timestamp value and % means modulus.

17. The apparatus of claim 16 , wherein the row and column keys enable access to the timestamp data, or data derived from the timestamp data, for access by means of a database management system.

Assignees

• Palantir Technologies Inc

Inventors

• Kong Jeremy
• Maretic Grgur Petric
• Ozakdag Gokcan
• Baker James
• Van Wassenhove Sandor
• Petracca Thomas

Classifications

• G06F16/278

  Data partitioning, e.g. horizontal or vertical partitioning · CPC title

• G06F16/221

  Column-oriented storage; Management thereof · CPC title

• G06F16/2379 Primary

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

• G06F16/2322 Primary

  using timestamps · CPC title

• G06F16/27

  Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor · CPC title