Redis教程

Redis之ziplist

本文主要是介绍Redis之ziplist,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

【ziplist结构】
Redis为了节约内存空间,zset和hash在元素个数较少的时候使用的是ziplist结构进行存储。zip+list,我们可以想到这应该是一系列的zip结构的数据链在了一起。压缩列表是一块连续的内存空间,元素之间紧挨着存储,没有任何冗余空隙。

struct ziplist<T>{
    int32 zlbytes;           //整个压缩列表占用的字节数
    int32 zltail_offset;     //最后一个元素距离压缩列表起始位置的偏移量,用于快速定位到最后一个节点
    int16 zllength;          //元素个数
    T[] entries;             //元素内容列表,紧密存储
    int8 zlend;              //标志压缩列表的结束,值恒为0XFF
}

这个zltail_offset是为了支持双向遍历,快速定位最后一个元素而设置的。注意到T[] entries这个属性,容纳的元素类型不同,他们的结构也不同。

struct entry {
    int<var> prevlen;         //前一个元素长度,用于快速定位到下一个元素的位置
    int<var> encoding;          //元素类型编码
    optional byte[] content;  //内容
}

prevlen是一个变长的整数,当字符串长度小于254时,就用1个字节表示,当长度大于254时,就用5个字节表示,第一个字节是0XFE,剩余四个字节表示字符串长度。
也就是说,程序可以只读第一个字节,如果大于0XFE,那么剩下四个字节就是长度,而如果小于OXFE,那么这个数值就是长度。

encoding存储了元素内容的编码类型信息,ziplist通过这个字段来决定后面的content形式。
如下图所示,说明了该协议的基本内容

注意content字段在结构体中定义为optional类型,表示这个字段是可选的,对于很小的整数而言,它的内容已经内联到encoding字段的尾部了。
【增加元素时的处理】
ziplist都是紧凑存储,没有冗余空间,意味着插入一个新的元素就要调用realloc扩展内存。
可能会分配一个新的内存空间,将之前的内容一次性拷贝到新的地址;也有可能在原有地址上进行扩展,这时就不需要进行旧内容的内存拷贝。
如果ziplist占据内存太大,重新分配内存和拷贝内存就会有很大的消耗,ziplist不适合存储大型字符串,存储的元素也不宜过多。所以Redis的处理是,较少的元素时,hash和zset的结构才是ziplist。
【级联更新】
首先解释下什么叫做级联更新,简单说,就是因为插入了新的元素,导致后续prevlen发生了变化,如果这个长度大于254,那么prevlen的结构就会发生变化,比如从1个字节增加到了多个字节,如果后续的prevlen也因此而发生字节的增加,那么这种情况就属于级联更新。
下面整理了几种更新的情况:
A.插入元素不要更新的情形,prevlen 远小于254
红色entry插入到黄色entry前

由于红色entry的长度为101,黄色entry的prevlen由0变成101,用1byte编码足够,不会发生更新。

B.当插入元素的长度大于等于254时,此时会发生更新
黄色节点的prevlen由1byte 增大到5 byte

C 当连续多个节点的数据接近254字节时,会发生级联更新,
注释:"…" 表示相同的节点,长度均和黄色节点相同

插入红色节点之后,黄色节点扩容达到254字节,导致后边的节点prevlen也需要扩容,这样连续的几个几点都需要更新,一直到绿色节点

下面是源代码:

 

/* When an entry is inserted, we need to set the prevlen field of the next
 * entry to equal the length of the inserted entry. It can occur that this
 * length cannot be encoded in 1 byte and the next entry needs to be grow
 * a bit larger to hold the 5-byte encoded prevlen. This can be done for free,
 * because this only happens when an entry is already being inserted (which
 * causes a realloc and memmove). However, encoding the prevlen may require
 * that this entry is grown as well. This effect may cascade throughout
 * the ziplist when there are consecutive entries with a size close to
 * ZIP_BIGLEN, so we need to check that the prevlen can be encoded in every
 * consecutive entry.
 *
 * Note that this effect can also happen in reverse, where the bytes required
 * to encode the prevlen field can shrink. This effect is deliberately ignored,
 * because it can cause a "flapping" effect where a chain prevlen fields is
 * first grown and then shrunk again after consecutive inserts. Rather, the
 * field is allowed to stay larger than necessary, because a large prevlen
 * field implies the ziplist is holding large entries anyway.
 *
 * The pointer "p" points to the first entry that does NOT need to be
 * updated, i.e. consecutive fields MAY need an update. */

static unsigned char *__ziplistCascadeUpdate(unsigned char *zl, unsigned char *p) {
    size_t curlen = intrev32ifbe(ZIPLIST_BYTES(zl)), rawlen, rawlensize;
    size_t offset, noffset, extra;
    unsigned char *np;
    zlentry cur, next;

    while (p[0] != ZIP_END) {
        cur = zipEntry(p);
        rawlen = cur.headersize + cur.len;
        rawlensize = zipPrevEncodeLength(NULL,rawlen);

        /* Abort if there is no next entry. */
        if (p[rawlen] == ZIP_END) break;
        next = zipEntry(p+rawlen);

        /* Abort when "prevlen" has not changed. */
        //如果prevlen的长度未变化,中断级联更新
        if (next.prevrawlen == rawlen) break;

        if (next.prevrawlensize < rawlensize) {
            /* The "prevlen" field of "next" needs more bytes to hold
             * the raw length of "cur". */
            //级联扩展
            offset = p-zl;
            extra = rawlensize-next.prevrawlensize;
            //扩大内存
            zl = ziplistResize(zl,curlen+extra);
            p = zl+offset;

            /* Current pointer and offset for next element. */
            np = p+rawlen;
            noffset = np-zl;

            /* Update tail offset when next element is not the tail element. */
            //更新zltail_offset指针
            if ((zl+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))) != np) {
                ZIPLIST_TAIL_OFFSET(zl) =
                    intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+extra);
            }

            /* Move the tail to the back. */
            //移动内存
            memmove(np+rawlensize,
                np+next.prevrawlensize,
                curlen-noffset-next.prevrawlensize-1);
            zipPrevEncodeLength(np,rawlen);

            /* Advance the cursor */
            p += rawlen;
            curlen += extra;
        } else {
            if (next.prevrawlensize > rawlensize) {
                /* This would result in shrinking, which we want to avoid.
                 * So, set "rawlen" in the available bytes. */
                //级联收缩,这里可以不用收缩,因为5个字节也是可以存储1个字节内容的
                //虽然空间有些浪费,但是避免了级联更新的操作
                zipPrevEncodeLengthForceLarge(p+rawlen,rawlen);
            } else {
                //大小没有变化,改一个长度值就可以了
                zipPrevEncodeLength(p+rawlen,rawlen);
            }

            /* Stop here, as the raw length of "next" has not changed. */
            break;
        }
    }
    return zl;
}

 

【intset小整数集合】
当set集合容纳的元素都是整数并且元素个数较少时,Redis会使用intset来存储集合元素。
intset是紧凑的数组结构,同时支持16,32,64位整数。

struct intset<T> {
    int32 encoding;      //决定整数位宽是16位,32位还是64位
    int32 length;        //元素个数
    int<T> contents;     //整数数组,可以是16位,32位还是64位
}

【参考】
《Redis深度历险 核心原理与应用实践》
https://blog.csdn.net/u010301542/article/details/100830218

这篇关于Redis之ziplist的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!