Parallel sort with a ranged, partitioned key-value store in a high perfomance computing environment
View Patent ↗Improved sorting techniques are provided that perform a parallel sort using a ranged, partitioned key-value store in a high performance computing (HPC) environment. A plurality of input data files comprising unsorted key-value data in a partitioned key-value store are sorted. The partitioned key-value store comprises a range server for each of a plurality of ranges. Each input data file has an associated reader thread. Each reader thread reads the unsorted key-value data in the corresponding input data file and performs a local sort of the unsorted key-value data to generate sorted key-value data. A plurality of sorted, ranged subsets of each of the sorted key-value data are generated based on the plurality of ranges. Each sorted, ranged subset corresponds to a given one of the ranges and is provided to one of the range servers corresponding to the range of the sorted, ranged subset. Each range server sorts the received sorted, ranged subsets and provides a sorted range. A plurality of the sorted ranges are concatenated to obtain a globally sorted result.
1. A method for sorting a plurality of input data files comprising unsorted key-value data in a partitioned key-value store comprising a range server for each of a plurality of ranges in said partitioned key-value store, said method comprising:
wherein each of said plurality of input data files has an associated reader thread, wherein each reader thread reads said unsorted key-value data in said corresponding input data file and performs a local sort of said unsorted key-value data to generate sorted key-value data;
generating a plurality of sorted, ranged subsets of each of said sorted key-value data based on said plurality of ranges, such that each of said sorted, ranged subsets corresponds to a given one of said ranges;
providing each of said plurality of sorted, ranged subsets to one of said range servers corresponding to said range of said sorted, ranged subset, wherein each of said range servers sorts said received sorted, ranged subsets and provides a sorted range; and
concatenating a plurality of said sorted ranges to obtain a globally sorted result.
2. The method of claim 1 , wherein said step of providing each of said plurality of sorted, ranged subsets to one of said range servers comprises a batch insert operation.
3. The method of claim 1 , wherein said partitioned key-value store is based on a Multidimensional Data Hashing Indexing Middleware (MDHIM) framework.
4. The method of claim 1 , wherein said partitioned key-value store employs Message Passing Interface (MPI) communications.
5. The method of claim 1 , wherein said reader thread is associated with an MDHIM client.
6. The method of claim 1 , wherein said step of generating a plurality of sorted, ranged subsets of each of said sorted key-value data is performed by said reader thread.
7. The method of claim 1 , wherein said range servers comprise MDHIM range servers.
8. An apparatus for sorting a plurality of input data files comprising unsorted key-value data in a partitioned key-value store comprising a range server for each of a plurality of ranges in
said partitioned key-value store, the apparatus comprising: a memory; and
at least one hardware device, coupled to the memory, operative to implement the following steps:
wherein each of said plurality of input data files has an associated reader thread, wherein each reader thread reads said unsorted key-value data in said corresponding input data file and performs a local sort of said unsorted key-value data to generate sorted key-value data;
generating a plurality of sorted, ranged subsets of each of said sorted key-value data based on said plurality of ranges, such that each of said sorted, ranged subsets corresponds to a given one of said ranges;
providing each of said plurality of sorted, ranged subsets to one of said range servers corresponding to said range of said sorted, ranged subset, wherein each of said range servers sorts said received sorted, ranged subsets and provides a sorted range; and
concatenating a plurality of said sorted ranges to obtain a globally sorted result.
9. The apparatus of claim 8 , wherein said plurality of sorted, ranged subsets are provided to one of said range servers using a batch insert operation.
10. The apparatus of claim 8 , wherein said partitioned key-value store is based on a Multidimensional Data Hashing Indexing Middleware (MDHIM) framework.
11. The apparatus of claim 8 , wherein said partitioned key-value store employs Message Passing Interface (MPI) communications.
12. The apparatus of claim 8 , wherein said reader thread is associated with an MDHIM client.
13. The apparatus of claim 8 , wherein said plurality of sorted, ranged subsets of each of said sorted key-value data are generated by said reader thread.
14. The apparatus of claim 8 , wherein said range servers comprise MDHIM range servers.
15. An article of manufacture for sorting a plurality of input data files comprising unsorted key-value data in a partitioned key-value store comprising a range server for each of a plurality of ranges in said partitioned key-value store, the article of manufacture comprising a non-transitory machine readable recordable storage medium containing one or more programs which when executed implement the steps of:
wherein each of said plurality of input data files has an associated reader thread, wherein each reader thread reads said unsorted key-value data in said corresponding input data file and performs a local sort of said unsorted key-value data to generate sorted key-value data;
generating a plurality of sorted, ranged subsets of each of said sorted key-value data based on said plurality of ranges, such that each of said sorted, ranged subsets corresponds to a given one of said ranges;
providing each of said plurality of sorted, ranged subsets to one of said range servers corresponding to said range of said sorted, ranged subset, wherein each of said range servers sorts said received sorted, ranged subsets and provides a sorted range; and
concatenating a plurality of said sorted ranges to obtain a globally sorted result.
16. The article of manufacture of claim 15 , wherein said step of providing each of said plurality of sorted, ranged subsets to one of said range servers comprises a batch insert operation.
17. The article of manufacture of claim 15 , wherein said partitioned key-value store is based on a Multidimensional Data Hashing Indexing Middleware (MDHIM) framework.
18. The article of manufacture of claim 15 , wherein said partitioned key-value store employs Message Passing Interface (MPI) communications.
19. The article of manufacture of claim 15 , wherein said reader thread is associated with an MDHIM client and wherein said range servers comprise MDHIM range servers.
20. The article of manufacture of claim 15 , wherein said step of generating a plurality of sorted, ranged subsets of each of said sorted key-value data is performed by said reader thread.