(九)— t_list,t_string的分析

最后更新于:2022-04-01 20:20:31

        今天我是看完了t_list和t_string的代码,从名字知道,这也是和之前的t_hash非常类似的,无非就是各种形式,转化来转化去的。先讲讲t_list,对比于昨天的t_hash,t_hash是ziplist和dict之间的转换,t_list则是描述的是ziplist压缩表和linedlist普通链表,换句话说,当client这个robj作为参数传入的时候,都分为ENCODING_ZIIPLIST和ENCODING_LINKEDLIST 2类编码方式处理。还有一个在t_list出现的一个 比较新颖的东西是出现了锁的概念,操作系统的东西在这里也会碰到了,这里的代码也非常值得学习。下面,我们看看一般的t_list中包括的一些方法和命令: ~~~ /* List方法 */ /* list的操作分为2种,LINKEDLIST普通链表和ZIPLIST压缩列表的相关操作 */ void listTypeTryConversion(robj *subject, robj *value) /* 判断是否需要将ziplist转为linkedlist */ void listTypePush(robj *subject, robj *value, int where) /* 在头部或尾部插入value元素 */ robj *listTypePop(robj *subject, int where) /* 在列表的头部或尾弹出元素 */ unsigned long listTypeLength(robj *subject) /* 列表的长度 */ listTypeIterator *listTypeInitIterator(robj *subject, long index, unsigned char direction) /* 返回列表迭代器,方向有头尾之分 */ void listTypeReleaseIterator(listTypeIterator *li) /* 释放列表迭代器 */ int listTypeNext(listTypeIterator *li, listTypeEntry *entry) /* 根据列表迭代器,获取下一个元素 */ robj *listTypeGet(listTypeEntry *entry) /* 获取listType元素,有ziplist和linkedlist */ void listTypeInsert(listTypeEntry *entry, robj *value, int where) /* listType了类型插入元素操作 */ int listTypeEqual(listTypeEntry *entry, robj *o) /* 判断2个元素是否相等 */ void listTypeDelete(listTypeEntry *entry) /* listType类型删除元素 */ void listTypeConvert(robj *subject, int enc) /* listType类型的转换操作,这里指的是往linkedList上转 */ /* List的相关命令 */ void pushGenericCommand(redisClient *c, int where) /* 插入操作命令的原始操作 */ void lpushCommand(redisClient *c) /* 左边插入元素命令 */ void rpushCommand(redisClient *c) /* 右边插入元素命令 */ void pushxGenericCommand(redisClient *c, robj *refval, robj *val, int where) /* 有返回状态的插入操作命令,假设首先都是能够实现插入命令的 */ void lpushxCommand(redisClient *c) /* 左边插入元素有返回消息的命令 */ void rpushxCommand(redisClient *c) /* 右边插入元素有返回消息的命令 */ void linsertCommand(redisClient *c) /* 列表指定位置插入元素操作命令 */ void llenCommand(redisClient *c) /* 列表返回长度命令 */ void lindexCommand(redisClient *c) /* 获取index位置的上的元素 */ void lsetCommand(redisClient *c) /* listType类型设置value命令 */ void popGenericCommand(redisClient *c, int where) /* 实现弹出操作的原始命令 */ void lpopCommand(redisClient *c) /* 左边弹出元素命令 */ void rpopCommand(redisClient *c) /* 右边弹出操作命令 */ void lrangeCommand(redisClient *c) /* 移动listType位置操作 */ void ltrimCommand(redisClient *c) /* listType实现截取操作,把多余范围的元素删除 */ void lremCommand(redisClient *c) /* 移除在listType中出现的与指定的元素相等的元素 */ void rpoplpushHandlePush(redisClient *c, robj *dstkey, robj *dstobj, robj *value) /* 元素从一个obj右边弹出,在从左侧推入另一个obj列表操作 */ void rpoplpushCommand(redisClient *c) /* 右边弹出,左边推入元素的命令 */ void blockForKeys(redisClient *c, robj **keys, int numkeys, time_t timeout, robj *target) >/* 设置客户端为阻塞模式,并设置超时时间,当请求特定的key元素时 */ void unblockClientWaitingData(redisClient *c) /* 客户端解锁操作 */ void signalListAsReady(redisDb *db, robj *key) /* 将key存入server中,后续可以用于客户端的存取 */ int serveClientBlockedOnList(redisClient *receiver, robj *key, robj *dstkey, redisDb *db, robj *value, int where) /* 根据server,Client的key,value情况,判断server此时能否服务于Client,否则Client将被阻塞 */ void handleClientsBlockedOnLists(void) /* 服务端解除阻塞住的Client */ int getTimeoutFromObjectOrReply(redisClient *c, robj *object, time_t *timeout) /* 获取超时时间 */ void blockingPopGenericCommand(redisClient *c, int where) /* 阻塞弹出命令的原始操作 */ void blpopCommand(redisClient *c) /* 左边弹出数据的阻塞式命令 */ void brpopCommand(redisClient *c) /* 右边弹出数据的阻塞式命令 */ void brpoplpushCommand(redisClient *c) /* 弹出推入阻塞式命令 */ ~~~ 看到这么多API,是否有被吓到的感觉,但里面其实很多的方法都很简单,我只挑几个比较典型的方法做一下分析,向什么返回长度了,获取,设置键值的大家可以自己看具体的方法,不难的。一般的t_list的处理流程,比如获取迭代器的方法: ~~~ /* Stores pointer to current the entry in the provided entry structure * and advances the position of the iterator. Returns 1 when the current * entry is in fact an entry, 0 otherwise. */ int listTypeNext(listTypeIterator *li, listTypeEntry *entry) { /* Protect from converting when iterating */ redisAssert(li->subject->encoding == li->encoding); entry->li = li; if (li->encoding == REDIS_ENCODING_ZIPLIST) { entry->zi = li->zi; if (entry->zi != NULL) { if (li->direction == REDIS_TAIL) //根据方向调用pre或next的方法 li->zi = ziplistNext(li->subject->ptr,li->zi); else li->zi = ziplistPrev(li->subject->ptr,li->zi); return 1; } } else if (li->encoding == REDIS_ENCODING_LINKEDLIST) { entry->ln = li->ln; if (entry->ln != NULL) { if (li->direction == REDIS_TAIL) //普通的列表的调用方式同上 li->ln = li->ln->next; else li->ln = li->ln->prev; return 1; } } else { redisPanic("Unknown list encoding"); } return 0; } ~~~ 很多API和t_hash的方法都是极其类似的,我就不多说了,我们将关注点,放在列表的锁控制上,先讲个前提,在redis客户端执行操作的时候,会有个请求超时时间,在这个请求的时间内,客户端如果没有找到key对应的数据,是会被阻塞的,什么意思呢,比如: ~~~ /* 设置客户端为阻塞模式,并设置超时时间,当请求特定的key元素时 */ /* 这个客户端阻塞的意思:当客户端请求list中某个特定key值时,如果key存在且列表非空,当然 */ /* 当然不会阻塞,正常返回数据,如果当客户端请求某个key不存在,或列表为empty的时候,客户端将被阻塞 */ /* 只有当有这个key被写入的时候,客户端才会被解锁 * ~~~ 这个其实就是操作系统中的PV操作类似的原理,跟java里的wait(),signal()方法的模型是一样的,他的实现代码如下: ~~~ /* This is how the current blocking POP works, we use BLPOP as example: * - If the user calls BLPOP and the key exists and contains a non empty list * then LPOP is called instead. So BLPOP is semantically the same as LPOP * if blocking is not required. * - If instead BLPOP is called and the key does not exists or the list is * empty we need to block. In order to do so we remove the notification for * new data to read in the client socket (so that we'll not serve new * requests if the blocking request is not served). Also we put the client * in a dictionary (db->blocking_keys) mapping keys to a list of clients * blocking for this keys. * - If a PUSH operation against a key with blocked clients waiting is * performed, we mark this key as "ready", and after the current command, * MULTI/EXEC block, or script, is executed, we serve all the clients waiting * for this list, from the one that blocked first, to the last, accordingly * to the number of elements we have in the ready list. */ /* Set a client in blocking mode for the specified key, with the specified * timeout */ /* 设置客户端为阻塞模式,并设置超时时间,当请求特定的key元素时 */ /* 这个客户端阻塞的意思:当客户端请求list中某个特定key值时,如果key存在且列表非空,当然 */ /* 当然不会阻塞,正常返回数据,如果当客户端请求某个key不存在,或列表为empty的时候,客户端将被阻塞 */ /* 只有当有这个key被写入的时候,客户端才会被解锁 */ void blockForKeys(redisClient *c, robj **keys, int numkeys, time_t timeout, robj *target) { dictEntry *de; list *l; int j; //设置超时时间 c->bpop.timeout = timeout; c->bpop.target = target; if (target != NULL) incrRefCount(target); for (j = 0; j < numkeys; j++) { //下面为为找到的key上锁 /* If the key already exists in the dict ignore it. */ //如果此时,某些key已经存在了,直接忽略 if (dictAdd(c->bpop.keys,keys[j],NULL) != DICT_OK) continue; incrRefCount(keys[j]); /* And in the other "side", to map keys -> clients */ //根据key找到对于请求该key的客户端,也就是将要被阻塞的Client de = dictFind(c->db->blocking_keys,keys[j]); if (de == NULL) { int retval; /* For every key we take a list of clients blocked for it */ l = listCreate(); //为c客户端添加一个阻塞的key retval = dictAdd(c->db->blocking_keys,keys[j],l); //增加key的引用次数 incrRefCount(keys[j]); redisAssertWithInfo(c,keys[j],retval == DICT_OK); } else { l = dictGetVal(de); } listAddNodeTail(l,c); } /* Mark the client as a blocked client */ /* 标记Client为阻塞的客户端 */ c->flags |= REDIS_BLOCKED; //服务端的阻塞客户端计数递增 server.bpop_blocked_clients++; } ~~~ 所有的key未来都会存在于server.readykeys里面,客户端判断自己所请求的key是否存在于服务端中的readykeys中,如果不存在就会被阻塞了。将key存入服务单的数据库的操作: ~~~ /* If the specified key has clients blocked waiting for list pushes, this * function will put the key reference into the server.ready_keys list. * Note that db->ready_keys is a hash table that allows us to avoid putting * the same key again and again in the list in case of multiple pushes * made by a script or in the context of MULTI/EXEC. * * The list will be finally processed by handleClientsBlockedOnLists() */ /* 将key存入server中,后续可以用于客户端的存取 */ void signalListAsReady(redisDb *db, robj *key) { readyList *rl; /* No clients blocking for this key? No need to queue it. */ /* 如果没有客户端为此key所阻塞的,直接不添加 */ if (dictFind(db->blocking_keys,key) == NULL) return; /* Key was already signaled? No need to queue it again. */ /* 如果key已经存在,不不要重复添加 */ if (dictFind(db->ready_keys,key) != NULL) return; /* Ok, we need to queue this key into server.ready_keys. */ rl = zmalloc(sizeof(*rl)); rl->key = key; rl->db = db; incrRefCount(key); //添加到list列表尾部 listAddNodeTail(server.ready_keys,rl); /* We also add the key in the db->ready_keys dictionary in order * to avoid adding it multiple times into a list with a simple O(1) * check. */ incrRefCount(key); redisAssert(dictAdd(db->ready_keys,key,NULL) == DICT_OK); } ~~~ 其实这里我不免会有个小问题,为什么list出现Client被阻塞的操作,而在t_hash中不会出现类似的操作呢?略疑惑。     下面说说t_string的用法,t_string里面没有涉及什么特定的结构体,就是最直接的键值对的设置,直接改变数据库中的键值,先列出里面的主要方法: ~~~ /* 方法 API */ static int checkStringLength(redisClient *c, long long size) /* 检查字符串长度是否超出限制最大长度,512*1024*1024个字节长度 */ void setGenericCommand(redisClient *c, int flags, robj *key, robj *val, robj *expire, int unit, robj *ok_reply, robj *abort_reply) /* 设置的泛型指令操作 */ void setCommand(redisClient *c) /* 设置的综合方法,设置都是根据Client中的参数而定 */ void setnxCommand(redisClient *c) /* key不存在的时候才设置值,flag为REDIS_SET_NX时 */ void setexCommand(redisClient *c) /* key存在的时候才设置值,flag为REDIS_SET_NO_FLAGS,命令到期时间单位为秒 */ void psetexCommand(redisClient *c) /* key存在的时候才设置值,flag为REDIS_SET_NO_FLAGS,命令到期时间单位为毫秒 */ int getGenericCommand(redisClient *c) /* 获取命令的泛型命令 */ void getCommand(redisClient *c) /* 获取命令的操作 */ void getsetCommand(redisClient *c) /* 获取set命令的操作 */ void setrangeCommand(redisClient *c) /* 设置rangge命令的操作 */ void getrangeCommand(redisClient *c) /* 获取range命令的操作 */ void mgetCommand(redisClient *c) /* 执行多次getCommand指令 */ void msetGenericCommand(redisClient *c, int nx) /* 一次运行多个设置操作泛型命令 */ void msetCommand(redisClient *c) /* 多次设置指令的非NX模式 */ void msetnxCommand(redisClient *c) /* 多次设置指令的NX模式,即只在不存在的时候才设置 */ void incrDecrCommand(redisClient *c, long long incr) /* 增加或减少固定值的操作,减少其实就是增加-1 */ void incrCommand(redisClient *c) /* 递增1操作,incr递增设置为1 */ void decrCommand(redisClient *c) /* 递减1操作,incr递增设置为-1 */ void incrbyCommand(redisClient *c) /* 增加指令,从Client中获取递增值 */ void decrbyCommand(redisClient *c) /* 减少指令,从Client中获取减少值 */ void incrbyfloatCommand(redisClient *c) /* 增加float类型值的操作命令,在获取原始值的时候,获取的方法不一样,为getLongDoubleFromObjectOrReply*/ void appendCommand(redisClient *c) /* 追加命令操作,其实也是key:value的形式 */ void strlenCommand(redisClient *c) /* 获取命令长度 */ ~~~ 里面都是一些键值对的简单操作,有一个不同点是,里面的设置操作分为3种: ~~~ /* SET操作的一些FLAG */ #define REDIS_SET_NO_FLAGS 0 #define REDIS_SET_NX (1<<0) /* Set if key not exists. */ #define REDIS_SET_XX (1<<1) /* Set if key exists. */ ~~~ 如上面所说,nx模式指的是key不存在的时候才设置值,xx为存在的时候设置,这种模式设置有命令到期时间的限制,分为单位为秒级和毫秒级,而nx模式下,没有时间上的限制,调用的泛型方法: ~~~ void setGenericCommand(redisClient *c, int flags, robj *key, robj *val, robj *expire, int unit, robj *ok_reply, robj *abort_reply) ~~~ 注意其中的expire,和时间单位unit: ~~~ /* key不存在的时候才设置值,flag为REDIS_SET_NX时 */ void setnxCommand(redisClient *c) { c->argv[2] = tryObjectEncoding(c->argv[2]); setGenericCommand(c,REDIS_SET_NX,c->argv[1],c->argv[2],NULL,0,shared.cone,shared.czero); } /* key存在的时候才设置值,flag为REDIS_SET_NO_FLAGS,命令到期时间单位为秒 */ void setexCommand(redisClient *c) { c->argv[3] = tryObjectEncoding(c->argv[3]); setGenericCommand(c,REDIS_SET_NO_FLAGS,c->argv[1],c->argv[3],c->argv[2],UNIT_SECONDS,NULL,NULL); } /* key存在的时候才设置值,flag为REDIS_SET_NO_FLAGS,命令到期时间单位为毫秒 */ void psetexCommand(redisClient *c) { c->argv[3] = tryObjectEncoding(c->argv[3]); setGenericCommand(c,REDIS_SET_NO_FLAGS,c->argv[1],c->argv[3],c->argv[2],UNIT_MILLISECONDS,NULL,NULL); } ~~~ nx模式时expire和unit参数分别为NULL,0,所以我做出了如下猜想,可能是因为,当键值对存在的时候,考虑多并发设置的情况,有些Client可能被阻塞,所以有超时时间的存在,而key不存在的时候,就看谁更快了吧,就是直接设置。下面还有一个这个文件比较有意思的方法,有点批处理的味道,换句话说,一个方法里执行多次set操作: ~~~ /* 一次运行多个设置操作泛型命令 */ void msetGenericCommand(redisClient *c, int nx) { int j, busykeys = 0; /* 设置操作一定是成对出现的 */ if ((c->argc % 2) == 0) { addReplyError(c,"wrong number of arguments for MSET"); return; } /* Handle the NX flag. The MSETNX semantic is to return zero and don't * set nothing at all if at least one already key exists. */ if (nx) { for (j = 1; j < c->argc; j += 2) { if (lookupKeyWrite(c->db,c->argv[j]) != NULL) { busykeys++; } } //如果key存在,返回0 if (busykeys) { addReply(c, shared.czero); return; } } //隔2个执行设置key操作指令一次 for (j = 1; j < c->argc; j += 2) { c->argv[j+1] = tryObjectEncoding(c->argv[j+1]); setKey(c->db,c->argv[j],c->argv[j+1]); notifyKeyspaceEvent(REDIS_NOTIFY_STRING,"set",c->argv[j],c->db->id); } server.dirty += (c->argc-1)/2; addReply(c, nx ? shared.cone : shared.ok); } ~~~ 也不是什么特别的操作,应该redis编写者为了方便效率的提高吧。其他的一些方法,请读者可以学习t_string.c的文件,还有提醒一点,在redis数据库中,存储的形式都是K-V形式的,所有的获取,设置都是通过KEY的形式操作,你会看到很多这样的方法: ~~~ dbAdd(c->db,c->argv[1],new); setKey(c->db,c->argv[j],c->argv[j+1]); ~~~
';