Large scale data storage in sparse tables

• US 20070033354A1
• Filed: 08/05/2005
• Published: 02/08/2007
• Est. Priority Date: 08/05/2005
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Ghemawat, Sanjay, Dean, Jeffrey, Burrows, Michael, Fikes, Andrew, Wallach, Deborah, Hsieh, Wilson, Chang, Fay
• Granted Patent: US 7,428,524 B2
• Time in Patent Office: Days
• US Class Current: 711/156
• CPC Class Codes: G06F 16/125 characterised by the use of retention policies retention policies for HSM systems G06F16/185
• CPC Class Codes: G06F 16/184 implemented as replicated file system
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99939 Privileged access
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

Each of a plurality of data items is stored in a table data structure. A row identifier and column identifier are associated with each respective data item, and each respective item is stored at a logical location in the table data structure specified by its row identifier and column identifier. A plurality of data items is stored in a cell of the table data structure, and a timestamp is associated with each of the plurality of data items stored in the cell. Each of the data items stored in the cell has the same row identifier, the same column identifier, and a distinct timestamp. In some embodiments, each row identifier is a string of arbitrary length and arbitrary value. Similarly, in some embodiments each column identifier is a string of arbitrary length and arbitrary value.

Claims

1. A method of storing data, comprising:

storing each of a plurality of data items in a table data structure, including associating a row identifier and column identifier with each respective data item and storing the respective item at a logical location in the table data structure specified by the row identifier and column identifier; and

storing in a cell of the table data structure a plurality of data items, and associating a timestamp with each of the plurality of data items stored in the cell, each of the plurality of data items stored in the cell having a same row identifier, a same column identifier, and a distinct timestamp.

2. The method of claim 1, wherein associating a row identifier with a respective data item includes associating a row identifier string with the respective data item, the row identifier string comprising a string of arbitrary length and arbitrary value.

3. The method of claim 1, wherein associating a row identifier and column identifier with a respective data item includes associating a row identifier string and column identifier string with the respective data item, the row identifier string and column identifier string each comprising a respective string of arbitrary length and arbitrary value.

4. The method of claim 1, including associating a first set of data access permissions with a first group of columns in the table data structure, and associating a second set of data access permissions with a second group of columns in the table data structure, wherein the first and second groups of columns are non-overlapping groups of columns and the first and second sets of data access permissions differ with respect to the data access permissions granted to at least one user or group of users.

5. The method of claim 4, including associating a data retention rule with a group of columns of the table data structure, the group of columns including the cell, wherein the data retention rule specifies that data items stored in cells in the group of columns may be deleted when their age, as determined by the timestamps associated with the data items, exceeds an age specified by the data retention rule.

6. The method of claim 5, including automatically deleting data items in the group of columns whose age, as determined by the timestamps associated with the data items, exceeds the age specified by the data retention rule.

7. The method of claim 1, including associating a data retention rule with a group of columns of the table data structure, the group of columns including the cell, wherein the data retention rule specifies that oldest data items stored in each respective cell in the group of columns may be deleted when the number of data items stored in the respective cell in the group of columns exceeds a number specified by the data retention rule.

8. The method of claim 7, including automatically deleting one or more oldest data items in the group of columns from cells that have more data items than the number specified by the data retention rule.

9. The method of claim 1, wherein the table data structure includes a plurality of tablets, comprising distinct non-overlapping groups of rows of the table data structure, and wherein the table data structure includes a plurality of locality groups, each including a distinct non-overlapping subset of the columns of the table data structure.

10. The method of claim 9, including storing the tablets in a plurality of distinct servers, including storing for each tablet a plurality of files corresponding to the plurality of locality groups.

11. A system for storing data, comprising:

a set of interconnected computers each having storage;

a table data structure, the table data structure including a plurality of rows and columns for storing data, wherein the rows have associated row identifiers, the columns have associated column identifiers, and each of a plurality of data items is stored in the table data structure at a respective cell in the table data structure specified by a respective row identifier and respective column identifier;

wherein a respective cell in the table stores a plurality of data items, each of the data items stored in the cell having associated therewith a respective timestamp, each of the plurality of data items stored in the cell having a same row identifier, a same column identifier, and a distinct timestamp; and

wherein the table data structure is stored within the storage of one or more of the set of interconnected computers.

12. The system of claim 11, wherein the table data structure is stored within the storage of two or more of the set of interconnected computers.

13. The system of claim 11, wherein each respective cell of the table data structure has a row identifier comprising a string of arbitrary length and arbitrary value.

14. The system of claim 13, wherein each respective cell of the table data structure has a column identifier comprising a string of arbitrary length and arbitrary value.

15. The system of claim 11, wherein the table data structure includes a first set of data access permissions associated with a first group of columns in the table data structure, and a second set of data access permissions associated with a second group of columns in the table data structure, wherein the first and second groups of columns are non-overlapping groups of columns and the first and second sets of data access permissions differ with respect to the data access permissions granted to at least one user or group of users.

16. The system of claim 11, wherein the table data structure includes a data retention rule associated with a group of columns of the table data structure, wherein the data retention rule specifies that data items stored in cells in the group of columns may be deleted when their age, as determined by the timestamps associated with the data items, exceeds an age specified by the data retention rule.

17. The system of claim 16, including executable instructions for automatically deleting data items in the group of columns whose age, as determined by the timestamps associated with the data items, exceeds the age specified by the data retention rule.

18. The system of claim 11, wherein the table data structure includes a data retention rule associated with a group of columns of the table data structure, wherein the data retention rule specifies that oldest data items stored in each respective cell in the group of columns may be deleted when the number of data items stored in the respective cell in the group of columns exceeds a number specified by the data retention rule.

19. The system of claim 18, including executable instructions for automatically deleting one or more oldest data items in the group of columns from cells that have more data items than the number specified by the data retention rule.

20. The system of claim 11, wherein the table data structure includes a plurality of tablets, comprising distinct non-overlapping groups of rows of the table data structure, and wherein the table data structure includes a plurality of locality groups, each including a distinct non-overlapping subset of the columns of the table data structure.

21. The system of claim 20, wherein the tablets are stored in the storage of two or more the interconnected computers, including storing for each tablet a plurality of files corresponding to the plurality of locality groups.