字典

-字典又称为符号表，关联数组或者map

我对于 字典和链表等其他数据结构的关系的理解是
整个redis就是一个字典，key是string（SDS），value（可以是SDS,List，hash等）

字典的实现

• 字典底层使用hash表（map）实现
• 一个hash 表里面可以有多个hash表节点（Node）
• 每个hash表节点 保存了字典中的一个键值对

dict.h文件的dictht就是hash表，里面的元素是：table（hash表数组），size（hash表大小），sizemask（hash表大小掩码，用于计算索引，总是等于size-1（就是类似于咱们的map总是是size-1 的二进制 这样的话 随机的概率好点）），used 已有的节点数量

• table 中的每一个元素都是一个指针，该指针指向了dictEntry（哈希表节点），一个dictEntry就是一个键值对

哈希表节点

dictEntry 的结构如下：key， v（值），其中v可以是指针，或者unit64_t整数或者init64_t整数，next是指向下一个hash表节点的指针，该指针，是当有键值hash一样的时候进行存储。

字典是在dict.h文件中的dict结构

具体属性type，privdata（私有数据），dictht ht[2] 哈希表（2个主要类似GC中的surivor区，不过大小不是一样，只有有数据的才有大小）， trehash（rehash索引，值=-1 代表没有rehash，主要是做渐进式rehash）

• type 指向dictType结构的指针

• privdata 保存了需要传给哪些类型特定函数的可选参数

• 可以看到type 和privdata 主要处理下面涉及到的函数

  
  image.png

• ht 包含两个项的数组，每一个都是dictht哈希表，一般情况下字典只使用ht[0],ht[1]只有在rehash使用，等rehash结束了 会修改名字

rehash 跟hashmap差不多（不仅包括扩展，还包括收缩）

• 1.先给ht[1]分配空间，扩展则是按照ht[0].used*2的n+1次方，收缩的话只是扩展的一半。
• 2重新计算hash值，把数据转移到ht[1]
• 3 当转移完毕则释放ht[0]。将ht[1]，设置为ht[0]，并为ht【1】设置一个空白的hash表

rehas的时机

• 在后台异步(Asynchronously)保存当前数据库的数据到磁盘。

[BGSAVE]命令执行之后立即返回 OK ，然后 Redis fork 出一个新子进程，原来的 Redis 进程(父进程)继续处理客户端请求，而子进程则负责将数据保存到磁盘，然后退出。

执行一个 AOF文件 重写操作。重写会创建一个当前 AOF 文件的体积优化版本。

即使 BGREWRITEAOF 执行失败，也不会有任何数据丢失，因为旧的 AOF 文件在 BGREWRITEAOF 成功之前不会被修改。

重写操作只会在没有其他持久化工作在后台执行时被触发，也就是说：

• 如果 Redis 的子进程正在执行快照的保存工作，那么 AOF 重写的操作会被预定(scheduled)，等到保存工作完成之后再执行 AOF 重写。在这种情况下， BGREWRITEAOF 的返回值仍然是 OK ，但还会加上一条额外的信息，说明 BGREWRITEAOF 要等到保存操作完成之后才能执行。在 Redis 2.6 或以上的版本，可以使用 INFO 命令查看 BGREWRITEAOF 是否被预定。
• 如果已经有别的 AOF 文件重写在执行，那么 BGREWRITEAOF 返回一个错误，并且这个新的 BGREWRITEAOF 请求也不会被预定到下次执行。

从 Redis 2.4 开始， AOF 重写由 Redis 自行触发， BGREWRITEAOF 仅仅用于手动触发重写操作。

• 服务器目前没有执行BGSAVE（RDB）或者BGREWRITEAOF(AOF)，并且负载因子大于1

• 服务器正在执行BGSAVE（RDB）或者BGREWRITEAOF(AOF)，但是负载因子大于5

• 之所以这个时候负载因子设为5，是因为此时有当前服务的子进程存在，大多数操作系统都会采用copy on write 来优化子进程的使用效率，这就意味着我们需要开辟一段内存给子进程使用（这段内存主进程用不了），等子进程使用完了 才会替换。所以为了避免在此期间进行扩展，进而增加内存压力 才提高到5

• 负载因子等于ht[0].used/ht[0].size

• 当负载因子小于0.1则进行收缩

渐进式rehash的步骤

• 1.为ht[1]分配空间，字典同时拥有2个hash表

• 2. 维持一个reshidx的计数器，在rehash期间每次成字典执行添加删除查找或者更新的操作外，还会顺带将ht[0]hash表上rehashidx对应的索引数据移动到ht[1]，移动一个就增加一个（hash表其底层就是一个数组）
• 3. 都执行完成了 则rehashidx会被设置为-1
     好处就是rehash的键值的时间 平摊到每一次的redis操作，这样避免了为了rehash 而暂停所有的请求

• 4.在此期间操作，我们会优先查找ht[0]，查找不到再会去ht[1]，此外新添加的键值只会保存到ht[1]