In-depth analysis of why Redis is so fast?

We all know that Redis is very fast, and its QPS can reach 100,000 (requests per second). Why is Redis so fast?, this article will learn with everyone. [Related recommendations: Redis video tutorial]

Memory-based implementation

We all know that memory reading and writing is faster than disk reading and writing A lot of. Redis is a database implemented based on memory storage. Compared with databases where data is stored on disk, disk I/O consumption is eliminated. Disk databases such as MySQL need to create indexes to speed up query efficiency, while Redis data is stored in memory and operates directly on the memory, so it is very fast.

Efficient data structure

We know that in order to improve efficiency, MySQL index chooses the B-tree data structure. In fact, a reasonable data structure can make your application/program faster. Let’s first look at the data structure & internal encoding diagram of Redis:

SDS simple dynamic string

##

struct sdshdr { //SDS简单动态字符串
    int len;    //记录buf中已使用的空间
    int free;   // buf中空闲空间长度
    char buf[]; //存储的实际内容
}

String Length processing

In C language, to get the length of the string

Little boy picking up snails, you need to traverse it from the beginning, and the complexity is O(n); In Redis, there is already a len field that records the length of the current string. You can get it directly, and the time complexity is O(1).

Reduce the number of memory reallocations

In C language, modifying a string requires reallocation of memory. The more frequent the modification, the more frequent the memory allocation, and allocating memory will

Consumption performance. In Redis, SDS provides two optimization strategies: space pre-allocation and lazy space release.

Space pre-allocation

When SDS simple dynamic string modification and space expansion, in addition to allocating necessary memory space, additional unused space will be allocated. The allocation rules are purple:

After the SDS is modified, the length of len is less than 1M, then additional unused space of the same length as len will be allocated. For example, len=100, after reallocation, the actual length of buf will become 100 (used space) 100 (extra space) 1 (null character) = 201.
• After the SDS is modified, if the len length is greater than 1M, the program will allocate 1M of unused space.

Lazy space release

When SDS is shortened, instead of reclaiming excess memory space, free is used to record the excess space. If there are subsequent modification operations, the space in free will be used directly to reduce memory allocation.

Hash

Redis is a K-V in-memory database, which uses a global hash to save all key-value pairs. This hash table is composed of multiple hash buckets. The entry element in the hash bucket stores the

*key and *value pointers, among which *key points to the actual key, *value points to the actual value.

The hash table lookup speed is very fast, somewhat similar to

HashMap in Java, which allows us to perform O(1) The time complexity of quickly finding key-value pairs. First, calculate the hash value through the key, find the corresponding hash bucket location, then locate the entry, and find the corresponding data in the entry.

Some friends may have questions: When you write a large amount of data into the hash table, won't you encounter the

Hash conflict problem, and then the efficiency will decrease.

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

In order to resolve hash conflicts, Redis uses

chain hashing. Chained hashing means that multiple elements in the same hash bucket are stored in a linked list, and they are connected in turn using pointers.

#Some friends may still have questions: The elements on the hash conflict chain can only be searched one by one through pointers and then operated. When a lot of data is inserted into the hash table, the more conflicts there will be, the longer the conflict linked list will be, and the query efficiency will be reduced.

In order to maintain efficiency, Redis will perform

rehash operations on the hash table, which means adding hash buckets and reducing conflicts. In order to make rehash more efficient, Redis also uses two global hash tables by default, one for current use, called the main hash table, and one for expansion, called the backup hash table.

跳跃表

跳跃表是Redis特有的数据结构，它其实就是在链表的基础上，增加多级索引，以提高查找效率。跳跃表的简单原理图如下:

• 每一层都有一条有序的链表，最底层的链表包含了所有的元素。
• 跳跃表支持平均 O（logN）,最坏 O（N）复杂度的节点查找，还可以通过顺序性操作批量处理节点。

压缩列表ziplist

压缩列表ziplist是列表键和字典键的的底层实现之一。它是由一系列特殊编码的内存块构成的列表， 一个ziplist可以包含多个entry， 每个entry可以保存一个长度受限的字符数组或者整数，如下：

• zlbytes ：记录整个压缩列表占用的内存字节数
• zltail: 尾节点至起始节点的偏移量
• zllen : 记录整个压缩列表包含的节点数量
• entryX: 压缩列表包含的各个节点
• zlend : 特殊值0xFF(十进制255)，用于标记压缩列表末端

由于内存是连续分配的，所以遍历速度很快。。

合理的数据编码

Redis支持多种数据基本类型，每种基本类型对应不同的数据结构，每种数据结构对应不一样的编码。为了提高性能，Redis设计者总结出，数据结构最适合的编码搭配。

Redis是使用对象（redisObject）来表示数据库中的键值，当我们在 Redis 中创建一个键值对时，至少创建两个对象，一个对象是用做键值对的键对象，另一个是键值对的值对象。

//关注公众号：捡田螺的小男孩
typedef struct redisObject{
    //类型
   unsigned type:4;
   //编码
   unsigned encoding:4;
   //指向底层数据结构的指针
   void *ptr;
    //...
 }robj;

redisObject中，type 对应的是对象类型，包含String对象、List对象、Hash对象、Set对象、zset对象。encoding 对应的是编码。

• String：如果存储数字的话，是用int类型的编码;如果存储非数字，小于等于39字节的字符串，是embstr；大于39个字节，则是raw编码。
• List：如果列表的元素个数小于512个，列表每个元素的值都小于64字节（默认），使用ziplist编码，否则使用linkedlist编码
• Hash：哈希类型元素个数小于512个，所有值小于64字节的话，使用ziplist编码,否则使用hashtable编码。
• Set：如果集合中的元素都是整数且元素个数小于512个，使用intset编码，否则使用hashtable编码。
• Zset：当有序集合的元素个数小于128个，每个元素的值小于64字节时，使用ziplist编码，否则使用skiplist（跳跃表）编码

合理的线程模型

单线程模型：避免了上下文切换

Redis是单线程的，其实是指Redis的网络IO和键值对读写是由一个线程来完成的。但Redis的其他功能，比如持久化、异步删除、集群数据同步等等，实际是由额外的线程执行的。

Redis的单线程模型，避免了CPU不必要的上下文切换和竞争锁的消耗。也正因为是单线程，如果某个命令执行过长（如hgetall命令），会造成阻塞。Redis是面向快速执行场景的内存数据库，所以要慎用如lrange和smembers、hgetall等命令。

什么是上下文切换？举个粟子：

• 比如你在看一本英文小说，你看到某一页，发现有个单词不会读，你加了个书签，然后去查字典。查完字典后，你回来从书签那里继续开始读，这个流程就很舒畅。
• 如果你一个人读这本书，肯定没啥问题。但是如果你去查字典的时候，别的小伙伴翻了一下你的书，然后溜了。你再回来看的时候，发现书不是你看的那一页了，你得花时间找到你的那一页。
• 一本书，你一个人怎么看怎么打标签都没事，但是人多了翻来翻去，这本书各种标记就很乱了。可能这个解释很粗糙，但是道理应该是一样的。

I/O 多路复用

什么是I/O多路复用？

• I/O: Network I/O
• Multi-channel: Multiple network connections
• Multiplexing: Multiplexing the same thread.
• IO multiplexing is actually a synchronous IO model, which implements a thread that can monitor multiple file handles; once a file handle is ready, it can notify the application to perform corresponding read and write operations; When no file handle is ready, the application will be blocked and the CPU will be handed over.

Multiple I/O multiplexing technology allows a single thread to efficiently handle multiple connection requests, and Redis uses epoll as I/O Implementation of multiplexing technology. Moreover, Redis's own event processing model converts connections, reads, writes, and closings in epoll into events, without wasting too much time on network I/O.

Virtual Memory Mechanism

Redis directly builds the VM mechanism by itself. It will not call system functions like ordinary systems and 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, thereby freeing up valuable memory space for other data that needs to be accessed (hot data). data). The VM function can realize the separation of hot and cold data, so that the hot data is still in the memory and the cold data is saved to the disk. This can avoid the problem of slow access speed caused by insufficient memory.

For more programming related knowledge, please visit: Programming Video! !

The above is the detailed content of In-depth analysis of why Redis is so fast?. For more information, please follow other related articles on the PHP Chinese website!