Shulou(Shulou.com)06/02 Report--

This article introduces the knowledge of "introduction and use of the underlying data structure of Redis". In the operation of actual cases, many people will encounter such a dilemma, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

Description

When it comes to the data structures of Redis, we will probably soon think of five common data structures of Redis: String, List, Hash, Set, Sorted Set, as well as their characteristics and application scenarios. But they are Redis exposed data structures for API operations, and what are the underlying data structures that make up them?

Simple dynamic string (SDS)

Linked list

Dictionaries

Jump table

Integer set

Compressed list

The GitHub address of Redis https://github.com/antirez/redis

Simple dynamic string (SDS)

Redis is written in C, but instead of using the string representation of C (C is an array of characters ending with\ 0 empty characters), Redis builds an abstract type of simple dynamic string (simple dynamic string,SDS) and represents it as the default string for Redis.

In Redis, the underlying key-value pairs that contain string values are implemented in SDS

Definition of SDS

The structure of SDS is defined in the sds.h file. After version 3.2 of Redis, the definition of SDS has changed from one data structure to five data structures. Different structures will be selected according to the content length of SDS storage, in order to achieve the effect of memory saving. For the specific structure definition, let's see the following code.

/ / 3.0struct sdshdr {/ / record the number of bytes used in the buf array, that is, the length of the string saved by SDS unsigned int len; / / record the number of unused bytes in the buf data unsigned int free; / / byte array, used to save the string char buf [];}; / 3.2 Note: sdshdr5 is never used, we just access the flags byte directly. * However is here to document the layout of type 5 SDS strings. * / struct _ attribute__ ((_ packed__)) sdshdr5 {unsigned char flags; / * 3 lsb of type, and 5 msb of string length * / char buf [];}; struct _ attribute__ ((_ _ packed__)) sdshdr8 {uint8_t len; / * used * / uint8_t alloc; / * excluding the header and null terminator * / unsigned char flags; / * 3 lsb of type, 5 unused bits * / char buf [];} Struct _ _ attribute__ ((_ _ packed__)) sdshdr16 {uint16_t len; / * used * / uint16_t alloc; / * excluding the header and null terminator * / unsigned char flags; / * 3 lsb of type, 5 unused bits * / char buf [];}; struct _ attribute__ ((_ _ packed__)) sdshdr32 {uint32_t len; / * used * / uint32_t alloc; / * excluding the header and null terminator * / unsigned char flags / * 3 lsb of type, 5 unused bits * / char buf [];}; struct _ attribute__ ((_ packed__)) sdshdr64 {uint64_t len; / * used * / uint64_t alloc; / * excluding the header and null terminator * / unsigned char flags; / * 3 lsb of type, 5 unused bits * / char buf [];}

After version 3.2, the corresponding data structure is selected according to the length of the string.

Static inline char sdsReqType (size_t string_size) {if (string_size)

fifty-four

The above is the search element, if you add an element, it is to flip a coin to determine how many layers the element will appear, that is to say, it will have the probability of a second level of one hand 2 and a probability of one hand four on the third level.

The deletion and addition of jump table nodes are unpredictable, it is difficult to ensure that the index of the jump table is always uniform, and the way of flipping a coin can make it generally uniform.

Suppose we already have a jump table for the above example, now add an element 18 to it, and determine the number of layers it will appear by flipping a coin, continue on the front and stop on the back, if I flip the coin twice, the first is the front and the second is the negative.

The deletion of the jump table is very simple, as long as you first find the node to be deleted, and then delete the same node in each layer.

The cost of maintaining the structural balance of the jump table is relatively low, and it depends entirely on randomness. Compared with the binary search tree, Rebalance is needed to readjust the structural balance after multiple insertions and deletions.

Realization of Jump Table

The implementation of the jump table of Redis is defined by redis.h/zskiplistNode and redis.h/zskiplist (redis.h has been changed to server.h after version 3.2). ZskiplistNode defines the node of the jump table, and zskiplist stores the relevant information of the jump table node.

/ * ZSETs use a specialized version of Skiplists * / typedef struct zskiplistNode {/ / member object (robj * obj;) sds ele; / / score double score; / / backward pointer struct zskiplistNode * backward; / / layer struct zskiplistLevel {/ / forward pointer struct zskiplistNode * forward / / Span / / Span is actually used to calculate the element ranking (rank). In the process of finding a node, the spans of all the layers visited along the way are accumulated, and the result is the ranking unsigned long span;} level of the target node in the jump table [];} zskiplistNode;typedef struct zskiplist {/ / header node and footer node struct zskiplistNode * header, * tail / / the number of nodes in the table unsigned long length; / / the number of layers of the node with the largest number of layers in the table int level;} zskiplist

ZskiplistNode structure

Level array (layer): each time a new jump table node is created, the size of the level array is calculated according to the power law, that is, the height of the secondary layer. Each layer has two attributes-forward pointer and span, and the forward pointer is used to access other pointers in the direction of the tail of the table. The span is used to record the distance between the current node and the node pointed to by the forward pointer (NULL, width 0).

Backward (back pointer): points to the previous node of the current node

Score (score): used to sort. If the score is the same, the member variables are sorted in lexicographic order.

Obj or ele: the member object is a pointer to a string object that holds a sds;. The member object of each node in the jump table must be unique, and the score can be the same.

Zskiplist structure

Header, tail header node and footer node

The number of nodes in the length table

The number of layers of the node with the largest number of layers in the level table

Suppose we now show a jump table with four nodes with heights of 2, 1, 4 and 3, respectively.

The header node of zskiplist is not a valid node. It has a ZSKIPLIST_ Maxlevel layer (layer 32). The forward of each layer points to the first node of the jump table of this layer. If not, it is NULL. In Redis, the structure of the above jump table is as follows

The number of layers of each jump table node is between 1 and 32.

In a jump table, the nodes are sorted by the size of the score, and the scores of multiple nodes can be the same. When the same, the nodes are sorted by the size of the member object.

The member variables of each node must be unique

Integer set

A set of integers (intset) is a collection abstract data structure used by Redis to hold integer values, which can save integer values of types int16_t, int32_t, and int64_t, and ensure that there are no duplicate elements in the set.

The set of integers is one of the underlying implementations of the set (Set). If a set contains only integer-valued elements and the number of elements is small, the set of integers will be used as the underlying implementation.

Definition and implementation of set of integers

The set of integers is defined as inset.h/inset

Typedef struct intset {/ / Encoding uint32_t encoding; / / the number of elements contained in the collection uint32_t length; / / an array of saved elements int8_t contents [];} intset

Contents array: each element of a collection of integers is sorted in the array by the size of the value, and does not contain duplicates.

Length records the number of elements in the set of integers, that is, the length of the contents array

Encoding determines the true type of contents array, such as INTSET_ENC_INT16, INTSET_ENC_INT32, INTSET_ENC_INT64

Upgrade of set of integers

When you want to add a new element to a collection of integers, and the type of the new element is longer than that of all existing elements in the collection of integers, the collection of integers needs to be upgrade before the new element can be added to the collection of integers. Every time you want to add a new element to a collection of integers, it is possible to cause an upgrade, and each upgrade requires a type conversion of all the elements already in the underlying array.

Upgrade to add a new element:

Expand the space size of the underlying array of integers according to the new element type, and allocate space for the new element

Convert the existing elements of the array to the type of the new element, put the converted elements in the correct position, and keep the array in order.

Add a new element to the underlying array

The upgrade strategy of integer set can improve the flexibility of integer set and save memory as much as possible.

In addition, the set of integers does not support degradation, and once upgraded, the coding will remain in the upgraded state.

Compressed list

Compressed list (ziplist) is designed to save memory. It is a sequential (sequential) data structure consisting of a series of specially encoded consecutive memory blocks. A compressed list can contain multiple nodes, each node can hold a byte array or an integer value.

Compressed list is one of the underlying implementations of list (List) and hash (Hash). A list contains only a small number of list items, and each list item is a small integer value or a relatively short string. Compressed list is used as the underlying implementation (quicklist is used after version 3.2).

The composition of compressed lists

A compressed list can contain multiple nodes (entry), each of which can hold an array of bytes or an integer value

The composition of each part is described as follows

Zlbytes: records the number of bytes of memory occupied by the entire compressed list, used when redistributing memory in the compressed list, or when calculating the location of the zlend

Zltail: record how many bytes the trailer node of the compressed list is from the starting address of the compressed list. With this offset, the address of the footer node can be determined without traversing the entire compressed list.

Zllen: record the number of nodes contained in the compressed list, but when the attribute value is less than UINT16_MAX (65535), this value is the number of nodes in the compressed list, otherwise you need to traverse the entire compressed list to calculate the real number of nodes.

EntryX: the node that compresses the list

Zlend: special value 0xFF (decimal 255), used to mark the end of the compressed list

Composition of compressed list nodes

Each compressed list node can hold a byte number or an integer value, which is structured as follows

Previous_entry_ength: record the length of the first byte of the compressed list

Encoding: the node's encoding holds the content type of the node's content

The content:content area is used to save the content of the node, and the content type and length of the node are determined by the encoding.

Object

The above describes the main underlying data structures of Redis, including simple dynamic strings (SDS), linked lists, dictionaries, jump tables, sets of integers, and compressed lists. But instead of directly using these data structures to build a key-value pair database, Redis creates an object system based on these data structures, that is, the well-known Redis data types that can be operated by API, such as String, List, Hash, Set, Sorted Set.

According to the type of object, we can judge whether an object can execute a given command, or according to different usage scenarios, the object settings can be implemented with a variety of different data structures, so as to optimize the use efficiency of objects in different scenes.

Type Encoding BOJECT ENCODING Command output object REDIS_STRINGREDIS_ENCODING_INT "int" string object implemented using integer values REDIS_STRINGREDIS_ENCODING_EMBSTR "embstr" string object implemented using embstr encoded simple dynamic string REDIS_STRINGREDIS_ENCODING_RAW "raw" string object REDIS_LISTREDIS_ENCODING_ZIPLIST "ziplist" implemented with simple dynamic string using compressed list object REDIS_LISTREDIS_ ENCODING_LINKEDLIST' "linkedlist' list object REDIS_HASHREDIS_ENCODING_ZIPLIST" ziplist using compressed list REDIS_HASHREDIS_ENCODING_HT "hashtable" Hash object REDIS_SETREDIS_ENCODING_INTSET "intset" Collection object REDIS_SETREDIS_ENCODING_HT "hashtable" implemented by integer collection REDIS_ZSETREDIS_ENCODING_ZIPLIST "ziplist" implemented by dictionary use The ordered collection object REDIS_ZSETREDIS_ENCODING_SKIPLIST "skiplist" implemented by the compressed list uses the jump table table to implement the ordered collection object "introduction and use of Redis underlying data structures". This is the end of the introduction. Thank you for your reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.