The original address: www.xilidou.com/2018/03/13/…

The last article wrote about the basic Redis data structure mutable strings, linked lists, dictionaries. You can check out the link. Today we continue to look at the basic data structures of Redis.

• The integer set
• Jump table
• List of compression

The integer set

Redis uses the integer set intset when a set contains only integers and the set has few elements. Let’s look at the intSet data structure:

typedef struct intset {
    
    // Encoding mode
    uint32_t encoding;

    // The number of elements the collection contains
    uint32_t length;

    // Hold an array of elements
    int8_t contents[];
} intset;

Copy the code

The intset data structure is easier to understand. A data store element, length holds the number of elements, which is the size of contents, and encoding holds how the data is encoded.

The encoding type of encoding includes:

#define INTSET_ENC_INT16 (sizeof(int16_t))
#define INTSET_ENC_INT32 (sizeof(int32_t))
#define INTSET_ENC_INT64 (sizeof(int64_t))
Copy the code

We can actually see that. The type of Redis encoding is the size of the index. As an in-memory database, this design is intended to save memory. For a number we can draw a graph to help us understand:

Since there are three data structures from small to large, use a small data structure to save memory when inserting data. If the inserted data is larger than the original data structure, capacity expansion will be triggered.

There are three steps for capacity expansion:

1. Depending on the type of the new element, change the data type of the entire array and reallocate the space
2. Replace the original data with the new data type, and put it back in the place it should be, and preserve the order
3. Insert a new element

Integer collections do not degrade and cannot be degraded once they are upgraded.

Jump table

Skip list is a kind of linked list. It is a data structure that uses space for time. Hop tables support lookups of O(logN) complexity on average and O(N) complexity at worst.

A skip table consists of a ZSkiplist and multiple ZskiplistNodes. Let’s look at their structure first:

/* ZSETs use a specialized version of Skiplists */
/* * Skip list node */
typedef struct zskiplistNode {

    // Member objects
    robj *obj;

    / / score
    double score;

    // Back up the pointer
    struct zskiplistNode *backward;

    / / layer
    struct zskiplistLevel {

        // Forward pointer
        struct zskiplistNode *forward;

        / / span
        unsigned int span;

    } level[];

} zskiplistNode;

/* * skip list */
typedef struct zskiplist {

    // Table header and table tail nodes
    struct zskiplistNode *header, *tail;

    // The number of nodes in the table
    unsigned long length;

    // The number of layers of the node with the largest middle level in the table
    int level;

} zskiplist;

Copy the code

So according to this code we can draw the following structure diagram:

In fact, a skip table is a data structure that uses space for time, using level as the index of the linked list.

The Redis authors were asked why they use skip lists instead of trees to build indexes. The author’s answer:

1. In the province.
2. Serving ZRANGE or ZREVRANGE is a typical linked list scenario. Time complexity behaves much like a balanced tree.
3. The most important point is that skip lists are easy to implement at the O(logN) level.

List of compression

Compressed linked list Redis is a bidirectional linked list designed to save as much memory as possible.

For a compressed list, the comments in the code give the following data structure:

Zlbytes indicates the number of memory bytes used for the entire compressed list

Zltail specifies the offset of the last node of the compressed list

Zllen is the number of compressed list entries

Entry is the ziplist node

The zlend flag compresses the end of the list

There is also a single pointer to the list:

ZIPLIST_ENTRY_HEAD Specifies the head offset of the start node of the list

ZIPLIST_ENTRY_TAIL Header offset of the end node of the list

ZIPLIST_ENTRY_END The offset at the end of the last node in the list

Let’s look at the structure of an entry:

/* * Save ziplist node information structure */
typedef struct zlentry {

    Prevrawlen: Length of the front node
    Prevrawlensize: Size of bytes required to encode prevrawlen
    unsigned int prevrawlensize, prevrawlen;

    Len: the length of the current node value
    // lensize: the size of the bytes required to encode len
    unsigned int lensize, len;

    // The size of the current node header
    // prevrawlenSize + lenSize
    unsigned int headersize;

    // The encoding type used for the current node value
    unsigned char encoding;

    // Pointer to the current node
    unsigned char *p;

} zlentry;

Copy the code

Explain each of these parameters in turn.

Prevrawlen: prevrawlen: prevrawlen: prevrawlen: prevrawlen: prevrawlen: prevrawlen: prevrawlen: prevrawlen: prevrawlen Instead of using the default int length to save memory, Redis gradually upgraded it. Similarly len records the length of the current node, lensize records the length of Len. Headersize is the sum of the two sizes mentioned above. Encoding is the data type of this node. Note here that the encoding type only includes integers and strings. Pointers to p nodes, without too much explanation.

Need to note, because each node to save the length of the previous node, if the update or delete nodes, and the data also needs to be modified after this node, there is a kind of in the worst case is that if each node in the zero point of the expansion and need, can cause after the node is to change the size of the parameters, triggered a chain reaction. This is the worst time complexity O(n^2) for compressed lists. However, all nodes are at critical value, so the probability of this is relatively small.

conclusion

This concludes the basic data structure of Redis. We can see that Redis is really stingy with memory usage, especially with regard to memory usage. At the same time, As a single-threaded application, Redis does not need to consider the problem of concurrency, exposing many parameters like size or length, and reducing many O(n) operations to O(1). Greatly improve efficiency. In the next lecture, we’ll look at how Redis provides services externally through these data structures. Redis code is really written well, simple and efficient. It is worth learning.

Welcome to follow my wechat official account: