From: antirez <antirez@gmail.com>
Date: Tue, 10 Nov 2009 16:48:01 +0000 (+0100)
Subject: Implemented a much better lazy expiring algorithm for EXPIRE
X-Git-Url: https://git.saurik.com/redis.git/commitdiff_plain/f23242938637c5c72f5a8104976a3f7764d66203

Implemented a much better lazy expiring algorithm for EXPIRE
---

diff --git a/redis.c b/redis.c
index 48ad6287..2d196674 100644
--- a/redis.c
+++ b/redis.c
@@ -940,14 +940,21 @@ static int serverCron(struct aeEventLoop *eventLoop, long long id, void *clientD
          }
     }
 
-    /* Try to expire a few timed out keys */
+    /* Try to expire a few timed out keys. The algorithm used is adaptive and
+     * will use few CPU cycles if there are few expiring keys, otherwise
+     * it will get more aggressive to avoid that too much memory is used by
+     * keys that can be removed from the keyspace. */
     for (j = 0; j < server.dbnum; j++) {
+        int expired;
         redisDb *db = server.db+j;
-        int num = dictSize(db->expires);
 
-        if (num) {
+        /* Continue to expire if at the end of the cycle more than 25%
+         * of the keys were expired. */
+        do {
+            int num = dictSize(db->expires);
             time_t now = time(NULL);
 
+            expired = 0;
             if (num > REDIS_EXPIRELOOKUPS_PER_CRON)
                 num = REDIS_EXPIRELOOKUPS_PER_CRON;
             while (num--) {
@@ -958,9 +965,10 @@ static int serverCron(struct aeEventLoop *eventLoop, long long id, void *clientD
                 t = (time_t) dictGetEntryVal(de);
                 if (now > t) {
                     deleteKey(db,dictGetEntryKey(de));
+                    expired++;
                 }
             }
-        }
+        } while (expired > REDIS_EXPIRELOOKUPS_PER_CRON/4);
     }
 
     /* Check if we should connect to a MASTER */