From: antirez Date: Thu, 28 Oct 2010 12:12:25 +0000 (+0200) Subject: Merge remote branch 'remotes/pietern/zrevrangebyscore' X-Git-Url: https://git.saurik.com/redis.git/commitdiff_plain/73abd0a9d2a956af34351c59e15eba603ab29c6e?hp=-c Merge remote branch 'remotes/pietern/zrevrangebyscore' --- 73abd0a9d2a956af34351c59e15eba603ab29c6e diff --combined src/redis.c index ab79e9da,8f208926..08bba542 --- a/src/redis.c +++ b/src/redis.c @@@ -120,6 -120,7 +120,7 @@@ struct redisCommand readonlyCommandTabl {"zinterstore",zinterstoreCommand,-4,REDIS_CMD_INLINE|REDIS_CMD_DENYOOM,zunionInterBlockClientOnSwappedKeys,0,0,0}, {"zrange",zrangeCommand,-4,REDIS_CMD_INLINE,NULL,1,1,1}, {"zrangebyscore",zrangebyscoreCommand,-4,REDIS_CMD_INLINE,NULL,1,1,1}, + {"zrevrangebyscore",zrevrangebyscoreCommand,-4,REDIS_CMD_INLINE,NULL,1,1,1}, {"zcount",zcountCommand,4,REDIS_CMD_INLINE,NULL,1,1,1}, {"zrevrange",zrevrangeCommand,-4,REDIS_CMD_INLINE,NULL,1,1,1}, {"zcard",zcardCommand,2,REDIS_CMD_INLINE,NULL,1,1,1}, @@@ -478,10 -479,6 +479,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++; @@@ -494,19 -491,19 +495,19 @@@ * in objects at every object access, and accuracy is not needed. * To access a global var is faster than calling time(NULL) */ server.unixtime = time(NULL); - /* We have just 21 bits per object for LRU information. - * So we use an (eventually wrapping) LRU clock with minutes resolution. + /* We have just 22 bits per object for LRU information. + * 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. * - * When we need to select what object to swap, we compute the minimum - * time distance between the current lruclock and the object last access - * lruclock info. Even if clocks will wrap on overflow, there is - * the interesting property that we are sure that at least - * ABS(A-B) minutes passed between current time and timestamp B. + * 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. But for this to happen a given object should never be touched + * for 1.5 years. * - * This is not precise but we don't need at all precision, but just - * something statistically reasonable. + * Note that you can change the resolution altering the + * REDIS_LRU_CLOCK_RESOLUTION define. */ - server.lruclock = (time(NULL)/60)&((1<<21)-1); + updateLRUClock(); /* We received a SIGTERM, shutting down here in a safe way, as it is * not ok doing so inside the signal handler. */ @@@ -737,8 -734,6 +738,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 */ @@@ -753,7 -748,6 +754,7 @@@ server.set_max_intset_entries = REDIS_SET_MAX_INTSET_ENTRIES; server.shutdown_asap = 0; + updateLRUClock(); resetServerSaveParams(); appendServerSaveParams(60*60,1); /* save after 1 hour and 1 change */ @@@ -823,8 -817,6 +824,8 @@@ void initServer() server.stat_numconnections = 0; server.stat_expiredkeys = 0; server.stat_starttime = time(NULL); + server.stat_keyspace_misses = 0; + server.stat_keyspace_hits = 0; server.unixtime = time(NULL); aeCreateTimeEvent(server.el, 1, serverCron, NULL, NULL); if (aeCreateFileEvent(server.el, server.fd, AE_READABLE, @@@ -1093,7 -1085,7 +1094,7 @@@ int prepareForShutdown() /* Append only file: fsync() the AOF and exit */ aof_fsync(server.appendfd); if (server.vm_enabled) unlink(server.vm_swap_file); - } else { + } else if (server.saveparamslen > 0) { /* Snapshotting. Perform a SYNC SAVE and exit */ if (rdbSave(server.dbfilename) != REDIS_OK) { /* Ooops.. error saving! The best we can do is to continue @@@ -1104,8 -1096,6 +1105,8 @@@ redisLog(REDIS_WARNING,"Error trying to save the DB, can't exit"); return REDIS_ERR; } + } else { + redisLog(REDIS_WARNING,"Not saving DB."); } if (server.daemonize) unlink(server.pidfile); redisLog(REDIS_WARNING,"Server exit now, bye bye..."); @@@ -1176,7 -1166,6 +1177,7 @@@ sds genRedisInfoString(void) "process_id:%ld\r\n" "uptime_in_seconds:%ld\r\n" "uptime_in_days:%ld\r\n" + "lru_clock:%ld\r\n" "used_cpu_sys:%.2f\r\n" "used_cpu_user:%.2f\r\n" "used_cpu_sys_childrens:%.2f\r\n" @@@ -1187,7 -1176,6 +1188,7 @@@ "used_memory:%zu\r\n" "used_memory_human:%s\r\n" "mem_fragmentation_ratio:%.2f\r\n" + "use_tcmalloc:%d\r\n" "changes_since_last_save:%lld\r\n" "bgsave_in_progress:%d\r\n" "last_save_time:%ld\r\n" @@@ -1195,8 -1183,6 +1196,8 @@@ "total_connections_received:%lld\r\n" "total_commands_processed:%lld\r\n" "expired_keys:%lld\r\n" + "keyspace_hits:%lld\r\n" + "keyspace_misses:%lld\r\n" "hash_max_zipmap_entries:%zu\r\n" "hash_max_zipmap_value:%zu\r\n" "pubsub_channels:%ld\r\n" @@@ -1211,7 -1197,6 +1212,7 @@@ (long) getpid(), uptime, uptime/(3600*24), + (unsigned long) server.lruclock, (float)self_ru.ru_utime.tv_sec+(float)self_ru.ru_utime.tv_usec/1000000, (float)self_ru.ru_stime.tv_sec+(float)self_ru.ru_stime.tv_usec/1000000, (float)c_ru.ru_utime.tv_sec+(float)c_ru.ru_utime.tv_usec/1000000, @@@ -1222,11 -1207,6 +1223,11 @@@ zmalloc_used_memory(), hmem, zmalloc_get_fragmentation_ratio(), +#ifdef USE_TCMALLOC + 1, +#else + 0, +#endif server.dirty, server.bgsavechildpid != -1, server.lastsave, @@@ -1234,8 -1214,6 +1235,8 @@@ server.stat_numconnections, server.stat_numcommands, server.stat_expiredkeys, + server.stat_keyspace_hits, + server.stat_keyspace_misses, server.hash_max_zipmap_entries, server.hash_max_zipmap_value, dictSize(server.pubsub_channels), @@@ -1352,93 -1330,10 +1353,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; @@@ -1606,7 -1501,6 +1607,7 @@@ void segvHandler(int sig, siginfo_t *in int i, trace_size = 0; ucontext_t *uc = (ucontext_t*) secret; sds infostring; + struct sigaction act; REDIS_NOTUSED(info); redisLog(REDIS_WARNING, @@@ -1628,16 -1522,7 +1629,16 @@@ /* free(messages); Don't call free() with possibly corrupted memory. */ if (server.daemonize) unlink(server.pidfile); - _exit(0); + + /* Make sure we exit with the right signal at the end. So for instance + * the core will be dumped if enabled. */ + sigemptyset (&act.sa_mask); + /* When the SA_SIGINFO flag is set in sa_flags then sa_sigaction + * is used. Otherwise, sa_handler is used */ + act.sa_flags = SA_NODEFER | SA_ONSTACK | SA_RESETHAND; + act.sa_handler = SIG_DFL; + sigaction (sig, &act, NULL); + kill(getpid(),sig); } void sigtermHandler(int sig) { diff --combined src/redis.h index 5aa85388,24dfb9b5..bc961a71 --- a/src/redis.h +++ b/src/redis.h @@@ -198,13 -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) @@@ -218,8 -211,6 +218,8 @@@ void _redisPanic(char *msg, char *file /* A redis object, that is a type able to hold a string / list / set */ /* 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 */ @@@ -357,14 -348,12 +357,14 @@@ struct redisServer aeEventLoop *el; int cronloops; /* number of times the cron function run */ list *objfreelist; /* A list of freed objects to avoid malloc() */ - time_t lastsave; /* Unix time of last save succeeede */ + time_t lastsave; /* Unix time of last save succeeede */ /* Fields used only for stats */ - time_t stat_starttime; /* server start time */ - long long stat_numcommands; /* number of processed commands */ - long long stat_numconnections; /* number of connections received */ - long long stat_expiredkeys; /* number of expired keys */ + time_t stat_starttime; /* server start time */ + long long stat_numcommands; /* number of processed commands */ + long long stat_numconnections; /* number of connections received */ + long long stat_expiredkeys; /* number of expired keys */ + long long stat_keyspace_hits; /* number of successful lookups of keys */ + long long stat_keyspace_misses; /* number of failed lookups of keys */ /* Configuration */ int verbosity; int glueoutputbuf; @@@ -401,8 -390,6 +401,8 @@@ 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 @@@ -691,16 -678,6 +691,16 @@@ int getLongLongFromObject(robj *o, lon char *strEncoding(int encoding); int compareStringObjects(robj *a, robj *b); int equalStringObjects(robj *a, robj *b); +unsigned long estimateObjectIdleTime(robj *o); + +/* Synchronous I/O with timeout */ +int syncWrite(int fd, char *ptr, ssize_t size, int timeout); +int syncRead(int fd, char *ptr, ssize_t size, int timeout); +int syncReadLine(int fd, char *ptr, ssize_t size, int timeout); +int fwriteBulkString(FILE *fp, char *s, unsigned long len); +int fwriteBulkDouble(FILE *fp, double d); +int fwriteBulkLongLong(FILE *fp, long long l); +int fwriteBulkObject(FILE *fp, robj *obj); /* Replication */ void replicationFeedSlaves(list *slaves, int dictid, robj **argv, int argc); @@@ -919,6 -896,7 +919,7 @@@ void zaddCommand(redisClient *c) void zincrbyCommand(redisClient *c); void zrangeCommand(redisClient *c); void zrangebyscoreCommand(redisClient *c); + void zrevrangebyscoreCommand(redisClient *c); void zcountCommand(redisClient *c); void zrevrangeCommand(redisClient *c); void zcardCommand(redisClient *c);