Granted Patent B1

US 9,183,200 · App. 13/564,984 · Granted Nov 10, 2015

Abstract

Claims (114)

1. A computer-implemented method, using one or more processors and a non-transient computer-readable storage medium, comprising:

partitioning a transaction log into a plurality of partitioned log files, wherein

the transaction log comprises a plurality of transaction objects, wherein

each of the transaction objects comprises a unique hash value, and

each of the unique hash values is based, at least in part, on information in a corresponding one of the transaction objects;

the partitioning the transaction log comprises

dividing the plurality of transaction objects into the plurality of partitioned log files, wherein

each of the plurality of partitioned log files is associated with a hash-value-based range constraint among a plurality of hash-value-based range constraints,

for each of the transaction objects to be partitioned, the dividing uses the unique hash value of said transaction object to allocate said transaction object to a corresponding partitioned log file of the plurality of partitioned log files, wherein

 the corresponding partitioned log file is associated with the hash-value-based range constraint that comprises the unique hash value of said transaction object, and

as a result of the dividing, each of the plurality of partitioned log files comprises a subset of the plurality of transaction objects; and

sorting each of the plurality of partitioned log files, wherein

the plurality of partitioned log files are sorted concurrently, and

the sorting produces a plurality of sorted partitioned log files.

2. The method of claim 1 , wherein

each of the transaction objects further comprises information about corresponding deduplicated data, and

the corresponding deduplicated data is stored in a deduplication store.

3. The method of claim 1 , further comprising:

updating a plurality of tables, wherein

the plurality of tables are updated concurrently, and

the updating uses the plurality of sorted partitioned log files.

4. The method of claim 3 , wherein the dividing the plurality of transaction objects further comprises:

comparing a first hash value of a first transaction object with a first hash value range associated with a first partitioned log file; and

storing the first transaction object in the first partitioned log file, in response to a determination that the first hash value falls within the first hash value range.

5. The method of claim 1 , wherein:

a number of hash-value-based range constraints among the plurality of hash-value-based range constraints does not exceed a number of CPU cores among a plurality of CPU cores, wherein

each CPU core is operably coupled to one or more processors; and

the sorting further comprises

assigning each of the plurality of partitioned log files to a respective thread of a plurality of threads, wherein

each of the plurality of threads is assigned to a separate CPU core among the plurality of CPU cores; and

concurrently sorting, by the respective thread, each of the plurality of partitioned log files.

6. The method of claim 3 , wherein

a reference list database comprises a plurality of tables,

the reference list database comprises information about deduplicated data stored in a deduplication store, and

each of the plurality of tables comprises a subset of the information.

7. The method of claim 3 , wherein the updating the plurality of tables further comprises:

assigning a respective table of the plurality of tables to a respective thread of a plurality of threads;

assigning a respective sorted partitioned log file of the plurality of sorted partitioned log files to the respective thread, wherein

the respective sorted partitioned log file shares at least a portion of a first hash-value-based range constraint associated with the respective table, wherein

the first hash-value-based range constraint is one of the plurality of hash-value-based range constraints; and

concurrently processing, by the respective thread, the respective sorted partitioned log file against the respective table.

8. The method of claim 7 , wherein the concurrently processing the respective sorted partitioned log file comprises:

generating a respective dump file for the respective table;

merging the respective sorted partitioned log file with the respective dump file to produce a respective merged dump file; and

importing the respective merged dump file into a temporary table.

9. The method of claim 3 , wherein the updating the plurality of tables comprises:

updating a plurality of temporary tables in parallel; and

replacing the plurality of tables with the plurality of temporary tables.

10. A non-transitory computer readable storage medium configured to store program instructions that, when executed on a processor, are configured to cause the processor to perform a method comprising:

partitioning a transaction log into a plurality of partitioned log files, wherein

the transaction log comprises a plurality of transaction objects, wherein

each of the transaction objects comprises a unique hash value, and

each of the unique hash values is based, at least in part, on information in a corresponding one of the transaction objects;

the partitioning the transaction log comprises

dividing the plurality of transaction objects into the plurality of partitioned log files, wherein

each of the plurality of partitioned log files is associated with a hash-value-based range constraint among a plurality of hash-value-based range constraints,

for each of the transaction objects to be partitioned, the dividing uses the unique hash value of said transaction object to allocate said transaction object to a corresponding partitioned log file of the plurality of partitioned log files, wherein

 the corresponding partitioned log file is associated with the hash-value-based range constraint that comprises the unique hash value of said transaction object, and

as a result of the dividing, each of the plurality of partitioned log files comprises a subset of the plurality of transaction objects; and

sorting each of the plurality of partitioned log files in parallel, wherein

the plurality of partitioned log files are sorted concurrently, and

the sorting produces a plurality of sorted partitioned log files.

11. The non-transitory computer readable storage medium of claim 10 , wherein

each of the transaction objects further comprises information about corresponding deduplicated data, and

the corresponding deduplicated data is stored in a deduplication store.

12. The non-transitory computer readable storage medium of claim 10 , wherein the method performed by the processor further comprises:

updating a plurality of tables, wherein

the plurality of tables are updated concurrently, and

the updating uses the plurality of sorted partitioned log files.

13. The non-transitory computer readable storage medium of claim 11 , wherein the dividing the plurality of transaction objects further comprises:

comparing a first hash value of a first transaction object with a first hash value range associated with a first partitioned log file; and

storing the first transaction object in the first partitioned log file, in response to a determination that the first hash value falls within the first hash value range.

14. The non-transitory computer readable storage medium of claim 10 , wherein

a number of hash-value-based range constraints among the plurality of hash-value-based range constraints does not exceed a number of CPU cores among a plurality of CPU cores, wherein each CPU core is operably coupled to one or more processors; and

the sorting further comprises

assigning each of the plurality of partitioned log files to a respective thread of a plurality of threads, wherein

each of the plurality of threads is assigned to a separate CPU core among the plurality of CPU cores; and

concurrently sorting, by the respective thread, each of the plurality of partitioned log files.

15. The non-transitory computer readable storage medium of claim 12 , wherein

a reference list database comprises the plurality of tables,

the reference list database comprises information about deduplicated data stored in a deduplication store, and

each of the plurality of tables comprises a subset of the information.

16. The non-transitory computer readable storage medium of claim 10 , wherein the updating the plurality of tables further comprises:

assigning a respective table of the plurality of tables to a respective thread of a plurality of threads;

assigning a respective sorted partitioned log file of the plurality of sorted partitioned log files to the respective thread, wherein

the respective sorted partitioned log file shares at least a portion of a first hash-value-based range constraint associated with the respective table; and

concurrently processing, by the respective thread, the respective sorted partitioned log file against the respective table.

17. The non-transitory computer readable storage medium of claim 16 , wherein the concurrently processing the respective sorted partitioned log file comprises:

generating a respective dump file for the respective table;

merging the respective sorted partitioned log file with the respective dump file to produce a respective merged dump file; and

importing the respective merged dump file into a temporary table.

18. The non-transitory computer readable storage medium of claim 12 , wherein the updating the plurality of tables comprises:

updating a plurality of temporary tables in parallel; and

replacing the plurality of tables with the plurality of temporary tables.

19. An apparatus comprising:

a partitioning module comprising:

means to partition a transaction log into a plurality of partitioned log files, wherein

the transaction log comprises a plurality of transaction objects, wherein

each of the transaction objects comprises a unique hash value, and

each of the unique hash values is based, at least in part, on information in a corresponding one of the transaction objects;

the means to partition the transaction log comprises

means for dividing the plurality of transaction objects into the plurality of partitioned log files, wherein

each of the plurality of partitioned log files is associated with a hash-value-based range constraint among a plurality of hash-value-based range constraints,

for each of the transaction objects to be partitioned, the means for dividing uses the unique hash value of said transaction object to allocate said transaction object to a corresponding partitioned log file of the plurality of partitioned log files, wherein

 the corresponding partitioned log file is associated with the hash-value-based range constraint that comprises the unique hash value of said transaction object, and

each of the plurality of partitioned log files comprises a subset of the plurality of transaction objects, as a result of the dividing; and

means to generate a plurality of sorted partitioned log files, wherein

the means to generate further comprises

means to sort each of the plurality of partitioned log files, wherein

 the plurality of partitioned log files are sorted concurrently, and

 the means to sort produces a plurality of sorted partitioned log files.

20. The apparatus of claim 19 , wherein

each of the transaction objects further comprises information about corresponding deduplicated data, and

the corresponding deduplicated data is stored in a deduplication store.

Assignments (13)