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.