APC cache: RED As Workaround For Thundering Herd Problem

patch-apc_red.patch

Index: apc_cache.c
===================================================================
--- apc_cache.c	(revision 320057)
+++ apc_cache.c	(working copy)
@@ -705,6 +705,13 @@
     volatile apc_cache_entry_t* value = NULL;
     unsigned long h;
 
+    /* APC-RED PATCH */
+    const int drop_cf = 75;
+    unsigned int probability = 0;
+    int red_cf = 0;
+    short drop = 0;
+    /* END OF APC-RED PATCH */
+
     if(apc_cache_busy(cache))
     {
         /* cache cleanup in progress */ 
@@ -720,8 +727,25 @@
     while (*slot) {
         if ((h == (*slot)->key.h) &&
             !memcmp((*slot)->key.data.user.identifier, strkey, keylen)) {
+            /* APC-RED PATCH */
+            if((*slot)->value->data.user.ttl) {
+                red_cf = (t - (*slot)->creation_time) * 100 /
+                    (*slot)->value->data.user.ttl;
+                if (red_cf >= 100) {
+                    drop = 1;
+                }
+                else if (red_cf <= drop_cf) {
+                    drop = 0;
+                }
+                else {
+                    probability = (red_cf - drop_cf) * 100 / (100 - drop_cf);
+                    drop = (arc4random() % 100) < probability ? 1 : 0;
+                }
+            }
+            /* END OF APC-RED PATCH */
+
             /* Check to make sure this entry isn't expired by a hard TTL */
-            if((*slot)->value->data.user.ttl && (time_t) ((*slot)->creation_time + (*slot)->value->data.user.ttl) < t) {
+            if(((*slot)->value->data.user.ttl && (time_t) ((*slot)->creation_time + (*slot)->value->data.user.ttl) < t) || drop) {
                 #if (USE_READ_LOCKS == 0) 
                 /* this is merely a memory-friendly optimization, if we do have a write-lock
                  * might as well move this to the deleted_list right-away. Otherwise an insert