| Jeremy Hylton : weblog : 2003-11-26 |
Wednesday, November 26, 2003, 5:09 p.m.
I used three simulators to look at a 36-hour trace from zope.org this afternoon. I compared a modified 2Q algorithm against the existing algorithms. It did better; the hit rate for a 100MB cache was almost equal to the hit rate for a cache of unbounded size. Not sure if 2Q can be implemented effectively, though.
I'm using the simul.py from the Zope 2.6 branch, because zope.org is running 2.6; the cache format is different for 2.7 and up. Jens gave me a cache trace containing 36 hours of zope.org data.
Three simluations are
I checked in the 2Q implementation. The original 2Q algorithm was simple because it dealt with fixed size blocks. I had to make a bunch of small changes to deal with variable sized blocks. There are also odd corners: When you store data that is currently in the cache, I allow the cache to exceed its size limits until the next cache miss.
None of the simulation deals with writing to real files. It's easy to handle the A1in cache -- things read recently but not promoted to the top-level cache -- because it's just FIFO. I assume A1out -- list of oids that fell off the end of A1in -- can be written out when the cache shuts down.
It's the top-level LRU cache that's tricky. I don't know if there's a good way to implement an LRU cache on top of a file. We'll probably need to simulate one of Tim's rotating-file-pointer schemes and see how much it hurts.
I simulated with a 100MB cache. Everything fits without eviction or flip in a 500MB cache, which might make the details of the replacement algorithm moot.
Each line in the simulation below represents a snapshot of data between client restarts. I don't know why the client restarts so often. There are a few bursts of heavy write activity in the traces -- 10:21 and 20:46 on Nov 25. The 2Q cache has a much higher hit rate for these segments -- 58% and 54% vs. 37% and 29%. I expect it's doing a better job of keeping hot objects in the cache, which it can do because it's got an idealized LRU component.
START TIME DURATION LOADS HITS INVALS WRITES FLIPS HITRATE Nov 25 00:36 2:19:55 51340 18759 68 116 2 36.5% Nov 25 02:56 1:55:01 54952 18481 33 442 3 33.6% Nov 25 04:51 1:30:01 72530 28127 55 97 3 38.8% Nov 25 06:21 1:00:13 46689 16871 19 111 2 36.1% Nov 25 07:21 1:45:09 53628 20045 64 143 3 37.4% Nov 25 09:06 1:15:02 58238 20881 28 163 3 35.9% Nov 25 10:21 2:05:01 126466 48034 604 4751 7 38.0% Nov 25 12:26 1:15:03 51919 18122 29 68 2 34.9% Nov 25 13:41 2:45:03 69965 22808 130 296 4 32.6% Nov 25 16:26 4:19:34 37131 12712 3 38 2 34.2% Nov 25 20:46 6:05:06 110716 34904 174 2605 7 31.5% Nov 26 02:51 2:04:57 79765 27891 507 1157 5 35.0% Nov 26 04:56 40:01 53910 19181 93 187 3 35.6% Nov 26 05:36 1:15:11 51677 17314 12 456 3 33.5% Nov 26 06:51 1:00:08 51355 18301 27 92 2 35.6% Nov 26 07:51 1:04:56 51923 18271 5 68 2 35.2% Nov 26 08:56 1:05:13 66551 24047 12 90 3 36.1% Nov 26 10:01 50:04 48137 17930 16 80 2 37.2% Nov 26 10:51 28:00 40506 16626 13 70 1 41.0% Nov 25 00:36 34:43:38 1177398 419305 1892 11030 59 35.6% OVERALL
START TIME DURATION LOADS HITS INVALS WRITES FLIPS HITRATE Nov 25 00:36 2:19:55 51340 16862 52 116 3 32.8% Nov 25 02:56 1:55:01 54952 16433 34 442 3 29.9% Nov 25 04:51 1:30:01 72530 26759 51 97 5 36.9% Nov 25 06:21 1:00:13 46689 16458 17 111 3 35.3% Nov 25 07:21 1:45:09 53628 18971 53 143 3 35.4% Nov 25 09:06 1:15:02 58238 20556 28 163 3 35.3% Nov 25 10:21 2:05:01 126466 46146 552 4751 9 36.5% Nov 25 12:26 1:15:03 51919 17269 26 68 3 33.3% Nov 25 13:41 2:45:03 69965 21461 138 296 5 30.7% Nov 25 16:26 4:19:34 37131 12409 3 38 2 33.4% Nov 25 20:46 6:05:06 110716 31716 171 2605 9 28.6% Nov 26 02:51 2:04:57 79765 27015 478 1157 6 33.9% Nov 26 04:56 40:01 53910 18012 86 187 3 33.4% Nov 26 05:36 1:15:11 51677 16902 12 456 3 32.7% Nov 26 06:51 1:00:08 51355 16659 27 92 3 32.4% Nov 26 07:51 1:04:56 51923 17963 5 68 3 34.6% Nov 26 08:56 1:05:13 66551 24446 14 90 4 36.7% Nov 26 10:01 50:04 48137 17694 18 80 3 36.8% Nov 26 10:51 28:00 40506 16581 13 70 2 40.9% Nov 25 00:36 34:43:38 1177398 400312 1778 11030 75 34.0% OVERALL
START TIME DURATION LOADS HITS INVALS WRITES EVICTS HITRATE Nov 25 00:36 2:19:55 51340 17629 142 116 23103 34.3% Nov 25 02:56 1:55:01 54952 20390 53 442 21426 37.1% Nov 25 04:51 1:30:01 72530 34056 71 97 11500 47.0% Nov 25 06:21 1:00:13 46689 18223 23 111 22910 39.0% Nov 25 07:21 1:45:09 53628 21960 91 143 10709 40.9% Nov 25 09:06 1:15:02 58238 23473 39 163 22095 40.3% Nov 25 10:21 2:05:01 126466 73543 822 4751 32547 58.2% Nov 25 12:26 1:15:03 51919 19069 51 68 14365 36.7% Nov 25 13:41 2:45:03 69965 31514 298 296 32707 45.0% Nov 25 16:26 4:19:34 37131 12783 3 38 23743 34.4% Nov 25 20:46 6:05:06 110716 59497 286 2605 32389 53.7% Nov 26 02:51 2:04:57 79765 37405 671 1157 30926 46.9% Nov 26 04:56 40:01 53910 21659 120 187 24326 40.2% Nov 26 05:36 1:15:11 51677 20213 20 456 12664 39.1% Nov 26 06:51 1:00:08 51355 19113 29 92 18965 37.2% Nov 26 07:51 1:04:56 51923 19772 17 68 9988 38.1% Nov 26 08:56 1:05:13 66551 28465 15 90 18300 42.8% Nov 26 10:01 50:04 48137 19193 20 80 15014 39.9% Nov 26 10:51 28:00 40506 16625 12 70 0 41.0% Nov 25 00:36 34:43:38 1177398 514582 2783 11030 377677 43.7% OVERALL