Granted Patent B2

US 8,321,454 · App. 12/882,058 · Granted Nov 27, 2012

Assignee: MySpace LLC

Abstract

Claims (112)

1. A computer-implemented method for performing a sorted map-reduce job on a cluster comprising:

(A) defining a cluster of two or more computers by:

(1) installing a map-reduce framework onto each of the two or more computers; and

(2) formatting the cluster by:

(i) identifying the two or more computers in the cluster;

(ii) establishing communication between the two or more computers; and

(iii) enabling the cluster of two or more computers to function as a unit;

(B) placing data into the cluster, wherein:

(1) the data is distributed onto the two or more computers in the cluster; and

(2) each of the two or more computers in the cluster contains a portion of the data;

(C) obtaining a map-reduce function to be executed by the map-reduce framework on the cluster;

(D) performing a first map function of the map-reduce function, wherein the first map function comprises:

(1) each of the two or more computers sorting the portion of the data stored on that computer;

(2) each of the two or more computers creating an abstraction comprising a representation of the sorted portion of data stored on that computer;

(3) each of the two or more computers exchanging the abstractions; and

(4) each of the two or more computers merging the abstractions to create a complete abstraction representing all of the data in the cluster;

(E) performing a second map function of the map-reduce function, wherein the second map function comprises:

(1) conducting a search of the complete abstraction to determine a redistribution of the data across the two or more computers; and

(2) conducting a data exchange wherein each of the two or more computers obtains data based on the redistribution and complete abstraction; and

(F) performing a reduce function of the map-reduce function comprising each of the two or more computers performing, in parallel, the reduce function on the data obtained based on the redistribution to produce a result.

2. The computer-implemented method of claim 1 , wherein:

the data is placed into the cluster using a PUT command; and

each of the two or more computers in the cluster is assigned a portion of the data.

3. The computer-implemented method of claim 1 , wherein the abstraction comprising a representation of the sorted portion of the data stored on that computer comprises is a less than 5 kilobytes per terabyte of data.

4. The computer-implemented method of claim 1 , wherein, the redistribution defines a range of (key,value) pairs that each of the two or more computers will be responsible for.

5. The computer-implemented method of claim 1 , wherein all of the data is stored as big endian.

6. The computer-implemented method of claim 1 , further comprising persisting memory cache across the cluster wherein:

a failure of one of the two or more computers results in the replacing of the failed computer with a different computer;

the replacing is performed as a single transaction; and

a redundant copy of the data is obtained from remaining computers in the cluster.

7. The computer-implemented method of claim 1 , comprising performing a second map-reduce function, wherein the second map-reduce function utilizes the complete abstraction to perform a deep graph traversal using a distributed binary search.

8. The computer-implemented method of claim 1 , further comprising utilizing a random-access look-up-table (LUT) in the cluster, wherein the LUT identifies:

the redistribution of the data; and

aggregate available memory in the cluster.

9. The computer-implemented method of claim 1 , further comprising:

receiving a structured query language (SQL) query in the cluster;

translating, within the cluster and without additional user input, the SQL query into a second map-reduce function; and

performing the second map-reduce function on the data in the cluster.

10. The computer-implemented method of claim 9 , wherein the SQL query comprises an ORDER BY clause.

11. An apparatus for performing a sorted map-reduce job on a computer cluster comprising:

(A) a computer cluster comprising two or more computers;

(B) a map-reduce framework installed onto each of the two or more computers, wherein:

(1) the map-reduce framework defines the cluster;

(2) the cluster is formatted by:

(i) identifying the two or more computers in the cluster;

(ii) establishing communication between the two or more computers; and

(iii) enabling the cluster of two or more computers to function as a unit;

(C) data that is placed into the cluster, wherein:

(1) the data is distributed onto the two or more computers in the cluster; and

(2) each of the two or more computers in the cluster contains a portion of the data;

(D) a map-reduce function configured to be executed by the map-reduce framework on the cluster;

(E) a first map function of the map-reduce function, wherein the first map function comprises:

(1) each of the two or more computers sorting the portion of the data stored on that computer;

(2) each of the two or more computers creating an abstraction comprising a representation of the sorted portion of data stored on that computer;

(3) each of the two or more computers exchanging the abstractions; and

(4) each of the two or more computers merging the abstractions to create a complete abstraction representing all of the data in the cluster;

(F) a second map function of the map-reduce function, wherein the second map function comprises:

(1) conducting a search of the complete abstraction to determine a redistribution of the data across the two or more computers; and

(2) conducting a data exchange wherein each of the two or more computers obtains data based on the redistribution and complete abstraction; and

(G) a reduce function of the map-reduce function, wherein the reduce function comprises each of the two or more computers performing, in parallel, the reduce function on the data obtained based on the redistribution to produce a result.

12. The apparatus of claim 11 , wherein:

the data is placed into the cluster using a PUT command; and

each of the two or more computers in the cluster is assigned a portion of the data.

13. The apparatus of claim 11 , wherein the abstraction comprising a representation of the sorted portion of the data stored on that computer comprises is a less than 5 kilobytes per terabyte of data.

14. The apparatus of claim 11 , wherein, the redistribution defines a range of (key,value) pairs that each of the two or more computers will be responsible for.

15. The apparatus of claim 11 , wherein all of the data is stored as big endian.

16. The apparatus of claim 11 , further comprising persisting memory cache across the cluster wherein:

a failure of one of the two or more computers results in the replacing of the failed computer with a different computer;

the replacing is performed as a single transaction; and

a redundant copy of the data is obtained from remaining computers in the cluster.

17. The apparatus of claim 11 , further comprising a second map-reduce function, wherein the second map-reduce function utilizes the complete abstraction to perform a deep graph traversal using a distributed binary search.

18. The apparatus of claim 11 , further comprising a random-access look-up-table (LUT) in the cluster, wherein the LUT identifies:

the redistribution of the data; and

aggregate available memory in the cluster.

19. The apparatus of claim 11 , further comprising a query optimizer configured to:

receive a structured query language (SQL) query in the cluster;

translate, within the cluster and without additional user input, the SQL query into a second map-reduce function; and

perform the second map-reduce function on the data in the cluster.

20. The apparatus of claim 19 , wherein the SQL query comprises an ORDER BY clause.

21. A system for performing a sorted map-reduce job on a computer cluster comprising:

(A) a computer cluster comprising two or more computers that are communicatively coupled to each other enabling the cluster to function as a unit;

(B) a map-reduce framework installed onto each of the two or more computers;

(C) data distributed across the cluster such that each of the two or more computers in the cluster contains a portion of the data;

(D) a map-reduce function configured to be executed by the map-reduce framework on the cluster;

(E) a first map function of the map-reduce function, wherein the first map function comprises:

(1) each of the two or more computers sorting the portion of the data stored on that computer;

(2) each of the two or more computers creating an abstraction comprising a representation of the sorted portion of data stored on that computer;

(3) each of the two or more computers exchanging the abstractions; and

(4) each of the two or more computers merging the abstractions to create a complete abstraction representing all of the data in the cluster;

(F) a second map function of the map-reduce function, wherein the second map function comprises:

(1) conducting a search of the complete abstraction to determine a redistribution of the data across the two or more computers; and

(2) conducting a data exchange wherein each of the two or more computers obtains data based on the redistribution and complete abstraction; and

(G) a reduce function of the map-reduce function, wherein the reduce function comprises each of the two or more computers performing, in parallel, the reduce function on the data obtained based on the redistribution to produce a result.

22. The system of claim 21 , wherein:

the data is placed into the cluster using a PUT command; and

each of the two or more computers in the cluster is assigned a portion of the data.

23. The system of claim 21 , wherein the abstraction comprising a representation of the sorted portion of the data stored on that computer comprises is a less than 5 kilobytes per terabyte of data.

24. The system of claim 21 , wherein, the redistribution defines a range of (key,value) pairs that each of the two or more computers will be responsible for.

25. The system of claim 21 , wherein all of the data is stored as big endian.

26. The system of claim 21 , further comprising persisting memory cache across the cluster wherein:

a failure of one of the two or more computers results in the replacing of the failed computer with a different computer;

the replacing is performed as a single transaction; and

a redundant copy of the data is obtained from remaining computers in the cluster.

27. The system of claim 21 , further comprising a second map-reduce function, wherein the second map-reduce function utilizes the complete abstraction to perform a deep graph traversal using a distributed binary search.

28. The system of claim 21 , further comprising a random-access look-up-table (LUT) in the cluster, wherein the LUT identifies:

the redistribution of the data; and

aggregate available memory in the cluster.

29. The system of claim 21 , further comprising a query optimizer configured to:

receive a structured query language (SQL) query in the cluster;

translate, within the cluster and without additional user input, the SQL query into a second map-reduce function; and

perform the second map-reduce function on the data in the cluster.

30. The system of claim 29 , wherein the SQL query comprises an ORDER BY clause.

Assignments (12)

Continuity (2)