baiyan所有视频：【日常学习记录】使用视频录制设备记录日常学习。什么是dict，也就是字典，也叫哈希表。在redis的五大数据结构中，dict结构用在以下两种情况：hash：数据量小的时候用ziplist，数据量大的时候用dictzset，数据量大的时候用ziplist小，数据量大的时候使用skiplist+结合以上两种情况，我们可以看出dict也是一个比较复杂的数据结构，通常在数据量大的情况下使用。通常，一个字典是这样的：在这个哈希表中，每个存储单元被称为一个桶。我们在这个dict(hashtable)中插入一个键值对"name"=>"baiyan"。假设这个key“name”的hash运算结果为3，那么我们在这个hashtable位置寻找下标3插入，得到如图的情况。我们可以看到dict最大的优势就是它的查找时间复杂度是O(1)，这是其他任何数据结构都无法比拟的。我们在查找的时候，先对key“name”进行hash，得到结果3，直接到dict索引为3的位置去查找值“baiyan”，时间复杂度为O(1)。相当快。redis中字典的基本结构在redis中，在普通字典的基础上，为了方便扩缩，增加了一些描述字段。还是基于上面的例子，redis中的存储结构如下图所示：dicttht的结构如下：typedefstructdicttht{dictEntry**table;无符号长尺寸；无符号长尺寸掩码；unsignedlongused;}dicttht;在dicttht中，真正存放数据的地方是**table的dictEntry类型的二级指针。我们可以把它分开。首先，第一个指针可以表示一个一维数组，即哈希表。后面的指针表示在每个一维数组（哈希表）的存储单元中，存储了一个dictEntry类型的指针，这个指针指向我们存放键值对的dictEntry类型结构的位置。如图所示存放最终键值对的dictEntry结构如下：typedefstructdictEntry{void*key;union{void*val;uint64_tu64；int64_ts64；双d;}v;结构dictEntry*下一个;}dictEntry;一个存储key-value对的入口，这里主要是key和value字段。由于dict中存储的key和value可以是字符串、整数等，所以这里用void*指针来表示。我们注意到最后有一个同类型dictEntry的next指针，用来解决我们常说的hash冲突问题。哈希冲突当我们对不同的键进行哈希运算，结果相同时，就会遇到哈希冲突的问题。哈希冲突的常用解决方案有两种：开放寻址和链寻址。Redis使用的是后者。通过这个next指针，我们可以将哈希值相同的元素拼接起来，解决哈希冲突的问题。注意在redis的源码实现中，往dict中插入元素时，使用的是链表的头部插入方式，即新元素插入到链表的头部，这样就不必每次都遍历到链表的尾部进行插入，降低了插入的时间复杂度。链地址法带来的问题假设我们不断往dict中插入元素，那么哈希表的所有桶都会被填满，而在链地址法解决哈希冲突的过程中，每个桶后面的链表会是很长。这样，这个链表的时间复杂度就会逐渐退化为O(n)。对于整体的dict，其查询效率会大大降低。为了解决数据量过大导致dict性能下降的问题，我们需要对其进行扩容以满足后续插入元素的存储需求。divideandconquerrehash通常情况下，我们会对哈希表做2倍的扩充，即从2->4、4->8等。假设我们已经在我们的一个dict中存储了很多数据，我们还需要往这个dict中插入很多数据。在后续插入大量数据的过程中，因为需要解决dict性能下降的问题，所以需要对其进行扩容。扩容时，所有的key-value对都需要重新哈希一次，重新分配到对应的bucket位置。我们称此过程为重新哈希。在rehash过程中，需要进行大量的hash操作，开销相当大，耗时也相当长。由于redis是单进程单线程架构，在执行rehash的过程中，由于其开销大，时间长，会导致redis进程阻塞，进而无法在线提供数据存储服务，redis服务将作为不可用返回给外部。为了解决一次性rehash导致redis进程阻塞的问题，采用分而治之的编程思想，将一次rehash操作分散成多个步骤，以减少rehash给redis进程带来的资源占用。举个例子，可以在后续的get和set操作中进行rehash操作。为了实现这种操作，redis其实设计了两个哈希表，一个是我们前面提到的对外提供访问服务的哈希表，另一个是专门用于rehash操作的。这种分而治之的思想，将一个数据量大的rehash操作分成多次完成，称为progressiverehash：目前处于rehash状态。我们可以看到，在上图的基础上，我们新增了一个结构体dict，其中ht[2]字段负责指向两个哈希表。下面这个哈希表的大小是前面的大小8*2=16，没有任何元素。dict的结构如下：typedefstructdict{dictType*type;无效*私有数据；字典ht[2];长重新哈希；/*重新哈希进程ID。如果值为-1，则不在rehash中，否则在rehash中*/unsignedlongiterators;/*当前运行的迭代器数量*/}dict;注意rehashidx字段，代表我们rehash的过程。注意我们每执行一次get或者set等命令，都会进行一次rehash，即将原哈希表ht[0]上的一个元素移动到新的哈希表ht[1]中，只移动每次一个元素，移动完成后，rehashidx会+1，直到原哈希表上的所有元素都移动到新的哈希表中。rehash完成后，新的哈希表ht[1]会被置为ht[0]，提供在线服务。而原来的哈希表ht[0]会被销毁。rehash的源码如下：intdictRehash(dict*d,intn){intempty_visits=n*10;/*要访问的空桶的最大数量。*/if(!dictIsRehashing(d))返回0;while(n--&&d->ht[0].used!=0){dictEntry*de,*nextde;/*请注意，rehashidx不会溢出，因为我们确信还有更多*元素，因为ht[0].used!=0*/assert(d->ht[0].size>(unsignedlong)d->rehashidx);while(d->ht[0].table[d->rehashidx]==NULL){d->rehashidx++;如果(--empty_visits==0)返回1；}de=d->ht[0].table[d->rehashidx];/*将旧哈希表ht[0]中的元素移动到新哈希表ht[1]中*/while(de){uint64_th;nextde=de->下一个；/*计算新哈希表的索引下标ht[1]*/h=dictHashKey(d,de->key)&d->ht[1].sizemask;//哈希算法de->next=d->ht[1].table[h];d->ht[1].table[h]=de;d->ht[0].used--;d->ht[1].used++;de=nextde;}d->ht[0].table[d->rehashidx]=NULL;d->rehashidx++;}/*检查rehash是否完成，如果完成，设置rehashidx为-1*/if(d->ht[0].used==0){zfree(d->ht[0].table);d->ht[0]=d->ht[1];_dictReset(&d->ht[1]);d->rehashidx=-1;返回0；}/*Moretorehash...*/return1;}rehash过程中rehash可能带来的问题影响如果在rehash过程中（比如容量从4扩容到8），如果我们需要找一个元素，首先我们会计算哈希值（假设为3）找到旧的哈希表ht[0]，如果找到位置3上没有元素，则说明这个元素已经重新哈希过，到新的哈希表上对应的位置3或7去查找就可以了。rehash对遍历的影响想象这样一种情况：在rehash之前，我们第一次使用SCAN命令遍历dict；而rehash结束后，我们进行第二次SCAN遍历，会发生什么？在讨论这个问题之前，让我们先熟悉一下SCAN命令。我们知道，当我们执行keys时，会返回所有的key值，因为key加在一起的数量相当多，如果一次性全部遍历，会导致单进程redis阻塞很长时间。本版块无法随时对外提供服务。为了解决这个问题，SCAN命令诞生了。它不会一次返回所有的key，而是每次返回一部分key，并记录本次遍历的进度。这里用游标来记录。下次再次运行SCAN命令时，redis会继续从光标位置向下遍历。SCAN命令其实是一种分而治之的思想，让每次遍历一小部分，直到遍历完成。SCAN命令官方解释如下：SCAN命令是一个基于游标的迭代器：每次调用SCAN命令后，都会返回一个新的游标给用户，用户需要使用这个新的游标作为下一次迭代中SCAN命令的游标参数。这将继续之前的迭代过程。SCAN命令的用法如下：redis127.0.0.1:6379>scan01)"17"2)1)"key:12"2)"key:8"3)"key:4"4)"key:14"5)"key:16"6)"key:17"7)"key:15"8)"key:10"9)"key:3"10)"key:7"11)"key:1"redis127.0.0.1:6379>scan171)"0"2)1)"key:5"2)"key:18"3)"key:0"4)"key:2"5)"key:19"6)"key:13"7)"key:6"8)"key:9"9)"key:11"在上面的例子中，第一次迭代使用0作为光标，表示新的开始迭代。第二次迭代使用第一次迭代返回的游标，即命令以第一个元素的值17回复。从上面的例子可以看出，SCAN命令的回复是一个包含两个元素的数组，第一个数组元素是下一次迭代的新游标，第二个数组元素是一个数组，数组包含所有元素正在迭代。第二次调用SCAN命令时，命令返回游标0，表示迭代结束，整个集合遍历完毕。以0为游标开始新的迭代，调用SCAN命令，直到命令返回游标0。我们称这个过程为完全遍历。回到正题，我们来解决之前的问题。我们把dict的结构简化一下，只留下两个基本的哈希表结构。我们现在有4个元素：12、13、14、15，假设哈希算法是余数。假设我们在rehash之前使用SCAN命令。基于我们之前提到的知识点，由于SCAN是基于游标的增量遍历，我们假设SCAN命令只遍历到游标为1的位置然后停止：我们得到第一次遍历的结果:12开始重新哈希。rehash结束，我们再次使用SCAN命令遍历一遍。由于上次返回的游标是1，所以我们继续从1的位置开始遍历，但是这次需要在新的哈希表中遍历：第二次SCAN命令遍历的结果是：12,13,14,15然后我们将两次SCAN的结果合并在一起，分别是12、12、13、14、15。我们发现元素12被多遍历了一次，这与我们的预期不符。所以我们得出结论，在rehash过程中执行SCAN命令会导致遍历结果冗余。解决方案为了解决rehash扩缩容过程中重复遍历的问题，redis对哈希表的下标做了如下修改（v为哈希表的下标）：v=rev(v);v++;v=转速(v);先反转光标，加一，再反转，也就是我们所说的“高++”操作。这里的这几步就是通过前面的下标计算哈希表中下一个桶的下标。举个例子：一开始，00号桶是不应该被移动的。正常的低位++之后，00后面应该是01。但是，现在是高位++，01原来位置的下标会变成10……以此类推。最终哈希表的下标会由原来的00、01、10、11的顺序变为00、10、01、11，如图：这样可以保证我们不会执行SCAN命令多次。重复遍历？接下来就是见证奇迹的时刻了：首先，在rehash之前，先对其进行SCAN。同样，我们假设SCAN命令只遍历到游标为1的位置就停止了：我们得到第一次遍历的结果：12startsrehashrehashends，我们再用SCAN命令遍历一遍。这里注意，上次返回的游标是2，我们从2的位置继续遍历，也是在新的哈希表中遍历：可以看到，稍微修改下标，就可以解决问题由rehash引起的SCAN重复遍历的问题。遍历dict的源码如下：unsignedlongdictScan(dict*d,unsignedlongv,dictScanFunction*fn,dictScanBucketFunction*bucketfn,void*privdata){dicttht*t0,*t1;constdictEntry*de,*next;无符号长m0，m1；如果(dictSize(d)==0)返回0；//如果在SCAN期间没有执行rehashif(!dictIsRehashing(d)){t0=&(d->ht[0]);m0=t0->大小掩码；/*在光标处发出条目*/if(bucketfn)bucketfn(privdata,&t0->table[v&m0]);de=t0->表[v&m0];while(de){//遍历同一个桶上后面附加的链表next=de->next;fn(privdata,de);de=下一个；}/*设置未屏蔽的位，以便递增反向游标*对屏蔽的位进行操作*/v|=~m0;/*递增反向游标*/v=rev(v);//反转vv++;//反转后为高++v=rev(v);//反转回来，得到下一个游标值//如果在SCAN期间正在进行重新散列}else{t0=&d->ht[0];t1=&d->ht[1];/*确保t0是较小的表而t1是较大的表*/if(t0->size>t1->size){t0=&d->ht[1];t1=&d->ht[0];}m0=t0->大小掩码；m1=t1->大小掩码；/*在光标处发出条目*/if(bucketfn)bucketfn(privdata,&t0->table[v&m0]);de=t0->表[v&m0];while(de){//遍历同一个桶上的链表next=de->next;fn(privdata,de);de=下一个；}/*迭代较大表中的索引，这些索引是较小表中游标指向的索引的扩展*/do{/*在游标处发出条目*/if(bucketfn)bucketfn(privdata,&t1->table[v&m1]);de=t1->表[v&m1];while(de){//遍历同一个桶链表next=de->next;fn(privdata,de);de=下一个；}/*递增未被较小掩码覆盖的反向光标。*/v|=~m1;v=转速(v);//反转vv++;//反转后为高位++v=rev(v);//将其反转以获取下一个光标值/*当掩码差异覆盖的位不为零时继续*/}while(v&(m0^m1));}returnv;}关于rehash过程对SCAN的影响，限于篇幅仅展示这种情况。更多内容请参考：Redis扫描命令原理
