Introduction to the
Redis is an open source, in-memory data structure storage system that can be used as a database, cache, and messaging middleware. It supports many types of data structures, such as strings (hashes), lists (Lists), sets (sets), sorted sets (sorted sets) and range queries, bitmaps, Hyperloglogs and Geospatial index radius query, etc. Redis is built with replication, LUA scripting, LRU eviction, transactions and different levels of disk persistence, And provides high availability through Redis Sentinel and Automated partitioning (Cluster).
Why use a cache server
Caching is an effective way to improve hotspot data access performance in high concurrency scenarios and is often used in development projects.
Caches are classified into local cache, distributed cache, and multi-level cache.
For example, in our JVM heap, local cache is memory access, has no overhead of remote interaction, and has the best performance. However, limited by the capacity of a single machine, local cache is generally small and cannot be extended.
Distributed caches generally have good horizontal scaling capability and can cope well with large data volume scenarios. The disadvantage is that remote requests are required and the performance is not as good as local caching.
To balance this situation, multi-level caches are generally used in actual services. The local cache stores only the most frequently accessed hotspot data, and other hotspot data is stored in the distributed cache.
Redis & Memcached
-
Data structures: Memcached only supports simple key/value data structures, unlike Redis, which supports rich data types.
-
Persistent: Memcached cannot be persisted. Data cannot be backed up and can only be used for caching. After a restart, all data is lost.
-
Multithreading: Redis uses single threads to avoid the frequent context switching problems of multithreading and prevent the race problems that can arise from multithreading.
Memcache has some problems, such as poor concurrency, poor operability, insufficient atomic operation and data inconsistency in misoperation.
Because Redis uses only one core, while Memcached can use multiple cores, Redis performs better than Memcached when storing small data. For data over 100K, Memcached outperforms Redis, which has recently been optimized for storing large data, but still lags behind Memcached.
-
Distributed: Redis natively supports clustering mode, Memcached has no native clustering mode.
Redis supports data Replication. Data can be synchronized and replicated in real time through the master-slave mechanism. The master-slave mechanism is an important means for Redis to implement HA.
Threading model
file event handler
The structure of the file event handler consists of four parts:
- Multiple Socket
- IO multiplexing procedures
- File event dispatcher
- Event handler (connection reply handler, command request handler, command reply handler)
Multiple sockets may concurrently produce different operations, each corresponding to a different file event, but IO multiplexers listen for multiple sockets, queue events generated by the Socket, and the event dispatcher fetches events from the queue one at a time. The event is passed to the corresponding event handler for processing.
Why is Redis single thread so efficient?
- Completely memory based, the vast majority of requests are pure memory operations, very fast. Its data is stored in memory, similar to a HashMap, which has the advantage of O(1) time complexity for both lookup and operation.
- The use of single thread, avoid unnecessary context switch and competition conditions, there is no multi-process or multi-threading caused by the switch and CPU consumption, do not have to consider the problem of various locks, there is no lock release lock operation, there is no performance consumption due to the possibility of deadlock;
- Use multiplex I/O multiplexing model, non-blocking IO;
- Redis directly built the VM mechanism itself, because the general system calls system functions, will waste a certain amount of time to move and request;
The data structure
Basic: String, Hash, List, Set, SortedSet
Advanced: HyperLogLog, Geo, Pub/Sub, bitmaps
High: BloomFilter
basic
String: stores a simple object serialization String. Application scenarios: Cache hotspot data, counters, and session tokens
Hash: Saves unnested object attributes
List: lists. Application scenarios: simple message queue and paging
Set: unordered Set, automatic deduplication, application scenario: mutual friends
Sorted Set: ordered collection, automatic deduplication, application scenarios: ranking list, microblogging hot search
The advanced
Geo: can be used to save the geographical location, and the location distance calculation or according to the radius of the location calculation. Application scenario: Nearby people
Pub/Sub: subscribe/publish. Application scenario: simple message queue
HyperLogLog: Algorithm used to do cardinality statistics, such as data set {1, 3, 5, 7, 5, 7, 8}, then the cardinality of the data set {1, 3, 5, 7, 8}, cardinality (not repeating elements) is 5. Cardinality statistics is the rapid calculation of the cardinality within acceptable limits of error. Application scenario: Daily active user
Bitmap: Stores information in bits, which is the same as byte arrays, and has high counting efficiency. Application scenarios: Daily active users and Bloom filter
Bitmaps requires 12.5m of memory to store 100 million users
senior
BloomFilter
Bloom filters can be used to retrieve whether an element is in a collection. Its advantage is that its space efficiency and query time are far more than the general algorithm, but its disadvantage is that it has certain error recognition rate and deletion difficulty. It’s possible that the element you’re looking for is not in the container, but the value is 1 for all k positions that you hash. If the Bloom Filter stores blacklists, you can create a whitelist to store elements that might be misjudged. Deletion is difficult. An element put into the container is mapped to 1 in the k positions of the bit array. When deleting it, it cannot be simply set to 0 directly, which may affect the judgment of other elements.
Bloom filters work by mapping an element as it is added to a collection to K points in an array of bits set to 1 by K hash functions. When we search, we know (roughly) if it is in the set by looking at whether all of the points are 1’s: if any of the points have 0’s, the element must not be there; If both are 1, the element being checked is most likely in. That’s the basic idea of a Bloom filter.
Bloom Filter differs from single hash function bitmap in that Bloom Filter uses k hash functions, with each string corresponding to k bits. Thus reducing the probability of conflict.
Underlying data structure
SDS
Redis uses SDS (Simple Dynamic String) to store strings. SDS is also used as the AOF buffer in the BUFFER AOF module.
struct sdshdr {
// The length of occupied space in buF
int len;
// The length of the remaining free space in the BUF
int free;
// Data space
char buf[];
};
Copy the code
Benefits of using SDS:
- Easy to get the string length
- Prevent buffer overflow
- Reduce the number of memory reallocations when modifying strings
The list
One of the underlying implementations of List is a linked List
typedef struct listNode{
struct listNode *prev;
struct listNode * next;
void * value;
}
Copy the code
- Double-ended: Linked list nodes with prev and next Pointers, the time complexity of obtaining a node’s pre-node and post-node is O (N).
- Acyclic: the prev pointer on the head node and the NEXT pointer on the tail node both point to NULL, and access to the schema is terminated by NULL
- Header and tail: Because there are head and tail Pointers, the program takes O(1) time to obtain the first and last nodes of the list.
- Length counter: The linked list contains len, an attribute that records the length of the list
The integer set
The set of integers is one of the underlying implementations of a set. When a set contains only integers and the number of elements in the set is small, Redis uses intSet as the underlying implementation of the set.
typedef struct intset{
// Encoding mode
uint32_t enconding;
// The number of elements the collection contains
uint32_t length;
// Hold an array of elements
int8_t contents[];
}
Copy the code
The underlying implementation of a collection of integers is an array, which holds the collection elements in an ordered, non-repetitive pattern, and changes the type of the array as needed according to the type of the newly added element.
The dictionary
A dictionary, also known as a Symbol table, associative array, or map, is an abstract data structure for holding key-value pairs. Similar to HashMap, when a hash conflict occurs, elements are inserted using the head of a normal unidirectional list.
Rehash redistributes HT [0] data to HT [1], releases HT [0], sets HT [1] to HT [0], and finally allocates a blank hash table for HT [1].
Detailed steps for progressive Rehash:
1. Allocate space for HT [1] so that the dictionary holds both HT [0] and HT [1]
2. Maintain an index counter variable rehashidx in the dictionary and set its value to 0 to indicate the start of rehash
3. During rehash, every time a CRUD operation is performed on the dictionary, the program rehashes the data in HT [0] into the HT [1] table and increments the rehashidx by one, in addition to the specified operation
4. When all data in HT [0] is transferred to HT [1], set rehashidx to -1, indicating that rehash is complete
The benefit of adopting progressive Rehash is that it takes a divide-and-conquer approach, avoiding the massive computation that comes with centralized Rehash.
Jump table
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 are randomized data that store elements in a hierarchical linked list in an orderly fashion. Skip lists are as efficient as balanced trees — search, delete, add, and so on can be done in logarithmic expected time, and are much simpler and more intuitive to implement than balanced trees.
Redis uses skip tables in only two places, one to implement ordered collection keys and the other as internal data structures in cluster nodes.
persistence
RDB does mirrored full persistence and AOF does incremental persistence. Because RDB takes a long time and is not real-time enough, a large amount of data will be lost during downtime, so AOF is needed to cooperate with RDB.
RDB
RDB has very little impact on the performance of Redis, because it only forks a child process for persistence during data synchronization. Forking means that Redis creates a child process to perform RDB operations, cow means copy on write. After the child process is created, the parent and child processes share data segments. The parent process continues to provide read and write services and the dirty page data is gradually separated from the child process.
RDB is faster at data recovery than AOF because the data files are small and each record is saved only once, whereas AOF may hold multiple operation records for one record. RDB file storage format and Redis data in memory encoding format is the same, no data encoding work, so the CPU consumption is far less than AOF log loading.
Disadvantages: The snapshot interval may be long. If RDB is used for persistence, more data may be lost due to service failure. Large files may cause client lag during snapshot generation
The SAVE command is executed directly by the server process and blocks the server. The BGSAVE command is performed by the child process and does not block the server.
All save conditions set with the save option are saved in the server state. When any of the save conditions are met, the server automatically executes the BGSAVE command.
AOF
By default, RDB takes snapshots every five minutes, but AOF takes snapshots every second through a background thread called fsync, which loses at most one second of data.
AOF writes to log files in appends-only mode. It only writes data in append mode, which naturally reduces the overhead of disk addressing. The write performance is amazing, and the file is not easy to damage.
AOF logs are recorded in a way called very readable, which makes them suitable for emergency recovery in case of catastrophic data deletion. For example, the company’s interns flushes all data in flushall, so you can make a copy of the AOF log file as soon as the backend rewrite doesn’t happen. Delete the last flushall command and we’re done.
Disadvantages: The same data, AOF file is larger than RDB; When AOF is enabled, Redis supports lower QPS than RDB because logs are refreshed asynchronously every second
The AOF file records the database state of the server by saving all write command requests to modify the database; Command requests are stored in the AOF buffer and then periodically written and synchronized to the AOF file.
AOF rewrite first reads the current value of the key from the database, then uses a command to record the key value pair, instead of the previous multiple commands to record the key value pair, resulting in a new AOF file, the new AOF file and the original DATABASE state, but smaller;
When the BGREWRITEAOF command is executed, Redis maintains an AOF rewrite buffer that keeps track of all write commands executed by the server while the child process creates a new AOF file. When the child process completes creating a new AOF file, the server appends all the contents of the rewrite buffer to the end of the new AOF file. Finally, the server completes the AOF file rewrite by replacing the old AOF file with the new one.
Configuration items
no-appendfsync-on-rewrite
Whether to block background writes. The default value is no(blocking write operations). No means that the set operation of the new main process will be blocked, and yes means that the set operation of the new main process will not be blocked, and will be synchronized to the AOF file after the whole background write is completed. However, there is a small risk of data loss, and if performance is required, you can set it to yes to process commands asynchronously only when writing in the background.
auto-aof-rewrite-percentage
The percentage of the size of AOF files increased since the last rewriting-percentage 100. If the size of AOF files is at least 100% larger than the size of the last rewriting-percentage 100 file, Redis will execute the BGREWRITEAOF command.
auto-aof-rewrite-min-size
The minimum size of an AOF file to trigger a rewrite, i.e., the initial size of an AOF file to trigger a rewrite, and subsequent overwrites will not be based on this variable (based on the size of the last rewrite).
Out of memory
Expiry policies
Redis key expiration strategy, is a regular delete + lazy delete two.
Regular good understanding, default 100ms randomly selected some set expiration time key, to check whether expired, expired delete.
Inert delete, query and then determine whether expired, expired delete key does not return value.
Memory flushing mechanism
Redis triggers memory flushing when new data reaches the memory limit.
Configuration items
maxmemory
When configuring Redis to store data, specify a limited memory size, such as 100m. When the cache consumes more memory than this value, data flushing is triggered. If the value is set to 0, there is no limit on the amount of cached data, that is, the LRU function does not take effect. The default memory limit is 3GB for the 32-bit memory.
maxmemory_policy
Triggers the elimination policy after data elimination
- No-eviction: Returns errors when memory limit is reached and clients attempt to execute commands that will allow more memory to be used (most write instructions, but DEL and a few exceptions)
- Allkeys-lru: Attempts to reclaim the least-used key (LRU) to make room for newly added data.
- Volatile – LRU: Attempts to reclaim the least-used key (LRU), but only the key in the expired set, so that newly added data has space to store.
- Allkeys-lfu: Attempts to reclaim the most recently used key (LFU) to make room for newly added data.
- Volatile – lFU: Attempts to reclaim the least recently used key (LFU), but only the key in the expired set, so that newly added data can be stored.
- Allkeys-random: Retrieves random keys to make room for newly added data.
- Volatile -random: Retrievals random keys to make room for newly added data, but only for keys in expired collections.
- Volatile – TTL: Retrievals the keys in the expired set, and prioritized the keys with a shorter TTL to make room for newly added data.
maxmemory_samples
The precision of random sampling, that is, the number of keys taken out immediately. The larger the value is, the closer it is to the real LRU algorithm. However, the larger the value is, the higher the corresponding consumption will be, which has a certain impact on performance. The default sample value is 5.
Approximate LRU algorithm
The real LRU algorithm requires a bidirectional linked list to record the most recently accessed order of data, which is relatively memory consuming.
Redis does this by sampling a small number of keys and then reclaiming the oldest keys that have not been accessed. By adjusting maxmemory-samples, the accuracy of the algorithm can be adjusted.
The key space of Redis is placed in a hash table, and to select the oldest unaccessed key from all the keys, you need another data structure to store the source information, which is obviously not cost-effective. At first, Redis just randomly selected 3 keys and eliminated them. Later, the algorithm improved to N keys, the default is 5.
Redis 3.0 improves the performance of the algorithm by providing a pool of candidate keys to be eliminated. By default, there are 16 candidates in the pool, which are sorted according to the idle time. During the update, N keys are randomly selected from the Redis key space and their idle time is calculated. The key will enter the pool only when the pool is insufficient or the idle time is greater than the minimum one. Then, the key with the maximum idle time is selected from the pool and eliminated.
The reason why Redis doesn’t use a real LRU implementation is because it requires too much memory. But approximated LRU algorithms should be equivalent for applications.
- Light gray bands are objects that have been reclaimed.
- Gray bands are objects that have not been collected.
- The green band is the object being added.
- In the theory of the LRU implementation, we hope that the first half in the old key will expire. Redis’s LRU algorithm is the outdated key of probability.
distributed
Redis supports three distributed deployment modes: master-slave replication, sentinel mode, and cluster mode
A master-slave replication
Way to work
Redis can use master slave synchronization and slave slave synchronization. During the first synchronization, the primary node performs a BGSave and records subsequent modifications to the memory buffer. After the synchronization is complete, the RDB file is fully synchronized to the replication node, and the replication node loads the RDB image to the memory. After the loading is complete, the master node is notified to synchronize the modified operation records to the replication node for replay. Subsequent increments are synchronized through an AOF log, similar to a database’s binlog.
advantages
Read/write separation can be implemented to share the load of read operations on the primary server
disadvantages
Redis does not have automatic fault tolerance and recovery functions. The breakdown of the slave host will lead to the failure of some front-end read and write requests. Therefore, it is difficult to support online capacity expansion, which becomes complicated when the cluster capacity reaches the upper limit.
The guard mode
When the primary server is out of service, a secondary server can be upgraded to the primary so that service can continue, but this process requires manual operation. To this end, Redis 2.8 provides the Sentinel tool for automated system monitoring and recovery.
The sentry’s role is to monitor the health of the Redis system. Its functions include the following two.
(1) Monitor the normal operation of the primary and secondary servers. (2) When the primary server fails, the secondary server will be automatically converted to the primary server.
Way to work
Sentinel is a high availability (HA) solution of Redis. Sentinel system consists of one or more Sentinel instances, which can monitor any number of master servers and all slave servers under these master servers. Automatically upgrades a secondary server under the offline primary server to the new primary server, which then continues to process command requests in place of the offline primary server.
Sentinel (Sentinel) mechanism provided by Redis automatically monitors the running status of master/slave after Redis is started in Sentinel mode. The basic principle is as follows: Each sentinel only has one election chance. When the main library fails, the sentinels vote to choose one from the library to take over the tasks of the main library, and the rest are still from the library
advantages
- Read/write separation can be implemented to share the load of read operations on the primary server
- The master and slave can be switched automatically for higher availability
disadvantages
- Redis is difficult to support online capacity expansion, which can be complicated when the cluster capacity reaches its maximum
Cluster pattern
Redis cluster is a distributed server farm consisting of multiple master and slave node groups with replication, high availability and sharding features. The Redis cluster can perform node removal and failover without sentinel sentinel. Each node needs to be set to cluster mode, which has no central node and can scale horizontally and linearly to tens of thousands of nodes according to official documentation (no more than 1000 nodes are officially recommended). Redis clusters provide better performance and high availability than previous versions of Sentinel mode, and cluster configuration is very simple.
The cluster mode has the following characteristics:
- Distributed network service cluster composed of multiple Redis servers;
- There are multiple Master nodes in the cluster, and each Master node is readable and writable.
- Nodes communicate with each other and are connected in pairs;
- The Redis cluster has no central node.
advantages
-
In sentry mode, there is still only one Master node. Sentinel mode does not relieve write stress when concurrent write requests are large. We know that only the master node has the write ability. If multiple master nodes can be configured in a cluster to ease the write pressure, the Redis-Cluster cluster mode can meet such requirements.
-
In a Redis-cluster Cluster, slave nodes can be added to each master node, and the master and slave nodes directly follow the characteristics of the master and slave model.
When users need to process more read requests, adding secondary nodes can expand the read performance of the system.
failover
The primary nodes of the Redis cluster have built-in node failure detection and automatic failover similar to Redis Sentinel. When a primary node in the cluster goes offline, other online primary nodes in the cluster notice this and fail over the offline primary nodes. The method of cluster failover is basically the same as that of Redis Sentinel, except that in a cluster, the failover is performed by other online primary nodes in the cluster, so the cluster does not need to use Redis Sentinel.
Cluster Sharding strategy
Common clustering sharding algorithms include general Hash algorithm, consistent Hash algorithm, and Hash Slot algorithm. Redis uses Hash Slot
General hash algorithm
Calculation method: Hash (key)%N
Disadvantages: If you add a redis, the mapping formula becomes hash(key)%(N+1)
If a Redis is down, the mapping formula becomes hash(key)%(n-1)
In both cases, almost all caches are invalidated.
Consistent hashing algorithm
Construct a ring of integers of length 2^32 and place it on the ring based on the hash value of the node name (distributed around [0,2^32-1]). Now to store the resource, find the nearest node on the ring clockwise according to the Hash value of the Key of the resource (also distributed at [0,2^32-1]), and establish the mapping relationship between the resource and the node.
Advantages: When a node is down, data on the upper node is migrated to the next node in the clockwise direction. When a new node is added, only part of the data needs to be migrated to this node with little impact on other nodes
Deleting a node
The new node
Disadvantages: Data is not evenly distributed in the ring. A node may store too much data. When the node goes down, a large amount of data floods into the next node, causing the other node to fail, and then all nodes fail
Improvements: Introduced the concept of virtual nodes, imagine that there are many “virtual nodes” on this ring, the storage of data is to find a virtual node along the clockwise direction of the ring, each virtual node will be associated with a real node
The Hash algorithm of Slot
Redis uses Hash Slot sharding algorithm to calculate the storage location of keys. The cluster divides the database into 16384 slots, and all key-value data is stored in one of these slots. Slot_number =CRC16(key)%16384. CRC16 is a 16-bit cyclic redundancy checksum function.
The client may select any redis instance to send the command, and each Redis instance that receives the command will compute the hash slot corresponding to the key. If it receives the command, it will process the hash slot locally. Otherwise, it will return moved to the client and ask the client to redirect to the corresponding node to execute the command
Matters needing attention
Set the expiration time
If a large number of key expiration times are set too centrally, Redis may experience a temporary lag at that point in time. Severe caching avalanches occur, and we generally need to add a random value to the time to spread out the expiration time.
E-commerce home pages often use scheduled tasks to refresh the cache. A large number of data may have a concentrated expiration time. If the expiration time is the same and a large number of users flood in at the expiration time, the cache avalanche may occur.
Cache avalanche: When a large number of cached keys fail at the same time and a large number of requests fall on the database, the database becomes overwhelmed. (Handling method: Add a random value to the failure time to avoid simultaneous failure)
Cache penetration: users constantly access data that is not in the cache or database. (Processing method: request parameter verification, put the key that cannot be queried into the cache, and set the value to NULL)
Cache breakdown: For hot data, if there are always high concurrency requests, just when the cache expires, then a large number of requests will fall on the database (set the hot period not to expire)
Keys defects
Redis single-threaded. The keys command causes the thread to block for a period of time and the online service to pause until the command is executed. The scan command can be used to extract the key list of the specified mode without blocking, but there is a certain probability of repetition. It is ok to perform a deduplication on the client, but the overall time will be longer than that of the direct command of keys.
Question supplement
Redis dictionary incrementally expands
Although Redis implements progressive rehash on the secondary server for read and write operations, if the server is idle, the Redis database will use two hash tables for a long time. So in a Periodic Redis function, if a dictionary is found doing progressive rehash, it will take 1 millisecond to help with progressive rehash
persistence
Redis persisted database files are RDB files. If AOF is enabled, data is persisted in AOF files
Why are there 16,384 hash slots
Write in the last
I started to write blog articles recently. If you think your writing is ok, please give me a thumbs-up to let me know that I did not spend my time in vain. Your thumbs-up is a great encouragement to me.
Do not build a high platform with floating sand, and you.