The world martial arts, invincible, only fast not broken!

Learning a technology usually involves only scattered technical points, without establishing a complete knowledge framework and architecture system in my mind and without a systematic view. This will be very demanding, and there will be a look as if they will, then forget, a face mengbi.

Follow “code elder brother byte” to thoroughly understand Redis and deeply master the core principles and actual combat skills of Redis. Build a complete knowledge framework together, learn to sort out the whole knowledge system.

In fact, the system view is very important. To some extent, when solving problems, having a system view means that you can locate and solve problems in a systematic way.

Redis panorama

The panorama can be expanded around two latitudes, which are:

Application dimensions: cache usage, clustering usage, clever use of data structures

System dimension: can be classified as three high

  1. High performance: thread model, network IO model, data structure, persistence mechanism;
  2. High availability: master/slave replication, sentinel Cluster, Cluster sharding Cluster;
  3. High scalability: load balancing

The Redis series begins with the following mind map, this time exploring the core knowledge of Redis from the Only Unbreakable Secrets.

The only secret that can’t be broken

I was asked “Why is Redis fast?” when I had an interview with 996 big factories some time ago.

65: Well, because it is based on memory implementation and single thread model

Interviewer: Anything else?

Brother 65: No.

Many people are only aware of memory-based implementations, and the reasons for other cores are ambiguous. Today follow “code elder brother byte” together to explore the real fast reason, do a only fast not broken true man!

For high performance, Redis has been optimized from all aspects, and the next time you are interviewed, the interviewer will ask why Redis performance is so high, but can not just say the silly single thread and memory storage.

According to official data, The QPS of Redis can reach about 100,000 (requests per second). If you are interested, you can refer to the official benchmark “How Fast is Redis?” IO /topics/benc…

The horizontal axis is the number of connections, and the vertical axis is QPS. At this point, this chart reflects an order of magnitude, I hope you can describe it correctly in the interview, do not ask you when you answered the order of magnitude is far away!

Fully implemented in memory

65 brother: I know this, Redis is based on memory database, compared with disk database, completely lift disk speed, just like Duan Yu’s lingbo micro step. For disk databases, data is first read into memory via IO operations.

Yes, both read and write operations are done in memory, so let’s compare memory operations with disk operations.

Disk call stack diagram

Memory operations

The memory is directly controlled by the CPU, that is, the memory controller integrated within the CPU. Therefore, the memory is directly connected to the CPU and enjoys the optimal bandwidth for communication with the CPU.

Redis stores data in memory, read and write operations are not due to disk I/O speed limit, so speed fly general feeling!

Finally, the various delay times of the system are quantified in a graph (some data are quoted by Brendan Gregg)

Efficient data structures

Brother 65: When LEARNING MySQL, I know that B+ Tree data structure is used to improve the retrieval speed, so the fast speed of Redis should also be related to the data structure.

Correct answer, the data structure is not the five data types Redis provides for us to use: String, List, Hash, Set, SortedSet.

In Redis, the five data types and application scenarios are as follows:

  • String: cache, counter, distributed lock, etc.
  • List: linked List, queue, timeline List of followers on Weibo, etc.
  • Hash: user information, Hash table, etc.
  • Set: to delike, like, stomp on, share friends, etc.
  • Zset: ranking list of page views and clicks, etc.

The above should be called the data types supported by Redis, which is how data is stored. “Code brother byte” refers to the efficient data structures used to support these five data types.

Brother 65: Why so many data structures?

Of course, for the sake of speed, different data types use different data structures to speed up. Each data type is supported by one or more data structures, with six underlying data structures.

Redis hash dictionary

Redis as a whole is a hash table that holds all key-value pairs, regardless of the data type. A hash table is essentially an array. Each element is called a hash bucket, and each entry in the bucket holds a pointer to the actual value, regardless of the data type.

The entire database is a global hash table, and the time complexity of hash table is O(1). You only need to calculate the hash value of each key to know the corresponding hash bucket position, and locate the entry in the bucket to find the corresponding data, which is also one of the reasons why Redis is fast.

What about Hash conflicts?

As more and more data is written to Redis, hash conflicts are inevitable, with different keys calculating the same hash value.

Redis resolves conflicts with chained hashing: elements in the same bucket are stored in a linked list. However, when the linked list is too long, the search performance may deteriorate, so Redis uses two global hash tables in pursuit of speed. Used for rehash operations to increase the number of existing hash buckets and reduce hash conflicts.

Hash table 1 is initially used by default to hold key-value pair data. Hash table 2 has no space allocated at this time. When more data triggers a rehash operation, the following operations are performed:

  1. Allocate more space to hash table 2;
  2. Copy the data from Hash table 1 to Hash table 2.
  3. Free the space of hash table 1.

It is important to note that the remapping of hash table 1 data to Hash table 2 is not a one-time process, and this will cause Redis to block and fail to serve.

Instead, a progressive rehash is used, starting with the first index in hash table 1 and copying all data at that position into Hash table 2 to spread the rehash over multiple requests to avoid time-consuming blocking.

SDS simple dynamic characters

Redis is implemented in C language, why do you make a new SDS dynamic string?

String structure is the most widely used, usually used to cache user information after login, key = userId, value = user information JSON serialized into a string.

C language string to obtain the length of “MageByte”, to be iterated from the beginning, until “\0”, Redis as the only fast man is intolerable.

The comparison of C language string structure and SDS string structure is as follows:

SDS is different from C strings

O(1) Time complexity This parameter specifies the length of the string

The time complexity of traversing the entire string is O(n). The traversing of the C string ends when ‘\0’ is encountered.

Len in SDS holds the length of this string, O(1) time complexity.

Space preallocation

When SDS is modified, the program allocates not only the required space for SDS, but also additional unused space.

The allocation rules are as follows: If len is less than 1M long after SDS modification, the program will allocate the same length of unused space as LEN. For example, if len=10, after reallocation, the actual length of buF becomes 10(used space)+10(extra space)+1(null characters)=21. If len is greater than 1M after modification to SDS, the program allocates 1M of unused space.

Inert space release

When shortening SDS, the program will not reclaim the excess memory space, but use the free field to record the number of bytes and do not release them. If the append operation is needed later, the unused space in free will be directly used to reduce the memory allocation.

Binary security

In Redis, you can store not only String data, but also some binary data.

Binary data is not a regular string format and contains special characters such as ‘\0’, which in C indicates the end of the string, but in SDS, the end of the string is marked by the Len attribute.

ZipList compressed list

Compressed lists are one of the underlying implementations of the List, Hash, and sorted Set data types.

When a list has only a small amount of data, and each list item is either a small integer value or a short string, Redis uses compressed lists for the underlying implementation of list keys.

Ziplist is a sequential data structure composed of a series of contiguous memory blocks with special encoding. A Ziplist can contain multiple entry nodes, and each node can store integers or strings.

Ziplist has three fields zlBytes, zltail, and zllen in the header of the table, which respectively represent the number of bytes occupied by the list, the offset at the end of the list, and the number of entries in the list. The compressed list also has a Zlend at the end of the table, indicating the end of the list.

struct ziplist<T> {
    int32 zlbytes; // The number of bytes for the entire compressed list
    int32 zltail_offset; // The offset of the last element from the start of the compressed list, used to quickly locate the last node
    int16 zllength; // Number of elements
    T[] entries; // A list of element contents, stored compactly one by one
    int8 zlend; // Marks the end of the compressed list with a constant value of 0xFF
}
Copy the code

If we want to locate the first and last elements, we can locate them directly by the length of the first three fields of the table, which is O(1). When you look for other elements, it’s not as efficient, you have to look one by one, and that’s order N.

Double side list

The Redis List data type is commonly used in scenarios such as queues, timeline lists of twitter followers, etc. Both the fifO queue and the fifO stack support these features well.

The features of Redis’s linked list implementation can be summarized as follows:

  • Double-ended: Linked list nodes have prev and next Pointers, and the complexity of obtaining the pre-node and post-node of a node is O (1).
  • Acyclic: The prev pointer on the head node and the next pointer on the tail node point to NULL, and access to the linked list ends at NULL.
  • With head and tail Pointers: Through the head and tail Pointers of the list structure, the complexity of the program to obtain the head and tail nodes of the linked list is O (1).
  • List length counter: The program uses the len attribute of the list structure to count the list nodes held by the list. The complexity of obtaining the number of nodes in the list is O (1).
  • Polymorphic: Linked list nodes use void* Pointers to hold node values, and you can set type-specific functions for node values through the DUP, free, and match attributes of the list structure, so linked lists can be used to hold various types of values.

Later versions revamped the list data structure, using QuickList instead of Ziplist and LinkedList.

Quicklist is a hybrid of Ziplist and LinkedList, which splits the linkedList into segments, each of which is stored compactly using ziplist, and multiple Ziplists are connected together using bidirectional Pointers.

That’s why Redis is fast, not missing any details that can improve performance.

SkipList jump table

The sorted set type is sorted using a “skip list” data structure.

A skiplist is an ordered data structure that enables fast access to nodes by maintaining multiple Pointers to other nodes in each node.

Skip lists support node lookup with average O (logN) and worst O (N) complexity, and batch processing of nodes through sequential operations.

On the basis of linked list, hop table adds multi-level index to realize fast location of data through several jumps of index position, as shown in the figure below:

It takes three lookups to find the element 40.

Integer array (intSet)

Redis uses the collection of integers as the underlying implementation of the collection key when a collection contains only integer numeric elements and the number of elements in the collection is small. The structure is as follows:

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

Contents array is a low-level implementation of the contents array: each element of the contents array is an item of the contents array, and each item is arranged in order of value from smallest to largest in the array, and the array contains no duplicates. The Length property records the number of elements in the integer collection, which is the length of the contents array.

Reasonable data encoding

Redis uses redisObject to represent the key value in the database. When we create a key-value pair in Redis, we create at least two objects, one for the key object and the other for the value object of the key-value pair.

For example, when we execute SET MSG XXX, the key of the key-value pair is an object containing the string “MSG”, and the value object of the key-value pair is an object containing the string “XXX”.

redisObject

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

The type field records the type of the object, including string object, list object, hash object, collection object, ordered collection object.

For each data type, the underlying support may be multiple data structures, and when to use which data structure is a matter of coding transformation.

Let’s take a look at how different data types are encoded:

String: Int encoding is used for numbers, or raw encoding is used for non-numbers.

List: The encoding of the List object can be Ziplist or LinkedList, the string length < 64 bytes and the number of elements < 512 use ziplist encoding, otherwise converted to linkedList encoding;

Note: These two conditions can be modified in redis.conf:

list-max-ziplist-entries 512
list-max-ziplist-value 64
Copy the code

Hash: The Hash object can be ziplist or Hashtable.

Ziplist encoding is used when the Hash object meets both of the following conditions:

  • The key and value strings of all key-value pairs saved by the Hash object are smaller than 64 bytes.
  • The Hash object stores less than 512 key-value pairs.

Otherwise, hashTable encoding.

Set: The encoding of a Set can be an intset or a hashtable. The intset encoding uses a Set of integers as its underlying implementation, storing all elements in a Set of integers.

Save elements as integers and the number of elements is less than a certain range, use intset encoding. If any condition is not met, use Hashtable encoding.

Zset: The encoding of a Zset object can be ziplist or Zkiplist. When stored in ziplist, each collection element is stored using two compressed lists next to each other.

The first node of the Ziplist compressed list stores the members of the element, and the second node stores the score value of the element in an ordered order from smallest to largest.

When the Zset object meets the following two conditions at the same time, ziplist encoding is used:

  • Zset holds less than 128 elements.
  • Zset elements are all less than 64 bytes long.

If any of the above conditions are not met, ziplist is converted to Zkiplist encoding. Note: These two conditions can be modified in redis.conf:

zset-max-ziplist-entries 128
zset-max-ziplist-value 64
Copy the code

Single threaded model

Why is Redis single-threaded instead of multi-threaded to make full use of the CPU?

Let’s be clear: Redis single threading refers to the Redis network IO and key/value reads and writes are performed by a single thread. Redis persistence, cluster data synchronization, asynchronous deletion, etc. are all performed by other threads.

As for why single threads are used, let’s first look at the disadvantages of multithreading.

Disadvantages of multithreading

Using multiple threads usually increases system throughput and makes full use of CPU resources.

However, after the use of multi-threading, without a good system design, there may be a scenario as shown in the following figure, increasing the number of threads, the early throughput will increase, and then further new threads, the system throughput will almost no longer increase, or even decline!

Before running each task, the CPU needs to know where the task loads and starts running. That is, the system needs help to pre-set CPU registers and program counters, which is called the CPU context.

These saved contexts are stored in the system kernel and reloaded when tasks are rescheduled. This way, the original state of the task will not be affected, and the task will appear to be running continuously.

When we switch contexts, we need to do a lot of work, which is a very resource-intensive operation.

In addition, when multithreading parallel modify shared data, in order to ensure the correct data, the need for locking mechanism will bring additional performance overhead, faced with concurrent access control of shared resources.

With the introduction of multithreading, it is necessary to use synchronization primitives to protect concurrent reads and writes of shared resources, which increases the code complexity and debugging difficulty.

What are the benefits of a single thread?

  1. No performance cost due to thread creation;
  2. Avoid the CPU consumption caused by context switch, no overhead of multithreading switch;
  3. Avoid contention issues between threads, such as adding locks, releasing locks, deadlocks, etc., and do not need to consider various locks.
  4. The code is clearer and the processing logic is simple.

Is a single thread underusing CPU resources?

Official answer: Because Redis is a memory-based operation, CPU is not the bottleneck of Redis. The bottleneck of Redis is most likely the size of machine memory or network bandwidth. Since single-threading is easy to implement and the CPU is not a bottleneck, it makes sense to adopt a single-threaded solution. Redis. IO /topics/ FAQ

I/O multiplexing model

Redis uses I/O multiplexing to process connections concurrently. A simple event framework implemented by epoll + itself is used. Read, write, close, connect in ePoll are converted into events, and then take advantage of ePoll’s multiplexing features without wasting any time on IO.

Brother 65: What is I/O multiplexing?

Before explaining I/O multiplexing let’s look at what happens to basic I/O operations.

Basic IO model

A basic network IO model, when processing a GET request, goes through the following process:

  1. Setup with the clientaccept;
  2. Read the request from the socketrecv;
  3. Parse requests sent by clientsparse;
  4. performgetInstruction;
  5. Responding to client data, that is, writing data back to the socket.

Bind/LISTEN, Accept, RECv, parse, and Send belong to network I/O processing, while GET belongs to key-value data operation. Since Redis is single-threaded, the most basic implementation is to perform these operations in sequence in a single thread.

The key point is that Accept and RECV block. When Redis listens for a connection request from a client, but fails to establish a connection, the accept() function blocks, causing other clients to fail to establish a connection with Redis.

Similarly, when Redis reads data from a client via recv(), Redis blocks at recv() if the data never arrives.

The reason for the block is that traditional blocking I/O is used, that is, network operations such as read, Accept, and RECV are blocked and wait. As shown below:

IO multiplexing

Multiplexing refers to multiple socket connections, and multiplexing refers to the reuse of a thread. There are three main techniques for multiplexing: SELECT, Poll, and epoll. Epoll is the latest and best multiplexing technology available.

The basic principle is that the kernel does not monitor the connection of the application itself, but rather the file descriptor of the application.

When the client runs, it generates sockets with different event types. On the server side, the I/O multiplexer (I/O multiplexer module) queues messages (the SOCKET queue for the I/O multiplexer shown below) and forwards them to different event handlers through a file event dispatcher.

To put it simply: in the single-threaded Redis case, the kernel listens for connection requests or data requests on the socket and hands them over to the Redis thread whenever they arrive. This implements the effect of one Redis thread processing multiple I/O streams.

Select /epoll provides an event-based callback mechanism that calls the corresponding event handler for different events. So Redis is constantly handling events to improve Redis response performance.

The Redis thread does not block on a particular listener or connected socket, that is, on a particular client request processing. Because of this, Redis can connect to multiple clients at the same time and process requests, increasing concurrency.

Summary of the principle that only fast can not break

65 elder brother: after study I finally know Redis why fast essence reason, “code elder brother” you don’t talk, I come to sum up! I will like and share this post later to let more people know the core principles of Redis Express.

  1. Pure memory operations are generally simple access operations. Threads take up a lot of time, and the time is mainly spent on IO, so the reading speed is fast.
  2. The entire Redis is a global hash table, and its time complexity is O(1). In order to prevent hash conflicts from making the linked list too long, Redis will perform rehash operations to expand the number of hash buckets and reduce hash conflicts. In addition, progressive rehash is used to prevent thread blocking due to large remapping data at one time. Cleverly spread one-off copies over multiple requests to avoid blocking.
  3. Redis uses non-blocking IO: IO multiplexing, using a single thread to poll descriptors, database on, off, read, write are converted into events, Redis uses its own implementation of the event separator, relatively high efficiency.
  4. Adopting single thread model ensures atomicity of each operation and reduces context switching and contention of threads.
  5. Redis uses hash structure in the whole process to speed up data reading, and some special data structures are optimized for data storage, such as compressed table for compressed storage of short data, and, for example, hop table, which uses ordered data structure to speed up data reading.
  6. Select different encoding based on the data type stored

In the next Redis Blog post, follow me for some real hardcore knowledge.

In addition, the technical reader group has also been opened, and the background replies to “Add group” to obtain the wechat of the author of “code elder brother byte”, so that we can grow and communicate together.

That’s the secret of Redis. If you think it’s good, please like it and share it.