[OpenAFS] Windows cache rehashed...

[Jeffrey Altman]

This is a cryptographically signed message in MIME format.

--------------ms010200090304070004000501
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit

My favorite interview question to ask is "please describe for me an 
algorithm to sort a list of names."  Job applicants usually fall into 
three categories:

    * 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.


--------------ms010200090304070004000501
Content-Type: application/x-pkcs7-signature; name="smime.p7s"
Content-Transfer-Encoding: base64
Content-Disposition: attachment; filename="smime.p7s"
Content-Description: S/MIME Cryptographic Signature

MIAGCSqGSIb3DQEHAqCAMIACAQExCzAJBgUrDgMCGgUAMIAGCSqGSIb3DQEHAQAAoIIJUDCC
AwYwggJvoAMCAQICAwpxijANBgkqhkiG9w0BAQQFADCBkjELMAkGA1UEBhMCWkExFTATBgNV
BAgTDFdlc3Rlcm4gQ2FwZTESMBAGA1UEBxMJQ2FwZSBUb3duMQ8wDQYDVQQKEwZUaGF3dGUx
HTAbBgNVBAsTFENlcnRpZmljYXRlIFNlcnZpY2VzMSgwJgYDVQQDEx9QZXJzb25hbCBGcmVl
bWFpbCBSU0EgMjAwMC44LjMwMB4XDTAzMDczMDAyMDkyOFoXDTA0MDcyOTAyMDkyOFowRjEf
MB0GA1UEAxMWVGhhd3RlIEZyZWVtYWlsIE1lbWJlcjEjMCEGCSqGSIb3DQEJARYUamFsdG1h
bkBjb2x1bWJpYS5lZHUwggEiMA0GCSqGSIb3DQEBAQUAA4IBDwAwggEKAoIBAQDBtDG6ZyGA
sK+rZOfKPKGBn6oCTLYSLk/mpeX9QTmTG71qh308KUeN35qqoRXjLvscfw6NPOYXiuxE/RqL
sx7WKEnK3C4gzzpioCTX1b7o4M7YbpvCRBFPE9Jgsd0yz2EN+mk/pPuK1GP+iQNot2m4A56A
aPe6F5T25GqffU535GNIdAtWPao6wHcOm17se25ny/TNzb9mlA4UzYl9XP7MF1fkpJyaDDAy
DNNTSSjxBdPVs2EaYq1p/xadXbIpysQiySXAxoeiZusgJopRHLcBsBmmY9QVD4QnUqZVmfJ5
f1CiNri5vlexKCmdFSrxMLuoLr4EQZCECdusp6ZnIt75AgMBAAGjMTAvMB8GA1UdEQQYMBaB
FGphbHRtYW5AY29sdW1iaWEuZWR1MAwGA1UdEwEB/wQCMAAwDQYJKoZIhvcNAQEEBQADgYEA
DPKe/CuAgEUxsrPskJQx2fL6soAEG2iqrqOGIRREHDaXWDBNMEWEbOEMLvh3+yhqHOUc9x3r
2IfsP/XHnujaqsMVXLagokVTnpPN675wv8LZ8hLHblLnykaTCq6RZpVskh2iAiJwpYMcKNF6
jyYaQyGHBGT3PK8uVGVCG4Pp9k4wggMGMIICb6ADAgECAgMKcYowDQYJKoZIhvcNAQEEBQAw
gZIxCzAJBgNVBAYTAlpBMRUwEwYDVQQIEwxXZXN0ZXJuIENhcGUxEjAQBgNVBAcTCUNhcGUg
VG93bjEPMA0GA1UEChMGVGhhd3RlMR0wGwYDVQQLExRDZXJ0aWZpY2F0ZSBTZXJ2aWNlczEo
MCYGA1UEAxMfUGVyc29uYWwgRnJlZW1haWwgUlNBIDIwMDAuOC4zMDAeFw0wMzA3MzAwMjA5
MjhaFw0wNDA3MjkwMjA5MjhaMEYxHzAdBgNVBAMTFlRoYXd0ZSBGcmVlbWFpbCBNZW1iZXIx
IzAhBgkqhkiG9w0BCQEWFGphbHRtYW5AY29sdW1iaWEuZWR1MIIBIjANBgkqhkiG9w0BAQEF
AAOCAQ8AMIIBCgKCAQEAwbQxumchgLCvq2TnyjyhgZ+qAky2Ei5P5qXl/UE5kxu9aod9PClH
jd+aqqEV4y77HH8OjTzmF4rsRP0ai7Me1ihJytwuIM86YqAk19W+6ODO2G6bwkQRTxPSYLHd
Ms9hDfppP6T7itRj/okDaLdpuAOegGj3uheU9uRqn31Od+RjSHQLVj2qOsB3Dpte7HtuZ8v0
zc2/ZpQOFM2JfVz+zBdX5KScmgwwMgzTU0ko8QXT1bNhGmKtaf8WnV2yKcrEIsklwMaHombr
ICaKURy3AbAZpmPUFQ+EJ1KmVZnyeX9Qoja4ub5XsSgpnRUq8TC7qC6+BEGQhAnbrKemZyLe
+QIDAQABozEwLzAfBgNVHREEGDAWgRRqYWx0bWFuQGNvbHVtYmlhLmVkdTAMBgNVHRMBAf8E
AjAAMA0GCSqGSIb3DQEBBAUAA4GBAAzynvwrgIBFMbKz7JCUMdny+rKABBtoqq6jhiEURBw2
l1gwTTBFhGzhDC74d/soahzlHPcd69iH7D/1x57o2qrDFVy2oKJFU56Tzeu+cL/C2fISx25S
58pGkwqukWaVbJIdogIicKWDHCjReo8mGkMhhwRk9zyvLlRlQhuD6fZOMIIDODCCAqGgAwIB
AgIQZkVyt8x09c9jdkWE0C6RATANBgkqhkiG9w0BAQQFADCB0TELMAkGA1UEBhMCWkExFTAT
BgNVBAgTDFdlc3Rlcm4gQ2FwZTESMBAGA1UEBxMJQ2FwZSBUb3duMRowGAYDVQQKExFUaGF3
dGUgQ29uc3VsdGluZzEoMCYGA1UECxMfQ2VydGlmaWNhdGlvbiBTZXJ2aWNlcyBEaXZpc2lv
bjEkMCIGA1UEAxMbVGhhd3RlIFBlcnNvbmFsIEZyZWVtYWlsIENBMSswKQYJKoZIhvcNAQkB
FhxwZXJzb25hbC1mcmVlbWFpbEB0aGF3dGUuY29tMB4XDTAwMDgzMDAwMDAwMFoXDTA0MDgy
NzIzNTk1OVowgZIxCzAJBgNVBAYTAlpBMRUwEwYDVQQIEwxXZXN0ZXJuIENhcGUxEjAQBgNV
BAcTCUNhcGUgVG93bjEPMA0GA1UEChMGVGhhd3RlMR0wGwYDVQQLExRDZXJ0aWZpY2F0ZSBT
ZXJ2aWNlczEoMCYGA1UEAxMfUGVyc29uYWwgRnJlZW1haWwgUlNBIDIwMDAuOC4zMDCBnzAN
BgkqhkiG9w0BAQEFAAOBjQAwgYkCgYEA3jMypmPHCSVFPtJueCdngcXaiBmClw7jRCmKYzUq
bXA8+tyu9+50bzC8M5B/+TRxoKNtmPHDT6Jl2w36S/HW3WGl+YXNVZo1Gp2Sdagnrthy+boC
9tewkd4c6avgGAOofENCUFGHgzzwObSbVIoTh/+zm51JZgAtCYnslGvpoWkCAwEAAaNOMEww
KQYDVR0RBCIwIKQeMBwxGjAYBgNVBAMTEVByaXZhdGVMYWJlbDEtMjk3MBIGA1UdEwEB/wQI
MAYBAf8CAQAwCwYDVR0PBAQDAgEGMA0GCSqGSIb3DQEBBAUAA4GBADGxS0dd+QFx5fVTbF15
1j2YwCYTYoEipxL4IpXoG0m3J3sEObr85vIk65H6vewNKjj3UFWobPcNrUwbvAP0teuiR59s
ogxYjTFCCRFssBpp0SsSskBdavl50OouJd2K5PzbDR+dAvNa28o89kTqJmmHf0iezqWf54TY
yWJirQXGMYID1TCCA9ECAQEwgZowgZIxCzAJBgNVBAYTAlpBMRUwEwYDVQQIEwxXZXN0ZXJu
IENhcGUxEjAQBgNVBAcTCUNhcGUgVG93bjEPMA0GA1UEChMGVGhhd3RlMR0wGwYDVQQLExRD
ZXJ0aWZpY2F0ZSBTZXJ2aWNlczEoMCYGA1UEAxMfUGVyc29uYWwgRnJlZW1haWwgUlNBIDIw
MDAuOC4zMAIDCnGKMAkGBSsOAwIaBQCgggIPMBgGCSqGSIb3DQEJAzELBgkqhkiG9w0BBwEw
HAYJKoZIhvcNAQkFMQ8XDTAzMTIxNjEzMDM1MlowIwYJKoZIhvcNAQkEMRYEFCIjQXEnB/8m
5dHXZkagp0Il/qhmMFIGCSqGSIb3DQEJDzFFMEMwCgYIKoZIhvcNAwcwDgYIKoZIhvcNAwIC
AgCAMA0GCCqGSIb3DQMCAgFAMAcGBSsOAwIHMA0GCCqGSIb3DQMCAgEoMIGrBgkrBgEEAYI3
EAQxgZ0wgZowgZIxCzAJBgNVBAYTAlpBMRUwEwYDVQQIEwxXZXN0ZXJuIENhcGUxEjAQBgNV
BAcTCUNhcGUgVG93bjEPMA0GA1UEChMGVGhhd3RlMR0wGwYDVQQLExRDZXJ0aWZpY2F0ZSBT
ZXJ2aWNlczEoMCYGA1UEAxMfUGVyc29uYWwgRnJlZW1haWwgUlNBIDIwMDAuOC4zMAIDCnGK
MIGtBgsqhkiG9w0BCRACCzGBnaCBmjCBkjELMAkGA1UEBhMCWkExFTATBgNVBAgTDFdlc3Rl
cm4gQ2FwZTESMBAGA1UEBxMJQ2FwZSBUb3duMQ8wDQYDVQQKEwZUaGF3dGUxHTAbBgNVBAsT
FENlcnRpZmljYXRlIFNlcnZpY2VzMSgwJgYDVQQDEx9QZXJzb25hbCBGcmVlbWFpbCBSU0Eg
MjAwMC44LjMwAgMKcYowDQYJKoZIhvcNAQEBBQAEggEAFWyXj+QFp0VpuoWzg3aY037qJcAj
0Kqw/Vw3SuUzL9AHOISE5kZ/p1+Itp4jNxjyiHeGHpz1VMp9jm/H7oART0Wm9myzdxTw/osl
i1sryQ27CUOJsLVbaHeIveTWaZfAoMzXxdp50XioWFeGgXlgDglxm1ph+NAf/i8Hc7SLqbHl
AyDH2nmqKb9uDO+U3tJ/Ct+YobwGDqJZW/4ITh05JKA9Gxoy60uwHNHY6dgoWiDstveGPzhz
9DiafHzTCOGzlUVwRBF6/ZPidCnQxAJRS9p1j5EioMu8v32+Sj99L0VEkxun+fX3C503cbZ7
WLpveTj+q2MgfafwIn8nJcZ3PQAAAAAAAA==
--------------ms010200090304070004000501--