图解+源码角度理解Redis底层原理(一)
文中可能出现一些对C语言概念的讲解，如果你熟悉C，可能会觉得这种讲解很啰嗦，但是考虑到有些人对C不熟悉(包括我自己)，所以有些地方做了C语言概念的讲解。
文章太长，加之我C语言基础不怎么样，出现错误，在所难免，本文是我通过查阅redis官方文档+网上资料+阅读并理解部分redis源码所总结出来的，如果有哪个地方我理解错了，或者写错了，请大牛们指出，我看到后会第一时间修改！
Redis的五种存储类型
- 1、string：字符串类型，一个key对应一个value；
- 2、hash：哈希，一个key对应一组键值对，类似mysql中一个id对应一行数据；
- 3、list：列表，是一个由字符串组成的列表，数据是有序的；
- 4、set：集合，一组string类型数据的集合，与数学中的集合类似，可实现交集、并集、差集；
- 5、zset：有序集合，与集合类似，只不过多了一个score用于排序。
Redis五种类型宏定义，源码在这里第641行
/* The actual Redis Object */
#define OBJ_STRING 0 /* String object. */
#define OBJ_LIST 1 /* List object. */
#define OBJ_SET 2 /* Set object. */
#define OBJ_ZSET 3 /* Sorted set object. */
#define OBJ_HASH 4 /* Hash object. */
string(字符串)类型
string类型是redis最基本的类似，可以理解为跟memcache一样的类型，一个key对应一个value。value是二进制安全的，也就是说value可以是任何数据，比如一张图片，一个文件，一个序列化的对象等等，value最大支持512MB。
应用场景：
- 1、用于做数据缓存：比如手机验证码，发了就设置到redis里，并给一个有效时间，如果验证码被使用了，就把这个key删掉，换句话说，如果没有删掉，那说明还未被使用，就可以把这个未使用的再发一遍，如果有效时间过期了，说明需要重新生成(一般短信验证码都是5分钟或10分钟内使用才有效，超过时间你填对了也无效的)；
- 2、计数：decr，秒杀的时候可以做原子性的库存自减，incr还可以做访问量自增统计、点赞数、喜欢数、收藏数、评论数。
- 3、限流：短信一分钟内限制发送次数(设置key过期时间为60秒，数字自增，比如一分钟允许发3次，如果返回3那就不允许发送)。以ip为key，访问一次增加一次，增加到一定次数时禁止访问，等key过期失效才访问；
- 4、字符串的bitmap可用作点赞、签到、打卡。
- 5、分布式锁：使用setnx，只有key不存在才能设置成功。
Hash(哈希)类型
哈希就是多个键值对，一条哈希数据，其实就相当于关系数据库一条记录，key对应数据库的id，值就是很多键值对，比如name=>张三，age=>23，gender=>男，……
当然用string类型也可以存，一种方法是分别存，key用“id+属性”方式，比如：
123_name => 张三
123_age => 23
123_gender => 男
124_name => 李四
124_age => 22
124_gender => 女
另一种就是存一个key，value如果是对象就序列化，如果是数组就转json，这样一个key=>value就能存，但是如果涉及到修改数据，就要整个取出来修改后再替换存回去，增加了序列化和反序列化(json化/反json化)的开销，而用Hash类型存储，就可以像数据库一样，单独对某个字段进行更新或获取。
应用：
存储数据库中的一组数据，比如“user101”是id为101的用户，以“user101”为key，则值有用户名，姓名，年龄等等，就可以用哈希来存。
List(列表)类型
List是一个字符串列表，按插入顺序排序，可以分别从头部或尾部进行push/pop操作。当固定一边，比如固定从右边进，右边出时，列表就相当于一个栈。
应用：
- 1、可以做简单的队列使用(使用lpush + brpop，b是block，如果没有数据会阻塞，直到有数据才会rpop)，由于消费后就会被删除，所以可能出现丢数据的情况，所以只能做简单的消息队列；
- 2、微博最新的一页，微博显示5条最热评论(或最新评论)，微信朋友圈第一页
set(集合)类型
就是数学中的集合概念，有两个重要特性：互异性，无序性，互异性就是集合中的元素都是不相同的，不可能重复，无序性就是集合中的元素是无序的，你每次取出来几个，可能顺序都不一样。
由于集合的互异性，它天生具有数据排重的功能，因为重复的数据根本不可能被写入，所以集合可用于计算两个集合的交集、并集、差集。
应用：
- 1、一个用户所有的关注人存在一个集合中
- 2、一个用户所有的粉丝存在一个集合中
zset(有序集合)类型
zset就是在set的基础上添加了一个排序权重——score(分值)，让本来无序的集合并的有序。
应用：
排行榜
远程字典服务器
Redis存储原理概述
其实Redis就是个“键值对”存储引擎，你别管它什么类型，最终都是“一个键对应一个值”，只不过，这“一个值”未必是“一个字符串”(数字按字符串算，内部会优化)，它还可能是由多个字符串按一定的规则构成的复合类型，比如list,hash,set,zset。
那么“键值对”中的“键”和“值”是怎么存的呢？Redis构建了两个结构体类型：
- 1、sds类型：用于存储字符串，“键值对”中的“键”就是使用sds类型来存储；
- 2、RedisObject类型：用于存储“键值对”中的“值”。
Redis的所有键都是字符串，所以都是使用sds类型存储的，注意这里很多人很多文章都搞错了，很多人都以为key也是存储在RedisObject里的，但其实并不是，证明文章有：How key/value pairs are stored in Redis、redis 一组kv实际内存占用计算，另外在rdb.c文件的int rdbLoadRioWithLoadingCtx函数中，就有sds key和robj *val的定义，这说明key是sds类型，而value是redisObject类型。
而所有值，都是一个RedisObject对象，当然它不是直接存在RedisObject里，而是根据数据类型的不同，由RedisObject分别指向不同的类型，比如存的是字符串，RedisObject就会指向一个sds对象，如果存的是其它四种类型，即list,hash,set,zset，RedisObject会指向这四种类型的数据，当然这四种数据类型本身并不是一个字符串或一个数字，而是由多个sds字符串根据一定的规则组成的结构。
什么是字典？
Redis这个词其实是Remote Dictionary Server的缩写，意思是“远程字典服务器”。从它的名字全称就可以看出，Redis其实是个字典服务器，它的存储结构就是个字典。
什么是字典：字典是一种用于保存“键值对”的抽象数据结构。字典又称为符号表(symbol table)、关联数组(associative array)或映射表(map)等等。
在字典中，一个键(key)可以和一个值(value)进行关联(或者说将键映射为值)，这些关联的键和值就称为“键值对”(key-value pair)。
字典中每个键都是独一无二的，程序可以在字典中根据键查找与之关联的值，或者通过键来更新值，又或者根据键来删除整个键值对，等等。
所以前面Redis存储原理概述中所说的“键值对”存储引擎，其实就是字典引擎，或者叫字典服务器。
Redis如何保存键值对？
前面说过，Redis就是个键值对服务器，那么Redis是怎么保存成千上万的“键值对”的呢？毫无疑问，就是使用“字典结构”来保存的，毕竟前面说了，Redis的名字本身就是“远程字典服务器”的意思，它保存“键值对”肯定就是用字典结构来保存了。
下图展示了Redis的string类型是如何存储两个“键值对”的(Redis<7.0)
下图展示了Redis的hash类型是如何存储的(使用ziplist存储哈希类型，在Redis<7.0时使用)
前面都是Redis6.2版本，从7.0开始dictht被去掉了，直接从dict指向ht_table数组，数组的元素都指向dictEntry，去掉这一层之后，由于少了一些header占用空间，所以内存占用更少了。
下图展示了Redis的string类型是如何存储两个“键值对”的(Redis>=7.0)
下图展示了Redis的hash类型是如何存储的(使用listpack存储哈希类型，在Redis>=7.0时使用)
除了以上几张图所画的，RedisObject中的*ptr其实还可以指向quicklist,hashtable等结构，由于这两个结构比较大，一张图画不下，就不画了，后面会给出单独的quicklist和hashtable的图。总之Redis的值都是一个RedisObject，再根据具体的值的不同，RedisObejct的*ptr会指向该具体值，只不过这个“具体值”有时候并不是一个单一的值，而是一个复合结构。
Redis的字典
Redis宏观结构
由前面什么是字典？和Redis如何保存键值对？可知，Redis保存“键值对”的主要结构就是字典，只不过字典是宏观的结构，它的下层还有很多其它的存储结构。
Redis存储两个“键值对”示意图(Redis6.2)
Redis存储两个“键值对”示意图(Redis>=7.0)
由上面第一张图可知：
- 1、Redis用一个redisServer结构体指向它的16个DB(编号0-15)；
- 2、每一个DB都指向一个字典(dict)，即每个DB中的所有“键值对”都是由“一个字典结构”来保存的；
- 3、每个字典包含两个哈希表(dictht)，之所以包含两个哈希表，是因为在存储过程中需要不断的rehash(重哈希)，而rehash需要两个哈希表之间不断的交换数据。特别注意，这里说“包含”而不是指向，是因为两个dictht本身就是dict结构体中一个dictht类型的数组，数组包含两个元素，它们是包含关系，并不是“指向”，上图中画成“指向”，是因为在dict里面画两个dictht结构画不下，太大了，不方便画；
- 4、每个哈希表结构指向一个“字典条目数组”，该数组为指针数组，即数组的每个元素都是一个指针，用于指向一个字典条目(dictEntry)
- 5、每个字典条目(dictEntry)就是一个“键值对”，到了这里我们终于明白，“键值对”原来是存储在这里的；
- 6、每个键值对中的“键”指向一个sds字符串，因为键一定是字符串；
- 7、每个键值对中的“值”指向一个RedisObject结构体，再由RedisObject结构体指向具体类型的数据。因为Redis的值类型有五种，当然这五种值类型也只是宏观体现，其底层是用其它更多的其它类型来存储的，比如如果值是list类型，那RedisObject中的
*ptr有可能指向ziplist, listpack, quicklist(ziplist), quicklist(listpack)等等，而如果值是hash类型，那RedisObject中的*ptr有可能指向ziplist,listpack,hashtable等等； - 8、由上面第二张图可知，从Redis7.0开始，dictht被去掉，dict直接指向两个dictEntry数组(同理，两个数组是因为需要rehash)。
注意：虽然Redis的字典由哈希表作为底层结构，但这里所说的哈希表并不是Redis五种存储类型(string,list,hash,set,zset)中的hash，虽然五种类型中的hash存储类型就是用这种结构实现的，但那是另一层结构。当value为hash类型时，RedisObject中的*ptr指向一个“字典结构”，这个被指向的“字典结构”就是哈希类型的“底层”，当然这个“底层”(即字典)本身也不是最底层，它又是由哈希结构来实现的。
即值类型为hash类型时，是由字典结实现，但字典结构又是由哈希结构实现的，是不是感觉有点绕？因为字典结构是一个抽象的数据结构，它本身可以由多种数据结构来实现，只不过大多采用哈希结构来实现而已，所以“哈希类型”并不等于“哈希结构”，比如数据量少时，哈希类型其实是用ziplist或listpack来实现的，而数据量多时，会使用字典结构实现，只不过这个字典结构是个抽象概念，其本质上还是使用哈希结构来实现的。
简单来讲就是：字典结构被用在多个地方，一个地方是全局“键值对”，还有一个是值为hash类型时也是用字典保存，还有哨兵结构等都是用字典来保存的。
hash表原理与哈希冲突
hashtable(哈希表)基本原理是把数据映射到数组中的某个位置，这样就可以通过数组下标访问该数据了。后面的Hash类型存储原理-控制参数中有说到Redis什么时候会使用hashtable来存储。
- 如上图图1所示，数组长度为4，通过将“数字%4”取模，得到它们应该保存的位置，这样就把数字与数组的下标对应起来了，这样只要我想知道7在哪里，只要计算
7%4=3就知道它在数组下标为3处； - 如上图图2所示，有可能出现两个数字指向同一个地址，这种情况叫哈希冲突(collosion)，一般解决冲突的办法有开放地址法、再散列法、链地址法等等，Redis采用的是链地址法；
- 如上图图3所示，通过链地址法解决哈希冲突，把指向同一个地址的数字串连起来，当然其实它的箭头应该是反过来，数组中存储的是指针，指向整个链的开始地址
Redis的hash原理就是通过一个哈希函数，把Redis的key转换为一个整数，然后这个整数再对数组长度进行取模，比如某个key值(字符串)转为整数后是11，数组大小为4(数组长度为4)，那么计算11%4=3，就知道它应该放到数组下标为3的元素中。
用“按位与”做取模运算
前面hash表原理与哈希冲突中说过，hash表其实就是通过把要保存的数据通过hash算法转换为数字后，通过取模把它映射到中的，所以哈希表中取模操作非常常用，所以我们必须保证取模操作非常高效。
对于计算机来说，“按位与”运算非常简单，所以把取模运算转换成“按位与”运算，将会让取模效率变的非常高效，事实上Redis中哈希表的取模运算就是用“按位与”来实现的。关于模的概念，可以看参考我另一篇文章中的“模”的概念。
取模：表示计算两个数相除后的余数，比如7%4表示7对4取模(4就是“模”)，表示7除以4的余数，7除以4=1余3。但是电脑是怎么计算这个7%4的呢？其实已经有一个等式：a%b = a&(b-1)(b必须为2n)，&就是“按位与”，即两个数的二进制位相与。
这里我们来算一下7%4，因为4=22，符合条件
111 --- a=7
011 --- b-1=4-1=3
----
011 --- 3
以上计算结果是对的，7%4确实等于3。
我们再来算一个，13%8，8=23，符合条件
1101 --- a=13
0111 --- b=8-1=7
----
0101 --- 5
以上结果是对的，13%8确实等于5。
我们再来算一个，13%4，4=22，符合条件
1101 --- a=13
0011 --- b=4-1=3
----
0001 --- 1
以上结果是对的，13%4确实等于1。
经过以上三个实例，我们总结一下，为什么取模运算可以用“按位与”代替呢？主要是因为模是2n，如果模不是2n，那就没办法这样做。
为什么模是2n时，可以把取模运算转换为“按位与”运算呢？因为2n一定是100……0(n个0)，也就是它最高位总是为1，剩下的都是0，而减去1，由于低位全是0，没法减，它会一直向高位借位，最终借到最高位(最左侧那一位)，这样就相当于刚好把最高位变成0，其它全变1，然后某个数与它做按位与，只有和“模”的1相对应的低位会被原样保留下来，高位则全部被去掉，而这刚好就是取模的原理。
二级指针与指针数组
之所以讲这个，是因为哈希表结构体用到了双重指针，怕有人看不懂，所以先讲讲二级指针与指针数组。
- 1、二级指针，也叫双重指针，就是指向指针的指针，一级指针指向的“值”就是真正的值，二级指针指向的“值”是一个地址(即指针)，这个地址再指向真正的值；
- 2、指针数组：数组中的元素都是指针；
二级指针与指针数组是有一定关系的，如果你想要用一个指针来指向“数组指针”，那么这个指针必须用“二级指针”，请看下边的例子
#include <stdio.h>
int main(int argc, char const *argv[])
{
// 定义3个int型变量并初始化
int a = 11, b = 22, c = 33;
// 定义一个数组，它的每个元素都是一个指向整型数字的指针，即该数组的每个元素都是“int*”类型
int* arr[3] = {&a, &b, &c};
//定义一个指针*p，用它来指向arr，由于arr的类型是“int*”，所以*p的类型也必须为“int*”
int* *p = arr;
// 当然现实中一般写成
// int *arr[3] = {&a, &b, &c};
// int **p = arr;
// 其实数组的地址就是数组第一个元素的地址，由于**p指向数组arr，所以**p就是arr[0]
// 指向的值(*p是arr[0]本身，它是一个地址，再加个*，即*(*p)，表示取这个地址的内容)
printf("arr数组第一个元素指向的值 => %d\n", *(*p));
// 当然括号是可以去掉的
printf("arr数组第一个元素指向的值 => %d\n", **p);
// 以次类推，**(p+1)就表示数组arr的第二个元素指向的值
printf("arr数组第二个元素指向的值 => %d\n", **(p+1));
// **(p+2)就表示数组arr的第三个元素指向的值
printf("arr数组第三个元素指向的值 => %d\n", **(p+2));
return 0;
}
// arr数组第一个元素指向的值 => 11
// arr数组第一个元素指向的值 => 11
// arr数组第二个元素指向的值 => 22
// arr数组第三个元素指向的值 => 33
共用体(联合体)
共用体，也叫联合体，共用体和结构体，除了结构体定义用struct，共用体定义用union之外，其它完全一样，但它的表现就有所区别了。
以下是定义共用体的3种方法以及检测“共用体类型变量”和“共用体本身”占用的内存大小
#include <stdio.h>
int main(int argc, char const *argv[])
{
// 定义共用体方式1: 先定义共用体，再使用共用体名字定义共用体类型变量
union data1{
int n;
char ch;
double f;
};
union data1 a1, b1, c1;
// 定义共用体方式2: 定义共用体的同时，定义共用体变量，因为有名称，
// 所以后续还需要定义该共用体的其它变量，可以直接用共用体的名称来定义，
union data2{
int n;
char ch;
double f;
} a2, b2, c2;
// 定义共用体方式3: 定义共用体的同时，直接定义共用体类型
// 变量，因为没有名称，以后无法再定义该共用体类型的变量
union{
int n;
char ch;
double f;
} a3, b3, c3;
// 检测一下前面方式1定义的"union data1"类型的共用体变量
// “a1”占用的内存大小以及共用体data1本身占用的内存大小
// 输出: 8, 8
printf("%lu, %lu\n", sizeof(a1), sizeof(union data1) );
return 0;
}
把以上代码保存到test.c文件中，然后在终端中test.c所在目录下运行以下命令即可执行(必须保证当前目录下没有test文件，因为运行会生成test文件，如果之前就有，会造成冲突，无法生成)
gcc -o test test.c && ./test
运行后你会发现输出是“8, 8”，也就是“union data1”类型的共用体变量占用8个字节，union data1共用体也占8个字节，我们来分析一下共用体各属性占用字节数：
int n占4个字节；char ch占1个字节；double f占8个字节；
如果是结构体的话，由前面结构体成员对齐和结构体成员不对齐可知，结构体所占用的内存至少也是结构体内各个属性占用的内存之和，但共用体占用的内存却是它最长的那个属性占用的字节数，为什么呢？因为共用体所有属性具有同一个起始地址，它们的地址是共用的，这也是它叫“共用体”的原因。
如下图所示，char ch, int n, float f共同占用一个内存空间，它们具有同一个起始地址，这也代表着它们的值会相互覆盖，只有最后赋值的那个属性才有效
共用体的主要作用是为了节省内存，当有两个属性不需要同时用到时，共用体属性相互覆盖的缺点就可以忽略，就可以用共用体来代替结构体以节省内存。
字典相关的结构体
字典主要三个结构体为：dict结构体、dictht结构体(<7.0)、dictEntry结构体。
dict结构体(<7.0)：即字典结构体
// 6.2
typedef struct dict {
dictType *type;
void *privdata;
dictht ht[2];
long rehashidx; /* rehashing not in progress if rehashidx == -1 */
int16_t pauserehash; /* If >0 rehashing is paused (<0 indicates coding error) */
} dict;
*type由于字典结构被用在多个地方，比如Redis的整体“键值对”用字典，hash存储类型中的“值”也是一个一个的“键值对”，它同样也是使用这个字典结构来保存，哨兵模式中，也是用字典来存储管理所有的master节点和slave节点。虽然它们都是用字典结构存，但具体肯定有所区别的，而这个*type就是用来指向字典在具体的应用场景下特定的处理函数的；*privdata即private data，私有数据，是配合*type指向的函数一起使用的；ht[2]哈希表，用于指向两个dictEntry类型的哈希数组；rehashidx用于标记rehash到哪个元素，idx就是index，即索引，当没有rehash时，它的值为-1；pauserehashrehash停止标记，如果大于0表示停止，小于0表示错误，等于0表示未停止；
dict结构体(>=7.0)：由于该版本去掉了dictht结构体，所以把6.2中本来放在dictht结构体中的**table、size、used都放到dict结构体中了，但是没有sizemask，因为它等于size-1，所以可通过size计算得出
// 7.0
struct dict {
dictType *type;
// 7.0中取消dictht结构，所以从字典这里直接指向dictEntry数组
dictEntry **ht_table[2];
// 由于7.0取消了dictht结构，6.2中两个dictht结构中
// 的used属性被挪到这里，用一个数组的两个元素来表示
unsigned long ht_used[2];
long rehashidx; /* rehashing not in progress if rehashidx == -1 */
/* Keep small vars at end for optimal (minimal) struct padding */
int16_t pauserehash; /* If >0 rehashing is paused (<0 indicates coding error) */
// 由于7.0取消了dictht结构，6.2中两个dictht结构中
// 的size属性被挪到这里，用一个数组的两个元素来表示
signed char ht_size_exp[2]; /* exponent of size. (size = 1<<exp) */
};
*type由于字典结构被用在多个地方，比如Redis的整体“键值对”用字典，hash存储类型中的“值”也是一个一个的“键值对”，它同样也是使用这个字典结构来保存，哨兵模式中，也是用字典来存储管理所有的master节点和slave节点。虽然它们都是用字典结构存，但具体肯定有所区别的，而这个*type就是用来指向字典在具体的应用场景下特定的处理函数的；**ht_table[2]指向两个ht_table数组，ht_table数组中的元素都是指针，用于指向dictEntry类型的元素；ht_used[2]由于7.0取消了dictht结构，6.2中两个dictht结构中的used字段就放到了这里，表示已经存了几个元素；rehashidx用于标记rehash到哪个元素，idx就是index，即索引，当没有rehash时，它的值为-1；pauserehashrehash停止标记，如果大于0表示停止，小于0表示错误，等于0表示未停止；ht_size_exp[2]由于7.0取消了dictht结构，6.2中两个dictht结构中的size字段就放到了这里，但跟6.2的dictht不同的是，这里并不是直接存size，而是存的size的指数n，因为size总是2n，使用时通过把1左移n位得到size值(1左移n位就是2n)，同理sizemmask也是通过size-1得到，相关的两个函数是宏函数，在7.0版本的dict.h文件第76和77行#define DICTHT_SIZE(exp) ((exp) == -1 ? 0 : (unsigned long)1<<(exp)) #define DICTHT_SIZE_MASK(exp) ((exp) == -1 ? 0 : (DICTHT_SIZE(exp))-1)
哈希表结构体(7.0中已去掉)
typedef struct dictht {
dictEntry **table;
unsigned long size;
unsigned long sizemask;
unsigned long used;
} dictht;
table是一个数组，该数组中的元素都是指针，**table是一个二级指针，它指向table数组，由于数组中的每项元素都是一个指向dictEntry的指针，所以你可以这么理解(dictEntry*) *table，这样的话，*table是一个指针，用于指向一个数组，数组中的每个元素都是dictEntry*类型的指针(即指向dictEntry结构体的指针)；size记录哈希表的大小(即table数组的大小)，该值一定是2n，原因是为了把取模转换成位运算，在用“按位与”做取模运算中有说到；sizemask该值永远等于size-1，原因是为了把取模转换成按位与运算，因为这个属性和哈希值一起可以决定一个键应该被放到table数组的哪个索引上。取模转换为按位与运算，前面用“按位与”做取模运算已经讲的很清楚了，这也是为什么sizemask=size-1的原因；used哈希表已有条目数(即dictEntry数量)，used/size就是load factor(装载因子)，装载因子越大，说明哈希冲突概率越高。
字典条目(dictEntry)结构体
typedef struct dictEntry {
void *key;
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
struct dictEntry *next;
// 7.0就增加了该属性，其它没变
void *metadata[];
} dictEntry;
*key用于指向Redis“键值对”中的“键”，比如set name Jack，key就是“name”，又比如hset user name "张三" age 18 gender 1，那么key就是“name,age,gender”，注意由于整个键值对空间就是一个字典，而五种类型中的hash类型也是一个字典，所以这个key既可以指整个Redis空间的key，也可以指hash类型value中的key；v是一个共用体类型，根据前面共用体(联合体)所说，由于v中的多个属性不需要共同使用，它每次只会用到其中的一个，所以就可以用共用体以节省内存。比如当dictEntry用作key=>value结构时，v.*val指向一个RedisObject，而当用于记录整个dictEntry的过期时间时，v.u64用于保存key的过期时间，这个可在db.c中的void setExpire函数中找到它的使用；*next它是一个指针，用于指向下一个字典条目(即dictEntry)。前面hash表原理与哈希冲突有提到，当发生哈希冲突时，Redis是使用“链地址法”来解决冲突的，即所有具有被分配到相同地址的dictEntry会组成一个单链表，而next就是单链表中指向下一个节点的指针；
字典初始化过程
Redis6.2
/* Reset a hash table already initialized with ht_init().
* NOTE: This function should only be called by ht_destroy(). */
static void _dictReset(dictht *ht)
{
ht->table = NULL;
ht->size = 0;
ht->sizemask = 0;
ht->used = 0;
}
/* Create a new hash table */
dict *dictCreate(dictType *type, void *privDataPtr)
{
dict *d = zmalloc(sizeof(*d));
_dictInit(d,type,privDataPtr);
return d;
}
/* Initialize the hash table */
int _dictInit(dict *d, dictType *type, void *privDataPtr)
{
_dictReset(&d->ht[0]);
_dictReset(&d->ht[1]);
d->type = type;
d->privdata = privDataPtr;
d->rehashidx = -1;
d->pauserehash = 0;
return DICT_OK;
}
Redis7.0
/* Reset hash table parameters already initialized with _dictInit()*/
static void _dictReset(dict *d, int htidx)
{
d->ht_table[htidx] = NULL;
d->ht_size_exp[htidx] = -1;
d->ht_used[htidx] = 0;
}
/* Create a new hash table */
dict *dictCreate(dictType *type)
{
dict *d = zmalloc(sizeof(*d));
_dictInit(d,type);
return d;
}
/* Initialize the hash table */
int _dictInit(dict *d, dictType *type)
{
_dictReset(d, 0);
_dictReset(d, 1);
d->type = type;
d->rehashidx = -1;
d->pauserehash = 0;
return DICT_OK;
}
字典初始化函数调用过程：dictCreate -> _dictInit -> _dictReset，_dictReset()函数中我们可以看到，无论是6.2还是7.0，它们对应的table或ht_table都被初始化为空值。
redis key过期原理
redis key的过期时间，是设置在dictEntry共用体中的uint64_t u64这个属性中的。
Redis是通过db.c中的void setExpire函数来设置key的过期时间
/* Set an expire to the specified key. If the expire is set in the context
* of an user calling a command 'c' is the client, otherwise 'c' is set
* to NULL. The 'when' parameter is the absolute unix time in milliseconds
* after which the key will no longer be considered valid. */
void setExpire(client *c, redisDb *db, robj *key, long long when) {
dictEntry *kde, *de;
/* Reuse the sds from the main dict in the expire dict */
kde = dictFind(db->dict,key->ptr);
serverAssertWithInfo(NULL,key,kde != NULL);
de = dictAddOrFind(db->expires,dictGetKey(kde));
// 设置过期时间
dictSetSignedIntegerVal(de,when);
int writable_slave = server.masterhost && server.repl_slave_ro == 0;
if (c && writable_slave && !(c->flags & CLIENT_MASTER))
rememberSlaveKeyWithExpire(db,key);
}
可以看到它最终是调用这句来设置过期时间的
dictSetSignedIntegerVal(de,when);
上边的函数的函数体在dict.h第124行，如下所示，可以看到它是把时间设置到dictEntry共用体中的s64字段中的
#define dictSetSignedIntegerVal(entry, _val_) \
do { (entry)->v.s64 = _val_; } while(0)
新节点添加到哈希链头部
Redis6.2的dict.c中dictAddRaw函数是用于添加dictEntry字典项(字典条目)的函数，该函数只添加key，不添加value(留给用户来添加)
dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing)
{
long index;
dictEntry *entry;
dictht *ht;
if (dictIsRehashing(d)) _dictRehashStep(d);
/* Get the index of the new element, or -1 if
* the element already exists. */
// _dictKeyIndex()函数会计算该元素应该被插入到哈希table的第几个元素中(即计算出index值)
// 如果元素已存在
if ((index = _dictKeyIndex(d, key, dictHashKey(d,key), existing)) == -1)
return NULL;
/* Allocate the memory and store the new entry.
* Insert the element in top, with the assumption that in a database
* system it is more likely that recently added entries are accessed
* more frequently. */
ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
// 给新条目(entry)分配内存
entry = zmalloc(sizeof(*entry));
// 把entry的下一个元素指向table[index]
entry->next = ht->table[index];
// 再把entry赋值给table[index]，其实就是把元素插到table[index]元素哈希链的头部
// 因为新添加的元素被使用的可能性更大，所以要往哈希链的头部添加新元素
ht->table[index] = entry;
ht->used++;
/* Set the hash entry fields. */
dictSetKey(d, entry, key);
return entry;
}
其实它的这段注释也有说明，大概意思就是说：把元素插入到头部，假定在一个数据库系统中，新添加的元素(条目)更有可能被经常访问
/* Allocate the memory and store the new entry.
* Insert the element in top, with the assumption that in a database
* system it is more likely that recently added entries are accessed
* more frequently. */
rehash(重哈希)
由前面Redis宏观结构中的示意图可知，每一个“键值对”都是一个字典条目（dictEntry)，这些字典条目是被一个叫dictEntry的数组所映射的。
由于我们设置的“键值对”会越来越多，所以字典条目(dictEntry)会越来越多，而dicEntry数组容量是有限的，它的初始长度是4，这个值可以在dict.h-6.2第105行或dict.h-7.0第110行找到(7.0中没有直接给出，而是用1左移的方式计算获得)，如果每个元素都指向一个dictEntry，那它最多能指向4个，所以肯定会出现多个值被分配到同一个数组下标(反过来理解，就是同一个数组元素可能指向多个dictEntry)，这个就叫哈冲突。
Redis的解决办法是把被分配到同一下标的dictEntry用指针串起来，组成一个单链表，当我们使用Redis命令查询某个key的值时，如果该key对应的值不唯一(而是一个链表)，则需要循环遍历链表，把命令中的key与链表中每个dictEntry的key进行对比，直到匹配上，才返回该dictEntry中的value值。
dictEntry数组如下图所示
假设我们数组长度保持4不变，我们设置了400个键值对，那么平均一个数组元素就要指向100个dictEntry(当然实际上肯定不是平均，而是有多有少)，这100个dictEntry会组成一个单链表，由于在链表上查找需要循环匹配，元素越多，它的查找时长就越长，链表查询复杂度为O(n)。
解决这个问题的办法就是对数组进行扩容，如果我们把数组数量扩展为28=256，那么400个元素分配到256个元素上，一个元素分两个都不够分，肯定有些元素分到一个，有些元素分到两个，当然事实上可能没有这么平均，可能出现有些元素没有分配到，但有些分配到3个，但无论如何，每个数组元素指向的单链表只有一两个元素，查找消耗的时长大大减小。
我们知道，每个key被映射到哪个数组元素上，是通过把key转为整数后再对数组的长度进行取模，可是数组长度变长了，对数组取模后它的位置就变了，所以必须在数组扩容后，把之前的dictEntry全部再重新做一遍哈希并对新的数组长度进行取模，以把它们映射到新的位置上，这个过程就叫rehash(重哈希)。
可是，如果在rehash的过程中又有查找数据的需求，而被查找的那个数据很可能还没有做rehash，这样就会导致找不到那个key，那就只能等rehash过程结束再允许查找，这样表现出来就是查找时间变长，变慢，要知道Redis可能上几百万几千万甚至上亿的key，要完成整个rehash过程是需要一定的时间的，怎么解决这个问题呢？
Redis的方法是不扩展原来的数组，而是新建一个新长度的数组(在6.2版本来说，就是ht[1])，这个在Redis宏观结构中可以看到，6.2中有两个dictht，一个指向实际的数组，一个指向NULL，而7.0中ht_table也是有两个元素，一个指向实际数组，另一个指向NULL。拿6.2来说，现在就是要让指向NULL的那个指针指向新数组(ht[1])，然后把原数组(ht[0])中的元素全部rehash(重哈希)到新数组(ht[1])中。
并且Redis并不是一次性把所有ht[0]中的元素rehash到ht[1]中，而是把这个操作分散到redis的各个增删改查操作中，这个叫渐进式hash(incremental hash)，在6.2版本的dict.c第282行中有一个_dictRehashStep函数，该函数是进行“一步”rehash操作，它其实就是调用dictRehash函数，并把第二个参数n设置为1，意思是进行一步rehash，如下所示
static void _dictRehashStep(dict *d) {
if (d->pauserehash == 0) dictRehash(d,1);
}
然后我们在该文件内搜索_dictRehashStep，你会发现有以下函数都调用了_dictRehashStep函数，
dictAddRaw -- 添加dictEntry
dictGenericDelete --删除dictEntry
dictFind -- 查找dictEntry
dictGetRandomKey -- 随机返回一个dictEntry
dictGetSomeKeys -- 随机返回多个dictEntry
这就说明了rehash被分配到各种操作中，它们会在做该操作之前判断当前是否正在进行rehash，如果是，它就会先进行一次rehash，再做它本身的操作，这样的话像查询一个key，由于是先做rehash，就不怕因为数组扩容导致找不到它了。
还记得这个dict结构体吗？它的rehashidx(rehash index)属性就是用来标记当前已经rehash到哪儿了，其实它就是ht[0]数组中的下标，rehash是从ht[0]数组的0下标开始的，即rehashidx最开始是被设置为0的，在6.2版本中，是在dict.c文件第142行的_dictExpand函数最后会执行d->rehashidx = 0
// 6.2
typedef struct dict {
dictType *type;
void *privdata;
dictht ht[2];
long rehashidx; /* rehashing not in progress if rehashidx == -1 */
int16_t pauserehash; /* If >0 rehashing is paused (<0 indicates coding error) */
} dict;
Rehash操作最终是在dictRehash函数中进行的(_dictRehashStep函数会调用dictRehash)，在6.2版本中，该函数是在dict.c的第202行，以下是dictRehash函数源码(6.2版本)
// 传进来的参数，第一个就是要进行rehash的字典，第二个参数
// 表示要进行几次rehash，一般都是一次，因为是渐进式rehash
int dictRehash(dict *d, int n) {
int empty_visits = n*10; /* Max number of empty buckets to visit. */
// 如果不是正在进行rehash，返回0，表示当前未进行rehash
if (!dictIsRehashing(d)) return 0;
// 当ht[0].used不为0，即存在dictEntry元素时，进行n步rehash
while(n-- && d->ht[0].used != 0) {
dictEntry *de, *nextde;
/* Note that rehashidx can't overflow as we are sure there are more
* elements because ht[0].used != 0 */
// 由于rehashidx就是用于指示dictht数组的下标用的，下标当然不能超过数组的size，否则就报错了，所以这里用assert(断言)数组的大小(size)是大于rehashidx的
assert(d->ht[0].size > (unsigned long)d->rehashidx);
// 如果当前元素(一般叫bucket)为空，那就不需要rehash
while(d->ht[0].table[d->rehashidx] == NULL) {
// rehashidx++，直接挪到下一个元素
d->rehashidx++;
// empty_visits用于控制连续的空元素，就是当dictht指向的数组中有连续10个元素都是空的，
// 那么就停止rehash，并返回1，表示正在rehash，为什么要这样呢？因为rehash是分散到每一
// 步具体的操作中的(增删改查操作)，你不能在一步操作中就把rehash全部给做完，因为如果table
// 中有数据的话，其实只要对该元素中的dictEntry单链表中的所有dictEntry进行rehash，现在由
// 于是空，所以就多判断几个，但如果10个元素都为空，那么也不能一直这么判断下去，而是把接下来
// 的工作交给下一次操作
if (--empty_visits == 0) return 1;
}
// 获取ht[0]数组中下标为rehashidx的元素(rehashidx从0开始)
de = d->ht[0].table[d->rehashidx];
/* Move all the keys in this bucket from the old to the new hash HT */
// 由于de是一条单链表，所以需要循环它，把它的每个元素(dictEntry)进行rehash
while(de) {
uint64_t h;
// 先获取de的下一个元素
nextde = de->next;
/* Get the index in the new hash table */
// 通过dictHashKey()函数把key转为整型，然后与sizemask(size-1)做
// 按位与操作完成取模运算(这个在前面《用“按位与”做取模运算》中有说原理)
h = dictHashKey(d, de->key) & d->ht[1].sizemask;
// 因为前面已经获取过下一个元素了，所以这里让de的next指向ht[1]中的已有数据
de->next = d->ht[1].table[h];
// 然后把整个de赋值给ht[1]数组中的相应元素，其实前面这几句加起来，就是
// 向ht[1]数组中对应元素的头部插入一个dictEntry，毕竟它是一个单链表
d->ht[1].table[h] = de;
d->ht[0].used--;
d->ht[1].used++;
de = nextde;
}
// 把ht[0]数组中下标为rehashidx的元素设置为NULL，即当一个数组元素
// (一般叫bucket)中的dictEntry链表完成rehash之后，就让它指向NULL
d->ht[0].table[d->rehashidx] = NULL;
// 然后把下标自加，就是挪到下一个下标
d->rehashidx++;
}
/* Check if we already rehashed the whole table... */
// 当ht[0]的used值为0时，说明它上面的元素已经全部搬到ht[1]中了
if (d->ht[0].used == 0) {
// 所以就可以释放掉ht[0]的table数组了，不要让它空占内存
zfree(d->ht[0].table);
// 这句其实是把ht[1]重新变为ht[0]，毕竟平时主要使用ht[0]，ht[1]相当于只是rehash时倒腾数据用的
d->ht[0] = d->ht[1];
// 最后把ht[1]reset一次，它又变为空了，又可以等待下次rehash了
_dictReset(&d->ht[1]);
// 把rehashidx设置为-1，表示rehash已经完成了
d->rehashidx = -1;
// return 0表示没有正在进行rehash操作
return 0;
}
/* More to rehash... */
// return 1说明正在进行rehash操作
return 1;
}
扩容条件：看函数中的注释
/* Expand the hash table if needed */
static int _dictExpandIfNeeded(dict *d)
{
/* Incremental rehashing already in progress. Return. */
// 如果正在扩容，则不允许扩展，直接返回DICT_OK
if (dictIsRehashing(d)) return DICT_OK;
// 当size为0时，扩展为初始大小DICT_HT_INITIAL_SIZE(其实就是4，在dict.h中有它的宏定义)
// 这个其实就是在最开始使用，一个键都没有设置的时候使用的
if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);
/* If we reached the 1:1 ratio, and we are allowed to resize the hash
* table (global setting) or we should avoid it but the ratio between
* elements/buckets is over the "safe" threshold, we resize doubling
* the number of buckets. */
// 当used(已有的dictEntry数)大于等于ht[0]数组的大小，并且符合其它条件时
// (比如dict_can_resize设置为1时，或used/size的比值大于强制resize的比率时)
// dict_force_resize_ratio这个值在dict.c文件中可以搜索到，它的值是5，即已有
// dictEntry数为数组长度的5倍时，会强制扩容(当然这个强制扩容需要内存允许才行，
// 所以有dictTypeExpandAllowed()函数来检测，因为有时候扩容需要内存比较多)
if (d->ht[0].used >= d->ht[0].size &&
(dict_can_resize ||
d->ht[0].used/d->ht[0].size > dict_force_resize_ratio) &&
dictTypeExpandAllowed(d))
{
// 扩展的容量为used+1，有些人可能会觉得奇怪，为什么辛辛苦苦扩展容量，却只扩展了一个容量呢？
// 其实并不一定是，因为如果是强制扩容的话，它其实是扩容了5倍了
return dictExpand(d, d->ht[0].used + 1);
}
return DICT_OK;
}
重哈希完成后，ht[1]会变成ht[0]
缩容：缩容的话，是缩容到used值(即当前dictEntry数)，6.2版本中，在dict.c第129行
/* Resize the table to the minimal size that contains all the elements,
* but with the invariant of a USED/BUCKETS ratio near to <= 1 */
int dictResize(dict *d)
{
unsigned long minimal;
if (!dict_can_resize || dictIsRehashing(d)) return DICT_ERR;
minimal = d->ht[0].used;
if (minimal < DICT_HT_INITIAL_SIZE)
minimal = DICT_HT_INITIAL_SIZE;
return dictExpand(d, minimal);
}
缩容条件：server.c文件中：databasesCron→tryResizeHashTables→htNeedsResize，最终在htNeedsResize函数中
int htNeedsResize(dict *dict) {
long long size, used;
// 即：ht[0].size+ht[1].size
size = dictSlots(dict);
// 即：ht[0].used+ht[1].used
used = dictSize(dict);
// 最后这里缩容条件，首先size肯定要大于初始长度DICT_HT_INITIAL_SIZE，否则根本没必要缩，因为DICT_HT_INITIAL_SIZE才4，已经是最小长度了
// 其次是used/size的100倍小于HASHTABLE_MIN_FILL(这个值在server.h文件中能搜索到，是10)
return (size > DICT_HT_INITIAL_SIZE &&
(used*100/size < HASHTABLE_MIN_FILL));
}
RedisObject
RedisObject结构体解析
前面Redis存储原理概述中说过，Redis“键值对”中的“值”都是保存到一个RedisObject中的，即无论Redis的值是简单的string，还是复杂的list,hash,set,zset，它们都被抽象为一个RedisObject，具体的数据再由RedisObject中的*ptr指针来指向。
RedisObject示意图，其中的encoding来自server.h中第827行
编码方式除了上图中的10种，还有zipmap, linkedlist已经不使用了，而ziplist和listpack写在一起，是因为在6.2中还没有listpack，而在7.0中已经使用listpack代替ziplist了，就是说ziplist和listpack只能二者选其一。
RedisObject源码在server.h(7.0)的第850行(或server.h(6.2)的第674行)
typedef struct redisObject {
unsigned type:4;
unsigned encoding:4;
unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
* LFU data (least significant 8 bits frequency
* and most significant 16 bits access time). */
int refcount;
void *ptr;
} robj;
typedef：用于定义一个自定义的类型，比如以下命令，把unsigned int定义成一个UINT类型，这样可以起到简化代码的作用
/* 定义一个uint类型 */
typedef unsigned int UINT；
/* 用UINT定义变量，就相当于是 unsigned int */
UINT a,b,c;
知道typedef的含义之后，再来看前面的代码，其实可以把它分成两部分写(只不过一般都写在一起)
/* 先定义一个redisObject结构体 */
struct redisObject {
unsigned type:4;
unsigned encoding:4;
unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
* LFU data (least significant 8 bits frequency
* and most significant 16 bits access time). */
int refcount;
void *ptr;
}
/* 然后定义一个结构体类型的类型，名为：robj */
typedef struct redisObject robj;
unsigned type:4用于表示Redis的五种数据类型，即string,list,hash,set,zset。冒号表示位域，就是它的值比较小，用一个int 32位来存放会浪费很多空间，所以就用位域，表示多个属性共用一个字节，结构体中共享位域的多个属性必须是相同类型(在这里都是unsigned，它是unsigned int的简写)，这里type占4位，共可表示24=16种类型，当然目前只有五种类型；unsigned encoding:4用于表示五种数据类型的底层数据结构，长度也是4位，共可表示24=16种编码；unsigned lru:LRU_BITS定义一个unsigned int类型的lru属性，长度是LRU_BITS位，那LRU_BITS是多少呢？其实在源码server.h第843行中有定义，就是24bit(3个字节)。该属性用于记录该redisObject上次被访问的时间，这个时间可以在垃圾回收时，如果服务器开启了maxmemory选项且内存淘汰策略选择的是allkey-lru或者volatile-lru，当服务器占用的内存超过maxmemory选项所设置的上限时，空转时长较高的那部分键值将会优先被服务器释放，进而回收内存；int refcount引用计数，占4个字节(因为int型占4个字节)，redis为了节省内存，当一些对象重复出现时，不会创建新对象，而是将它的引用计数+1，比如一个string类型的value和一个set类型中的某个元素value是一样的，那它们就会共享同一个RedisObject对象，当引用计数为0时，说明这个对象没有被使用，就可以销毁了，不过目前只支持整数值对象的共享(因为非整数类型，特别是复合类型，判断两个值是否相等的复杂度时间比较大,O(n)或O(n2)，不值得去做这个事情，所以一般重复创建一个，用空间换时间)；void *prt真实数据地址指针，指向一个sds字符串对象，在32位系统中占4个字节，在64位系统中占8个字节(现在几乎都是64位系统了，所以都是8字节)；
一个redisObject的大小为16字节
4bits type + 4bits encoding + 24bits lru + 4Bytes refcount + 8Bytes *ptr = 32bits + 12Bytes = 4Bytes+12Bytes = 16Bytes(字节)
几个词的缩写：
LRU: Least Recently Used，最近最少使用
LFU: Least Frequently Used，最不经常使用
MRU: Most Frequently Used，最经常使用
lsb: least significant bit，二进制中的低位(在左侧)，比如least significant 8 bits就是低8位的意思
msb: most significant bit，二进制中的高位(在右侧)
创建一个redisObject(object.c第42行)
robj *createObject(int type, void *ptr) {
robj *o = zmalloc(sizeof(*o));
o->type = type;
o->encoding = OBJ_ENCODING_RAW;
o->ptr = ptr;
o->refcount = 1;
/* Set the LRU to the current lruclock (minutes resolution), or
* alternatively the LFU counter. */
if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
o->lru = (LFUGetTimeInMinutes()<<8) | LFU_INIT_VAL;
} else {
o->lru = LRU_CLOCK();
}
return o;
}
关于Redis键的类型的问题
前面说了Redis的键都是sds类型，但是实际情况可能更复杂一点，因为它在代码中有时候是redisObject类型，下面我们拿集合命令sadd来说明。
我们要向集合添加一个元素，是这样添加的：
sadd set1 ele1 ele2 ele3
其中“sadd”是向集合添加元素的命令，“set1”是key，ele1,ele2,ele3都是要设置进去的集合元素，在编程语言里面，获取命令中的参数，一般都有两个变量：argv和argc，其中arg表示arguments，即“参数”，argv中的v表示value，argc中的c表示count，所以其实argc表示的是参数个数(参数分隔符为空格)，而argv就是一个数组，数组中的每个元素，刚好就是命令中的每个元素，比如在上边的命令中，sadd就位于argv[0]，set1就位于argv[1]，后面三个分别为argv[2],argv[3],argv[4]。
我们来看一下，sadd这个命令到底是怎么执行的，sadd命令调用的其实就是t_set.c文件中的“saddCommand”函数
void saddCommand(client *c) {
robj *set;
int j, added = 0;
// 先查看一下key在不在，c->argv[1]就是key，我们发现c是client结构体类型
set = lookupKeyWrite(c->db,c->argv[1]);
if (checkType(c,set,OBJ_SET)) return;
if (set == NULL) {
set = setTypeCreate(c->argv[2]->ptr);
dbAdd(c->db,c->argv[1],set);
}
for (j = 2; j < c->argc; j++) {
if (setTypeAdd(set,c->argv[j]->ptr)) added++;
}
if (added) {
signalModifiedKey(c,c->db,c->argv[1]);
notifyKeyspaceEvent(NOTIFY_SET,"sadd",c->argv[1],c->db->id);
}
server.dirty += added;
addReplyLongLong(c,added);
}
继续看一下client结构体，它在server.h中，这个结构体的属性非常多，我就不粘贴过来了，但是在它的开头往下几行，就能看到argv属性，它是这样的
robj **argv;
也就是说，这个argv属性被Redis封装成了一个robj类型的指针数组，就是说argv是一个数组，它的每个元素都是一个robj类型的指针(都指向一个robj类型的变量)，所以刚刚前面那个c->argv[1]就是一个robj类型的变量(只不过这个变量是一个指针)。
我们继续跟踪进lookupKeyWrite()函数里，发现它调用的是另一个函数，但是通过它接收的函数参数，我们发现key是一个robj类型的指针(而不是sds)
robj *lookupKeyWrite(redisDb *db, robj *key) {
return lookupKeyWriteWithFlags(db, key, LOOKUP_NONE);
}
继续跟进lookupKeyWriteWithFlags函数里
robj *lookupKeyWriteWithFlags(redisDb *db, robj *key, int flags) {
expireIfNeeded(db,key);
return lookupKey(db,key,flags);
}
继续跟lookupKey函数，我们发现，它是把key->ptr传给了dictFind函数的第二个参数，而由于key从前面传进来时，就是一个robj类型的指针，所以key->ptr其实就是redisObject结构体中的那个ptr属性所指向的值
robj *lookupKey(redisDb *db, robj *key, int flags) {
dictEntry *de = dictFind(db->dict,key->ptr);
if (de) {
robj *val = dictGetVal(de);
/* Update the access time for the ageing algorithm.
* Don't do it if we have a saving child, as this will trigger
* a copy on write madness. */
if (!hasActiveChildProcess() && !(flags & LOOKUP_NOTOUCH)){
if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
updateLFU(val);
} else {
val->lru = LRU_CLOCK();
}
}
return val;
} else {
return NULL;
}
}
我们继续跟dictFind函数
dictEntry *dictFind(dict *d, const void *key)
{
dictEntry *he;
uint64_t h, idx, table;
if (dictSize(d) == 0) return NULL; /* dict is empty */
if (dictIsRehashing(d)) _dictRehashStep(d);
// key最终被用在这里
h = dictHashKey(d, key);
for (table = 0; table <= 1; table++) {
idx = h & d->ht[table “” not found /]
.sizemask;
he = d->ht[table “” not found /]
.table[idx];
while(he) {
if (key==he->key || dictCompareKeys(d, key, he->key))
return he;
he = he->next;
}
if (!dictIsRehashing(d)) return NULL;
}
return NULL;
}
再跟进去dictHashKey函数，最终发现它是一个宏函数，最终调用的是hashFunction，这个函数是客户端自定义的函数
#define dictHashKey(d, key) (d)->type->hashFunction(key)
跟到这里，我们发现，这个key最初传进来时，是redisObject类型的，而不是sds类型的，但这仅仅只是查找key的时候，用的是RedisObject类型，而存储的时候是存的sds类型，关于这个，这篇文章有说到。
那怎么证明Redis的key在存储的时候是用的sds类型呢？
我们可以在所有文件中搜索“dictFind”函数，因为dictFind函数的作用，就是在给定的字典(参数1)里查找给定的key(参数2)，可以发现，所有调用dictFind的地方，都可以找到它的第二个参数就是sds类型，说明Redis存储key的时候用的就是sds类型。
比如哈希类型中的hashTypeGetFromHashTable这个函数
sds hashTypeGetFromHashTable(robj *o, sds field) {
dictEntry *de;
serverAssert(o->encoding == OBJ_ENCODING_HT);
de = dictFind(o->ptr, field);
if (de == NULL) return NULL;
return dictGetVal(de);
}
又比如集合类型中的setTypeIsMember函数
int setTypeIsMember(robj *subject, sds value) {
long long llval;
if (subject->encoding == OBJ_ENCODING_HT) {
return dictFind((dict*)subject->ptr,value) != NULL;
} else if (subject->encoding == OBJ_ENCODING_INTSET) {
if (isSdsRepresentableAsLongLong(value,&llval) == C_OK) {
return intsetFind((intset*)subject->ptr,llval);
}
} else {
serverPanic("Unknown set encoding");
}
return 0;
}
就包括前面sadd命令跟进来，到lookupKey的时候，它也是调用这句
dictEntry *de = dictFind(db->dict,key->ptr);
这个key->ptr，从前面我们知道这里的这个“key”是一个redisObject类型对象，而由于key本质上是字符串，所以redisObject类型对象的ptr指针实际上是指向一个sds类型字符串的。
综上所述，Redis的key存储的是sds类型的，只不过在处理客户端命令的时候，传进来时统一用了redisObject类型而已。
sds(简单动态字符串)
什么是sds？
我们知道，redis中的key也好，value也好，基本上都是两种类型，要么是整型，要么是字符串(即使是list, hash, set类型，它里面的元素最终还是整型或字符串)，所以理解字符串在Redis中是怎么存的，非常重要！
Redis中的字符串是一种自定义的结构体类型字符串，叫sds，是simple dynamic string的首字母缩写，中文翻译为“简单动态字符串”。
C语言中的字符串
C语言的字符串必须使用数组来存，就算用字面量的方式，它本质上也是数组存的
#include <stdio.h>
#include <string.h>
// 计算字符串数组长度
int get_length(char str[])
{
char *p = str;
int count = 0;
// *p++就是*(p++)，就是地址自增1，就是移动到下一个地址
while (*p++ != '\0')
{
count++;
}
return count;
}
int main(){
// ======= C语言创建字符串方式1:字面量方式 =======
// 字面量方式创建字符串数组，它会自动在最后加一个0作为
// 结束符，0是ASCII码，是null的意思，转成二进制就是8个0
char str1[] = "hello world";
// ======= C语言创建字符串方式2:数组方式 =======
// 数组方式创建字符串数组1，需要自己加null结束符
char str2[] = {'h', 'e', 'l', 'l', 'l', ' ', 'w', 'o', 'r', 'l', 'd', 0};
// ======= C语言创建字符串方式3:数组方式 =======
// 数组方式创建字符串数组2，需要自己加null结束符，因为用了引号，所以要写成\0
char str3[] = {'h', 'e', 'l', 'l', 'l', ' ', 'w', 'o', 'r', 'l', 'd', '\0'};
// ======= C语言创建字符串方式4:指针方式 =======
// 指针方式本质上是指向字符串数组的第一个元素
char *str4 = "hello world";
// 打印三个字符串
printf("%s\n", str1);
printf("%s\n", str2);
printf("%s\n", str3);
printf("%s\n", str4);
// ====== C语言计算字符串长度方法1 ======
size_t len = strlen(str1);
printf("%zu\n", len);
// ===== C语言计算字符串长度方法2 ======
// 计算数组长度，sizeof()函数是计算字节长度，由于一个char字符占一
// 个字节，所以获取到的字节数就是长度刚好就是字符串长度
int len2 = sizeof(str1) / sizeof(char) - 1;
printf("%d\n", len2);
// 如果不是char类型，比如如果是int类型，则需要除以sizeof(int)来获取字符串长度，
// 而sizeof(int)就不是1了，而是4. 而且由于数字不是字符串，并不需要0结束符，所以不用减1
int arr[] = {1, 2, 3, 4, 5};
int len3 = sizeof(arr) / sizeof(int);
printf("%d\n", len3);
// 使用自定义的函数获取字符串长度，本质是循环计数
printf("%d\n", get_length(str1));
}
把以上代码保存到test.c文件中，然后在终端中test.c所在目录下运行以下命令即可执行(必须保证当前目录下没有test文件，因为运行会生成test文件，如果之前就有，会造成冲突，无法生成)
gcc -o test test.c && ./test
由以上C代码可以看出，计算数组的方法就是
- sizeof，sizeof是C语言中的单目操作符，不是函数，它用于以字节的形式返回其操作数占用的内存大小；
- strlen，其实strlen也是循环计算，只不过是C言官方集成的而已，可以看strlen的源码：strlen.c；
- 自己用while循环计算。
sds字符串
由以上C语言中的字符串可知，C语言中的字符串其实是不方便直接使用的，要获取一个字符串长度都需要循环计算，需要消耗一定的cpu资源。
另外就是由于我们无法保证存储的字符串中没有\0，而如果直接用C语言的数组来存字符串，它遇到\0就认为是字符串结束，但实际上它遇到的\0很可能是字符串本身的内容，而不是字符串的结束，所以这样会造成无法正确读取字符串的问题。
由于以上原因，redis自己定义了一种字符串类型(sds类型)，它会把字符串长度直接存起来，要获取的时候直接返回长度就行，既不需要循环计算浪费cpu资源、浪费时间，又能防止读取字符串时读取到字符串本身的\0字符就被认为是结束，因为有长度就直接按长度来识别结尾，不再使用\0来识别结尾。
sds类型数据结构示意图如下所示，注意buf[]数组还是会使用\0作为数组的结尾，但是读取的时候会直接使用len来识别结尾，而不会识别\0，既然这样那在后面加\0干嘛呢？不要它不是更好吗？原因是这样就可以直接使用部分C语言的字符串函数，因为C语言标准数组就是有\0结尾的
sds字符串结构体源码
以下sds字符串类型的结构体源码(在sds.h第43行开始)
typedef char *sds;
/* Note: sdshdr5 is never used, we just access the flags byte directly.
* However is here to document the layout of type 5 SDS strings. */
struct __attribute__ ((__packed__)) sdshdr5 {
unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
uint8_t len; /* used */
uint8_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
uint16_t len; /* used */
uint16_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
uint32_t len; /* used */
uint32_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
uint64_t len; /* used */
uint64_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
如上源码所示，为了存储不同长度的字符串，redis设置了5种结构体，分别为：sdshdr5, sdshdr8,sdshdr16, sdshdr32, sdshdr64，它们的结构都是一样的(sdshdr5略有不同后面会解释)，只是存储容量不一样，分别用于存储不同长度的字符串，因为用大容量结构体存小长度字符串，会造成很多空间浪费。
其中sds表示simple dynamic string，简单动态字符串，hdr表示header，头部信息的意思，后面的5, 8, 16, 32, 64表示二进制位数，代表它们能存储的字节数为2n-1，n就是5, 8, 16, 32, 64。
结构体成员对齐
以下C语言代码大家可以自己执行看一下
#include <stdio.h>
int main(){
double age;
printf("\ndouble类型的age变量占用内存大小: %lu 字节\n",sizeof(age));
char name;
printf("char类型的name变量占用内存大小: %lu 字节\n",sizeof(name));
char sex;
printf("char类型的sex变量占用内存大小: %lu 字节\n",sizeof(sex));
struct st1 {
char name;
double age;
char sex;
};
printf("st1结构体占用内存大小: %lu 字节\n\n", sizeof(struct st1));
}
// double类型的age变量占用内存大小: 8 字节
// char类型的name变量占用内存大小: 1 字节
// char类型的sex变量占用内存大小: 1 字节
// st1结构体占用内存大小: 24 字节
执行后可以发现，单独的三个变量，占用字节数加起来是10个字节，可是三个变量放到结构体里，却占用了24字节，这是什么？这是因为默认情况下，结构体内的变量都会以占用字节数最大的成员为准进行对齐，以上例子中，double类型在64位系统占8字节，所以两个char虽然各自只占用1字节，它也往8字节对齐，对齐是为了CPU更快读取，具体原理可以自己去查查，但是对齐会造成空间浪费，像name和sex就有7个字节是空的，都浪费掉了。
结构体不对齐
前面说了结构体默认会有成员变量对齐问题，那如果我不想对齐呢？在struct关键字和结构体名称之间添加__attribute__ ((__packed__))即可取消对齐，这样结构体就会紧凑方式排列以节省空间，再次运行以下代码你会发现，这次结构体占用的内存字节数，刚好是三个变量占用字节数之和
#include <stdio.h>
int main(){
double age;
printf("\ndouble类型的age变量占用内存大小: %lu 字节\n",sizeof(age));
char name;
printf("char类型的name变量占用内存大小: %lu 字节\n",sizeof(name));
char sex;
printf("char类型的sex变量占用内存大小: %lu 字节\n",sizeof(sex));
struct __attribute__ ((__packed__)) st1 {
char name;
double age;
char sex;
};
printf("st1结构体占用内存大小: %lu 字节\n\n", sizeof(struct st1));
}
// double类型的age变量占用内存大小: 8 字节
// char类型的name变量占用内存大小: 1 字节
// char类型的sex变量占用内存大小: 1 字节
// st1结构体占用内存大小: 10 字节
sds字符串结构体源码解析
前面说了sds字符串结构体源码，这里来解释一下源码的意思。
typedef char *sds
typedef前面讲过，用于自定义一个类型，这个类型可以是结构体，可以是已有类型，对已有类型进行定义，其实就相当于把原来的类型定义个别名，这样方便一点。所以这句就是定义了一个名为“sds”的“char指针”类型，这样的话，sds a就相当于char *a。
如下所示，执行以下代码你会发现，a和b都能存储一个字符串，其实它们类型是一样的，都是“char指针”类型
#include <stdio.h>
int main(){
typedef char *sds;
// 定义一个sds类型的a变量
sds a = "Hello World";
// 定义一个(char*)类型的b变量
char *b = "Hello World";
printf("%s ---- %s\n", a, b);
}
// Hello World ---- Hello World
uint64_t len
存储buff[]占用的字节数(不包含\0字符)，这样当需要获取字符串长度时，直接返回这个值就可以，就不需要像c语言的字符串那样需要循环统计(既浪费cpu资源又浪费时间，还会遇到\0截断问题)。
uint64_t alloc
alloc是allocate(分配的意思)，表示分配给buff[]的空间，不包括\0终止符，也就是说，如果alloc是9B，buff[]的长度实际上是10B，只不过实际存的有效字节是9B，因为最后1B是\0终止符。
为什么要分配呢？因为buf[]是一个c数组，定义数组必须预先给它分配空间，然后才能存数据。分配规则在sds.c第239行的_sdsMakeRoomFor()函数中的以下几行
// 分配规则1: newlen(新长度)默认情况下等于原长度+要增加的长度，就是要多少就申请多少内存
reqlen = newlen = (len+addlen);
assert(newlen > len); /* Catch size_t overflow */
// 分配规则2: 如果是贪婪模式，则会多“预留一部分空间”，以免造成频繁分配内存，到底要多预留多少呢？有两个规则
if (greedy == 1) {
// 分配规则2-1: 如果newlen小于SDS_MAX_PREALLOC(1M)，则直接把newlen翻倍(x2)
if (newlen < SDS_MAX_PREALLOC)
newlen *= 2;
else
// 分配规则2-2: 如果newlen大于1M，则只增加1M空间
newlen += SDS_MAX_PREALLOC;
}
其中SDS_MAX_PREALLOC在sds.h第36行有定义，如下所示，1024*1024就是1MB
#define SDS_MAX_PREALLOC (1024*1024)
unsigned char flags
flags有两种，一种是sdshdr5的，另一种是非sdshdr5的
// sdshdr5的flags
unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
// 非sdshdr5(即sdshdr8, sdshdr16, sdshdr32, sdshdr64)
unsigned char flags; /* 3 lsb of type, 5 unused bits */
它们的注释有一个共同的地方“3 lsb of type”，”3 lsb”就是“低三位”，意思是用一个字节的3位低位表示sds类型，这个类型就是redis五种数据类型中的一种：string, hash, list, set, zset，因为两位二进制最多表示4个数，不够用，所以要用3位来表示。
3 lsb(低三位)如下图所示
低三位表示的类型如下
| 二进制 | 具体类型 |
|---|---|
| 00000000 | sdshdr5 |
| 00000001 | sdshdr8 |
| 00000010 | sdshdr16 |
| 00000011 | sdshdr32 |
| 00000100 | sdshdr64 |
lsb: least significant bit，表示二进制数中1个字节8位中的低位(在右侧)，3 lsb就是低三位。
msb: most significant bit，表示二进制数中1个字节8位中的高位(在左侧)，5 msb就是高五位。
对于sdshdr5类型来说，sdshdr5中的5是5位二进制，它能表示的最大数为5个1(11111)，转成十进制就是25-1=31，所以它最多能保存31个字节，而flags中的高5位(即5 msb)刚好也是5位，所以这5位刚好可以用来表示sdshdr5类型保存的字符串长度。
而sdshdr8以上的类型，5位肯定存不下，所以就另外用一个len来保存它的长度，另外也由于sdshdr5最大长度才31，所以对于sdshdr5类型的字符串，直接就给它分配31个字节了，根本不需要alloc来记录给它分配了多少空间，所以为什么sdshdr5类型没有len和alloc这两个属性，就是这个原因。
其实源码中sdshdr5的注释“sdshdr5 is never used”非常误导人，这个PR中有提到，这篇文章中有详细的分析，而这篇文章应该是copy前面那篇的，国外这篇文章竟然把前面那篇完全翻译成英文了。
“sdshdr5 is never used”主要是说不用在value上，sdshdr5主要是用在key的长度为1-31的时候使用(因为key长度不可能为0，而32的话，5位二进制已经存不下，所以只能是1-31)，而value的话，即使value长度小于32，也不会用sdshdr5存，原因可能是key设置了就设置了，是不可能改变的(只能删除)，而值的话是可以更新的，万一更新后长度大于31，又要改类型，因为31这个长度是很容易被超过的，与其频繁更新数据类型，不如直接用sdshdr8, 16, 32, 64等类型。
char buf[]
真正存储字符串的数组。本来C语言中定义数组，方括号里必须写上一个数字，表示这个数组的长度，但是如果这个数组作为结构体的最后一个元素的话(结构体有2个或2个以上的成员)，就可以不指定数组的长度，这叫“柔性数组”，这样就可以在使用的时候再去分配长度了。而且sizeof计算结构体大小时，是不会包括柔性数组大小的，因为它还没被分配空间，比如sizeof(struct sdshdr8)，它是不包括buf[]数组的大小的，无论这个数组是什么类型(事实上它也可能是一个结构体类型)。
为什么要在使用的时候分配长度呢？因为像sdshdr16，它能保存的最多字节数为232-1 = 4294967296，即42.9亿个字节的数据，但你不可能一开始就给它分配65535个字节，万一存不了这么多，那就白白浪费这么多内存，所以都是设置字符串的时候，按字符串长度来分配，如果修改了值，且修改后的字符串变长了，则根据一定的规则来扩展容量，这个在前面“uint64_t alloc”中有说到。
uint64_t
这是一个数据类型，但它不是新类型，还记得上边提到过的typedef吗？uint64_t其实就是unsigned long long类型(就是64位的int型)，后面的_t表示是用typedef定义的，因为太长了不太方便，所以用typedef重新定义一个别名。
根据字符串长度决定类型
由上边的源码可以看到，redis分别定义了多种不同长度的sds类型，并通过sdsReqType第60行的sdsReqType函数判断字符串的长度以决定使用哪个长度的sds类型
static inline char sdsReqType(size_t string_size) {
if (string_size < 1<<5)
return SDS_TYPE_5;
if (string_size < 1<<8)
return SDS_TYPE_8;
if (string_size < 1<<16)
return SDS_TYPE_16;
#if (LONG_MAX == LLONG_MAX)
if (string_size < 1ll<<32)
return SDS_TYPE_32;
return SDS_TYPE_64;
#else
return SDS_TYPE_32;
#endif
}
- 其中
#开头的if else，并不是注释，而是条件编译，意思是如果LONG_MAX == LLONG_MAX为true，它就会编译if中的语句，否则就编译else中的语句； 1<<n表示1左移n位，1左移n位，其实就是2n，比如1<<8就是28=256，string_size < 1<<8就相当于string_size < 256。
sds encoding
encoding是编码的意思，在这里指数据在redis中的实际存储类型(当然这些存储类型也是自定义的)。
Redis中的所有编码
对于Redis6.2，encoding的类型定义在server.h第652行，可以看到一共有11种，其中zipmap(压缩字典2.6.0-rc1开始弃用，改用ziplist)、OBJ_ENCODING_LINKEDLIST(双链表)已不再使用，所以其实一共有9种
/* Objects encoding. Some kind of objects like Strings and Hashes can be
* internally represented in multiple ways. The 'encoding' field of the object
* is set to one of this fields for this object. */
#define OBJ_ENCODING_RAW 0 /* Raw representation */
#define OBJ_ENCODING_INT 1 /* Encoded as integer */
#define OBJ_ENCODING_HT 2 /* Encoded as hash table */
#define OBJ_ENCODING_ZIPMAP 3 /* Encoded as zipmap */
#define OBJ_ENCODING_LINKEDLIST 4 /* No longer used: old list encoding. */
#define OBJ_ENCODING_ZIPLIST 5 /* Encoded as ziplist */
#define OBJ_ENCODING_INTSET 6 /* Encoded as intset */
#define OBJ_ENCODING_SKIPLIST 7 /* Encoded as skiplist */
#define OBJ_ENCODING_EMBSTR 8 /* Embedded sds string encoding */
#define OBJ_ENCODING_QUICKLIST 9 /* Encoded as linked list of ziplists */
#define OBJ_ENCODING_STREAM 10 /* Encoded as a radix tree of listpacks */
而对于Redis7.0，encoding的类型定义在server.h中第827行，共12种，其中ZIPMAP、LINKEDLIST、ZIPLIST这3种老类型在Redis7.0中已经不使用了，所以实际上是8种编码类型
/* Objects encoding. Some kind of objects like Strings and Hashes can be
* internally represented in multiple ways. The 'encoding' field of the object
* is set to one of this fields for this object. */
#define OBJ_ENCODING_RAW 0 /* Raw representation */
#define OBJ_ENCODING_INT 1 /* Encoded as integer */
#define OBJ_ENCODING_HT 2 /* Encoded as hash table */
#define OBJ_ENCODING_ZIPMAP 3 /* No longer used: old hash encoding. */
#define OBJ_ENCODING_LINKEDLIST 4 /* No longer used: old list encoding. */
#define OBJ_ENCODING_ZIPLIST 5 /* No longer used: old list/hash/zset encoding. */
#define OBJ_ENCODING_INTSET 6 /* Encoded as intset */
#define OBJ_ENCODING_SKIPLIST 7 /* Encoded as skiplist */
#define OBJ_ENCODING_EMBSTR 8 /* Embedded sds string encoding */
#define OBJ_ENCODING_QUICKLIST 9 /* Encoded as linked list of listpacks */
#define OBJ_ENCODING_STREAM 10 /* Encoded as a radix tree of listpacks */
#define OBJ_ENCODING_LISTPACK 11 /* Encoded as a listpack */
截止到Redis6.2和7.0，Redis的五种数据类型的底层就是用这9种(<7.0)或8种(>=7.0)编码类型来存储的，这里我们只讲sds字符串的编码，其它编码会在对应章节里讲。
int编码(sds)
我们设置了一个string类型的字符串，但字符串是纯数字，可以看到，虽然值是string类型，但内部编码其实是使用了int型存储的
127.0.0.1:6378>
127.0.0.1:6378> set name 123
OK
127.0.0.1:6378> type name
string
127.0.0.1:6378> object encoding name
"int"
127.0.0.1:6378>
由前面可知，redis中的每个值都是一个RedisObject来存储的，当然RedisObject本身只是存值的一些相关参数，比如类型(五种类型中的一种)、编码(8种编码中的一种)、引用计数等等。
而真正的值是由RedisObject中一个8字节的指针void *ptr来指向的，但一个整型数字完全没必要再通过一个8字节的指针来指向，因为8字节(64位)最大可存储264-1，这个数有多大呢？大约是1.8446×1019，什么概念呢？1010就是100亿，109就是10亿，100亿x10亿=1000亿亿，1.8446×1000亿亿=1844.6亿亿，嗯，我也不知道这到底是多大的数了，反正就是大到我们平时根本不可能存这么大的数，也就是说8个字节完全可以存放下我们在实际使用中能用到的任何一个整型数字了，而且这样做还能减少一次内存I/O，所以int型编码的值实际上是直接存储在指针位置中的。
embstr编码(sds)
emb是embed(嵌入式)，embstr就是嵌入式字符串，为什么叫嵌入式呢？我们先来看一下设置一个name字符串
set name Bruce
这是redis中最为普通不过的操作了，就是设置一个string类型，key为“name”，value为“Bruce”，由前面的RedisObject存储结构体分析可知，“Bruce”这个值并不是直接存的，它的存储结构如下图所示
按上图所示的存储结构，其实Redis存储一个value，它是需要分配两次内存的，一次用来存储RedisObject，一次用来存储sds字符串，当这个value被删除时，这两次分配的内存是需要分别释放的，即释放内存也要释放两次。
但是如果RedisObject与sds(在本例中是sdshdr8)总长度不超过64字节时，Redis会把它们俩安排在一个内存块中，即让sds字符串紧跟挨在RedisObject后面，这样就相当于把sds字符串“嵌入(英文叫embed)”到RedisObject所在的内存块中(而不是重新分配另一个内存块)。
这样做的好处就是，为这个字符串分配内存时，只需要分配一次内存就可以了，同理，销毁的时候，也只需要释放一次内存就可以了，我们知道，分配内存和释放内存都需要一定的代价的，少分配一次，少释放一次，就能多节省一点服务器资源和时间。
现在有两个问题：
- 1、总长度不超过64字节，那么实际能存储的字符串是多长呢？—— 是44字节！
- 2、为什么规定总长度不超过64字节？为什么不是32字节或128字节或者其它字节数？—— 跟CPU缓存行有关！
答问题1：RedisObject占16字节
type 4bit + encoding 4bit + LRU 24bit + refcount 4Bytes + ptr 8Bytes = 16Bytes
sds的header(非数据部分)占3字节
len 8bit + alloc 8bit + flags 8bit = 3Bytes
所以RedisObejct + sds header = 19Bytes，64-19=45Bytes，所以buf[]最多能存45字节，但是别忘了，它是使用C语言数组的方式的，它的最后有一个字节的\0，所以实际上我们能存储的字符串长度为45-1=44Bytes。
如果你不明白为什么RedisObject占16字节，可以看看前面的RedisObject结构体解析，同理，如果你不明白为什么sds header占3字节，可以看看前面的sds字符串结构体源码中的sdshdr8结构体(embstr就是用的这个结构体)。
为什么有些文章写的是39字节？
在Redis 3.2之前的版本中，由于sds并没有分多种长度，而是直接用最大长度，即8字节。而3.2开始，sds分成了多个长度，embstr中存的是sdshdr8类型的sds，8表示8bit，sdshdr8结构体占3字节，所以sds header在3.2之前比3.2之后多占用了5个字节，44-5=39，这就是为什么很多文章写着当字符串不超过39字节时会使用embstr编码，而很多人又没仔细研究，直接用网上的旧资料，以为也是39字节，他们不知道redis现在都7.0了，早就已经改了。
答问题2：因为一个CPU缓存行为64字节。
什么是“缓存行”？
CPU有一级二级(甚至三级)缓存，当CPU要处理内存中的数据的时候，并不是直接处理，而是先把它们读入CPU缓存中，而缓存是有缓存行的概念的，缓存行就是缓存中的最小存储单位，相当于硬盘有“页”的概念，一般来说，一个缓存行的大小是64字节。
当RedisObject+sds长度不大于64字节时，可被一次性读入CPU缓存行中进而被CPU处理，这样可以大大加快处理的速度，但是如果RedisObject+sds长度大于64字节，一个缓存行存不下，那就需要再次读取，这样就需要再次寻址，无法达到一次读入缓存行的速度优势。
为什么不是sdshdr16,sdshdr32，而是sdshdr8呢？因为sdsdhr8类型字符串最长为28-1=255，再除去一个字节的\0结束符，以及3个字节的sds的header，其实sdsdhr8类型能存的最长字符串为255-4=251，但缓存行只有64字节，连sdshdr8的最大长度都存不下，更别说sdshdr16和sdshdr32了，所以它会选sdshdr8类型的字符串来存，以节省空间。
embstr编码字符串是只读的
embstr编码字符串是只读的(不允许修改的)，因为在内存中sds紧紧的与RedisObject挨在一起，如果修改后的字符串比原字符串长，导致RedisObject+sds整个长度大于64字节的话，就无法被一次性读入CPU缓存行，也就失去了这么做的意义了，为了避免这种情况的发生，即使你修改后的字符串小于原字符串，它也会立即变为raw编码(后面会讲到)。
需要注意的是，编码一旦升级(int–>enmstr–>raw)，即使后期再把字符串修改为符合原内存编码的存储格式时，编码也不会回退。
embstr编码在一个缓存行中的示意图如下所示
关于RedisObject指针问题
很多人可能会想到，既然sds已经紧挨着RedisObject存了，那还需要指针来指向它吗？理论上其实是可以不用*prt指针的，但由于redis所有读取RedisObject的函数都是统一的，都是会处理指针的，如果对embstr做单独的处理，也就是不使用指针，将会需要修改大量代码来处理这个“例外”，所以即使sds就跟在RedisObject后面，这个指针还是指向sds的，可以参考这里。
raw编码(sds)
根据embstr编码(sds)可知，如果字符串长度大于44字节，那么一个缓存行就存不下了，所以就不把sds与RedisObject放在一个内存块中了(因为反正都要分两次读入)，而是分别分配两个块内存，让RedisObject的ptr指针指向sds所在的内存地址，这种编码方式就叫raw编码。
embstr编码与raw编码的区别：
- 1、分配内存：raw编码会调用两次内分配函数来分别创建redisObject结构和sds结构，而embstr编码则通过调用一次内存分配函数来分配一块连续的空间，空间中依次包含redisObject和sds两个结构；
- 2、释放内存：raw编码在释放内存时，要调用两次释放内存函数，而embstr在释放内存时只需要调用一次内存释放函数就可能；
- 3、raw编码允许修改字符串的值，而embstr编码不允许修改字符串的值。
位图(bitmap)
位图是redis的一个功能，用于进行位操作以及位运算。由于位图是完全使用sds来存储的，所以位图不算是一种数据类型，只能说它是string类型的一种应用。
我们知道string有三种编码，int, embstr, raw，那么位图是用哪种编码存储的呢？答案是raw类型，因为embstr类型是不允许修改的，一修改就会转换为raw类型，但为什么不是int类型呢？说实话我不知道！
位图占用的空间的大概值可以用(ceil(offset/8)/1024/1024)MB来计算。
setbit
设置key对应的value的第offset位的值为value(只能0或1)
setbit key offset value
- key: 就是键，你向redis设置任何数据，都必须有一个键和一个值；
- offset: 偏移(从0开始)
- value: 要设置的值，只能是0和1两种值，否则报错！
例
setbit signup_status 4 1
整个命令的意思就是，在redis中设置一个字符串，它的键是“signup_status”，它的值的第4位为1(注意这个4是从0开始数的，如果从1开始数就是第5位了)，返回值为第4位被设置为1之前的值(如果之前没有设置过，那就是0)。
getbit
获取key对应的value的第offset位(只有0和1两种值)
getbit key offset
例：
getbit signup_status 4
bitcount
bitcount即“bit count”，用于统计key对应的value中位值为1的位的个数，比如1011有三个1，那bitcount结果就是3
bitcount key
例：
bitcount signup_status
bitpos
bitpos即“bit pos”，pos是position的缩写，用于从左往右查找0或1，并返回第一个找到的0或1的位置
bitpos key bit [start] [end]
- 其中bit有两种值：0和1，代表你想找0还是找1；
- start和end代表查找范围，它们的单位是byte(redis7.0中可指定为bit)。
比如我有一个位图是这样的：1111001101100101，该位图共16位，即两个字节，分开写是这样的“11110011 01100101”。
现在我们使用bitpos执行以下命令
bitpos testbit 0
- bit为0，说明你想要从左往右查找为0的位，并返回该位在整个位图中的位置；
- 省略了start和end，说明start是0，end是整个位图占用的字节数；
- 对于1111001101100101，从左往右数，它的第1个0在第4位(从0开始数)，所以返回4，如果是
bitpos testbit 1那就返回0，因为跳过了一个字节(8位)，而第二个字节的第0位就是1，所以返回0。
例：以下命令中，第一个0，表示要从左往右查找0，并返回第一个遇到的0的位置，第二个1是start值，表示从第1个字节开始找(从0开始数)，即相当于跳过了一个字节(即跳过了前面8位，当然由于是从0开始数的，所以是跳过了0-7位，相当于从第8位开始查找)
bitpos testbit 0 1
该命令返回0，因为对于1111001101100101来说，它的第二个字节是“01100101”，它的第0位就是0，所以返回0。
注意：
- 1、对于未设置的位，如果你没有指定start值，则查0时会默认未设置的位为0，但如果指定了start值，则未设置的位会被认为不存在，从而返回-1。比如你设置了一个字节全是1(8个位全是1)，即11111111，此时你用
bitpos testbit 0去查找，它会返回8，因为前面8位(下标0-7)都是1，下标为8的位没有设置，所以默认为0。但是如果你用bitpos testbit 0 1去查，它不会返回0，而是返回-1，即跳过前面设置过的1个字节(8位)后，后面未设置的位会被认为不存在而不会被认为是0； - 2、对于未设置的key，你去查找0，永远返回0，因为默认认为该key值是0，就算start值不为0，它也返回0；
bitop
bitop是“bit op”，op是operation的缩写，表示“位操作”的意思，千万别看成“bit top”。
位操作其实就是按位运算，按位运算有：与、或、非、异或 共四种操作，分别用：AND, OR, NOT, XOR 操作符来表示。除了“非(NOT)”只接收一个参数外，其它的都可以接收多个参数。
命令格式如下
# 按位与
bitop and key1 key2 …… keyN
# 按位或
bitop or key1 key2 …… keyN
# 按位异或
bitop xor key1 key2 …… keyN
# 按位非
bitop not key
其实它就是把各个key的位做“按位与”、“按位或”、“按位异或”操作，或者把给定key做“按位非”操作。
bitfield
这个命令非常强大，可以通过设置十进制整型数字(正负数都可以)来一次性设置多个位，获取也是返回十进制数，并且可以多个命令同时使用。
# get数据
bitfield key get <type> <offset>
# set数据，value不限制0和1，可以是任意整数(包括负整数)
bitfield key set <type> <offset> <value>
# 增加数据
bitfield key incrby <type> <offset> <increment>
事实上，除bitfield key外，后面的都叫“子命令”，包括set,get,incrby，所有子命令可以一次性执行多条，混合使用都可以，比如
# 多个set一起用
bitfield key set <type> <offset> <value> set <type> <offset>
# set和get混合使用
bitfield key set <type> <offset> <value> get <type> <offset>
# incrby和get一起用
bitfield key incrby <type> <offset> <increment> get <type> <offset>
假设我要设置第1~3位为1，其实就是从第0位开始连续3位都设置成1，用bitfield命令可以这样写
bitfield test1 set u3 0 7
- “test1”是键，这个没什么好说的；
set u3 0 7是设置数据命令，我们对应一下上面的格式，可以知道u3就是<type>，0就是<offset>，7就是<value>；u3中“u”的意思是unsigned int，意思是把要存储的值以无符号整型的形式存储，而3是指设置3位，另外还有“i”开头的，i就是int，前面没有unsigned，意思就是有符号整型。即<type>参数有两种值，“uN”或“iN”，其中N是正整数，表示设置的位数，而u或i用于表示无符号或有符号整型；- offset为0表示从第0位开始设置，结合u3中的3，可以知道，是从第0位开始设置，共设置3位(其实就是设置第0,1,2这三个位)；
- “7”是要设置的值，它被设置进去之后，其实就是二进制“111”，可以分别用
getbit test1 0,getbit test1 1,getbit test1 2,getbit test1 3来查看，会发现前面三位都是1，第四位是0。
我们来获取一下上边设置的3个位，u表示unsigned int，3表示获取3位，0表示从第0位开始获取，它会返回“7”，但你要知道，7存储的时候就是存成二进制“111”的
bitfield test1 get u3 0
如果我把上边设置的7当成是有符号(i表示int，3表示获取3位)来获取
bitfield test1 get i3 0
那么它会返回多少呢？因为“111”中，第一个“1”当作符号位，我们都知道符号位为1就是负数，所以它肯定返回一个负数，后面剩下“11”就是十进制的“3”，所以它会返回“-3”吗？答案是：错！
我们知道，二进制是以补码形式存储的，正数的补码与原码相同，而负数的补码=反码+1，要知道原码，我们首先要算出反码然后把它按位取反就是原码了，根据“补码=反码+1”可知“反码=补码-1”，即：反码=11-1=10，而10取反变成原码为01，即最终它的原码是01，01就是十进制的1，加上前面的负数，就是“-1”，所以最终它会返回“-1”。
同时使用两个命令，先设置再获取的例子
bitfield testbit set u2 3 3 get u2 3
set u2 3 3，“u2”表示设置一个无符号2个二进制位的数，第一个“3”表示从第4位开始设置(从0开始数)，第二个“3”表示要设置的数字，3转成二进制就是“11”，刚好是2位。
get u2 3，“u2”表示获取一个2位二进制位的无符号整型数字，“3”表示从第4位开始获取(从0开始数)。
incrby意思是“把原来的值增加一个值”，至于增加多少呢？这是你自己决定的，你传的参数是多少它就增加多少。
比如我从第0位开始，设置一个3位无符号整型数字2
bitfield testbit2 set u3 0 2
然后我再把这个2加1(也要从第0位开始，3位无符号整型)，最终结果就是3(当然它会返回2，位图操作返回的都是操作前的数)
# 把前面设置的2加1
bitfield testbit2 incrby u3 0 1
# 获取一下，如果前面操作正确，这里应该返回3
bitfield testbit2 get u3 0
在前面已经是3的基础上，再次增加5
bitfield testbit2 incrby u3 0 5
理论上3+5=8，但是要注意，我们的前提是u3(3位unsigned int)，u3能保存的最大数是“111”，即十进制的“7”，可是现在是8，所以实际上会溢出，所以实际上它只能保存1，因为8满了减去最大值7，就剩1了，就好像时钟超过了12点，比如13点其实就是13-12=1点。
溢出规则：
- wrap：默认值，wrap是环绕的意思，对于正数，就像我前面说的时钟，超过了能存储的最大值，那就对”模”进行取模，比如三位无符号整型的模是8(23=8)，那15的话，就是对7取模：15%8=7，所以结果就是1，但如果是有符号整型的话，你就得知道环绕规律了，如下图，是使用4位二进制存储有符号的数一共能存16个数，0~7为正数，-1~-8为负数，按下图，7+1=-8，而-8-1=7，即超过负数最小值时，需要减去负数最小值，比如15，而正数越过边界，就是负数最小值，如果对-0和-8不太懂，可以看这篇文章
-
sat：sat是saturation的前三个字母，意思是“饱和”的意思，比如颜色中的“饱和度”英文就叫saturation。饱和的意思，就是不能越界，而是保持最大值或最小值，比如对于4位无符号整数，那么15就是最大值，如果你8+9=17，那么结果就会是15，多出的就丢掉了，你再怎么加，它也是15，而对于负数，就是4位二进制能表示的最小负数为-8，所以你-5-4，本来应该等于-9，但是由于最小只能存-8，所以它就会保持-8这个值
- fail：fail是失败的意思，意思是越界了就不让操作，比如4位无符号二进制，8+8=16，超过了15，那么这个操作就会被禁止，结果就是没加上，还是8。
溢出规则的使用：
溢出规则必须在可能发生溢出的命令之前使用overflow xxx来指定，一般来说，可能发生溢出的命令主要是incrby，当然set也有可能，如果你直接设置一个超出指定位存储范围的数的话
bitfield test_overflow overflow wrap set u3 0 15
以上命令最终存的是-1，因为越过了最大正数的界，如下图所示，你按顺序数过去，你会发现-1就是15，只不过它在负数区域，所以它是-1。事实上还能从二进制中来计算，比如-1在电脑中存储为1111(补码，因为电脑中存的都是补码，它的反码是1111-1=1110，按位取反1001就是原码，符号位不取反)，而1111如果按无符号算，它就是15，也就是说当符号位参与运算时，它就是对应的正数，不得不说，这真的很神奇
如果你指定溢出规则为sat(饱和)，它将会保持最大值，3位无符号二进制最大值是111，即十进制的7，所以以下命令最终设置的是7
bitfield test_overflow overflow wrap set u3 0 15
如果指定溢出规则为fail(失败)，如果会发生溢出，那么这个设置将会失败，值还是保存它原来的值，但set和incrby操作都会返回nil
bitfield test_overflow overflow fail set u3 0 15
bitfield_ro
与bitfield用法一样，只不过只能用bitfield中的获取命令(其实就是只能用get命令)，而不能用设置命令(set和incrby)，因为ro是read only的意思。
bitmap的应用
日活统计
如何统计当前系统每天登录的用户数量？
使用Redis的Bitmaps，将 系统名+日期设置为key 如zcy20211215，value中使用用户的Id做offset，用0和1记录用户在当天是否登录过，登录将对应的位设置为1。
这样做之后，每天可以得到一个Bitmaps，如果想获取某天登录过的用户数量，直接使用bitcount操作即可。
如果想统计过去30天都登录过的用户，可以使用BITOP AND操作，将那30天的Bitmaps进行“按位与”操作。
布隆过滤器：详见这里
布隆过滤器(bloom filter)，用来判断一个元素是否在一个集合中，这种算法由一个二进制数组和多个Hash算法组成。
把集合中的每一个值按照提供的Hash算法算出对应的Hash值，然后将Hash值对数组长度取模后得到需要计入数组的索引值，并且将数组这个位置的值从0改成1。在判断一个元素是否存在于这个集合中时，你只需要将这个元素按照相同的算法计算出索引值，如果这个位置的值为1就认为这个元素极大可能在集合中，否则认为绝对不在集合中。
可能存在：如果布隆过滤器所有Hash的值都是1的话，则代表这个数据可能存在，原因是可能有不同的数字经过哈希后，分配到的位置跟之前设置过的一个数字一模一样，所以即使后面那个数字并不存在，但布隆过滤器会让我们感觉它存在，这种情况叫“误判”。
一定不存在：如果布隆过滤器其中一个Hash值为0的话，则该数据一定不存在，因为存在的话，不可能有为0的情况，它一定会分配到一个索引的。
怎样降低误判率：
- 方法1:增加二进制位数，位数多，数据会更分散，不更不容易冲突；
- 方法2:增加hash次数，多个hash函数，更有可能让hash函数能让两个不同的数据产生不同的hash值，进而对应到二进制数组中的不同索引。
由于文章太长，我分成两篇来发布，下一篇为：图解+源码角度理解Redis底层原理(二)。
e.top/1821.html)。
6p