Variadic ZREM

[redis.git] / src / dscache.c

diff --git a/src/dscache.c b/src/dscache.c
index b37a8cd3bb0e67e1eedc911f2a8c346ffe8faed0..46300e63700e8c7c7bc2958e5a0656db701d5b80 100644 (file)
--- a/src/dscache.c
+++ b/src/dscache.c
@@ -19,74 +19,70 @@
 
 /* TODO:
  *
 
 /* TODO:
  *

- * - The WATCH helper will be used to signal the cache system
- *   we need to flush a given key/dbid into disk, adding this key/dbid
- *   pair into a server.ds_cache_dirty linked list AND hash table (so that we
- *   don't add the same thing multiple times).
- *
- * - cron() checks if there are elements on this list. When there are things
- *   to flush, we create an IO Job for the I/O thread.
- *   NOTE: We disalbe object sharing when server.ds_enabled == 1 so objects
- *   that are referenced an IO job for flushing on disk are marked as
- *   o->storage == REDIS_DS_SAVING.
- *
- * - This is what we do on key lookup:
- *   1) The key already exists in memory. object->storage == REDIS_DS_MEMORY
- *      or it is object->storage == REDIS_DS_DIRTY:
- *      We don't do nothing special, lookup, return value object pointer.
- *   2) The key is in memory but object->storage == REDIS_DS_SAVING.
- *      When this happens we block waiting for the I/O thread to process
- *      this object. Then continue.
- *   3) The key is not in memory. We block to load the key from disk.
- *      Of course the key may not be present at all on the disk store as well,
- *      in such case we just detect this condition and continue, returning
- *      NULL from lookup.
- *
- * - Preloading of needed keys:
- *   1) As it was done with VM, also with this new system we try preloading
- *      keys a client is going to use. We block the client, load keys
- *      using the I/O thread, unblock the client. Same code as VM more or less.
- *
- * - Reclaiming memory.
- *   In cron() we detect our memory limit was reached. What we
- *   do is deleting keys that are REDIS_DS_MEMORY, using LRU.
- *
- *   If this is not enough to return again under the memory limits we also
- *   start to flush keys that need to be synched on disk synchronously,
- *   removing it from the memory. We do this blocking as memory limit is a
- *   much "harder" barrirer in the new design.
- *
- * - IO thread operations are no longer stopped for sync loading/saving of
- *   things. When a key is found to be in the process of being saved
- *   we simply wait for the IO thread to end its work.
- *
- *   Otherwise if there is to load a key without any IO thread operation
- *   just started it is blocking-loaded in the lookup function.
+ * WARNING: most of the following todo items and design issues are no
+ * longer relevant with the new design. Here as a checklist to see if
+ * some old ideas still apply.

  *
  * - What happens when an object is destroyed?
  *
  *
  * - What happens when an object is destroyed?
  *

- *   If o->storage == REDIS_DS_MEMORY then we simply destory the object.
- *   If o->storage == REDIS_DS_DIRTY we can still remove the object. It had
- *                    changes not flushed on disk, but is being removed so
- *                    who cares.
- *   if o->storage == REDIS_DS_SAVING then the object is being saved so
- *                    it is impossible that its refcount == 1, must be at
- *                    least two. When the object is saved the storage will
- *                    be set back to DS_MEMORY.
+ *   If the object is destroyed since semantically it was deleted or
+ *   replaced with something new, we don't care if there was a SAVE
+ *   job pending for it. Anyway when the IO JOb will be created we'll get
+ *   the pointer of the current value.

  *
  *

- * - What happens when keys are deleted?
- *
- *   We simply schedule a key flush operation as usually, but when the
- *   IO thread will be created the object pointer will be set to NULL
- *   so the IO thread will know that the work to do is to delete the key
- *   from the disk store.
+ *   If the object is already a REDIS_IO_SAVEINPROG object, then it is
+ *   impossible that we get a decrRefCount() that will reach refcount of zero
+ *   since the object is both in the dataset and in the io job entry.

  *
  * - What happens with MULTI/EXEC?
  *
  *
  * - What happens with MULTI/EXEC?
  *

- *   Good question.
+ *   Good question. Without some kind of versioning with a global counter
+ *   it is not possible to have trasactions on disk, but they are still
+ *   useful since from the point of view of memory and client bugs it is
+ *   a protection anyway. Also it's useful for WATCH.
+ *
+ *   Btw there is to check what happens when WATCH gets combined to keys
+ *   that gets removed from the object cache. Should be save but better
+ *   to check.
+ *
+ * - Check if/why INCR will not update the LRU info for the object.
+ *
+ * - Fix/Check the following race condition: a key gets a DEL so there is
+ *   a write operation scheduled against this key. Later the same key will
+ *   be the argument of a GET, but the write operation was still not
+ *   completed (to delete the file). If the GET will be for some reason
+ *   a blocking loading (via lookup) we can load the old value on memory.
+ *
+ *   This problems can be fixed with negative caching. We can use it
+ *   to optimize the system, but also when a key is deleted we mark
+ *   it as non existing on disk as well (in a way that this cache
+ *   entry can't be evicted, setting time to 0), then we avoid looking at
+ *   the disk at all if the key can't be there. When an IO Job complete
+ *   a deletion, we set the time of the negative caching to a non zero
+ *   value so it will be evicted later.
+ *
+ *   Are there other patterns like this where we load stale data?
+ *
+ *   Also, make sure that key preloading is ONLY done for keys that are
+ *   not marked as cacheKeyDoesNotExist(), otherwise, again, we can load
+ *   data from disk that should instead be deleted.
+ *
+ * - dsSet() should use rename(2) in order to avoid corruptions.
+ *
+ * - Don't add a LOAD if there is already a LOADINPROGRESS, or is this
+ *   impossible since anyway the io_keys stuff will work as lock?
+ *
+ * - Serialize special encoded things in a raw form.

  *
  *

- * - If dsSet() fails on the write thread log the error and reschedule the
- *   key for flush.
+ * - When putting IO read operations on top of the queue, do this only if
+ *   the already-on-top operation is not a save or if it is a save that
+ *   is scheduled for later execution. If there is a save that is ready to
+ *   fire, let's insert the load operation just before the first save that
+ *   is scheduled for later exection for instance.
+ *
+ * - Support MULTI/EXEC transactions via a journal file, that is played on
+ *   startup to check if there is cleanup to do. This way we can implement
+ *   transactions with our simple file based KV store.

  */
 
 /* Virtual Memory is composed mainly of two subsystems:
  */
 
 /* Virtual Memory is composed mainly of two subsystems:


@@ -111,6 +107,8 @@
  */
 
 void spawnIOThread(void);
  */
 
 void spawnIOThread(void);

+int cacheScheduleIOPushJobs(int flags);
+int processActiveIOJobs(int max);

 
 /* =================== Virtual Memory - Blocking Side  ====================== */
 
 
 /* =================== Virtual Memory - Blocking Side  ====================== */
 


@@ -133,6 +131,8 @@ void dsInit(void) {
     server.io_processed = listCreate();
     server.io_ready_clients = listCreate();
     pthread_mutex_init(&server.io_mutex,NULL);
     server.io_processed = listCreate();
     server.io_ready_clients = listCreate();
     pthread_mutex_init(&server.io_mutex,NULL);

+    pthread_cond_init(&server.io_condvar,NULL);
+    pthread_mutex_init(&server.bgsavethread_mutex,NULL);

     server.io_active_threads = 0;
     if (pipe(pipefds) == -1) {
         redisLog(REDIS_WARNING,"Unable to intialized DS: pipe(2): %s. Exiting."
     server.io_active_threads = 0;
     if (pipe(pipefds) == -1) {
         redisLog(REDIS_WARNING,"Unable to intialized DS: pipe(2): %s. Exiting."


@@ -185,21 +185,21 @@ int cacheFreeOneEntry(void) {
          * are swappable objects */
         int maxtries = 100;
 
          * are swappable objects */
         int maxtries = 100;
 

-        if (dictSize(db->dict) == 0) continue;
-        for (i = 0; i < 5; i++) {
+        for (i = 0; i < 5 && dictSize(db->dict); i++) {

             dictEntry *de;
             double swappability;
             dictEntry *de;
             double swappability;

+            robj keyobj;
+            sds keystr;

 
             if (maxtries) maxtries--;
             de = dictGetRandomKey(db->dict);
 
             if (maxtries) maxtries--;
             de = dictGetRandomKey(db->dict);

+            keystr = dictGetEntryKey(de);

             val = dictGetEntryVal(de);
             val = dictGetEntryVal(de);

-            /* Only swap objects that are currently in memory.
-             *
-             * Also don't swap shared objects: not a good idea in general and
-             * we need to ensure that the main thread does not touch the
-             * object while the I/O thread is using it, but we can't
-             * control other keys without adding additional mutex. */
-            if (val->storage != REDIS_DS_MEMORY) {
+            initStaticStringObject(keyobj,keystr);
+
+            /* Don't remove objects that are currently target of a
+             * read or write operation. */
+            if (cacheScheduleIOGetFlags(db,&keyobj) != 0) {

                 if (maxtries) i--; /* don't count this try */
                 continue;
             }
                 if (maxtries) i--; /* don't count this try */
                 continue;
             }


@@ -212,10 +212,17 @@ int cacheFreeOneEntry(void) {
         }
     }
     if (best == NULL) {
         }
     }
     if (best == NULL) {

-        /* FIXME: If there are objects marked as DS_DIRTY or DS_SAVING
-         * let's wait for this objects to be clear and retry...
-         *
-         * Object cache vm limit is considered an hard limit. */
+        /* Not able to free a single object? we should check if our
+         * IO queues have stuff in queue, and try to consume the queue
+         * otherwise we'll use an infinite amount of memory if changes to
+         * the dataset are faster than I/O */
+        if (listLength(server.cache_io_queue) > 0) {
+            redisLog(REDIS_DEBUG,"--- Busy waiting IO to reclaim memory");
+            cacheScheduleIOPushJobs(REDIS_IO_ASAP);
+            processActiveIOJobs(1);
+            return REDIS_OK;
+        }
+        /* Nothing to free at all... */

         return REDIS_ERR;
     }
     key = dictGetEntryKey(best);
         return REDIS_ERR;
     }
     key = dictGetEntryKey(best);


@@ -233,14 +240,72 @@ int cacheFreeOneEntry(void) {
     return REDIS_OK;
 }
 
     return REDIS_OK;
 }
 

-/* Return true if it's safe to swap out objects in a given moment.
- * Basically we don't want to swap objects out while there is a BGSAVE
- * or a BGAEOREWRITE running in backgroud. */
-int dsCanTouchDiskStore(void) {
-    return (server.bgsavechildpid == -1 && server.bgrewritechildpid == -1);
+/* ==================== Disk store negative caching  ========================
+ *
+ * When disk store is enabled, we need negative caching, that is, to remember
+ * keys that are for sure *not* on the disk key-value store.
+ *
+ * This is usefuls because without negative caching cache misses will cost us
+ * a disk lookup, even if the same non existing key is accessed again and again.
+ *
+ * With negative caching we remember that the key is not on disk, so if it's
+ * not in memory and we have a negative cache entry, we don't try a disk
+ * access at all.
+ */
+
+/* Returns true if the specified key may exists on disk, that is, we don't
+ * have an entry in our negative cache for this key */
+int cacheKeyMayExist(redisDb *db, robj *key) {
+    return dictFind(db->io_negcache,key) == NULL;
+}
+
+/* Set the specified key as an entry that may possibily exist on disk, that is,
+ * remove the negative cache entry for this key if any. */
+void cacheSetKeyMayExist(redisDb *db, robj *key) {
+    dictDelete(db->io_negcache,key);
+}
+
+/* Set the specified key as non existing on disk, that is, create a negative
+ * cache entry for this key. */
+void cacheSetKeyDoesNotExist(redisDb *db, robj *key) {
+    if (dictReplace(db->io_negcache,key,(void*)time(NULL))) {
+        incrRefCount(key);
+    }
+}
+
+/* Remove one entry from negative cache using approximated LRU. */
+int negativeCacheEvictOneEntry(void) {
+    struct dictEntry *de;
+    robj *best = NULL;
+    redisDb *best_db = NULL;
+    time_t time, best_time = 0;
+    int j;
+
+    for (j = 0; j < server.dbnum; j++) {
+        redisDb *db = server.db+j;
+        int i;
+
+        if (dictSize(db->io_negcache) == 0) continue;
+        for (i = 0; i < 3; i++) {
+            de = dictGetRandomKey(db->io_negcache);
+            time = (time_t) dictGetEntryVal(de);
+
+            if (best == NULL || time < best_time) {
+                best = dictGetEntryKey(de);
+                best_db = db;
+                best_time = time;
+            }
+        }
+    }
+    if (best) {
+        dictDelete(best_db->io_negcache,best);
+        return REDIS_OK;
+    } else {
+        return REDIS_ERR;
+    }

 }
 
 }
 

-/* =================== Virtual Memory - Threaded I/O  ======================= */
+/* ================== Disk store cache - Threaded I/O  ====================== */

 
 void freeIOJob(iojob *j) {
     decrRefCount(j->key);
 
 void freeIOJob(iojob *j) {
     decrRefCount(j->key);


@@ -251,7 +316,14 @@ void freeIOJob(iojob *j) {
 
 /* Every time a thread finished a Job, it writes a byte into the write side
  * of an unix pipe in order to "awake" the main thread, and this function
 
 /* Every time a thread finished a Job, it writes a byte into the write side
  * of an unix pipe in order to "awake" the main thread, and this function

- * is called. */
+ * is called.
+ *
+ * If privdata == NULL the function will try to put more jobs in the queue
+ * of IO jobs to process as more room is made. privdata is equal to NULL
+ * when the function is called from the event loop, so we want to push
+ * more IO jobs in the queue. Instead when the function is called by
+ * other functions that want to create a write-barrier to avoid race 
+ * conditions we don't push new jobs in the queue. */

 void vmThreadedIOCompletedJob(aeEventLoop *el, int fd, void *privdata,
             int mask)
 {
 void vmThreadedIOCompletedJob(aeEventLoop *el, int fd, void *privdata,
             int mask)
 {


@@ -259,7 +331,6 @@ void vmThreadedIOCompletedJob(aeEventLoop *el, int fd, void *privdata,
     int retval, processed = 0, toprocess = -1;
     REDIS_NOTUSED(el);
     REDIS_NOTUSED(mask);
     int retval, processed = 0, toprocess = -1;
     REDIS_NOTUSED(el);
     REDIS_NOTUSED(mask);

-    REDIS_NOTUSED(privdata);

 
     /* For every byte we read in the read side of the pipe, there is one
      * I/O job completed to process. */
 
     /* For every byte we read in the read side of the pipe, there is one
      * I/O job completed to process. */


@@ -289,23 +360,35 @@ void vmThreadedIOCompletedJob(aeEventLoop *el, int fd, void *privdata,
         if (j->type == REDIS_IOJOB_LOAD) {
             /* Create the key-value pair in the in-memory database */
             if (j->val != NULL) {
         if (j->type == REDIS_IOJOB_LOAD) {
             /* Create the key-value pair in the in-memory database */
             if (j->val != NULL) {

-                dbAdd(j->db,j->key,j->val);
-                incrRefCount(j->val);
-                if (j->expire != -1) setExpire(j->db,j->key,j->expire);
+                /* Note: it's possible that the key is already in memory
+                 * due to a blocking load operation. */
+                if (dbAdd(j->db,j->key,j->val) == REDIS_OK) {
+                    incrRefCount(j->val);
+                    if (j->expire != -1) setExpire(j->db,j->key,j->expire);
+                }

             } else {
             } else {

-                /* The key does not exist. Create a negative cache entry
-                 * for this key. */
-                /* FIXME: add this entry into the negative cache */
+                /* Key not found on disk. If it is also not in memory
+                 * as a cached object, nor there is a job writing it
+                 * in background, we are sure the key does not exist
+                 * currently.
+                 *
+                 * So we set a negative cache entry avoiding that the
+                 * resumed client will block load what does not exist... */
+                if (dictFind(j->db->dict,j->key->ptr) == NULL &&
+                    (cacheScheduleIOGetFlags(j->db,j->key) &
+                      (REDIS_IO_SAVE|REDIS_IO_SAVEINPROG)) == 0)
+                {
+                    cacheSetKeyDoesNotExist(j->db,j->key);
+                }

             }
             }

-            /* Handle clients waiting for this key to be loaded. */
+            cacheScheduleIODelFlag(j->db,j->key,REDIS_IO_LOADINPROG);

             handleClientsBlockedOnSwappedKey(j->db,j->key);
             handleClientsBlockedOnSwappedKey(j->db,j->key);

-            freeIOJob(j);

         } else if (j->type == REDIS_IOJOB_SAVE) {
         } else if (j->type == REDIS_IOJOB_SAVE) {

-            redisAssert(j->val->storage == REDIS_DS_SAVING);
-            j->val->storage = REDIS_DS_MEMORY;
-            freeIOJob(j);
+            cacheScheduleIODelFlag(j->db,j->key,REDIS_IO_SAVEINPROG);

         }
         }

+        freeIOJob(j);

         processed++;
         processed++;

+        if (privdata == NULL) cacheScheduleIOPushJobs(0);

         if (processed == toprocess) return;
     }
     if (retval < 0 && errno != EAGAIN) {
         if (processed == toprocess) return;
     }
     if (retval < 0 && errno != EAGAIN) {


@@ -327,17 +410,22 @@ void *IOThreadEntryPoint(void *arg) {
     iojob *j;
     listNode *ln;
     REDIS_NOTUSED(arg);
     iojob *j;
     listNode *ln;
     REDIS_NOTUSED(arg);

+    long long start;

 
     pthread_detach(pthread_self());
 
     pthread_detach(pthread_self());

+    lockThreadedIO();

     while(1) {
         /* Get a new job to process */
     while(1) {
         /* Get a new job to process */

-        lockThreadedIO();

         if (listLength(server.io_newjobs) == 0) {
         if (listLength(server.io_newjobs) == 0) {

-            /* No new jobs in queue, exit. */
-            unlockThreadedIO();
-            sleep(1);
+            /* Wait for more work to do */
+            redisLog(REDIS_DEBUG,"[T] wait for signal");
+            pthread_cond_wait(&server.io_condvar,&server.io_mutex);
+            redisLog(REDIS_DEBUG,"[T] signal received");

             continue;
         }
             continue;
         }

+        start = ustime();
+        redisLog(REDIS_DEBUG,"[T] %ld IO jobs to process",
+            listLength(server.io_newjobs));

         ln = listFirst(server.io_newjobs);
         j = ln->value;
         listDelNode(server.io_newjobs,ln);
         ln = listFirst(server.io_newjobs);
         j = ln->value;
         listDelNode(server.io_newjobs,ln);


@@ -345,7 +433,8 @@ void *IOThreadEntryPoint(void *arg) {
         listAddNodeTail(server.io_processing,j);
         ln = listLast(server.io_processing); /* We use ln later to remove it */
         unlockThreadedIO();
         listAddNodeTail(server.io_processing,j);
         ln = listLast(server.io_processing); /* We use ln later to remove it */
         unlockThreadedIO();

-        redisLog(REDIS_DEBUG,"Thread %ld: new job type %s: %p about key '%s'",
+
+        redisLog(REDIS_DEBUG,"[T] %ld: new job type %s: %p about key '%s'",

             (long) pthread_self(),
             (j->type == REDIS_IOJOB_LOAD) ? "load" : "save",
             (void*)j, (char*)j->key->ptr);
             (long) pthread_self(),
             (j->type == REDIS_IOJOB_LOAD) ? "load" : "save",
             (void*)j, (char*)j->key->ptr);


@@ -357,25 +446,30 @@ void *IOThreadEntryPoint(void *arg) {
             j->val = dsGet(j->db,j->key,&expire);
             if (j->val) j->expire = expire;
         } else if (j->type == REDIS_IOJOB_SAVE) {
             j->val = dsGet(j->db,j->key,&expire);
             if (j->val) j->expire = expire;
         } else if (j->type == REDIS_IOJOB_SAVE) {

-            redisAssert(j->val->storage == REDIS_DS_SAVING);
-            if (j->val)
-                dsSet(j->db,j->key,j->val);
-            else
+            if (j->val) {
+                dsSet(j->db,j->key,j->val,j->expire);
+            } else {

                 dsDel(j->db,j->key);
                 dsDel(j->db,j->key);

+            }

         }
 
         /* Done: insert the job into the processed queue */
         }
 
         /* Done: insert the job into the processed queue */

-        redisLog(REDIS_DEBUG,"Thread %ld completed the job: %p (key %s)",
+        redisLog(REDIS_DEBUG,"[T] %ld completed the job: %p (key %s)",

             (long) pthread_self(), (void*)j, (char*)j->key->ptr);
             (long) pthread_self(), (void*)j, (char*)j->key->ptr);

+
+        redisLog(REDIS_DEBUG,"[T] lock IO");

         lockThreadedIO();
         lockThreadedIO();

+        redisLog(REDIS_DEBUG,"[T] IO locked");

         listDelNode(server.io_processing,ln);
         listAddNodeTail(server.io_processed,j);
         listDelNode(server.io_processing,ln);
         listAddNodeTail(server.io_processed,j);

-        unlockThreadedIO();

 
         /* Signal the main thread there is new stuff to process */
         redisAssert(write(server.io_ready_pipe_write,"x",1) == 1);
 
         /* Signal the main thread there is new stuff to process */
         redisAssert(write(server.io_ready_pipe_write,"x",1) == 1);

+        redisLog(REDIS_DEBUG,"TIME (%c): %lld\n", j->type == REDIS_IOJOB_LOAD ? 'L' : 'S', ustime()-start);

     }
     }

-    return NULL; /* never reached */
+    /* never reached, but that's the full pattern... */
+    unlockThreadedIO();
+    return NULL;

 }
 
 void spawnIOThread(void) {
 }
 
 void spawnIOThread(void) {


@@ -397,34 +491,95 @@ void spawnIOThread(void) {
     server.io_active_threads++;
 }
 
     server.io_active_threads++;
 }
 

-/* We need to wait for the last thread to exit before we are able to
- * fork() in order to BGSAVE or BGREWRITEAOF. */
-void waitEmptyIOJobsQueue(void) {
-    while(1) {
+/* Wait that up to 'max' pending IO Jobs are processed by the I/O thread.
+ * From our point of view an IO job processed means that the count of
+ * server.io_processed must increase by one.
+ *
+ * If max is -1, all the pending IO jobs will be processed.
+ *
+ * Returns the number of IO jobs processed.
+ *
+ * NOTE: while this may appear like a busy loop, we are actually blocked
+ * by IO since we continuously acquire/release the IO lock. */
+int processActiveIOJobs(int max) {
+    int processed = 0;
+
+    while(max == -1 || max > 0) {

         int io_processed_len;
 
         int io_processed_len;
 

+        redisLog(REDIS_DEBUG,"[P] lock IO");

         lockThreadedIO();
         lockThreadedIO();

+        redisLog(REDIS_DEBUG,"Waiting IO jobs processing: new:%d proessing:%d processed:%d",listLength(server.io_newjobs),listLength(server.io_processing),listLength(server.io_processed));
+

         if (listLength(server.io_newjobs) == 0 &&
         if (listLength(server.io_newjobs) == 0 &&

-            listLength(server.io_processing) == 0 &&
-            server.io_active_threads == 0)
+            listLength(server.io_processing) == 0)

         {
         {

+            /* There is nothing more to process */
+            redisLog(REDIS_DEBUG,"[P] Nothing to process, unlock IO, return");

             unlockThreadedIO();
             unlockThreadedIO();

-            return;
+            break;
+        }
+
+#if 1
+        /* If there are new jobs we need to signal the thread to
+         * process the next one. FIXME: drop this if useless. */
+        redisLog(REDIS_DEBUG,"[P] waitEmptyIOJobsQueue: new %d, processing %d, processed %d",
+            listLength(server.io_newjobs),
+            listLength(server.io_processing),
+            listLength(server.io_processed));
+
+        if (listLength(server.io_newjobs)) {
+            redisLog(REDIS_DEBUG,"[P] There are new jobs, signal");
+            pthread_cond_signal(&server.io_condvar);

         }
         }

-        /* While waiting for empty jobs queue condition we post-process some
-         * finshed job, as I/O threads may be hanging trying to write against
-         * the io_ready_pipe_write FD but there are so much pending jobs that
-         * it's blocking. */
+#endif
+
+        /* Check if we can process some finished job */

         io_processed_len = listLength(server.io_processed);
         io_processed_len = listLength(server.io_processed);

+        redisLog(REDIS_DEBUG,"[P] Unblock IO");

         unlockThreadedIO();
         unlockThreadedIO();

+        redisLog(REDIS_DEBUG,"[P] Wait");
+        usleep(10000);

         if (io_processed_len) {
             vmThreadedIOCompletedJob(NULL,server.io_ready_pipe_read,
                                                         (void*)0xdeadbeef,0);
         if (io_processed_len) {
             vmThreadedIOCompletedJob(NULL,server.io_ready_pipe_read,
                                                         (void*)0xdeadbeef,0);

-            usleep(1000); /* 1 millisecond */
-        } else {
-            usleep(10000); /* 10 milliseconds */
+            processed++;
+            if (max != -1) max--;

         }
     }
         }
     }

+    return processed;
+}
+
+void waitEmptyIOJobsQueue(void) {
+    processActiveIOJobs(-1);
+}
+
+/* Process up to 'max' IO Jobs already completed by threads but still waiting
+ * processing from the main thread.
+ *
+ * If max == -1 all the pending jobs are processed.
+ *
+ * The number of processed jobs is returned. */
+int processPendingIOJobs(int max) {
+    int processed = 0;
+
+    while(max == -1 || max > 0) {
+        int io_processed_len;
+
+        lockThreadedIO();
+        io_processed_len = listLength(server.io_processed);
+        unlockThreadedIO();
+        if (io_processed_len == 0) break;
+        vmThreadedIOCompletedJob(NULL,server.io_ready_pipe_read,
+                                                    (void*)0xdeadbeef,0);
+        if (max != -1) max--;
+        processed++;
+    }
+    return processed;
+}
+
+void processAllPendingIOJobs(void) {
+    processPendingIOJobs(-1);

 }
 
 /* This function must be called while with threaded IO locked */
 }
 
 /* This function must be called while with threaded IO locked */


@@ -432,11 +587,23 @@ void queueIOJob(iojob *j) {
     redisLog(REDIS_DEBUG,"Queued IO Job %p type %d about key '%s'\n",
         (void*)j, j->type, (char*)j->key->ptr);
     listAddNodeTail(server.io_newjobs,j);
     redisLog(REDIS_DEBUG,"Queued IO Job %p type %d about key '%s'\n",
         (void*)j, j->type, (char*)j->key->ptr);
     listAddNodeTail(server.io_newjobs,j);

-    if (server.io_active_threads < server.vm_max_threads)
-        spawnIOThread();

 }
 
 }
 

-void dsCreateIOJob(int type, redisDb *db, robj *key, robj *val) {
+/* Consume all the IO scheduled operations, and all the thread IO jobs
+ * so that eventually the state of diskstore is a point-in-time snapshot.
+ *
+ * This is useful when we need to BGSAVE with diskstore enabled. */
+void cacheForcePointInTime(void) {
+    redisLog(REDIS_NOTICE,"Diskstore: synching on disk to reach point-in-time state.");
+    while (listLength(server.cache_io_queue) != 0) {
+        cacheScheduleIOPushJobs(REDIS_IO_ASAP);
+        processActiveIOJobs(1);
+    }
+    waitEmptyIOJobsQueue();
+    processAllPendingIOJobs();
+}
+
+void cacheCreateIOJob(int type, redisDb *db, robj *key, robj *val, time_t expire) {

     iojob *j;
 
     j = zmalloc(sizeof(*j));
     iojob *j;
 
     j = zmalloc(sizeof(*j));


@@ -446,86 +613,240 @@ void dsCreateIOJob(int type, redisDb *db, robj *key, robj *val) {
     incrRefCount(key);
     j->val = val;
     if (val) incrRefCount(val);
     incrRefCount(key);
     j->val = val;
     if (val) incrRefCount(val);

+    j->expire = expire;

 
     lockThreadedIO();
     queueIOJob(j);
 
     lockThreadedIO();
     queueIOJob(j);

+    pthread_cond_signal(&server.io_condvar);

     unlockThreadedIO();
 }
 
     unlockThreadedIO();
 }
 

-void cacheScheduleForFlush(redisDb *db, robj *key) {
-    dirtykey *dk;
-    dictEntry *de;
-    
-    de = dictFind(db->dict,key->ptr);
-    if (de) {
-        robj *val = dictGetEntryVal(de);
-        if (val->storage == REDIS_DS_DIRTY)
-            return;
-        else
-            val->storage = REDIS_DS_DIRTY;
+/* ============= Disk store cache - Scheduling of IO operations ============= 
+ *
+ * We use a queue and an hash table to hold the state of IO operations
+ * so that's fast to lookup if there is already an IO operation in queue
+ * for a given key.
+ *
+ * There are two types of IO operations for a given key:
+ * REDIS_IO_LOAD and REDIS_IO_SAVE.
+ *
+ * The function cacheScheduleIO() function pushes the specified IO operation
+ * in the queue, but avoid adding the same key for the same operation
+ * multiple times, thanks to the associated hash table.
+ *
+ * We take a set of flags per every key, so when the scheduled IO operation
+ * gets moved from the scheduled queue to the actual IO Jobs queue that
+ * is processed by the IO thread, we flag it as IO_LOADINPROG or
+ * IO_SAVEINPROG.
+ *
+ * So for every given key we always know if there is some IO operation
+ * scheduled, or in progress, for this key.
+ *
+ * NOTE: all this is very important in order to guarantee correctness of
+ * the Disk Store Cache. Jobs are always queued here. Load jobs are
+ * queued at the head for faster execution only in the case there is not
+ * already a write operation of some kind for this job.
+ *
+ * So we have ordering, but can do exceptions when there are no already
+ * operations for a given key. Also when we need to block load a given
+ * key, for an immediate lookup operation, we can check if the key can
+ * be accessed synchronously without race conditions (no IN PROGRESS
+ * operations for this key), otherwise we blocking wait for completion. */
+
+#define REDIS_IO_LOAD 1
+#define REDIS_IO_SAVE 2
+#define REDIS_IO_LOADINPROG 4
+#define REDIS_IO_SAVEINPROG 8
+
+void cacheScheduleIOAddFlag(redisDb *db, robj *key, long flag) {
+    struct dictEntry *de = dictFind(db->io_queued,key);
+
+    if (!de) {
+        dictAdd(db->io_queued,key,(void*)flag);
+        incrRefCount(key);
+        return;
+    } else {
+        long flags = (long) dictGetEntryVal(de);
+
+        if (flags & flag) {
+            redisLog(REDIS_WARNING,"Adding the same flag again: was: %ld, addede: %ld",flags,flag);
+            redisAssert(!(flags & flag));
+        }
+        flags |= flag;
+        dictGetEntryVal(de) = (void*) flags;

     }
     }

+}
+
+void cacheScheduleIODelFlag(redisDb *db, robj *key, long flag) {
+    struct dictEntry *de = dictFind(db->io_queued,key);
+    long flags;
+
+    redisAssert(de != NULL);
+    flags = (long) dictGetEntryVal(de);
+    redisAssert(flags & flag);
+    flags &= ~flag;
+    if (flags == 0) {
+        dictDelete(db->io_queued,key);
+    } else {
+        dictGetEntryVal(de) = (void*) flags;
+    }
+}
+
+int cacheScheduleIOGetFlags(redisDb *db, robj *key) {
+    struct dictEntry *de = dictFind(db->io_queued,key);
+
+    return (de == NULL) ? 0 : ((long) dictGetEntryVal(de));
+}

 
 

-    redisLog(REDIS_DEBUG,"Scheduling key %s for saving",key->ptr);
-    dk = zmalloc(sizeof(*dk));
-    dk->db = db;
-    dk->key = key;
+void cacheScheduleIO(redisDb *db, robj *key, int type) {
+    ioop *op;
+    long flags;
+
+    if ((flags = cacheScheduleIOGetFlags(db,key)) & type) return;
+    
+    redisLog(REDIS_DEBUG,"Scheduling key %s for %s",
+        key->ptr, type == REDIS_IO_LOAD ? "loading" : "saving");
+    cacheScheduleIOAddFlag(db,key,type);
+    op = zmalloc(sizeof(*op));
+    op->type = type;
+    op->db = db;
+    op->key = key;

     incrRefCount(key);
     incrRefCount(key);

-    dk->ctime = time(NULL);
-    listAddNodeTail(server.cache_flush_queue, key);
+    op->ctime = time(NULL);
+
+    /* Give priority to load operations if there are no save already
+     * in queue for the same key. */
+    if (type == REDIS_IO_LOAD && !(flags & REDIS_IO_SAVE)) {
+        listAddNodeHead(server.cache_io_queue, op);
+        cacheScheduleIOPushJobs(REDIS_IO_ONLYLOADS);
+    } else {
+        /* FIXME: probably when this happens we want to at least move
+         * the write job about this queue on top, and set the creation time
+         * to a value that will force processing ASAP. */
+        listAddNodeTail(server.cache_io_queue, op);
+    }

 }
 
 }
 

-void cacheCron(void) {
+/* Push scheduled IO operations into IO Jobs that the IO thread can process.
+ *
+ * If flags include REDIS_IO_ONLYLOADS only load jobs are processed:this is
+ * useful since it's safe to push LOAD IO jobs from any place of the code, while
+ * SAVE io jobs should never be pushed while we are processing a command
+ * (not protected by lookupKey() that will block on keys in IO_SAVEINPROG
+ * state.
+ *
+ * The REDIS_IO_ASAP flag tells the function to don't wait for the IO job
+ * scheduled completion time, but just do the operation ASAP. This is useful
+ * when we need to reclaim memory from the IO queue.
+ */
+#define MAX_IO_JOBS_QUEUE 10
+int cacheScheduleIOPushJobs(int flags) {

     time_t now = time(NULL);
     listNode *ln;
     time_t now = time(NULL);
     listNode *ln;

+    int jobs, topush = 0, pushed = 0;

 
 

-    /* Sync stuff on disk */
-    while((ln = listFirst(server.cache_flush_queue)) != NULL) {
-        dirtykey *dk = ln->value;
+    /* Don't push new jobs if there is a threaded BGSAVE in progress. */
+    if (server.bgsavethread != (pthread_t) -1) return 0;

 
 

-        if ((now - dk->ctime) >= server.cache_flush_delay) {
-            struct dictEntry *de;
-            robj *val;
+    /* Sync stuff on disk, but only if we have less
+     * than MAX_IO_JOBS_QUEUE IO jobs. */
+    lockThreadedIO();
+    jobs = listLength(server.io_newjobs);
+    unlockThreadedIO();
+
+    topush = MAX_IO_JOBS_QUEUE-jobs;
+    if (topush < 0) topush = 0;
+    if (topush > (signed)listLength(server.cache_io_queue))
+        topush = listLength(server.cache_io_queue);
+
+    while((ln = listFirst(server.cache_io_queue)) != NULL) {
+        ioop *op = ln->value;
+        struct dictEntry *de;
+        robj *val;
+
+        if (!topush) break;
+        topush--;

 
 

-            redisLog(REDIS_DEBUG,"Creating IO Job to save key %s",dk->key->ptr);
+        if (op->type != REDIS_IO_LOAD && flags & REDIS_IO_ONLYLOADS) break;

 
 

-            /* Lookup the key. We need to check if it's still here and
-             * possibly access to the value. */
-            de = dictFind(dk->db->dict,dk->key->ptr);
+        /* Don't execute SAVE before the scheduled time for completion */
+        if (op->type == REDIS_IO_SAVE && !(flags & REDIS_IO_ASAP) &&
+              (now - op->ctime) < server.cache_flush_delay) break;
+
+        /* Don't add a SAVE job in the IO thread queue if there is already
+         * a save in progress for the same key. */
+        if (op->type == REDIS_IO_SAVE && 
+            cacheScheduleIOGetFlags(op->db,op->key) & REDIS_IO_SAVEINPROG)
+        {
+            /* Move the operation at the end of the list if there
+             * are other operations, so we can try to process the next one.
+             * Otherwise break, nothing to do here. */
+            if (listLength(server.cache_io_queue) > 1) {
+                listDelNode(server.cache_io_queue,ln);
+                listAddNodeTail(server.cache_io_queue,op);
+                continue;
+            } else {
+                break;
+            }
+        }
+
+        redisLog(REDIS_DEBUG,"Creating IO %s Job for key %s",
+            op->type == REDIS_IO_LOAD ? "load" : "save", op->key->ptr);
+
+        if (op->type == REDIS_IO_LOAD) {
+            cacheCreateIOJob(REDIS_IOJOB_LOAD,op->db,op->key,NULL,0);
+        } else {
+            time_t expire = -1;
+
+            /* Lookup the key, in order to put the current value in the IO
+             * Job. Otherwise if the key does not exists we schedule a disk
+             * store delete operation, setting the value to NULL. */
+            de = dictFind(op->db->dict,op->key->ptr);

             if (de) {
                 val = dictGetEntryVal(de);
             if (de) {
                 val = dictGetEntryVal(de);

-                redisAssert(val->storage == REDIS_DS_DIRTY);
-                val->storage = REDIS_DS_SAVING;
+                expire = getExpire(op->db,op->key);

             } else {
                 /* Setting the value to NULL tells the IO thread to delete
                  * the key on disk. */
                 val = NULL;
             }
             } else {
                 /* Setting the value to NULL tells the IO thread to delete
                  * the key on disk. */
                 val = NULL;
             }

-            dsCreateIOJob(REDIS_IOJOB_SAVE,dk->db,dk->key,val);
-            listDelNode(server.cache_flush_queue,ln);
-        } else {
-            break; /* too early */
+            cacheCreateIOJob(REDIS_IOJOB_SAVE,op->db,op->key,val,expire);

         }
         }

+        /* Mark the operation as in progress. */
+        cacheScheduleIODelFlag(op->db,op->key,op->type);
+        cacheScheduleIOAddFlag(op->db,op->key,
+            (op->type == REDIS_IO_LOAD) ? REDIS_IO_LOADINPROG :
+                                          REDIS_IO_SAVEINPROG);
+        /* Finally remove the operation from the queue.
+         * But we'll have trace of it in the hash table. */
+        listDelNode(server.cache_io_queue,ln);
+        decrRefCount(op->key);
+        zfree(op);
+        pushed++;

     }
     }

+    return pushed;
+}
+
+void cacheCron(void) {
+    /* Push jobs */
+    cacheScheduleIOPushJobs(0);

 
     /* Reclaim memory from the object cache */
     while (server.ds_enabled && zmalloc_used_memory() >
             server.cache_max_memory)
     {
 
     /* Reclaim memory from the object cache */
     while (server.ds_enabled && zmalloc_used_memory() >
             server.cache_max_memory)
     {

-        if (cacheFreeOneEntry() == REDIS_ERR) break;
+        int done = 0;
+
+        if (cacheFreeOneEntry() == REDIS_OK) done++;
+        if (negativeCacheEvictOneEntry() == REDIS_OK) done++;
+        if (done == 0) break; /* nothing more to free */

     }
 }
 
     }
 }
 

-/* ============ Virtual Memory - Blocking clients on missing keys =========== */
+/* ========== Disk store cache - Blocking clients on missing keys =========== */

 
 /* This function makes the clinet 'c' waiting for the key 'key' to be loaded.
 
 /* This function makes the clinet 'c' waiting for the key 'key' to be loaded.

- * If the key is already in memory we don't need to block, regardless
- * of the storage of the value object for this key:
- *
- * - If it's REDIS_DS_MEMORY we have the key in memory.
- * - If it's REDIS_DS_DIRTY they key was modified, but still in memory.
- * - if it's REDIS_DS_SAVING the key is being saved by an IO Job. When
- *   the client will lookup the key it will block if the key is still
- *   in this stage but it's more or less the best we can do.
+ * If the key is already in memory we don't need to block.

  *
  *   FIXME: we should try if it's actually better to suspend the client
  *   accessing an object that is being saved, and awake it only when
  *
  *   FIXME: we should try if it's actually better to suspend the client
  *   accessing an object that is being saved, and awake it only when


@@ -545,6 +866,9 @@ int waitForSwappedKey(redisClient *c, robj *key) {
     de = dictFind(c->db->dict,key->ptr);
     if (de != NULL) return 0;
 
     de = dictFind(c->db->dict,key->ptr);
     if (de != NULL) return 0;
 

+    /* Don't wait for keys we are sure are not on disk either */
+    if (!cacheKeyMayExist(c->db,key)) return 0;
+

     /* Add the key to the list of keys this client is waiting for.
      * This maps clients to keys they are waiting for. */
     listAddNodeTail(c->io_keys,key);
     /* Add the key to the list of keys this client is waiting for.
      * This maps clients to keys they are waiting for. */
     listAddNodeTail(c->io_keys,key);


@@ -566,62 +890,17 @@ int waitForSwappedKey(redisClient *c, robj *key) {
     listAddNodeTail(l,c);
 
     /* Are we already loading the key from disk? If not create a job */
     listAddNodeTail(l,c);
 
     /* Are we already loading the key from disk? If not create a job */

-    if (de == NULL)
-        dsCreateIOJob(REDIS_IOJOB_LOAD,c->db,key,NULL);
-    return 1;
-}
-
-/* Preload keys for any command with first, last and step values for
- * the command keys prototype, as defined in the command table. */
-void waitForMultipleSwappedKeys(redisClient *c, struct redisCommand *cmd, int argc, robj **argv) {
-    int j, last;
-    if (cmd->vm_firstkey == 0) return;
-    last = cmd->vm_lastkey;
-    if (last < 0) last = argc+last;
-    for (j = cmd->vm_firstkey; j <= last; j += cmd->vm_keystep) {
-        redisAssert(j < argc);
-        waitForSwappedKey(c,argv[j]);
-    }
-}
-
-/* Preload keys needed for the ZUNIONSTORE and ZINTERSTORE commands.
- * Note that the number of keys to preload is user-defined, so we need to
- * apply a sanity check against argc. */
-void zunionInterBlockClientOnSwappedKeys(redisClient *c, struct redisCommand *cmd, int argc, robj **argv) {
-    int i, num;
-    REDIS_NOTUSED(cmd);
-
-    num = atoi(argv[2]->ptr);
-    if (num > (argc-3)) return;
-    for (i = 0; i < num; i++) {
-        waitForSwappedKey(c,argv[3+i]);
-    }
-}
-
-/* Preload keys needed to execute the entire MULTI/EXEC block.
- *
- * This function is called by blockClientOnSwappedKeys when EXEC is issued,
- * and will block the client when any command requires a swapped out value. */
-void execBlockClientOnSwappedKeys(redisClient *c, struct redisCommand *cmd, int argc, robj **argv) {
-    int i, margc;
-    struct redisCommand *mcmd;
-    robj **margv;
-    REDIS_NOTUSED(cmd);
-    REDIS_NOTUSED(argc);
-    REDIS_NOTUSED(argv);
-
-    if (!(c->flags & REDIS_MULTI)) return;
-    for (i = 0; i < c->mstate.count; i++) {
-        mcmd = c->mstate.commands[i].cmd;
-        margc = c->mstate.commands[i].argc;
-        margv = c->mstate.commands[i].argv;
-
-        if (mcmd->vm_preload_proc != NULL) {
-            mcmd->vm_preload_proc(c,mcmd,margc,margv);
-        } else {
-            waitForMultipleSwappedKeys(c,mcmd,margc,margv);
-        }
+    if (de == NULL) {
+        int flags = cacheScheduleIOGetFlags(c->db,key);
+
+        /* It is possible that even if there are no clients waiting for
+         * a load operation, still we have a load operation in progress.
+         * For instance think to a client performing a GET and then
+         * closing the connection */
+        if ((flags & (REDIS_IO_LOAD|REDIS_IO_LOADINPROG)) == 0)
+            cacheScheduleIO(c->db,key,REDIS_IO_LOAD);

     }
     }

+    return 1;

 }
 
 /* Is this client attempting to run a command against swapped keys?
 }
 
 /* Is this client attempting to run a command against swapped keys?


@@ -635,10 +914,39 @@ void execBlockClientOnSwappedKeys(redisClient *c, struct redisCommand *cmd, int
  * Return 1 if the client is marked as blocked, 0 if the client can
  * continue as the keys it is going to access appear to be in memory. */
 int blockClientOnSwappedKeys(redisClient *c, struct redisCommand *cmd) {
  * Return 1 if the client is marked as blocked, 0 if the client can
  * continue as the keys it is going to access appear to be in memory. */
 int blockClientOnSwappedKeys(redisClient *c, struct redisCommand *cmd) {

-    if (cmd->vm_preload_proc != NULL) {
-        cmd->vm_preload_proc(c,cmd,c->argc,c->argv);
+    int *keyindex, numkeys, j, i;
+
+    /* EXEC is a special case, we need to preload all the commands
+     * queued into the transaction */
+    if (cmd->proc == execCommand) {
+        struct redisCommand *mcmd;
+        robj **margv;
+        int margc;
+
+        if (!(c->flags & REDIS_MULTI)) return 0;
+        for (i = 0; i < c->mstate.count; i++) {
+            mcmd = c->mstate.commands[i].cmd;
+            margc = c->mstate.commands[i].argc;
+            margv = c->mstate.commands[i].argv;
+
+            keyindex = getKeysFromCommand(mcmd,margv,margc,&numkeys,
+                                          REDIS_GETKEYS_PRELOAD);
+            for (j = 0; j < numkeys; j++) {
+                redisLog(REDIS_DEBUG,"Preloading %s",
+                    (char*)margv[keyindex[j]]->ptr);
+                waitForSwappedKey(c,margv[keyindex[j]]);
+            }
+            getKeysFreeResult(keyindex);
+        }

     } else {
     } else {

-        waitForMultipleSwappedKeys(c,cmd,c->argc,c->argv);
+        keyindex = getKeysFromCommand(cmd,c->argv,c->argc,&numkeys,
+                                      REDIS_GETKEYS_PRELOAD);
+        for (j = 0; j < numkeys; j++) {
+            redisLog(REDIS_DEBUG,"Preloading %s",
+                (char*)c->argv[keyindex[j]]->ptr);
+            waitForSwappedKey(c,c->argv[keyindex[j]]);
+        }
+        getKeysFreeResult(keyindex);

     }
 
     /* If the client was blocked for at least one key, mark it as blocked. */
     }
 
     /* If the client was blocked for at least one key, mark it as blocked. */