redis基础数据结构-zipmap简介

数据结构

1
2
3
--------------------------------------------------------------------------------------------------------------------------------------------------
cnt |key1.len|key1.context|val1.len|free1.len|val1.context|null1.context|key2.len|key2.context|val2.len|free2.len|val2.context|null2.context|0xFF|
--------------------------------------------------------------------------------------------------------------------------------------------------
  • cnt:一个字节,如果<ZIPMAP_BIGLEN(254),则是key-val对的数量,否则==ZIPMAP_BIGLEN时需要循环遍历zip来确定实时的数量
  • key.len: 头字节若<ZIPMAP_BIGLEN则存储的是key的长度,否则==ZIPMAP_BIGLEN时,key的长度存在后续4个字节中
  • key.context:可包含二进制数据的的key
  • val.len:同key.len
  • free.len:固定一个字节,理论上能给val预留不超过255个byte,但实际代码中不能超过
    超过ZIPMAP_VALUE_MAX_FREE(4),否则会被回收(不太明白作者为何不将此值扩大点)
  • OXFF:标志位,zip的尽头

特点

  • 给val预留了free,避免频繁的系统调用
  • len采用非固定格式,尽量的避免浪费MEM

主要接口函数

  • 构建zipmap

    1
    2
    3
    4
    5
    6
    7
    8
    /* Create a new empty zipmap. */
    unsigned char *zipmapNew(void) {
    unsigned char *zm = zmalloc(2);

    zm[0] = 0; /* Length */
    zm[1] = ZIPMAP_END;
    return zm;
    }
  • 计算key.len和val.len的实际代表的长度

    1
    2
    3
    4
    5
    6
    7
    8
    /* Decode the encoded length pointed by 'p' */
    static unsigned int zipmapDecodeLength(unsigned char *p) {
    unsigned int len = *p;

    if (len < ZIPMAP_BIGLEN) return len;
    memcpy(&len,p+1,sizeof(unsigned int));
    return len;
    }
  • 设置一对key.val

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    /* Set key to value, creating the key if it does not already exist.
    * If 'update' is not NULL, *update is set to 1 if the key was
    * already preset, otherwise to 0. */
    unsigned char *zipmapSet(unsigned char *zm, unsigned char *key, unsigned int klen, unsigned char *val, unsigned int vlen, int *update) {
    unsigned int zmlen, offset;
    unsigned int freelen, reqlen = zipmapRequiredLength(klen,vlen);
    unsigned int empty, vempty;
    unsigned char *p;

    freelen = reqlen;
    if (update) *update = 0;
    p = zipmapLookupRaw(zm,key,klen,&zmlen);
    if (p == NULL) {
    /* Key not found: enlarge */
    zm = zipmapResize(zm, zmlen+reqlen);
    p = zm+zmlen-1;
    zmlen = zmlen+reqlen; /* 新的总长 */

    /* Increase zipmap length (this is an insert) */
    if (zm[0] < ZIPMAP_BIGLEN) zm[0]++;
    } else {
    /* Key found. Is there enough space for the new value? */
    /* Compute the total length: */
    if (update) *update = 1; /* key已存在,则更新key对应的val */
    freelen = zipmapRawEntryLength(p);
    if (freelen < reqlen) { /* 现存的空间不够用 */
    /* Store the offset of this key within the current zipmap, so
    * it can be resized. Then, move the tail backwards so this
    * pair fits at the current position. */
    offset = p-zm;
    zm = zipmapResize(zm, zmlen-freelen+reqlen);
    p = zm+offset;

    /* The +1 in the number of bytes to be moved is caused by the
    * end-of-zipmap byte. Note: the *original* zmlen is used.
    * void *memmove(void *dest, const void *src, size_t n) */
    memmove(p+reqlen, p+freelen, zmlen-(offset+freelen+1));
    zmlen = zmlen-freelen+reqlen;
    freelen = reqlen;
    }
    }

    /* We now have a suitable block where the key/value entry can
    * be written. If there is too much free space, move the tail
    * of the zipmap a few bytes to the front and shrink the zipmap,
    * as we want zipmaps to be very space efficient. */
    empty = freelen-reqlen;
    if (empty >= ZIPMAP_VALUE_MAX_FREE) {
    /* First, move the tail <empty> bytes to the front, then resize
    * the zipmap to be <empty> bytes smaller. */
    offset = p-zm;
    memmove(p+reqlen, p+freelen, zmlen-(offset+freelen+1));
    zmlen -= empty;
    zm = zipmapResize(zm, zmlen);
    p = zm+offset;
    vempty = 0;
    } else {
    vempty = empty;
    }

    /* Just write the key + value and we are done. */
    /* Key: */
    p += zipmapEncodeLength(p,klen);
    memcpy(p,key,klen);
    p += klen;
    /* Value: */
    p += zipmapEncodeLength(p,vlen);
    *p++ = vempty;
    memcpy(p,val,vlen);
    return zm;
    }
  • 删除一对key.val

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    /* Remove the specified key. If 'deleted' is not NULL the pointed integer is
    * set to 0 if the key was not found, to 1 if it was found and deleted. */
    unsigned char *zipmapDel(unsigned char *zm, unsigned char *key, unsigned int klen, int *deleted) {
    unsigned int zmlen, freelen;
    unsigned char *p = zipmapLookupRaw(zm,key,klen,&zmlen);
    if (p) {
    freelen = zipmapRawEntryLength(p);
    memmove(p, p+freelen, zmlen-((p-zm)+freelen+1));
    zm = zipmapResize(zm, zmlen-freelen);

    /* Decrease zipmap length */
    if (zm[0] < ZIPMAP_BIGLEN) zm[0]--;

    if (deleted) *deleted = 1;
    } else {
    if (deleted) *deleted = 0;
    }
    return zm;
    }
  • 读取指定的val值

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    /* Search a key and retrieve the pointer and len of the associated value.
    * If the key is found the function returns 1, otherwise 0. */
    int zipmapGet(unsigned char *zm, unsigned char *key, unsigned int klen, unsigned char **value, unsigned int *vlen) {
    unsigned char *p;

    if ((p = zipmapLookupRaw(zm,key,klen,NULL)) == NULL) return 0;
    p += zipmapRawKeyLength(p);
    *vlen = zipmapDecodeLength(p);
    *value = p + ZIPMAP_LEN_BYTES(*vlen) + 1;
    return 1;
    }
  • 迭代遍历zipmap

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    /* Call it before to iterate trought elements via zipmapNext() */
    unsigned char *zipmapRewind(unsigned char *zm) {
    return zm+1;
    }

    /* This function is used to iterate through all the zipmap elements.
    * In the first call the first argument is the pointer to the zipmap + 1.
    * In the next calls what zipmapNext returns is used as first argument.
    * Example:
    *
    * unsigned char *i = zipmapRewind(my_zipmap);
    * while((i = zipmapNext(i,&key,&klen,&value,&vlen)) != NULL) {
    * printf("%d bytes key at $p\n", klen, key);
    * printf("%d bytes value at $p\n", vlen, value);
    * }
    */
    unsigned char *zipmapNext(unsigned char *zm, unsigned char **key, unsigned int *klen, unsigned char **value, unsigned int *vlen) {
    if (zm[0] == ZIPMAP_END) return NULL;
    if (key) {
    *key = zm;
    *klen = zipmapDecodeLength(zm);
    *key += ZIPMAP_LEN_BYTES(*klen);
    }
    zm += zipmapRawKeyLength(zm);
    if (value) {
    *value = zm+1; /* +1是free.len.head格式占用的一个字节空间 */
    *vlen = zipmapDecodeLength(zm);
    *value += ZIPMAP_LEN_BYTES(*vlen);
    }
    zm += zipmapRawValueLength(zm);
    return zm;
    }
-------------本文结束 感谢阅读-------------