ItGo.me - 专注IT技术分享

首页 > Redis > Redis源码分析(十八)——排序Sort

Redis源码分析(十八)——排序Sort

时间:2016-08-28来源:网友分享 点击:

Redis的排序命令SORT: 将给定的列表 或集合或 有序集的键的元素对应到一个数组中去,然后按给定选项排序,然后返回排序后的元素值;或者将排序后的元素保存到一个给定的键,并存入数据库字典中,返回所保存的元素个数。

具体排序命令用法可参考:

其中数组的元素为结构:

typedef struct _redisSortObject {robj *obj;//被排序的键的值//权重union {double score;//给数值排序时使用robj *cmpobj;// 排序带有 BY 选项的字符串值时使用(当 SORT 命令使用了 BY 选项时, 命令使用其他键的值作为权重来进行排序操作)} u;} redisSortObject;//排序数值元素 结构
排序前,将给定键的元素的redisSortObject结构对应到数组中去,如图一:


而排序后,如图二:



排序命令的实现步骤:

*1*创建一个和给定键值长度相同的数组,该数组的每个项都是redisSortObject结构

*2*遍历数组,将数组的每个项的obj指针分别指向给定键的各个值,使数组与键值列表(以列表为例)构成一对一。

*3*遍历数组,将各个obj指针所指的列表元素转换成一个double类型(或者字符串,与给定选项相关),并将给浮点数保存到obj的u.score中。如上图1所示。

*4*根据u.score(与给定选项相关:排序比较的权值不一样)的值,对数值进行排序(按升序或降序改变obj指针指向的类表元素)。如上图二所示。

*5*遍历数组,将各个obj指向的列表项作为排序的结果返回给客户端。或者将排序结构存放到给定键的值中,并将该键值存入数据库。


排序命令函数:

排序时采用快速排序算法。该函数是Redis中最复杂的函数,实现了上面的五个处理步骤。先了解排序命令的基本用法,有助于更好的理解该命令的实现过程。其中 比如在处理有序集排序时的优化处理等。

(其中快速排序基本实现参考:)

<span style="font-size:18px;">void sortCommand(redisClient *c) {list *operations;//操作链表unsigned int outputlen = 0;//要回复的元素个数int desc = 0, alpha = 0;long limit_start = 0, limit_count = -1, start, end;int j, dontsort = 0, vectorlen;int getop = 0; /* GET操作计数 GET operation counter */int int_convertion_error = 0;int syntax_error = 0;robj *sortval, *sortby = NULL, *storekey = NULL;redisSortObject *vector; /* Resulting vector to sort *//* Lookup the key to sort. It must be of the right types */// 获取要排序的键,并检查他是否可以被排序的类型sortval = lookupKeyRead(c->db,c->argv[1]);if (sortval && sortval->type != REDIS_SET &&sortval->type != REDIS_LIST &&sortval->type != REDIS_ZSET){addReply(c,shared.wrongtypeerr);return;}/* Create a list of operations to perform for every sorted element.* Operations can be GET/DEL/INCR/DECR */// 创建一个链表,链表中保存了要对所有已排序元素执行的操作// 操作可以是 GET 、 DEL 、 INCR 或者 DECRoperations = listCreate();//操作链表listSetFreeMethod(operations,zfree);// 指向选项参数位置j = 2; /* options start at argv[2] *//* Now we need to protect sortval incrementing its count, in the future* SORT may have options able to overwrite/delete keys during the sorting* and the sorted key itself may get destroyed */// 为 sortval 的引用计数增一// 在将来, SORT 命令可以在排序某个键的过程中,覆盖或者删除那个键if (sortval)incrRefCount(sortval);elsesortval = createListObject();/* The SORT command has an SQL-alike syntax, parse it */// 读入并分析 SORT 命令的选项while(j < c->argc) {int leftargs = c->argc-j-1;// ASC 选项   升序if (!strcasecmp(c->argv[j]->ptr,"asc")) {desc = 0;// DESC 选项   降序对比来比较被排序的元素} else if (!strcasecmp(c->argv[j]->ptr,"desc")) {desc = 1;// ALPHA 选项  假设被排序键包含的都是字符串值, 并且以字符串的方式来进行排序} else if (!strcasecmp(c->argv[j]->ptr,"alpha")) {alpha = 1;// LIMIT 选项    命令只保留排序结果集中 LIMIT 选项指定的元素} else if (!strcasecmp(c->argv[j]->ptr,"limit") && leftargs >= 2) {// start 参数和 count 参数if ((getLongFromObjectOrReply(c, c->argv[j+1], &limit_start, NULL)!= REDIS_OK) ||(getLongFromObjectOrReply(c, c->argv[j+2], &limit_count, NULL)!= REDIS_OK)){syntax_error++;break;}j+=2;// STORE 选项  命令会将排序结果集保存在指定的键里面} else if (!strcasecmp(c->argv[j]->ptr,"store") && leftargs >= 1) {// 目标键storekey = c->argv[j+1];j++;// BY 选项    命令使用其他键的值作为权重来进行排序操作} else if (!strcasecmp(c->argv[j]->ptr,"by") && leftargs >= 1) {// 排序的顺序由这个模式决定sortby = c->argv[j+1];/* If the BY pattern does not contain '*', i.e. it is constant,* we don't need to sort nor to lookup the weight keys. */// 如果 sortby 模式里面不包含 '*' 符号,// 那么无须执行排序操作if (strchr(c->argv[j+1]->ptr,'*') == NULL) {dontsort = 1;} else {/* If BY is specified with a real patter, we can't accept* it in cluster mode. */if (server.cluster_enabled) {addReplyError(c,"BY option of SORT denied in Cluster mode.");syntax_error++;break;}}j++;// GET 选项    命令会根据排序结果集中的元素, 以及 GET 选项给定的模式,//查找并返回其他键的值, 而不是返回被排序的元素。} else if (!strcasecmp(c->argv[j]->ptr,"get") && leftargs >= 1) {// 创建一个 GET 操作// 不能在集群模式下使用 GET 选项if (server.cluster_enabled) {addReplyError(c,"GET option of SORT denied in Cluster mode.");syntax_error++;break;}listAddNodeTail(operations,createSortOperation(REDIS_SORT_GET,c->argv[j+1]));getop++;j++;// 未知选项,语法出错} else {addReply(c,shared.syntaxerr);syntax_error++;break;}j++;}/* Handle syntax errors set during options parsing. */if (syntax_error) {decrRefCount(sortval);listRelease(operations);return;}/* For the STORE option, or when SORT is called from a Lua script,* we want to force a specific ordering even when no explicit ordering* was asked (SORT BY nosort). This guarantees that replication / AOF* is deterministic.** 对于 STORE 选项,以及从 Lua 脚本中调用 SORT 命令的情况来看,* 我们想即使在没有指定排序方式的情况下,也强制指定一个排序方法。* 这可以保证复制/AOF 是确定性的。** However in the case 'dontsort' is true, but the type to sort is a* sorted set, we don't need to do anything as ordering is guaranteed* in this special case.** 在 dontsort 为真,并且被排序的键不是有序集合时,* 我们才需要为排序指定排序方式,* 因为有序集合的成员已经是有序的了。*/if ((storekey || c->flags & REDIS_LUA_CLIENT) &&(dontsort && sortval->type != REDIS_ZSET)){/* Force ALPHA sorting */// 强制 ALPHA 排序dontsort = 0;alpha = 1;sortby = NULL;}/* Destructively convert encoded sorted sets for SORT. */// 被排序的有序集合必须是 SKIPLIST 编码的// 如果不是的话,那么将它转换成 SKIPLIST 编码if (sortval->type == REDIS_ZSET)zsetConvert(sortval, REDIS_ENCODING_SKIPLIST);/* Objtain the length of the object to sort. */// 获取要排序对象的长度switch(sortval->type) {case REDIS_LIST: vectorlen = listTypeLength(sortval); break;case REDIS_SET: vectorlen =  setTypeSize(sortval); break;case REDIS_ZSET: vectorlen = dictSize(((zset*)sortval->ptr)->dict); break;default: vectorlen = 0; redisPanic("Bad SORT type"); /* Avoid GCC warning */}/* Perform LIMIT start,count sanity checking. */// 对 LIMIT 选项的 start 和 count 参数进行检查start = (limit_start < 0) ? 0 : limit_start;end = (limit_count < 0) ? vectorlen-1 : start+limit_count-1;if (start >= vectorlen) {start = vectorlen-1;end = vectorlen-2;}if (end >= vectorlen) end = vectorlen-1;/* Optimization:* 优化** 1) if the object to sort is a sorted set.*    如果排序的对象是有序集合* 2) There is nothing to sort as dontsort is true (BY <constant string>).*  dontsort 为真,表示没有什么需要排序* 3) We have a LIMIT option that actually reduces the number of elements*    to fetch.*  LIMIT 选项所设置的范围比起有序集合的长度要小** In this case to load all the objects in the vector is a huge waste of* resources. We just allocate a vector that is big enough for the selected* range length, and make sure to load just this part in the vector.** 在这种情况下,不需要载入有序集合中的所有元素,只要载入给定范围(range)内的元素就可以了。*/if (sortval->type == REDIS_ZSET &&dontsort &&(start != 0 || end != vectorlen-1)){vectorlen = end-start+1;}/* Load the sorting vector with all the objects to sort */// 创建 redisSortObject 数组vector = zmalloc(sizeof(redisSortObject)*vectorlen);//只需分配需要返回的元素的个数所需的空间j = 0;// 将列表项放入数组if (sortval->type == REDIS_LIST) {listTypeIterator *li = listTypeInitIterator(sortval,0,REDIS_TAIL);listTypeEntry entry;while(listTypeNext(li,&entry)) {vector[j].obj = listTypeGet(&entry);vector[j].u.score = 0;vector[j].u.cmpobj = NULL;j++;}listTypeReleaseIterator(li);// 将集合元素放入数组} else if (sortval->type == REDIS_SET) {setTypeIterator *si = setTypeInitIterator(sortval);robj *ele;while((ele = setTypeNextObject(si)) != NULL) {vector[j].obj = ele;vector[j].u.score = 0;vector[j].u.cmpobj = NULL;j++;}setTypeReleaseIterator(si);// 在 dontsort 为真的情况下// 将有序集合的部分成员放进数组} else if (sortval->type == REDIS_ZSET && dontsort) {/* Special handling for a sorted set, if 'dontsort' is true.* This makes sure we return elements in the sorted set original* ordering, accordingly to DESC / ASC options.** Note that in this case we also handle LIMIT here in a direct* way, just getting the required range, as an optimization. */// 这是前面说过的,可以进行优化的 casezset *zs = sortval->ptr;zskiplist *zsl = zs->zsl;zskiplistNode *ln;robj *ele;int rangelen = vectorlen;/* Check if starting point is trivial, before doing log(N) lookup. */// 根据 desc 或者 asc 排序,指向初始节点if (desc) {long zsetlen = dictSize(((zset*)sortval->ptr)->dict);ln = zsl->tail;if (start > 0)ln = zslGetElementByRank(zsl,zsetlen-start);} else {ln = zsl->header->level[0].forward;if (start > 0)ln = zslGetElementByRank(zsl,start+1);}// 遍历范围中的所有节点,并放进数组while(rangelen--) {redisAssertWithInfo(c,sortval,ln != NULL);ele = ln->obj;vector[j].obj = ele;vector[j].u.score = 0;vector[j].u.cmpobj = NULL;j++;ln = desc ? ln->backward : ln->level[0].forward;}/* The code producing the output does not know that in the case of* sorted set, 'dontsort', and LIMIT, we are able to get just the* range, already sorted, so we need to adjust "start" and "end"* to make sure start is set to 0. */end -= start;start = 0;// 普通情况下的有序集合,将所有集合成员放进数组} else if (sortval->type == REDIS_ZSET) {dict *set = ((zset*)sortval->ptr)->dict;dictIterator *di;dictEntry *setele;di = dictGetIterator(set);while((setele = dictNext(di)) != NULL) {vector[j].obj = dictGetKey(setele);vector[j].u.score = 0;vector[j].u.cmpobj = NULL;j++;}dictReleaseIterator(di);} else {redisPanic("Unknown type");}redisAssertWithInfo(c,sortval,j == vectorlen);/* Now it's time to load the right scores in the sorting vector */// 载入权重值if (dontsort == 0) {for (j = 0; j < vectorlen; j++) {robj *byval;// 如果使用了 BY 选项,那么就根据指定的对象作为权重if (sortby) {/* lookup value to sort by */byval = lookupKeyByPattern(c->db,sortby,vector[j].obj);if (!byval) continue;// 如果没有使用 BY 选项,那么使用对象本身作为权重} else {/* use object itself to sort by */byval = vector[j].obj;}// 如果是 ALPHA 排序,那么将对比对象改为解码后的 byvalif (alpha) {if (sortby) vector[j].u.cmpobj = getDecodedObject(byval);// 否则,将字符串对象转换成 double 类型} else {if (sdsEncodedObject(byval)) {char *eptr;// 将字符串转换成 double 类型vector[j].u.score = strtod(byval->ptr,&eptr);if (eptr[0] != '\0' || errno == ERANGE ||isnan(vector[j].u.score)){int_convertion_error = 1;}} else if (byval->encoding == REDIS_ENCODING_INT) {/* Don't need to decode the object if it's* integer-encoded (the only encoding supported) so* far. We can just cast it */// 直接将整数设置为权重vector[j].u.score = (long)byval->ptr;} else {redisAssertWithInfo(c,sortval,1 != 1);}}/* when the object was retrieved using lookupKeyByPattern,* its refcount needs to be decreased. */if (sortby) {decrRefCount(byval);}}}// 排序if (dontsort == 0) {server.sort_desc = desc;server.sort_alpha = alpha;server.sort_bypattern = sortby ? 1 : 0;server.sort_store = storekey ? 1 : 0;if (sortby && (start != 0 || end != vectorlen-1))pqsort(vector,vectorlen,sizeof(redisSortObject),sortCompare, start,end);elseqsort(vector,vectorlen,sizeof(redisSortObject),sortCompare);}/* Send command output to the output buffer, performing the specified* GET/DEL/INCR/DECR operations if any. */// 将命令的输出放到输出缓冲区// 然后执行给定的 GET / DEL / INCR 或 DECR 操作outputlen = getop ? getop*(end-start+1) : end-start+1;if (int_convertion_error) {addReplyError(c,"One or more scores can't be converted into double");} else if (storekey == NULL) {/* STORE option not specified, sent the sorting result to client */// STORE 选项未使用,直接将排序结果发送给客户端addReplyMultiBulkLen(c,outputlen);for (j = start; j <= end; j++) {listNode *ln;listIter li;// 没有设置 GET 选项,直接将结果添加到回复if (!getop) addReplyBulk(c,vector[j].obj);// 有设置 GET 选项。。。// 遍历设置的操作listRewind(operations,&li);while((ln = listNext(&li))) {redisSortOperation *sop = ln->value;// 解释并查找键robj *val = lookupKeyByPattern(c->db,sop->pattern,vector[j].obj);// 执行 GET 操作,将指定键的值添加到回复if (sop->type == REDIS_SORT_GET) {if (!val) {addReply(c,shared.nullbulk);} else {addReplyBulk(c,val);decrRefCount(val);}// DEL 、INCR 和 DECR 操作都尚未实现} else {/* Always fails */redisAssertWithInfo(c,sortval,sop->type == REDIS_SORT_GET);}}}} else {robj *sobj = createZiplistObject();/* STORE option specified, set the sorting result as a List object */// 已设置 STORE 选项,将排序结果保存到列表对象for (j = start; j <= end; j++) {listNode *ln;listIter li;// 没有 GET ,直接返回排序元素if (!getop) {listTypePush(sobj,vector[j].obj,REDIS_TAIL);// 有 GET ,获取指定的键} else {listRewind(operations,&li);while((ln = listNext(&li))) {redisSortOperation *sop = ln->value;robj *val = lookupKeyByPattern(c->db,sop->pattern,vector[j].obj);if (sop->type == REDIS_SORT_GET) {if (!val) val = createStringObject("",0);/* listTypePush does an incrRefCount, so we should take care* care of the incremented refcount caused by either* lookupKeyByPattern or createStringObject("",0) */listTypePush(sobj,val,REDIS_TAIL);decrRefCount(val);} else {/* Always fails */redisAssertWithInfo(c,sortval,sop->type == REDIS_SORT_GET);}}}}// 如果排序结果不为空,那么将结果列表关联到数据库键,并发送事件if (outputlen) {setKey(c->db,storekey,sobj);notifyKeyspaceEvent(REDIS_NOTIFY_LIST,"sortstore",storekey,c->db->id);server.dirty += outputlen;// 如果排序结果为空,那么只要删除 storekey 就可以了,因为没有结果可以保存} else if (dbDelete(c->db,storekey)) {signalModifiedKey(c->db,storekey);notifyKeyspaceEvent(REDIS_NOTIFY_GENERIC,"del",storekey,c->db->id);server.dirty++;}decrRefCount(sobj);addReplyLongLong(c,outputlen);}/* Cleanup */if (sortval->type == REDIS_LIST || sortval->type == REDIS_SET)for (j = 0; j < vectorlen; j++)decrRefCount(vector[j].obj);decrRefCount(sortval);listRelease(operations);for (j = 0; j < vectorlen; j++) {if (alpha && vector[j].u.cmpobj)decrRefCount(vector[j].u.cmpobj);}zfree(vector);}</span>










Redis源码分析(十八)——排序Sort

Redis源码分析(十八)——排序Sort  讨论


Flask+Nginx+Gunicorn+Redis+Mysql搭建一个小站

首先简单介绍一下这几个东东。 Flask是一个轻量级的Web应用框架, 基于Werkzeug和 Jinja2 模板引擎,使用 Python编写,可扩展强。 Nginx是一个高性能的 HTTP 和 反向代理服务器,在高并发方面表现非常...

redis 中文手册

https://redis.readthedocs.org/en/latest/ http://www.cnblogs.com/ikodota/archive/2012/03/05/php_redis_cn.html redis 中文手册 redis 中文手册 讨论...

一个 C++ redis 集群管理工具

集群版 redis3.0 发布以来,官方仅提供了一个使用 ruby 写的集群管理工具,在创建 redis 集群时需要使用该工具。因为 ruby 中的一些包依赖问题,导致一些生手在建立 redis 集群时吃尽了苦头。于...

Redis的排序命令SORT: 将给定的列表 或集合或 有序集的键的元素对应到一个数组中去,然后按给定选项排序,然后返回排序后的元素;或者将排序后的元素保存到一个给定的键,并存入数据库
------分隔线----------------------------