windows7建设网站,个人网站模板素材,it外包公司招聘,登录住房城乡建设部官方网站前言
当数据量较小时#xff0c;Redis 会优先考虑用 ziplist 来存储 hash、list、zset#xff0c;这么做可以有效的节省内存空间#xff0c;因为 ziplist 是一块连续的内存空间#xff0c;它采用一种紧凑的方式来存储元素。但是它也有缺点#xff0c;比如查找的时间复杂度…前言
当数据量较小时Redis 会优先考虑用 ziplist 来存储 hash、list、zset这么做可以有效的节省内存空间因为 ziplist 是一块连续的内存空间它采用一种紧凑的方式来存储元素。但是它也有缺点比如查找的时间复杂度高、内存分配的开销、连锁更新的风险等。 于是 Redis 在 3.0 版本推出了 quicklist它可以看作是 ziplist 的升级版本质是把多个 ziplist 串联成链表把每个 ziplist 限制在一定的大小以此来降低 内存分配、连锁更新 的影响但是它并没有完全解决连锁更新的问题并且链表的每个节点也是要额外占用内存的。 Redis 5.0 终于推出了一个新的紧凑列表 listpack它沿用了 ziplist 的内存布局元素紧挨在一起没有指针的额外开销同时解决了连锁更新的问题。
listpack
listpack 的设计和 ziplist 如出一辙如果你了解 ziplist相信很容易理解 listpack。 listpack 也叫 紧凑列表它采用紧凑的内存布局本质上仍是一个字节数组。为了节省空间它采用了多种编码方式来表示不同长度的整型和字符串。最后它不再像 ziplist 一样元素还要记录上一个元素的大小而是记录当前元素的大下彻底解决了连锁更新的问题。
totalbyteslistpack 占用的字节数4 字节sizelistpack 元素数量2 字节element元素end结尾符 0xFF 1 字节
totalbytes size 也被称作 listpack 头部大小是 6 字节再加上 1 字节的结尾符所以一个空的 listpack 大小是 7 字节。
编码方式
为了节省内存listpack 针对不同长度的整型和字符串定义了多种编码方式
#define LP_ENCODING_7BIT_UINT 0
#define LP_ENCODING_13BIT_INT 0xC0
#define LP_ENCODING_16BIT_INT 0xF1
#define LP_ENCODING_24BIT_INT 0xF2
#define LP_ENCODING_32BIT_INT 0xF3
#define LP_ENCODING_64BIT_INT 0xF4
#define LP_ENCODING_6BIT_STR 0x80
#define LP_ENCODING_12BIT_STR 0xE0
#define LP_ENCODING_32BIT_STR 0xF0_UINT 结尾无符号整型_INT 结尾有符号整型_STR 结尾字符串
这里对编码方式举例解释一下其它几种以此类推
LP_ENCODING_7BIT_UINT代表 7Bit 无符号整型1 个字节表示高 1 位是 0低 7 位表示整型值LP_ENCODING_13BIT_INT代表 13Bit 有符号整型2 字节表示高 3 位是 110低 13 位 表示整型值LP_ENCODING_6BIT_STR长度不超过 63 的字符串。1 字节表示 encoding高 2 位是 10低 6 位代表字符串的长度data 部分是具体的字符串值
避免连锁更新
listpack 彻底解决了 ziplist 连锁更新的问题怎么做的呢 ziplist 为什么会存在连锁更新的问题就是因为每个元素要记录上一个元素的长度而且采用变长字节记录小于 254 就用1字节否则用5字节。如此一来某个元素修改时影响的就不仅仅是自己了还会影响后面的元素引发连锁反应。 listpack 解决方式就是元素不再记录上一个元素的大小了而是改为记录自身的大小这样元素与元素之间就独立了不会相互影响到。
遍历问题
ziplist 元素记录上一个元素的大小是为了支持从后向前遍历。listpack 改为记录元素自身大小了那么还支持双向遍历吗 答案是支持的我们来看一下双向遍历的过程。
正向遍历
正向遍历时listpack 首先跳过 6 字节的头部指针就会指向第一个元素再根据元素的 encoding 字段得到元素的长度和类型然后就可以正常访问元素了。再根据 encoding 计算当前元素长度占用的字节数跳过当前元素占用的字节数就可以访问下一个元素了直到访问到结尾符代表结束。
反向遍历
首先访问 listpack 的前4字节得到总长度然后就可以定位到末尾结尾符位置。然后指针左移就可以访问到最后一个元素的长度 len指针再左移 len 就可以访问最后一个元素的 encoding根据编码方式访问元素。指针再左移又可以访问到倒数第2个元素的长度以此类推。 访问元素长度len字段时有一个关键点就是如何判断 len 部分结束了。因为 len 可能占用1字节也可能占用多个字节。listpack 的做法是每个字节只使用 7 Bit最高位来表示是否还要继续读。
尾巴
listpack 是 Redis 对 ziplist 的改进版本彻底解决 ziplist 连锁更新的问题。紧凑的内存布局避免了传统链表指针带来的访问效率和内存占用问题非常适合小数据量的存储。 需要注意的是listpack 查询效率依然是 O(N)查找时间会随着元素数量线性增长不过好在 Redis 基本拿它存储少量数据所以 N 的值一般不会太大。
