注:主要内容整理来自redis中几种哈希函数的研究
哈希就是离散算法
将一个键值转换成我们需要的数组索引下标的方法

LRU(Least Recently Used)最近最少使用统计算法

当Redis使用的内存超出设置的可以最大使用内存后
Redis会通过LRU的配置来回收内存
Redis对象的lru是用1<<24 - 1长度的字节表示的
可以连续标识194天的数据

Redis这里的LRU算法是近似算法
不是完全精确地获取到最合理的答案
而是按照采样结果查找到一个比较近似的结果
这个结果可能不是最合理的
但肯定不是最坏的

Redis的内存回收算法采用
引用计数算法
通过增减对象的引用计数来判断
是否需要回收对象的内存

• 优点
  • 代码逻辑清晰
  • 不会有集中清理数据时造成的假死现象
• 缺点
  • 无法解决循环引用问题(无视弱指针吧)
  • 增加/减少引用数时的函数要对称,不能漏掉(c里面没有构造析构函数)

这个数据结构分析的比较粗糙,因为实际使用的是redis2.8没有用这个结构.时间不够用了,先把代码粘过来
Redis3.2版本新增数据结构
代替原有的list的功能
本质是一个双向链表,
链表的节点是ziplist,
而不是具体的值
同时增加了压缩选项
可已将ziplist数据进行压缩
压缩算法为lzf算法
与原始链表对比
- 原始链表定位特定元素时耗时较大
- 原始链表元素分散,容易产生较多内存碎片
基本操作原理
向ql插入数据时
先获得头/尾的zl
当zl数量没有超过指定的zl元素数上限时
直接在zl中插入数据,
否则新建节点和空的zl,
然后再插入数据

相关文件

• quicklist.h
• quicklist.c
  阅读全文 »

Redis3.2版本前的数据结构
本质是一个双向链表
最基本的双向链表
附带一个迭代器
3.2版本后使用quicklist代替

相关文件

• adlist.h
• adlist.c
  阅读全文 »

ziplist本质上就是字符串数组
当存储元素数量<UINT16_MAX时,可以直接读取长度
当存储元素数量>=UINT16_MAX时,需要遍历整个ziplist才能获取长度
采用了不同的编码来对数字,字符串存储进行了压缩

• 结构
  <总字节数(4字节)><最后一个元素的偏移量(从头开始算)(4字节)><总元素个数(2字节)><数据(不定字节)>…<0xFF结尾标记(1字节)>
• 数据的结构
  • 头
    • 前一个数据的编码类型和长度
      • 当长度小于0xFE时,是一个字节
      • 当长度大于等于0xFE时,是5个字节(第一个字节+4个字节的长度信息)
    • 当前数据的编码类型和长度
      第一个字节的前两位
      • 字符串
        • 00??????
          数据头总共占用一个字节
          后六位表示字符串长度
        • 01??????|????????
          数据头总共占用两个字节
          后14位表示字符串长度
        • 10______|????????|????????|????????|????????
          数据头总共占用5个字节
          后4个字节表示字符串长度
      • 数字
        • 11000000
          表示int16_t
          后面两个字节为具体数据
        • 11010000
          表示int32_t
          后面4个字节为具体数据
        • 11100000
          表示int64_t
          后面8个字节为具体数据
        • 11110000
          表示int24_t
          后面3个字节为具体数据
        • 11111110
          表示int8_t
          后面1个字节为具体数据
        • 11110001-11111101
          直接表示0-12的值
          后面没有数据
          值直接就在当前字节中
          其中
          11110001 0
          11110010 1
          …
          11111101 12
          就是字节后4位的值直接转化为整数
          然后-1所得的值
          结尾不是1110是因为1110为int8_t
          结尾不是1111是因为1111为ziplist结尾标记
  • 数据
    根据数据长度定义的连续字符串

相关文件

• ziplist.h
• ziplist.c
  阅读全文 »

跳表
就是分层级的有序链表
查询数据快,结构简单
跳表所有层级的第一个元素都是header的头元素(空数据)
结尾是实际插入的元素
跳表的第一个实际插入的元素是回退不到header的
代码中
forward的处理是遍历循环处理
backward的处理是一个if判断
是因为forward是层级相关的,所有层级都要处理
而backward只是一个值,backward本身只记录0级的数据

相关文件

• server.h
• t_zset.c
  阅读全文 »

set的一种优化数据结构
试用于元素数量较少
元素类型为int16_t,int32_t,int64_t
的情况
本质是uint8_t[]
set的编码会根据内容元素自动变更
不需要手动变更编码
从小到大递增排序

相关文件

• intset.h
• intset.c

本质是链表
dict本身包含一个长度是2的链表数组
原因:
- 减少rehashing过程中阻塞操作的时常
- 可以方便的rehash,提高hash表效率

相关文件

• dict.h
• dict.c

本质上就是char*字符串
通过指定的格式排列的数据结构
基本格式

1
2
3
4
5

<zmlen>	// 当zmlen小于254时,记录的是键值对的个数,当等于254时,表示需要遍历整个zipmap才能指导具体的长度
		<len>$key1<len><free>$value1	// 键长度->键->值长度->1字节无用空间长度->无用空间->值(无用空间在代码中貌似不太对,有的地方有用,有的地方没有用(关于free的代码都不完善,没有统一),应该是所有使用的地方,无用空间长度都是0)
		<len>$key2<len><free>$value2
		...
<255> // zipmap结尾

1
2

#define ZIPMAP_BIGLEN 254 // zm的长度上限,当数据长度超过254时,使用254标记,并将后4(根据unsigned int长度变化)为记录为数据长度
#define ZIPMAP_END 255 // zm的结尾标记

相关文件

• zipmap.h
• zipmap.c