Method and system for sorting data in a cloud-computing environment and other distributed computing environments
The current document is directed to a method and system for data processing in cloud-computing environments and other distributed-computing environments. Implementations of a merge sort suitable for the sorting of data within cloud-computing environments and other distributed-computing environments are disclosed. These implementations takes advantage of the massive parallelism available in cloud-computing environments as well as take into consideration numerous constraints regarding data-storage and data-retrieval operations in a cloud-computing environment. The implementations provide a type of data-sorting method and system that iteratively carries out highly parallel merge-sort operations that can be effectively applied over a range of data-set sizes up to extremely large data sets.
1. A merge-sort system comprising:
a distributed computing environment, implemented on multiple physical computer systems, that provides computational resources for execution of tasks and that provides a virtual data-storage subsystem for storing and retrieving data objects; and
computer instructions, encoded in one or more physical data-storage devices, that control the distributed computing environment to:
receive an indication of a number of data objects stored within the distributed computing environment, wherein:
each data object includes multiple records, and
each record comprises a key and a data value;
distribute tasks to computational resources within the distributed computing environment where the tasks are executed, wherein:
each task is associated with a data object, and
each task sorts the records of the data object associated with the task by key value; and
while a range of key values in any data object of the number of data objects overlaps with a range of key values in any other data object of the number of data objects, distribute tasks to computational resources within the distributed computing environment where the tasks are executed, wherein:
each task is associated with a subset of the data objects, and
each task merge sorts the records of the subset of the data objects associated with the task by key value.
2. The merge-sort system of claim 1 wherein the number of data objects and subsets of the number of data objects are represented by manifest objects, each manifest object including a set of one or more block-information objects, each block-information object representing a data object and including an identifier for the data object, a key value of a first record contained in the data object, and a key value of a last record contained in the data object.
3. The merge-sort system of claim 2 wherein the distributed computing system, after receiving the indication of the number of data objects stored within the distributed computing environment, represents the number of data objects by a manifest object.
4. The merge-sort system of claim 3 wherein the distributed computing system distributes the tasks associated with data objects to computational resources for sorting the records within the data objects by:
representing each data object in a separate manifest object;
associating each separate manifest object with a record-sorting task which reads, from a data-storage subsystem of the distributed computing system, the data object referenced by the manifest, sorts the records of the data object in memory, and writes the sorted data object back to the data-storage subsystem of the distributed computing system; and
following execution of the record-sorting tasks, reassembling the separate manifest objects into a single, result manifest object.
5. The merge-sort system of claim 3 wherein the distributed computing system distributes the tasks associated with data objects to computational resources for sorting the records within the data objects by:
partitioning a result manifest object that represents the number of data objects into separate manifest objects that each represent a subset of the data objects;
associating each separate manifest object with a merge-sort task which reads, from a data-storage subsystem of the distributed computing system, the data objects referenced by a manifest object, merge-sorts the records of the data objects into result data objects, writes the result data objects back to the data-storage subsystem of the distributed computing system, and generates a separate result manifest object that references the result data objects; and
following execution of the merge-sort tasks, reassembling the separate result manifests into a single, result manifest.
6. The merge-sort system of claim 2 wherein, when a range of key values in no data object of the number of data objects overlaps with a range of key values in any other data object of the number of data objects, the distributed computing system sorts the block-information objects within a final, result manifest object to produce a representation of a set of data objects in which the records are sorted by key value.
7. The merge-sort system of claim 6 wherein the final manifest object that represents a set of data objects in which the records are sorted by key value, represents a set of data objects in which the records are sorted by key value with respect to one of:
a single sort dimension; and
multiple sort dimensions.
8. The merge-sort system of claim 6 wherein the final, result manifest object that represents of a set of data objects in which the records are sorted by key value represents a set of data objects in which the records are sorted in one of:
ascending order;
descending order; and
a complex order defined by a relational operator.
9. A method in a distributed computing environment, implemented on multiple physical computer systems, that provides computational resources for execution of tasks and that provides a virtual data-storage subsystem for storing and retrieving data objects, the method comprising:
receiving an indication of a number of data objects stored within the distributed computing environment, wherein:
each data object includes multiple records, and
each record comprises a key and a data value;
distributing tasks to computational resources within the distributed computing environment where the tasks are executed, wherein:
each task is associated with a data object, and
each task sorts the records of the data object associated with the task by key value; and
while a range of key values in any data object of the number of data objects overlaps with a range of key values in any other data object of the number of data objects, distributing tasks to computational resources within the distributed computing environment where the tasks are executed, wherein:
each task is associated with a subset of the data objects, and
each task merge sorts the records of the subset of the data objects associated with the task by key value.
10. The method of claim 9 further comprising representing the number of data objects and subsets of the number of data objects by manifest objects, each manifest object including a set of one or more block-information objects, each block-information object representing a data object and including an identifier for the data object, a key value of a first record contained in the data object, and a key value of a last record contained in the data object.
11. The method of claim 10 further including, after receiving the indication of the number of data objects stored within the distributed computing environment, representing the number of data objects by a manifest object.
12. The method of claim 11 further including distributing the tasks associated with data objects to computational resources for sorting the records within the data objects by:
representing each data object in a separate manifest object,
associating each separate manifest object with a record-sorting task which reads, from a data-storage subsystem of the distributed computing system, the data object referenced by the manifest, sorts the records of the data object in memory, and writes the sorted data object back to the data-storage subsystem of the distributed computing system; and
following execution of the record-sorting tasks, reassembling the separate manifest objects into a single, result manifest object.
13. The method of claim 11 further including distributing the tasks associated with data objects to computational resources for sorting the records within the data objects by:
partitioning a result manifest object that represents the number of data objects into separate manifest objects that each represent a subset of the data objects;
associating each separate manifest object with a merge-sort task which reads, from a data-storage subsystem of the distributed computing system, the data objects referenced by a manifest object, merge-sorts the records of the data objects into result data objects, writes the result data objects back to the data-storage subsystem of the distributed computing system, and generates a separate result manifest object that references the result data objects; and
following execution of the merge-sort tasks, reassembling the separate result manifests into a single, result manifest.
14. The method of claim 10 further including:
when a range of key values in no data object of the number of data objects overlaps with a range of key values in any other data object of the number of data objects,
sorting the block-information objects within a final, result manifest object to produce a representation of a set of data objects in which the records are sorted by key value.
15. The method of claim 14 wherein the final manifest object that represents a set of data objects in which the records are sorted by key value, represents a set of data objects in which the records are sorted by key value with respect to one of:
a single sort dimension; and
multiple sort dimensions.
16. The method of claim 14 wherein the final, result manifest object that represents of a set of data objects in which the records are sorted by key value represents a set of data objects in which the records are sorted in one of:
ascending order;
descending order; and
a complex order defined by a relational operator.