13 ms·

What's wrong with 1975 programming

293 points by dchest 16y ago

buro9 16y ago
I prefer the bit in this article: http://www.varnish-cache.org/wiki/ArchitectureInlineC http://www.varnish-cache.org/wiki/ArchitectureInlineC Where he says: "It is a particular common kind of hubris for IT architects, to think that they know better than 100% of everybody else, this is less of a sin in Open Source than in Closed Source, but a sin nontheless."
tptacek 16y ago
This is one of the best systems programming articles I've read in a very long time. Short summary: * 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.
- gruseom 16y ago
  Now that's interesting. I've been asking around for a while to find out what other systems programming experts think of this article, specifically the first point about not fighting with VM, which is the most prominent one (including in phk's provocative recent ACM article). I'd also like to know what other things, besides these, Varnish does to achieve its performance. I'm sold on the idea that most of us have been doing this kind of thing wrong. Let's hear more about how to do it right.
  - tptacek 16y ago
    For what it's worth, I've been in and out of the FreeBSD kernel since 1995 and am an unabashed PHK fan.
  - dedward 16y ago
    IT's not so much that it's "wrong" - it's just ignored. 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).
- masklinn 16y ago
  > hey, 'antirez, what's your take on that? You wrote an ad hoc pager for Redis Antirez referenced this article and explained why he disregarded these advices in the initial Redis VMEM post.
  - tptacek 16y ago
    Neato; link?
    - bretthoerner 16y ago
      http://antirez.com/post/redis-virtual-memory-story.html http://antirez.com/post/redis-virtual-memory-story.html (See comments #29 and #30 for the reference)
      - masklinn 16y ago
        Mmmm crap technically he didn't reference this article (explicitly), I should have checked.
    - deleted 16y ago
      [deleted]
- JoachimSchipper 16y ago
  On one hand, mmap() is very nice. On the other, you may run into the limits on process size, and this is essentially unsolvable [1]. So your program is limited to 3GB of data on 32-bit machines. 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.
  - masklinn 16y ago
    Admittedly, at this point you could probably consider that 32b machines are legacy and unsupported (FWIW there was a Steam stats thing posted a few months back indicating that more than half of their Windows 7 users were on 64b... I can only expect that those ratios are much higher for unices)
  - nkurz 16y ago
    I understand the issue of process size, but I'm confused why this is a concern. 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.
    - JoachimSchipper 16y ago
      Yes, you can mmap() and munmap() as needed, but that makes things a lot less convenient - you'll still need to keep track of which data is on the disk and which data isn't, etc. At this point, you've already solved half of the problem of using malloc(), read() and free() instead of mmap() and munmap(). 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/ 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.)
- antirez 16y ago
  If you have mostly big objects (relative to hardware page size) and the encoding in memory and when stored on disk are pretty similar, this is indeed a good idea (to trust the virtual memory I mean). 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).
  - cninja 16y ago
    What are the difficulties in using some sort of compression algorithm like LZJB on the disk's page file? 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.
    - antirez 16y ago
      A linked list is hard to compress in memory as the overhead is the metadata: pointers, malloc overhead, ... but when written on disk can be represented as prefixed length strings. With VM the live representation and serialization format are the same.
      - signa11 16y ago
        just curious: is it not possible to have some form of unrolled-linked-list to mitigate this effects somewhat ? or perhaps you have already tried it, and it doesn't really fit the bill.
        nitrogen 16y ago
        It kind of sounds like you're describing a sparse array.
- Locke1689 16y ago
  It's pretty good. Maybe because I'm also a kernel developer, but these suggestions seem obvious to me. That is, instead of Varnish being novel and well-optimized, it appears that Varnish is pretty conventionally optimized and Squid is just a god-awful piece of development. 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).
  - jacquesm 16y ago
    Varnish is a massive VM to network pipe, nothing 'sophisticated' happens to the data that it deals with. 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.
  - SwellJoe 16y ago
    Squid is just a god-awful piece of development 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.
- deleted 16y ago
  [deleted]
- strlen 16y ago
  > hey, 'antirez, what's your take on that? You wrote an ad hoc pager for Redis. 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.
- barrkel 16y ago
  The major assumption is that the OS VMM's caching behaviour is as smart or smarter than the application's caching behaviour; that is, the operating system knows better than the application when to evict something from the cache. That may be true for many stupid applications, but I seriously doubt it's always the case.
  - shabble 16y ago
    I was informed recently in a Masters level course on database implementation that databases typically wish to explicitly circumvent a lot of this caching, especially for IO buffering, since they can do the same thing at the app level, but leverage the fact they have much more well-defined access patterns than some generic kernel system that has to perform adequately across all workloads. 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.
    - btilly 16y ago
      Another big reasons that databases with to circumvent this caching is that they really, really need to make sure that when a transaction is committed, that they know what is on disk. Having the OS pretend stuff is written to disk is great for performance, but not so great when you're trying to recover after someone pulled the power.
      - dedward 16y ago
        This is where you get DBs that use their own raw block devices, as well as keeping transaction logs on other regular filesystems for integrity.... Oracle does something similar no?
    - dfox 16y ago
      For example PostgreSQL actually has almost none caching built-in and almost exclusively relies on OS (in default and recommended configuration). 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).
- btilly 16y ago
  Here is a contrarian perspective. 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.
  - JulianMorrison 16y ago
    If you are running any modern program, there will be a proportion of its functionality and data you never use. That ends up paged to disk, freeing up RAM for what you do use. That's what VM is for, really. Using it as "memory" is very 1970s. It's more of a "forgettory".
    - btilly 16y ago
      If that works for you, then you obviously aren't trying to consistently hit a low latency SLA. Which brings me back to my point.
    - nostrademons 16y ago
      I suspect you're thinking "desktop" and btilly is thinking "server", and you're going to end up talking past each other. Or, if you are thinking servers, then you're thinking "one server" and he is thinking "one million servers". 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.
      - btilly 16y ago
        Shhh...don't give away any secrets. ;-) 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.
old-gregg 16y ago
MongoDB guys outsourced the entire caching/memory management to OS VM and on my (modest) workloads it performs really well. It probably also means that OS is a bit more relevant now and the choice b/w BSD/Linux isn't just about personal preference anymore, I can imagine that their VM characteristics are quite different and "2006 style" software like mongod won't work the same. Anyone with low-level experience with BSD/Linux VMs?
helmut_hed 16y ago
It seems to me that the first point made (on the performance of Squid's LRU caching) is really just that Squid is doing a bad job at it, and Varnish doesn't try at all (lets the VM system take care of it). In theory, managing memory at the object/application level should give you some advantages over doing it at the page/kernel level. I can imagine, for example, cases where Squid might perform better by moving entire objects to/from disk, rather than a page at a time in response to faults. In this case "1975 programming" really means trying to manage the memory hierarchy in the interest of performance, which is timeless. Indeed, the author later states that Varnish tries hard to "reuse memory which is likely to be in the caches", which sounds like the same idea applied to a different level.
- JoachimSchipper 16y ago
  The kernel VM system has a lot more ("global") information, though.
blueag 16y ago
Using the VM only work if the size of the cache fits in the process address space. If your cache size is greater than 4GB in a 32 bit machine, you will have to manage the cache on disk. It becomes less of a problem now with 64bit machine.
obama121012 16y ago
Happy shopping, happy with life, all in here,Please click: HtTp://WwW.wOwCoOl.OrG Dear Customer, How are you, There are many good products Please click the following URL http://wowcool.org/productlist.asp?id=s55 http://wowcool.org/productlist.asp?id=s55 【T-shirt】 http://wowcool.org/productlist.asp?id=s13 http://wowcool.org/productlist.asp?id=s13 【 MTB】 http://wowcool.org/productlist.asp?id=n49 http://wowcool.org/productlist.asp?id=n49 【Jordan 2010】 http://wowcool.org/productlist.asp?id=s44 http://wowcool.org/productlist.asp?id=s44 【Watch】 http://wowcool.org/productlist.asp?id=s46 http://wowcool.org/productlist.asp?id=s46 【Jewerly】 http://wowcool.org/productlist.asp?id=s45 http://wowcool.org/productlist.asp?id=s45 【Sunglass】 http://wowcool.org/productlist.asp?id=s60 http://wowcool.org/productlist.asp?id=s60 【Jean】 http://wowcool.org/productlist.asp?id=s53 http://wowcool.org/productlist.asp?id=s53 【handbags】 http://wowcool.org/productlist.asp?id=s68 http://wowcool.org/productlist.asp?id=s68 【Jacket】 The website wholesale for many kinds of fashion shoes, like the nike,jordan,prada,adidas, also including the jeans,shirts,bags,hat and the decorations. All the products are free shipping, and the the price is competitive, and also can accept paypal payment.,after the payment, can ship within short time hTtP://wWw.WoWcOoL.oRg
deleted 16y ago
[deleted]
kaib 16y ago
There is one interesting argument for not using the OS virtual memory system. By using VM you have just turned disk errors into RAM errors. Many programs can potentially handle disk corruption, almost none can cope with bad RAM.
_delirium 16y ago
I know infinitely less about caching and VM than the author of the linked article, but I was surprised by this part: Varnish also only has a single file on the disk whereas squid puts one object in its own separate file. The HTTP objects are not needed as filesystem objects, so there is no point in wasting time in the filesystem name space (directories, filenames and all that) for each object, all we need to have in Varnish is a pointer into virtual memory and a length, the kernel does the rest. I've had more than one systems person give me the opposite advice, that yes, using the OS's caching layer to do your disk/RAM balancing is good, but you should write into files that are divided on logical boundaries that correlate with how you use the data. Their argument was that this gives the caching layer more information, e.g. it can consolidate all your tiny objects into one part of the cache to avoid your small objects unnecessarily pinning a ton of VM pages, and can do things like prefetch pages when you start to read a big object, or even choose not to load a very large object into the cache at all if you're reading it sequentially (keeping it from clobbering the cache). When evicting pages it can also take small-versus-big-object and these-pages-go-together issues into account, as opposed to all pages looking alike. That's all hearsay, though, and I have no idea if it actually improves things in practice on current OSs or with which kinds of workloads.
- nkurz 16y ago
  Both arguments might be correct. If you are dealing with a language that makes a strong distinction between the object and the memory layout of that object, you might be better off handling the serialization yourself. But Varnish is in C, and data on disk is mapped to memory then used directly as a struct. Thus there are no small objects scattered around--- each 'object' is contiguous, and most likely on a single page. Prefetches happen automatically --- in Linux at least, disk caching and the VM are essentially synonymous. The benefit of using the VM directly with mmap() is that you have more control over the details and less overhead.
  - _delirium 16y ago
    > in Linux at least, disk caching and the VM are essentially synonymous Ah that could explain it. The people I know seem to be working on fs-level caches that operate at least in part on file granularity, so maybe they assume Linux/FBSD do fs-level stuff as well. They seem to try to do things like deciding whether to cache or not based in part on how big the file being read is, and what its historical usage patterns are.
deleted 16y ago
[deleted]
haberman 16y ago
This Squid vs. Varnish comparison is quite similar to the sync vs. async debate for network programming. In both cases, the question is: do I use some OS abstraction (Virtual Memory or threads, respectively) as my application's primary scheduling mechanism, or do I handle scheduling more explicitly at the application level? Of course the OS guys like PHK or Linus think you should use the OS mechanisms. Linus hates O_DIRECT (http://kerneltrap.org/node/7563 http://kerneltrap.org/node/7563) and PHK is taking a similar tack with this article. Just let the OS handle it. But there are real downsides to this approach. One is that it makes you far more dependent on the quality of the OS implementation. I'm sure PHK trusts FreeBSD and Linus trusts Linux, but if you're writing for cross-platform you might end up on a bad VM implementation. The last thing you want to tell your customers is that they have to upgrade or change their OS to get decent performance. Also, the OS is by design a more static and less flexible piece of software than anything you put in user-space. What if you need something that your VM system doesn't currently provide? For example, how are you going to measure (from user-space) the percentage of requests that incurred a disk read? Disk reads are invisible with mmap'd VM. What if you need to prioritize your I/O so that some requests get their disk reads serviced even if there are lots of low-priority reads already queued? If you've bought in whole-hog into an OS-based approach and your OS doesn't support features like this, you don't have a lot of options. And while it's great in lots of cases that the page cache can be shared across processes, OS's don't have great isolation between processes using the page cache. If you run some giant "cp" and completely trash the page cache, your Varnish process is likely to take a latency hit. In a shared server environment, you want to be able to draw walls of isolation so that each user gets the resources that he/she was promised. A shared page cache is hard to fit within an isolation model like this, whereas an explicit cache in user-space works fine. Think about the microkernel vs. monolithic kernel debate. Maybe monolithic kernels won, but it's still a good principle that if it can be left out of the kernel without loss of performance, it should. Why is it better to use an interface like VM than to use some user-space library that manages disk I/O? The kernel's one advantage is that it can handle page faults (and so can make a memory reference into an I/O operation), but that's also the property that makes it difficult to do good accounting of when you're actually incurring I/O operations. One final thing to mention: if you're using VM in this way, things degenerate badly in low-memory situations. Since the pages of data are competing with pages of the program itself, the program can get swapped out to service data I/O. If you've ever seen a Linux box thrash with its HDD light flashing like mad, you know how bad things can get when memory is temporarily too scarce to even let programs stay resident. Using vast amounts of VM exacerbates this, because it makes your programs and your data compete for the same RAM.
drv 16y ago
These "1975" programming concepts are essentially the same ideas taught in the CS computer architecture course I took (circa 2006). The main focus was on the memory hierarchy of modern computers, which was fine, but there was not much advice about letting virtual memory do its job - the course covered mostly how things work under the hood, but did not give practical programming recommendations. I can see how budding programmers could get the idea that "disks are slow, so I should try to manage when data gets copied to and from RAM" without realizing that the system software is already taking care of it and that attempting to do it manually will generally just make matters worse. As an aside, I found it really hard to read this article because of the grammar errors. Nearly every paragraph has a run-on sentence, and there's plenty of missing punctuation. The style also seemed more like off-the-cuff rambling (especially the long-winded attempts at humor near the beginning) than carefully-written advice, which almost made me stop reading before getting to the real content. The message is good, though, even obscured by these problems.
vladev 16y ago
Does anyone know a good book that explains these things (CPU caches, RAM, virtual memory, etc.) in more detail?
- lfittl 16y ago
  I've found "Inside the Machine" by Jon Stokes to be quite a good read, though it's a bit dated by now (published 2006) http://www.amazon.com/dp/1593271042/ http://www.amazon.com/dp/1593271042/
  - wmf 16y ago
    For programmers I would recommend a real computer architecture textbook (e.g. http://books.google.com/books?id=57UIPoLt3tkC http://books.google.com/books?id=57UIPoLt3tkC) instead of Stokes's analogy-laden book.
- 0bfusct3 16y ago
  Professional Linux Kernel Architecture has a good introduction into the Linux/os nomenclature.
afhof 16y ago
I was taught that the purpose of virtual memory was originally for running multiple programs without their memory spaces overlapping rather than to use more memory than the system actually had. Is this incorrect?
- HenryR 16y ago
  You're correct in a sense - virtual memory gives each process its own completely independent memory space that's addressed linearly. In order to preserve the illusion of independence, the OS has to deal with the possibility that the sum of the sizes of all the memory that each process wants to use might be greater than the amount of physical memory available. So rather than aggressively limit the amount of virtual address space that each process can use, it simply only keeps a subset of that memory in physical memory at any one time. You can have virtual memory without paging, but then each process has to compete for a very limited resource. You can also have paging without virtual memory - process A's copy of physical address X can be swapped out to be replaced with process B's copy. However processes are then still limited by having only as large an address space as physical memory in the machine, and virtual memory is such a huge win for hiding the layout of physical memory from processes as well as isolating them from one another (so no corruption possibilities) that it's pretty much unheard of to do this. You get such a big advantage from having a layer of indirection sometimes...
herf 16y ago
These systems seem to be, in practice, relying on having working sets that mostly fit in RAM. It's a nice world when you can stack 64GB in a box and never worry about disk, but having worked on systems that need more working set than this, I don't think this idea actually scales up as well as is claimed. Two issues: 1. Small objects aren't batched by a VM, so they can't be combined into long streaming writes and reads. Doing 4k writes and reads is useless on a modern disk. 128k to 1MB is more appropriate if you can organize things that way. 2. If your workload "mostly" fits in RAM, and then as your application scales, the working set exceeds RAM, you wind up doing some queries that are instant, and some that are a million times slower (a real, uncached disk seek). Unless you plan for this, your app can fall over and you just won't know what happened. You need to know the fraction of requests that will go to disk and plan to have spindles (or RAM) to handle it. I don't like systems that make measuring what's going on at this level any harder to do. The author's claim is that you get to share RAM with the VM, which is great, but in practice a lot of systems use kernel-supported sendfile() to do work (i.e. have a small streaming buffer per network connection), or cache super-hot objects in a relatively small amount of RAM. The assumption that all user-mode caches try to allocate as much RAM as possible is not true. Alternately, larger systems separate RAM cache entirely from disk-bound boxes (e.g., dedicated memcached). I think a more complete treatment of this problem would explain scaling over working set more aggressively, and it would explain using instrumentation how the system degrades at scale.
- jacquesm 16y ago
  Currently serving up billions of images per day from memory images that are more than 100 times the available physical memory (and there's plenty of that). Small objects can be batched in to a single page at the application level, the VM will then move these in and out of the resident pool as one unit. The operating system uses elevator sorting and knows enough about the disk that it will attempt to sequentially invalidate pages. The assumption is not that the working set will fit (mostly) in to RAM, the assumption is that a page fault is a relatively rare occurrence and that other threads will not be stalled by the IO done for one. It is the changes to the working set that determine page faults, not the size of the total set. On my boxes I solved one issue with this (and the maximum number of systemwide sockets) by running a varnish instance for every physical CPU in the machines.
Oxryly 16y ago
Hmm... I thought the scourge of 1975 programming was ignoring the vast and growing gap between the speed of the processor and the speed of RAM. 2010 programming has to deal with the fact that chasing a (non-cached) pointer can consume hundreds of processor cycles. So much for trees...
DannoHung 16y ago
I wish that this explanation could be expanded upon a little. Perhaps with some annotations of selected sections of the source code.
gwern 16y ago
Fighting with the OS - such as the VM system - is one of the primary arguments for exokernel-style OSs; see http://en.wikipedia.org/wiki/Exokernel http://en.wikipedia.org/wiki/Exokernel http://pdos.csail.mit.edu/exo.html http://pdos.csail.mit.edu/exo.html (In fact, I think one of their use cases showing an order of magnitude or 2 improvement specifically involves pairing an app with a custom VM algorithm.)
c00p3r 16y ago
There are so many cheap RAM and CPU idle circles that you even can build data storages or programming languages on top of ridiculously inefficient JVM. ^_^ The point is that there is the kernel to manage system resources, which is very good one.

293 points by dchest 16y ago

buro9 16y ago

I prefer the bit in this article: http://www.varnish-cache.org/wiki/ArchitectureInlineC http://www.varnish-cache.org/wiki/ArchitectureInlineC Where he says: "It is a particular common kind of hubris for IT architects, to think that they know better than 100% of everybody else, this is less of a sin in Open Source than in Closed Source, but a sin nontheless."

tptacek 16y ago

This is one of the best systems programming articles I've read in a very long time. Short summary: * 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.

gruseom 16y ago
Now that's interesting. I've been asking around for a while to find out what other systems programming experts think of this article, specifically the first point about not fighting with VM, which is the most prominent one (including in phk's provocative recent ACM article). I'd also like to know what other things, besides these, Varnish does to achieve its performance. I'm sold on the idea that most of us have been doing this kind of thing wrong. Let's hear more about how to do it right.
- tptacek 16y ago
  For what it's worth, I've been in and out of the FreeBSD kernel since 1995 and am an unabashed PHK fan.
- dedward 16y ago
  IT's not so much that it's "wrong" - it's just ignored. 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).
masklinn 16y ago
> hey, 'antirez, what's your take on that? You wrote an ad hoc pager for Redis Antirez referenced this article and explained why he disregarded these advices in the initial Redis VMEM post.
- tptacek 16y ago
  Neato; link?
  - bretthoerner 16y ago
    http://antirez.com/post/redis-virtual-memory-story.html http://antirez.com/post/redis-virtual-memory-story.html (See comments #29 and #30 for the reference)
    - masklinn 16y ago
      Mmmm crap technically he didn't reference this article (explicitly), I should have checked.
  - deleted 16y ago
    [deleted]
JoachimSchipper 16y ago
On one hand, mmap() is very nice. On the other, you may run into the limits on process size, and this is essentially unsolvable [1]. So your program is limited to 3GB of data on 32-bit machines. 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.
- masklinn 16y ago
  Admittedly, at this point you could probably consider that 32b machines are legacy and unsupported (FWIW there was a Steam stats thing posted a few months back indicating that more than half of their Windows 7 users were on 64b... I can only expect that those ratios are much higher for unices)
- nkurz 16y ago
  I understand the issue of process size, but I'm confused why this is a concern. 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.
  - JoachimSchipper 16y ago
    Yes, you can mmap() and munmap() as needed, but that makes things a lot less convenient - you'll still need to keep track of which data is on the disk and which data isn't, etc. At this point, you've already solved half of the problem of using malloc(), read() and free() instead of mmap() and munmap(). 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/ 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.)
antirez 16y ago
If you have mostly big objects (relative to hardware page size) and the encoding in memory and when stored on disk are pretty similar, this is indeed a good idea (to trust the virtual memory I mean). 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).
- cninja 16y ago
  What are the difficulties in using some sort of compression algorithm like LZJB on the disk's page file? 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.
  - antirez 16y ago
    A linked list is hard to compress in memory as the overhead is the metadata: pointers, malloc overhead, ... but when written on disk can be represented as prefixed length strings. With VM the live representation and serialization format are the same.
    - signa11 16y ago
      just curious: is it not possible to have some form of unrolled-linked-list to mitigate this effects somewhat ? or perhaps you have already tried it, and it doesn't really fit the bill.
      - nitrogen 16y ago
        It kind of sounds like you're describing a sparse array.
Locke1689 16y ago
It's pretty good. Maybe because I'm also a kernel developer, but these suggestions seem obvious to me. That is, instead of Varnish being novel and well-optimized, it appears that Varnish is pretty conventionally optimized and Squid is just a god-awful piece of development. 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).
- jacquesm 16y ago
  Varnish is a massive VM to network pipe, nothing 'sophisticated' happens to the data that it deals with. 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.
- SwellJoe 16y ago
  Squid is just a god-awful piece of development 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.
deleted 16y ago
[deleted]
strlen 16y ago
> hey, 'antirez, what's your take on that? You wrote an ad hoc pager for Redis. 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.
barrkel 16y ago
The major assumption is that the OS VMM's caching behaviour is as smart or smarter than the application's caching behaviour; that is, the operating system knows better than the application when to evict something from the cache. That may be true for many stupid applications, but I seriously doubt it's always the case.
- shabble 16y ago
  I was informed recently in a Masters level course on database implementation that databases typically wish to explicitly circumvent a lot of this caching, especially for IO buffering, since they can do the same thing at the app level, but leverage the fact they have much more well-defined access patterns than some generic kernel system that has to perform adequately across all workloads. 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.
  - btilly 16y ago
    Another big reasons that databases with to circumvent this caching is that they really, really need to make sure that when a transaction is committed, that they know what is on disk. Having the OS pretend stuff is written to disk is great for performance, but not so great when you're trying to recover after someone pulled the power.
    - dedward 16y ago
      This is where you get DBs that use their own raw block devices, as well as keeping transaction logs on other regular filesystems for integrity.... Oracle does something similar no?
  - dfox 16y ago
    For example PostgreSQL actually has almost none caching built-in and almost exclusively relies on OS (in default and recommended configuration). 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).
btilly 16y ago
Here is a contrarian perspective. 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.
- JulianMorrison 16y ago
  If you are running any modern program, there will be a proportion of its functionality and data you never use. That ends up paged to disk, freeing up RAM for what you do use. That's what VM is for, really. Using it as "memory" is very 1970s. It's more of a "forgettory".
  - btilly 16y ago
    If that works for you, then you obviously aren't trying to consistently hit a low latency SLA. Which brings me back to my point.
  - nostrademons 16y ago
    I suspect you're thinking "desktop" and btilly is thinking "server", and you're going to end up talking past each other. Or, if you are thinking servers, then you're thinking "one server" and he is thinking "one million servers". 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.
    - btilly 16y ago
      Shhh...don't give away any secrets. ;-) 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.

old-gregg 16y ago

MongoDB guys outsourced the entire caching/memory management to OS VM and on my (modest) workloads it performs really well. It probably also means that OS is a bit more relevant now and the choice b/w BSD/Linux isn't just about personal preference anymore, I can imagine that their VM characteristics are quite different and "2006 style" software like mongod won't work the same. Anyone with low-level experience with BSD/Linux VMs?

helmut_hed 16y ago

It seems to me that the first point made (on the performance of Squid's LRU caching) is really just that Squid is doing a bad job at it, and Varnish doesn't try at all (lets the VM system take care of it). In theory, managing memory at the object/application level should give you some advantages over doing it at the page/kernel level. I can imagine, for example, cases where Squid might perform better by moving entire objects to/from disk, rather than a page at a time in response to faults. In this case "1975 programming" really means trying to manage the memory hierarchy in the interest of performance, which is timeless. Indeed, the author later states that Varnish tries hard to "reuse memory which is likely to be in the caches", which sounds like the same idea applied to a different level.

JoachimSchipper 16y ago
The kernel VM system has a lot more ("global") information, though.

blueag 16y ago

Using the VM only work if the size of the cache fits in the process address space. If your cache size is greater than 4GB in a 32 bit machine, you will have to manage the cache on disk. It becomes less of a problem now with 64bit machine.

obama121012 16y ago

Happy shopping, happy with life, all in here,Please click: HtTp://WwW.wOwCoOl.OrG Dear Customer, How are you, There are many good products Please click the following URL http://wowcool.org/productlist.asp?id=s55 http://wowcool.org/productlist.asp?id=s55 【T-shirt】 http://wowcool.org/productlist.asp?id=s13 http://wowcool.org/productlist.asp?id=s13 【 MTB】 http://wowcool.org/productlist.asp?id=n49 http://wowcool.org/productlist.asp?id=n49 【Jordan 2010】 http://wowcool.org/productlist.asp?id=s44 http://wowcool.org/productlist.asp?id=s44 【Watch】 http://wowcool.org/productlist.asp?id=s46 http://wowcool.org/productlist.asp?id=s46 【Jewerly】 http://wowcool.org/productlist.asp?id=s45 http://wowcool.org/productlist.asp?id=s45 【Sunglass】 http://wowcool.org/productlist.asp?id=s60 http://wowcool.org/productlist.asp?id=s60 【Jean】 http://wowcool.org/productlist.asp?id=s53 http://wowcool.org/productlist.asp?id=s53 【handbags】 http://wowcool.org/productlist.asp?id=s68 http://wowcool.org/productlist.asp?id=s68 【Jacket】 The website wholesale for many kinds of fashion shoes, like the nike,jordan,prada,adidas, also including the jeans,shirts,bags,hat and the decorations. All the products are free shipping, and the the price is competitive, and also can accept paypal payment.,after the payment, can ship within short time hTtP://wWw.WoWcOoL.oRg

deleted 16y ago

[deleted]

kaib 16y ago

There is one interesting argument for not using the OS virtual memory system. By using VM you have just turned disk errors into RAM errors. Many programs can potentially handle disk corruption, almost none can cope with bad RAM.

_delirium 16y ago

I know infinitely less about caching and VM than the author of the linked article, but I was surprised by this part: Varnish also only has a single file on the disk whereas squid puts one object in its own separate file. The HTTP objects are not needed as filesystem objects, so there is no point in wasting time in the filesystem name space (directories, filenames and all that) for each object, all we need to have in Varnish is a pointer into virtual memory and a length, the kernel does the rest. I've had more than one systems person give me the opposite advice, that yes, using the OS's caching layer to do your disk/RAM balancing is good, but you should write into files that are divided on logical boundaries that correlate with how you use the data. Their argument was that this gives the caching layer more information, e.g. it can consolidate all your tiny objects into one part of the cache to avoid your small objects unnecessarily pinning a ton of VM pages, and can do things like prefetch pages when you start to read a big object, or even choose not to load a very large object into the cache at all if you're reading it sequentially (keeping it from clobbering the cache). When evicting pages it can also take small-versus-big-object and these-pages-go-together issues into account, as opposed to all pages looking alike. That's all hearsay, though, and I have no idea if it actually improves things in practice on current OSs or with which kinds of workloads.

nkurz 16y ago
Both arguments might be correct. If you are dealing with a language that makes a strong distinction between the object and the memory layout of that object, you might be better off handling the serialization yourself. But Varnish is in C, and data on disk is mapped to memory then used directly as a struct. Thus there are no small objects scattered around--- each 'object' is contiguous, and most likely on a single page. Prefetches happen automatically --- in Linux at least, disk caching and the VM are essentially synonymous. The benefit of using the VM directly with mmap() is that you have more control over the details and less overhead.
- _delirium 16y ago
  > in Linux at least, disk caching and the VM are essentially synonymous Ah that could explain it. The people I know seem to be working on fs-level caches that operate at least in part on file granularity, so maybe they assume Linux/FBSD do fs-level stuff as well. They seem to try to do things like deciding whether to cache or not based in part on how big the file being read is, and what its historical usage patterns are.

deleted 16y ago

[deleted]

haberman 16y ago

This Squid vs. Varnish comparison is quite similar to the sync vs. async debate for network programming. In both cases, the question is: do I use some OS abstraction (Virtual Memory or threads, respectively) as my application's primary scheduling mechanism, or do I handle scheduling more explicitly at the application level? Of course the OS guys like PHK or Linus think you should use the OS mechanisms. Linus hates O_DIRECT (http://kerneltrap.org/node/7563 http://kerneltrap.org/node/7563) and PHK is taking a similar tack with this article. Just let the OS handle it. But there are real downsides to this approach. One is that it makes you far more dependent on the quality of the OS implementation. I'm sure PHK trusts FreeBSD and Linus trusts Linux, but if you're writing for cross-platform you might end up on a bad VM implementation. The last thing you want to tell your customers is that they have to upgrade or change their OS to get decent performance. Also, the OS is by design a more static and less flexible piece of software than anything you put in user-space. What if you need something that your VM system doesn't currently provide? For example, how are you going to measure (from user-space) the percentage of requests that incurred a disk read? Disk reads are invisible with mmap'd VM. What if you need to prioritize your I/O so that some requests get their disk reads serviced even if there are lots of low-priority reads already queued? If you've bought in whole-hog into an OS-based approach and your OS doesn't support features like this, you don't have a lot of options. And while it's great in lots of cases that the page cache can be shared across processes, OS's don't have great isolation between processes using the page cache. If you run some giant "cp" and completely trash the page cache, your Varnish process is likely to take a latency hit. In a shared server environment, you want to be able to draw walls of isolation so that each user gets the resources that he/she was promised. A shared page cache is hard to fit within an isolation model like this, whereas an explicit cache in user-space works fine. Think about the microkernel vs. monolithic kernel debate. Maybe monolithic kernels won, but it's still a good principle that if it can be left out of the kernel without loss of performance, it should. Why is it better to use an interface like VM than to use some user-space library that manages disk I/O? The kernel's one advantage is that it can handle page faults (and so can make a memory reference into an I/O operation), but that's also the property that makes it difficult to do good accounting of when you're actually incurring I/O operations. One final thing to mention: if you're using VM in this way, things degenerate badly in low-memory situations. Since the pages of data are competing with pages of the program itself, the program can get swapped out to service data I/O. If you've ever seen a Linux box thrash with its HDD light flashing like mad, you know how bad things can get when memory is temporarily too scarce to even let programs stay resident. Using vast amounts of VM exacerbates this, because it makes your programs and your data compete for the same RAM.

drv 16y ago

These "1975" programming concepts are essentially the same ideas taught in the CS computer architecture course I took (circa 2006). The main focus was on the memory hierarchy of modern computers, which was fine, but there was not much advice about letting virtual memory do its job - the course covered mostly how things work under the hood, but did not give practical programming recommendations. I can see how budding programmers could get the idea that "disks are slow, so I should try to manage when data gets copied to and from RAM" without realizing that the system software is already taking care of it and that attempting to do it manually will generally just make matters worse. As an aside, I found it really hard to read this article because of the grammar errors. Nearly every paragraph has a run-on sentence, and there's plenty of missing punctuation. The style also seemed more like off-the-cuff rambling (especially the long-winded attempts at humor near the beginning) than carefully-written advice, which almost made me stop reading before getting to the real content. The message is good, though, even obscured by these problems.

vladev 16y ago

Does anyone know a good book that explains these things (CPU caches, RAM, virtual memory, etc.) in more detail?

lfittl 16y ago
I've found "Inside the Machine" by Jon Stokes to be quite a good read, though it's a bit dated by now (published 2006) http://www.amazon.com/dp/1593271042/ http://www.amazon.com/dp/1593271042/
- wmf 16y ago
  For programmers I would recommend a real computer architecture textbook (e.g. http://books.google.com/books?id=57UIPoLt3tkC http://books.google.com/books?id=57UIPoLt3tkC) instead of Stokes's analogy-laden book.
0bfusct3 16y ago
Professional Linux Kernel Architecture has a good introduction into the Linux/os nomenclature.

afhof 16y ago

I was taught that the purpose of virtual memory was originally for running multiple programs without their memory spaces overlapping rather than to use more memory than the system actually had. Is this incorrect?

HenryR 16y ago
You're correct in a sense - virtual memory gives each process its own completely independent memory space that's addressed linearly. In order to preserve the illusion of independence, the OS has to deal with the possibility that the sum of the sizes of all the memory that each process wants to use might be greater than the amount of physical memory available. So rather than aggressively limit the amount of virtual address space that each process can use, it simply only keeps a subset of that memory in physical memory at any one time. You can have virtual memory without paging, but then each process has to compete for a very limited resource. You can also have paging without virtual memory - process A's copy of physical address X can be swapped out to be replaced with process B's copy. However processes are then still limited by having only as large an address space as physical memory in the machine, and virtual memory is such a huge win for hiding the layout of physical memory from processes as well as isolating them from one another (so no corruption possibilities) that it's pretty much unheard of to do this. You get such a big advantage from having a layer of indirection sometimes...

herf 16y ago

These systems seem to be, in practice, relying on having working sets that mostly fit in RAM. It's a nice world when you can stack 64GB in a box and never worry about disk, but having worked on systems that need more working set than this, I don't think this idea actually scales up as well as is claimed. Two issues: 1. Small objects aren't batched by a VM, so they can't be combined into long streaming writes and reads. Doing 4k writes and reads is useless on a modern disk. 128k to 1MB is more appropriate if you can organize things that way. 2. If your workload "mostly" fits in RAM, and then as your application scales, the working set exceeds RAM, you wind up doing some queries that are instant, and some that are a million times slower (a real, uncached disk seek). Unless you plan for this, your app can fall over and you just won't know what happened. You need to know the fraction of requests that will go to disk and plan to have spindles (or RAM) to handle it. I don't like systems that make measuring what's going on at this level any harder to do. The author's claim is that you get to share RAM with the VM, which is great, but in practice a lot of systems use kernel-supported sendfile() to do work (i.e. have a small streaming buffer per network connection), or cache super-hot objects in a relatively small amount of RAM. The assumption that all user-mode caches try to allocate as much RAM as possible is not true. Alternately, larger systems separate RAM cache entirely from disk-bound boxes (e.g., dedicated memcached). I think a more complete treatment of this problem would explain scaling over working set more aggressively, and it would explain using instrumentation how the system degrades at scale.

jacquesm 16y ago
Currently serving up billions of images per day from memory images that are more than 100 times the available physical memory (and there's plenty of that). Small objects can be batched in to a single page at the application level, the VM will then move these in and out of the resident pool as one unit. The operating system uses elevator sorting and knows enough about the disk that it will attempt to sequentially invalidate pages. The assumption is not that the working set will fit (mostly) in to RAM, the assumption is that a page fault is a relatively rare occurrence and that other threads will not be stalled by the IO done for one. It is the changes to the working set that determine page faults, not the size of the total set. On my boxes I solved one issue with this (and the maximum number of systemwide sockets) by running a varnish instance for every physical CPU in the machines.

Oxryly 16y ago

Hmm... I thought the scourge of 1975 programming was ignoring the vast and growing gap between the speed of the processor and the speed of RAM. 2010 programming has to deal with the fact that chasing a (non-cached) pointer can consume hundreds of processor cycles. So much for trees...

DannoHung 16y ago

I wish that this explanation could be expanded upon a little. Perhaps with some annotations of selected sections of the source code.

gwern 16y ago

Fighting with the OS - such as the VM system - is one of the primary arguments for exokernel-style OSs; see http://en.wikipedia.org/wiki/Exokernel http://en.wikipedia.org/wiki/Exokernel http://pdos.csail.mit.edu/exo.html http://pdos.csail.mit.edu/exo.html (In fact, I think one of their use cases showing an order of magnitude or 2 improvement specifically involves pairing an app with a custom VM algorithm.)

c00p3r 16y ago

There are so many cheap RAM and CPU idle circles that you even can build data storages or programming languages on top of ridiculously inefficient JVM. ^_^ The point is that there is the kernel to manage system resources, which is very good one.