浅谈redis底层数据结构

简单动态数组（String的底层）

redis的SDS字符串数组和C底层的数组稍有不同。

不同点：通过将字节数组进一步的封装，是字符串的数据结构变成len,free,buf[]这种形式。类似于ArrayList与普通数组的不同，主要有以下不同。

redis中SDS数据结构

1. 不以遍历整个数组的方式得到数组长度，直接从len得到
2. 动态扩容机制

• 空间预分配
  所谓预分配其实就是数组的容量动态扩容，扩容规则是：
  1. 如果SDS小于1MB的话，扩容当前字节数的2倍+1，例如SDS现在为13字节，扩容后的长度是13 + 13 + 1(用于保留/0)=27字节。

  2. 如果SDS大于1MB，遍在此基础上增加1M+1字节，例如现在为30MB长度，扩容后为30MB + 1MB + 1B。

     
     
     空间预分配
• 惰性空间释放
  当底层buf数组的实际使用小于数组容量时候不马上缩容。

3. 二进制安全，由于buf[]数组是以len查询长度的，不以/0作为结束符号，所以redis对于文本的存储是兼容。

二进制安全

4. 兼容C的部分函数，redis在每个buf[]数组末尾都加了/0作为结束符，所以兼容C的部分函数。见上图。

链表（list的底层）

记忆点：list底层数据结构逻辑:list----listNode
链表被广泛用于实现 redis的各种功能，比如列表键、发布与订阅、慢查询、监视器等。

1. 每个链表节点由一个 listNode结构来表示，每个节点都有一个指向前节点pre和后节点next的指针．所以 Redis的链表实现是双端链表。
2. 每个链表使用一个list结构来表示，这个结构带有表头节点指针head、表尾节点指针tail，以及链表长度等信息。其中match为比较节点值和给定值的函数，dup是复制节点值的函数，free为释放节点值的函数。
3. 因为链表表头节点的前节点和表尾节点的后节点都指向 null ．所以 redis的链表实现是无环链表。
4. 通过为链表设置不同的类型特定函数，可以用于保存各种不同类型的值。

由list和listNode结构组成的链表

由listNode节点组成的链表

字典（整个数据库的实现）

记忆点：
字典（dict）底层数据结构逻辑:dict--[dictht[ ]/ rehashidx]--[dictEntry(table) / size / used]

普通状态下的dict

根据hash值和sizemark计算出索引值，采用拉链法解决hash冲突

k1与k2发生hash冲突

rehash扩容方式--渐进式（为了保证性能）
随着操作的不断执行，哈希表保存的键值对会逐渐地增多或者减少，为了让哈希表的负载因子(load factor）维持在一个合理的范围之内，当哈希表保存的键值对数量太多或者太少时，程序需要对哈希表的大小进行相应的扩展或者收缩。

1. 扩容数量：ht[0].used2,并通过取近似保证其为2^n幂，例如ht[0].used=10，ht[0].used2=20，此时应取32为大于20的第一个2^n -- 2^5作为新的容量。
2. 扩容时机：
   1. 服务器目前没有在执行BGSAVE命令或者BGREWRITEAOF命令 ，并且哈希表的负载因子大于等于1。
   2. 服务器目前没有在执行BGSAVE命令或者BGREWRITEAOF命令 ，并且哈希表的负载因子大于等于5。
      其中哈希表的负载因子可以通过公式：
      负载因子 = 哈希表已保存节点数量/哈希表大小
      扩容产生不同的原因在于Redis在持久化的时候需要创建当前服务器进程的子进程，而大多数操作系统都采用写时复制（copy-on-write)技术来优化了进程的使用效率，所以在子进程存在期间，服务器会提高执行扩展操作所需要的负载因子，从而尽可能地避免在子进程存在期间进行哈希表扩展操作，这可以避免不必要的内存写人操作，最大限度地节约内存。换言之就是持久化的时候对内存的消耗比较大，而redis希望提高在持久化的时候扩容的阈值以保证内存的充足。
      另一方面，当哈希表的负载因子小于0.1时，程序自动开始对哈希表执行收缩操作。
3. rehash的过程

执行rehash之前的字典

为ht1准备dictEntry对象，准备将数据迁移到此size更大的表

这里需要说明的是为了保证redis的性能扩容不是一次性就完成的，而是随着之后的每次操作进行。redis每执行一次增删改才做，数据迁移一部分。这就是redis的渐进式rehash。

循序渐进的把ht0的数据迁移到ht1上

将ht1替换成ht0，并把原来的ht0释放,并创建一个新的空的ht1，完成数据的迁移扩容

4. rehash时的操作
   因为在进行渐进式rehash的过程中，字典会同时使用ht[0] 和ht[1]两个哈希表，所以在渐进式rehash进行期间，字典的删除（delete)、査找（find）、更新（update) 等操作会在两个哈希表上进行。例如，要在字典里面査找一个键的话，程序会先在ht[0]里面进行査找，如果没找到的话，就会继续到ht[1]里面进行査找。
   另外，在渐进式rehash执行期间，新添加到字典的键值对一律会被保存到ht[1]里面，而ht[0]则不再进行任何添加操作，这一措施保证了ht[0]包含的键值对数量会只减不增，并随着rehash操作的执行而最终变成空表。

未完待续。。。