how about not using a mechanical disk.
solid state seeks are like 10 or 50 times faster.
How to speed up massive data analysis by eliminating disk seeks
11–20 of 28 posts
Re: How to speed up massive data analysis by eliminating disk seeks
#12is it really faster to write to a bunch of text files, sort them to a new bigger text file, and then do the insert? seems like a lot of extra steps, all involving a lot of reading and writing..
Re: How to speed up massive data analysis by eliminating disk seeks
#13You can even combine this approach with split and parallel make to do a cheap single-machine parallel sort. I use a little script that generates a Makefile that can be called with make -j n that splits an input file, sorts the parts, and then merges them with sort -m. It's proved to be quite handy.
Re: How to speed up massive data analysis by eliminating disk seeks
#14how about not using a mechanical disk. solid state seeks are like 10 or 50 times faster.
because (as it says in the article) he's running on EC2 and it isn't an option.
Re: How to speed up massive data analysis by eliminating disk seeks
#15This is precisely how data is stored in ranges within HBase/Hypertable. Your data is also sorted between mapping and reducing.
Re: How to speed up massive data analysis by eliminating disk seeks
#16[deleted]
Re: How to speed up massive data analysis by eliminating disk seeks
#17I'm certain I'm re-inventing the wheel with this approach, but I obviously haven't been researching in the right places, since I hadn't run across this approach before I cobbled it together. I'm expecting an education on what I'm missing from the HN community!
The "external sorting" chapter of TAoCP might also be interresting in this context (5.4 in Vol. 3), even though Knuth thought that "the once-crucial topic of patterns for tape merging has become of limited relevance to currnt needs" (p. 251) due to the rapid development of disks in the 80s and 90s, so that his exposition might "be their last grabd appearance before they acept a final curtain call." Little did he know that disk would soon become the new tape...
To his credit, he ended the introduction to the chapter with the citation "for all we know now, these techniques may well become crucial again."
Re: How to speed up massive data analysis by eliminating disk seeks
#18is it really faster to write to a bunch of text files, sort them to a new bigger text file, and then do the insert? seems like a lot of extra steps, all involving a lot of reading and writing..
It depends. For example, what's the balance between reading and writing, how stream-oriented your processing is, how important is random access between different records, etc.
This approach can be easily augmented too. For example, doing a binary search for a particular line in a text file when you don't have all the lines in RAM is somewhat tedious; it can be made much easier by creating a simple index for the file, consisting of a flat array of the file offset of every line start. That flat array can be stored in a file also; then, both the total number of lines and the contents of a line at any given index are trivial to retrieve.
If you have to handle a small number of updates while still handling lots of reads, then you can use a two-layer approach. Keep a cache of all pending updates in memory in an efficient manner (e.g. hash table), and look up the cache before falling back to the disk; and when writing, both update the cache and write out to an update log, which can be sorted and included in the main store later, when it makes sense.
Re: How to speed up massive data analysis by eliminating disk seeks
#19I'm certain I'm re-inventing the wheel with this approach, but I obviously haven't been researching in the right places, since I hadn't run across this approach before I cobbled it together. I'm expecting an education on what I'm missing from the HN community!
Column stores (http://en.wikipedia.org/wiki/Column-oriented_DBMS) have been designed specially for this case. There are a few ones (monet, cstore) but the really good ones are sadly $$$.
That said, their ideas are quite straightforward and you could look them up quickly (I forgot the blog I was thinking about, but check also here: http://www.vldb.org/ ).
Re: How to speed up massive data analysis by eliminating disk seeks
#20I'm certain I'm re-inventing the wheel with this approach, but I obviously haven't been researching in the right places, since I hadn't run across this approach before I cobbled it together. I'm expecting an education on what I'm missing from the HN community!
I've had a similar problem when dealing with a relatively large data set (in a consumer PC context) that really really needed random access. I was using sorted text files with indexes (flat array of line start offsets), but eventually I redesigned to use a (Patricia) trie, so that I could store all the data in memory.
Crunching the data down in size to make it both small yet low-cost to extract was then the challenge. I started out with sorted text files on the order of 550MB, and ended up with memory dumps of efficiently packed tries on the order of 95MB, with further scope for compression possible through huffman encoding of markov chains (encoding letter transition probabilities with a path through a huffman binary tree), that I didn't need to implement because I had already achieved my goals.
The trivial parallelization available through sorting massive text files is hard to beat, though, especially as you can write ad-hoc bash scripts to do work with sort, uniq, sed, etc.