Cache miss stampedes [patch]

[BUSTARRET, Jean-francois]

> > -----Message d'origine-----
> > De : dormando [mailto:dormando at rydia.net]
> > > You would not need tuning, and the rate of incoming
> > requests is not a
> > > problem IMHO.
> > > 
> > > - If the rate is very low, one can expect that there won't be any 
> > > stampede (unless the regeneration code is veeeeeeery slow,
> > but this a
> > > code tuning problem, and not a caching one)
> > > - If the rate is moderate, it works fine
> > > - If the rate is very high, I still prefer to 1% of requests 
> > > regenerating the key instead of 100% one minute later...
> > 
> > Or do you mean it simply returns a cache miss randomly? I 
> guess that'd 
> > work.
> 
> Yep ! 1% of cache requests will return a cache miss, 99% will 
> return a cache hit with the data.

Here is a patch against 1.2.2 (no comments, no doc yet), in case someone
wants to give it a try.

Usage : add -e duration to the commandline

The chance of returning a cache miss grow with time, starting at
it->exptime - duration (0%) and ending at it->exptime (100%).

diff -rup memcached-1.2.2/items.c memcached-1.2.2-randomexp/items.c
--- memcached-1.2.2/items.c     2007-05-03 00:58:51.000000000 +0200
+++ memcached-1.2.2-randomexp/items.c  2007-07-26 14:09:57.000000000
+0200
@@ -387,6 +387,13 @@ item *do_item_get_notedeleted(const char
         do_item_unlink(it);           // MTSAFE - cache_lock held
         it = 0;
     }
+    if (it != NULL && settings.random_exp_time > 0 && it->exptime != 0
&& it->exptime <= current_time + settings.random_exp_time) {
+        int threshold = (current_time - it->exptime +
settings.random_exp_time);
+        threshold = RAND_MAX / settings.random_exp_time /
settings.random_exp_time * threshold * threshold;
+        if (rand() <= threshold) {
+                it = 0;
+        }
+    }

     if (it != NULL) {
         it->refcount++;
diff -rup memcached-1.2.2/memcached.c
memcached-1.2.2-randomexp/memcached.c
--- memcached-1.2.2/memcached.c 2007-05-03 00:58:51.000000000 +0200
+++ memcached-1.2.2-randomexp/memcached.c    2007-07-26
14:08:29.000000000 +0200
@@ -185,6 +185,7 @@ static void settings_init(void) {
 #endif
     settings.prefix_delimiter = ':';
     settings.detail_enabled = 0;
+    settings.random_exp_time = 0;
 }

 /* returns true if a deleted item's delete-locked-time is over, and it
@@ -2475,7 +2476,7 @@ int main (int argc, char **argv) {
     setbuf(stderr, NULL);

     /* process arguments */
-    while ((c = getopt(argc, argv,
"bp:s:U:m:Mc:khirvdl:u:P:f:s:n:t:D:")) != -1) {
+    while ((c = getopt(argc, argv,
"bp:s:U:m:Mc:khirvdl:u:P:f:s:n:t:D:e:")) != -1) {
         switch (c) {
         case 'U':
             settings.udpport = atoi(optarg);
@@ -2559,6 +2560,10 @@ int main (int argc, char **argv) {
             settings.prefix_delimiter = optarg[0];
             settings.detail_enabled = 1;
             break;
+        case 'e':
+            settings.random_exp_time = atoi(optarg);
+            srand(time(0));
+            break;
         default:
             fprintf(stderr, "Illegal argument \"%c\"\n", c);
             return 1;
diff -rup memcached-1.2.2/memcached.h
memcached-1.2.2-randomexp/memcached.h
--- memcached-1.2.2/memcached.h 2007-05-03 00:58:51.000000000 +0200
+++ memcached-1.2.2-randomexp/memcached.h    2007-07-26
13:30:54.000000000 +0200
@@ -79,6 +79,7 @@ struct settings {
     int num_threads;        /* number of libevent threads to run */
     char prefix_delimiter;  /* character that marks a key prefix (for
stats) */
     int detail_enabled;     /* nonzero if we're collecting detailed
stats */
+    int random_exp_time;
 };

 extern struct stats stats;