* documentation. */
/* TODO:
+ *
+ * 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.
*
* - 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
* - What happens with MULTI/EXEC?
*
* Good question.
+ *
+ * - If dsSet() fails on the write thread log the error and reschedule the
+ * key for flush.
+ *
+ * - Check 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() 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?
*/
/* Virtual Memory is composed mainly of two subsystems:
zmalloc_enable_thread_safeness(); /* we need thread safe zmalloc() */
- redisLog(REDIS_NOTICE,"Initializing Disk Store at %s", server.ds_path);
+ redisLog(REDIS_NOTICE,"Opening Disk Store: %s", server.ds_path);
/* Open Disk Store */
if (dsOpen() != REDIS_OK) {
redisLog(REDIS_WARNING,"Fatal error opening disk store. Exiting.");
server.io_processed = listCreate();
server.io_ready_clients = listCreate();
pthread_mutex_init(&server.io_mutex,NULL);
+ pthread_cond_init(&server.io_condvar,NULL);
server.io_active_threads = 0;
if (pipe(pipefds) == -1) {
redisLog(REDIS_WARNING,"Unable to intialized DS: pipe(2): %s. Exiting."
for (i = 0; i < 5; i++) {
dictEntry *de;
double swappability;
+ robj keyobj;
+ sds keystr;
if (maxtries) maxtries--;
de = dictGetRandomKey(db->dict);
+ keystr = dictGetEntryKey(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;
}
return (server.bgsavechildpid == -1 && server.bgrewritechildpid == -1);
}
-/* =================== Virtual Memory - Threaded I/O ======================= */
+/* ==================== 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);
+ }
+}
+
+/* ================== Disk store cache - Threaded I/O ====================== */
void freeIOJob(iojob *j) {
decrRefCount(j->key);
while((retval = read(fd,buf,1)) == 1) {
iojob *j;
listNode *ln;
- struct dictEntry *de;
redisLog(REDIS_DEBUG,"Processing I/O completed job");
redisLog(REDIS_DEBUG,"COMPLETED Job type %s, key: %s",
(j->type == REDIS_IOJOB_LOAD) ? "load" : "save",
(unsigned char*)j->key->ptr);
- de = dictFind(j->db->dict,j->key->ptr);
- redisAssert(de != NULL);
if (j->type == REDIS_IOJOB_LOAD) {
/* Create the key-value pair in the in-memory database */
- dbAdd(j->db,j->key,j->val);
- /* Handle clients waiting for this key to be loaded. */
+ if (j->val != NULL) {
+ /* 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 {
+ /* The key does not exist. Create a negative cache entry
+ * for this key. */
+ cacheSetKeyDoesNotExist(j->db,j->key);
+ }
+ cacheScheduleIODelFlag(j->db,j->key,REDIS_IO_LOADINPROG);
handleClientsBlockedOnSwappedKey(j->db,j->key);
freeIOJob(j);
} else if (j->type == REDIS_IOJOB_SAVE) {
- redisAssert(j->val->storage == REDIS_DS_SAVING);
- j->val->storage = REDIS_DS_MEMORY;
+ if (j->val) {
+ cacheSetKeyMayExist(j->db,j->key);
+ } else {
+ cacheSetKeyDoesNotExist(j->db,j->key);
+ }
+ cacheScheduleIODelFlag(j->db,j->key,REDIS_IO_SAVEINPROG);
freeIOJob(j);
}
processed++;
REDIS_NOTUSED(arg);
pthread_detach(pthread_self());
+ lockThreadedIO();
while(1) {
/* Get a new job to process */
- lockThreadedIO();
if (listLength(server.io_newjobs) == 0) {
- /* No new jobs in queue, exit. */
- redisLog(REDIS_DEBUG,"Thread %ld exiting, nothing to do",
- (long) pthread_self());
- server.io_active_threads--;
- unlockThreadedIO();
- return NULL;
+ /* Wait for more work to do */
+ pthread_cond_wait(&server.io_condvar,&server.io_mutex);
+ continue;
}
+ redisLog(REDIS_DEBUG,"%ld IO jobs to process",
+ listLength(server.io_newjobs));
ln = listFirst(server.io_newjobs);
j = ln->value;
listDelNode(server.io_newjobs,ln);
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'",
(long) pthread_self(),
(j->type == REDIS_IOJOB_LOAD) ? "load" : "save",
/* Process the Job */
if (j->type == REDIS_IOJOB_LOAD) {
- j->val = dsGet(j->db,j->key);
- redisAssert(j->val != NULL);
+ time_t expire;
+
+ 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)
+ if (j->val) {
dsSet(j->db,j->key,j->val);
- else
+ } else {
dsDel(j->db,j->key);
+ }
}
/* Done: insert the job into the processed queue */
redisLog(REDIS_DEBUG,"Thread %ld completed the job: %p (key %s)",
(long) pthread_self(), (void*)j, (char*)j->key->ptr);
+
lockThreadedIO();
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);
}
- return NULL; /* never reached */
+ /* never reached, but that's the full pattern... */
+ unlockThreadedIO();
+ return NULL;
}
void spawnIOThread(void) {
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. */
+/* Wait that all the pending IO Jobs are processed */
void waitEmptyIOJobsQueue(void) {
while(1) {
int io_processed_len;
lockThreadedIO();
if (listLength(server.io_newjobs) == 0 &&
- listLength(server.io_processing) == 0 &&
- server.io_active_threads == 0)
+ listLength(server.io_processing) == 0)
{
unlockThreadedIO();
return;
}
+ /* If there are new jobs we need to signal the thread to
+ * process the next one. */
+ redisLog(REDIS_DEBUG,"waitEmptyIOJobsQueue: new %d, processing %d",
+ listLength(server.io_newjobs),
+ listLength(server.io_processing));
+ /*
+ if (listLength(server.io_newjobs)) {
+ 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
}
}
+/* Process all the IO Jobs already completed by threads but still waiting
+ * processing from the main thread. */
+void processAllPendingIOJobs(void) {
+ while(1) {
+ int io_processed_len;
+
+ lockThreadedIO();
+ io_processed_len = listLength(server.io_processed);
+ unlockThreadedIO();
+ if (io_processed_len == 0) return;
+ vmThreadedIOCompletedJob(NULL,server.io_ready_pipe_read,
+ (void*)0xdeadbeef,0);
+ }
+}
+
/* This function must be called while with threaded IO locked */
void queueIOJob(iojob *j) {
redisLog(REDIS_DEBUG,"Queued IO Job %p type %d about key '%s'\n",
j->key = key;
incrRefCount(key);
j->val = val;
- incrRefCount(val);
+ if (val) incrRefCount(val);
lockThreadedIO();
queueIOJob(j);
+ pthread_cond_signal(&server.io_condvar);
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;
- dk = zmalloc(sizeof(*dk));
- dk->db = db;
- dk->key = key;
+ 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));
+}
+
+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);
- 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);
+ } 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) {
time_t now = time(NULL);
listNode *ln;
+ int jobs, topush = 0;
- /* Sync stuff on disk */
- while((ln = listFirst(server.cache_flush_queue)) != NULL) {
- dirtykey *dk = ln->value;
+ /* Sync stuff on disk, but only if we have less than 100 IO jobs */
+ lockThreadedIO();
+ jobs = listLength(server.io_newjobs);
+ unlockThreadedIO();
+
+ topush = 100-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;
- if ((now - dk->ctime) >= server.cache_flush_delay) {
+ if (!topush) break;
+ topush--;
+
+ if (op->type == REDIS_IO_LOAD ||
+ (now - op->ctime) >= server.cache_flush_delay)
+ {
struct dictEntry *de;
robj *val;
- /* 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);
- if (de) {
- val = dictGetEntryVal(de);
- redisAssert(val->storage == REDIS_DS_DIRTY);
- val->storage = REDIS_DS_SAVING;
+ /* Don't add a SAVE job in 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 of there
+ * are other operations. 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) {
+ dsCreateIOJob(REDIS_IOJOB_LOAD,op->db,op->key,NULL);
} else {
- /* Setting the value to NULL tells the IO thread to delete
- * the key on disk. */
- val = NULL;
+ /* 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);
+ } else {
+ /* Setting the value to NULL tells the IO thread to delete
+ * the key on disk. */
+ val = NULL;
+ }
+ dsCreateIOJob(REDIS_IOJOB_SAVE,op->db,op->key,val);
}
- dsCreateIOJob(REDIS_IOJOB_SAVE,dk->db,dk->key,val);
- listDelNode(server.cache_flush_queue,ln);
+ /* 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);
} else {
break; /* too early */
}
server.cache_max_memory)
{
if (cacheFreeOneEntry() == REDIS_ERR) break;
+ /* FIXME: also free negative cache entries here. */
}
}
-/* ============ 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.
- * 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
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);
/* Are we already loading the key from disk? If not create a job */
if (de == NULL)
- dsCreateIOJob(REDIS_IOJOB_LOAD,c->db,key,NULL);
+ cacheScheduleIO(c->db,key,REDIS_IO_LOAD);
return 1;
}
projects / redis.git / blobdiff