Shulou(Shulou.com)05/31 Report--

Redis data structure of the underlying implementation analysis, many novices are not very clear about this, in order to help you solve this problem, the following editor will explain for you in detail, people with this need can come to learn, I hope you can gain something.

1. Overview

Redis is an open source key-value database written in ANSI C language. We may subjectively think that the string in Redis is represented by the traditional string in C language, but it is not. Instead of directly using the traditional string representation in C language, Redis has constructed an abstract type called simple dynamic string (simple dynamic string SDS). And use SDS as the default string representation of Redis: redis > SET msg "hello world"

SDS definition:

Struct sdshdr {/ / record the number of bytes used in the buf array / equal to the length of the SDS saved string int len; / / record the number of unused bytes in the buf array int free; / / byte array, used to hold the string char buf [];}

Photo Source: "Redis Design and implementation"

Let's look at the definition of the SDS data type above:

Len saves the length of the string saved by SDS

The buf [] array is used to hold each element of the string

Free j records the number of unused bytes in the buf array

2. Compared with C language

In general, in addition to saving string values in the database, SDS can also be used as a buffer: an AOF buffer in the AOF module and an input buffer in the client state. It will be covered later when we introduce the persistence of Redis.

III. Linked list

1. Overview

The linked list provides efficient node rearrangement ability and sequential node access, and the length of the linked list can be flexibly adjusted by adding and deleting nodes.

Linked lists are widely used in Redis. For example, one of the underlying implementations of list keys is linked lists. When a list key contains a large number of elements, or when the elements in the list are long strings, Redis uses the linked list as the underlying implementation of the list key.

Each linked list node is represented by a listNode structure (adlist.h/listNode):

Typedef struct listNode {/ / Front node struct listNode * prev; / / Post node struct listNode * next; / / value of the node void * value;} listNode

Data structure of linked list:

Typedef struct list {/ / header node listNode * head; / / number of nodes contained in the footer node listNode * tail; / / Node value copy function void (* free) (void * ptr); / / Node value release function void (* free) (void * ptr) / / Node value comparison function int (* match) (void * ptr,void * key);} list

Composition structure diagram

2. Characteristics of Redis linked list

Double-ended: the linked list has references to the front node and the post node, and the time complexity of getting both nodes is O (1).

Acyclic: both the prev pointer of the header node and the next pointer of the footer node point to NULL, and access to the linked list ends with NULL.

Length counter with linked list: the time complexity of getting the length of the linked list through the len property is O (1).

Polymorphism: linked list nodes use void* pointers to hold node values, which can save different types of values.

IV. Dictionary

1. Overview

A dictionary, also known as a symbol table or associative array, or map, is an abstract data structure used to hold key-value pairs. Each key key in the dictionary is unique, and the value can be found or modified through key. There is no built-in implementation of this data structure in C, so the dictionary is still built by Redis itself.

Hash table structure definition:

Typedef struct dictht {/ / Hash table array dictEntry * * table; / / Hash table size unsigned long size; / / Hash table size mask, which is used to calculate the index value / / always equal to size-1 unsigned long sizemask; / / the number of nodes already in the hash table unsigned long used;} dictht

The hash table consists of an array table. Each element in table points to the dict.h/dictEntry structure. The dictEntry structure is defined as follows:

Typedef struct dictEntry {/ / key void * key; / / value union {void * val; uint64_tu64; int64_ts64;} v; / / points to the next hash table node to form a linked list struct dictEntry * next;} dictEntry

The key is used to save the key, and the val property is used to hold the value, which can be a pointer, a uint64_t integer, or an int64_t integer.

Notice that there is also a pointer to the next hash table node. We know that the biggest problem with the hash table is the existence of hash conflicts, how to solve the hash conflicts, there are open address method and chain address method. What is used here is the chain address method, through the pointer next, multiple key-value pairs with the same hash value can be connected together to solve the hash conflict.

Fifth, jump table

1. Overview

Jump table (skiplist) is an ordered data structure, which can quickly access nodes by maintaining multiple pointers to other nodes in each node. The jump table is a kind of randomized data, and the jump table stores elements in a hierarchical linked list in an orderly way, and its efficiency is comparable to that of the balanced tree-- searching, deleting, adding and other operations can be done in the logarithmic expected time, and compared with the balanced tree, the implementation of the jump table is much simpler and more intuitive.

Redis only uses jump tables in two places, one to implement ordered collection keys, and the other to be used as an internal data structure in cluster nodes.

The jump table node in Redis is defined as follows:

Typedef struct zskiplistNode {/ / layer struct zskiplistLevel {/ / forward pointer struct zskiplistNode * forward; / / Span unsigned int span;} level []; / / backward pointer struct zskiplistNode * backward; / / score double score; / / member object robj * obj;} zskiplistNode

Multiple jump table nodes form a single jump table:

Typedef struct zskiplist {/ / header node and footer node structz skiplistNode * header, * tail; / / 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

The header and tail pointers point to the header and footer nodes of the jump table, respectively.

The length attribute records the number of nodes

The level attribute records the number of layers at which the number of layers is the highest.

The following figure shows the complete jump table and the detailed structure diagram of a single node, respectively:

2. Characteristics

The jump table has the following properties:

It consists of many layers of structure.

Each layer is an ordered linked list.

The linked list at the lowest level (Level 1) contains all the elements

If an element appears in the linked list of Level I, it also appears in the linked list under Level I.

Each node contains two pointers, one to the next element in the same list and one to the element in the lower layer.

VI. Set of integers

1. Overview

The set of integers is defined in Redis Design and implementation as follows: "the set of integers is one of the underlying implementations of the collection. When a set contains only integers and the number of elements in the set is small, redis uses the set of integers intset as the underlying implementation of the set."

We can understand the set of integers in this way, it is actually a special set, the data stored in it can only be integers, and the amount of data can not be too large.

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

Let's take a look at a completed integer set structure diagram:

Encoding: used to define the encoding of a collection of integers

Length: used to record the number of variables in a collection of integers

Contents: an array used to hold elements. Although we see in the data structure diagram that intset defines the array as int8_t, the type of elements that the array holds actually depends on encoding.

2. Characteristics

The set of integers is one of the underlying implementations of set construction.

The underlying implementation of the set of integers is an array, which holds the set elements in an ordered, non-repetitive normal form. If necessary, the program will change the type of the array according to the newly added element type.

The upgrade operation brings operational flexibility to the set of integers and saves memory 2 as much as possible

Sets of integers only support upgrade operations, not demotion operations

7. Compress list

1. Overview

A compressed list 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 list item is either a small integer or a short string, Redis uses a compressed list as the underlying implementation of the list key.

A compressed list consists of the following:

Zlbytes: used to record the number of bytes of memory consumed by the entire compressed list

Zltail: record how many bytes the end node of the list is from the starting address of the compressed list

Zllen: records the number of nodes contained in the compressed list

EntryX: to say that the list contains each node

Zlend: used to mark the end of a compressed list

2. Characteristics

Compressed list is a sequential data structure developed to save memory.

Compressed list is used as one of the underlying implementations of list keys and hash keys

A compressed list can contain multiple nodes, each of which can hold an array of bytes or integer values

Adding a new node to the compressed list may trigger chained update operations.

Is it helpful for you to read the above content? If you want to know more about the relevant knowledge or read more related articles, please follow the industry information channel, thank you for your support.

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.