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

This article mainly introduces "what is the Redis data structure and memory management method". In the daily operation, I believe that many people have doubts about the Redis data structure and memory management methods. The editor consulted all kinds of materials and sorted out simple and easy-to-use operation methods. I hope it will be helpful for you to answer the doubts about "what are Redis data structures and memory management methods?" Next, please follow the editor to study!

one。 Network model

Redis is a typical Reactor-based event-driven model, single-process single-threaded, efficient framework is always similar. The network model is almost the same as spp's asynchronous model.

The Redis process is divided into three synchronization modules: the receiving request processor, the response processor and the response processor. Each request has to go through these three parts.

Redis integrates a variety of event management mechanisms, such as libevent/epoll/kqueue/select, and can freely choose the appropriate management mechanism according to the version of the operating system, among which libevent is the best one.

Redis's network model has the advantages of all event-driven models, high efficiency and low consumption. However, in the face of a long operation, the request cannot be processed, and the request can only be responded to after the event has been processed. We have encountered such a scenario in the business before, when all the key-value in the redis is deleted, the whole operation time is long, and all requests cannot be responded during the operation. Therefore, a clear understanding of the network model helps to enhance the strengths and avoid weaknesses in the business, reduce long and time-consuming requests, and make the most of the asynchronous model with as many simple and short time-consuming requests as possible. in fact, this has been reflected many times in the design of Redis.

two。 Data structure and memory management 1. String 1.1 structure

The string of Redis is the secondary encapsulation of the original string of C language, and its structure is as follows:

Struct sdshdr {long len; long free; char buf [];}

As you can see, whenever you define a string, Redis allocates additional space for managing property fields in addition to the space for saving characters.

1.2 memory management mode

The biggest advantage of dynamic memory management is that it can make full use of memory space and reduce memory fragmentation, while the disadvantage is that it is easy to cause frequent memory jitter. Two optimization strategies of "space pre-allocation" and "inert space release" are usually used to reduce memory jitter, and redis is no exception.

Every time you modify the content of a string, first check whether the memory space meets the requirements, otherwise it will be doubled or increased by M; when you reduce the content of the string, the memory will not be reclaimed immediately, but on demand.

With regard to the optimization of memory management, the most basic starting point is the tradeoff between wasting a little space or sacrificing some time. The core idea adopted by arena mechanisms such as STL, tcmalloc and protobuf3 is "pre-allocation and late recovery", and so is Redis.

1.3 binary security

The flag that determines whether a string ends or not is the len field, not the C language'\ 0', so it is binary safe.

Rest assured that the binary string serialized by pb is stored in redis.

In short, through the simple encapsulation of redis, the operation of redis string is more convenient, the performance is more friendly, and shields some problems of C language string that users need to care about.

two。 Dictionary (hash)

The bottom layer of the dictionary must be hash. When it comes to hash, it will involve hash algorithm, conflict resolution and hash table expansion and reduction.

2.1 hash algorithm

Redis uses the commonly used Murmurhash3,Murmurhash algorithm which can give the hash distribution under any input sequence, and the calculation speed is very fast. The previous requirement of Local-Cache with shared memory makes use of the advantages of Murmurhash to solve the problem of poor hash distribution of hash functions in the original structure.

2.2 hash conflict resolution

Chain address method to solve hash conflicts, the general solution is nothing special. By the way, if you choose to use chain addresses to resolve conflicts, there must be a very good hashing hash function, otherwise the performance of hash will be greatly reduced. Redis chose Murmurhash, so you can rest assured that you can boldly adopt the chain address scheme.

2.3 hash capacity expansion and reduction

Keep the hash table within a reasonable load range, referred to as the rehash process.

The process of rehash is also a process of tradeoff. Before making an evaluation, it is clear that no matter what rehash strategy is used in the middle, rehash must be: allocate a new memory block, move the old data to the new memory block, and release the old memory block.

When will the old data be moved? How do I move it? It becomes a question to be weighed.

The first part of the network model clearly points out the characteristics of Redis's event-driven model, which is not suitable for long and time-consuming operations. If a hashtable is very large and needs to be expanded to copy the old data at one time, it will be very time-consuming and violate the event-driven characteristics. So Redis still adopts a lazy scheme:

After the new space is allocated, starting the rehashidx identifier indicates the beginning of the rehash process; then all operations involved in adding, deleting, modifying and querying will migrate the data to the new space until the old spatial data size of 0 indicates that the data is already in the new space, and disable rehashidx to indicate the end of rehash.

Divide and conquer the one-time centralized problem, which is reflected incisively and vividly in Redis's design philosophy, mainly in order to avoid time-consuming operations and affect Redis response to customer requests.

3. Integer set

Variable length integer storage, integers are divided into three variable length scales in 16-32-64, and planning is carried out according to the type of data stored.

Each insertion of a new element may result in a scale upgrade (for example, from 16 bits to 32 bits), so the time complexity of inserting integers is O (n). This is also a tradeoff between memory space and time to save memory as much as possible.

4. Jump table

The skilplist of Redis is no different from the ordinary skiplist. It is a multi-level linked list with redundant data from coarse to fine. There are not many places where jump tables are used in Redis, and ordered collections are common.

There is nothing special about Redis's jump watch and ordinary skiplist.

5. Linked list

The linked list of Redis is a bi-directional acyclic linked list with header and footer pointers. The operation time complexity for the head and tail is O (1), the search time complexity is O (n), and the insertion time complexity is O (1).

There is nothing special about Redis's linked list and normal linked list.

III. AOF and RDB persistence

AOF persistence log, RDB persistence entity data, AOF priority is higher than RDB.

1.AOF persistence

Mechanism: the data in the aof buffer is periodically written to disk through timing events.

2.AOF rewriting

To reduce AOF size, Redis provides AOF rewriting, which does the job of creating a new AOF file to replace the old AOF, and the new AOF file does not have a redundant instruction. (for example, insert A/B/C first for list, then delete Bhand C, and then insert D with a total of 6 instructions. The final state is ABG D, and only one instruction is needed)

The principle of implementation is to read the state of the existing database and deduce instructions according to the status, regardless of the previous AOF. Similarly, in order to avoid long time-consuming, the rewriting is carried out in the child process.

3.RDB persistence

Both SAVE and BGSAVE commands are used to generate RDB files. The difference is that BGSAVE will fork a child process to do it alone, which does not affect Redis processing normal requests.

The persistence operation is carried out after timing and a certain number of times.

In short, the process of RDB is actually relatively simple, after meeting the conditions directly to write the RDB file is over.

four。 Multi-machine and cluster 1. Master-slave server

Avoiding a single point is a common problem for all services, and Redis is no exception. To solve the single point, it is necessary to have a standby machine, and to have a standby machine is to solve the inherent problem of data synchronization.

1.1 sync-- original master-slave synchronization

The initial synchronization practice of Redis is the sync instruction, which uses sync to produce a full amount of data every time, so it is obvious that the design of full replication every time is more resource-consuming. The idea of improvement is also conventional logic, the first full amount, the remaining increments, which is now the work of psync instructions.

1.2 psync

The technical means of partial resynchronization is "offset sequence number + backlog buffer", as follows:

(1) Master and slave maintain a seq respectively. Each time the master completes a request, the master seq+1 and updates his own seq after each synchronization.

(2) each time you plan to synchronize, you always bring your own seq to the master. The master compares his seq with the slave error result with the size of the backlog buffer. If it is less than the backlog buffer size, take the corresponding operation directly from the backlog buffer for partial resynchronization.

(3) otherwise, it means that the backlog buffer cannot cover the inconsistent data and carry out full synchronization.

The essential approach is to exchange space for time, obviously sacrificing part of the space here for efficient partial resynchronization, and the income ratio is very large.

2.Sentinel

Essence: multi-master-slave server Redis system, multi-master-slave management monitoring is added to ensure high availability of the system.

3. Cluster

The official version of Redis cluster has not yet become popular in industry, the following mainly introduces the management system and operation system of the cluster.

2.1 slot- Cluster Unit

The datazone of the cluster consists of slot, and the slot for each node is allocated when the cluster is started.

2.2 customer request

When a customer requests, if the corresponding data hash does not belong to the slots managed by the request node, a MOVED error will be returned to the customer and the correct slots will be given.

From this point of view, the redis cluster is not friendly enough, and the state within the cluster must be perceived by the customer.

2.3 disaster recovery

The master-slave server is used to back up the master, and if the master fails, the slave replaces the master.

Through the research of Redis, I deeply realize that all the processes of design are the process of tradeoff and abandonment. The same is true in daily work and development. whether a sentence of code is written well or whether a module is designed scientifically is measured from the perspective of speed and memory to see whether optimization is needed or not, and to evaluate what each optimization will gain and what will be lost at the same time. What gains far outweigh losses is good optimization, which is often more targeted and efficient for development and promotion.

At this point, the study on "what are the Redis data structures and memory management methods" is over. I hope to be able to solve your doubts. The collocation of theory and practice can better help you learn, go and try it! If you want to continue to learn more related knowledge, please continue to follow the website, the editor will continue to work hard to bring you more practical articles!

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.