Jeremy Hylton : weblog : 2003-11-26

Simulating a 2Q Object Cache

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

ZEOCacheSimulation
the old algorithm without copy-to-current-file
AltZEOCacheSimulation
current algorithm, with copy-to-current-file
Idealized2Q
object-based 2Q algorithm without file storage details

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.

ZEOCacheSimulation, cache size 100,000,000 bytes

  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

AltZEOCacheSimulation, cache size 100,000,000 bytes

  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

TwoQSimluation, cache size 100,000,000 bytes

  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