Read C10K? Both select() and poll() have this problem internally. You have to use one of the more advanced techniques available if you really want to scale. epoll(), kqueue() or friends.
I thought the same exact thing when I read rtm's description. I thought to myself select()/poll() is much more efficient, and it sounds like that's not what's implemented underneath.
I imagine mzscheme is using select under the hood. But I'm surprised they're not using poll. There's something up with the racket page, so I'm not able to download the mzscheme source just now (via http://arclanguage.org/install), but that's one thing I've noticed in Python web server implementations. Side-stepping epoll, libevent and all that for a second, there's a tendency to use select (which uses an array of file descriptors; 0 to highest file descriptor) instead of poll (which isn't encumbered the same way).
I think in part there is a tendency, among server developers, correctly, to fear anything that looks like a busy wait (e.g., with the name poll). But really poll is just as asynchronous as select in this context (I don't know about FreeBSD's implementation -- but Linux puts to sleep wait queues the same way, afaik). It just doesn't suffer from the crazy indexing scheme of select....
At any rate, I didn't get a chance to finish probing the internals of what mzscheme uses. But if there's a way to substitute poll for select, it can often alleviate those issues of 900 requests queue up and you eventually have an fd with a value of 1024 or greater -- even though you may not have 1024 actual concurrent requests....
Though others feel free to correct me if I'm wrong. I only comment because I came across a similar issue recently. This link may be useful too:
ETA. i finally got a copy of the most recent racket source (though probably not the one rtm and pg are using). but if anyone is curious, browse racket/src/network.c. the source version for mac uses a bunch of selects (e.g., for tcp-accept). replacing with poll might help.... the max number of FDs per login session is often 1024 by default. so you might want to bump that up if it's not already. and consider using poll.... just an idea.
Filo was a total hacker, reportedly still is. At least into the late 90's, he was active on the FreeBSD mailing lists with encyclopedic knowledge of SCSI card and NIC drivers and assorted other hardware and FreeBSD stuff. He was oft found sitting on the hallway floor in the first colo I used (ISI in Mountain View), screwdrivering the chassis' of Yahoo's early servers.
Yep. He's still a mensch. Yahoo did some incredible stuff on Apache & FreeBSD back in the day. I remember a hack that added hardcoded HTTP headers to the image files on disk, to squeeze that extra nilth percent out of the server.
Yes. Having worked at Yahoo, this isn't even a bit surprising. rtm's capitalization of 'filo' as 'Filo' -- everybody spelled it lowercase i.e., as an /etc/passwd entry not a lastname -- is the surprising part.
Regardless of what you think of Yahoo's current situation, somebody who could easily retire wealthy but still hacks and flies economy class on Southwest to meetings in remote offices is worthy of respect.
Yahoo's entire BSD kernel team report to filo still.
Last time I had lunch with him we talked about the minutia of DNS server implementations because I was working on some optimization tricks and he was really interested in seeing them get implemented.
filo is a really amazing guy. He's the most down to earth billionaire I know. He talks way more about his family and hacking more than 'stuff'. If he isn't hacking on code as much as he used to it's because he cares about his company and is doing an important job looking after technical stuff that needs doing, even if it isn't interesting.
The traffic graphs linked in this post [0] are an interesting addition to the "How often do you visit HN?" poll [1] that was done a week ago. From the graphs, it looks like there are about 10x as many page views as unique IPs.
I worked at a startup once that made a network card that did this type of buffering (wait for whole HTTP requests, then forward as a lump to the host, across a local fast bus).
Pretty whizzy, definitely helped server scaling.
We started shipping in 2001; the dot-com bust more or less canceled any interest in the product, and canceled the company, too . . .
related but a little different (just FYI): some Intel nics can handle interrupt modulation. Decreased latency but wouldn't fix the open handle/scaling issues here.
That's not the bottleneck. Essentially there's an in-memory database (known as hash tables). Stuff is lazily loaded off disk into memory, but most of the frequently needed stuff is loaded once at startup.
The bottleneck is the amount of garbage created by generating pages. IIRC there is some horrible inefficiency involving UTF-8 characters.
Maybe that's just for dynamic pages. Probably most of the most popular pages are cached and wouldn't be considered in that 20 req/sec. Just my own wild guess though.
YC ranks 2400 on Alexa, and I'm sure most of the traffic is HN. I bet you'd be hard-pressed to find a top 10k site written in Scheme. Does anyone know of one?
"It turns out there is a hack in FreeBSD, invented by Filo, that causes the O/S not to give a new connection to the server until an entire HTTP request has arrived."
I wouldn't call it a hack, but a feature ;-)
# Buffer a HTTP request in the kernel
# until it's completely read.
apache22_http_accept_enable="yes"
I think it means that your web app can survive being slashdotted. So, a lightweight C10K-capable frontend, all static content on a CDN, everything heavily cached, database queries optimized to the hilt, etc... etc... Some people think that just using a NoSQL database is sufficient, but there's much more to it. Interesting talk on this stuff (was posted on HN earlier): http://ontwik.com/python/django-deployment-workshop-by-jacob...
Would be interesting to see if traffic goes up after this and is elastic. Marissa Mayer had a talk at some conference in 2009 where she explained her early tests on number of search results on Google - 10, 20, 25, 30 - but in the end it was just about the speed associated with loading the pages that accounted for the number of pageviews and visitors.
Sounds like there is a scalability issue within MzScheme in that it iterates over the number of threads, asking each thread about the sockets it has. As one can tell, once # of threads and # of sockets grow - finding which thread to run in user space becomes awfully expensive. As any clever admin will do, a least invasive fix involving limiting the number of connections and threads was done - with what sounds like immediate results!
I have no idea what MzScheme is but I am curious about why is HN running threads in user space in 2011? The OS kernel knows best what thread to pick to run and that is a very well tuned, O(1) operation for Linux and Solaris.
I don't know much about MzScheme, but it's quite possible that "thread" means "stack", not "OS thread". One context stack per TCP connection is quite sustainable; with Haskell's threads and Perl's coros, I run out of fds long before I'm using any significant amount of memory. (This is somewhere around 30,000 open connections on my un-tweaked Linux desktop. I know I can do a lot more if I tried.)
The issue, in the case of HN, is with O(n) IO watchers. Most sockets are idle most of the time, so you really want an algorithm that is O(n) over active sockets, not O(n) over active and inactive sockets. You typically have so few active fds at any time that the n is really tiny, making massively scalable network servers trivial to write. But you also have a lot of connections at any one time, so if you are O(n) over active and inactive fds, then you are going to have performance issues. Basically, you don't want to pay for connections that aren't doing anything.
Fortunately, we have the technology; epoll on Linux, kqueue on BSDs, /dev/poll on Solaris. You just need to use an event loop, so it does all the hard stuff for you (and so you don't have to worry about the OS differences). Hacking a proper event loop into MzScheme may be hard, but it's absolutely necessary for writing scalable network servers. Handling 10k+ open connections is trivial with today's technology. And, all the cool kids are doing it (node.js, GHC, etc.).
MzScheme is an implementation of Scheme (dialect of Lisp); it implements its own threading. This is not uncommon for languages which support (or used to support) many OSes, with many different versions of threading: it's easier to write it yourself, once, than maintain N+1 OS-specific versions.
Of course, these days, N+1 is probably 2, since everything except Windows supports pthreads.
I don't know the details. I suspect the answer is that the threading support was written when pthread support was less common, and the MzScheme developers haven't been sufficiently interested in rewriting it.
Racket now includes a new facility -- "features" -- which are essentially a lightweight OS-level thread. There's also another -- "places" -- which is a more separated heavy threads (closer to a new process), but that one is not enabled by default.
Reverse-proxying via nginx would solve this problem and more: the arbitrary 30 second limit on form submission (hotspots sometimes are slow...), nginx could handle rate limiting & logging instead of srv.arc, etc. The Arc codebase would btw be smaller and cleaner (no policy/sanitization code, etc.).
Serving static content via Apache was a first step ;-)
Did you just tell people running a company that reinvented funding with their custom written news site written in their own programming language with a custom web server that they shouldn't re-invent the wheel?
They think they can build a better wheel. They seem to like doing it and have a habit of it. There's nothing wrong with that.
Right, they only re-invent wheels when they feel they can make a better one. I don't think they feel they can go through the effort of fabricating a better chip. Though I wouldn't put it past rtm to try.
The philosophy "Don't reinvent the wheel" however, is definitely inconsistent with their philosophy. They will reinvent the wheel whenever they feel they can make a better one. Just because they haven't reinvented every wheel does not mean "don't reinvent the wheel" applies to this group.
They chose to create the best solution they think they can. They don't seem to care whether or not that involves reinventing wheels. The original argument that they should seems pretty silly.
Off-topically, piecing together the years that the previous posts were made, it looks like February 4 2009 had a downvote cap of 100. It's 500 as of late last year. That suggests the annual karma inflation rate in the HN economy is sqrt(5), or ~224%.
> It turns out there is a hack in FreeBSD, invented by Filo, that causes the O/S not to give a new connection to the server until an entire HTTP request has arrived. This might reduce the number of threads a lot, and thus improve performance; I'll give it a try today or tomorrow.
Anyone know if they're referring to "accept filters" here? FreeBSD folks can "man accf_http" if they're curious, which does prevent a request from being handed off to the application until the complete (and valid?) request has been made. Certainly not a "hack" but a feature of the OS itself.
Or they could use a proxy. All this "fuck me I'm famous" attitude is stupid.
Anyone know if they're referring to "accept filters" here? FreeBSD folks can "man accf_http" if they're curious, which does prevent a request from being handed off to the application until the complete (and valid?) request has been made. Certainly not a "hack" but a feature of the OS itself.
If you choose to. We pushed north of 800 r/s in production, and just shy of 4k in our LAN, that's using stock hunchentoot with just mere customization.
You are using multi-cores, it doesn't count (and please stop showing off with your mythical LISP, it doesn't even have hygiene, au contraire Haskell & Javascript).
Well, HN is written in Arc, which is a layer on top of MzScheme. MzScheme handling of sockets is actually already done with the select() syscall, and its "threads" are lightweight non-blocking threads (think Erlang). So it's already async but with "sugar".
Which is why it's good to have a mature VM underneath your language. Paul's choice of basing an implementation of Arc on MzScheme was a very good one (I remember people criticizing him for not building a standalone implementation with a new VM).
I write time-critical applications in Clojure and JVM's -XX:+UseConcMarkSweepGC flag is a lifesaver. We no longer get those multi-second pauses when full GC occurs.
> Java technology is not fault tolerant and is not designed, manufactured, or intended for use or resale as on-line control equipment in hazardous environments requiring fail-safe performance, such as in the operation of nuclear facilities, aircraft navigation or communication systems, air traffic control, direct life support machines, or weapons systems, in which the failure of Java technology could lead directly to death, personal injury, or severe physical or environmental damage
It had to be some dialect of Lisp with continuations, which meant Scheme, and MzScheme seemed the best. Our first version ran on Scheme48, but that was such a pain that we switched.
My response TBH, would be that there is no point spending months tweaking the engine of a ford to try and get it to perform like a porche. Just get a porche in the first place.
I don't value "being able to write it in my favorite language" at all. From what I've read, pg does. To the extent that the product suffers.
There would be absolutely no point me trying to improve mzScheme when you can do exactly the same job in other languages/platforms, and the user doesn't care/know the difference. HN could be rewritten in a weekend, in PHP/python/whatever and we wouldn't be sitting here waiting for pages to load.
(I run Mibbit, which handles a few thousand HTTP requests a second, on VPS level hardware. In Java).
It depends on what you mean by "perform better". Any reference-counted GC mechanism will have memory leaks, which is a serious problem in a long-running process. Python gets around this by also occasionally running a traditional GC, which, btw, is a stop-the-world GC.
Of course you can write a link aggregator in a weekend, but you can't write HN in a weekend - there's a lot of complexity in the HN source around controlling voting rings, spam, etc. When you're dealing with complex issues, it's a net win to use a language that enables you to think at the highest level of abstraction possible.
Let me add that one "thread" per connection works in Erlang for up to 80k connections easily. And since each "thread" is actually a process and each with their own GC, long pause-times are never a problem.
It is not the year, but the naivety that is the problem here, if any.
pg / rtm: If you need any FreeBSD-related help, please let me know (preferably not in the next couple of days, though...). There are lots of HN fans in the FreeBSD developer community.
201 comments
[ 2.4 ms ] story [ 179 ms ] threadThey've never heard of select()? </snark>
But really, is there some reason that it's hard to collect up all the fds at once or something?
I think in part there is a tendency, among server developers, correctly, to fear anything that looks like a busy wait (e.g., with the name poll). But really poll is just as asynchronous as select in this context (I don't know about FreeBSD's implementation -- but Linux puts to sleep wait queues the same way, afaik). It just doesn't suffer from the crazy indexing scheme of select....
At any rate, I didn't get a chance to finish probing the internals of what mzscheme uses. But if there's a way to substitute poll for select, it can often alleviate those issues of 900 requests queue up and you eventually have an fd with a value of 1024 or greater -- even though you may not have 1024 actual concurrent requests....
Though others feel free to correct me if I'm wrong. I only comment because I came across a similar issue recently. This link may be useful too:
http://www.makelinux.net/ldd3/chp-6-sect-3.shtml
ETA. i finally got a copy of the most recent racket source (though probably not the one rtm and pg are using). but if anyone is curious, browse racket/src/network.c. the source version for mac uses a bunch of selects (e.g., for tcp-accept). replacing with poll might help.... the max number of FDs per login session is often 1024 by default. so you might want to bump that up if it's not already. and consider using poll.... just an idea.
http://zer0.org/daemons/yahoobsd.html
Regardless of what you think of Yahoo's current situation, somebody who could easily retire wealthy but still hacks and flies economy class on Southwest to meetings in remote offices is worthy of respect.
Last time I had lunch with him we talked about the minutia of DNS server implementations because I was working on some optimization tricks and he was really interested in seeing them get implemented.
filo is a really amazing guy. He's the most down to earth billionaire I know. He talks way more about his family and hacking more than 'stuff'. If he isn't hacking on code as much as he used to it's because he cares about his company and is doing an important job looking after technical stuff that needs doing, even if it isn't interesting.
[0] http://ycombinator.com/images/hntraffic-17jan11.png [1] http://news.ycombinator.com/item?id=2090191
Pretty whizzy, definitely helped server scaling.
We started shipping in 2001; the dot-com bust more or less canceled any interest in the product, and canceled the company, too . . .
The bottleneck is the amount of garbage created by generating pages. IIRC there is some horrible inefficiency involving UTF-8 characters.
What is the main bottleneck of HN?
http://www.alexa.com/siteinfo/ycombinator.com
I wouldn't call it a hack, but a feature ;-)
Is HackerNews web scale?"Shards are the secret ingredient in the web scale sauce. They just work."
I have no idea what MzScheme is but I am curious about why is HN running threads in user space in 2011? The OS kernel knows best what thread to pick to run and that is a very well tuned, O(1) operation for Linux and Solaris.
The issue, in the case of HN, is with O(n) IO watchers. Most sockets are idle most of the time, so you really want an algorithm that is O(n) over active sockets, not O(n) over active and inactive sockets. You typically have so few active fds at any time that the n is really tiny, making massively scalable network servers trivial to write. But you also have a lot of connections at any one time, so if you are O(n) over active and inactive fds, then you are going to have performance issues. Basically, you don't want to pay for connections that aren't doing anything.
Fortunately, we have the technology; epoll on Linux, kqueue on BSDs, /dev/poll on Solaris. You just need to use an event loop, so it does all the hard stuff for you (and so you don't have to worry about the OS differences). Hacking a proper event loop into MzScheme may be hard, but it's absolutely necessary for writing scalable network servers. Handling 10k+ open connections is trivial with today's technology. And, all the cool kids are doing it (node.js, GHC, etc.).
http://www.cs.brown.edu/~sk/Publications/Papers/Published/kh...
Of course, these days, N+1 is probably 2, since everything except Windows supports pthreads.
Serving static content via Apache was a first step ;-)
Don't reinvent the wheel!
They think they can build a better wheel. They seem to like doing it and have a habit of it. There's nothing wrong with that.
The philosophy "Don't reinvent the wheel" however, is definitely inconsistent with their philosophy. They will reinvent the wheel whenever they feel they can make a better one. Just because they haven't reinvented every wheel does not mean "don't reinvent the wheel" applies to this group.
They chose to create the best solution they think they can. They don't seem to care whether or not that involves reinventing wheels. The original argument that they should seems pretty silly.
Anyone know if they're referring to "accept filters" here? FreeBSD folks can "man accf_http" if they're curious, which does prevent a request from being handed off to the application until the complete (and valid?) request has been made. Certainly not a "hack" but a feature of the OS itself.
Or they could use a proxy. All this "fuck me I'm famous" attitude is stupid.
http://en.wikipedia.org/wiki/Robert_Tappan_Morris
http://lib.store.yahoo.net/lib/paulgraham/bbnexcerpts.txt
2: same acronym as RTFM, but polite.
Diagnosis: Badass.
Most recently, one of the creators of Arc (along with pg), the language used to create/run HN.
This guy here broke the 10k barrier:
http://john.freml.in/teepeedee2-c10k
http://hoytech.com/antiweb
http://en.wikipedia.org/wiki/Morris_worm
I write time-critical applications in Clojure and JVM's -XX:+UseConcMarkSweepGC flag is a lifesaver. We no longer get those multi-second pauses when full GC occurs.
What is this the 1990s?
I'd trust my life on the JVM, it's pretty battle tested, and the GC is simply awesome.
You sure you want to do that? :-)
> Java technology is not fault tolerant and is not designed, manufactured, or intended for use or resale as on-line control equipment in hazardous environments requiring fail-safe performance, such as in the operation of nuclear facilities, aircraft navigation or communication systems, air traffic control, direct life support machines, or weapons systems, in which the failure of Java technology could lead directly to death, personal injury, or severe physical or environmental damage
http://technet.microsoft.com/en-us/library/cc976720.aspx
I wouldn't trust anything from microsoft though.
It's easy to criticize, but let's see what happens when the pedal hits the metal.
I don't value "being able to write it in my favorite language" at all. From what I've read, pg does. To the extent that the product suffers.
There would be absolutely no point me trying to improve mzScheme when you can do exactly the same job in other languages/platforms, and the user doesn't care/know the difference. HN could be rewritten in a weekend, in PHP/python/whatever and we wouldn't be sitting here waiting for pages to load.
(I run Mibbit, which handles a few thousand HTTP requests a second, on VPS level hardware. In Java).
In any event, it's a "solved problem". The sheer amount of time and effort going into this is silly. Just pick a better language/platform and use it.
Don't slam something saying I could do better, and then have your bluff called.
Makes you look silly. This applies to even if the person calling your bluff was NOT pg.
It is not the year, but the naivety that is the problem here, if any.
Thanks for the work and it sure seems to be a lot more responsive.