Data sorting world record: 1 terabyte, 1 minute(scienceblog.com)
scienceblog.com
Data sorting world record: 1 terabyte, 1 minute
http://scienceblog.com/36957/data-sorting-world-record-falls-computer-scientists-break-terabyte-sort-barrier-in-60-seconds/
5 comments
the size is given because one can understand how many machines it would take to hold the data in the memory, how much bandwidth is required to move data around and latency.
Its hard to understand if you are just a programmer, a computer science graduate can easily identify with size in bytes since they represent accurate amount rather than vague billion entries.
In later case you need to specify two variables size of entry and number of entries.
the larger entries become the easier is to sort them, if they get smaller then you can have an O(n) sorting ability.
The 100 byte records is fixed in literature and well understood by practitioners, what you are experiencing is your naivete.
Its hard to understand if you are just a programmer, a computer science graduate can easily identify with size in bytes since they represent accurate amount rather than vague billion entries.
In later case you need to specify two variables size of entry and number of entries.
the larger entries become the easier is to sort them, if they get smaller then you can have an O(n) sorting ability.
The 100 byte records is fixed in literature and well understood by practitioners, what you are experiencing is your naivete.
That's pretty impressive. Back in 2008, Google did a 1TB sort in 68 seconds (http://googleblog.blogspot.com/2008/11/sorting-1pb-with-mapr...), breaking the previous record of 209 seconds (which I think was done on Yahoo's Hadoop cluster)
I expect these aren't quite comparable (the op link talks about it being non-generalized data), but it's interesting how these high performance numbers are becoming more achievable.
I expect these aren't quite comparable (the op link talks about it being non-generalized data), but it's interesting how these high performance numbers are becoming more achievable.
Here is a link the tech specifics from the TritonSort team (PDF) http://sortbenchmark.org/tritonsort_2010_May_15.pdf
Here's Google's cached copy: http://webcache.googleusercontent.com/search?q=cache:2fmfGIe...
To break the terabyte barrier for the Indy Minute Sort, the computer science researchers built a system made up of 52 computer nodes. Each node is a commodity server with two quad-core processors, 24 gigabytes (GB) memory and sixteen 500 GB disks — all inter-connected by a Cisco Nexus 5020 switch.
That's some pretty impressive hardware. Must've been pretty fun. Not something just anyone gets to work on. :)
That's some pretty impressive hardware. Must've been pretty fun. Not something just anyone gets to work on. :)
it's hard to infer if the record is being set due to better hardware or better algorithms. I'd like to see benchmark improvements in algorithms not hardware, but I'm a software guy.
It's hardware. They have have 52 servers, each with 16 disks which I assume are capable of I/O at 100MB/s. That's an aggregate disk I/O rate of 83.2 GB/s. Their network switch provides 10Gbps connectivity between each pair, which implies they can move data between nodes at 65 GB/s. With that hardware setup they can read 1TB from disk and distribute in around 15 seconds. They can write sorted data back to disk in 12 seconds. That leaves a little over 30 seconds for each node to sort 19.2 GB in memory. But each node has 8 cores, so each core has to sort 2.4 GB in 30 seconds. I've seen Burstsort chew through that amount of data in half the time.
That's a blunt pronouncement. It sounds very much like software improvements played a role:
"We asked ourselves, ‘What does it mean to build a balanced system where we are not wasting any system resources in carrying out high end computation?’” said Vahdat. “If you are idling your processors or not using all your RAM, you’re burning energy and losing efficiency.”
From personal experience, the hardest part of dealing with super-high-end hardware is utilizing the capacity that it gives you. You don't just throw a larger computer at a program written in Blub for a smaller system, and gain instant world-record performance. If nothing else, you usually have to re-architect your code to match the assumptions of the new hardware.
Also, the I/O numbers you're assuming are probably very high: you never get 100% utilization of a network interface -- 70% is more realistic. And for a problem like this, you're bounded not by the product of the bandwidth of the pairwise interconnects (i.e. (10Gbps * 52) / 8 == 65GB/s), but the bandwidth of any single interconnect, because you can get to a point where you're transferring most of the data across a few connections. Also, latency matters a lot, because a small connection latency can easily throttle your overall bandwidth when you're moving lots of small chunks of data.
Realistically, these guys probably had something more like 7Gbps / 8 = ~.88 GB/s bandwidth between nodes, not counting latency. That means that it would take ~1163s to transfer 1TB between any two nodes -- which means that that naive solution (distributed merge sort where the intermediates are transferred between nodes) is already ruled out. So, like I said, we're back to software improvements, if only to utilize the hardware available.
"We asked ourselves, ‘What does it mean to build a balanced system where we are not wasting any system resources in carrying out high end computation?’” said Vahdat. “If you are idling your processors or not using all your RAM, you’re burning energy and losing efficiency.”
From personal experience, the hardest part of dealing with super-high-end hardware is utilizing the capacity that it gives you. You don't just throw a larger computer at a program written in Blub for a smaller system, and gain instant world-record performance. If nothing else, you usually have to re-architect your code to match the assumptions of the new hardware.
Also, the I/O numbers you're assuming are probably very high: you never get 100% utilization of a network interface -- 70% is more realistic. And for a problem like this, you're bounded not by the product of the bandwidth of the pairwise interconnects (i.e. (10Gbps * 52) / 8 == 65GB/s), but the bandwidth of any single interconnect, because you can get to a point where you're transferring most of the data across a few connections. Also, latency matters a lot, because a small connection latency can easily throttle your overall bandwidth when you're moving lots of small chunks of data.
Realistically, these guys probably had something more like 7Gbps / 8 = ~.88 GB/s bandwidth between nodes, not counting latency. That means that it would take ~1163s to transfer 1TB between any two nodes -- which means that that naive solution (distributed merge sort where the intermediates are transferred between nodes) is already ruled out. So, like I said, we're back to software improvements, if only to utilize the hardware available.
I should add that it's the massive network switch that makes this all possible. You can scale disk I/O by adding disks, and you can scale in-memory sorting by adding cores and memory. But it's awfully expensive to buy your way out of a bottleneck in your network when everyone needs to talk to each other at full speed.
I was under the impression (could be remembering something wrong, however) that sorting algorithms had a provable (or at least strongly believed) best-case of O(nlogn), and that we already have algorithms that meet that.
If that is correct, most improvements would probably come from hardware and software use-case tuning.
If that is correct, most improvements would probably come from hardware and software use-case tuning.
Big-O notation is a theoretical tool, it's somewhat useful in practice but it won't necessarily tell you which of two algorithms is faster. It doesn't tell you about cache performance, memory requirements, or even if there's a large coefficient on that n * log(n) term.
That's for comparison-based sorting algorithms (i.e. sorting objects where the only information you have about them is whether one object is "bigger"/"smaller" than the other. For objects where you have more information about the object (i.e. integers) you can sort faster. My supervisor for my Master's Thesis did just that: http://www.drdobbs.com/184404062
yes its an engineering exercise.
They imply that it's largely software, but obviously the hardware is not the same. If they actually reduced power consumption by 75% then it's pretty interesting regardless of what the mix is.
I don't know why they measure in bytes, which is nearly meaningless. I can sort a single 1TB record in my head right now. There, I'm done.