Shoestring Budget? Starting to feel growth issues on your back-end? Embrace unix and C
Our site is a search engine - like google, but for flash content. We threw together the site in a weekend and have been slowly tweaking it over time but recently have run into some growth issues. If you have funding or investors and have growth issues, you can just throw more hardware at the problem and ta-da! You're fast again. However, for those of us who don't have money being thrown at us, we have to be a little more creative and start to look at optimization.
I've got a couple of old machines and an 8-drive SCSI RAID in my basement that I'm using for our search engine to crawl the web and process the data that we index for our search engine. My machines are not quad-core and don't have 64GB of ram in them. They're old and tiny.
When we first put http://mediawombat.com together, we threw it all together just to get it to work. We did everything as quick and dirty as we could. We used perl and mysql for the back-end. The crawler was straight-forward, single-threaded, slow, clunky, but it worked. After about 4 months of collecting data, we started to see some growth issues. Searches were becoming slow.
We were using a live search through all of our indexed data. First step to optimization - caching of course. This was a pretty easy no-brainer. We recorded all of the searches that people did on our site and we pre-cached the search results for the top-2000 of the most-popular searches. This way, when someone does a search for a popular search phrase, they get (almost) immediate results. Not too bad of a solution.
Just a few weeks ago, I noticed that our crawler has become the slowest part of our back-end process. We had crawled most of our initial sites and gotten some good data back, but now, the crawler is just crawling lots of uninteresting urls and not getting anything of any value back. We overflowed onto other sites with no flash and were now crawling sites that didn't return any useful data back. We were wasting resources.
So, I was at my mother-in-law's place last weekend and she doesn't have any internet connectivity. I was bored and needed some time away from the family to geek-out. I thought to myself how I could make the back-end crawler and database more optimized ... I re-wrote the crawler in C and made it multi-threadded. And instead of reading and writing to a database, I used flat files. I also pre-processed everything outside of the database using the old-style unix text utilities (grep, sort, uniq, sed, awk, ...). One of those cartoonish lightbulb-over-the-head moments happened to me.
The unix text utilities were written in the 60's and 70's when computers were 33mhz and had 5MB of ram. Of course these utilities are going to be lean and mean! Perl was a memory hog and if I multi-threadded it, ate up most of my available ram on my machine if I spawned > 5 threads.
I read the man pages on all of the unix text utils that I could find. I even found some new ones that I didn't even know about before (and I've been using unix (linux) as my primary OS since 1990). I managed to replace about 90% of my crawler that was previously written in perl, to a bunch of unix utilities, a few shell scripts and my multi-threadded crawler in C. I did my crawling operations in bulk and processed them in the background while the crawler was doing it's thing.
I was super-proud that I had optimized the code as much as I had. I went from about 30k urls a day to about 60k urls crawled an hour! To me, that was a huge speedup! Anyway, to make a long story short, I'm still looking for ways to optimize things and I've got a long list of things to do if/when the time becomes available and I've got more time than money at this point so it's worth the effort, and it's really rewarding!
122 comments
[ 2.7 ms ] story [ 209 ms ] threadI'm not positive (I was born in the 70s), but I'm pretty sure they had less RAM and speed than this.
Unix can be really small, if we sacrifice some stuff.
Damn, do I feel spoiled watching a modest app compile in a few seconds today!
It served around 40 terminals.
I wonder what the result would be if you did everything you describe, but wrote the code that's now in C, in Python instead. I suspect the speed would be very similar. (I like C, for what it's worth.)
Is that a joke?
1. Spawn some threads (Python uses native threading) 2. Connect to and load some URLs (This isn't going to be slow anywhere.) 3. Run some regular expressions (Python's regexp engine is all C) 4. Write to the disk. (Python uses the standard system libraries for this)
It wouldn't be as fast, but it might be surprisingly close. There would be fewer lines of code to boot.
The problem would be the GIL (Global Interpreter Lock). You couldn't actually have more than 1 thread running at a time. It sounds like the man only has 1 processor, so that wouldn't be the end of the world, but if he has more, you can just swap in the process module for the threading module. Of course, then you might have some RAM issues.
Twisted is one way, but Python ships with asynchronous libraries http://docs.python.org/lib/module-asyncore.html.
Not actually true; socket calls release the GIL when they're not active, as do many of python's C libraries. Especially the better-written standard ones.
The GIL is not as big of a problem as most people see it, it only interferes with CPU bound, highly parallelizable tasks.
Switching from a scripting language to C doesn't mean an automatic huge speed boost. It depends where your time is being spent.
Next step, get rid of those threads and use non blocking IO ;)
I'd definitely agree though with the OP... having limitations forces you to look at better ways to do stuff, and ways to squeeze every last drop out of the hardware/resources.
Java is a popular, hyped language. It's just not a very good one.
Second, for more perf analysis, there are some very good unix tools for profiling & optimizing C code. Many of them free.
This is great news and a great way to spread the word about your service. Don't let that opportunity go to waste!
I think you'd better get a doctor to look at that.
If your crawler is I/O-bound, then just wait till you discover epoll :)
Or, on a more general note, have a look at http://www.kegel.com/c10k.html
I thought that most of these solutions deal with CPU-bound and sometimes RAM-bound situations -- i.e. they fix spending too much time spinning the CPU in various ways waiting for I/O, or too many threads at once taking up too much RAM.
The general method appears to be, write the program using an event model, then create a thread per CPU, which each thread waiting on epoll() (timeouts optional).
From what I understand (and how I've used it in my work), one uses epoll() specifically because they're NOT I/O-bound and so need to come up with strategies for using the minimum amount of CPU and RAM per simultaneous I/O so as to avoid becoming CPU- or RAM- bound.
Hence my original point -- if one is I/O-bound while using poll(), it doesn't really matter whether the CPU is spinning on that or epoll(), since I/O won't happen any faster.
Alternative arrangement is to have a single IO thread that deals exclusively with getting data off the wire and multiple "worker" threads that handle the actual processing. I like this model better, because it provides cleaner logic separation, run-time threading control and it has several other advantages. Though "your experience may vary".
Lots of companies take this approach, of Python + C/C++. A few that come to mind are Google, Weta, ILM, iRobot, and Tipjoy.
Most of the language is closely tied to "tables", which are very similar to Python's dictionaries. Unlike Python, however, it has real closures and tail call optimization.
"userdata" are first-class values in Lua. They are containers for pointers to arbitrary C structures, and by overloading their behavior it's extremely easy to interface between C and Lua.
Lua tables are extremely elegant, and are the basis of object and class systems, all data structures, namespaces, packaging, and libraries.
The Lua interpreter is quite fast by itself, and with the LuaJIT written by Mike Pall your speeds can be even greater. The rumor is that the first public release of LuaJIT 2.0 is coming this winter... that one is a tracing compiler based on the same concepts as Tamarin, SpiderMonkey, and V8.
I read The Implementation of Lua 5.0 (www.tecgraf.puc-rio.br/~lhf/ftp/doc/jucs05.pdf, 15ish page pdf) last week, experimented some with _Programming in Lua_ 2nd ed. since, and I've been very impressed with how tasteful the overall language design seems. It seems like a brilliant tiny language, much like Forth and its descendants. (I've read that the Lua source is good reading, too. See: http://www.reddit.com/comments/63hth/ask_reddit_which_oss_co...)
The Lua Emacs mode is nothing special, but I'll see if I can improve it. :)
The nice thing about Inline is that the bindings are obviously named (function foo() in C becomes sub foo in Perl), and it's all automagic. Of course, if your C/C++ code is big or an existing library you want to bind to rather than just a few bits and pieces, perlxs (and its related utilities) might very well still be the way to go. There is XSpp, which supposedly makes C++ and XS play nicer together. But perlxs is dramatically better than SWIG in most circumstances I can think of (I don't mean to imply that SWIG is not a wonderful tool--it's a fantastic tool, but both Perl and Python have language-specific solutions to most of the same problems that are superior).
But you can't beat Inline::C (and I guess Inline::CPP) for simplicity. If you know both Perl and C/C++ their usage is absolutely obvious. perlxs requires a little more reading, and I have to consult the docs whenever I cross paths with it. Python has Weave (part of SciPy), if you like the inline model, though I'm not sure it's being maintained heavily these days.
If large data sets are your problem (some of the things you might use the numeric data structure tools in Boost for), PDL might be a solution, since it has a lot of tools for manipulating large data sets without having to revert to writing your own C. Likewise NumPy in Python. And, of course, there are already Perl bindings for Boost in CPAN, though the vast majority of Boost seems to be just making C++ more like Perl, rather than adding anything that Perl coders would find interesting.
It lets you use arbitrary c libraries in Python. It automatically does the wrapping for you.
There are also pretty big costs associated with shell scripted processing, like spawning a new shell for every command (while Perl, Python, etc. do not, unless you're explicitly forking). While there was a thread about programmers greps a few days ago, and out of curiosity I compared find+grep to grin and ack, and found that find piped to grep required a quarter the time of ack (written in Perl) and more than an order of magnitude less time than grin (written in Python) to perform a simple search, I also know that for more complex cases the cost of shell-based processing grows as complexity grows.
For an interesting comparison, look at the GNU autotools vs. cons (in Perl) or SCons (in Python). Both cons are dramatically faster than the autotools. Partly because they aren't as complex and don't target quite as many build systems, but also partly because they do most everything from a single running process.
had to be root to raise the user's maxproc-max (previous experiments locked me out --- "sh can't fork" messages ... can't even ssh in)
it's done in a 100mbps amd2000+ 256 mb 40 GB IDE OpenBSD colo ... but i don't think the hardware matters that much (the cilk is really the key)
Rewriting something in C should be the last thing you do, not the first. The first thing you should do is find out why it's slow. In your case, it sounds as though you were fetching one url at a time (blocking). Switching to async io all could have fixed this.
Btw, if you're using the Gnu utilities, it's unlikely that they were written in the 60's and 70's (also, people were processing much smaller amounts of data back then).
Also, I'm 40 years old. When I went to college, C programming was the norm, so it wasn't that difficult for me and didn't take long to implement and seemed like a great place to start to optimize things. It's fast, saturates my home Comcast pipe (they might cap my bandwidth, which I'm now worried about) and takes about 200M of memory with 30k URLs loaded into the queue. I suppose that I could reduce the memory requirements of the app some more by keeping the URLs in a BerkDB or something, but I think that 200m is acceptable for my needs now. For me, it's all about getting the most out of my available resources without throwing more money at it.
Re: gnu utils and 60's and 70's comments ... Yea, I admit that my knowledge of the gnu utils started in 1990 and I know that unix has been around since the 60's, so my initial post stating that the utils have been around since the 60's and that CPU speed and memory sizes were larger than they actually were back then were incorrect. My bad. ;)
root 6984 3.0 0.5 215832 5168 pts/5 Sl+ 12:59 0:00 ./crawl
I'm using a linked-list in C to store all of the queued-up URLs so all of the threads can mark them as being worked on or whatever. Also, the app and curl lib takes a few megs too. I'm sure that the heap and multi-threadding libs are responsible for some of the resident memory usage. :) the on-disk binary is only 12k if that make a difference. ;)
The struct:
typedef struct my_url { char * url; int retcode; double old_size; double new_size; status status; struct my_url * next; char * filename; int flashurl_id; int depth; } my_url;
I also like keeping them in memory as opposed to a BDB because of access speed - 25+ threads don't have to wait when it's all in memory, but 25+ threads hitting a BDB would be much nastier on the OS.
http://www.hpl.hp.com/personal/Hans_Boehm/gc/
I wonder if it's really more of an intimidation factor than anything (and I'm not saying this to be a jerk, I am truly curious why people have the perception that C is such a nightmare to maintain).
Second, are those garbage collectors widely used in C code and if not why?
I don't disagree, btw, that dynamic languages are easier, but I'm really wondering if C's maintenance is really more of a perception than a reality.
Or is it more likely that like most C folk, you're just stuck on execution speed as the only measure of a language or you don't know what maintainability actually means?
C's being hard to maintain is not a perception, it's a reality. If C were easy to maintain there wouldn't have been room for scripting languages to exist, everyone would have just kept using C. C is extremely low level and extremely powerful, making it hard to work in and very dangerous.
Yes you can do anything with a for loop, but I'd much rather use higher level abstractions like higher order functions, first class functions, objects, continuations, and exceptions and not be able to directly play with memory or pointers because I don't give a crap about the machine, I give a crap about abstracting and solving my problem with the least amount of necessary boilerplate or repetitive code.
Look, make it simple, assume for the sake of argument that Python and C have exactly equal execution speed under all circumstances, given that axiom, why would anyone choose C over Python? Which language do you think most people would choose?
There are "C folk" who won't use anything else because they're stuck in the rut of only thinking of execution speed, pointing that out is not a flaw, it's a fact.
http://www.p-nand-q.com/python/obfuscated_python.html http://en.wikipedia.org/wiki/International_Obfuscated_C_Code...
I would suggest that neither one is particularly maintainable, nor are either of these styles of code likely to appear in the real world. Therefore the worst case for these languages is not really more telling, and not applicable to this discussion.
By the way, a lot of these perl and python scripts spend most of their time calling into C libraries anyway, so the performance difference is often negligible.
Please, HN, change the color of text in posts like the above. There is very little contrast between #828282 (copy) and #F6F6EF (background), and I for one am sick of having to fix this with Firebug.
https://www.squarefree.com/bookmarklets/zap.html
Add it to your bookmarks toolbar, and any site you use it on will turn all text into black-on-white (in fact, it gets rid of most background colors and images), remove anything flash-based, links are changed to blue & underlined, etc.
Shell scripts are hard to make robust. I don't understand why you wouldn't just drive the unix utilities from perl.
Why use perl threads on unix? Everyone know they suck. Why not fork and use a transactional database for IPC?
I remain unconvinced of the alleged wins people have with flat file solutions. It's usually about replacing a toy like mysql or some convoluted berkelydb mess. You can use db2 for free up to 2 gigs of memory. Why waste even a minute replicating transactional RDBMS functionality by hand? As soon as you're dealing with flock and company and you COULD be using a DB, you should, as far as I'm concerned.
A simplified example: If I crawl a website, the chances are good that I'll pull several thousand copies of the same url from the site over and over again. I want to insert all URLs that I find back into the database so I can can crawl them, but I don't want any dupes. I just want to crawl the URL once and then move on. If I insert a URL into a DB and let the DB check if it's a dupe, then I waste DB time/IO. My solution was to crawl thousands of pages, dump all of the urls into a text file, run the text file through 'sort | uniq' and then dump those URLs into the DB and let the DB ignore the dupes at that level. I still have to use a DB to do some of the work, but pre-processing the data up-front using 'sort | uniq' is mega-speedier in my special case.
Also, I did wrap most of the scripts with perl to talk to mysql and do other sanity-checking that's easier in perl than bash or tcsh. :)
I agree about the built-in Unix utils. You just do not see people taking advantage of these powerful and extremely optimized programs any more. I wonder how many times grep or sort have been unwittingly rewritten in Perl or Ruby because the programmer lacked familiarity with basic Unix tools?
As for your crawler, I think the significant thing here is that you rewrote something in C after you already had it working in another language. Not to bag on C, but writing the original in a higher level language first gives you a better shot at correcting any bugs in the actual solution domain. Then if you move to C you're only fighting against C, not against C and bugs in your solution at the same time.
If you haven't yet, check out _The Unix Programming Environment_ and _The Practice of Programming_, both by Rob Pike and Brian Kernighan (K of K&R). They're concise, highly informative books about using the Unix toolset to their maximum potential. The former was written back when computers were slow and had little memory, the latter in from 1999 but very much in the same spirit. (It seems to include a lot of insights from developing Plan 9.)
Also, a dissenting opinion here: C's performance vs. higher level languages' development speed is not necessarily an either/or choice. Some languages (OCaml, the Chicken Scheme compiler, implementations of Common Lisp with type annotations or inference for optimizing, Haskell (under certain conditions...), others) can perform very favorably compared to C, but tend to be much, much easier to maintain and debug.
As a generalization, languages that let you pin down types are faster because they only need to determine casts once, at compile time, but if those decisions can be postponed until your program is already mostly worked out (or better still, automatically inferred and checked for internal consistency), you can keep the overall design flexible while you're experimenting with it. Win / win.
Also (as I note in a comment below), Python can perform quite well when the program is small amounts of Python tying together calls to its standard library, much of which (e.g. string processing) is written in heavily optimized C.
Alternately, you could embed Lua in your C and write the parts that don't need to be tuned (or the first draft of everything) in that.
Keep in mind that each language has a learning curve. As you learn more languages, that curve becomes much easier to traverse. However, the goal is to Get Stuff Done. The most straightforward engineering tactic to accomplish that is to become highly skilled with a few choice tools, then use those tools to solve almost all of your problems. (Note: that's different than a "one tool for every problem" mindset. You can solve most problems with a small toolbox while still avoiding the trap of using an inappropriate tool for the job.)
I dabble in languages for fun, but find that I ultimately end up using the new techniques I learn in a few practical multiparadigm languages, e.g. OCaml, Lisp, and Python* . If you want to learn about types/powerful type systems, try Haskell or one of the MLs. If you want to see a brilliantly designed module system, look at the MLs. If you want to see well-designed syntactic sugar, look at Python and Lua (among others). If you want to understand OO better, look at Smalltalk. Etc. Spending a week (or weekend) now and then exploring the ideas and mindsets in unfamiliar languages, particularly those influential on what you do your real work in, can really expand your toolkit. (Also, read code.)
* Python is not fully multiparadigm, e.g. it's awkward for functional programming, but it's fairly flexible, and its giant standard library makes up for several weaknesses IMO.
Really knowing any one of the several languages I listed in the initial comment would probably be enough, and some approaches (e.g. Lua in C) could probably be learned relatively quickly. I suspect it would probably take much more time to learn to use C++ really well than OCaml or Lisp, though.
I'd be interested in seeing the results of a rewrite not to C, but to python or ruby where the threading support is much much better. Then you could rewrite functions at a time in C as needed, but not have the extra burden of rewriting the whole thing.
I totally agree with the rest of the approach. Going low tech and using unix tools is a very good way to reduce overhead, increase parallelism, and delay calculations. One of the nice things about this approach is you can cobble up another $50 unix box to do some of the bulk processing via nfs or other means.
Congrats... It sounds like a very interesting project.
Could you elaborate a bit on this?
I don't have as much experience with python threads as I do ruby. I've toyed with the internals of python and perl as well and know perl to be a wasteland and python to be rather elegantly clean. So I would expect python's threads to be better implemented. Poking at it, it does appear to be so.
Ahh, that makes sense. I'm willing to bet that the vast majority of perl code runs on *nix systems (I know that with the exception of one app, all the perl I've ever written was only run on linux servers).
I can only hope that it has improved since then, but I've moved on to greener pastures.
Its called Unix For Poets and it'll show you just how far you can really push these tools.
Does your crawler support gzip compressed transfers?
What speed is your Comcast link?
Yea, the crawler uses libcurl, which supports gzip compressed content.
My comcast link is (theoretically) 7Mbit down, 385Kbit up.
If you've got some code that works well and you can solidify into c++ (ie - you're no longer tweaking it 3 times a day) - it's totally worth spending the time to rewrite.
I think C++ on rails would be a great idea, ie - some code generators to help you port your most used .rhtml views over to C++.