02. Redis Blockbuster: viewing core principles from high-frequency problems

It is declared that this document is reproduced in the code byte , Reprint the document only for learning 、 Review for no other purpose

「 Code byte 」 From the high-frequency interview questions to sweep with you Redis Core knowledge points , Fundamental understanding Redis , Don't be a tool of eight part essay , To be the God of changing the world .

Brother Ma has written so far 9 piece Redis Serial , Backstage a small partner also asked me to write some articles about the interview , therefore “ Face bully ” The series came out .

If you read it carefully 《Redis series 》 And understand , It's no business hanging an interviewer .

1. Redis Core ： The secret that can't be broken quickly

2. Redis Journal ：AOF and RDB Fast recovery from downtime , Data is not lost

3. Redis High availability ： Data consistency synchronization principle of master-slave architecture

4. Redis Actual combat ：6.x edition Sentinel Sentry group set up

5. Redis High availability ：Sentinel The principle of sentry group

6. Redis Actual combat ：6.x edition Cluster Cluster building

7. Redis High availability ：Cluster Can clusters expand indefinitely ？ What is the principle ？

8. Redis Actual combat ： Skillfully use Bitmap Achieve billion level massive data statistics

9. Redis Actual combat ： Skillfully using data structure to realize billion level data statistics

Redis Why so soon? ？

A lot of people just know it's K/V NoSQl In-memory database , Single thread …… There is no comprehensive understanding Redis So we can't go on asking .

The problem is to find out the foundation , We can Redis The implementation of the underlying data structure of different data types 、 Completely based on memory 、IO Multiplexing network model 、 Threading model 、 Progressive type rehash…...

Just how fast ？

We can talk about how fast it is first , According to official figures ,Redis Of QPS It can reach about 100000（ Requests per second ）, If you are interested, please refer to the official benchmark program test 《How fast is Redis？》, Address ：https://redis.io/topics/benchmarks

The benchmark

Horizontal axis is the number of connections , The vertical axis is QPS.

*

This picture reflects an order of magnitude , Let the interviewer feel that you have read the official documents through quantification , Very rigorous .

Based on memory implementation

Redis It's a memory based database , Compared to disk databases , The speed at which the disk is fully hit .

Read and write operations are performed in memory , We compare the differences between memory operation and disk operation .

Disk call

Memory operations

Memory is directly controlled by CPU control , That is to say CPU Internal integrated memory controller , So memory is directly related to CPU docking , Enjoy and CPU The optimal bandwidth of communication .

Finally, a graph is used to quantify the delay time of the system （ Some data references Brendan Gregg）

Efficient data structure

Study MySQL I know that in order to improve the retrieval speed, I used B+ Tree data structure , therefore Redis Speed should also be related to data structure .

Redis Altogether 5 Type of data ,String、List、Hash、Set、SortedSet.

Different data types are supported by one or more data structures , The purpose is to pursue faster speed .

*

From brother ma ： We can explain the advantages of the underlying data structure of each data type separately , A lot of people just know the data type , And saying the underlying data structure can make people shine .

SDS Simple dynamic string advantages

C Language strings and SDS

1. SDS in len Save the length of the string ,O(1) Time complexity query string length information .

2. Space preallocation ：SDS After being modified , Not only will the program be SDS Allocate the necessary space , Additional unused space will also be allocated .

3. Inert space release ： When the SDS During the shortening operation , Programs don't reclaim extra memory space , But use free Field records the number of bytes and does not release , If you need to append operation , Direct use free Unused space in , Reduced memory allocation .

zipList Compressed list

The compressed list is List 、hash、 sorted Set One of the underlying implementations of three data types .

When a list has only a small amount of data , And each list item is either a small integer value , Or it's a shorter string , that Redis Will use compressed list to do the bottom implementation of list key .

ziplist

So the memory is compact , To save memory .

quicklist

The following versions have reformed the list data structure , Use quicklist Instead of ziplist and linkedlist.

quicklist yes ziplist and linkedlist Mixture , It will linkedlist Segmentation by segment , Use of each section ziplist To compact storage , Multiple ziplist Connected in series with two-way pointer .

skipList Skip list

sorted set The sorting function of the type is through 「 Skip list 」 Data structure to achieve .

Skip list （skiplist） Is an ordered data structure , It maintains multiple pointers to other nodes in each node , So as to achieve the purpose of fast access to nodes .

Jump list is based on linked list , Added multi tier index , Through a few jumps in the index position , Realize the rapid positioning of data , As shown in the figure below ：

Skip list

An array of integers （intset）

When a set contains only integer value elements , And when the number of elements in this collection is small ,Redis We will use the integer set as the underlying implementation of the set key , Save memory .

Single thread model

*

From brother ma ： What we need to pay attention to ,Redis Single thread refers to  Redis Network of IO （6.x Post version network IO Using multithreading ） And the key value pair instruction reading and writing is executed by a thread .  about Redis The persistence of 、 Cluster data synchronization 、 Asynchronous deletion is executed by other threads .

Never say Redis There is only one thread .

Single thread means Redis The execution of key value to read and write instruction is single thread .

Let's start with the official answer , It feels rigorous enough , Instead of following others' example to recite some blogs .

Official answer ： because Redis Is a memory based operation ,CPU No Redis Bottleneck ,Redis The bottleneck is the most It could be the size of the machine memory or the network bandwidth . Since a single thread is easy to implement , and CPU Not a bottleneck , So it's natural to adopt a single thread solution . Original address ：https://redis.io/topics/faq.

*

Why not use multithreading to make the most of CPU Well ？

Before running each task ,CPU You need to know where the task loads and starts running . in other words , The system needs to help it preset CPU Registers and program counters , This is called CPU Context .

When switching context , We need to do a lot of work , This is a very resource intensive operation .

Introduce multithreading development , We need to use synchronization primitives to protect the concurrent reading and writing of shared resources , Increase code complexity and debugging difficulty .

*

What are the benefits of single threading ？

1. No performance consumption due to thread creation ;

2. Avoid context switching CPU Consume , There is no overhead of multithreading ;

3. Avoid the competition between threads , Like adding locks 、 Release the lock 、 Deadlock, etc , There's no need to think about locks .

4. The code is clearer , The processing logic is simple .

I/O Multiplexing model

Redis use I/O Multiplexing technology , Concurrent processing connection . Adopted epoll + Simple event framework implemented by ourselves .

epoll Reading in Chinese 、 Write 、 close 、 Connections are converted to events , And then use it epoll Multiplexing characteristics of , Never in IO Waste a little time .

High performance IO Multiplexing

Redis Threads do not block on a particular listening or connected socket , in other words , It doesn't block the processing of a specific client request . Because of this ,Redis You can connect to multiple clients and process requests at the same time , To improve concurrency .

Redis overall situation hash Dictionaries

Redis The whole is one Hash table to hold all key value pairs , Whether the data type is 5 Any one of these . Hashtable , It's essentially an array , Each element is called a hash bucket , Whatever the data type , In every bucket entry A pointer that holds the actual value .

Redis Global hash table

And the time complexity of hash table is O(1), Just calculate the hash value of each key , You will know the corresponding location of the hash bucket , Locate the inside of the barrel entry Find the corresponding data , This is also Redis One of the reasons for being fast .

Redis Use object （redisObject） To represent key values in the database , When we're in Redis When creating a key value pair in , Create at least two objects , An object is a key object used as a key value pair , The other is the value object of the key value pair .

That is, every one of them entry preserved 「 Key value pair 」 Of redisObject object , adopt redisObject To find the corresponding data .

typedef struct redisObject{
    // type 
   unsigned type:4;
   // code 
   unsigned encoding:4;
   // Pointer to the underlying data structure 
   void *ptr;
    //...
 }robj;

Hash What about the conflict ？

Redis adopt Chained hash Resolve conflicts ： The same The elements in the bucket are stored in a linked list . But when the linked list is too long, it will lead to poor search performance , therefore Redis In pursuit of fast , Two global hash tables are used . be used for rehash operation , Increase the number of existing hash buckets , Reduce hash conflicts .

Start using... By default 「hash surface 1 」 Save key value pair data ,「hash surface 2」 There's no space allocated at the moment . As more and more data triggers rehash operation , Then do the following ：

1. to 「hash surface 2 」 Allocate more space ;

2. take 「hash surface 1 」 Data remapping copy to 「hash surface 2」 in ;

3. Release 「hash surface 1」 Space .

It is worth noting that , take hash surface 1 The data is remapped to hash surface 2 It's not a one-off process , This will cause Redis Blocking , Unable to provide services .

Instead, it adopted Progressive type rehash, Every time a client request is processed , First from 「 hash surface 1」 Start with the first index in , Put the position of Copy all data to 「hash surface 2」 in , That's how it will rehash Spread over multiple requests , Avoid time-consuming congestion .

Redis How to achieve persistence ？ How to recover data after downtime ？

Redis Data persistence using 「RDB Data snapshot 」 To achieve rapid recovery from downtime . however Taking full data snapshots too often , There are two serious performance overhead ：

1. Frequent generation RDB File write to disk , Disk pressure is too high . There will be a last RDB Not finished , The next one is coming up again , Fall into a dead cycle .

2. fork Out bgsave The child process blocks the main thread , The more memory the main thread has , The longer the blocking time .

therefore Redis And designed AOF Write log records instructions that modify memory .

*

interviewer ： What is? RDB memory dump ？

stay Redis perform 「 Write 」 In the process of instruction , Memory data changes all the time . So called memory snapshot , Refers to Redis The state data of the data in memory at a certain moment .

It's like time is fixed at a certain moment , When we take pictures , A moment can be completely recorded by taking pictures .

Redis It's similar to this , That is to take a moment's data as a file , Write to disk . This snapshot file is called  RDB file ,RDB Namely Redis DataBase Abbreviation .

RDB memory dump

When doing data recovery , Direct will RDB The file is read into memory to complete the recovery .

*

interviewer ： It's generating RDB period ,Redis Can write requests be processed at the same time ？

Tolerable ,Redis Multi process using the operating system Copy on write technology COW(Copy On Write)  To achieve snapshot persistence , Ensure data consistency .

Redis Will be called on persistence glibc Function of fork Generate a subprocess , Snapshot persistence is completely left to the child process to handle , The parent process continues to process client requests .

When the main thread executes the write instruction to modify the data , This data will be copied , bgsave  The child process reads the copy data and writes it to RDB file .

This ensures the integrity of the snapshot , It also allows the main thread to modify the data at the same time , Avoid the impact on normal business .

Copy on write technology ensures that data can be modified during snapshot

*

interviewer ： that AOF What is it again? ？

AOF The log records from Redis All modified instruction sequences since instance creation , Then you can pass on an empty Redis The instance executes all instructions in sequence , That is to say 「 replay 」, To restore Redis The status of the memory data structure of the current instance .

Redis Provided AOF Configuration item appendfsync The write back strategy directly determines AOF The efficiency and security of persistence capabilities .

• always： Synchronous write back , When the write instruction is finished, it will be  aof_buf The contents of the buffer are flushed to AOF file .

• everysec： Write back every second , The write instruction is finished , The log will only write AOF File buffer , Synchronize buffer contents to disk every second .

• no：  Operating system control , Write execution completed , Write the log to AOF File memory buffer , It's up to the operating system to decide when to write to disk .

There is no best of both strategies , We need to make a trade-off between performance and reliability .

*

interviewer ： since RDB There are two performance issues , Then why not AOF that will do .

AOF Write a Prelog , It's a record of each 「 Write 」 Command operation . Don't like RDB Full snapshot leads to performance loss , But the execution speed didn't RDB fast , At the same time, too large log file can also cause performance problems .

therefore ,Redis Designed a killer 「AOF Rewrite mechanism 」,Redis Provides  bgrewriteaof Instructions are used for AOF Keep your weight down .

Its principle is to open up a subprocess to traverse memory and convert it into a series of Redis Operation instructions of , Serialize to a new AOF Log file . Increment occurred during operation after serialization AOF The log is appended to this new AOF Log file , Replace the old one immediately after the addition AOF The log file is missing , The job of slimming is done .

AOF Rewrite mechanism (3 One to one )

*

interviewer ： How to minimize data loss and balance performance ？

restart Redis when , We seldom use rdb To restore memory state , Because a lot of data will be lost . We usually use AOF Log replay , But replay AOF Log performance is relative rdb It's a lot slower , In this way Redis When the examples are large , It takes a long time to start .

Redis 4.0 To solve this problem , Brings a new persistence option —— Mix persistence . take rdb The content of the file and the incremental AOF Log files exist together . there AOF Logs are no longer full logs , It is The increment from the beginning of persistence to the end of persistence AOF journal , Usually this part AOF The log is very small .

therefore stay Redis When restarting , You can load rdb The content of , Then replay the increment AOF Log can completely replace the previous AOF Full file replay , The restart efficiency has been greatly improved .

Redis Master slave architecture data synchronization

Redis Provides a master-slave model , Copy... By master-slave , Copy one redundant copy of data to another Redis The server .

*

interviewer ： How to ensure data consistency between master and slave ？

To ensure the consistency of the replica data , The master-slave architecture adopts the way of reading and writing separation .

• Read operations ： Lord 、 It can be executed from the library ;

• Write operations ： The main library executes first , Then synchronize the write operation to the slave Library ;

Redis Read / write separation

*

interviewer ： Does master-slave copy have any other functions ？

1. Fault recovery ： When the primary node goes down , Other nodes can still provide services ;

2. Load balancing ：Master Nodes provide write services ,Slave Nodes provide read services , Share the pressure ;

3. High availability cornerstone ： It's the sentry and cluster The basis of implementation , It's the cornerstone of high availability .

*

interviewer ： How master-slave replication works ？

There are three types of synchronization ：

1. The first master-slave full copy ;

2. Synchronization between master and slave during normal operation ;

3. The network between master and slave is disconnected, reconnected and synchronized .

*

interviewer ： How to achieve the first synchronization ？

The first replication process of master-slave libraries can be roughly divided into 3 Stages ： Connection establishment phase （ Preparation stage ）、 The master database synchronizes data to the slave database stage 、 Send a new write command during synchronization to the slave library phase ;

Redis Full amount of synchronization

1. Establishing a connection ： The slave library will establish a connection with the master library , Execute... From the library replicaof And send the psync Command and tell the main library that synchronization is about to take place , After the main database confirms the reply , The master and slave libraries are synchronized .

2. The master database synchronizes the data to the slave database ：master perform  bgsave Command to generate RDB file , And send the file to the slave Library , meanwhile Main library For every one slave Open up a piece of replication buffer Buffer records are generated from RDB All write commands received at the beginning of the file . Save from library RDB Empty the database and load it again RDB Data into memory .

3. send out RDB After receiving the new write command to the slave Library ： It's generating RDB The write operation after the file is not recorded to the just RDB In file , In order to ensure the consistency of master-slave database data , So the main library will use one in memory called replication buffer Record RDB All write operations after file generation . And send the data to slave.

*

interviewer ： What if the network between the master and slave databases is broken ？ Do you want to copy all the data again after disconnection ？

stay Redis 2.8 Before , If the master-slave database has a network flash when the command propagates , that , The slave database will make a full copy with the master database again , It's very expensive .

from Redis 2.8 Start , After the Internet was disconnected , The master-slave database will continue to synchronize by incremental replication .

Incremental replication ： Used for replication after network interruption , Only write commands executed by the master node during the interrupt are sent to the slave node , More efficient than full replication .

The implementation secret of disconnected reconnection incremental replication is  repl_backlog_buffer  buffer , No matter when master Write instructions will be recorded in  repl_backlog_buffer  in , Because memory is limited , repl_backlog_buffer  It's a fixed length ring array , If the array is full , It will cover the previous content from the beginning .

master Use  master_repl_offset Record the position offset you wrote ,slave Then use  slave_repl_offset Record the offset that has been read .

repl_backlog_buffer

When the master and slave are disconnected and reconnected ,slave Will send psync Order to master, At the same time, I will put my own  runID,slave_repl_offset Send to master.

master Only need to  master_repl_offset And  slave_repl_offset You can synchronize the commands between them to the slave library .

The execution flow of incremental replication is as follows ：

Redis Incremental replication

*

interviewer ： So after full synchronization , How to synchronize data during normal operation ？

When the master and slave libraries are fully replicated , They will always maintain a network connection between them , Through this connection, the master database will synchronize the subsequent command operations received successively to the slave database , This process is also known as command propagation based on long connections , The purpose of using long connections is to avoid the overhead caused by frequent connection establishment .

The sentinel principle is a series of questions

*

interviewer ： All right , I know so much , You know, The sentry group principle ？

The sentry is Redis A mode of operation of , It focuses on Yes Redis example （ Master node 、 From the node ） Monitoring the operation status of , When the master node fails, a series of mechanisms can be used to select the master and switch between the master and the slave , Achieve failover , Make sure that the whole Redis Availability of the system .

His architecture is as follows ：

Redis The sentry cluster

Redis Sentinels have the following capabilities ：

• monitor ： Continuous monitoring master 、slave Whether it is in the expected working state .

• Switch the main library automatically ： When Master Operational failure , Sentinels start the auto recovery process ： from slave Choose one of them as the new master.

• notice ： Give Way slave perform replicaof , With the new master Sync ; And inform the client with the new master Establishing a connection .

*

interviewer ： How do sentinels know each other ？

The sentry and master Establish communication , utilize master Provide release / The subscription mechanism publishes its own information , Like height and weight 、 Are you single? 、IP、 port ……

master There is one  __sentinel__:hello  A dedicated channel for , Used to publish and subscribe messages between sentinels . It's like  __sentinel__:hello  Wechat group , Sentinels use master Set up a wechat group to release their own news , At the same time, follow the news from other sentinels .

*

interviewer ： The Sentinels are connected , But we need to talk to slave Establishing a connection , Otherwise, we can't monitor them , How do you know slave And monitor their ？

The key is to use master To achieve , The sentry turned to master send out  INFO  command , master The leader naturally knows what he has salve My little brother's . therefore master After receiving the command , It will be slave The list tells the sentry .

The sentry is based on master Responsive slave List information with every salve Establishing a connection , And continuously monitor the sentry based on this connection .

INFO Command acquisition slave Information

Cluster Cluster cannon

*

interviewer ： Except for the Sentinels , Is there any other high availability means ？

Yes Cluster Cluster for high availability , The Sentinels are monitoring Redis Clusters are master-slave architectures , Unable to expand horizontally . Use Redis Cluster colony , It mainly solves various slow problems caused by large amount of data storage , At the same time, it is also convenient for horizontal expansion .

In front of millions 、 With tens of millions of users , Laterally extended Redis Slicing clusters would be a great choice .

*

interviewer ： What is? Cluster colony ？

Redis Cluster is a distributed database solution , Clustering is done by fragmentation （sharding） For data management （「 Divide and conquer thoughts 」 A practice of ）, It also provides replication and failover capabilities .

Divide the data into 16384 Of slots, Each node is responsible for some slots . Slot information is stored in each node .

It's decentralized , As shown in the figure , The cluster consists of three Redis Node composition , Each node is responsible for a part of the data of the whole cluster , How much data each node is responsible for may be different .

Redis Cluster architecture

Three nodes are connected to form a peer-to-peer cluster , They pass through  Gossip Protocols interact with each other in cluster information , Finally, each node holds the other nodes slots Distribution .

*

interviewer ： How does the hash slot map to Redis For instance ？

1. According to the key value of key, Use CRC16 Algorithm , Work out a 16 bit Value ;

2. take 16 bit The value of is right 16384 Perform mold extraction , obtain 0 ～ 16383 The number of represents key The corresponding hashico .

3. Locate the corresponding instance according to the slot information .

Key value pair data 、 Hash slot 、Redis The mapping between instances is as follows ：

data 、Slot Mapping to instances

*

interviewer ：Cluster How to achieve failover ？

Redis The cluster node adopts  Gossip  Protocol to broadcast their own state and their own cognitive changes of the whole cluster . For example, a node finds that a node is disconnected (PFail), It will broadcast this message to the entire cluster , Other nodes can also receive this information .

If a node receives the number of lost connections from a node (PFail Count) Has reached the majority of the cluster , You can mark this node to determine the offline status (Fail), Then broadcast... To the entire cluster , Force other nodes to receive the fact that the node is offline , And immediately switch between the master and the slave of the lost node .

*

interviewer ： How can the client determine which instance the accessed data is distributed on ？

Redis The instance will pass its hash slot information through Gossip The protocol is sent to other instances in the cluster , Realize the diffusion of hash slot allocation information .

such , Each instance in the cluster has all the mapping information between hash slots and instances .

When the client connects to any instance , The instance responds the mapping relationship between the hash slot and the instance to the client , The client will cache the hash slot and instance mapping information locally .

When requested by the client , The accountant worked out the hash slot corresponding to the key , Then, the hash slot instance mapping information in the local cache is used to locate the instance where the data is located , Then send the request to the corresponding instance .

Redis The client locates the node where the data is located

*

interviewer ： What is? Redis Redirection mechanism ？

The mapping relationship between hash slot and instance is changed due to new instance or load balancing redistribution , The client sends the request to the instance , There is no corresponding data for this instance , The Redis The instance tells the client to send the request to another instance .

Redis adopt MOVED Mistakes and ASK The error tells the client .

MOVED

MOVED  error （ Load balancing , The data has been migrated to other instances ）： When the client sends a key value pair operation request to an instance , When the slot where the key is located is not in charge of itself , The instance returns a MOVED Error directing to the node in charge of the slot .

meanwhile , The client also updates the local cache , Will be slot And Redis The instance correspondence is updated correctly .

MOVED Instructions

ASK

If a slot There's a lot of data , Partial migration to new instance , There's still a part that hasn't moved .

If requested key If it is found in the current node, execute the command directly , Otherwise, we need to ASK Wrong response .

When the migration of the slot is not completed , If you need access to key Where Slot From example 1 Migrate to example 2（ If key No longer in the instance 1）, example 1 It will return a message to the client ASK Error message ： Requested by the client key The hash slot is being migrated to the instance 2 On , You give me an example first 2 Send a ASKING command , Then send the operation command .

For example, the client requests to locate key = 「 official account : Code byte 」 The groove of 16330 In the instance 172.17.18.1 On , node 1 If you can find it, just execute the command , Otherwise respond ASK error message , And guide the client to the target node being migrated 172.17.18.2.

ASK error

Be careful ：ASK The error instruction does not update the hash slot allocation information in the client cache .