WEB-SCALE DATA PROCESSING SYSTEM AND METHOD

• US 20100088352A1
• Filed: 10/02/2009
• Published: 04/08/2010
• Est. Priority Date: 10/03/2008
• Status: Active Grant

• Current Assignee: SEOmoz
• Original Assignee: SEOmoz
• Inventors: Gerner, Nicholas Stefan, Hendrickson, Benjamin Cappel
• Granted Patent: US 8,180,774 B2
• Time in Patent Office: Days
• US Class Current: 707/808
• CPC Class Codes: H03M 7/04 the radix thereof being two
• CPC Class Codes: H03M 7/40 Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code

Abstract

A web-scale data processing system and method are provided herein.

Claims

1. A method executing on at least one computing system for merging records from a plurality of conflicting namespaces into a globally-unified namespace, the method comprising:

performing steps a-d for an initial iteration level; and

performing at least steps a-c for a next iteration level;

a. obtaining a first plurality of source columns associated with the current iteration level, each source column including a plurality of records with source-column-unique, but not first-plurality-unique, identifiers;

b. grouping said first plurality of source columns into a current merge-group set comprising at least two merge groups for said initial iteration level and at least one merge group for said next iteration level, each merge group including at least two source columns;

c. for each merge group in said current merge-group set;

i. sorting and merging records from said at least two source columns in the current merge group into a merged column having a plurality of records with merged-column-unique identifiers;

ii. storing the current merged column; and

iii. for each of said at least two source columns in the current merge group, creating a translation table associated with the current iteration-level identifier, said translation table comprising a source entry for each source-column-unique record identifier in the current source column and a destination entry for each corresponding merged-column-unique record identifier in the current merged column;

d. associating the at least two current merged columns with said next iteration level.

2. The method of claim 1, further comprising:

obtaining a first translation table associated with said next iteration level;

obtaining a second translation table associated with said initial iteration level;

iteratively translating destination entries in said second translation table according to corresponding destination entries in said first translation table; and

storing the translated second translation table in association with said initial iteration level.

3. The method of claim 2, wherein iteratively translating destination entries in said second translation table according to corresponding destination entries in said first translation table comprises:

for each second-translation-table source entry;

identifying a second-translation-table destination entry corresponding to the current second-translation-table source entry;

identifying a first-translation-table source entry corresponding to the identified second-translation-table destination entry;

identifying a first-translation-table destination entry corresponding to the identified first-translation-table source entry; and

replacing said second-translation-table destination entry with the identified first-translation-table destination entry.

4. The method of claim 2, further comprising:

obtaining a link column associated with one of said first plurality of source columns associated with said initial iteration level, wherein said link column comprises a plurality of link records, each link record referencing a pair of source-column-unique record identifiers associated with said one of said first plurality of source columns;

obtaining said translated second translation table associated with said initial iteration level;

iteratively translating said plurality of link records in said link column according to said translated second translation table; and

storing the translated link column in association with said initial iteration level.

5. The method of claim 4, wherein iteratively translating said plurality of link records in said link column according to said translated second translation table comprises:

for each source-column-unique record identifier referenced in each of said plurality of link records;

identifying a translated-second-translation-table source entry corresponding to the current source-column-unique record identifier;

identifying a translated-second-translation-table destination entry corresponding to the identified translated-second-translation-table source entry; and

replacing the current source-column-unique record identifier with the identified translated-second-translation-table destination entry.

6. The method of claim 4, further comprising:

obtaining a plurality of said translated link columns associated with said initial iteration level; and

sorting and merging link records from said plurality of said translated link columns into a merged link column.

7. The method of claim 1, wherein sorting and merging records from said at least two source columns in the current merge group into a merged column having a plurality of records with merged-column-unique identifiers comprises:

sorting, by a first computing device, a first plurality of records corresponding to a first one of said at least two source columns;

determining a plurality of exclusive data ranges, including at least a first data range that corresponds to a first subset of said sorted first plurality of records and a second data range that corresponds to a second subset of said sorted first plurality of records; and

providing, to a remote computing device, said second subset of said sorted first plurality of records corresponding to said second data range;

obtaining, from said remote computing device, a third subset of a sorted second plurality of records corresponding to said first data range, said sorted second plurality of records corresponding to a second one of said at least two source columns;

merging said first subset of said sorted first plurality of records and said third subset of said sorted second plurality of records into a merged and sorted plurality of records corresponding to said first data range; and

storing said merged and sorted plurality of records by said first computing device.

8. A computing apparatus comprising a processor and a memory, the memory storing instructions that, when executed by the processor, perform a method for merging records from a plurality of conflicting namespaces into a globally-unified namespace, the method comprising:

performing steps a-d for an initial iteration level; and

performing at least steps a-c for a next iteration level;

a. obtaining a first plurality of source columns associated with the current iteration level, each source column including a plurality of records with source-column-unique, but not first-plurality-unique, identifiers;

b. grouping said first plurality of source columns into a current merge-group set comprising at least two merge groups for said initial iteration level and at least one merge group for said next iteration level, each merge group including at least two source columns;

c. for each merge group in said current merge-group set;

i. sorting and merging records from said at least two source columns in the current merge group into a merged column having a plurality of records with merged-column-unique identifiers;

ii. storing the current merged column; and

iii. for each of said at least two source columns in the current merge group, creating a translation table associated with the current iteration-level identifier, said translation table comprising a source entry for each source-column-unique record identifier in the current source column and a destination entry for each corresponding merged-column-unique record identifier in the current merged column;

d. associating the at least two current merged columns with said next iteration level.

9. The method of claim 8, the method further comprising:

obtaining a first translation table associated with said next iteration level;

obtaining a second translation table associated with said initial iteration level;

iteratively translating destination entries in said second translation table according to corresponding destination entries in said first translation table; and

storing the translated second translation table in association with said initial iteration level.

10. The computing apparatus of claim 9, wherein iteratively translating destination entries in said second translation table according to corresponding destination entries in said first translation table comprises:

for each second-translation-table source entry;

identifying a second-translation-table destination entry corresponding to the current second-translation-table source entry;

identifying a first-translation-table source entry corresponding to the identified second-translation-table destination entry;

identifying a first-translation-table destination entry corresponding to the identified first-translation-table source entry; and

replacing said second-translation-table destination entry with the identified first-translation-table destination entry.

11. The computing apparatus of claim 9, the method further comprising:

obtaining a link column associated with one of said first plurality of source columns associated with said initial iteration level, wherein said link column comprises a plurality of link records, each link record referencing a pair of source-column-unique record identifiers associated with said one of said first plurality of source columns;

obtaining said translated second translation table associated with said initial iteration level;

iteratively translating said plurality of link records in said link column according to said translated second translation table; and

storing the translated link column in association with said initial iteration level.

12. The computing apparatus of claim 11, wherein iteratively translating said plurality of link records in said link column according to said translated second translation table comprises:

for each source-column-unique record identifier referenced in each of said plurality of link records;

identifying a translated-second-translation-table source entry corresponding to the current source-column-unique record identifier;

identifying a translated-second-translation-table destination entry corresponding to the identified translated-second-translation-table source entry; and

replacing the current source-column-unique record identifier with the identified translated-second-translation-table destination entry.

13. The computing apparatus of claim 11, the method further comprising:

obtaining a plurality of said translated link columns associated with said initial iteration level; and

sorting and merging link records from said plurality of said translated link columns into a merged link column.

14. The computing apparatus of claim 8, wherein sorting and merging records from said at least two source columns in the current merge group into a merged column having a plurality of records with merged-column-unique identifiers comprises:

sorting, by the computing apparatus, a first plurality of records corresponding to a first one of said at least two source columns;

determining a plurality of exclusive data ranges, including at least a first data range that corresponds to a first subset of said sorted first plurality of records and a second data range that corresponds to a second subset of said sorted first plurality of records; and

providing, to a remote computing device, said second subset of said sorted first plurality of records corresponding to said second data range;

obtaining, from said remote computing device, a third subset of a sorted second plurality of records corresponding to said first data range, said sorted second plurality of records corresponding to a second one of said at least two source columns;

merging said first subset of said sorted first plurality of records and said third subset of said sorted second plurality of records into a merged and sorted plurality of records corresponding to said first data range;

storing said merged and sorted plurality of records by the computing apparatus.

15. A computer-readable storage medium having stored thereon instructions that, when executed by at least one processor, perform a method for merging records from a plurality of conflicting namespaces into a globally-unified namespace, the method comprising:

performing steps a-d for an initial iteration level; and

performing at least steps a-c for a next iteration level;

a. obtaining a first plurality of source columns associated with the current iteration level, each source column including a plurality of records with source-column-unique, but not first-plurality-unique, identifiers;

b. grouping said first plurality of source columns into a current merge-group set comprising at least two merge groups for said initial iteration level and at least one merge group for said next iteration level, each merge group including at least two source columns;

c. for each merge group in said current merge-group set;

i. sorting and merging records from said at least two source columns in the current merge group into a merged column having a plurality of records with merged-column-unique identifiers;

ii. storing the current merged column; and

iii. for each of said at least two source columns in the current merge group, creating a translation table associated with the current iteration-level identifier, said translation table comprising a source entry for each source-column-unique record identifier in the current source column and a destination entry for each corresponding merged-column-unique record identifier in the current merged column;

d. associating the at least two current merged columns with said next iteration level.

16. The storage medium of claim 15, the method further comprising:

obtaining a first translation table associated with said next iteration level;

obtaining a second translation table associated with said initial iteration level;

iteratively translating destination entries in said second translation table according to corresponding destination entries in said first translation table; and

storing the translated second translation table in association with said initial iteration level.

17. The storage medium of claim 16, wherein iteratively translating destination entries in said second translation table according to corresponding destination entries in said first translation table comprises:

for each second-translation-table source entry;

identifying a second-translation-table destination entry corresponding to the current second-translation-table source entry;

identifying a first-translation-table source entry corresponding to the identified second-translation-table destination entry;

identifying a first-translation-table destination entry corresponding to the identified first-translation-table source entry; and

replacing said second-translation-table destination entry with the identified first-translation-table destination entry.

18. The storage medium of claim 16, the method further comprising:

obtaining a link column associated with one of said first plurality of source columns associated with said initial iteration level, wherein said link column comprises a plurality of link records, each link record referencing a pair of source-column-unique record identifiers associated with said one of said first plurality of source columns;

obtaining said translated second translation table associated with said initial iteration level;

iteratively translating said plurality of link records in said link column according to said translated second translation table; and

storing the translated link column in association with said initial iteration level.

19. The storage medium of claim 18, wherein iteratively translating said plurality of link records in said link column according to said translated second translation table comprises:

for each source-column-unique record identifier referenced in each of said plurality of link records;

identifying a translated-second-translation-table source entry corresponding to the current source-column-unique record identifier;

identifying a translated-second-translation-table destination entry corresponding to the identified translated-second-translation-table source entry; and

replacing the current source-column-unique record identifier with the identified translated-second-translation-table destination entry.

20. The storage medium of claim 18, the method further comprising:

obtaining a plurality of said translated link columns associated with said initial iteration level; and

sorting and merging link records from said plurality of said translated link columns into a merged link column.

21. The storage medium of claim 15, wherein sorting and merging records from said at least two source columns in the current merge group into a merged column having a plurality of records with merged-column-unique identifiers comprises:

sorting, by a first computing device, a first plurality of records corresponding to a first one of said at least two source columns;

determining a plurality of exclusive data ranges, including at least a first data range that corresponds to a first subset of said sorted first plurality of records and a second data range that corresponds to a second subset of said sorted first plurality of records; and

providing, to a remote computing device, said second subset of said sorted first plurality of records corresponding to said second data range;

obtaining, from said remote computing device, a third subset of a sorted second plurality of records corresponding to said first data range, said sorted second plurality of records corresponding to a second one of said at least two source columns;

merging said first subset of said sorted first plurality of records and said third subset of said sorted second plurality of records into a merged and sorted plurality of records corresponding to said first data range;

storing said merged and sorted plurality of records by the first computing device.