Partition-based index management in hadoop-like data stores

• US 9,959,306 B2
• Filed: 06/12/2015
• Issued: 05/01/2018
• Est. Priority Date: 06/12/2015
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Chang, Yuan-Chi, Fong, Liana L., Tan, Wei
• Primary Examiner(s): Ly, Anh
• Application Number:
  US14/737,586
• Publication Number:
  US 20160364424A1
• Time in Patent Office: 1,054 Days
• CPC Class Codes: G06F 16/13 File access structures, e.g. distributed indices arrangements of input from, or output to, record carriers G06F3/06
• CPC Class Codes: G06F 16/21 Design, administration or maintenance of databases
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/2272 Management thereof
• CPC Class Codes: G06F 16/2282 Tablespace storage structures; Management thereof
• CPC Class Codes: G06F 16/2379 Updates performed during online database operations; commit processing
• CPC Class Codes: G06F 16/2386 Bulk updating operations data conversion details G06F16/258
• CPC Class Codes: G06F 16/278 Data partitioning, e.g. horizontal or vertical partitioning
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP
• CPC Class Codes: G06F 16/901 Indexing; Data structures therefor; Storage structures for retrieval from the web G06F16/951

Abstract

A method for processing a dataset in a partitioned distributed storage system having data stored in a base table and an index stored in an index table, may include receiving base and index table metadata from the partitioned distributed storage system, where the base and index table metadata includes respective table partition information. The method may further include partitioning the dataset into a set of base-delta files according to the base table metadata, and generating a set of index-delta files corresponding with the base-delta files according to the index table metadata. The method may additionally include updating the partitioned distributed storage system with the set of base-delta and the set of index-delta files, where a first update of the base table is synchronous with a second update of the index table.

Claims

1. A method for maintaining an index of a processing a dataset in a partitioned distributed storage system after a batch update of a dataset, the partitioned distributed storage system having data stored in a base table and an index stored in an index table, comprising:

locking the base table and the index table to prevent external update operations;

receiving base and index table metadata from the partitioned distributed storage system, wherein the base table metadata and the index table metadata include respective base table partition information and index table partition information;

partitioning the dataset into a set of base-delta files according to the base table metadata;

generating a set of index-delta files corresponding with the base-delta files according to the index table metadata;

updating the partitioned distributed storage system with the set of base-delta files and the set of index-delta files,

wherein a first update of the base table is synchronous with a second update of the index table; and

unlocking, subsequent to the update, the base table and the index table.

2. The method of claim 1, wherein the partitioning comprises:

determining from the base table metadata a partitioning criteria; and

allocating the dataset to the set of base-delta files according to a partitioning criteria.

3. The method of claim 1, wherein the generating comprises:

determining from the index table metadata a criteria for generating index-deltas from a set of base table deltas,

wherein the set of base table deltas include the dataset as allocated to the base-delta files, and the set of index-deltas include references to the set of base table deltas;

generating the index-deltas according to the criteria for generating index-deltas; and

determining from the index table metadata a partitioning criteria for allocating the set of index deltas to the set of index-delta files;

allocating the set of index-deltas to the set of index-delta files according to the partitioning criteria.

4. The method of claim 1, wherein the updating comprises:

merging the set of base-delta and the set of index-delta files into a respective one or more corresponding partitions of the base and index tables; and

updating the base and index table metadata in the partitioned distributed storage system.

5. The method of claim 4, wherein the base table is updated in parallel with the index table.

6. The method of claim 4, wherein a plurality of partitioned base tables and index tables are updated in parallel.

7. The method of claim 1, wherein the updating comprises:

deleting the set of base-delta files and set of index-delta files in a respective one or more corresponding partitions of the base and index tables; and

updating the base table metadata and the index table metadata in the partitioned distributed storage system.

8. The method of claim 7, wherein the deleting comprises:

determining whether the set of base-delta files have been merged with respective partitions of the base table;

deleting, in response to determining that the set of base-delta files have not been merged, the set of base-delta files from the respective partitions of the base table; and

generating, in response to determining that the set of base-delta files have been merged, delete markers files corresponding with the set of base-delta files in respective partitions of the base table.

9. The method of claim 7, wherein the deleting comprises:

determining whether the set of index-delta files have been merged with respective partitions of the index table;

deleting, in response to determining that the set of index-delta files have not been merged, the set of index-delta files from the respective partitions of the index table; and

generating, in response to determining that the set of index-delta files have been merged, delete markers files corresponding with the set of index-delta files in respective partitions of the index table.

10. The method of claim 1, wherein the partitioned distributed storage system is a Hadoop-like distributed file system.

11. A system for maintaining an index of a partitioned distributed storage system having data stored in a base table and an index stored in an index table, comprising:

one or more computing nodes having a memory and a hardware processor; and

a non-transitory computer readable storage medium of the one or more computing nodes having program instructions embodied therewith, the program instructions executable by the processor to cause the system to;

lock the base table and the index table to prevent external update operations;

receive base and index table metadata from the partitioned distributed storage system, wherein the base table metadata and the index table metadata include respective base table partition information and index table partition information;

partition the dataset into a set of base-delta files according to the base table metadata;

generate a set of index-delta files corresponding with the base-delta files according to the index table metadata; and

update the partitioned distributed storage system with the set of base-delta files and the set of index-delta files,

wherein a first update of the base table is synchronous with a second update of the index table; and

unlock, subsequent to the update, the base table and the index table.

12. The system of claim 11, wherein the program instructions executable by the processor further causes the system to:

determine from the base table metadata a partitioning criteria; and

allocate the dataset to the set of base-delta files according to a partitioning criteria.

13. The system of claim 11, wherein the program instructions executable by the processor further causes the system to:

determine from the index table metadata a criteria for generating index-deltas from a set of base table deltas,

wherein the set of base table deltas include the dataset as allocated to the base-delta files, and the set of index-deltas include references to the set of base table deltas;

generate the index-deltas according to the criteria for generating index-deltas; and

determine from the index table metadata a partitioning criteria for allocating the set of index deltas to the set of index-delta files; and

allocating the set of index-deltas to the set of index-delta files according to the partitioning criteria.

14. The system of claim 11, wherein the program instructions executable by the processor further causes the system to:

merge the set of base-delta files and the set of index-delta files into a respective one or more corresponding partitions of the base and index tables; and

update the base table metadata and the table metadata in the partitioned distributed storage system.

15. The system of claim 11, wherein the program instructions executable by the processor further causes the system to:

delete the set of base-delta files and the set of index-delta files in a respective one or more corresponding partitions of the base and index tables; and

update the base table metadata and the index table metadata in the partitioned distributed storage system.

16. A computer program product for processing a dataset in a partitioned distributed storage system having data stored in a base table and an index stored in an index table, the computer program product including a computer readable storage medium having program instructions embodied therewith, wherein the computer readable storage medium is not a transitory signal per se, the program instructions executable by a processing circuit to cause the processing circuit to perform a method comprising:

locking the base table and the index table to prevent external update operations;

receiving base and index table metadata from the partitioned distributed storage system, wherein the base table metadata and the index table metadata include respective base table partition information and index table partition information;

partitioning the dataset into a set of base-delta files according to the base table metadata;

generating a set of index-delta files corresponding with the base-delta files according to the index table metadata;

updating the partitioned distributed storage system with the set of base-delta files and the set of index-delta files,

wherein a first update of the base table is synchronous with a second update of the index table; and

unlocking, subsequent to the second update, the base table and the index table.

17. The computer program product of claim 16, wherein the program instructions executable by the processor further causes the system to:

determining from the base table metadata a partitioning criteria; and

allocating the dataset to the set of base-delta files according to a partitioning criteria.

18. The computer program product of claim 16, wherein the generating comprises:

determining from the index table metadata a criteria for generating index-deltas from a set of base table deltas,

wherein the set of base table deltas include the dataset as allocated to the base-delta files, and the set of index-deltas include references to the set of base table deltas;

generating the index-deltas according to the criteria for generating index-deltas; and

determining from the index table metadata a partitioning criteria for allocating the set of index deltas to the set of index-delta files;

allocating the set of index-deltas to the set of index-delta files according to the partitioning criteria.

19. The computer program product of claim 16, wherein the updating comprises:

merging the set of base-delta and the set of index-delta files into a respective one or more corresponding partitions of the base and index tables; and

updating the base table metadata and the table metadata in the partitioned distributed storage system.

20. The computer program product of claim 16, wherein the updating comprises:

deleting the set of base-delta files and the set of index-delta files in a respective one or more corresponding partitions of the base and index tables; and

updating the base table metadata and the index table metadata in the partitioned distributed storage system.