Date: Sun, 26 Jan 2003 22:57:02 -0800 (PST) From: Matthew Dillon <dillon@apollo.backplane.com> To: Terry Lambert <tlambert2@mindspring.com> Cc: kientzle@acm.org, Sean Hamilton <sh@bel.bc.ca>, hackers@FreeBSD.ORG Subject: Re: Random disk cache expiry Message-ID: <200301270657.h0R6v2qH071774@apollo.backplane.com> References: <000501c2c4dd$f43ed450$16e306cf@slugabed.org> <200301261931.h0QJVCp8052101@apollo.backplane.com> <3E348B51.6F4D6096@mindspring.com> <200301270142.h0R1guR3070182@apollo.backplane.com> <3E3494CC.5895492D@mindspring.com> <3E34A6BB.2090601@acm.org> <3E34CA7F.D0E0A260@mindspring.com>
next in thread | previous in thread | raw e-mail | index | archive | help
Mmmmm. Basically what it comes down to is that without foreknowledge
of the data locations being accessed, it is not possible for any
cache algorithm to adapt to all the myrid ways data might be accessed.
If you focus the cache on one methodology it will probably perform
terribly when presented with some other methodology.
What this means is that for the cases where you *KNOW* how a program
intends to access a dataset larger then main memory, it is better
to have the program explicitly cache/not-cache the data under program
control rather then trying to force the system cache to adapt.
I'll also be nice and decode some of Terry's Jargon for the rest of
the readers.
:will result in significant failure of random page replacement to
:result in cache hits; likewise, going to 85% overage will practically
:guarantee an almost 100% failure rate, as cyclical access with random
:replacement is statistically more likely, in aggregate, to replace
:the pages which are there longer (the probability is iterative and
:additive: it's effectively a permutation).
What Terry is saying is that if you have a dataset that is 2x
the size of your cache, the cache hit rate on that data with random
page replacement is NOT going to be 50%. This is because with random
page replacement the likelihood of a piece of data being found in
the cache depends on how long the data has been sitting in the cache.
The longer the data has been sitting in the cache, the less likely you
will find it when you need it (because it is more likely to have been
replaced by the random replacement algorithm over time).
So, again, the best caching methodology to use in the case where
you *know* how much data you will be accessing and how you will access
it is to build the caching directly into your program and not depend
on system caching at all (for datasets which are far larger then
main memory).
This is true of all systems, not just BSD. This is one reason why
databases do their own caching (another is so databases know when an
access will require I/O for scheduling reasons, but that's a different
story).
The FreeBSD VM caching system does prevent one process from exhausting
another process's cached data due to a sequential access, but the
FreeBSD VM cache does not try to outsmart sequential data accesses to
datasets which are larger then available cache space because it's an
insanely difficult (impossible) problem to solve properly without
foreknowledge of what data elements will be accessed when.
This isn't to say that we can't improve on what we have now.
I certainly think we can. But there is no magic bullet that will
deal with every situation.
-Matt
To Unsubscribe: send mail to majordomo@FreeBSD.org
with "unsubscribe freebsd-hackers" in the body of the message
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?200301270657.h0R6v2qH071774>