Sorting 39GB for a Penny

Bradley C. Kuszmaul MIT CSAIL, Tokutek Inc., Cilk Arts Inc., and MIT Lincoln Laboratories May 1, 2007
Abstract I sorted 39GB for a penny using a cheap general purpose processor and two disk drives, running each drive at about 28MB/s sustained. No special-purpose processors, such as GPUs, were employed for the in-memory part of the sort. The sort is a general-purpose sort that can compare records of arbitrary size, and does not rely on the keys being uniformly randomly distributed.

1 The Algorithm

My sort, called TokuMergeSort, employs a classic a two-step merge sort, similar to the one used by Gnu Sort [1]. The rst step splits the data into small sorted les (sometimes called runs). The second step merges the small sorted les to produce the output. The input le and the nal le are stored on one disk, and the temporary les are stored on another disk. TokuMergeSort employs multithreading to keep the different disks busy, and it employs a priority queue to merge hundreds of les in one pass efciently. In contrast, Gnu Sort is single threaded and uses an inefcient data structure for merging, which means that Gnu Sort requires several passes to merge hundreds of les.

Splitting

The splitting step repeatedly reads a buffer full of data from the input le into main memory, sorts the buffer in main memory, and then writes the sorted data to a temporary le. At the end of the splitting step TokuMergeSort has constructed several hundred sorted les. As shown in Figure 1, TokuMergeSort creates three threads (using pthreads): a reader thread, a sorter thread, and a writer thread. TokuMergeSort also allocates three buffers. At any given time the reader is reading into a buffer, the sorter is sorting a buffer, and the writer is writing a buffer. TokuMergeSort sets up three queues to communicate between the threads. The reader thread tries to keep the input disk busy, the writer thread tries to keep the output disk busy, and the sorter thread tries to keep the CPU busy sorting. I built both Indy and a Daytona implementations of TokuMergeSort. Both versions of the TokuMergeSort splitter employ quicksort [3] for the in-memory sort of a single buffer. My Indy version takes advantage of knowledge that the records are 100 bytes and that the sort key is the rst 10 bytes, and that the sort key is random. The Indy sort rst sorts small records each comprised of only the sort key and a pointer, and then permutes the 100-byte records in place. This permutation simplies the writer threads job, since the buffer is fully sorted. My Daytona version sorts records of varying sizes, uses the entire record as a sort key, and does not rely on the sort key having any particular distribution (e.g., it works just as well on nonrandom keys.) The sorter thread simply sorts pointers to the records, and does not permute the actual data. Instead, the writer thread must permute the data as it is being written to the temporary le. The readers complexity also increases slightly, since the end of a record may not align with the end of the buffer, but this complexity has almost no impact on performance. Figure 2 shows the time breakdown for the two versions of the splitter. The reader thread dominates the performance. The Daytona sorter thread takes about 50% more CPU cycles than the Indy sorter thread, but the sorter thread
work is sponsored in part by NSF grants CCP-0621511 and CCF-0541209.

reader thread

sorter thread

writer thread

Figure 1: The TokuMergeSort splitter step is implemented by three threads. A reader thread, a sorter thread, and a writer thread. Three buffers of data are cycled between the threads by using three queues. The reader thread reads into a buffer, and then enqueues it for the sorter. The sorter thread dequeues the buffer, sorts it, and enqueues it for the writer. The writer thread dequeues a sorted buffer, writes it to disk and then enqueues the buffer for the reader to rell. is still idle more than half the time. The writer gets slower, but since the disk I/O for writes occurs asynchronously to the calls to write, it turns out that the writer thread is still idle. (That is, the kernel itself is running threads that actually perform the disk writes.) Thus the Indy and the Daytona sort run in about the same time. The two disks on this system cannot compete with last years 59GB Indy sort [2], but they are good enough to outperform last years Daytona Pennysort winner [4] using only two disks (instead of 4) and 512MiB memory instead of 1GiB memory. The input le and output le together are too big to t one disk. Deleting the input le takes about 50 seconds. An alterantive would have been to trim the input by 6GB using ftruncate(), which takes 13s instead, and gives a total sort size of 40GB for a penny. Sincen Since such trimming is too special purpose for the Daytona, I can only claim the 39GB rate.

Merging

The merging step merges the temporary les to produce the nal output le, and deletes the temporary les. The merger employs a priority queue built using a heap [5]. The merger creates a small buffer for each of the hundreds of temporary les, and then places the buffer into a priority queue sorted by the sort key. The merger repeatedly removes the buffer with the smallest key, writes its line to the output le, adjusts the buffer to contain the next line, and then reinserts the buffer into the priority queue. When the buffer becomes empty, the buffer is relled from disk. A heap implements a priority queue with O(log N) comparisons per reinsertion, where N is the number of 2
read time sort CPU time write time
Indy 1203.8s 388.2s 748.0s
Daytona 1210.0s 580.6s 828.6s
Figure 2: Time breakdown for Indy vs. Daytona splitter. These are the times that the respective threads (reader, sorter, and writer) were busy performing their tasks. Each thread spent the rest of its spent waiting on the queue for the previous step to complete. step split trim input delete input merge remove temporaries total elapsed time time budget elapsed time 40GB 1304s 13s 1482s 55s 2854s 2863s 39GB 2703 2863
Figure 3: Elapsed time for 40GB sort (trimming the input just enough to t the output on disk), and for 39GB sort (deleting the input).
open temporary les. In contrast, Gnu Sort [1] creates a buffer for each open le, and then repeatedly scans all the buffers to nd the smallest key, and then outputs that line. Thus Gnu Sort implements a priority queue where each operation takes time O(N) for each line, and so Gnu Sort constructs a merge tree in which 16 les are merged into a bigger le, and then 16 of those larger les are merged into a bigger le, and so forth. Hence the merge phase of a terabyte sort would require two to three passes over the data. Because TokuMergeSort uses an efcient priority queue, it can merge many hundreds of les in a single pass. The merger is organized as two threads, a merge-reader, and a merge-writer. The merge-writer removes lines from the priority queue, and writes them to the output. The merge-reader rells the buffers. The merger performs double-buffering. For each open temporary, two buffers are allocated. One buffer is being consumed by the merge-writer, and the other buffer is being relled by the merge-reader. The merge-reader lls one buffer at a time, and is idle for a total of only 10.2s (out of about 20 minutes for the merge phase), which indicates that the reader the performance-limiting thread. The elapsed time for TokuMergeSort is broken down as shown in Figure 3.

2 Conclusion

Figure 4 shows my hardware conguration. The system comprised a dual-core AMD 64 processor and two ATA disk drives. I placed the two disk drives on different ATA channels, so they showed up in Linux as /dev/sda and /dev/sdc. I purchased the cheapest processor I could nd (which surprisingly is dual-core), the cheapest disks I could nd (80GB Deskstar with 2MB caches), and the cheapest infrastructure I could nd (motherboards, cases, fans, and power supplies.) The TokuMergeSort Daytona penny sort program demonstrates that sorting performance on simple hardware is very cost effective. No special purpose hardware (such as a GPU) is needed to speed up the in-memory part of the sort. Only two disk drives are needed to achieve good performance, and using additional disk drives to amortize the cost of the processor and power supply would provide only a small performance advantage. The cheap microprocessors of the future are likely to provide 4, 8 or more cores and increased memory bandwidth, further reducing the impact of processor performance on sorting. 3
Component AMD Athlon 64 X2 Dual Core Processor 4200+ 2GHz (512KB cache/core) 512MB DDR 500MHz PC3200 Hitachi HDS728080PLAT20 80GB disk drive, 2MB cache (2 at $39.50 each) ASUS a8v-xe socket 939 k8t890 atx amd motherboard CPU Fan Cooler Master RR-KEEE-LEE1-GP Case 11.99 (POWMAX MM3800) powersupply 9.99 (JPAC ATX500 ATX 5000 W Power Supply) fan 1.99 Logicsys Computer 80mm case fan Software: Redhat Fedora Core 6, Linux 2.6.19-1.2895.fc6 SMP Assembly Total price Time budget: 94608000s/32908cents =
ewiz.com price $93.73 30.39 79.00 52.02 6.18 22.66 9.99 1.44 0.00 35.00 $330.31 2863s/cent
Figure 4: Hardware used for the TokuMergeSort Penny Daytona entry

References

[1] Gnu sort. http://www.gnu.org/software/coreutils/, 2006. [2] Naga K. Govindaraju, Jim Gray, Ritech Kumar, and Dinesh Manocha. GPUTeraSort: High performance graphics co-processor sorting for large database management. Technical Report TR-2005-183, Microsoft, November 2005. Revised March 2006. [3] C. A. R. Hoare. Quicksort. Computer Journal, 5(1):1015, 1962. [4] Xing Huang and BinHeng Song. Bytes-split-index sort (bsis). http://research.microsoft.com/barc/ SortBenchmark/BSIS-PennySort 2006.pdf, April 2006. [5] J. W. J. Williams. Algorithm 232 (heapsort). Communications of the ACM, 7:347348, 1964.