Rodert single row learning redis advanced [Bronze]

Posted Jun 16, 202014 min read

bronze of redis

[toc]

Unsuccessful uploading of individual pictures, please read PDF.

å ¨è¿  é  æ?? å ¥å ¾ç  æ????è¿ °

Foreword

Disclaimer:Refer to the source Internet, you can leave a message if you have any disputes. Standing on the shoulders of our predecessors, we can see further.

This tutorial is pure hand-made, dedicated to the most practical tutorial, no rewards are needed, just hope that a lot of forwarding support.
Welcome to my public account, I hope to get to know you, or remind you, WeChat search:JavaPub

If you have any questions, please come and talk!

å ¨è¿  é  æ?? å ¥å ¾ç  æ????è¿ °

This article continues to study Redis, the previous one [rodert single row learning redis introduction [black iron]]( https://mp.weixin.qq.com/s?__biz=MzUzNDUyOTY0Nw==&mid=2247484011&idx=1&sn=1ffdb758a552db1934f41b1c4496bb36&chksm=fa92116bbbdbdbd9bdbdbdbdbdbdbdbddd = 126 & sessionid = 1592125292 & key = 2e8f81eda3e54fad9074a8b209275cc64f9c5dd28066961b7be2f518b92c55507968ed1b6278d887e87fd9f464f4b4899c8cf651adda04616c16f3c11e97de5ebdc827c9144e99e8b08451af86234894 & ascene = 1 & uin = MTk1NDc4MzM2Mg%3D%3D & devicetype = Windows + 10 + x64 & version = 62090070 & lang = zh_CN & exportkey = AWHTYrB4gjJmGEbHtri6R6w%3D & pass_ticket = leo%2BHfJ0BW2bC82%2BQSYAPob7M1DzxC09JpT%2BAvOxTmnKdJp6Basn7bAq9v%2Fv3xN%2B) of Redis <font color = # 159957>Install and Commonly used data The structure has been sorted out, if you have not read it, you can go back and read it before continuing this article~

The last article is an explanation of some redis basic data type APIs. This article is the underlying implementation of data types. The main contents are:

  • Why use Redis
  • Redis data structure analysis
  • SDS simple dynamic string
  • Hash table
  • Jump table
  • Integer collection
  • Compressed list
  • Data structure objects in Redis
  • ...
  1. Talk about Redis again

What is Redis? In mandarin, it is:

Redis is an open source(BSD licensed), in-memory data structure store, used as a database, cache and message broker.

Redis is an open source, memory-based data structure storage, which can be used asdatabase,cacheandmessage middleware**.

If you want to try the Redis command and are too lazy to install, you can use this http://try.redis.io/ website.

  1. Why use Redis

Previous articleWe have a certain understanding

Redis is based on memory, which is often used as a cache technology, and the Redis storage method is key-value Form.

Why don't we use Java Map?

  • Java Map is local cache, the main features are light weight and fast, the life cycle ends with the destruction of jvm, and in the case of multiple instances Each instance needs to save a cache, and the cache does not have consistency.
  • The JVM memory is too large to be easily hung up, and there are various expiry mechanism, storage structureyou need to manually write it
  • Redis will periodically save the cache to the hard disk, restart to restore the data, rich data structure, cache mechanism and other practical functions.
  1. Why use cache?

High concurrency, high availability This is a word often mentioned on the Internet. Performance problems will appear when there are a large number of requests in the program. The first point of general performance problems is The database can't bear it anymore, the database read and write will have disk operations, and the disk speed is much slower than the memory.

So we add a cache in the middle:

image-20200616152518589

  1. Redis data structure

4.1. SDS simple dynamic string

4.1.1. SDS simple dynamic string

Redis is written in C language.

We now know that all Redis keys are strings, and the values are the bottom of the five types of keys:string, hash, list, set, and sorted set Implement the data structure.

Redis does not directly use the traditional C language string representation(character arrays that end with null characters, hereinafter referred to as C strings), but instead builds an abstraction called simple dynamic string(SDS) Type, and use SDS as Redis' default string representation.

Redis uses the sds.h/sdshdr structure to represent an SDS value:

struct sdshdr {

    //record the number of used bytes in the buf array
    //equal to the length of the string saved by SDS
    int len;

    //record the number of unused bytes in the buf array
    int free;

    //Byte array, used to save the string
    char buf[];

};

SDS picture

The image above is an example of SDS, ending with a null character '\0'. The advantage of following the convention of ending with a null character is that SDS can directly reuse a part of the functions in the C string function library.

For example, if we have a pointer s to the SDS shown in Figure 2-1, then we can directly use the stdio.h/printf function by executing the following statement:

printf("%s", s->buf);

To print out the string value "Redis" saved by SDS without writing a special printing function for SDS.

4.1.2. Benefits of SDS simple dynamic strings

  1. The len attribute records the length of the string in the sdshdr data structure. Then when getting the length of the string, time complexity only needs O(1). Constant complexity gets the string length.
  2. SDS will not overflow, if the SDS is modified, there is not enough space. The space will be expanded first and then modified!(Dynamic expansion mechanism is implemented inside). Prevent buffer overflow.
  3. SDS can reduce the number of memory allocations(space pre-allocation mechanism). When expanding the space, in addition to the space necessary for modification, additional free space(free attribute) is also allocated. Reduce the number of memory reallocations required to modify the length of the string.
  4. SDS is Binary Security. SDS processes the data stored in the buf array in a binary manner.
  5. You can use some functions in the <string.h> library. Compatible with some C string functions.

4.2. Redis linked list and linked list nodes

Java learners should be familiar with linked lists, which is a typical and commonly used data structure in Java.

Each linked list node uses an adlist.h/listNode structure to represent:

typedef struct listNode {

    //leading node
    struct listNode *prev;

    //Post node
    struct listNode *next;

    //The value of the node
    void *value;

} listNode;

Using listNode can form a linked list. In Redis, use list structure to hold a linked list:

typedef struct list {

    //Header node
    listNode *head;

    //Trailing node
    listNode *tail;

    //The number of nodes contained in the linked list
    unsigned long len;

    //Node value copy function
    void *(*dup)(void *ptr);

    //Node value release function
    void(*free)(void *ptr);

    //Node value comparison function
    int(*match)(void *ptr, void *key);

} list;

A linked list consisting of one list structure and three listNode structures:

image-20200615212853670

4.2.2. Redis list focus

  • Linked lists are widely used to implement various Redis functions, such as list key, publish and subscribe, slow query, monitor, etc.
  • Each linked list node is represented by a listNode structure, each node has a pointer to previous node and post node, so Redis's linked list implementation is double-ended linked list.
  • Each linked list is represented by a list structure with information such as header node pointer, tailer node pointer, and linked list length.
  • Because the leading node of the head node of the linked list and the trailing node of the tail node of the list both point to NULL, Redis's linked list implementation is an acyclic linked list.
  • By setting different types of specific functions for linked lists, Redis linked lists can be used to store various types of values.

4.3. Redis dictionary

4.3.1. Hash table

The dictionary is a concept in Redis. Redis' dictionary uses a hash table as the underlying implementation. There can be multiple hash table nodes in a hash table, and each hash table node stores a key-value pair in the dictionary.

Empty hash table
The hash table used by the Redis dictionary is defined by the dict.h/dictht structure:

typedef struct dictht {

    //Hash table array
    dictEntry **table;

    //Hash table size
    unsigned long size;

    //Hash table size mask, used to calculate the index value
    //always equal size-1
    unsigned long sizemask;

    //The number of nodes in the hash table
    unsigned long used;

} dictht;

image-20200615214714203

Hash Table Node
Hash table nodes are represented by dictEntry structures, and each dictEntry structure holds a key-value pair:

typedef struct dictEntry {

    //key
    void *key;

    //value
    union {
        void *val;
        uint64_t u64; //uint64_t integer
        int64_t s64; //int64_t integer
    } v;

    //point to the next hash table node to form a linked list
    struct dictEntry *next;

} dictEntry;

image-20200615215620644

Have you noticed that there is a conflict in the above picture, the two keys are on the same node, this is Redis Resolving key conflicts, Redis hash table uses separate chaining to resolve key conflicts:each Each hash table node has a next pointer. Multiple hash table nodes can use the next pointer to form a singly linked list. Multiple nodes that are assigned to the same index can be connected using this singly linked list. The problem of key conflicts.

Dictionary
The dictionary in Redis is represented by the dict.h/dict structure:

typedef struct dict {

    //Type-specific functions
    dictType *type;

    //Private data
    void *privdata;

    //hash table
    dictht ht[2];

    //rehash index
    //When rehash is not in progress, the value is -1
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */

} dict;

------------------Dividing line---------------------------

typedef struct dictType {

    //Function to calculate hash value
    unsigned int(*hashFunction)(const void *key);

    //Copy key function
    void *(*keyDup)(void *privdata, const void *key);

    //Function to copy value
    void *(*valDup)(void *privdata, const void *obj);

    //Function of contrast key
    int(*keyCompare)(void *privdata, const void *key1, const void *key2);

    //The function to destroy the key
    void(*keyDestructor)(void *privdata, void *key);

    //Function to destroy value
    void(*valDestructor)(void *privdata, void *obj);

} dictType;

The ht attribute is an array containing two items. Each item in the array is a dictht hash table. In general, the dictionary only uses ht[0] hash tables , Ht[1] hash table will only be used when rehash the ht[0] hash table.

image-20200615220230621

4.3.2. Redis rehash(rehash)

As the operation continues, the key-value pairs stored in the hash table will gradually increase or decrease, in order to maintain the load factor(load factor) of the hash table Within a reasonable range, when the number of key-value pairs stored in the hash table is too large or too small, the program needs to expand or shrink the size of the hash table accordingly.

When expanding or contracting the hash table, the reash process is not completed at once, but is done gradually.

The following are the detailed steps of the hash table progressive rehash:

Allocate space for ht[1]and let the dictionary hold two hash tables, ht[0]and ht[1].
Maintain an index counter variable rehashidx in the dictionary, and set its value to 0, indicating that the rehash work officially started.
During rehash, every time you add, delete, search, or update a dictionary, the program will, in addition to performing the specified operation, also pass all the key-value pairs of the ht[0]hash table on the rehashidx index to ht[1], when the rehash work is completed, the program increases the value of the rehashidx attribute by one.
With the continuous execution of dictionary operations, eventually at a certain point in time, all key-value pairs of ht[0]will be rehash to ht[1]. At this time, the program sets the value of the rehashidx attribute to -1, indicating the rehash operation completed.

4.3.3. Focus

  • Dictionaries are widely used to implement various Redis functions, including databases and hash keys.
  • The dictionary in Redis uses a hash table as the underlying implementation. Each dictionary has two hash tables, one for normal use and the other only for rehash.
  • When the dictionary is used as the underlying implementation of the database, or the underlying implementation of the hash key, Redis uses the MurmurHash2 algorithm to calculate the hash value of the key.
  • The hash table uses the chain address method to resolve key conflicts. Multiple key-value pairs assigned to the same index will be connected into a one-way linked list.
  • When expanding or contracting the hash table, the program needs to rehash all the key-value pairs contained in the existing hash table into the new hash table, and this rehash process is not completed at once. It is done gradually.

4.4. Jump table

4.4.1. Jump table

Redis's jump table is defined by two structures redis.h/zskiplistNode and redis.h/zskiplist, where the zskiplistNode structure is used to represent the jump table node, and the zskiplist structure is used to save the jump table node Relevant information, such as the number of nodes, and pointers to header node and trailer node, etc.

Jump table node

typedef struct zskiplistNode {

    //Back pointer
    struct zskiplistNode *backward;

    //score
    double score;

    //member object
    robj *obj;

    //Floor
    struct zskiplistLevel {

        //forward pointer
        struct zskiplistNode *forward;

        //span
        unsigned int span;

    } level[];

} zskiplistNode;
  • zskiplistNode nodes at different levels

image-20200616104418058

The level array of the skip table node can contain multiple elements, and each element contains a pointer to other nodes. Programs can use these layers to speed up access to other nodes. Generally speaking, The more the number of layers, the faster the access to other nodes**.

image-20200616104629451

See here, if you still have doubts and don t understand what is a jump table, send a good introduction to the jump table:[ https://www.cnblogs.com/hunte...] ( https://www . cnblogs.com/hunternet/p/11248192.html)

4.4.2. Focus

  1. The skip table is one of the underlying implementations of ordered collections, except that it has no other application in Redis.
  2. Redis's skip table implementation consists of two structures, zskiplist and zskiplistNode, where zskiplist is used to save jump table information(such as table head node, table tail node, length), and zskiplistNode is used to represent jump table node.
  3. The layer height of each jump table node is 1 to 32**random number** .
  4. In the same jump table, multiple nodes can contain same score, but each node's member object Must be unique.
  5. The nodes in the skip table are sorted according to the score size. When the scores are the same, the nodes are sorted according to the size of the member object.

4.5. Set of integers

  • Integer set is one of the underlying implementations of set key(set)**.
  • The underlying implementation of the set of integers is array, this array is saved in ordered and non-repetitive Collection elements, when necessary, the program will change the type of this array according to newly added element type, .
  • The upgrade operation brings operational flexibility to the set of integers and saves memory as much as possible.
  • Integer collectionOnly supports upgrade operation, does not support downgrade operation.

An integer set(intset) is a collection abstract data structure used by Redis to store integer values. It can save integer values of type int16_t, int32_t, or int64_t, and guarantee that no Duplicate elements.

data structure:

typedef struct intset {

    //Encoding
    uint32_t encoding;

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

    //Array of saved elements
    int8_t contents[];

} intset;

image-20200616111727776

4.6. Compressed list

4.6.1. Preface

As with integer sets, compressed lists are not basic data structures, but a data storage structure designed by Redis itself. It is a bit like an array, with a continuous memory space to store data. However, it differs from arrays in that it allows different sizes of stored data.

We know that the array requires that each element has the same size, if you want to store strings of different lengths, you need to use the string size of maximum length as the element size . Taking the maximum length as the standard, a part of the storage space will be wasted.

The advantage of the array takes up a piece of continuous spacecan make good use of CPU cache to access data. If we want to retain this advantage and want to save storage space, we can compress the array.

Then you need to add a lenght attribute to each node.

4.6.2. Redis compressed list

_Zipped list(zip1ist) is one of the underlying implementations of Redis lists and Redis hashes. _

  • When a list contains only a small number of list items, and each list item is either a small integer value or a string with a relatively short length, Redis will use a compressed list as the underlying implementation of the list.
  • When a hash contains only a few key-value pairs, and the keys and values of each key-value pair are either small integer values or short-length strings, Redis will use a compressed list for hashing The underlying implementation.

image-20200616142749605

Reference: https://www.cnblogs.com/hunte...

  1. The table is a sequential data structure designed by Redis to save memory.
  2. Tables are used as one of the underlying implementations of list keys and hash keys.
  3. The compressed list can contain multiple nodes, and each node can hold a byte array or integer value.
  4. Add new nodes to the compressed list, or delete nodes from the compressed list, may cause a chain update operation, but the probability of such operations is not high.

4.7. Redis objects

4.7.1. Redis objects

When we create a key-value pair in Redis, we will create at least two objects, one for the key(key object) and one for the value(value object).

  • Redis object structure

    typedef struct redisObject {

      //Types of
      unsigned type:4;
    
      //encoding
      unsigned encoding:4;
    
      //Pointer to the underlying data structure
      void *ptr;
    
      //...

    } robj;

  • Redis memory recycling

It is worth mentioning that redis memory recycling, because C language does not have automatic memory recycling function, so Redis built a reference count in its own object system(Reference counting) memory recycling mechanism, through this mechanism, the program can track the reference count information of the object, automatically release the object at the appropriate time and perform Memory recycling. The reference count information of each object is recorded by the refcount attribute of the redisObject structure:

typedef struct redisObject {

    //...

    //Reference counting
    int refcount;

    //...

} robj;
  • Redis object sharing

For example, suppose key A creates a string object containing the integer value 100 as the value object. If key B also creates a string object that also holds the integer value 100 as the value object.

In Redis, letting multiple keys share the same value object requires the following two steps:

  1. Point the value pointer of the database key to an existing value object;
  2. Increment the reference count of the shared value object by one.

Currently, Redis will create 10,000 string objects when initializing the server. These objects contain all integer values from 0 to 9999. When the server needs to use a string object with a value of 0 to 9999, the server These shared objects will be used instead of newly created objects.

  • Idle time of Redis object

In addition to the four attributes type, encoding, ptr, and refcount introduced earlier, the last attribute included in the redisObject structure is lru attribute, which records the last time the object was accessed by the command program:

typedef struct redisObject {

    //...

    unsigned lru:22;

    //...

} robj;

4.7.2. Focus

Memory reclamation and idling time of objects involve Redis configuration files(memory algorithm volatile-lru, allkeys-lru and other knowledge points), a separate article will explain in detail later.

  • The key and value of each key-value pair in the Redis database is an object.
  • Redis has wordscharacter string, list, hash, set, ordered set five types of objects, each type of object has at least two or more Encoding method, different encodings can optimize the use efficiency of objects in different usage scenarios.
  • Before executing certain commands, the server will first check whether the given key type can execute the specified command, and checking the type of a key is to check the type of the key's value object.
  • Redis's object system has a reference counting implementation of memory recycling mechanism, when an object is no longer used, the memory occupied by the object will be automatically released .
  • Redis will share string objects with values from 0 to 9999.
  • Subject will record the time of his last visit, this time can be used to calculate the object's idle time.