Skip to Content
Find More Like This
Return to Search

Parallel sort with a ranged, partitioned key-value store in a high perfomance computing environment

United States Patent

January 26, 2016
View the Complete Patent at the US Patent & Trademark Office
Los Alamos National Laboratory - Visit the Technology Transfer Division Website
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.
Bent; John M. (Los Alamos, NM), Faibish; Sorin (Newton, MA), Grider; Gary (Los Alamos, NM), Torres; Aaron (Los Alamos, NM), Poole; Stephen W. (Knoxville, TN)
EMC Corporation (Hopkinton, MA), Los Alamos National Security, LLC (Los Alamos, NM)
14/ 143,771
December 30, 2013
STATEMENT OF GOVERNMENT RIGHTS This invention was made under a Cooperative Research and Development Agreement between EMC Corporation and Los Alamos National Security, LLC. The United States government has rights in this invention pursuant to Contract No. DE-AC52-06NA25396 between the United States Department of Energy and Los Alamos National Security, LLC for the operation of Los Alamos National Laboratory.