江苏龙网

  1. 主页 > 生活百科 > >

Redis底层数据结构解密

Redis

不要虚度每一天，你的经验就是这样积累出来，然后用在了你的事情上面 。
一：摘要概述
很多 redis 的使用者都可以清晰明白的道出Redis中常用的对象如string、list、hash、set、zset,一些场景比较丰富的使用者可能会说布隆过滤器、geo、Hash等 。但是对于这些对象底层实现的数据结构却是知之甚少,将会详细阐述redis中的底层数据结构 。为了弥补大家的创伤，今天分享Redis底层数据结构内容 。
 
二：SDS
string作为redis中常用对象之一,普遍用于用户信息缓存等场景 。当string对象中encoding编码为embstr或raw时都是采用sds作为其底层实现
 
2.1 SDS结构
源码文件位于redis安装目录src下的sds.h,sds声明了五种头部类型,分别为sdshdr5、sdshdr8、sdshdr16、sdshdr32、sdshdr64 。根据字符串长度创建不同头部的sds实例
 
struct __attribute__ ((__packed__)) sdshdr8 {
uint8_t len;
uint8_t alloc;
unsigned char flags;
char buf[];
};
 
属性名称作用含义
len字符串长度
alloc预分配空间大小
flags低三位用于表示sds类型,可以查看sds.h文件76-82行定义
buf[]存储字符串用数组
2.2 SDS与C字符串区别
区别描述
长度计算 c中的字符串长度计算需要数组遍历,但是redis中的sds自身维护了len属性 。所以O(1)时间复杂度即可
缓冲区溢出c中字符串更改如果未提前做好内存分配则会内存溢出,但是sds则会根据alloc与len计算预留内存是否足够分配重新申请内存
动态扩展 缓冲区溢出已经阐述这个概念,sds的内存空间会在字符串内容变更时自动扩展计算 。策略为当字符换小于1M时*2翻倍,大于1M时每次扩容1M
惰性释放 与空间预分配相似操作的还有内存惰性释放,即字符串删除某些内容后所占用的内存空间并不会立即释放,后续字符串变更扩展就无需再申请内存
二：ZipList
ziplist可以说把redis对于内存的极致操作体现的淋漓尽致,链表除了节点值之外还需要维护前后节点两个指针,并且还会造成内存碎片 。压缩列表紧凑的内存布局,所有节点都维护在整块内存中处理
 
2.1 ZipList结构
属性名称作用含义
zlbytes列表健占用内存的总字节数,在对列表健内存重分配或者是计算zlend的时候使用
zltail 指向压缩列表起始地址的指针
zllen 压缩列表的节点数量
entry压缩列表保存的节点数据
zlend压缩列表的尾节点
2.2 Entry节点结构
 
属性名称作用含义
previous_entry_length 字节为单位记录上一个节点的长度,如果上一个字节长度小于254占用1字节 。大于254占用5字节,第一个字节设置为OxFE(十进制254),后面四个字节储存长度
encoding 记录content记录的数据类型以及长度 。长度一、二、五字节,值的最高位为00、01、10表示类型为字节数组,长度使用除去最高位的其它位记录 。11开头表示储存整数,除去最高位其他位置表示content数据长度
content 记录压缩列表记录的数据
2.3 连锁更新
一个压缩列表节点在保存上一个节点长度使用previous_entry_length属性,这个属性可以使用1字节或者是5字节 。假设现有一个压缩列表里面保存的节点长度全部都是250-253,这时候previous_entry_length使用一字节记录就行 。但是这时候添加一个新节点到头节点的位置,恰好这个节点的大小大于254字节,这时候所有后面字节都需要更新,因为他们的previous_entry_length都会变成5字节
 
三：QuickList
list 链表是redis中常用对象之一,之前一些版本中底层编码数据采用双向链表、压缩列表的数据结构 。但是后续考虑链表指针维护开销以及内存碎片原因,开发新的数据结构quicklist,这是一个双向链表和压缩列表的混合体
 
3.1 quicklist图示
 
3.2 结构描述
typedef struct quicklist {
quicklistNode *head;
quicklistNode *tail;
unsigned long count;
unsigned long len;
int fill : 16;
unsigned int compress : 16;
} quicklist;
 
属性名称作用含义
head头部节点
tail 尾部节点
count压缩列表元素数量总数
len ziplist节点数量
fill 单个ziplist节点的填充因子
compress不压缩节点的深度
3.3 ziplist节点
quicklist 内部默认单个 ziplist 长度为 8k字节，超出了这个字节数就会新建一个 ziplist 。ziplist 的长度由配置参数 list-max-ziplist-size决定

Redis底层数据结构解密

文章插图


推荐阅读


上一篇：什么是接口幂等性？为什么会产生这个问题？如何保证接口幂等性？

下一篇：HotStuff算法详解