三、底层实现
1. 内存回收
采用引用计数技术实现内存回收机制
2. 对象共享
如果多个键的对象值都相同，对于相同的对象值，这些键就会同时指向这个对象。节省空间。
举例：Redis 在初始化服务器时，创建一万个字符串对象，这些对象包含了从 0 到 9999 的所有整数值，当服务器需要用到值为 0 到 9999 的字符串对象时，服务器就会使用这些共享对象，而不是新创建对象。
1 | // 查看键 a 所对应的值对象的引用计数 |
3. 对象的空转时长
redisObject 结构包含一个属性为 lru ，该属性记录了对象最后一次被命令程序访问的时间。
1 | // 查看键 msg 的空转时长 |
空转时长是通过将当前时间减去键的值对象的 lru 时间计算得出的。当服务器占用的内存过高，需要清理时，空转时长较高的那部分键会优先被服务器释放，从而回收内存。
四、底层数据结构的实现
1. 简单动态字符串sds
- 安全兼容部分C 字符串函数
- 长整型或浮点数通过字符串保存
2. 链表 likedlist
- 由listNode组成的双端双向链表。通过dup(),free(),match()函数实现多态
3. 字典 dict/hashtable
- 双哈希表，哈希算法采用MurmurHash，链式存储解决冲突
- rehash通过将ht[0]中的所有键值对rehash到分配更多/更少空间的ht[1]后切换
- 在执行 BGSAVE 或BGREWRITEAOF 的创建子进程中，提高负载因子以避免子进程存在期间进行rehash
- 渐进式rehash，避免了集中式 rehash 而带来的庞大计算量，均摊每次对字典执行添加、删除、查找或者更新操作时，将 ht[0] 哈希表在 rehashidx 索引上的所有键值对 rehash 到 ht[1]，然后自增rehashidx，相当于每次转移一行。渐进式rehash期间，RUD操作在两表上都进行，加入C操作在ht[1]上，保证ht[0]只减不增加
4. 有序集合 zset
- 有序集合zset包含1个字典dict和1个跳跃表zskiplist。让有序集合的查找和范围型操作都尽可能快地执行
- 有序有排位zskiplist。zskiplistNode根据幂次定律生成高度，每层有level[i].forward前进指针，level[i].span记录同层间两顶点的跨度(用于计算rank=sum(span))。节点根据score排序，分值相同的节点将按照成员对象obj在字典序中的大小来进行排序
- zskiplist的CRUD操作时间复杂度在O(logN)
5. 整数集合 intset
- 保存整数值int16/int32/int64的集合，通过encoding的int8有序数组实现
- 自动进行自动升级与降级，通过空间重分配+从后向前复制实现
6. 压缩列表
- 特殊编码的连续内存块组成的有序列表，编码字节数组或整型数组
- 从表尾向表头遍历：只要我们拥有了一个指向某个节点起始地址的指针， 那么通过这个指针以及这个节点的 previous_entry_length 属性， 就可以一直向前一个节点回溯
- 查找R为O(N)，NextNode/PrevNode为O(1)。CUD操作可能引发连锁更新，让每个节点的previous_entry_length 属性都符合压缩列表对节点的要求，执行 N 次空间重分配操作，时间复杂度平均O(N)，最坏在O(N^2)。适合少量元素