From: antirez Date: Tue, 9 Mar 2010 15:19:33 +0000 (+0100) Subject: Merged ZREVRANK from Pietern X-Git-Url: https://git.saurik.com/redis.git/commitdiff_plain/e3f46030fcfd0ffd916d473b16d0ed07e138fefb?hp=798d9e55317d67fa694e5408dc30a61e021e8b49 Merged ZREVRANK from Pietern --- diff --git a/TODO b/TODO index e54a0aec..f9fa8f2a 100644 --- a/TODO +++ b/TODO @@ -59,6 +59,7 @@ BIG ONES: SMALL ONES: +* If sizeof(double) == sizeof(void*) we could store the double value of sorted sets directly in place of the pointer instead of allocating it in the heap. * Delete on writes against expire policy should only happen after argument parsing for commands doing their own arg parsing stuff. * Give errors when incrementing a key that does not look like an integer, when providing as a sorted set score something can't be parsed as a double, and so forth. * MSADD (n keys) (n values). See this thread in the Redis google group: http://groups.google.com/group/redis-db/browse_thread/thread/e766d84eb375cd41 diff --git a/redis.c b/redis.c index c882694d..c1777c76 100644 --- a/redis.c +++ b/redis.c @@ -226,6 +226,10 @@ #define APPENDFSYNC_ALWAYS 1 #define APPENDFSYNC_EVERYSEC 2 +/* Hashes related defaults */ +#define REDIS_HASH_MAX_ZIPMAP_ENTRIES 64 +#define REDIS_HASH_MAX_ZIPMAP_VALUE 512 + /* We can print the stacktrace, so our assert is defined this way: */ #define redisAssert(_e) ((_e)?(void)0 : (_redisAssert(#_e,__FILE__,__LINE__),_exit(1))) static void _redisAssert(char *estr, char *file, int line); @@ -391,6 +395,9 @@ struct redisServer { off_t vm_page_size; off_t vm_pages; unsigned long long vm_max_memory; + /* Hashes config */ + size_t hash_max_zipmap_entries; + size_t hash_max_zipmap_value; /* Virtual memory state */ FILE *vm_fp; int vm_fd; @@ -583,6 +590,7 @@ static void readQueryFromClient(aeEventLoop *el, int fd, void *privdata, int mas static struct redisCommand *lookupCommand(char *name); static void call(redisClient *c, struct redisCommand *cmd); static void resetClient(redisClient *c); +static void convertToRealHash(robj *o); static void authCommand(redisClient *c); static void pingCommand(redisClient *c); @@ -1467,6 +1475,8 @@ static void initServerConfig() { server.vm_max_memory = 1024LL*1024*1024*1; /* 1 GB of RAM */ server.vm_max_threads = 4; server.vm_blocked_clients = 0; + server.hash_max_zipmap_entries = REDIS_HASH_MAX_ZIPMAP_ENTRIES; + server.hash_max_zipmap_value = REDIS_HASH_MAX_ZIPMAP_VALUE; resetServerSaveParams(); @@ -1727,6 +1737,12 @@ static void loadServerConfig(char *filename) { server.vm_pages = strtoll(argv[1], NULL, 10); } else if (!strcasecmp(argv[0],"vm-max-threads") && argc == 2) { server.vm_max_threads = strtoll(argv[1], NULL, 10); + } else if (!strcasecmp(argv[0],"hash-max-zipmap-entries") && argc == 2){ + server.hash_max_zipmap_entries = strtol(argv[1], NULL, 10); + } else if (!strcasecmp(argv[0],"hash-max-zipmap-value") && argc == 2){ + server.hash_max_zipmap_value = strtol(argv[1], NULL, 10); + } else if (!strcasecmp(argv[0],"vm-max-threads") && argc == 2) { + server.vm_max_threads = strtoll(argv[1], NULL, 10); } else { err = "Bad directive or wrong number of arguments"; goto loaderr; } @@ -2605,7 +2621,17 @@ static void freeZsetObject(robj *o) { } static void freeHashObject(robj *o) { - dictRelease((dict*) o->ptr); + switch (o->encoding) { + case REDIS_ENCODING_HT: + dictRelease((dict*) o->ptr); + break; + case REDIS_ENCODING_ZIPMAP: + zfree(o->ptr); + break; + default: + redisAssert(0); + break; + } } static void incrRefCount(robj *o) { @@ -2910,7 +2936,7 @@ static int rdbSaveLen(FILE *fp, uint32_t len) { /* String objects in the form "2391" "-100" without any space and with a * range of values that can fit in an 8, 16 or 32 bit signed value can be * encoded as integers to save space */ -static int rdbTryIntegerEncoding(sds s, unsigned char *enc) { +static int rdbTryIntegerEncoding(char *s, size_t len, unsigned char *enc) { long long value; char *endptr, buf[32]; @@ -2921,7 +2947,7 @@ static int rdbTryIntegerEncoding(sds s, unsigned char *enc) { /* If the number converted back into a string is not identical * then it's not possible to encode the string as integer */ - if (strlen(buf) != sdslen(s) || memcmp(buf,s,sdslen(s))) return 0; + if (strlen(buf) != len || memcmp(buf,s,len)) return 0; /* Finally check if it fits in our ranges */ if (value >= -(1<<7) && value <= (1<<7)-1) { @@ -2945,16 +2971,16 @@ static int rdbTryIntegerEncoding(sds s, unsigned char *enc) { } } -static int rdbSaveLzfStringObject(FILE *fp, robj *obj) { - unsigned int comprlen, outlen; +static int rdbSaveLzfStringObject(FILE *fp, unsigned char *s, size_t len) { + size_t comprlen, outlen; unsigned char byte; void *out; /* We require at least four bytes compression for this to be worth it */ - outlen = sdslen(obj->ptr)-4; - if (outlen <= 0) return 0; + if (len <= 4) return 0; + outlen = len-4; if ((out = zmalloc(outlen+1)) == NULL) return 0; - comprlen = lzf_compress(obj->ptr, sdslen(obj->ptr), out, outlen); + comprlen = lzf_compress(s, len, out, outlen); if (comprlen == 0) { zfree(out); return 0; @@ -2963,7 +2989,7 @@ static int rdbSaveLzfStringObject(FILE *fp, robj *obj) { byte = (REDIS_RDB_ENCVAL<<6)|REDIS_RDB_ENC_LZF; if (fwrite(&byte,1,1,fp) == 0) goto writeerr; if (rdbSaveLen(fp,comprlen) == -1) goto writeerr; - if (rdbSaveLen(fp,sdslen(obj->ptr)) == -1) goto writeerr; + if (rdbSaveLen(fp,len) == -1) goto writeerr; if (fwrite(out,comprlen,1,fp) == 0) goto writeerr; zfree(out); return comprlen; @@ -2975,16 +3001,13 @@ writeerr: /* Save a string objet as [len][data] on disk. If the object is a string * representation of an integer value we try to safe it in a special form */ -static int rdbSaveStringObjectRaw(FILE *fp, robj *obj) { - size_t len; +static int rdbSaveRawString(FILE *fp, unsigned char *s, size_t len) { int enclen; - len = sdslen(obj->ptr); - /* Try integer encoding */ if (len <= 11) { unsigned char buf[5]; - if ((enclen = rdbTryIntegerEncoding(obj->ptr,buf)) > 0) { + if ((enclen = rdbTryIntegerEncoding((char*)s,len,buf)) > 0) { if (fwrite(buf,enclen,1,fp) == 0) return -1; return 0; } @@ -2995,7 +3018,7 @@ static int rdbSaveStringObjectRaw(FILE *fp, robj *obj) { if (server.rdbcompression && len > 20) { int retval; - retval = rdbSaveLzfStringObject(fp,obj); + retval = rdbSaveLzfStringObject(fp,s,len); if (retval == -1) return -1; if (retval > 0) return 0; /* retval == 0 means data can't be compressed, save the old way */ @@ -3003,7 +3026,7 @@ static int rdbSaveStringObjectRaw(FILE *fp, robj *obj) { /* Store verbatim */ if (rdbSaveLen(fp,len) == -1) return -1; - if (len && fwrite(obj->ptr,len,1,fp) == 0) return -1; + if (len && fwrite(s,len,1,fp) == 0) return -1; return 0; } @@ -3018,10 +3041,10 @@ static int rdbSaveStringObject(FILE *fp, robj *obj) { * this in order to avoid bugs) */ if (obj->encoding != REDIS_ENCODING_RAW) { obj = getDecodedObject(obj); - retval = rdbSaveStringObjectRaw(fp,obj); + retval = rdbSaveRawString(fp,obj->ptr,sdslen(obj->ptr)); decrRefCount(obj); } else { - retval = rdbSaveStringObjectRaw(fp,obj); + retval = rdbSaveRawString(fp,obj->ptr,sdslen(obj->ptr)); } return retval; } @@ -3099,6 +3122,33 @@ static int rdbSaveObject(FILE *fp, robj *o) { if (rdbSaveDoubleValue(fp,*score) == -1) return -1; } dictReleaseIterator(di); + } else if (o->type == REDIS_HASH) { + /* Save a hash value */ + if (o->encoding == REDIS_ENCODING_ZIPMAP) { + unsigned char *p = zipmapRewind(o->ptr); + unsigned int count = zipmapLen(o->ptr); + unsigned char *key, *val; + unsigned int klen, vlen; + + if (rdbSaveLen(fp,count) == -1) return -1; + while((p = zipmapNext(p,&key,&klen,&val,&vlen)) != NULL) { + if (rdbSaveRawString(fp,key,klen) == -1) return -1; + if (rdbSaveRawString(fp,val,vlen) == -1) return -1; + } + } else { + dictIterator *di = dictGetIterator(o->ptr); + dictEntry *de; + + if (rdbSaveLen(fp,dictSize((dict*)o->ptr)) == -1) return -1; + while((de = dictNext(di)) != NULL) { + robj *key = dictGetEntryKey(de); + robj *val = dictGetEntryVal(de); + + if (rdbSaveStringObject(fp,key) == -1) return -1; + if (rdbSaveStringObject(fp,val) == -1) return -1; + } + dictReleaseIterator(di); + } } else { redisAssert(0 != 0); } @@ -3423,7 +3473,7 @@ static robj *rdbLoadObject(int type, FILE *fp) { } } else if (type == REDIS_ZSET) { /* Read list/set value */ - uint32_t zsetlen; + size_t zsetlen; zset *zs; if ((zsetlen = rdbLoadLen(fp,NULL)) == REDIS_RDB_LENERR) return NULL; @@ -3441,6 +3491,46 @@ static robj *rdbLoadObject(int type, FILE *fp) { zslInsert(zs->zsl,*score,ele); incrRefCount(ele); /* added to skiplist */ } + } else if (type == REDIS_HASH) { + size_t hashlen; + + if ((hashlen = rdbLoadLen(fp,NULL)) == REDIS_RDB_LENERR) return NULL; + o = createHashObject(); + /* Too many entries? Use an hash table. */ + if (hashlen > server.hash_max_zipmap_entries) + convertToRealHash(o); + /* Load every key/value, then set it into the zipmap or hash + * table, as needed. */ + while(hashlen--) { + robj *key, *val; + + if ((key = rdbLoadStringObject(fp)) == NULL) return NULL; + if ((val = rdbLoadStringObject(fp)) == NULL) return NULL; + /* If we are using a zipmap and there are too big values + * the object is converted to real hash table encoding. */ + if (o->encoding != REDIS_ENCODING_HT && + (sdslen(key->ptr) > server.hash_max_zipmap_value || + sdslen(val->ptr) > server.hash_max_zipmap_value)) + { + convertToRealHash(o); + } + + if (o->encoding == REDIS_ENCODING_ZIPMAP) { + unsigned char *zm = o->ptr; + + zm = zipmapSet(zm,key->ptr,sdslen(key->ptr), + val->ptr,sdslen(val->ptr),NULL); + o->ptr = zm; + decrRefCount(key); + decrRefCount(val); + } else { + tryObjectEncoding(key); + tryObjectEncoding(val); + dictAdd((dict*)o->ptr,key,val); + incrRefCount(key); + incrRefCount(val); + } + } } else { redisAssert(0 != 0); } @@ -3948,7 +4038,8 @@ static void typeCommand(redisClient *c) { case REDIS_LIST: type = "+list"; break; case REDIS_SET: type = "+set"; break; case REDIS_ZSET: type = "+zset"; break; - default: type = "unknown"; break; + case REDIS_HASH: type = "+hash"; break; + default: type = "+unknown"; break; } } addReplySds(c,sdsnew(type)); @@ -5591,7 +5682,7 @@ static void zrevrankCommand(redisClient *c) { zrankGenericCommand(c, 1); } -/* ==================================== Hash ================================ */ +/* =================================== Hashes =============================== */ static void hsetCommand(redisClient *c) { int update = 0; robj *o = lookupKeyWrite(c->db,c->argv[1]); @@ -5608,9 +5699,12 @@ static void hsetCommand(redisClient *c) { } if (o->encoding == REDIS_ENCODING_ZIPMAP) { unsigned char *zm = o->ptr; + robj *valobj = getDecodedObject(c->argv[3]); zm = zipmapSet(zm,c->argv[2]->ptr,sdslen(c->argv[2]->ptr), - c->argv[3]->ptr,sdslen(c->argv[3]->ptr),&update); + valobj->ptr,sdslen(valobj->ptr),&update); + decrRefCount(valobj); + o->ptr = zm; } else { if (dictAdd(o->ptr,c->argv[2],c->argv[3]) == DICT_OK) { incrRefCount(c->argv[2]); @@ -5661,6 +5755,27 @@ static void hgetCommand(redisClient *c) { } } +static void convertToRealHash(robj *o) { + unsigned char *key, *val, *p, *zm = o->ptr; + unsigned int klen, vlen; + dict *dict = dictCreate(&hashDictType,NULL); + + assert(o->type == REDIS_HASH && o->encoding != REDIS_ENCODING_HT); + p = zipmapRewind(zm); + while((p = zipmapNext(p,&key,&klen,&val,&vlen)) != NULL) { + robj *keyobj, *valobj; + + keyobj = createStringObject((char*)key,klen); + valobj = createStringObject((char*)val,vlen); + tryObjectEncoding(keyobj); + tryObjectEncoding(valobj); + dictAdd(dict,keyobj,valobj); + } + o->encoding = REDIS_ENCODING_HT; + o->ptr = dict; + zfree(zm); +} + /* ========================= Non type-specific commands ==================== */ static void flushdbCommand(redisClient *c) { diff --git a/redis.conf b/redis.conf index 2923a3aa..0ed593d2 100644 --- a/redis.conf +++ b/redis.conf @@ -271,3 +271,10 @@ glueoutputbuf yes # your development environment so that we can test it better. shareobjects no shareobjectspoolsize 1024 + +# Hashes are encoded in a special way (much more memory efficient) when they +# have at max a given numer of elements, and the biggest element does not +# exceed a given threshold. You can configure this limits with the following +# configuration directives. +hash-max-zipmap-entries 64 +hash-max-zipmap-value 512 diff --git a/staticsymbols.h b/staticsymbols.h index 446a5dc4..85f07d32 100644 --- a/staticsymbols.h +++ b/staticsymbols.h @@ -5,8 +5,10 @@ static struct redisFunctionSym symsTable[] = { {"addReply",(unsigned long)addReply}, {"addReplyBulkLen",(unsigned long)addReplyBulkLen}, {"addReplyDouble",(unsigned long)addReplyDouble}, +{"addReplyLong",(unsigned long)addReplyLong}, {"addReplySds",(unsigned long)addReplySds}, {"aofRemoveTempFile",(unsigned long)aofRemoveTempFile}, +{"appendCommand",(unsigned long)appendCommand}, {"appendServerSaveParams",(unsigned long)appendServerSaveParams}, {"authCommand",(unsigned long)authCommand}, {"beforeSleep",(unsigned long)beforeSleep}, @@ -23,6 +25,7 @@ static struct redisFunctionSym symsTable[] = { {"compareStringObjects",(unsigned long)compareStringObjects}, {"computeObjectSwappability",(unsigned long)computeObjectSwappability}, {"createClient",(unsigned long)createClient}, +{"createHashObject",(unsigned long)createHashObject}, {"createListObject",(unsigned long)createListObject}, {"createObject",(unsigned long)createObject}, {"createSetObject",(unsigned long)createSetObject}, @@ -45,6 +48,7 @@ static struct redisFunctionSym symsTable[] = { {"dictObjKeyCompare",(unsigned long)dictObjKeyCompare}, {"dictRedisObjectDestructor",(unsigned long)dictRedisObjectDestructor}, {"dictVanillaFree",(unsigned long)dictVanillaFree}, +{"discardCommand",(unsigned long)discardCommand}, {"dontWaitForSwappedKey",(unsigned long)dontWaitForSwappedKey}, {"dupClientReplyValue",(unsigned long)dupClientReplyValue}, {"dupStringObject",(unsigned long)dupStringObject}, @@ -75,6 +79,7 @@ static struct redisFunctionSym symsTable[] = { {"fwriteBulkDouble",(unsigned long)fwriteBulkDouble}, {"fwriteBulkLong",(unsigned long)fwriteBulkLong}, {"genRedisInfoString",(unsigned long)genRedisInfoString}, +{"genericZrangebyscoreCommand",(unsigned long)genericZrangebyscoreCommand}, {"getCommand",(unsigned long)getCommand}, {"getDecodedObject",(unsigned long)getDecodedObject}, {"getExpire",(unsigned long)getExpire}, @@ -84,6 +89,8 @@ static struct redisFunctionSym symsTable[] = { {"glueReplyBuffersIfNeeded",(unsigned long)glueReplyBuffersIfNeeded}, {"handleClientsBlockedOnSwappedKey",(unsigned long)handleClientsBlockedOnSwappedKey}, {"handleClientsWaitingListPush",(unsigned long)handleClientsWaitingListPush}, +{"hgetCommand",(unsigned long)hgetCommand}, +{"hsetCommand",(unsigned long)hsetCommand}, {"htNeedsResize",(unsigned long)htNeedsResize}, {"incrCommand",(unsigned long)incrCommand}, {"incrDecrCommand",(unsigned long)incrDecrCommand}, @@ -143,8 +150,8 @@ static struct redisFunctionSym symsTable[] = { {"rdbSaveLen",(unsigned long)rdbSaveLen}, {"rdbSaveLzfStringObject",(unsigned long)rdbSaveLzfStringObject}, {"rdbSaveObject",(unsigned long)rdbSaveObject}, +{"rdbSaveRawString",(unsigned long)rdbSaveRawString}, {"rdbSaveStringObject",(unsigned long)rdbSaveStringObject}, -{"rdbSaveStringObjectRaw",(unsigned long)rdbSaveStringObjectRaw}, {"rdbSaveTime",(unsigned long)rdbSaveTime}, {"rdbSaveType",(unsigned long)rdbSaveType}, {"rdbSavedObjectLen",(unsigned long)rdbSavedObjectLen}, @@ -196,6 +203,7 @@ static struct redisFunctionSym symsTable[] = { {"srandmemberCommand",(unsigned long)srandmemberCommand}, {"sremCommand",(unsigned long)sremCommand}, {"stringObjectLen",(unsigned long)stringObjectLen}, +{"substrCommand",(unsigned long)substrCommand}, {"sunionCommand",(unsigned long)sunionCommand}, {"sunionDiffGenericCommand",(unsigned long)sunionDiffGenericCommand}, {"sunionstoreCommand",(unsigned long)sunionstoreCommand}, @@ -240,10 +248,12 @@ static struct redisFunctionSym symsTable[] = { {"zaddCommand",(unsigned long)zaddCommand}, {"zaddGenericCommand",(unsigned long)zaddGenericCommand}, {"zcardCommand",(unsigned long)zcardCommand}, +{"zcountCommand",(unsigned long)zcountCommand}, {"zincrbyCommand",(unsigned long)zincrbyCommand}, {"zrangeCommand",(unsigned long)zrangeCommand}, {"zrangeGenericCommand",(unsigned long)zrangeGenericCommand}, {"zrangebyscoreCommand",(unsigned long)zrangebyscoreCommand}, +{"zrankCommand",(unsigned long)zrankCommand}, {"zremCommand",(unsigned long)zremCommand}, {"zremrangebyscoreCommand",(unsigned long)zremrangebyscoreCommand}, {"zrevrangeCommand",(unsigned long)zrevrangeCommand}, diff --git a/zipmap.c b/zipmap.c index 05bf6d6d..5f024dfa 100644 --- a/zipmap.c +++ b/zipmap.c @@ -363,6 +363,15 @@ int zipmapExists(unsigned char *zm, unsigned char *key, unsigned int klen) { return zipmapLookupRaw(zm,key,klen,NULL,NULL,NULL) != NULL; } +/* Return the number of entries inside a zipmap */ +unsigned int zipmapLen(unsigned char *zm) { + unsigned char *p = zipmapRewind(zm); + unsigned int len = 0; + + while((p = zipmapNext(p,NULL,NULL,NULL,NULL)) != NULL) len++; + return len; +} + void zipmapRepr(unsigned char *p) { unsigned int l; @@ -405,6 +414,13 @@ int main(void) { unsigned char *zm; zm = zipmapNew(); + + zm = zipmapSet(zm,(unsigned char*) "name",4, (unsigned char*) "foo",3,NULL); + zm = zipmapSet(zm,(unsigned char*) "surname",7, (unsigned char*) "foo",3,NULL); + zm = zipmapSet(zm,(unsigned char*) "age",3, (unsigned char*) "foo",3,NULL); + zipmapRepr(zm); + exit(1); + zm = zipmapSet(zm,(unsigned char*) "hello",5, (unsigned char*) "world!",6,NULL); zm = zipmapSet(zm,(unsigned char*) "foo",3, (unsigned char*) "bar",3,NULL); zm = zipmapSet(zm,(unsigned char*) "foo",3, (unsigned char*) "!",1,NULL); diff --git a/zipmap.h b/zipmap.h index bf65740c..089472ed 100644 --- a/zipmap.h +++ b/zipmap.h @@ -42,5 +42,6 @@ unsigned char *zipmapRewind(unsigned char *zm); unsigned char *zipmapNext(unsigned char *zm, unsigned char **key, unsigned int *klen, unsigned char **value, unsigned int *vlen); int zipmapGet(unsigned char *zm, unsigned char *key, unsigned int klen, unsigned char **value, unsigned int *vlen); int zipmapExists(unsigned char *zm, unsigned char *key, unsigned int klen); +unsigned int zipmapLen(unsigned char *zm); #endif