Summary includes data structure, persistence, master and slave replication, cluster, sentinel, transaction, cache three issues, distributed lock knowledge, hope to help!
The data structure
string
In the data structure of Redis, String is mainly used to store some data of String type. The implementation of String type in Redis is realized by SDS, which is a dynamic String type. In Redis, string length and string expansion are realized by defined objects. A string object is defined in Redis. The main data stored in this object is string length length, unused string capacity free, and string data, etc.
Therefore, the time complexity of obtaining the length of a string in Redis is O1. In order to solve the problem of storing variable strings, Redis uses dynamic expansion to solve this problem. When Redis adds a string to a string, it will judge whether the capacity of the string is sufficient. Redis performs a pre-allocation strategy for strings, that is, when SDS allocates space for strings, it also allocates a capacity for unused strings, which can be used to prepare for new strings.
If Redis allocates 10 bytes of unused space to the SDS, then the total length of the SDS is 10+10+1=21. The last increment is because Redis follows the C rule of adding an empty byte at the end.
The list
The linked list structure in Redis is roughly the same as that in data structures.
The dictionary
Redis uses a table attribute to hold the key-value values. The tabkle attribute is an array. In Redis, the table attribute is used to hold the key-value values. This array is of type dictEntry, which is what we call key-value.
Redis also uses the hashing algorithm to store dictionary values. Since the hashing algorithm is used, it is inevitable that there will be a hash conflict problem, that is, two or more keys are allocated to an array. In this case, Redis uses the chain address method to solve the problem. Each hash table node has a next pointer, and multiple hash table nodes can use the next pointer to form a single necklace table. Multiple nodes assigned to the same table can be connected through the unidirectional list.
Jump table
The bottom implementation of ZSet in Redis is realized by skip list, and ordered collection is realized by skip list.
Jump table implementation is based on a special kind of data structure, the structure of time complexity for Ologn, this can make a comparison with balanced tree, to look for in the balanced tree a number of paths from the root down through the search, until you find the data, if the data is too much, then find the path length and impact on the performance of a certain, Skip lists are a great solution to this problem.
Jump table has several concepts, layer, length, head, tail, score, members of the object, the jump table structure is divided into multiple nodes, each node contains score, members of the object, layer, score for each node to store values, and the data in the node is stored in order, members of the object can be understood as each node to save a member of the object, Layer is a characteristic part in skip list, skip list can realize fast query is dependent on layer.
Node can be understood as a floor, member objects are stored in the first layer, the score is stored in the second layer, the second layer above is the layer, each layer can be connected to the previous node.
As shown in the figure, node 1 points to the ninth layer of node 4, so if you want to access the data of 6, you can find the data of 6 in node 4 directly from node 1 to node 4. This path can only be traveled once.
The integer
In Redis, integer data structures are used to store integers. Integers in Redis can distinguish between 16-bit, 32-bit and 64-bit data. Therefore, in order to solve the problem of data transformation, Redis uses the upgrade method to realize data storage. When the data changes to the 32-bit, then under 16 is not enough to store the data, you need to upgrade the key value of 16 bits, upgrade to 32 bits to store the changes, and 32-bit store 64 – bit data can perform upgrades, and the upgrade process is irreversible, it also ensures data with change after no longer need to upgrade.
Persistence mechanism
AOF
In order to make up for the fact that RDB can lose data at a certain point in time, Redis also has another method of persisting data. The difference between AOF and RDB is that RDB persists data, while AOF persists data. When Redis runs a write command, the command is successfully executed. If AOF persistence is enabled, these write commands are stored in the AOF buffer.
Enable AOF persistence in the Redis configuration file by setting the appendonly parameter.
AOF persistence has three modes: always, everysec, no,
Always means that executing a write command will write data from the Aof buffer to the Aof file and synchronize the Aof file,
Everysec means that a write command is executed to write data from the Aof buffer to an Aof file, and the subsequent Aof files are synchronized every second
No means that a write command is executed to write data from the Aof buffer to the Aof file, but the AOF file is not synchronized. It is up to the operating system to synchronize aof files.
As you can see from the above, AOF persistence will lose less data, so when using Redis, you can enable both persistence to keep data loss to a minimum.
RDB
RDB mode persistence is divided into two implementation methods, SAVE and BGSAVE. The implementation of SAVE is rough. When the SAVE command is executed for persistence, Redis will persist through the main thread, so when the persistence operation is performed, other tasks must stop and wait for the end of the persistence operation, other tasks will be performed. This persistence mode affects the execution of Redis tasks and is not recommended.
The other is BGSAVE, BGSAVE is more gentle, this way does not occupy the main thread Redis, but on the basis of the main thread fork a child thread for persistence operation, so it does not affect the main thread processing Redis tasks, but will consume some performance. Generally, BGSAVE is used to persist RDB.
On the other hand, RDB persists data, which is called the database state. When we perform operations on the Redis database, RDB persistence will persist the data to disk, but this way of persisting will lose some of the data, because RDB persistence starts at a point in time. RDB persistence is performed at a certain point in time, and if a subsequent outage occurs, data after that point in time will be lost.
Finally, when Redis starts up, it will automatically check whether the RDB file exists. If the RDB file exists, it will load the RDB file and restore the data in the RDB file. However, if the AOF persistence is enabled in Redis, then Redis will load the AOF persistent file first.
A master-slave replication
Redis sometimes needs to synchronize data from other servers, which can be achieved by the master/slave replication function in Redis. There are two versions of master/slave replication in Redis, before 2.8 and after 2.8, first say before 2.8.
Before version 2.8, master-slave replication was realized by SYNC. In Redis, the implementation process of SYNC consists of two steps, namely synchronization and command propagation. Synchronization mainly realizes sending persistent files of the master database to the slave database and synchronizing data through files, while command propagation realizes after sending persistent files. The commands executed by the master database are sent to the slave database synchronously, thus ensuring the data consistency between the master and slave databases.
The old version: the SYNC
1, synchronization,
When the slave database executes SYNC and sends it to the master database, the master database receives the SYNC command and executes the BGSAVE command for RDB persistence. Then, the persisting RDB file is sent to the slave database, and the file is received from the master database and loaded. Commands executed by the primary database after persistence are synchronized to the buffer.
2. Command propagation
After the synchronization is complete, the master database will persist all data from the master database from BGSAVE, and the data generated by the master database will be stored in the buffer, and the data in the buffer will be synchronized to the slave database to achieve command propagation. This ensures that the data generated by the master database will be sent to the slave database in time to ensure the consistency of the data.
But the way of the master-slave replication will exist problems, when from the database after downtime, then will need to send again during the master-slave replication to RDB file, and then spread to command, but already have previous data from the database, the lack of just after downtime data, perform all such master-slave replication for Redis more consumption performance, So it was optimized after 2.8.
New: PSYNC
The new version of master-slave replication is implemented using PSYNC, which has two modes: full resynchronization and partial resynchronization. When the slave database has never copied the data from the master database, the PSYNC command will use full resynchronization to synchronize the data.
1. Complete resynchronization
The full resynchronization process is similar to the previous version of SYNC, with the RDB file being sent before command propagation.
2. Partial resynchronization
Partial resynchronization is designed to handle disconnected reconnections. For partial resynchronization, you need to know several concepts, such as the copy offset, the copy backlog buffer, and the container ID.
Copy the offset is divided into two, one is offset refers to the primary database is sent to the main database data from a database offsets, an offset from the database to mean that receives the primary database data from the database offsets, when the offset is less than the primary database from the database when the offset is proved that the need for master-slave replication.
Copy the backlog buffer. When the master database sends commands to the slave database, these commands are written to the copy backlog buffer. The commands written to the buffer are synchronized with the offset of the master database.
The container ID, the container ID is the ID of the primary database in case the primary database goes down, the primary database changes, the original primary database becomes invalid, and the secondary database cannot replicate from the original primary database. In this case, you need the container ID to solve this problem. When the container ID stored in the slave database is inconsistent with the ID of the primary database to be requested, the primary database has changed and a full resynchronization of the new primary database is required.
The sentry
The function of sentinel in Redis is mainly to manage the Redis cluster. When there is a Master and multiple slaves in a Redis cluster, when the master is disconnected, there needs to be an administrator to maintain the normal operation of the whole cluster, but the master server is disconnected. The whole cluster will crash, and that’s what the sentry will do.
Sentinel monitors all Redis servers in a Redis cluster, and when the master server is disconnected, sentinel is in charge of maintaining the entire cluster.
Implementation:
If the sentinel detects that the master is disconnected, it will remove the master server from the monitor list, select a new master server from the slave server, and set the old master server to the slave server. In this way, when the old master server is reconnected to the new master server, it will become the slave server of the new master server, so that the old master server will not have to compete with the new master server for the master role when the old master server is reconnected, and the stability of the whole cluster is guaranteed.
In the use of sentinels, multiple sentinels generally work together and a voting mechanism is conducted among sentinels. Only when multiple sentinels jointly decide to disconnect a Redis server, this server will be removed from the surveillance of sentinels. For example, when there are three sentinels monitoring a cluster, when the master server is disconnected, The master server is removed from the cluster only when both sentinels agree that the server is offline. Sentinel then completes the failover operation, elects the new master server, and converts the old server to the slave server of the new master.
The status of the sentinel monitoring server is to send monitoring commands every ten seconds.
The cluster
When using Redis, a Redis database is not enough to meet the requirements of the scenarios. At this time, Redis cluster is needed to solve the scenarios that pursue high performance.
Each Redis database is a cluster. Multiple Redis databases form a whole cluster. When we want to add a database to the cluster, we use the cluster meet command to do so.
Implementation method: CLUSTER MEET
Process:
The Redis cluster is enabled by setting the cluster-enable parameter in the configuration file. When this parameter is enabled, run the cluster meet command to add the database to the cluster.
The underlying implementation of the cluster is based on the clusterNode structure. Each node in the cluster has a clusterNode. This structure holds the node name, node IP address, node port, and current era.
Each node also uses the clusterState structure to store its connection to other databases in the cluster. The clusterNode holds the current era of the cluster, the status of the cluster, and an array of Nodes. The array structure is the clusterNode structure. So the Nodes array holds the clusterNode structure of other databases.
The transaction
Transaction has also been touched in the database. The understanding of transaction is that multiple operations are executed in order, and either all of them succeed or fail. As long as there is an error in one operation, the original operation will be rolled back and the subsequent operation will not be executed.
The transaction function is also realized in Redis, and the transaction of Redis is realized through MULTI, EXEC and WATCH.
Implementation method
The MULTI command is used to start the transaction. When we execute the MULTI command, the client will start the transaction, and the subsequent commands will be cached temporarily, waiting for the transaction to start.
The EXEC command executes transactions. All commands executed after the MULTI command are executed sequentially after the EXEC command is executed and the results are returned.
The WATCH command is used to monitor the key in the transaction. The WATCH command can monitor the key we operate. If the key we operate is modified by other clients, our transaction cannot be executed successfully.
process
The Redis transaction process is divided into three steps: transaction start, command enqueue, and transaction execution.
WATCH Command Implementation
If the key of the operation is the key in the transaction when executing the modification command LPUSH, SET, SADD, DEL, etc., then the transaction will fail to execute and return an empty reply.
In addition, some special cases of transactions are as follows: When we execute the multi command after executing various commands error, then finally execute the EXEC command, Redis will directly report error before 2.6.5, after 2.6.5 will not execute these error commands.
If the operation key type of the command executed after the MULTI command is incorrect, the transaction will be executed successfully when the transaction is finally executed through EXEC, but the wrong command will be reported.
Three problems with Redis cache
Cache avalanche
Cache avalanche occurs when a large amount of data in the cache is invalid, so a large number of requests will be sent to the DB, and the large number of requests will cause the DB to crash, causing the cache avalanche.
In the case of cache avalanche, we can make the cache data invalidation time set more uniform to avoid the large number of cache times invalidation at the same time. Because we can add a random value to the cache time, so that the cache time invalidation time is also random, avoiding the problem of cache invalidation together.
Since cache invalidation, it can also be avoided by master-slave replication mode, by setting multiple slave databases, when a database cache invalidation, the request can be sent to another database cache, avoid directly to the DB request.
The cache to penetrate
Cache penetration means that a large number of requests are made for data that does not exist in the cache or DB. As a result, a large number of requests are sent to DB, resulting in excessive pressure on DB and eventually causing DB to crash. For example, in the e-commerce business, a request for an item with ID =-1 does not exist in the cache or DB. When a large number of these requests are sent to DB, DB will crash.
To avoid this situation, we can adopt the following methods: First, implement simple filtering logic in the interface, and add judgment conditions in the interface to filter some data that does not meet the requirements to avoid the request to the cache. Second, the use of bloom filter, bloom filter is a long binary vector and a series of random mapping function, whether can be used to retrieve an element in a collection, so that when a request to carry id = 1 to cache, whether through the bloom filter retrieval – 1 in the cache, if there is no will not enter the cache and DB, This ensures that intercepting requests upstream will not hit the cache or THE DB.
The implementation of Bloom filter is mainly based on the hash function. For example, the location of data stored in a hashMap is realized by the hash function. However, a single hash function will have the problem of hash collision, and bloom filter uses multiple hash functions to solve this problem. If one of the values of the hash functions indicates that the element is not in the set, then that element is definitely not in the set, and if all of the values of the hash functions indicate that the element is in the set (which is possible), then that element is in the set.
Therefore, the Bloom filter does not need to store the element itself to determine the element, and the space efficiency and query efficiency are better.
However, it also has some disadvantages, namely, misjudgment. Its judgment is not accurate and there will be some errors. With the increase of elements, the error rate will also increase. In addition, the hash table can be used directly to filter the data if there are few elements.
Cache breakdown
The problem with a cache breakdown is that when a large number of requests to access a cache fail at a moment’s time, these requests will be sent to the DB at once, causing the DB to crash, resulting in a cache breakdown.
Cache breakdown can imagine the situation of e-commerce snapping up, if a commodity in the e-commerce snapping up, a large number of users are snapping up the goods to place an order, if the commodity cache time suddenly expired, then the order request will be hit to DB, causing the collapse of DB.
Therefore, for this kind of problem, the operation of placing an order can be locked. Only the user’s request can grab the lock to place an order, so there is only one request for placing an order at a moment. Even if the cache is invalid, only one request will be sent to DB.
In Redis, this can be achieved by setting a distributed lock, which limits the cache data to only one request at a time.
Redis distributed lock implementation
In view of the above cache breakdown problem, Redis can implement distributed lock to ensure that only one request can obtain the cache data at a time.
Redis can implement distributed lock through the setNX method. The setNX method is a method of Redis to add cache, the process of the method is: the cache key and value request to the method, the method calls SetParams method nx and the px method, the Nx method is used to determine whether the cache key exists. The px method is used to set the expiration time of the key. When the expiration time is exceeded, the key will become invalid. When we want to delete the key, we will use lua script to implement the implementation.
But this implementing distributed lock also exist some problems, the first is the expiration time problem, if we set the expiration time for 1 s, but a user when using the key after 1 s is not over yet, then the key will be failure, and the user clearly has not used up, so this time will need to consider an expiration time contract.
If the renewal expiration time exists in Redis, there is a Watch Dog to solve this problem. The function of Watch Dog is to monitor the use of a key and the client. If the client is still using the key after the expiration time, Then Watch Dog will renew the client until it runs out.
In addition to Redis, zooKeeper can also implement distributed locking. Zookeeper has persistent nodes and temporary nodes, which can be implemented according to the characteristics of the node.
First create a lasting node perLock, all need to get locked thread will create a temporary order under the last node child nodes, and each time it is the smallest order node for locks, processed when the smallest node, disconnect the connection, temporary node is automatically deleted, and then let the other node without acquiring a lock for the lock. And when a client creates a temporary node and fails to acquire the lock, it will find the node with the smallest serial number to acquire the lock, and then register a listening time on the node. When the node with the smallest serial number disconnects and releases the lock, then the later node will acquire the lock.
Only from the “Redis design and implementation” and usually read the accumulation of blog, if there is infringement please inform delete!