List of compression

Ziplist is one of the underlying implementations of list keys and hash keys. When a list key contains only a small number of list items, and each item is either a small integer value or a short string length, Redis uses compressed lists for the underlying implementation of the list key.

Compressing list composition

Compressed lists, developed by Redis to save memory, are sequential data structures composed of a series of specially encoded contiguous memory blocks. A compressed list can contain any number of entries, each of which can hold either a byte array or an integer value.

  • zlbytes: 4 bytes, recordThe number of bytes of memory occupied by the entire compressed list. Used when reallocating memory to a compressed list or calculating the location of Zlend
  • zltail: 4 bytes, records the compression listHow many bytes is the end of the table from the start address of the compressed list. With this offset, the address of the node at the end of the table can be determined without facilitating the entire compressed list
  • zllen: records the number of nodes in the compressed list. When the value of this attribute is less than 65535, the value of this attribute is the number of nodes contained in the compressed list. When this value is equal to 65535, the real number of nodes needs to be calculated conveniently
  • entryX: Compresses each node in the list. The length of the node is determined by the memory stored in the node
  • zlend: Special value 0xFF (decimal 255), used to mark the end of the compressed list

Compressing list node composition

Each compressed list can hold either a byte array or an integer value.

Each compressed list node consists of previous_entry_LENGTH, Encoding, and Content.

previous_entry_length

The previous_entry_length property records, in bytes, the length of the previous node in the compressed list. The length of the previous_entry_length attribute can be 1 or 5 bytes.

If the length of the previous object is less than 254 bytes, the length of the previous_entry_length attribute is 1 byte; Otherwise, the length is 5 bytes, where the first byte of the property is set to 0xFE and the next four bytes are used to hold the length of the previous node.

The compressed list traverses from the end of the table to the top of the table using this principle. As long as you have a pointer to the start address of a node, you can use this pointer and the previous_entry_length attribute of this node to trace back to the previous node and finally reach the top node of the compressed list.

encoding

The Encoding property records the type and length of data held by the node’s Content property.

content

The content property of a node holds the value of the node, which can be a byte array or an integer. The type and length of the value are determined by the encoding property of the node.

Chain update

Since the previous_entry_length attribute of each node records the length of the previous node, if there are multiple consecutive nodes between 250 and 253 bytes in a compressed list, The previous_entry_length attribute of the first node is only 1, so the length of the new node cannot be saved. Therefore, space redistribution is performed on the compressed list. Expand the previous_entry_length property of the current node from 1 byte to 5 bytes.

Similarly, a reallocation operation on the current node may affect the next node or, in the worst case, the last node.

Redis refers to this kind of continuous space expansion operation as “chained update”.

In addition to adding new nodes may cause cascading updates, deleting nodes may also cause cascading updates.

Because chained updates require N space reallocations of the compressed list in the worst case, and the worst complexity of each space reallocation is O(N), the worst complexity of continuous updates is O(N2).

Despite the complexity of chained updates, the chance of real performance problems is very low. First, the compression list happens to have multiple consecutive nodes between 250 and 253 bytes in length for cascading updates to be triggered, which is rare in practice. Second, even if there are cascading updates, there is no performance impact as long as the number of nodes being updated is small.