A few years back a non-technical person asked me to explain what, exactly, the operating system did. I first started out by speaking in broad generalities, saying that it takes care of the basic needs of the computer and that it helps one thing talk to another. But that answer wasn't good enough. This person wanted me to go into more detail. What happens when I'm in the calculator application and I type 1+1 and hit enter? What things need to happen?
That really tripped me up. It's hard to even know where to start when someone who's curious like that asks a relatively innocent question like that. So I decided to just start from the basics. "A processor has these things called registers", I said. "And they store a tiny little amount of information, which they can do things with, like add and subtract." That seemed to basically satisfy them, but not me.
I made sure to say that, "You can't just keep everything in registers, because there are only a few of those. So you have to keep some data stored in this place with more space for data but it's slower." To which they responded, "Oh, so is that why when I add more RAM my computer gets faster?" "No," I said, "this is all still on the processor." "OK, so what's RAM then and why is it supposed to help?" they asked. "Because we can't store everything on the processor itself, because there's not enough space for data, so we have to store it in this place with much more space for data, but which is slower."
At this point I realized how redundant this conversation was going to get. It's the same thing for the hard drive, and (if you're old-school) tape drive or (if you're new-school) the internet. At the same point that person seemed to get bored--that moment of curiosity had passed. Computers just do their thing and we really didn't have to do anything special for all of that data movement to take place.
That's what struck me. When you come down to it, computers are just a waterfall of different caches, with systems that determine what piece of data goes where and when. For the most part, in user space, we don't care about much of that either. When writing a web application or even a desktop application, we don't much care whether a bit is in the register, the L1 or L2 cache, RAM, or if it's being swapped to disk. We just care that whatever system is managing that data, it's doing the best it can to make our application fast.
But then another thing struck me. Most web developers DO have to worry about the cache. We do it every day. Whether you're using memcached or velocity or some other caching system, everyone's manually moving data from the database to a cache layer, and back again. Sometimes we do clever things to make sure this cached data is correct, but sometimes we do some braindead things. We certainly manage the cache keys ourselves and we come up with systems again and again to do the same thing.
Does this strike anyone else as inconsistent? For practically every cache layer down the chain, a system (whose algorithms are usually the result of years and years of work and testing) automatically determines how to best utilize that cache, yet we do not yet have a good system for doing that with databases. Why do you think that is? Is it truly one of the two hard problems of computer science? Is it impossible to do this automatically? I honestly don't have the answers, but I'm interested if you do.
All Content
By Ocean at 4:20 a.m. on Nov. 8, 2008
Work from MSR: ftp://ftp.research.microsoft.com/users/palarson/mtcachedebull.pdf :
" MTCache is a prototype mid-tier database caching solution for SQL Server that transparently offloads part of the query workload from a backend server to front-end servers. The goal is to improve
system throughput and scalability but without requiring application changes..."
ftp://ftp.research.microsoft.com/pub/debull/A04june/bornhoevd.ps :
"Caching as a means to improve scalability, throughput, and response time for Web applications has re-
ceived a lot of attention. Caching can take place at different levels in a multi-tier architecture. However,
due to the increased personalization and dynamism in Web content, caching at the bottom of the multi-
tier architecture – the database level – can be beneficial to all upper levels because of better reusability
of the cached data..."
By bill at 9 a.m. on Nov. 8, 2008
isn't there an old line that goes something like "programming is an exercise in caching"?
By manthrax at 9:17 a.m. on Nov. 8, 2008
I think I first saw that quote, "all programming is an exercise in caching" in the Black Art of Game Programming book, by Michael Abrash, attributed to Terje Matheson, an apparently god-like assembly language hand optimizer.
By Eric Florenzano at 2:49 p.m. on Nov. 8, 2008
That's really insightful. I hadn't heard that one!
By Ryan at 1:08 p.m. on Nov. 8, 2008
Actually the data layer caches, the file system layer caches, the web server caches, the client browser caches, the middleware possibly caches. I bet if you zoom in on any layer it is a bit chaotic, just like the application layer or presentation layer.
The thing is those layers are mechanical in their requests, it is always for known paths, types, etc.
With web we are the layer dealing with human interaction and irrational and unpredictable patterns. So caching has to be a top demand thing, keyword caching can't be too overly cache heavy but more the top 500 terms.
Caching is difficult on a rapidly changing data state layer. What to cache, what not to cache, how many layers of cache, caching and clustering and keeping data real-time. All very difficult things, the front we are on now is here. When we get this figured the next level will be more choatic.
By Grammer Nazi at 1:19 p.m. on Nov. 8, 2008
In reference to the last paragraph.
Are you really trying to say that there are only two hard problems for computers, and that this is one of them?
...or did you mean "too" ?
By Eric Florenzano at 2:51 p.m. on Nov. 8, 2008
Actually I was referring to the classic Phil Karlton quote, "There are only two hard things in Computer Science: cache invalidation and naming things". http://www.tbray.org/ongoing/When/200x/2005/12/23/UPI Obviously that's a gross oversimplification but at times it certainly seems true.
By Aaron Boodman at 1:35 p.m. on Nov. 8, 2008
Many desktop applications *do* care quite a bit about whether something is in RAM or on the disk. Server applications I have worked on have also tried very hard to keep everything they need for a given user in RAM.
I think it may have been a mistake for the desktop OSes to try and abstract the difference between RAM and disk away as much as they did. Making synchronous calls to the disk is one reason Windows tends to hang so much when opening file dialogs, opening explorer, etc.
By Eric Florenzano at 2:56 p.m. on Nov. 8, 2008
That's true, and perhaps I took my point a bit too far in talking about RAM/Disk. That being said, do you think that this abstraction should be lifted for everything? For the on-die caches etc.? I think that there's a reasonable amount of abstraction that's good for dealing with caches, but I agree, when it comes to RAM vs. Disk, it's good to care where your data is.
By Jimbo at 2:08 p.m. on Nov. 8, 2008
Maurice Wilkes (http://en.wikipedia.org/wiki/Maurice_Wilkes), said that all of computer science is either caching or abstraction.
Seemed an offhand comment when I first heard it, but it's surprisingly true and insightful.
By Evan at 2:26 p.m. on Nov. 8, 2008
This is very insightful. Thank you for sharing with us!
By robolange at 3:21 p.m. on Nov. 8, 2008
Part 1
It is gross oversimplification to say that we have systems that automatically determine the best utilization of caches. Modern compilers and operating systems are designed with some relatively simple heuristics to try to make good use of the cache hierarchy for the average case, but this is typically far from optimal. For any particular data-bound program, hand-optimization (and by that I mean writing high-level code differently, not necessarily writing in assembly) of the dominant parts of the program will almost always yield significant performance improvements and reductions of cache misses over that of static compiler optimizations. (Whether performance is a sufficiently important requirement to go to this expense for a particular program is a different issue.)
Continued...
By robolange at 3:22 p.m. on Nov. 8, 2008
Part 2
Optimizing compilers can do a lot for us in terms of register allocation, and OS memory management can try to keep frequently-used data in RAM. However, individual programmers must still take great care to write their code to make the best use of the cache hierarchy.
Many optimizations, which cannot be made automatically by a compiler, are machine-independent, so a programmer can learn to write with these optimizations and improve cache use in general for programs. However, many optimizations are machine-specific (due to varying cache sizes and cache replacement policies of the hardware, among other parameters), and must be redone every time the hardware platform changes. For well-known mathematical problems, special-purpose compiler systems have been built to optimize the mathematics code automatically for an individual machine (e.g., Spiral, FFTW, ATLAS). In general, though, only experimentation and hand-optimization work.
Continued...
By robolange at 3:22 p.m. on Nov. 8, 2008
Part 3
All of this ignores the effects of multiple processor systems and heterogeneous architectures (e.g., CPU+GPU), which add yet more layers of complexity.
So cache hierarchy utilization is still very much an open problem in computer science. Given that, it is only natural that more complex lower layers of the hierarchy, such as database accesses, require even more effort by programmers to use correctly.
By Scott Walters at 4:02 p.m. on Nov. 8, 2008
Yes. This does strike me. At some point, "single image" clustering was developed, where processors linked together over interconnects appeared as one large computer, primarily to support scientific computing, where one application required lots of processong power and RAM. Other lesser (more manual) versions of clustering were created -- primarily to support database. But now as web developers tend to use the database as the interconnect, but not on top of any sort of cluster. A bit ironic if you ask me. I work on http://search.cpan.org/author/AWWAIID/Continuity-0.996/lib/Continuity.pm by the way. Web development has a long way to go before its up to what we had in the 80's.
-scott
By Timothy Fitz at 4:26 p.m. on Nov. 8, 2008
There *are* good ways to do caching, the problem is that if your cache is correct, i.e. it supports ACID and never returns stale data then you've gone and reimplemented your backing store.
The dramatic benefits from Memcache come from forcing you to add tolerable data lag into your system. In exchange for inaccuracy you can gain dramatic performance enhancements.
To take your analogy a further step, your application level caching policy is the equivalent of the processors memory model: What guarantees does your caching layer give you? Thankfully on x86, there are -alot- of guarantees, and things pretty much work the way you would expect. On other architectures your threads can be given stale cached data from L1/L2 cache. You're back in the world of data inaccuracy vs efficiency.
So to make a long story short, all you really want are caching primitives that are easy to drop-in and have understandable speed/accuracy tradeoffs.
By pc486 at 6:09 p.m. on Nov. 8, 2008
Congratulations, you've rediscovered the memory hierarchy <http://en.wikipedia.org/wiki/Memory_hierarchy>. There is no One True Way when it comes to deciding what should be pushed up or down the hierarchy. This is why kernels offer hinting methods like the madvise() system call. Even databases have solid cache systems but are often left under engineered in the real world.
Web developers often use caches off the database due to a few aspects inherent with databases. Computing values from a normalized database takes time, and so it's a good target for memorization. Even if it's cheap to compute or pull at the database, the HTTP daemon might not be on the same computer. Now we have TCP connections to start, perhaps out of a connection pool (another cache!), but even that wont save you from latencies inherent with networks. Then there's always the issue with poorly designed, setup and maintained database servers; a common occurrence in the wild.
By Tim at 7:16 p.m. on Nov. 8, 2008
Maybe you should explain what system you're using, and what kind of "worrying" you're doing. :-) From what I've seen, it's about as automatic at the web-dev level as anywhere else -- the only difference is that since it's an open-source piece of software and not baked in (like, say, my L2 caches), you can inspect and tweak it, so we do.
Your RDBMS has its own caching subsystem (which you can tweak, but I never have). If you use Memcached, you add maybe one line to your config that tells your framework where to find it, and it uses that for free. Just like your CPU and OS, if you add a cache to the system, your stuff just goes faster.
By Tim at 7:16 p.m. on Nov. 8, 2008
...
If anything, web developers are working with bigger systems than before (like tens or hundreds of gigabytes, or more), so making the caches work just right is more important, so we tweak them. (Also, you tweak it in one place and everybody benefits, as opposed to, say, 3d game programmers, who also care about caches but have much less control over the memory subsystem that it'll be run on.) I suspect your other caches aren't all that perfect -- does anybody even know what their L2 hit rate is? I know my swap system is sometimes ridiculously stupid.
I guess there's also no economic incentive to make it tweakable. A CPU (or any hardware unit) with a fixed caching algorithm is simpler and cheaper to make, and they make you buy a new one to get the new algorithm. Whereas free software libraries have a great incentive to make it tweakable.
By Christie Hines at 3:51 p.m. on Nov. 12, 2008
8knp0n618f45yass
By bopdilly at 6:25 a.m. on Nov. 16, 2008
Excellent site! I wish the owner to develop and please all! http://sex-free-online.ru/map.html
By videoonlinego at 5:47 p.m. on Nov. 17, 2008
It is not out-of-date information? Because I have other data on this theme. http://video-online-go.ru/map.html
By googlaaa at 3:21 p.m. on April 23, 2009
MYwRfJ http://google.com
By ben 10 oyunları at 3:06 a.m. on May 25, 2009
For the on-die caches etc.? I think that there's a reasonable amount of abstraction that's good for dealing with caches, but I agree, when it comes to RAM vs. Disk, it's good to care where your data is.
By buy cheap wow gold at 4:43 a.m. on June 13, 2009
I’d like to know more details, thx.
By Lingerie at 8:10 p.m. on June 22, 2009
How about pass the sender in the constructor of the manager (unless there is some magical way to pass it in Python) and then register with the save and delete signals only for that sender
By jordan shoes at 1:37 a.m. on June 25, 2009
For the on-die caches etc.? I think that there's a reasonable amount of abstraction that's good for dealing with caches, but I agree, when it comes to RAM vs. Disk, it's good to care where your data is.
By jordan shoes at 1:38 a.m. on June 25, 2009
This is very insightful. Thank you for sharing with us!
By ugg boots at 1:39 a.m. on June 25, 2009
I’d like to know more details, thx.
By nike shoes at 1:39 a.m. on June 25, 2009
guess there's also no economic incentive to make it tweakable. A CPU (or any hardware unit) with a fixed caching algorithm is simpler and cheaper to make, and they make you buy a new one to get the new algorithm. Whereas free software libraries have a great incentive to make it tweakable.
By tiffany jewellery at 1:40 a.m. on June 25, 2009
This is very insightful. Thank you for sharing with us!