From: antirez Date: Thu, 14 Oct 2010 19:22:21 +0000 (+0200) Subject: implemented different algorithms for maxmemory X-Git-Url: https://git.saurik.com/redis.git/commitdiff_plain/165346ca29972817b1245e689315edeba1fe369b implemented different algorithms for maxmemory --- diff --git a/redis.conf b/redis.conf index b087417a..a7914fd1 100644 --- a/redis.conf +++ b/redis.conf @@ -148,6 +148,25 @@ dir ./ # # maxmemory +# MAXMEMORY POLICY: how Redis will select what to remove when maxmemory +# is reached? You can select among five behavior: +# +# volatile-lru -> remove the key with an expire set using an LRU algorithm +# allkeys-lru -> remove any key accordingly to the LRU algorithm +# volatile-random -> remove a random key with an expire set +# allkeys->random -> remove a random key, any key +# volatile-ttl -> remove the key with the nearest expire time (minor TTL) +# +# maxmemory-policy volatile-lru + +# LRU and minimal TTL algorithms are not precise algorithms but approximated +# algorithms (in order to save memory), so you can select as well the sample +# size to check. For instance for default Redis will check three keys and +# pick the one that was used less recently, you can change the sample size +# using the following configuration directive. +# +# maxmemory-sample 3 + ############################## APPEND ONLY MODE ############################### # By default Redis asynchronously dumps the dataset on disk. If you can live diff --git a/src/config.c b/src/config.c index 1bd678c7..73d3ae87 100644 --- a/src/config.c +++ b/src/config.c @@ -123,6 +123,21 @@ void loadServerConfig(char *filename) { server.maxclients = atoi(argv[1]); } else if (!strcasecmp(argv[0],"maxmemory") && argc == 2) { server.maxmemory = memtoll(argv[1],NULL); + } else if (!strcasecmp(argv[0],"maxmemory-policy") && argc == 2) { + if (!strcasecmp(argv[1],"volatile-lru")) { + server.maxmemory_policy = REDIS_MAXMEMORY_VOLATILE_LRU; + } else if (!strcasecmp(argv[1],"volatile-random")) { + server.maxmemory_policy = REDIS_MAXMEMORY_VOLATILE_RANDOM; + } else if (!strcasecmp(argv[1],"volatile-ttl")) { + server.maxmemory_policy = REDIS_MAXMEMORY_VOLATILE_TTL; + } else if (!strcasecmp(argv[1],"allkeys-lru")) { + server.maxmemory_policy = REDIS_MAXMEMORY_ALLKEYS_LRU; + } else if (!strcasecmp(argv[1],"allkeys-random")) { + server.maxmemory_policy = REDIS_MAXMEMORY_ALLKEYS_RANDOM; + } else { + err = "Invalid maxmemory policy"; + goto loaderr; + } } else if (!strcasecmp(argv[0],"slaveof") && argc == 3) { server.masterhost = sdsnew(argv[1]); server.masterport = atoi(argv[2]); @@ -242,6 +257,20 @@ void configSetCommand(redisClient *c) { ll < 0) goto badfmt; server.maxmemory = ll; if (server.maxmemory) freeMemoryIfNeeded(); + } else if (!strcasecmp(c->argv[2]->ptr,"maxmemory-policy")) { + if (!strcasecmp(o->ptr,"volatile-lru")) { + server.maxmemory_policy = REDIS_MAXMEMORY_VOLATILE_LRU; + } else if (!strcasecmp(o->ptr,"volatile-random")) { + server.maxmemory_policy = REDIS_MAXMEMORY_VOLATILE_RANDOM; + } else if (!strcasecmp(o->ptr,"volatile-ttl")) { + server.maxmemory_policy = REDIS_MAXMEMORY_VOLATILE_TTL; + } else if (!strcasecmp(o->ptr,"allkeys-lru")) { + server.maxmemory_policy = REDIS_MAXMEMORY_ALLKEYS_LRU; + } else if (!strcasecmp(o->ptr,"allkeys-random")) { + server.maxmemory_policy = REDIS_MAXMEMORY_ALLKEYS_RANDOM; + } else { + goto badfmt; + } } else if (!strcasecmp(c->argv[2]->ptr,"timeout")) { if (getLongLongFromObject(o,&ll) == REDIS_ERR || ll < 0 || ll > LONG_MAX) goto badfmt; @@ -358,6 +387,21 @@ void configGetCommand(redisClient *c) { addReplyBulkCString(c,buf); matches++; } + if (stringmatch(pattern,"maxmemory-policy",0)) { + char *s; + + switch(server.maxmemory_policy) { + case REDIS_MAXMEMORY_VOLATILE_LRU: s = "volatile-lru"; break; + case REDIS_MAXMEMORY_VOLATILE_TTL: s = "volatile-ttl"; break; + case REDIS_MAXMEMORY_VOLATILE_RANDOM: s = "volatile-random"; break; + case REDIS_MAXMEMORY_ALLKEYS_LRU: s = "allkeys-lru"; break; + case REDIS_MAXMEMORY_ALLKEYS_RANDOM: s = "allkeys-random"; break; + default: s = "unknown"; break; /* too harmless to panic */ + } + addReplyBulkCString(c,"maxmemory-policy"); + addReplyBulkCString(c,s); + matches++; + } if (stringmatch(pattern,"timeout",0)) { char buf[128]; diff --git a/src/object.c b/src/object.c index e7fa3742..bba44824 100644 --- a/src/object.c +++ b/src/object.c @@ -443,8 +443,9 @@ char *strEncoding(int encoding) { * requested, using an approximated LRU algorithm. */ unsigned long estimateObjectIdleTime(robj *o) { if (server.lruclock >= o->lru) { - return (server.lruclock - o->lru) * 60; + return (server.lruclock - o->lru) * REDIS_LRU_CLOCK_RESOLUTION; } else { - return ((REDIS_LRU_CLOCK_MAX - o->lru) + server.lruclock) * 60; + return ((REDIS_LRU_CLOCK_MAX - o->lru) + server.lruclock) * + REDIS_LRU_CLOCK_RESOLUTION; } } diff --git a/src/redis.c b/src/redis.c index 774b3a81..6ce271c0 100644 --- a/src/redis.c +++ b/src/redis.c @@ -478,6 +478,10 @@ void activeExpireCycle(void) { } } +void updateLRUClock(void) { + server.lruclock = (time(NULL)/REDIS_LRU_CLOCK_RESOLUTION) & + REDIS_LRU_CLOCK_MAX; +} int serverCron(struct aeEventLoop *eventLoop, long long id, void *clientData) { int j, loops = server.cronloops++; @@ -491,14 +495,18 @@ int serverCron(struct aeEventLoop *eventLoop, long long id, void *clientData) { * To access a global var is faster than calling time(NULL) */ server.unixtime = time(NULL); /* We have just 22 bits per object for LRU information. - * So we use an (eventually wrapping) LRU clock with minutes resolution. - * 2^22 minutes are more than 7 years. + * So we use an (eventually wrapping) LRU clock with 10 seconds resolution. + * 2^22 bits with 10 seconds resoluton is more or less 1.5 years. * - * Note that even if this will wrap after 7 years it's not a problem, + * Note that even if this will wrap after 1.5 years it's not a problem, * everything will still work but just some object will appear younger - * to Redis :) + * to Redis. But for this to happen a given object should never be touched + * for 1.5 years. + * + * Note that you can change the resolution altering the + * REDIS_LRU_CLOCK_RESOLUTION define. */ - server.lruclock = (time(NULL)/60) & REDIS_LRU_CLOCK_MAX; + updateLRUClock(); /* We received a SIGTERM, shutting down here in a safe way, as it is * not ok doing so inside the signal handler. */ @@ -729,6 +737,8 @@ void initServerConfig() { server.maxclients = 0; server.blpop_blocked_clients = 0; server.maxmemory = 0; + server.maxmemory_policy = REDIS_MAXMEMORY_VOLATILE_LRU; + server.maxmemory_samples = 3; server.vm_enabled = 0; server.vm_swap_file = zstrdup("/tmp/redis-%p.vm"); server.vm_page_size = 256; /* 256 bytes per page */ @@ -742,6 +752,7 @@ void initServerConfig() { server.list_max_ziplist_value = REDIS_LIST_MAX_ZIPLIST_VALUE; server.set_max_intset_entries = REDIS_SET_MAX_INTSET_ENTRIES; server.shutdown_asap = 0; + updateLRUClock(); resetServerSaveParams(); @@ -1327,10 +1338,93 @@ int tryFreeOneObjectFromFreelist(void) { * memory usage. */ void freeMemoryIfNeeded(void) { + /* Remove keys accordingly to the active policy as long as we are + * over the memory limit. */ while (server.maxmemory && zmalloc_used_memory() > server.maxmemory) { int j, k, freed = 0; + /* Basic strategy -- remove objects from the free list. */ if (tryFreeOneObjectFromFreelist() == REDIS_OK) continue; + + for (j = 0; j < server.dbnum; j++) { + long bestval; + sds bestkey = NULL; + struct dictEntry *de; + redisDb *db = server.db+j; + dict *dict; + + if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_LRU || + server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_RANDOM) + { + dict = server.db[j].dict; + } else { + dict = server.db[j].expires; + } + if (dictSize(dict) == 0) continue; + + /* volatile-random and allkeys-random policy */ + if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_RANDOM || + server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_RANDOM) + { + de = dictGetRandomKey(dict); + bestkey = dictGetEntryKey(de); + } + + /* volatile-lru and allkeys-lru policy */ + else if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_LRU || + server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_LRU) + { + for (k = 0; k < server.maxmemory_samples; k++) { + sds thiskey; + long thisval; + robj *o; + + de = dictGetRandomKey(dict); + thiskey = dictGetEntryKey(de); + o = dictGetEntryVal(de); + thisval = estimateObjectIdleTime(o); + + /* Higher idle time is better candidate for deletion */ + if (bestkey == NULL || thisval > bestval) { + bestkey = thiskey; + bestval = thisval; + } + } + } + + /* volatile-ttl */ + else if (server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_TTL) { + for (k = 0; k < server.maxmemory_samples; k++) { + sds thiskey; + long thisval; + + de = dictGetRandomKey(dict); + thiskey = dictGetEntryKey(de); + thisval = (long) dictGetEntryVal(de); + + /* Expire sooner (minor expire unix timestamp) is better + * candidate for deletion */ + if (bestkey == NULL || thisval < bestval) { + bestkey = thiskey; + bestval = thisval; + } + } + } + + /* Finally remove the selected key. */ + if (bestkey) { + robj *keyobj = createStringObject(bestkey,sdslen(bestkey)); + dbDelete(db,keyobj); + server.stat_expiredkeys++; + decrRefCount(keyobj); + freed++; + } + } + if (!freed) return; /* nothing to free... */ + } + + while(0) { + int j, k, freed = 0; for (j = 0; j < server.dbnum; j++) { int minttl = -1; sds minkey = NULL; diff --git a/src/redis.h b/src/redis.h index d768b184..9b16b024 100644 --- a/src/redis.h +++ b/src/redis.h @@ -198,6 +198,13 @@ #define REDIS_OP_DIFF 1 #define REDIS_OP_INTER 2 +/* Redis maxmemory strategies */ +#define REDIS_MAXMEMORY_VOLATILE_LRU 0 +#define REDIS_MAXMEMORY_VOLATILE_TTL 1 +#define REDIS_MAXMEMORY_VOLATILE_RANDOM 2 +#define REDIS_MAXMEMORY_ALLKEYS_LRU 3 +#define REDIS_MAXMEMORY_ALLKEYS_RANDOM 4 + /* We can print the stacktrace, so our assert is defined this way: */ #define redisAssert(_e) ((_e)?(void)0 : (_redisAssert(#_e,__FILE__,__LINE__),_exit(1))) #define redisPanic(_e) _redisPanic(#_e,__FILE__,__LINE__),_exit(1) @@ -212,6 +219,7 @@ void _redisPanic(char *msg, char *file, int line); /* The actual Redis Object */ #define REDIS_LRU_CLOCK_MAX ((1<<21)-1) /* Max value of obj->lru */ +#define REDIS_LRU_CLOCK_RESOLUTION 10 /* LRU clock resolution in seconds */ typedef struct redisObject { unsigned type:4; unsigned storage:2; /* REDIS_VM_MEMORY or REDIS_VM_SWAPPING */ @@ -391,6 +399,8 @@ struct redisServer { int replstate; unsigned int maxclients; unsigned long long maxmemory; + int maxmemory_policy; + int maxmemory_samples; unsigned int blpop_blocked_clients; unsigned int vm_blocked_clients; /* Sort parameters - qsort_r() is only available under BSD so we