* a small number who are confused and don't know how to answer * an overwhelmingly large number for proceed to describe a solution * a very small number who ask the question: "how large is the list?"
I bring this up not to tell you that I do not hire people that fall into the first two categories but to stress the importance of the question "how large is the list?". The size of the list determines the feasibility of a given solution as well as how much time is worth spending on it.
If the list is really small, say 10 items, then an insertion sort is fine. If the list is larger but can still fit in memory, then a quicksort is preferred. However, if the list is much larger than the available memory, I will require a mergesort possibly combined with something else.
I raise this point because we must evaluate the existing cache algorithms in light of the design considerations at the time it was developed. The cache was designed to manage a small space because the available memory and drive space on the machines it was running on were small. A 20MB cache in 1995 would have been huge. A 20MB cache with a 32K block size would have resulted in 640 cache slots.
From your description below you are specifying a 256MB cache and a 1K block size. That means you are asking an algorithm designed to manage fewer than 1000 cache slots to instead manage 256,000 cache slots. Algorithms which work well for small numbers do not usually work well for large numbers.
If we think about it carefully it would make perfect sense that the performance of the cache should drop off rapidly when the cache is full and the number of cache slots is high. Up until the time the cache is full, the cache algorithms can afford to use a lazy garbage collector to dispose of cache slots which are older than the acceptable age. Once the cache is full, in order to place something into the cache the least recently used cache slot must be found so it can be replaced. Searching 640 items is going to take 1/400th the time of searching 256,000 items on each write.
If you are going to use a large total cache size, then you must use a significantly larger block size. For a 256MB cache you may even have to use a block size as large as 128K (4000 cache slots) or even 256K (2000 cache slots).
The moral of the story is simply that the algorithms designed for the current cache implementation were appropriate for the scale of the problem at the time of their implementation. They are no longer appropriate given the scale of the problem today.
Jeffrey Altman
P.S. - The request number for this topic is 2628. I would appreciate it if any new information you find would be submitted to the request. That way when someone does find the time or resources to work on the cache manager all of the background information will be in one place.
Rodney M Dyer wrote:
Here is what we've found...
* We tested on new Dell OptiPlex GX 270 P4 3.0 GHz machines with 1 Gig RAM and 100 MBit connections to our file servers.
* We set the AFS cache to 256 Meg and 48 Meg.
* With a fresh restart of AFS and an empty cache, fs getcacheparms returns...
AFS using 100 of the cache's available 256000 1K byte blocks.
* We started ProE. The load time on average was 30 seconds. This is on-par with our Sun Solaris 9 Blade 150's load-time. The cache setting had little to no effect (as expected on first load).
* The resultant fs getcacheparms after ProE is loaded is (for 256 Meg cache)...
AFS using 57685 of the cache's available 256000 1K byte blocks.
* Starting ProE again resulted in a load time of 10-15 seconds...excellent, cache works.
* Even with a 48 Meg cache, the load time was a decent average of 25 to 30 seconds.
smime.p7s
Description: S/MIME Cryptographic Signature
