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

Editor to share with you why Redis is so fast, I believe most people still do not understand, so share this article for your reference, I hope you can learn a lot after reading this article, let's go to understand it!

We all know that Redis is very fast, and its QPS can reach 100000 (requests per second). Then why is Redis so fast?

Memory-based implementation

We all know that reading and writing to memory is much faster than reading and writing to disk. Redis is a database based on memory storage. Compared with the database where the data is stored on disk, it saves the consumption of disk Imando O. Disk databases such as MySQL need to establish indexes to speed up query efficiency, while Redis data are stored in memory and operate directly in memory, so it is very fast.

Efficient data structure

We know that in order to improve efficiency, MySQL index chooses the data structure of B+ tree. In fact, a reasonable data structure can make your application / program faster. First, take a look at the data structure of Redis & the internal coding diagram:

SDS simple dynamic string

Struct sdshdr {/ / SDS simple dynamic string int len; / / record the length of free space in int free; / / buf used in buf char buf []; / / actual content stored} string length processing

In the C language, to get the length of the string of the little boy picking up the snail, you need to traverse from scratch with a complexity of O (n). In Redis, there is already a len field to record the length of the current string, which can be obtained directly, with a time complexity of O (1).

Reduce the number of memory reallocations

In C language, modifying a string requires memory reallocation. The more frequent the modification, the more frequent the memory allocation, and allocating memory consumes performance. In Redis, SDS provides two optimization strategies: space pre-allocation and inert space release.

Space pre-allocation

When SDS makes simple dynamic string modification and space expansion, it allocates additional unused space in addition to the necessary memory space. The allocation rules are purple:

After the SDS is modified, the length of the len is less than 1m, then additional unused space of the same length as the len will be allocated. For example, len=100, after reallocation, the actual length of buf becomes 100 (used space) + 100 (extra space) + 1 (null character) = 201.

After the SDS modification, the len length is greater than 1m, then the program will allocate 1m of unused space.

Release of inert space

When the SDS is shortened, instead of reclaiming the excess memory space, you use free to record the excess space. Subsequent modification operations will directly use the space in free to reduce memory allocation.

Hash

Redis, as an in-memory database of Kmuri V, uses a global hash to hold all the key-value pairs. This hash table consists of multiple hash buckets. The entry element in the hash bucket holds * key and * value pointers, where * key points to the actual key and * value points to the actual value.

Hash table lookup rate is very fast, somewhat similar to HashMap in Java, it allows us to quickly find key-value pairs in O (1) time complexity. First, calculate the hash value through key, find the corresponding hash bucket location, then locate to entry, and find the corresponding data in entry.

Some friends may have doubts: when you write a large amount of data to the hash table, you will encounter the problem of hash conflict, and the efficiency will come down.

Hash conflict: through different key, the same hash value is calculated, resulting in falling in the same hash bucket.

In order to solve the hash conflict, Redis uses chain hash. Chained hash means that in the same hash bucket, multiple elements are stored in a linked list, and they are connected by pointers in turn.

Some friends may also have doubts: the elements on the hash conflict chain can only be looked up and manipulated one by one through the pointer. When more data is inserted into the hash table, the more conflicts and the longer the conflict linked list, the less efficient the query.

To remain efficient, Redis does rehash operations on the hash table, that is, increasing hash buckets and reducing collisions. To make rehash more efficient, Redis also uses two global hash tables by default, one for current use, called the primary hash table, and one for expansion, called the standby hash table.

Jump table

Jump table is a unique data structure of Redis. In fact, it adds multi-level index on the basis of linked list to improve search efficiency. The simple schematic diagram of the jump table is as follows:

Each layer has an ordered linked list, and the lowest linked list contains all the elements.

The jump table supports node lookup with average O (logN) and worst O (N) complexity, and can also batch process nodes through sequential operations.

Compressed list ziplist

Compressed list ziplist is one of the underlying implementations of list and dictionary keys. It is a list of specially encoded memory blocks. A ziplist can contain multiple entry, and each entry can hold an array of characters or integers of limited length, as follows:

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

Zltail: offset from tail node to start node

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

EntryX: compress each node contained in the list

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

Because the memory is allocated continuously, it traverses very quickly.

Reasonable data coding

Redis supports a variety of basic data types, each of which corresponds to a different data structure and each data structure corresponds to a different encoding. In order to improve performance, Redis designers concluded that the data structure is the most suitable coding match.

Redis uses redisObject to represent the key value in the database. When we create a key value pair in Redis, at least two objects are created. One object is the key object used as the key value pair, and the other is the value object of the key value pair.

/ / follow the official account: typedef struct redisObject {/ / Type unsigned type:4; / / Encoding unsigned encoding:4; / / pointer to the underlying data structure void * ptr; / /.} robj

In redisObject, type corresponds to the object type, including String object, List object, Hash object, Set object, and zset object. Encoding corresponds to coding.

String: if you store numbers, you use int type encoding; if you store non-numeric strings that are less than or equal to 39 bytes, if the embstr; is greater than 39 bytes, it is raw encoding.

List: if the number of elements in the list is less than 512, the value of each element in the list is less than 64 bytes (default), use ziplist encoding, otherwise use linkedlist encoding

Hash: if the number of hash type elements is less than 512, use ziplist encoding if all values are less than 64 bytes, otherwise use hashtable encoding.

Set: if all the elements in the collection are integers and the number of elements is less than 512, use intset encoding, otherwise use hashtable encoding.

Zset: use ziplist encoding when the number of elements in an ordered set is less than 128and the value of each element is less than 64 bytes, otherwise use skiplist (Jump Table) encoding

Reasonable threading model single threading model: avoiding context switching

Redis is single-threaded, which actually means that Redis's network IO and key-value pairs are read and written by a single thread. But other functions of Redis, such as persistence, asynchronous deletion, cluster data synchronization, and so on, are actually performed by additional threads.

The single-threaded model of Redis avoids the unnecessary context switching and competitive lock consumption of CPU. Also because it is single-threaded, if a command executes too long (such as the hgetall command), it will cause blocking. Redis is an in-memory database for fast execution scenarios, so be careful with commands such as lrange and smembers, hgetall, and so on.

What is context switching? Give an example of millet:

For example, if you are reading an English novel, you see a page and find that there is a word you can't read. You add a bookmark and look it up in the dictionary. After looking it up in the dictionary, you come back and start reading from the bookmark, and the process is very smooth.

If you read this book alone, there must be no problem. But if you look it up in the dictionary, the other friends go through your book and run away. When you come back to read it, you find that the book is not the page you read, and you have to take the time to find your page.

For a book, it doesn't matter how you look at it and how you label it, but when there are too many people turning over and over, the book's marks are very messy. This explanation may be rough, but the reason should be the same.

Ipaw O Multiplexing

What is Icano multiplexing?

ICompo: network Ihamo

Multiplex: multiple network connections

Reuse: reuse the same thread.

IO multiplexing is actually a synchronous IO model that implements that a thread can monitor multiple file handles; once a file handle is ready, it can notify the application to read and write accordingly; and when no file handle is ready, it blocks the application and hands over the cpu.

The multiplexing technology of multi-channel epoll O enables a single thread to process multiple connection requests efficiently, while epoll is used as the implementation of the multiplexing technology. And the event handling model of Redis itself converts the connection, read and write, and shutdown in epoll into events, and does not waste too much time on the network IWeiO.

Virtual memory mechanism

Redis directly built its own VM mechanism, unlike the general system will call system functions to deal with, will waste a certain amount of time to move and request.

What is the virtual memory mechanism of Redis?

The virtual memory mechanism is to temporarily swap infrequently accessed data (cold data) from memory to disk, thus freeing up valuable memory space for other data that needs to be accessed (hot data). The hot and cold data can be separated by the VM function, so that the hot data is still in memory and the cold data is saved to disk. In this way, the problem of slow access speed caused by insufficient memory can be avoided.

The above is all the contents of the article "Why Redis is so fast". Thank you for reading! I believe we all have a certain understanding, hope to share the content to help you, if you want to learn more knowledge, welcome to follow the industry information channel!

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.