Otherwise... no way, if you have data structures everything is fragmented around (and you want to use a lot object sharing, caching, ... for performance, without to mention hash tables that are very cool at filling at least 1 byte of tons of pages even with 2% of data inside).
Also data structures can often be serialized on disk using 1/10 of the space.
Using the VM is cool, but not so generally applicable. The proxy stuff is perfect. Also on-disk DB is perfect using the VM the other way around, to get a memory-cache for free, if you don't need strict consistency (see MongoDB).
To me the big reasons to serialize to disk are as a way of sharing data between processes, and as a way of making data permanent. But not for performance. Because compared to RAM, disk has none.
As for the best representation, I am not sure I agree. I agree that the best representation for frequently accessed data and seldom accessed data are frequently very different. Of course normally the former is in RAM while the latter is on disk. However it is not obvious to me that it is at all a bad thing to have some space used in RAM by infrequently accessed data. And if it is not, then you wind up with the solution I suggested. Just write out the data as you want it on disk, into RAM, don't touch it, and let the VM worry about when (and if) it needs to actually be paged to disk.
Of course this doesn't work if you're not using virtual memory. :-)
I'm pretty ignorant on systems programing, but I gather on most platforms there's a way to create a custom page fault handler, that could preserve your custom serialization format. Depending on how redis objects are linked however, allowing relocation may be complicated.
If, as you say, data can be that easily compressible, the IO speedups from reading the compressed data from disk and space savings would outweigh the CPU cycles necessary to do the decode, but my brief Google search for compressed page file implementations came up with nothing.
With VM the live representation and serialization format are the same.
[1] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.26.7...
hmm not really. this: [ http://en.wikipedia.org/wiki/Unrolled_linked_list ] is what i had in mind
As he says, this is a 2006 architecture. VM, cache line-size d working set, MRU scheduling -- this is stuff that's been around for a while. If he were writing this article about a 2010 architecture it would look a bit different. For example, trying to minimize memory access is a laudable goal but in the normal data sets the cache is usually overwhelmed pretty quickly. A 2010 architecture would feature NUMA optimization, although his practice of allocating thread data on the thread stack actually helps this a fair bit (inadvertent?). If Varnish uses threading at a significant level, this kind of optimization is only going to get more significant over time. The modern CPU architecture product cycle goes through a kind of give and take -- it alternates between having just enough fast memory and not enough. Right now, we are just about smack dab in the middle of "just enough," but the next Intel release is projected to move to "not enough." Threaded programs in NUMA start to matter a whole lot more on 16, 32, 64 cores.
P.S. We actually just ignore 32-bit architectures. Even modern commodity CPUs don't have them and anyone running a server architecture with only 4 GB of RAM has bigger problems than the proxy software.
Edit: Just saw antirez's post: very good. The VM architecture is good for general case, but it really wasn't designed for specialty applications. There are many operations that a VM can make if it knows a fair bit about the working set and the memory pattern, but that's not possible in a generic OS VM (prefetching and streaming are big ones).
This is nonsense. I was one of the developers on Squid for many years, which makes me more aware of its flaws than most folks, and it does have many flaws, even in current versions. But, to say it is god-awful development is pretty deeply ill-informed, and insulting to the small handful of dedicated volunteers who currently maintain Squid (which, I might add, is used by an order of magnitude more people on an order of magnitude more servers than Varnish; it is the most popular proxy cache in the world, serving about 80% of the market last time I saw research on the question).
Squid has different priorities and goals from Varnish. One of Squids priorities is to run on as many architectures and operating systems as possible. Another is to provide an extreme level of functionality, making it a swiss army knife of web proxy caching tasks. A third is being compatible with everything; and in the HTTP protocol world, this means dealing with thousands of edge cases and broken implementations. These things are not always consonant with being the fastest proxy, or with being the simplest design. Edge cases have a cost, which Squid pays because that's one of its goals.
Certainly, Squid has vestigial design decisions that cost it performance and efficiency on modern hardware (though the select/poll loop was the best we had until just a few short years ago, and the VM layer on many UNIXes is retarded; calling the way Squid does things 1975 technology is idiotic), but there have been improvements in a number of areas over the years.
Anyway, I would advise taking the flames of a developer on a dramatically less popular and less capable project with a grain of salt. There are interesting ideas to be found in Varnish and in its developers comments, but his knowledge of Squid is clearly limited, and his opinions are clearly motivated partly by a weird bit of anger toward the much more popular Squid.
Many products designed in the 90s and early 00s took compatibility very, very seriously. Things had to run on everything, and a lot of engineering effort went into patching over the differences between platforms. So you got things like Java, autoconf, Squid, Apache, Linux, various GUI abstraction layers, etc.
Now, it seems like the pendulum is swinging towards performance, simplicity, and ease-of-use, and people are saying "fuck compatibility". Since so much software has moved to the server side, people are just standardizing on one type of server (usually some Linux flavor), saying "We'll develop for this", and ignoring everything else. And as a result, products that used to be essential because things really needed to run on everything are getting a lot of hate for their byzantine config options.
I see this most with autoconf, another project that has had lots of abuse thrown at it, but it seems like it could apply to Squid or Java as well.
I think it comes down to younger folks not having experienced the pre-Linux world of the server-side (or at least the pre-Linux domination). There was a time when there were dramatic differences between the various UNIXen, and only something like autoconf could make an Open Source project build on anything approaching a majority of them.
I think a good example of a weird characteristic of Squid is its cache_dir directory layout. By default, it'll distribute files into a directory/subdirectory/ hierarchy. This doesn't really serve a useful purpose on modern systems (it doesn't really hurt anything, either, it just looks weird to modern users), but on some UNIXes back when Squid was being built there were dramatic performance effects from having huge directories full of thousands of files.
Likewise, the whole virtual memory argument that the original article talks about is complaining about something that was intentionally added to the Squid design in order to address the horrible characteristics of several major UNIX VM implementations (even now, having a good VM layer is not something you can just assume).
I feel a little bit of unease when I see projects that do choose the "we develop for this" model. I'm not sure it is a useful feeling, but I think we probably should keep our options open. I've made cross-platform a religion for most of my developer life, and it is perhaps less important now...but I don't think it's wise to just say, "OK, it runs on the latest Linux kernel. Fuck it, let's ship it. Screw everybody using anything else."
In the past there were branches for oddball systems, like Windows. But they eventually merged into HEAD. I'm not entirely sure DVCS solves the problems that having multiple branches introduces. I'd need to see some numbers or something. OpenSSH isn't in a DVCS, is it? So they aren't a data point in either direction, though I wasn't aware of OpenSSH-portable.
Not to poke at Squid (I'm far from qualified), but that's a horrible argument. There are plenty of extremely-highly-motivated people working on god-awful projects, believing they're being brilliant and revolutionary, when they're in fact re-doing something solved a decade earlier, built into the operating system they're using, and theirs runs 100x slower than the average naive implementation found by Googling.
Insulting it may be, but wrong it may be not.
I said it is deeply ill-informed. I said this after explaining that I was a Squid developer for many years. I was making a statement based on experience, not pleading a case. If you believe I'm incapable of determining whether a project is god-awful development or not, that's fine.
And then I said that it is insulting to dedicated volunteers. This was not an argument for why Squid is not awful development. I explained that later. I was simply stating that it's insulting.
And, as for this:
"when they're in fact re-doing something solved a decade earlier"
Yeah, in a lot of cases Squid is the "solved a decade earlier" example here.
"built into the operating system they're using, and theirs runs 100x slower than the average naive implementation found by Googling"
If you believe Squid fits this description you're really not qualified to comment on it.
As I said, Squid has many flaws, but it was not designed or developed by children or idiots. It was built by competent software developers who wrote many of the papers on the topics that it addresses, and invented many of the techniques that are now standard in proxy caching software. Varnish takes more ideas from the Squid developers than Squid developers could ever take from Varnish, whether he knows it or not.
Squid does have legacy and baggage. Squid also has capabilities that Varnish would never have need for (ICP, for example, cache digests, hierarchy features, etc.).
"Insulting it may be, but wrong it may be not."
And I said that it is both.
As I've said, I am not qualified to comment about Squid, nor was I. I was commenting about some / other developers and projects, not pointing a finger in any particular direction, and pretty clearly referring to extreme cases.
PHK was obviously referring to a specific issue; Squid's implementation and usage of caching in its particular area of application. Varnish is obviously better at that. Squid is obviously better when it comes to portability and flexibility.
I'm going to think out loud here, and please take a minute to consider this, because I'll just try to be honest, not mean or elitist: Is it enough for my software to compile and run correctly on multiple platforms for me to call it 'portable', or should I take advantage of the characteristics of each platform?
I know that when it comes to my work, I choose the second, and I'm guessing that PHK would too. The "1975 programming" bunch, well, maybe not.
Squid supports async IO threads on Linux, has experimental (maybe stable by now) support for epoll on Linux and kpoll on FreeBSD, it automatically chooses the best option for poll/select based on the platform it is building on, uses the best available malloc (and will use alternatives if available and the build system has a retarded one; it used to include dlmalloc in the source tree just in case no acceptable malloc was available but that's probably gone by now), can run as a service on Windows, etc., etc., etc.
So, Squid does both, in many regards. It not only builds and runs reliably on pretty much every platform you can throw at it, it runs better on platforms that provide the mechanisms it needs to run better (Linux and FreeBSD, in particular).
It can't trivially replicate the dumb (but very fast) pipeline from net to memory to net that Varnish uses because Squid has a dozen or more access points into the data passing through. It could certainly be cleaner and simpler, and there was a zero copy patch running around for a long time for Squid 2, which never reached stability (due to the huge amount of code you have to touch to make such an idea work). Maybe Squid 3 has done something about all that, I'm not sure.
Squid is not incredibly fast, but it's definitely able to take advantage of better and more modern platforms.
According to your logic, since more people use Windows, it is clearly a better engineered piece of software than Linux, right?
Do they improve performance on the latest version of Linux in the particular workloads for which Varnish is designed? Probably not.
"According to your logic, since more people use Windows, it is clearly a better engineered piece of software than Linux, right?"
Where do you see me stating that popularity equals better engineering? My only comments about popularity were about the motivations of the Varnish developer in his criticisms of Squid.
But, I would argue that one of the reasons Squid is more popular than Varnish (and any other proxy cache) is that it works in so many situations and does so many things. It doesn't have to do with engineering, at all, but answering the needs of a broad spectrum of people. It also helps that it has reliably been answering the needs of a broad spectrum of people for over a decade.
Squid is a goddamned institution, and while there's plenty of room for other proxy caching tools, like Varnish, it pisses me off to see folks hurling pointless abuse at people I know to be extremely good software developers (two of whom probably have written an awful lot of code in places that everybody here uses on a regular basis...if you use Ubuntu, for example).
There have been numerous proxy caches that have come and gone in those years, and there will likely be numerous that come and go while Squid continues doing its thing.
"That would make it more popular for the same reason that Apache is more popular than other open sourced webservers: name recognition?"
Do you really believe name recognition is the only reason Apache is the most popular web server?
It doesn't have anything to do with the huge array of capabilities that Apache has that no other web server has? Or the broad ancillary tools support? Or the huge pool of knowledge available for it? Or that it is proven reliable? Or that it can safely be expected to exist and still be a viable option in five or ten years?
But, to answer your question of whether I think Squid is popular for the same reason (or reasons, as I believe is the case) Apache is popular: Yes.
Squid is popular for exactly the same reasons Apache is popular. It is a reliable product that serves a wide variety of users very well. It is well-maintained and has a long history of being well-maintained. It is well-understood by a lot of people, so it's not going to be neglected or a source of contention if the IT guy moves to another job. It is fast enough for a lot of uses. It is extensible via a number of scriptable access points, so developers can easily make it do what they need it to do. And, despite the accusations of horrible design, it has proven itself to be quite resilient. The number of security issues in Squid, for example, has been truly miniscule in the past decade.
The funny thing is how many people are acting as though Varnish is going to somehow take the place of Squid as soon as people realize that Varnish is "better". For one small subset of problems for which Varnish is specifically built, it may make sense. But, for a huge array of other proxy and caching problems, Varnish isn't even a contender.
I should maybe explain that my first company was a web caching proxy company, building products based on Squid. I deployed Squid several thousand times over seven years. Varnish would have worked in maybe a few dozen of those deployments. Squid solves a ridiculous array of problems, even though it solves none of them as well as a purpose built application could solve any one of them. Varnish solves its handful of problems very well...and does nothing for all the rest of the use cases.
I think that that's a huge component of it. I know that I've been in a number of shops where they deployed Apache, not because it was the best tool for the job, but because it was the only tool of which the admins knew, and they didn't know where else to look.
I no opinions about Varnish vs Squid, but I will point out that I had no idea what Varnish was until I read this article, but I've known what Squid was for a while, so they're not competing on equal terms.
Caching problems can be a little tricky, and having someone experienced with the caching system when something goes wrong can help a lot.
I'd say squid is a bit like NFS. It's not the best system possible in theory, but goddamnit, it's been tested to hell and back in systems much larger than I'm dealing with, and we know where all the problems lie.
(Also note, I believe Windows is only more popular on the desktop; Windows has never been a majority player in terms of webservers and other public Internet infrastructure, unless you count private intranets. in the public Internet server space, windows is fighting with sun and apple for the scraps. Linux is the big player here. )
No, you'd be surprised. Windows, (running IIS) actually has about a quarter to a third of the public webserver market share: http://news.netcraft.com/archives/2010/07/16/july-2010-web-s...
ASP.NET is actually very popular.
If that were the case I wonder how well the model would hold up but it does what it does very well and there is as far as I have been able to determine no other program that comes close to the kind of throughput you can achieve with varnish.
Disclaimer: very happy varnish user here.
I believe the O`_DIRECT flag can be used for this purpose, although a quick bit of googling suggests it's getting flack from all over the place, including Linus himself.
I expect that most of DBMS that wish to circumvent OS-level caches do this because (a) it was good idea when they was first implemented and (b) use some highly-peculiar on-disk layout that might actually benefit from this (modern databases tend to not have any special "well-defined" access patterns).
Postgres does expect that in addition to its explicitly-managed cache (the shared_buffers setting), the OS will be caching a bunch of stuff as well, and its query optimizer takes this into account (the effective_cache_size setting). Reasonable conservative settings are 25% and 50% of system RAM, respectively.
There's no One True Source on this AFAICT, but http://wiki.postgresql.org/wiki/Tuning_Your_PostgreSQL_Serve... and http://www.postgresql.org/docs/current/static/runtime-config... are handy.
Antirez referenced this article and explained why he disregarded these advices in the initial Redis VMEM post.
(See comments #29 and #30 for the reference)
The performance characteristics of disk and RAM are so completely different that any program which swaps to disk is going to be effectively unusable. Therefore if you care about latency, turn VM off and provision a generous amount of RAM. Because VM only seems to work, until you actually use it, and only then do you discover how broken it is.
Now, much of this problem is caused by Linux's /really aggressive/ default memory over commit policies. Besides, swap gives you a free out if you are running programs that load up unnecessarily large libraries.
My desktop has swap. The servers I use do not.
Now if you've dealt with this already and just have your techniques secret you know all this but I'm going to yammer on anyhow, just 'cause I think it's a interesting subject; feel free to participate or not.
So in the modern virtual memory system there are lots of situations where more memory is allocated than used. If I have some massive, 200 megabyte webapp running under mod_perl or mod_php or what have you, and I have apache fork 1024 processes, (well, in that case I probably need to increase threads... but I digress) even through I should be using 200 gigs of ram, I'm not. fork uses copy on write; it only copies the data that changes.
this is pretty cool... I get to use 200 gigs of ram, but I only actually have to buy 400 megabytes or something. The problem is that it's impossible for the virtual memory system to tell ahead of time how much of that copy on write will actually be copied. without memory overcommit, the box will keep track of every fork and figure the max allocated ram, assuming no copy on write savings, and it will fail your fork or malloc when it reaches the total amount of swap plus ram. If you are trying to run 1024 identical 200 megabyte processes on a box with 8 gigs of ram and no swap this really sucks. So memory overcommit, especially when you don't have a lot of swap, is a nice thing to have.
But, you say, what if my 1024 identical 200MiB processes become non-identical? what if they start changing their memory, and copying and start using more ram than I have ram and swap in the box? on most linux systems, you'll get the oom-killer, which will randomly (well, not randomly, but it seems that way sometimes) kill a process. Sometimes it kills something unimportant.... sometimes it kills the webapp the box was built to house... sometimes it kills some background system process you were depending on. You can tweek this to hell and back, but any way you slice it, the oom-killer is bad news. Another option is to tell the computer to just panic when it finds it runs out of memory.
Now, if you turn memory overcommit off...well, your landings are much softer. without memory overcommit, the only time the box runs out of ram is at malloc time, and it can cause malloc to return an error, and (hopefully) be handled gracefully by the program asking for more ram.
the real problem with turning memory overcommit off is that if you are trying to run 1024 identical 200MiB processes on a box with only 4 gigabytes of combined ram and swap, your 21st fork will fail, even though, thanks to the magic of copy on write, there was plenty of unused ram to go around.
Now, the advantage to having a lot of swap on a system without memory overcommit is that the virtual memory manager is pretty smart; while the computer can /commit/ to allocating swap, as long as the magic of copy on write leaves it with free physical memory, it will use that physical memory. If it turns out it was too aggressive about over committing memory, well, it hits swap, and depending on how much ram you have that is seldom used, your box slows down by quite a lot. Of course, if you use swap for ram that is actually accessed very often, most people agree that the box might as well have just crashed or frozen. the disagreement, I think, comes when there is ram that is allocated for some seldom-used library or the like. the virtual memory system swaps that out to disk, and gives that bit of physical ram to something else it needs.
In a highly-scalable webapp, that infrequently-used functionality lives on another server, called via RPC. Instead of paging it out, you simply provision fewer machines for it, and then only make calls to it as necessary. Paging out one component of a large distributed system is dumb: you're potentially slowing everything else down because you couldn't spare one machine to keep the whole binary in RAM.
However my comment applies to much smaller websites as well. If you have a website running on a number of webservers, and the working set exceeds RAM, then the website slows to a crawl, requests pile up, RAM gets even more overloaded, and you have a very bad failure mode which can be hard to sort out. By contrast if you have no swap and lots of RAM, you could have kept humming. If you hit the limits of RAM, you stay fast but get OOM messages in the error logs, which is much easier to debug. Furthermore it now obviously makes sense to monitor how much RAM is really in use, so you can head off problems before you run out of RAM. This gives you early warning of issues before they happen.
Yes, it is true that this approach creates a potential problem when you wouldn't necessarily have had one before. But creating an avoidable potential problem frequently results in fewer actual outages than having a problem which can sneak up on you in a non-obvious way.
This was pointed out to me by a very competent sysadmin several years ago when she explained why she had set up the servers with no swap. And she proved her point when she told us, before anything went wrong, that we needed to buy more RAM for the servers.
Ram is cheap.
What if you are designing for a system that won't ever have a swapfile/pagefile? What if your application is designed so your working set fits in ram? Then you can use other methods and not worry about fighting as much with the VM.
I love this article - because a reverse proxy is a great example of this.
(You want to cache transitory data to disk - You plan to roll your own caching system to keep data locally so you don't go back and query source nodes. You want some legroom to work with working-sets that may be larger than your physical ram, and you may want that ram cache to survive reboots intact.
So memory-map the file and let the OS take care of the rest - makes sense to me.
EDIT: What I meant to say was "It's not so much not fighting with the VM - it's realizing that the VM is more than something to ignore, and that it can be used to your large advantage by treating it like what it really is - a system that deals with shuttling data between different levels of storage (disk/ram).
I am very curious about this too. I could see doing that in Java where you don't have ability to advise the VM on how you're going to be accessing memory mapped files (no madvise() or fadvise() available despite NIO support for mmap, thanks Sun!), but asides from portability to non-Linux OSes e.g., ZFS ARC Cache on Solaris doesn't honour madvise()/fadvise() the same way Linux page cache does, what would be the reasons against trusting the VM in C/C++ code where you can explicitly "advise" (Linux treats madvise() as imperative rather than advisory) the VM on your usage?
Redis is a cool product and antirez is a smart guy, so I am sure there must be a reason for this.
I also think hierarchical allocators - a slightly-formalized version of phk's "carve chunks off a block of pre-allocated memory" - deserve more attention. See SAMBA's talloc, or halloc.
[1] Well, you can write some code to page things out as appropriate, but by the time you're inventing your own virtual memory manager you're definitely doing it wrong. Just go with old-fashioned file-based code.
If you're going to try to push multiple Gbps out of a single box the least you could do is put a bunch of ram in it and install a 64 bit OS. That's a lot more bang for the buck than installing multiple 32 bit boxes with only a bit of memory in each.
1) You're not limited to having a single giant map of your entire data set for the life of the process. You can map in only the parts you are going to touch. For a CPU intensive request, a mmap()/munmap() pair isn't that much overhead.
2) You also can't address more than 64K of space on a 16-bit machine, but no one seems to worry too much about this anymore. Why would one worry about 32-bit machines when implementing a system that is handling gigabytes of data? Why not just run 64-bit and solve the 'problem'?
I agree with you on the allocators. A pet projects that I'd like to get back to is redesigning dlmalloc to run fast out of a shared mmap(). With some simple locking, I think one could get some really fast file-backed data structures.
POSIX mandates a 32-bit int - UNIX hasn't ever run on a 16-bit machine (yes, I know there are some abominations.) Au contraire, 32-bit machines are still common; download one of the 'whole archive' files from http://popcon.debian.org/ and run:
$ awk '$2 ~ /^linux-image-/ && $2 ~ /86/ { SUM += $6; }; END {print SUM;}' by_recent
$ awk '$2 ~ /^linux-image-/ && $2 ~ /amd64/ { SUM += $6; }; END {print SUM;}' by_recent
I got 8174 for /86/ and 4420 for /amd64/. Admittedly, this is in no way representative of anything, but clearly people are still using i386 (note that I summed the 'recent' column!)In short, i386 is not dead. And suggesting that it cannot handle "gigabytes of data" is absurd - Postfix/Dovecot, or PostgreSQL, or SAMBA, or pretty much whatever, can handle many, many gigabytes of data without issue on a i386 platform. Yes, you'll need to upgrade to 64-bit for the truly demanding tasks, but a database with a couple of (tens of) GB of data in it can work perfectly well on a scavenged i386, which is one of the good things of a unix-ish system.
(That said, you can trade off ease of implementation for being crippled on 32-bit platforms. But you are sacrificing something.)
That's afaik absolutely not true, Unix was actually developed on 16 bit machines, back in the stone age of computing, roughly 1969 (that's why the unix 'epoch' starts in 1970).
After a while 32 bit machine became available and Unix was ported to them.
Unless you wish to call the earliest versions of Unix 'abominations, but I'm thinking you have Xenix and such in mind when you write that.
I'm not following this. As I see it, all you have to do is keep insure that no more than 3GB are mapped for your process at a given time. You still let the kernel decide what's faulted in and when things are written out.
Maybe my perspective is skewed: I'm viewing it from the perspective of real-time search, with large posting lists being frequently read and updated, and lazily written out to disk. Is there a different situation that is harder?
> In short, i386 is not dead. And suggesting that it cannot handle "gigabytes of data" is absurd
I didn't mean to imply it couldn't, or that it wasn't in common use. Rather I was wondering why I as a open source software author (http://wiki.apache.org/incubator/LucyProposal) would choose to make my life more complicated by targeting new software at a 32-bit platform at the expense of code simplicity.
Our current plan is to optimize for 64-bit systems, and allow 32-bit compatibility for smaller data sets (tens of GB) by sprinkling in mmap()/munmap() calls as necessary: http://www.mail-archive.com/[email protected]/msg00...
Edit to add: I'm not trying to claim I'm definitively right. Rather, my point is that I care about the answers to these questions in practice as well as in theory. I worry about taking the wrong approach.
By making use of the mmap() method, he just ensures that when data he wants stored on disk somehow needs to be paged out of ram, it won't be duplicated.
* Trust the VM system to figure out how to page things (hey, 'antirez, what's your take on that? You wrote an ad hoc pager for Redis.) instead of getting fancy, because if you get fancy you'll end up fighting with the VM system.
* Minimize memory accesses and minimize the likelihood that you'll compete with other cores for access to a cache line; for instance, instead of piecemeal allocations, make a large master allocation for a request and carve it out.
* Schedule threads in most-recently-busy order, so that when a thread goes to pick up a request it's maximally likely to have a pre-heated cache and resident set of variables to work with.