Re:Ask HN: Sorting massive text files?
by arnabdotorg on Saturday August 14, 2010 @02:14PM
(#1603733)
Merge sort works very well if you have multiple cores available. The general idea is to split the file, sort in parallel, and then merge.
Here's a blog post I wrote about it:
GNU sort has a --compress-program option that can help if you're really tight on scratch space, e.g. lzop(1). The -T option or TMPDIR environment variable lets you state a filesystem with more free space can be used instead.
The -T option especially helps if you have more than one hard drive, and you're sorting a very large file where disk I/O is the bottleneck. You can use a second hard drive for the temporary files.
This is the approach that I use except that I generate a Makefile which has:
- a target to split the input into chunks
- targets to sort each of the split chunks
- a target to merge the sorted chunks using "sort -m"
http://vkundeti.blogspot.com/2008/03/tech-algorithmic-detail...
Thus, sort -u <filename> is your go-to for simple jobs. (Note that you'll need to have enough extra disk space to hold all of the temporary files.)
If you need to do something more sophisticated (e.g. joining lines from a web server log into sessions, then sorting sessions), you can still use divide-and-conquer, but you have to be smarter. Divide the file into N parts based on some logic (i.e. divide into files based on session ID), then sort the lines in each individually, then merge the results back together.
This is what map/reduce frameworks are made to do, of course, but something like Hadoop may be overkill unless you plan to do this type of thing often.