string 类型
string 是 Redis 中最基本的数据类型，Redis 是用 C 开发的，但是 Redis 中的 string 和 C 中的 string 有很大的区别。
string 类型在 Redis 中有三种存储方式：int、raw、embstr。即 这种 string 并不是字面意义上的 string。
int 格式存储
当一个 key 的 value 是整型并且 value 长度不超过 20 个字符，Redis 就将其编码为 int 类型。很显然这样做是为了节约内存。
Redis 默认会缓存 10000 个整型值（#define OBJSHAREDINTEGERS 10000），这就意味着，如果有 10 个不同的 key，value 都是 10000 以内的值，事实上全部都是共享同一个对象。
SDS （simple dynamic string）
在 Redis 3.2 版本之前如果存储的是一个字符串且长度大于 39 个字节，就会使用 SDS 的格式来存储，并且将 encoding 设置为 raw。如果存储的是一个字符串但是长度小于等于 39 个字节，则将 encoding 设置为 embstr 来存储。
在 3.2 版本之后 39 被改为 44。
sds 的定义如下：
struct sdshdr {
// buf 中已占用空间的长度
int len;
// buf 中剩余可用空间的长度
int free;
// 数据空间
char buf[];
}; 字段含义：
- len 用于记录 buf 中已经使用的空间长度；
- free 用于记录 buf 中还空余的空间（初次分配空间一般没有空余，在对字符串修改的时候，会有剩余空间出现）；
- buf 字符数组，用于记录我们的字符串。
当你在 Redis 存储一个 hello 时，它在 sds 中存储的结构大概如下：
raw 格式和 embstr 格式的区别在于：
raw 编码会调用两次内存分配来分别创建 redisObject 结构和 sdshdr 结构，而 embstr 编码则通过一次内存分配函数来获得一块连续的空间，空间中依次包含 redisObject 和 sdshdr 结构。
同样对于内存释放来说，embstr 只需要一次，而 sdshdr 需要两次。
另外，因为 embstr 编码格式的字符串对象所有数据都是保存在一块连续的内存块中，那么对于查找操作来说可以将整块数据放入缓存中，更有利于读取。
SDS 和 C 字符串的区别
字符串长度计算
C 语言中的字符串使用长度为 n+1 的字符串数组来表达长度为 n 的字符串，获取字符串长度需要遍历整个数组。而 SDS 使用独立的 len 字段来记录长度。
C 缓冲区溢出
有两个在内存中紧邻的字符串”hello“ 和 ”world“，现在要把 ”hello“ 改为 ”helloo“，但是忘记重新为 ”helloo“ 分配新的内存空间，那么在 C 中会把 ”helloo“ 的位置往后溢出到后面的内存空间，即 ”world“ 的位置会被挤占。这两个单词就变为：”hellooorld”。
使用 SDS 则不用担心这种问题。Redis 会在执行修改操作之前先检查分配给 SDS 的空间是否够用，如果不够会先拓展空间再执行修改操作。
另外 SDS 还提供两个实用功能：空间预分配 和 惰性释放空间。
预分配策略：
- 如果修改后的 SDS 长度 < 1MB，预分配同样 len 大小的空间；
- 如果修改后的 SDS 长度 > 1MB，预分配1MB 大小的空间。
缩短 SDS 空间时并不立即进行内存空间释放，而是记录 free 字节数。下次修改数据如果需要重新分配空间时优先取这一部分字节而不是重新分配。
Hash 类型
hash 类型的底层存储分别有两种方式：ziplist 和 hashtable。
hashtable 存储
hashtable 实现方式我们就不细说大家都懂，基于 hash 值来实现，Redis 解决 hash 冲突使用链地址法。与 Java 中的 HashMap 不同的是，在链地址法解决冲突的过程中，对于一个冲突的 key 总是会添加到当前链表的表头而不是表尾，这样添加节点的时间复杂度就为 o(1)。
hash 的存储逻辑我们就不说，详细说一下 rehash 的过程，这个实现比较有意思。
Redis 的 字典结构体 dict 中存放了两张 hash 表：
typedef struct dict{
dictType *type; //dictType结构，dictType结构中包含自定义的函数，这些函数使得key和value能够存储任何类型的数据
void *privdata; //私有数据，保存着dictType结构中函数的 参数
dictht ht[2]; //两张哈希表
long rehashidx; //rehash的标记，rehashidx=-1表示没有进行rehash，rehash时每迁移一个桶就对rehashidx加一
int itreators; //正在迭代的迭代器数量
}正常使用的就是 ht[0]，ht[1] 是只有在扩容/缩容 的时候才会用到。hash 都是有负载因子的，这里也不例外：
load factor = ht[0].used / ht[0].size
触发 rehash 有两种情况，一种是触发扩容，一种是触发缩容。
触发扩容的条件包括：
- 服务器当前没有在执行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且 load factor >= 1；
- 服务器当前正在执行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且 load factor >= 5；
触发缩容的条件：
负载因子 < 0.1 时（(ht[0].used / ht[0].siz) < 0.1）。
再说很好玩的一点：渐进式 rehash。这个在 Java 的 HashMap 中是没有的。
所谓渐进式 rehash 即 rehash 不是一次性、集中式的完成，而是分多次、渐进式的进行。
这样做的原因在于如果 hash 表里的 KV 对很大时，比如上百万的情况如果一次性将这些数据全部从 ht[0] 移到 ht[1] 所需的庞大计算量可能会导致 Redis 在一段时间内停止服务。为了避免这种情况所以 Redis 采取了渐进式 rehash。
渐进式 rehash 期间，Redis 会逐渐的将 ht[0] 的数据转移到 ht[1] ，查找/删除/更新 操作会先查 ht[0]， 查不到会再查 ht[1]，新增操作只会在 ht[1] 上执行。
zipList 存储
说完 hashtable 存储我们再来说另一种存储方式：zipList。翻译过来是压缩列表，但是并不是我们理解表意上面的那种压缩。
zipList 是 list 键、 hash 键以及 zset 键的底层实现之一（3.0 之后 list 键已经不直接使用 zipList 和 linkedList 作为底层实现，取而代之的是 quickList）。
Redis 官方文档表示： zipList 是一个经过特殊编码的双向链表，这种双向链表与普通的双向链表的区别在于：它不存储上个节点和下个节点的指针，而是上个节点的长度和当前节点的长度。它的设计目标就是为了提高存储效率，zipList 适用于字段少和字段值少的场景。可用于存储字符串或整数，整数是按照二进制表示进行编码，而不是编码成字符串。
另外普通的链表中的每一项可能都不在一块连续的内存空间中，通过指针来表示数据引用。而 zipList 为了减少内存碎片率和提高查询效率，一个 zipList 对象将独自占用一块完整的独立内存空间。
下图展示了 zipList 的构成：
- zlbytes：32 bit，表示 zipList 占用的字节总数（也包括 zlbytes 本身占用的 4 个字节）。
- zltail： 32 bit，表示 zipList 表中最后一项（entry）在 zipList 中的偏移字节数。zltail 的存在使得我们可以很方便地找到最后一项（不用遍历整个zipList ），从而可以在 zipList 尾端快速地执行 push 或 pop 操作。
- zllen： 16 bit， 表示 zipList 中数据项（entry）的个数。zllen 字段因为只有 16 bit，所以可以表达的最大值为 2^16-1。这里需要特别注意的是，如果 zipList 中数据项个数超过了 16bit 能表达的最大值，zipList 仍然可以来表示。那怎么表示呢？这里做了这样的规定：如果 zllen 小于等于 216-2（也就是不等于216-1），那么 zllen 就表示 zipList 中数据项的个数；否则，也就是 zllen 等于 16bit 全为 1 的情况，那么 zllen 就不表示数据项个数了，这时候要想知道 zipList 中数据项总数，那么必须对 zipList 从头到尾遍历各个数据项才能计数出来。
- entry：表示真正存放数据的数据项，长度不定。一个数据项（entry）也有它自己的内部结构。具体结构我们下面画图解释。
- zlend：zipList 最后 1 个字节，是一个结束标记，值固定等于 255。
再说 zipList entry 的结构：
pre_entry_length：根据编码方式的不同， pre_entry_length 可能占用 1 字节或者 5 字节：
- 1 字节：如果前一节点的长度小于 254 字节，便使用一个字节保存它的值。
- 5 字节：如果前一节点的长度大于等于 254 字节，那么将第 1 个字节的值设为 254 ，然后用接下来的 4 个字节保存实际长度。
encoding 和 length
encoding 和 length 两部分一起决定了 content 部分所保存的数据的类型（以及长度）。其中， encoding 的长度为 2 bit ， 它的值可以是 00 、 01 、 10 和 11 ：
- 00 、 01 和 10 表示 content 部分保存着字符数组。
- 11 表示 content 部分保存着整数。
content 部分保存着节点的内容，类型和长度由 encoding 和 length 决定。
压缩列表的本质还是一个字节数组，操作时按照既定规则将字符写入 entry 中。既然底层是一块连续的内存块那么大小肯定是有限制的， hash 结构何时使用 hashtable ，何时使用 zipList 来进行存储呢？
当我们为某个 key 第一次执行 hset key field value 的时候，Redis 会创建一个 hash 结构，这个新创建的 hash 结构的底层就是 zipList 结构来存储的。
随着数据插入的越多，达到 Redis 配置的默认值：
hash-max-ziplist-entries 512
hash-max-ziplist-value 64- 当 hash 中的数据项（即field-value对）的数目超过 512 的时候，也就是 zipList 数据项超过 1024 的时候（请参考 t_hash.c 中的 hashTypeSet 函数）。
- 当 hash 中插入的任意一个 value 的长度超过了 64 的时候（请参考 t_hash.c 中的 hashTypeTryConversion函数）。
之所以有这两个条件限制，是因为 zipList 变大后会有几个缺点：
- 每次插入或修改引发的 realloc 操作会有更大的概率造成内存拷贝，从而降低性能。
- 一旦发生内存拷贝，内存拷贝的成本也相应增加，因为要拷贝更大的一块数据，类似 COW 的复制机制。
- 当 zipList 数据项过多的时候，在它上面查找指定的数据项就会性能变得很低，需要遍历整个链表。
