内容展示类网站,国外优秀摄影网站,想学设计怎么入门在家自己学,济南网站app开发的前言
为了节省内存#xff0c;Redis 推出了 ziplist 数据类型#xff0c;采用一种更加紧凑的方式来存储 hash、zset 元素。因为查找的时间复杂度是 O(N)#xff0c;且写入需要重新分配内存#xff0c;所以它仅适用于小数据量的存储#xff0c;而且它还存在 连锁更新 的风…前言
为了节省内存Redis 推出了 ziplist 数据类型采用一种更加紧凑的方式来存储 hash、zset 元素。因为查找的时间复杂度是 O(N)且写入需要重新分配内存所以它仅适用于小数据量的存储而且它还存在 连锁更新 的风险。 为了降低 ziplist 内存分配和连锁更新带来的影响Redis 又推出了 quicklist 数据结构我们来一睹它的风采。 注意quicklist只是降低了 ziplist 内存分配和连锁更新带来的影响没有从根本上解决这些问题。 quicklist quicklist 是由若干个 ziplist 节点组成的一条双向链表quicklist 的核心在于控制好每个 ziplist 的大小因为 ziplist 越大内存分配的开销越大连锁更新带来的影响也就越大。 Redis 提供了list-max-ziplist-size参数来限制 ziplist 大小值为负数时限制的是 ziplist 的内存空间值为正数时限制的是 ziplist 元素数量。默认值是 -2代表每个 ziplist 不超过 8KB。
-1最大 4KB-2最大 8KB默认值-3最大 16KB-4最大 32KB-5最大 64KB不推荐 0限制元素数量
另外 Redis 还支持对 quicklist 中的 ziplist 节点做压缩节点一旦压缩就意味着每次访问都必须先解压缩这势必会带来额外的开销。又因为两端的节点是访问频率较高的特别是头尾节点是最常访问的节点。因此为了兼顾访问性能和内存占用Redis 提供了list-compress-depth参数配置 quicklist 两端不压缩的节点数默认不压缩。
源码
quicklist
quicklist 是一条由若干个 ziplist 组成的双向链表为了快速访问两端节点quicklist 用两个指针分别指向了首尾节点同时记录下链表里的节点数以及所有的总元素数量这样就不必每次都再统计一遍。 fill限制单个 ziplsit 长度可以是内存空间也可以是元素数量compress限制了两端不被压缩的节点数量。
typedef struct quicklist {quicklistNode *head; // 头节点quicklistNode *tail; // 尾节点unsigned long count; // 总元素数量unsigned long len; // 节点数int fill : QL_FILL_BITS; // 限制ziplist长度 正数代表限制元素数量 负数代表限制内存大小unsigned int compress : QL_COMP_BITS; // 链表两端不压缩的节点数 因为两端会被频繁访问unsigned int bookmark_count: QL_BM_BITS;quicklistBookmark bookmarks[];
} quicklist;quicklistNode
quicklist 里的每个节点用 quicklistNode 表示每个节点都都有两个指针分别指向前驱节点和后继节点。 每个节点都是一个单独的 ziplist所以还有一个zl指针指向 ziplist。同时还会记录一些额外的数据比如元素数量ziplist 是否被压缩能否被压缩等等。
typedef struct quicklistNode {struct quicklistNode *prev; // 前驱节点struct quicklistNode *next; // 后继节点unsigned char *zl; // ziplist指针unsigned int sz; // ziplist大小unsigned int count : 16; // ziplist元素数量unsigned int encoding : 2; // 编码方式 ziplist/quicklistLZFunsigned int container : 2; // 存储方式unsigned int recompress : 1; // 是否压缩unsigned int attempted_compress : 1; // 数据能否被压缩 太小就没压缩的必要unsigned int extra : 10; // 预留位
} quicklistNode;quicklistLZF
ziplist 采用 LZF 压缩算法压缩后的结构是 quicklistLZF。sz 记录压缩后的数据长度compressed 是压缩后的字节数组。
typedef struct quicklistLZF {unsigned int sz; // 压缩后的长度char compressed[]; // 压缩后的数据
} quicklistLZF;quicklistEntry
quicklistEntry 代表 quicklist 里的一个 ziplist 节点里的一个元素。
typedef struct quicklistEntry {const quicklist *quicklist; // quicklist指针quicklistNode *node; // 所属node节点unsigned char *zi; // ziplist指针unsigned char *value; // 节点值指针long long longval; // 整形值unsigned int sz; // 节点长度int offset; // 偏移量
} quicklistEntry;quicklistCreate
创建一个空的 quicklist。
quicklist *quicklistCreate(void) {struct quicklist *quicklist;quicklist zmalloc(sizeof(*quicklist));quicklist-head quicklist-tail NULL;quicklist-len 0;quicklist-count 0;quicklist-compress 0;quicklist-fill -2; // 默认每个ziplist不超过8KBquicklist-bookmark_count 0;return quicklist;
}quicklistPush
插入元素根据 where 判断是插入到头部还是尾部。
void quicklistPush(quicklist *quicklist, void *value, const size_t sz,int where) {// 插入到头结点还是尾节点if (where QUICKLIST_HEAD) {quicklistPushHead(quicklist, value, sz);} else if (where QUICKLIST_TAIL) {quicklistPushTail(quicklist, value, sz);}
}quicklistPushTail
以插入到尾部为例quicklist 在插入前都会先判断目标 ziplist 是否能容纳新的元素如果能容纳则直接插入否则会创建新的 ziplist 节点再插入元素这样就可以限制每个 ziplist 大小。
int quicklistPushTail(quicklist *quicklist, void *value, size_t sz) {quicklistNode *orig_tail quicklist-tail;assert(sz UINT32_MAX); // 判断插入的目标node是否能容纳新元素if (likely(_quicklistNodeAllowInsert(quicklist-tail, quicklist-fill, sz))) {quicklist-tail-zl ziplistPush(quicklist-tail-zl, value, sz, ZIPLIST_TAIL);quicklistNodeUpdateSz(quicklist-tail);} else {// 不能容纳则创建新的节点插入quicklistNode *node quicklistCreateNode();node-zl ziplistPush(ziplistNew(), value, sz, ZIPLIST_TAIL);quicklistNodeUpdateSz(node);_quicklistInsertNodeAfter(quicklist, quicklist-tail, node);}quicklist-count;quicklist-tail-count;return (orig_tail ! quicklist-tail);
}尾巴
为了降低 ziplist 内存分配的开销和连锁更新带来的影响Redis 推出了 quicklist 数据结构它可以看作是 ziplist 的一个升级版本核心是限制每个 ziplist 的大小然后把它们串联成一条双向链表这样就可以把内存分配和连锁更新的开销分摊到每个节点上影响就不会那么大了同时又能利用 ziplist 节省内存的优点。 需要注意的是quicklist 不是银弹虽然可以降低 ziplist 的一些额外开销但它的查找效率依然是 O(N)。
