Take the 2-minute tour ×
Server Fault is a question and answer site for professional system and network administrators. It's 100% free, no registration required.

Greetings,

I'm looking for a high performance /bin/sort drop in replacement. I know there is pbzip2 for using multiple cores, but is there a similar product for /bin/sort?

I've found distsort.sh, but I want something less IO intensive. I'm looking to sort oh.. 60 gigs of data on a very frequent basis.

-daniel

share|improve this question
add comment

4 Answers

up vote 2 down vote accepted

GNU sort has -m which can probably help you out. Let us assume you have 200 .gz-files that you want to sort and combine. Then you could use GNU Parallel to do:

seq 1 200 | parallel mkfifo /tmp/{}
ls *.gz | nice parallel -j200 'zcat {} | sort >/tmp/$PARALLEL_SEQ' &
seq 1 200 | parallel -X sort -m /tmp/{} >/tmp/sorted

If I/O is the problem and memory is not an issue, the use -S for the first sort to make sure everything stays in memory. Also you may want to use lzop every time you write to disk (--compress-program=lzop): Disks are often the limiting factor so lzopping on the fly can give you extra speed. Or you could make a RAM disk and set -T to that dir.

share|improve this answer
    
I really like this!!! –  Daniel Jan 15 '11 at 20:39
add comment

Hrm. You're going to run into a few issues here, I think. First of all, your input data is going to have a big impact on sorting performance (different algorithms perform better or worse depending on the distribution of the input). However, a bigger problem up front is simply that 60GB is a lot of data.

Additionally, sorting doesn't paralellize as easily as compression because there's no proximity guarantees. In other words, with compression/decompression, you can break the input into discrete chunks, and operate on them each separately and independently. After each chunk is processed, they're simply concatenated together. With sorting, you've got multiple steps involved because you can't just concatenate the results (unless you do some preprocessing), you have to merge the results (because an entry at the beginning of the 60GB could end up adjacent to an entry at the end of the 60GB, after sorting).

I can basically think of a few general solutions here:

  • Prepartition your data in a way that is friendly to sorting and recombining. For example, if you were doing a simple alphabetic sorting, you might store your data in 26 buckets, one for each letter of the alphabet. Then you could sort each bucket individually, and recombine them at the end. The specifics of how you prepartition your data would be dependent on the data itself, your current storage method, etc. Some setups might work better for this than others.
  • Write your own sort front end that does basically what I wrote about above, but on the fly. In other words, you'd have a script that reads the input, and based on some very fast operation (such as reading the first letter, or whatever works for your data), then distributes that piece of data to the appropriate sort bucket. Each sort operates independently until all the data has been processed, then you combine it all back together. This is actually pretty similar to a special case of using MapReduce for sorting.
  • Use a MapReduce based sort solution. There's an Open Source project called Hadoop that provides a bunch of sub-projects, one of which is an Open Source MapReduce implementation. I've never used it, however, just read about it. I have no idea if it would be practically applicable to your particular problem.
  • Can you index the data, and then just sort that? Is the entire 60GB part of the sort key? Or is there a smaller part that you're sorting on, an then a bunch of additional data for each piece? If it's the latter, indexing and sorting just some sort of key value, and then looking up the additional data as needed, might be the way to go.
  • Perhaps you could completely pre-sort your data, and maintain it in a sorted state. Every time you add to, or update, the data, you would correct it from a sorted perspective. This solution would be highly dependent both on how you are storing your data, and on whether the performance impact from the sort updates would be acceptable.
  • Lastly, you could punt on the whole thing. Dump your data into an RDBMS (I like PostgresSQL myself), and let the database handle your sorting for you.

Without knowing a lot more about your data and the specifics of what you're doing, that's about the best I can offer for suggestions.

[Note: I'm not an expert on sorting, so someone smarter than me may be able to point out errors in my logic, or suggestions to improve on these.]

share|improve this answer
    
+1, Indexing and sorting on that. –  Chris S Jul 27 '10 at 0:30
    
+1 for Hadoop. This is probably the right way to do it. –  Tom O'Connor Jul 27 '10 at 10:34
    
These are good "algorithmic" solutions that work on solving the problem but they also cause a lot of logistical problems. I was fairly sure there would be a highly parallel-ized /bin/sort out there like pbzip2. –  Daniel Jul 30 '10 at 18:02
    
Yeah, it comes down to complexity. Some tools are relatively easy to parallelize (bzip2), while others are potentially much more difficult (sort). Heck, even within compression, it can vary a lot. bzip2, because it's the way it works, parallelizes much easier than gzip does (hence the reason pbzip2 has gained some popularity, while parallel gzip implementations are scarce). –  Christopher Cashell Jul 30 '10 at 20:14
add comment

In searching around, I found lots of references to academic papers and one commercial product called Nsort. I don't know anything about it other than that their web site claims that:

Nsort is a sort/merge program that can quickly sort large amounts of data, using large numbers of processors and disks in parallel. Unique in its CPU efficiency, Nsort is the only commercial sort program to demonstrate:

  • 1 Terabyte sorts (33 minutes)
  • 1 Gigabyte/sec file read and write rates

Nsort has a long history of sorting massive, production data sets, such as:

  • Web logs for high-traffic web sites
  • Phone logs
  • Government agency data
share|improve this answer
    
This is a very good solution –  Daniel Jul 30 '10 at 17:59
add comment

Perl ?

Edit: Well, this article is about Perl sort perf tunning. From what I can understand from it, it's basically more a best practice guide, comparing how a bad sort code can make your program very slow, and the opposite, how to make it faster.

Sloppy programming, sloppy performance.

share|improve this answer
    
What about perl makes it efficient for sorting? –  Chris S Jul 27 '10 at 0:31
1  
You should summarize how the paper you linked to applies to specific requirements specified by the OP. –  Dennis Williamson Jul 27 '10 at 2:06
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.