Slashdot Mirror
Data Sorting World Record — 1 Terabyte, 1 Minute
An anonymous reader writes "Computer scientists from the University of California, San Diego have broken the 'terabyte barrier' — and a world record — when they sorted more than a trillion bytes of data in 60 seconds. During this 2010 'Sort Benchmark' competition, a sort of 'World Cup of data sorting,' the UCSD team also tied a world record for fastest data sorting rate, sifting through one trillion data records in 172 minutes — and did so using just a quarter of the computing resources of the other record holder."
I have one record of size one terabyte.
Sort by size.
It is already sorted.
Sort finished. time: 0s! WTH!
In soviet Russia, God creates you!
As long as you use Intelligent Design Sort.
I had a 6502 system with BASIC in ROM and a machine code monitor. The idea is to copy a page (256 bytes) from the BASIC ROM to the video card address space. This puts random characters into one quarter of the screen. Then bubble sort the 256 bytes. It took about one second.
For extra difficulty do it again with the full 1K of video. Thats harder with the 6502 because you have to use vectors in RAM for the addresses. So reads and writes are a two step operation, as is incrementing the address. You have to test for carry. But the result was spectacular.
http://michaelsmith.id.au
Data Sorting World Record -- 1 Terabyte, 1 Minute
The fact that they needed a computer should disqualify them.
TFA variously refers to 1 trillion records and 1Tb of data. So each record is 1 byte?
Doesn't seem like that requires any real computation - you just go through the data maintaining a count of each of the 256 possible values (an embarassingly parallel problem), then write it back out with 256 memsets (likewise trivially parallelisable).
You almost think at this point that with super fast systems attention to algorithmic complexity hardly matters, it's good to see research still advancing and that there are areas where carefully designed algorithms make a huge difference. I look forward to seeing how they fare against the Daytona set.
"There is more worth loving than we have strength to love." - Brian Jay Stanley
How many parallel predicting octopuses were required to predict their victory?
134340: I am not a number. I am a free planet!
You've got to be kidding me. Each node was only 2 quad core processors, with 16 500GB drives (big potential disk IO per node) but this system doesn't even begin to scratch the very bottom of the top 500 list.
I just can't image that if even the bottom rung of the top 500 was even slightly interested in this record, that they wouldn't blow this team out of the water.
The cesspool just got a check and balance.
LARPers > Fan-fiction writers > Professional Data Sorting Competitors > Furries
The most important part of any system, is its Intelligent Qube.
I'm pretty sure that modern analytical DW systems like Greenplum or Teradata on the same number of nodes/RAM/disk/commodity servers could do this faster?
"a sort of 'World Cup of data sorting"
It ended in a 0-0 tie?
Why is sorting 1TB so hard?
I can just instruct my tape library to put the tapes in the library in alphabetical order in the slots... Y'know AA0000 AA0001 AA0002... moves a hell of a lot more than 1TB.
Is it sorted?
Did they sort the best case input and claim record? Or is it the average or worst case? Or the algo's best case time == worst case time?
When I read the summary I thought what's the big deal if the 1 TB of data only contained two records 0.5 TB each. Then I saw that kdawson wrote the summary. So I browsed over here and saw that the impressive thing is that they sorted 1,000,000,000,000 records of 100 bytes each with 10 byte keys.
Considering that the previous terabyte sort record was held by Hadoop, it's not surprising that another system can do the same job in a fraction of the time with a fraction of the resources.
Hadoop a useful framework, but it's a horribly inefficient resource hog. Who was the f*ing genius who thought it was a good idea to write a high performance computing application in Java?!?
Why is it that the proponents of "one nation under God" are so eager to get rid of "liberty and justice for all"?
Come to think of it, one area where it also matters currently is in mobile development. If you aren't considering memory or processor usage you can quickly lead yourself into some really bad performance, thinking hard about how to make use of what little you have really matters in that space too.
So only desktop or smallish backend development can generally remain unconcerned these days with algorithmic performance...
I had to work with large datasets in my previous life as a backend IT guy, but nothing at the levels you are talking about. Even then I thought carefully about how any give approach would affect performance.
"There is more worth loving than we have strength to love." - Brian Jay Stanley
I think this is cool, but.... how fast is it in a more practical situation?
source
Sorting (like most other algorithms) can be optimized for run-time or memory consumption. Assuming a box with infinite memory the sorting algorithm itself doesn't take any significant run-time. Considering the low amount of memory of the test systems compared to the data to be sorted a quite significant portion of the time required is disk-IO. So the main challenge here seems to be to minimize disk-access - and to put the fastest disks available into the test system. Why aren't they simply using SSDs, this would likely speed things up quite a lot...
when they sorted more than one terabyte of data (1,000 gigabytes or 1 million megabytes) in just 60 seconds.
Each node is a commodity server with two quad-core processors, 24 gigabytes (GB) memory and sixteen 500 GB disks
Ok, let's do the math. 52 computers X 24 GB RAM each = 1248 GB. Letting aside the RAM taken by OS, that's roughly 1 TB of RAM to dedicate for the sorting.
Le'me guess: the main difficulty was to partition the data and perform a merging of the in-memory sorted partitions?
(of course I'm posting before reading the details of the method they used, it is /. after all. I guess I even merit a price for the weirdness of RTFA article before posting)
Questions raise, answers kill. Raise questions to stay alive.
Impressive and all, but I take umbrage at calling it a "1 TB barrier". Is it disproportionately more difficult than sorting 0.99 TB?
Breaking "the sound barrier" was hard because of the inherent difficulty of going faster that sound in an atmosphere (sonic booms and whatnot). It was harder than simply travelling that fast would have been.
If this is just further evolution of sorting speed, it makes it a milestone, not a barrier.
Anyway to filter out articles by KDawson without logging in?
Yes but you have to install Flash.
"I like to lick butts!" by MobileTatsu-NJG (#32700246) (Score:5, Informative)
I have to admit that I'm genuinely impressed. This rate of data processing is almost as efficient as my girlfriend when she hears, evaluates and demolishes my alibis.
I've calculated my velocity with such exquisite precision that I have no idea where I am.
Let's consider 100TB in 172 minute thing they also did. 52 nodes, 16 spindles per node is 832 spindles total and 120GB of data per spindle. 120GB of data can be read in 20 minutes and transfered in another 15 to the target spindles (assuming uniform distribution of keys). You can then break it down into 2GB chunks locally (again by key) as you reduce. Then you spend another hour and a half reading individual chunks, sorting them in memory, concatenating and writing.
Of course this only works well if the keys are uniformly distributed (which they often are) and if data is already on the spindles (which it often isn't).
In third place, with a time of 01:02.305 is Sort United.
In second place, with a time of 00:58.112 is Team Sorted.
And in first place, with a time of 00:59:836 is UCSD!
Assuming UCSD gives the algorithm to SETI, anyway, and doesn't instead go to Wall Street to be used in detecting market trends and major share movements as part of their never-ending quest to separate the small investor from their money faster.
Orwell: "In a Time of Universal Deceit, telling the Truth is a Revolutionary Act"
This isn't about a new algorithm, really, bit about reducing the constants in existing algorithms. As far as I know, sorting is still O(n log n), and it is reasonable to believe it always will be.
Wow, I realize I am seriously a nerd, getting genuinely excited about someone sorting large amounts of data. Please don't tell my girlfriend, she'll realize I've been faking being a semi-normal cool guy for years, and leave me.
Just put a fucking bullet in your head and you'll never have to see another kdawson article again.
Don't do it while reading one of his articles or it will be imprinted in your eyes forever.
when are we going to have access to this technology? It is always nice to hear new breakthroughs, but governments always control access to these new technologies, and make it 5 to 10 years before we see any of it, while somewhere like japan, you already have it available...
A paper describing the test is here. TritonSort is the abstract method; GraySort and MinuteSort are concrete/benchmarked variations of TritonSort.
As TFA states, this is more about balancing system resources than anything else. The actual sort method used was "a variant of radix sort" (page two of the linked PDF). Everything else was an exercise in how to break up the data into manageable chunks (850MB), distribute the chunks to workers, then merge the results. That was the real breakthrough, I think. But I wonder how much is truly a breakthrough and how much was just taking advantage of modern hardware, since one of the major changes in MinuteSort is simply avoiding a couple of disk writes by keeping everything in RAM (a feat possible because that much RAM is readily available to a single worker).
Regardless, this kind of work is very cool. If web framework developers (for example) paid greater attention to balancing data flow and work performed, we could probably get away with half the hardware footprint in our data centers. As it stands now, too many COTS -- and hence, often-used -- frameworks are out of balance. They read too much data for the task, don't allow processing until it's all read in, etc.. This causes implementors to add hardware to scale up.
Hell, I can sort a terabyte of data in less than a second. As long as the records are a terabyte long.
upon hearing that news... ....
and so did
credit companies
banks
and other overlords
http://webcache.googleusercontent.com/search?q=cache:2fmfGIe5xN8J:sortbenchmark.org/tritonsort_2010_May_15.pdf+tritonsort&cd=1&hl=en&ct=clnk&gl=us
Hail Eris, full of mischief...
E pluribus sanguinem
Who cares about the time it took?
Show me the big-oh notation for the algorithm or I am simply not interested.
I bet they mandated Java, used a prototype algorithm or generic library, assigned a tiny slice of a shared virtual server, jacked the virtual memory, and rushed it to production, then threatened their employees until they made it execute in under a minute.
It's not the number of bytes that's important, it's the number of records and the size of the sort keys.
I can take two records of 0.5TB each and sort them quickly - very quickly if their sort keys are short.
The summary and article headline said "a terabyte" but the article says "They sorted one trillion data records." This is impressive with today's hardware. It will be child's play with hardware from "the day after tomorrow."
Knowledge is how to play a game, intelligence is how to win, wisdom is knowing what game to play.
I once read that bubble sort is the optimal sort on a Turing machine. Too bad it wasn't named tapeworm sort, then every student would understand immediately. It would be analyzed alongside dining-philosopher chopstick sort, where the dining philosopher won't each (finicky like Tesla) unless holding a matched pair, with the option of swapping hands if holding a pair of sticks before release.
If the purpose is to teach analysis of algorithms under different computational assumptions, there's nothing wrong with teaching bubble sort. When it gains rank in the panoply of commercially viable sorts, that's where the problems begin. But since when did academia much care about A) carefully informing you about the importance of the material they were teaching you, or B) the grim realities of commercial applicability.
Extreme adherence to practicality made C++ what it is today. All software for the F22 and F35 are written in C++. Not Haskell or LISP. The beautiful languages are the languages best suited to reject design iteration on practicality. If it's not very practical to begin with, why mess up a good thing? C++ never had that problem.
What my university failed to teach properly was radix-sort, which is both practical and of theoretical interest. If the time devoted to bubble sort had instead been devoted to radix sort, the astute reader would know that record length is a critical parameter in this benchmark protocol.
Hell, give me a one-bit record length and some fast disk drives, I could sort a terabyte at the same speed as UCal using a single loop of RS485 multidrop instead of that overpriced Cisco kit.
Don't bother reading TFA. It does not report the sort protocol record length.
"...100 terabytes of data is roughly equivalent to 4,000 single-layer Blu-Ray discs, 21,000 single-layer DVDs, 12,000 dual-layer DVDs or 142,248 CDs ..."
that is the space my pr0n takes up
- This can't be... - Be what? Be real?
abeertty There. 15 seconds.