7 ms·

What's wrong with 2006 programming?

157 points by antirez 16y ago

wmf 16y ago
Just to amplify his point, if you want your program to take page faults as PHK suggests, it has to be multithreaded. If you choose event-driven concurrency you can't afford to take page faults in mmap() or read(). When you make the threads vs. events decision you're implicitly making a bunch of related decisions about I/O and scheduling as well; a hybrid approach (like using events and mmap) won't work well.
- antirez 16y ago
  Exactly: one of the two must be threaded, the swapping subsystem or the side serving clients. Since Redis serves clients in an event driven fashion our VM I/O part is threaded. But it was much simpler to design a threaded VM compared to a fully threaded Redis, and anyway there were other good reasons for implementing VM at application level.
- nostrademons 16y ago
  You can use events + mmap, you just need to factor the paging latency into your design. Normally, this might mean mmapping a chunk of data at startup, touching it all so that it's resident in RAM, and then beginning to serve queries, keeping an eye on your total resident set so that it never pages out.
  - rbranson 16y ago
    What would be the point of being able to spill to disk if you've got to keep everything in RAM? Simple serialization?
    - nostrademons 16y ago
      The point is zero-copy on load, not being able to spill to disk. Most high-performance, scalable servers I've seen ignore virtual memory entirely and kill (+ restart) the process if it exceeds the physical memory available on the machine. Yes, that means they use pre-1960s technology; sometimes, the price of performance is ignoring the programming conveniences we've come up with in the last 50 years.
      - rbranson 16y ago
        Most applications need to perform some computations with data that is read from the backing store. Even simple sorts and searches will vastly outweigh the cost of an extra memcpy. Honestly, an HTTP cache is sort of a perfect case for the way in which Varnish was implemented. There is very little actual processing, if any, that needs to be done with the data that's read from disk. It just needs to be read from the backing store and shuttled over the socket as fast as possible, with very little friction. An extra memcpy or two matter in the Varnish scenario.
  - jasonwatkinspdx 16y ago
    The entire point of redis's VM layer is to serve data sets larger than ram when the request distribution is such not everything need be memory resident (I believe this is sometimes referred to as the 1:10 problem in the redis community). While ram is far cheaper than it once was, there still are substantial savings in reducing your resident set requirements from TBs to just hundreds of GBs.
- rbranson 16y ago
  This is exactly how Varnish is setup. It's threads basically only exist for I/O reasons. It takes some serious fu to effectively mix event-driven and threaded programming.
- ntoshev 16y ago
  Be sure to check PHK's comment (#5) madvise + mincore syscalls could be used to get the kernel to preload the pages asynchronously.
  - wmf 16y ago
    Not really; because mincore() does not generate events you'd have to poll to find out when the page-in has finished, which seems pretty wasteful. If I was doing disk I/O from an event-driven program I would rather use the Flash approach of using a small number of worker threads to perform blocking I/O. PHK says "I consider this a deficiency in POSIX standards, not in the concept of VM.", but you have to go to production with the kernel you have, not the kernel you wish you had.
    - ntoshev 16y ago
      I agree you have to make it work with the real and not ideal kernel :) Another thing PHK misses is that single-threaded approach solves the database concurrency problems for free, and people start to use it more - e.g. Stonebraker in his VoltDB. Polling mincore wouldn't be that bad as it would only happen between the commands and at least the core of the algorithm would be simple: before executing a command, check if it's data are in memory with mincore, if not ask to load them with madvise, and go to the next command. What does Flash use worker threads for?
      - wmf 16y ago
        Flash used worker threads for any operation that could potentially block, like disk reads. http://www.usenix.org/event/usenix99/full_papers/pai/pai_html/paper-html.html http://www.usenix.org/event/usenix99/full_papers/pai/pai_htm...
- shin_lao 16y ago
  Actually the hybrid approach works extremely well, it's just more delicate to architecture. The idea is to process in parallel everything you can and have the services ("processors") communicate asynchronously by events.
scott_s 16y ago
Again, the kernel will use a simple LRU algorithm, where the granularity is the page. I don't think it's accurate to describe any performance critical part of the Linux kernel as "simple." For an overview of the page replacement policy, see http://kerneltrap.org/node/7608 http://kerneltrap.org/node/7608. I wondered if CLOCK-Pro [1, 2] had made it into the kernel yet, but it looks like it has not. This author makes compelling arguments for implementing application level paging. But the nice thing about doing systems work is we never have to rely on arguments alone to evaluate something - show me numbers. [1] http://linux-mm.org/ClockProApproximation http://linux-mm.org/ClockProApproximation [2] http://www.cse.ohio-state.edu/~fchen/paper/papers/usenix05.pdf http://www.cse.ohio-state.edu/~fchen/paper/papers/usenix05.p...
- bch 16y ago
  There was no mention of Linux in the article. This system also runs on the various *BSDs, Solaris, MacOS...
  - scott_s 16y ago
    Then it's worth noting that CLOCK-Pro is used in NetBSD. My point here is that a lot of people have spent a lot of time working on the page replacement problem. I am very open to the idea that an application can beat the page replacement policy in the underlying kernel, for a variety of reasons. But: numbers. Always evaluate. The implementation of these algorithms in practice is always more subtle than our high level understanding, so we need to do real performance comparisons to know if we actually improved anything. (I'm getting my information from the algorithm's author's page: http://www.ece.eng.wayne.edu/~sjiang/ http://www.ece.eng.wayne.edu/~sjiang/ Jiang graduated from William and Mary while I was a young grad student there.)
    - bch 16y ago
      Agreed. "Problems" without measurements aren't worth much. My initial reaction was to your assumption about Linux, but we agree that assumptions in general aren't worth much.
    - 16y ago
wingo 16y ago
Fascinating article. I wonder how SSDs affect his conclusions, though. If you really care, don't you have an SSD? Especially for the recently mentioned 1:10 problem (10G of data, 1G of memory).
- deleted 16y ago
  [deleted]
bediger 16y ago
I blame Benjamin Zorn in this paper: http://www.cs.colorado.edu/department/publications/reports/docs/CU-CS-665-93.pdf http://www.cs.colorado.edu/department/publications/reports/d... for the whole "programmers shouldn't manage memory" myth. Clearly, if you know what you're doing, you can do better than the OS and/or malloc() does. If you don't know what you're doing, you have bigger problems than writing your own allocator will quickly solve.
- gjm11 16y ago
  It seems a bit strange to blame Zorn for spreading the myth that "programmers shouldn't manage memory" on the basis of that paper, when at about the same time he was writing a bunch of other papers extolling the virtues of customized memory allocators: http://portal.acm.org/citation.cfm?id=172674 http://portal.acm.org/citation.cfm?id=172674, for instance.
  - bediger 16y ago
    Did you read the "CustoMalloc" paper? It's more of the same. Just to illustrate, the paper you referenced has the title "CustoMalloc: efficient synthesized memory allocator". That is, "CustoMalloc" takes a look at memory usage patterns of a particular program, then generates a semi-customized allocator for that program.
    - gjm11 16y ago
      Yes, of course I read it. Yes, the allocators are synthesized; so what? The point is that "synthesize a semi-customized allocator for each program" is a very different thing from "just use what the system provides you with; you won't be able to do better".
- kenjackson 16y ago
  But the real point isn't "can you do a better job", but is it worth it to a better job? If I can use an OTS memory allocator and get within 2% of my hand-crafted hand-tuned allocator, I think I'd need to be extremely perf sensitive to care.
moron4hire 16y ago
Something like paging virtual memory for Redis is going to be a core feature. I can completely understand why they would want to keep core features "in house". It's not "not implemented here" syndrome if the entire point of your company is to implement things like this.
- davidw 16y ago
  The code is open source under a BSD style license, so it's not really about benefits for the company, which in this case is VMWare. They make their money elsewhere and pay antirez to hack on Redis, which is a pretty good deal for users of Redis.
stephen 16y ago
I'm not an expert, but the application's memory usage being opaque to the kernel sounds vaguely like the problems Azul had scaling its Java runtime to large (>2GB) heaps. Azul recently open sourced some of their kernel patches: http://www.managedruntime.org/faq http://www.managedruntime.org/faq But that is about all I know.
poet 16y ago
Weird to see PHK being referred to as "the Varnish guy". :P
- Argorak 16y ago
  Especially as everyone should know that he is "the bikeshed guy" :).
  - gjm11 16y ago
    What colour should the varnish on the bikeshed be?
- antirez 16y ago
  Fixed in the article, sorry I was not aware that the "Varnish guy" was a well known programmer.
  - jacquesm 16y ago
    It's like referring to Donald Knuth as 'the TeX guy'.
    - antirez 16y ago
      With all the respect, I wish Poul-Henning Kamp the biggest of the fame, but it is hard to compare him with a world wide myth as Donald Knuth.
    - gwtw 16y ago
      Or a "CS Dude"[1]: [1]: "So, yes, Knuth and all the other CS dudes had their math figured out right." - The Varnish guy http://queue.acm.org/detail.cfm?id=1814327 http://queue.acm.org/detail.cfm?id=1814327
fleitz 16y ago
Stop thinking of RAM/disk/etc as storage systems and start thinking of them as retrieval systems. Then stop thinking of your data costs as $/GB (storage systems) and start thinking of your data costs as $/(IO/sec/GB) (retrieval systems). I know everyone these days seems to think that removing a structured query language parser from a database makes every other problem go away, but realistically RDBMS vendors spend millions of dollars trying to fix this exact problem. It's called cache invalidation and it's a hard problem to solve in a general way. SSDs are just a midpoint in the performance trade-off game. The OS is the worst at this, DBs are somewhat better, but realistically if you want serious performance out of your application you need to make those choices for yourself, and use all strategies where appropriate RAM for records you need instantly (memcache,redis,mongodb) SSDs for the stuff you can't afford to keep on an SSD And hard drives for stuff you can't afford to keep on an SSD. What you need to think about is the value of your data in dollars per IO/sec per DB ($/(IO/sec/GB), if the amortized value of that data exceeds the amortized cost of the retrieval system then buy it. Focus on increasing the value of your data, not reducing the costs of it's retrieval as that will drop by 1/2 every 18 months anyway. Alternatively, change your business model so you are going short on IO/sec/GB, (eg. pre-sell storage so that when you need to buy it you can do so cheaply) What I'm trying to say is that the value of a picture is worth more to Flickr than it is to Facebook, thus Flickr will have an easier time building it's retrieval systems than Facebook because of the costs involved. That's why Facebook had to write their own filesystem for retrieving pictures. I'd bet that any commercial DB will blow rings around redis/mongo/etc if you had your persistent store as a RAM disk and used hard drives for the transaction log. The cost of a SQL Server license is negligible if you're going to buy a server with $200,000 worth of RAM in it. If your data is valuable enough you could just keep everything in SRAM (L1/L2 cache) and buy processors just for the cache.
- jasonwatkinspdx 16y ago
  This has been well understood since antiquity (in the CS world at least). Read Jim Gray's "The 5 minute rule" and the more recent papers that cite it. Most likely the access frequency of your objects is not such to demand them residing in L2. Ultimately there's no need to use a commercial database either, as there are compelling open source alternatives, though if your needs are very specific, a commercial database may be your best tool.
deleted 16y ago
[deleted]
jamii 16y ago
In a vaguely similar vein, the recent Mirage paper showed impressive GC improvements by running ocaml on xen without an operating system in between. It allowed them to use a much simpler allocation algorithm. http://anil.recoil.org/papers/2010-hotcloud-lamp.pdf http://anil.recoil.org/papers/2010-hotcloud-lamp.pdf

157 points by antirez 16y ago

wmf 16y ago

Just to amplify his point, if you want your program to take page faults as PHK suggests, it has to be multithreaded. If you choose event-driven concurrency you can't afford to take page faults in mmap() or read(). When you make the threads vs. events decision you're implicitly making a bunch of related decisions about I/O and scheduling as well; a hybrid approach (like using events and mmap) won't work well.

antirez 16y ago
Exactly: one of the two must be threaded, the swapping subsystem or the side serving clients. Since Redis serves clients in an event driven fashion our VM I/O part is threaded. But it was much simpler to design a threaded VM compared to a fully threaded Redis, and anyway there were other good reasons for implementing VM at application level.
nostrademons 16y ago
You can use events + mmap, you just need to factor the paging latency into your design. Normally, this might mean mmapping a chunk of data at startup, touching it all so that it's resident in RAM, and then beginning to serve queries, keeping an eye on your total resident set so that it never pages out.
- rbranson 16y ago
  What would be the point of being able to spill to disk if you've got to keep everything in RAM? Simple serialization?
  - nostrademons 16y ago
    The point is zero-copy on load, not being able to spill to disk. Most high-performance, scalable servers I've seen ignore virtual memory entirely and kill (+ restart) the process if it exceeds the physical memory available on the machine. Yes, that means they use pre-1960s technology; sometimes, the price of performance is ignoring the programming conveniences we've come up with in the last 50 years.
    - rbranson 16y ago
      Most applications need to perform some computations with data that is read from the backing store. Even simple sorts and searches will vastly outweigh the cost of an extra memcpy. Honestly, an HTTP cache is sort of a perfect case for the way in which Varnish was implemented. There is very little actual processing, if any, that needs to be done with the data that's read from disk. It just needs to be read from the backing store and shuttled over the socket as fast as possible, with very little friction. An extra memcpy or two matter in the Varnish scenario.
- jasonwatkinspdx 16y ago
  The entire point of redis's VM layer is to serve data sets larger than ram when the request distribution is such not everything need be memory resident (I believe this is sometimes referred to as the 1:10 problem in the redis community). While ram is far cheaper than it once was, there still are substantial savings in reducing your resident set requirements from TBs to just hundreds of GBs.
rbranson 16y ago
This is exactly how Varnish is setup. It's threads basically only exist for I/O reasons. It takes some serious fu to effectively mix event-driven and threaded programming.
ntoshev 16y ago
Be sure to check PHK's comment (#5) madvise + mincore syscalls could be used to get the kernel to preload the pages asynchronously.
- wmf 16y ago
  Not really; because mincore() does not generate events you'd have to poll to find out when the page-in has finished, which seems pretty wasteful. If I was doing disk I/O from an event-driven program I would rather use the Flash approach of using a small number of worker threads to perform blocking I/O. PHK says "I consider this a deficiency in POSIX standards, not in the concept of VM.", but you have to go to production with the kernel you have, not the kernel you wish you had.
  - ntoshev 16y ago
    I agree you have to make it work with the real and not ideal kernel :) Another thing PHK misses is that single-threaded approach solves the database concurrency problems for free, and people start to use it more - e.g. Stonebraker in his VoltDB. Polling mincore wouldn't be that bad as it would only happen between the commands and at least the core of the algorithm would be simple: before executing a command, check if it's data are in memory with mincore, if not ask to load them with madvise, and go to the next command. What does Flash use worker threads for?
    - wmf 16y ago
      Flash used worker threads for any operation that could potentially block, like disk reads. http://www.usenix.org/event/usenix99/full_papers/pai/pai_html/paper-html.html http://www.usenix.org/event/usenix99/full_papers/pai/pai_htm...
shin_lao 16y ago
Actually the hybrid approach works extremely well, it's just more delicate to architecture. The idea is to process in parallel everything you can and have the services ("processors") communicate asynchronously by events.

scott_s 16y ago

Again, the kernel will use a simple LRU algorithm, where the granularity is the page. I don't think it's accurate to describe any performance critical part of the Linux kernel as "simple." For an overview of the page replacement policy, see http://kerneltrap.org/node/7608 http://kerneltrap.org/node/7608. I wondered if CLOCK-Pro [1, 2] had made it into the kernel yet, but it looks like it has not. This author makes compelling arguments for implementing application level paging. But the nice thing about doing systems work is we never have to rely on arguments alone to evaluate something - show me numbers. [1] http://linux-mm.org/ClockProApproximation http://linux-mm.org/ClockProApproximation [2] http://www.cse.ohio-state.edu/~fchen/paper/papers/usenix05.pdf http://www.cse.ohio-state.edu/~fchen/paper/papers/usenix05.p...

bch 16y ago
There was no mention of Linux in the article. This system also runs on the various *BSDs, Solaris, MacOS...
- scott_s 16y ago
  Then it's worth noting that CLOCK-Pro is used in NetBSD. My point here is that a lot of people have spent a lot of time working on the page replacement problem. I am very open to the idea that an application can beat the page replacement policy in the underlying kernel, for a variety of reasons. But: numbers. Always evaluate. The implementation of these algorithms in practice is always more subtle than our high level understanding, so we need to do real performance comparisons to know if we actually improved anything. (I'm getting my information from the algorithm's author's page: http://www.ece.eng.wayne.edu/~sjiang/ http://www.ece.eng.wayne.edu/~sjiang/ Jiang graduated from William and Mary while I was a young grad student there.)
  - bch 16y ago
    Agreed. "Problems" without measurements aren't worth much. My initial reaction was to your assumption about Linux, but we agree that assumptions in general aren't worth much.
  - 16y ago

wingo 16y ago

Fascinating article. I wonder how SSDs affect his conclusions, though. If you really care, don't you have an SSD? Especially for the recently mentioned 1:10 problem (10G of data, 1G of memory).

deleted 16y ago
[deleted]

bediger 16y ago

I blame Benjamin Zorn in this paper: http://www.cs.colorado.edu/department/publications/reports/docs/CU-CS-665-93.pdf http://www.cs.colorado.edu/department/publications/reports/d... for the whole "programmers shouldn't manage memory" myth. Clearly, if you know what you're doing, you can do better than the OS and/or malloc() does. If you don't know what you're doing, you have bigger problems than writing your own allocator will quickly solve.

gjm11 16y ago
It seems a bit strange to blame Zorn for spreading the myth that "programmers shouldn't manage memory" on the basis of that paper, when at about the same time he was writing a bunch of other papers extolling the virtues of customized memory allocators: http://portal.acm.org/citation.cfm?id=172674 http://portal.acm.org/citation.cfm?id=172674, for instance.
- bediger 16y ago
  Did you read the "CustoMalloc" paper? It's more of the same. Just to illustrate, the paper you referenced has the title "CustoMalloc: efficient synthesized memory allocator". That is, "CustoMalloc" takes a look at memory usage patterns of a particular program, then generates a semi-customized allocator for that program.
  - gjm11 16y ago
    Yes, of course I read it. Yes, the allocators are synthesized; so what? The point is that "synthesize a semi-customized allocator for each program" is a very different thing from "just use what the system provides you with; you won't be able to do better".
kenjackson 16y ago
But the real point isn't "can you do a better job", but is it worth it to a better job? If I can use an OTS memory allocator and get within 2% of my hand-crafted hand-tuned allocator, I think I'd need to be extremely perf sensitive to care.

moron4hire 16y ago

Something like paging virtual memory for Redis is going to be a core feature. I can completely understand why they would want to keep core features "in house". It's not "not implemented here" syndrome if the entire point of your company is to implement things like this.

davidw 16y ago
The code is open source under a BSD style license, so it's not really about benefits for the company, which in this case is VMWare. They make their money elsewhere and pay antirez to hack on Redis, which is a pretty good deal for users of Redis.

stephen 16y ago

I'm not an expert, but the application's memory usage being opaque to the kernel sounds vaguely like the problems Azul had scaling its Java runtime to large (>2GB) heaps. Azul recently open sourced some of their kernel patches: http://www.managedruntime.org/faq http://www.managedruntime.org/faq But that is about all I know.

poet 16y ago

Weird to see PHK being referred to as "the Varnish guy". :P

Argorak 16y ago
Especially as everyone should know that he is "the bikeshed guy" :).
- gjm11 16y ago
  What colour should the varnish on the bikeshed be?
antirez 16y ago
Fixed in the article, sorry I was not aware that the "Varnish guy" was a well known programmer.
- jacquesm 16y ago
  It's like referring to Donald Knuth as 'the TeX guy'.
  - antirez 16y ago
    With all the respect, I wish Poul-Henning Kamp the biggest of the fame, but it is hard to compare him with a world wide myth as Donald Knuth.
  - gwtw 16y ago
    Or a "CS Dude"[1]: [1]: "So, yes, Knuth and all the other CS dudes had their math figured out right." - The Varnish guy http://queue.acm.org/detail.cfm?id=1814327 http://queue.acm.org/detail.cfm?id=1814327

fleitz 16y ago

Stop thinking of RAM/disk/etc as storage systems and start thinking of them as retrieval systems. Then stop thinking of your data costs as $/GB (storage systems) and start thinking of your data costs as $/(IO/sec/GB) (retrieval systems). I know everyone these days seems to think that removing a structured query language parser from a database makes every other problem go away, but realistically RDBMS vendors spend millions of dollars trying to fix this exact problem. It's called cache invalidation and it's a hard problem to solve in a general way. SSDs are just a midpoint in the performance trade-off game. The OS is the worst at this, DBs are somewhat better, but realistically if you want serious performance out of your application you need to make those choices for yourself, and use all strategies where appropriate RAM for records you need instantly (memcache,redis,mongodb) SSDs for the stuff you can't afford to keep on an SSD And hard drives for stuff you can't afford to keep on an SSD. What you need to think about is the value of your data in dollars per IO/sec per DB ($/(IO/sec/GB), if the amortized value of that data exceeds the amortized cost of the retrieval system then buy it. Focus on increasing the value of your data, not reducing the costs of it's retrieval as that will drop by 1/2 every 18 months anyway. Alternatively, change your business model so you are going short on IO/sec/GB, (eg. pre-sell storage so that when you need to buy it you can do so cheaply) What I'm trying to say is that the value of a picture is worth more to Flickr than it is to Facebook, thus Flickr will have an easier time building it's retrieval systems than Facebook because of the costs involved. That's why Facebook had to write their own filesystem for retrieving pictures. I'd bet that any commercial DB will blow rings around redis/mongo/etc if you had your persistent store as a RAM disk and used hard drives for the transaction log. The cost of a SQL Server license is negligible if you're going to buy a server with $200,000 worth of RAM in it. If your data is valuable enough you could just keep everything in SRAM (L1/L2 cache) and buy processors just for the cache.

jasonwatkinspdx 16y ago
This has been well understood since antiquity (in the CS world at least). Read Jim Gray's "The 5 minute rule" and the more recent papers that cite it. Most likely the access frequency of your objects is not such to demand them residing in L2. Ultimately there's no need to use a commercial database either, as there are compelling open source alternatives, though if your needs are very specific, a commercial database may be your best tool.

deleted 16y ago

[deleted]

jamii 16y ago

In a vaguely similar vein, the recent Mirage paper showed impressive GC improvements by running ocaml on xen without an operating system in between. It allowed them to use a much simpler allocation algorithm. http://anil.recoil.org/papers/2010-hotcloud-lamp.pdf http://anil.recoil.org/papers/2010-hotcloud-lamp.pdf