This is the 6th day of my participation in the August More Text Challenge

1. Introduction

The bottom layer of ziplist is a byte array, which is a data structure designed by Redis to save memory. It can store multiple elements, and each element can be a byte array or an integer

Compressed lists apply to ordered collections, hashes, lists of Redis:

  • When ordered collections have fewer elements and are all short strings, the data structure used is a compressed list
  • The data structure used for lists is quickList, a combination of bidirectional linked lists and compressed lists
  • The underlying structure of the hash also contains the compressed list

2. Compress the storage structure of linked lists

2.1 Compressed List

Compressed list properties:

  • Zlbytes: indicates the length of the compressed list, which is 4 bytes. Therefore, the compressed list can contain a maximum of 2^32-1 bytes
  • Zltail: Represents the offset of the last element relative to the first address of the compressed list, which is 4 bytes
  • Zllen: indicates the number of elements, which is 2 bytes. Therefore, the number of elements stored in the compressed list is not more than 2^16-1. You must traverse the entire compressed list to obtain the number of elements
  • EntryX: Represents the element stored in the compressed list, which can be a byte array or an integer
  • Zlend: represents the end of the compressed list, accounting for 1 byte and always 0xFF

Redis compressed list attribute macro definition:

// ziplist.c

// zl points to zlbytes
#define ZIPLIST_BYTES(zl)       (*((uint32_t*)(zl)))

// zl+4 points to zltail
#define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t*)((zl)+sizeof(uint32_t))))

// zl+8 points to zllen
#define ZIPLIST_LENGTH(zl)      (*((uint16_t*)((zl)+sizeof(uint32_t)*2)))

// Compress the list header size by 10 bytes (zlbytes+zltail+zllen)
#define ZIPLIST_HEADER_SIZE     (sizeof(uint32_t)*2+sizeof(uint16_t))

// Compress the list tail size to 1 byte
#define ZIPLIST_END_SIZE        (sizeof(uint8_t))

// Compress the head element of the list
#define ZIPLIST_ENTRY_HEAD(zl)  ((zl)+ZIPLIST_HEADER_SIZE)

// Compress the last element of the list
#define ZIPLIST_ENTRY_TAIL(zl)  ((zl)+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl)))

// Compress the end of the list element
#define ZIPLIST_ENTRY_END(zl)   ((zl)+intrev32ifbe(ZIPLIST_BYTES(zl))-1)
Copy the code

2.2 Encoding structure of compressed list elements

Attributes of the element encoding structure:

  • Previous_entry_length: Indicates the length of the previous element in 1 or 5 bytes
    • If the byte length of the preceding element is less than 254, it is 1 byte
    • When the byte length of the first element is greater than or equal to 254, it takes up five bytes. In this case, the first byte is fixed as 0xFE, and the last four bytes represent the length
    • If there is an element with the initial address p, p-previous_entry_length represents the initial address of the previous element, which allows the compressed list to be traversed from the end to the head
  • Encoding: The data type (integer or byte array) of the content
  • Content: Stores the data content of the element

To save memory, the length of the encoding property is variable:

Encoding encoding The length of the encoding The content type
00 BBBBBB (6 bits for content length) 1 byte A maximum length of 63 bytes
01 BBBBBB CCCCCCCC (14 bits indicates the content length) 2 – A byte array of maximum length 2^14-1
10—— aaaaaaaa BBBBBBBB CCCCCCCC DDDDDD (32 bits for content length) 5 bytes A byte array of maximum length 2^32-1
11000000 1 byte Int16 integer
11010000 1 byte Int32 integer
11100000 1 byte Int64 integer
11110000 1 byte 24 bit integer
11111110 1 byte 8-bit integer
1111 xxxx 1 byte There is no content attribute, and XXXX represents an integer between 0 and 12
  • The Content property stores either integers or arrays of bytes (and their maximum length) based on the first two bits of the encoding property
  • When content stores a byte array, the first two bytes after the first byte of the encoding property identify the actual length of the byte array
  • When content stores integers, bits 3 and 4 of the first byte of the Encoding attribute identify the type of the integer. When the encoding attribute identifies that the element stores integers in the range (0,12), the integer content is stored directly in the encoding attribute, with no content attribute

The following constants are defined in Redis to identify the encoding type of the encoding property:

  • // ziplist.c
#define ZIP_STR_06B (0 << 6)			 / / 00000000
#define ZIP_STR_14B (1 << 6)       / / 01000000
#define ZIP_STR_32B (2 << 6)       / / 10000000
#define ZIP_INT_16B (0xc0 | 0<<4)  / / 11000000 = 11000000 | 00000000
#define ZIP_INT_32B (0xc0 | 1<<4)  / / 11010000 = 11000000 | 00010000
#define ZIP_INT_64B (0xc0 | 2<<4)  / / 11100000 = 11000000 | 00100000
#define ZIP_INT_24B (0xc0 | 3<<4)  / / 11110000 = 11000000 | 00110000
#define ZIP_INT_8B 0xfe            / / 11111110
Copy the code

3. The structure of the body

3.1 Element encoding cache

The encoding structure of the compressed list element is complex. When the length of the previous element, the data type stored in the element and the data content of the element are obtained after decoding, these attributes can be cached in the structure Zlentry

  • // ziplist.c
typedef struct zlentry {
    unsigned int prevrawlensize; 
    unsigned int prevrawlen;     
    unsigned int lensize;       
    unsigned int len;           
    unsigned int headersize;     
    unsigned char encoding;      
    unsigned char *p;            
} zlentry;
Copy the code

  • Prevrawlensize: Previous_entry_length Specifies the byte length of the attribute

  • Prevrawlen: Length of the previous element in bytes

  • Lensize: encoding Specifies the byte length of the attribute

  • Len: The length of the element’s data content in bytes

  • Headersize: the byte length of the element’s header (prevrawlenSize +lensize)

  • Encoding: Type of element data content

  • P: the first address of the element

3.2 Element Decoding

  • // ziplist.c
void zipEntry(unsigned char *p, zlentry *e) {
    Prevrawlensize prevrawlen
    ZIP_DECODE_PREVLEN(p, e->prevrawlensize, e->prevrawlen);
    Encoding, lensize, len
    ZIP_DECODE_LENGTH(p + e->prevrawlensize, e->encoding, e->lensize, e->len);
    / / headersize calculation
    e->headersize = e->prevrawlensize + e->lensize;
    / / set p
    e->p = p;
}
Copy the code
  • // ziplist.c
// PTR refers to the first address of the element, which is the first address of the previous_entry_length attribute
#define ZIP_DECODE_PREVLEN(ptr, prevlensize, prevlen) do { 
    / / parsing prevlensize
    ZIP_DECODE_PREVLENSIZE(ptr, prevlensize);                                  
    if ((prevlensize) == 1) {
        // If the previous_entry_length attribute is 1 byte
        Prevlen is parsed based on the byte
        (prevlen) = (ptr)[0];                                                  
    } else if ((prevlensize) == 5) {
        // If the previous_entry_length attribute is 5 bytes
        Prevlen is parsed from bytes 2 to 5
        assert(sizeof((prevlen)) == 4);                                    
        memcpy(&(prevlen), ((char*)(ptr)) + 1.4); memrev32ifbe(&prevlen); }}while(0);

#define ZIP_BIG_PREVLEN 254

#define ZIP_DECODE_PREVLENSIZE(ptr, prevlensize) do {                          
    if ((ptr)[0] < ZIP_BIG_PREVLEN) {
        // If the preceding element is less than 254 bytes
        Previous_entry_length takes 1 byte, prevlenSize =1
        (prevlensize) = 1;                                                     
    } else {
        // If the preceding element has a length of 254 or greater
        Previous_entry_length takes 5 bytes, prevlenSize =5
        (prevlensize) = 5; }}while(0);
Copy the code
  • // ziplist.c
#define ZIP_STR_MASK 0xc0 / / 11000000

// PTR points to the first address of the element encoding attribute
#define ZIP_DECODE_LENGTH(ptr, encoding, lensize, len) do {
    / / analytic encoding
    ZIP_ENTRY_ENCODING((ptr), (encoding));                                     
    if ((encoding) < ZIP_STR_MASK) { 
        // When the element is a byte array
        // Distinguish the encoding type from the first two characters of the first byte (maximum length)
        // Select lensize and len
        if ((encoding) == ZIP_STR_06B) { 
            (lensize) = 1;                                                     
            (len) = (ptr)[0] & 0x3f;                                           
        } else if ((encoding) == ZIP_STR_14B) {                                
            (lensize) = 2;                                                     
            (len) = (((ptr)[0] & 0x3f) < <8) | (ptr)[1];                       
        } else if ((encoding) == ZIP_STR_32B) {                                
            (lensize) = 5;                                                     
            (len) = ((ptr)[1] < <24) |                                         
                    ((ptr)[2] < <16) |                                         
                    ((ptr)[3] < <8) |                                         
                    ((ptr)[4]);                                                
        } else {                                                               
            panic("Invalid string encoding 0x%02X", (encoding)); }}else { 
        // If the element is an integer, the encoding length is 1 byte
        (lensize) = 1;
        // Resolve the length of the integer len(len) = zipIntSize(encoding); }}while(0);

#define ZIP_ENTRY_ENCODING(ptr, encoding) do {  
    (encoding) = (ptr[0]);
    // Handle the first byte of the encoding attribute:
    // 1. PTR [0] < ZIP_STR_MASK, which is a byte array
    // 2. PTR [0] >= ZIP_STR_MASK, which is an integer and is not processed
    if ((encoding) < ZIP_STR_MASK) (encoding) &= ZIP_STR_MASK; 
} while(0);

unsigned int zipIntSize(unsigned char encoding) {
    // Compare encoding with len
    switch(encoding) {
    case ZIP_INT_8B:  return 1;
    case ZIP_INT_16B: return 2;
    case ZIP_INT_24B: return 3;
    case ZIP_INT_32B: return 4;
    case ZIP_INT_64B: return 8;
    }
    Len =0; len=0; len=0
    if (encoding >= ZIP_INT_IMM_MIN && encoding <= ZIP_INT_IMM_MAX)
        return 0;
    panic("Invalid integer encoding 0x%02X", encoding);
    return 0;
}
Copy the code

4. Basic operations

4.1 Creating a Compressed linked list

// ziplist.c
unsigned char *ziplistNew(void) {
    // Initial memory size = Compressed list head + tail = ZLbytes +zltail+zllen+zlend = 4+4+2+1 = 11
    unsigned int bytes = ZIPLIST_HEADER_SIZE+1;
    // Allocate memory
    unsigned char *zl = zmalloc(bytes);
    // Initialize compressed linked list attributes
    ZIPLIST_BYTES(zl) = intrev32ifbe(bytes);
    ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE);
    ZIPLIST_LENGTH(zl) = 0;
    // Set the trailing identifier 0xFF
    zl[bytes- 1] = ZIP_END;
    return zl;
}
Copy the code

4.2 Inserting Elements

Insert elements into a compressed list:

  • Element code
  • Reallocate space
  • Data replication
2 codes

Encoding parses the element’s previous_entry_Length, encoding, and content attributes

4.2.1.1 Insert Element Position

  • P0: When there is no element in the compressed list, the previous element does not exist, that is, the length of the previous element is 0
  • P1: The byte length of entryX element is required when inserting in the middle of an existing element in the compressed list. The previous_entry_length attribute of entryX+1 stores the byte length of entryX element, which can be obtained directly
  • P2: Obtain the byte length of entryN element after compression and insertion. Prevrawlensize, Lensize, and len of entryN element need to be parsed and added to obtain the length
4.2.1.2 Parsing Element Attributes
// ziplist.c
// zl: points to the start of the compressed list
// p: points to the insertion position of the element
// s: points to the inserted data content
// slen: indicates the length of data in bytes
unsigned char *__ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) {
    size_t curlen = intrev32ifbe(ZIPLIST_BYTES(zl)), reqlen;
    unsigned int prevlensize, prevlen = 0;
    size_t offset;
    int nextdiff = 0;
    unsigned char encoding = 0;
    long long value = 123456789;
    zlentry tail;

    if (p[0] != ZIP_END) {
        // The insertion position is in the middle of an existing element in the compressed list
        // call ZIP_DECODE_PREVLEN() to parse prevlen
        ZIP_DECODE_PREVLEN(p, prevlensize, prevlen);
    } else {
        // The insertion position is the end of the compression list
        unsigned char *ptail = ZIPLIST_ENTRY_TAIL(zl);
        Prevlen is resolved with zipRawEntryLength() when a tail element exists
        Prevlen =0; prevlen=0; prevlen=0
        if (ptail[0]! = ZIP_END) { prevlen = zipRawEntryLength(ptail); }}// Try to parse the data content s as an integer
    On success, the byte length of the integer s is further parsed according to encoding
    // On failure, s is a byte array with a length of slen
    if (zipTryEncoding(s,slen,&value,&encoding)) {
        reqlen = zipIntSize(encoding);
    } else {
        reqlen = slen;
    }
    
    // Get the length of previous_entry_length and encoding in bytes, and add up to reqlen
    reqlen += zipStorePrevEntryLength(NULL,prevlen);
    reqlen += zipStoreEntryEncoding(NULL,encoding,slen);

    // The length of the inserted element has been resolved
    // And the byte lengths and values of the three attributes
    / /...
}
Copy the code
4.2.1.3 Integer Resolution
// ziplist.c
int zipTryEncoding(unsigned char *entry, unsigned int entrylen, long long *v, unsigned char *encoding) {
    long long value;

    If the length of data content bytes is 0 or greater than or equal to 32, 0 is returned
    if (entrylen >= 32 || entrylen == 0) return 0;
    if (string2ll((char*)entry,entrylen,&value)) {
        // The data content is resolved to an integer value of type long long
        // Further parse out the encoding property
        if (value >= 0 && value <= 12) {
            *encoding = ZIP_INT_IMM_MIN+value;
        } else if (value >= INT8_MIN && value <= INT8_MAX) {
            *encoding = ZIP_INT_8B;
        } else if (value >= INT16_MIN && value <= INT16_MAX) {
            *encoding = ZIP_INT_16B;
        } else if (value >= INT24_MIN && value <= INT24_MAX) {
            *encoding = ZIP_INT_24B;
        } else if (value >= INT32_MIN && value <= INT32_MAX) {
            *encoding = ZIP_INT_32B;
        } else {
            *encoding = ZIP_INT_64B;
        }
        // Pass the value of value to the caller
        *v = value;
        return 1;
    }
    return 0;
}
Copy the code
4.2.1.4 Obtaining the byte length of the previous_entry_length attribute
// ziplist.c
unsigned int zipStorePrevEntryLength(unsigned char *p, unsigned int len) {
    
    if (p == NULL) {
        // if p == NULL, the length of the previous_entry_length attribute is returned
        // When len < 254, the previous_entry_length attribute takes up 1 byte
        // When len >= 254, the previous_entry_length attribute takes up 5 bytes
        return (len < ZIP_BIG_PREVLEN) ? 1 : sizeof(len)+1;
    } else {
        // p ! = NULL, len is stored in the previous_entry_length attribute
        if (len < ZIP_BIG_PREVLEN) {
            // The previous_entry_length attribute occupies 1 byte
            // The first byte stores len
            p[0] = len;
            return 1;
        } else {
            returnzipStorePrevEntryLengthLarge(p,len); }}}int zipStorePrevEntryLengthLarge(unsigned char *p, unsigned int len) {
    if(p ! =NULL) {
        // Previous_entry_length takes up 5 bytes
        // The first byte is fixed to 0xFE
        // The last four bytes are stored len
        p[0] = ZIP_BIG_PREVLEN;
        memcpy(p+1,&len,sizeof(len));
        memrev32ifbe(p+1);
    }
    return 1+sizeof(len);
}
Copy the code
4.2.1.5 Obtaining the length of the Encoding attribute
// ziplist.c
unsigned int zipStoreEntryEncoding(unsigned char *p, unsigned char encoding, unsigned int rawlen) {
    unsigned char len = 1, buf[5];

    if (ZIP_IS_STR(encoding)) {
        // The data type is byte array
        // p=NULL returns the length of the encoding attribute
        // p! =NULL stores the type and length of the byte array in the Encoding property
        if (rawlen <= 0x3f) {
            // The length of the byte array must be shorter than or equal to 63 bytes. The encoding attribute takes up one byte
            if(! p)return len;
            buf[0] = ZIP_STR_06B | rawlen;
        } else if (rawlen <= 0x3fff) {
            // the length of the array is 63,2^14-1. The encoding attribute takes 2 bytes
            len += 1;
            if(! p)return len;
            buf[0] = ZIP_STR_14B | ((rawlen >> 8) & 0x3f);
            buf[1] = rawlen & 0xff;
        } else {
            // The length of the array is 2^14-1,2^32-1. The encoding attribute takes up 5 bytes
            len += 4;
            if(! p)return len;
            buf[0] = ZIP_STR_32B;
            buf[1] = (rawlen >> 24) & 0xff;
            buf[2] = (rawlen >> 16) & 0xff;
            buf[3] = (rawlen >> 8) & 0xff;
            buf[4] = rawlen & 0xff; }}else {
        // The data type is integer
        // p=NULL returns the length of bytes required for the encoding property
        // p! =NULL, stores the type of the integer in the Encoding property
        if(! p)return len;
        buf[0] = encoding;
    }

    memcpy(p,buf,len);
    return len;
}
Copy the code
4.2.2 Redistributing space

When new elements are inserted, the compressed list has more space, so it needs to be reallocated

New space size = old space size + new element space size, this equation is not completely valid. Assume that the entryX element is 128 bytes long before the element is inserted, and the previous_entry_length attribute of the entryX+1 element is 1 byte. When adding an entryNew element with a length of 1024 bytes, the entryX+1 element’s previous_entry_length attribute takes up 5 bytes, meaning that the compressed list increases the length by 1024 bytes, plus 4 bytes of the entryX+1 element extension. The entryX+1 element length may increase by 4 bytes, decrease by 4 bytes, or remain the same

// ziplist.c
unsigned char *__ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) {
    / /...

    int forcelarge = 0;
    Nextdiff indicates the change in the length of the next element when a new element is inserted, which may be 0, -4, or +4
    Nextdiff =0; nextdiff=0; nextdiff=0
    // Otherwise nextDiff is further calculated
    nextdiff = (p[0] != ZIP_END) ? zipPrevLenByteDiff(p,reqlen) : 0;
    if (nextdiff == 4 - && reqlen < 4) {
        // Nextdiff = -4 and reqlen < 4
        // Reallocating space may result in data loss (data is not replicated yet)
        // To avoid this, reassign nextDiff =0 and mark forcelarge=1
        // The above situation does not usually occur, only after the chain update can exist
        nextdiff = 0;
        forcelarge = 1;
    }

    // Reallocate the space, which may cause the insertion position p to fail
    // So record the offset of pointer p relative to the start address of the compressed list, zl
    offset = p-zl;
    // Reallocate space
    zl = ziplistResize(zl,curlen+reqlen+nextdiff);
    // recalculate the insertion position p
    p = zl+offset;

    / /...
}

int zipPrevLenByteDiff(unsigned char *p, unsigned int len) {
    unsigned int prevlensize;
    Prevlensize calculates the length of the previous_entry_length attribute that p points to
    ZIP_DECODE_PREVLENSIZE(p, prevlensize);
    Len calculates the length of the previous_entry_length attribute in bytes
    // Then subtract from prevlenSize
    return zipStorePrevEntryLength(NULL, len) - prevlensize;
}
Copy the code
4.2.3 Data Replication

After the memory is reallocated, you need to move the element after position P to the specified location to free up the memory space of the element to be inserted, and then insert the element

// ziplist.c
unsigned char *__ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) {
    / /...
  
    if (p[0] != ZIP_END) {
        // If it is not a tail insert, the element after position p needs to be moved
      
        // Copy all elements after p to the new location
        // The block length is the total byte length of all elements after p plus nextDiff
        memmove(p+reqlen,p-nextdiff,curlen-offset- 1+nextdiff);

        // Update the previous_entry_length attribute of the element next to the element to be inserted
        if (forcelarge)
            zipStorePrevEntryLengthLarge(p+reqlen,reqlen);
        else
            zipStorePrevEntryLength(p+reqlen,reqlen);

        / / update the zltail
        ZIPLIST_TAIL_OFFSET(zl) =
            intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+reqlen);

        // Decode the element after the element to be inserted to tail
        zipEntry(p+reqlen, &tail);
        if(p[reqlen+tail.headersize+tail.len] ! = ZIP_END) {Zltail also needs to offset NextDiff if the next element to be inserted is not a last elementZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff); }}else {
        // If a tail is inserted, the offset from p (the first address of the element to be inserted) to the first address of the compressed list is zltail
        ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(p-zl);
    }

    if(nextdiff ! =0) {
        // If nextDiff is not 0, then the compressed list may need to be continuously updated
        // This invalidates the start address of the compressed list and the insertion position p, so reassignment may be required
        offset = p-zl;
        zl = __ziplistCascadeUpdate(zl,p+reqlen);
        p = zl+offset;
    }

    // Encode the previous_entry_length, encoding, and content of the element to be inserted and store them at insert position P
    p += zipStorePrevEntryLength(p,prevlen);
    p += zipStoreEntryEncoding(p,encoding,slen);
    if (ZIP_IS_STR(encoding)) {
        memcpy(p,s,slen);
    } else {
        zipSaveInteger(p,value,encoding);
    }
    / / zllen plus 1
    ZIPLIST_INCR_LENGTH(zl,1);
    return zl;
}
Copy the code

4.3 Deleting Elements

Steps to remove elements from a compressed list:

  • Calculates the total length of the element to be deleted
  • Data replication
  • Reallocate memory
4.3.1 Calculate the total length of elements to be deleted
// ziplist.c
unsigned char *__ziplistDelete(unsigned char *zl, unsigned char *p, unsigned int num) {
    unsigned int i, totlen, deleted = 0;
    size_t offset;
    int nextdiff = 0;
    zlentry first, tail;

    // Decode the first element to be deleted first
    zipEntry(p, &first);
    // The pointer p moves to the end of the last element to be deleted
    // Simultaneously count deleted elements
    for (i = 0; p[0] != ZIP_END && i < num; i++) {
        p += zipRawEntryLength(p);
        deleted++;
    }

    // Calculate the total length of the element to be deleted
    totlen = p-first.p;
    
    / /...
}
Copy the code
4.3.2 Data Replication

Size of new space = size of old space – total length of elements to be deleted, this equation is not completely valid. If you delete elements between entryX+1 and entryn-1, the length of entryn-1 is 12 bytes, so the previous_entry_length attribute of entryN takes up 1 byte. After the element is deleted, the 512-byte entryX element becomes the first element of entryN. In this case, the previous_entry_length attribute of entryN needs to occupy 5 bytes. The total length of the compressed list after the element is deleted is also related to the entryN length of the element

// ziplist.c
unsigned char *__ziplistDelete(unsigned char *zl, unsigned char *p, unsigned int num) {
    / /...
  
    if (totlen > 0) {
        if (p[0] != ZIP_END) {
            // If the element to be deleted is deleted, p indicates that the element exists

            // Compute the nextdiff of the change in the length of the bytes p points to the element
            nextdiff = zipPrevLenByteDiff(p,first.prevrawlen);

            // Move p according to nextdiff
            p -= nextdiff;
            // Update p to point to the byte length of the previous element stored by the element's previous_entry_length attribute
            zipStorePrevEntryLength(p,first.prevrawlen);

            // Update zltail according to totlen
            ZIPLIST_TAIL_OFFSET(zl) =
                intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))-totlen);

            // Decode p to the element tail
            zipEntry(p, &tail);
            if(p[tail.headersize+tail.len] ! = ZIP_END) {// Update zltail when there are elements after tail
                ZIPLIST_TAIL_OFFSET(zl) =
                   intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff);
            }

            // Copy all elements after p to the new location
            // The block length is the total byte length of all elements after p
            memmove(first.p,p,
                intrev32ifbe(ZIPLIST_BYTES(zl))-(p-zl)- 1);
        } else {
            // If the element to be deleted is deleted, p indicates that the element does not exist
            // Calculate zltAIL directly without data replication
            ZIPLIST_TAIL_OFFSET(zl) =
                intrev32ifbe((first.p-zl)-first.prevrawlen);
        }

        / /...
    }
  
    / /...
}
Copy the code
4.3.3 Reallocating memory
// ziplist.c
unsigned char *__ziplistDelete(unsigned char *zl, unsigned char *p, unsigned int num) {
    / /...
  
    if (totlen > 0) {
        / /...

        // The first address and pointer p of the compressed list were invalidated during memory reallocation
        // Need to reassign
        offset = first.p-zl;
        zl = ziplistResize(zl, intrev32ifbe(ZIPLIST_BYTES(zl))-totlen+nextdiff);
        / / update the zllen
        ZIPLIST_INCR_LENGTH(zl,-deleted);
        p = zl+offset;

        if(nextdiff ! =0)
            // nextdiff! When =0, the length of the bytes p points to the element changes
            // May cause subsequent elements to require cascading updates
            zl = __ziplistCascadeUpdate(zl,p);
    }
    return zl;
}
Copy the code

4.4 Iterating through the Compression List

4.4.1 Forward traversal
// ziplist.c
unsigned char *ziplistNext(unsigned char *zl, unsigned char *p) {((void) zl);

    
    if (p[0] == ZIP_END) {
        // when p points to zlend, there are no more elements to traverse
        return NULL;
    }

    // Get the length of the bytes that point to the element and move the length to the beginning of the next element
    p += zipRawEntryLength(p);
    if (p[0] == ZIP_END) {
        return NULL;
    }

    return p;
}
Copy the code
4.4.2 Backward Traversal
// ziplist.c
unsigned char *ziplistPrev(unsigned char *zl, unsigned char *p) {
    unsigned int prevlensize, prevlen = 0;

    if (p[0] == ZIP_END) {
        // When p points to zlend, redirect p to the tail element
        // Return if the tail element exists
        // If the tail element does not exist, there is no element to traverse
        p = ZIPLIST_ENTRY_TAIL(zl);
        return (p[0] == ZIP_END) ? NULL : p;
    } else if (p == ZIPLIST_ENTRY_HEAD(zl)) {
        // when p points to the header element, there are no more elements to traverse
        return NULL;
    } else {
        // The byte length of the previous element stored according to the previous_entry_length attribute p points to the element
        // redirect p to the first address of the previous element
        ZIP_DECODE_PREVLEN(p, prevlensize, prevlen);
        assert(prevlen > 0);
        returnp-prevlen; }}Copy the code

4.5 Chain Update

When an element is inserted or deleted, the byte length of the element following the operation location may change, as well as the byte length of subsequent elements

  • When zL1 deletes element extryX at p1, the previous element of element entryX+1 becomes element entryx-1, and the length of the previous element changes from 128 bytes to 512 bytes. The length of entryX+1 needs to be expanded from 253 bytes to 257 bytes. (If the length of the preceding element is 254 bytes or greater, the length of previous_entry_length is 5 bytes.) And so on, a chain of updates
  • When zL2 inserts the element extryY in position P2, similar to the above deletion, the byte length of the previous element increases, causing the byte length of the following elements to also increase, and so on, chain updates occur
  • When an element is inserted or deleted, the byte length of the previous element becomes smaller, causing the byte length of the following element to become smaller, and Redis does nothing

// ziplist.c
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;

    // execute chaining update logic when p points to an element
    while (p[0] != ZIP_END) {
        // Decode p to the element cur
        zipEntry(p, &cur);
        // Get rawlen, the byte length of the element cur
        rawlen = cur.headersize + cur.len;
        // Get the length of the previous_entry_length attribute rawlensize
        rawlensize = zipStorePrevEntryLength(NULL,rawlen);

        // If the next element of element cur does not exist, there is no need to perform chained update logic
        if (p[rawlen] == ZIP_END) break;
        // p+rawlen points to the next element and decodes the element next
        zipEntry(p+rawlen, &next);

        // If the previous_entry_length attribute of element next stores the previous element's byte length unchanged
        // No chained update logic is required
        if (next.prevrawlen == rawlen) break;

        if (next.prevrawlensize < rawlensize) {
            // If the previous_entry_length attribute of element next is larger in bytes
          
            // The first address and pointer p of the compressed list were invalidated during memory reallocation
            // Need to reassign
            offset = p-zl;
            // Calculate the length of bytes needed to expand the previous_entry_length attribute of the element next extra
            extra = rawlensize-next.prevrawlensize;
            zl = ziplistResize(zl,curlen+extra);
            p = zl+offset;

            // np points to the first address of the element next
            np = p+rawlen;
            // The offset noffset of the first address of the element next relative to the first address of the compressed list
            noffset = np-zl;

            if((zl+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))) ! = np) {// If the element next is not the last element in the compressed list
                // Zltail needs to be updated
                ZIPLIST_TAIL_OFFSET(zl) =
                        intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+extra);
            }

            // Copy the data after the encoding attribute of the element next to the new address
            memmove(np+rawlensize,
                    np+next.prevrawlensize,
                    curlen-noffset-next.prevrawlensize- 1);
            // Store rawlen bytes of the cur element into the previous_entry_length attribute of the next element
            zipStorePrevEntryLength(np,rawlen);

            // Move the pointer p to the next element that needs to perform chained update logic
            p += rawlen;
            // Update the compressed list of bytes curlen
            curlen += extra;
        } else {
            if (next.prevrawlensize > rawlensize) {
                // If the length of the previous_entry_length attribute of the element next can be reduced
                // The chained update logic is not executed
                // Update only the values stored in the element next's previous_entry_length attribute (the byte length of the element cur)
                zipStorePrevEntryLengthLarge(p+rawlen,rawlen);
            } else {
                // If the length of the previous_entry_length attribute of element next remains the same
                // The chained update logic is not executed
                // Update only the values stored in the element next's previous_entry_length attribute (the byte length of the element cur)
                zipStorePrevEntryLength(p+rawlen,rawlen);
            }

            break; }}return zl;
}
Copy the code

Redis 5 Design and source code Analysis