Redis external data structure?

basis

  • String: internal realization of SDS, cache function, counter, and shared user Session.
  • List: ordered List, message queue, comment List
  • Hash: KV structure, no nested objects, few scenes.
  • Set: Automatic deduplication of unordered sets, reduplication and intersection merging operations in distributed environments.
  • Sorted Set: De-sorted, ranked, weighted queues.

A bit more advanced

  • HyperLogLog: for imprecise recasting function, more suitable for large-scale data recasting, such as statistics UV.
  • Geo: it can be used to save the geographical location and calculate the location distance or calculate the location according to the radius, people nearby, and calculate the optimal map path.
  • Pub/Sub: Subscribe to publish function, message queue.
  • Redis Module
  • BloomFilter: Bitmap supports storing information in bits, which can be used to implement BloomFilter.
  • RedisSearch
  • Redis-ML
  • Pipeline: Batch execute a set of instructions, return all results at once, reduce frequent request responses.

Redis internal data structure

  • dict
  • sds
  • ziplist
  • quicklist
  • skiplist

Here is mainly internal implementation, specific words here do not show, interested in their own access.

Is there a problem with a large number of keys expiring at the same time?

If there is too much concentration between Key expiration dates, Redis may experience a temporary lag. In severe cases, a cache avalanche can occur. You can spread out the expiration time by adding a random value to the expiration time.

Why is Redis single threaded?

Since CPU is not the bottleneck of Redis, the bottleneck of Redis is memory and network bandwidth, single thread is easy to implement, and CPU is not the bottleneck, so use single thread.

Why is Redis so fast?

  1. Completely memory based.
  2. The data structure is simple and the manipulation of the data is simple.
  3. Single threading avoids thread context switching overhead. There is no need to worry about locks, there is no lock and lock release.
  4. Use I/O multiplexing model, non-blocking IO.
  5. The underlying model is different, and the underlying implementation mode and client communication protocol are different. Redis built its own VM mechanism, and the general system calls function, will waste a certain amount of time to move and request.

Distributed lock?

High performance lock release. Blocking and non-blocking locks can be used. Deadlock cannot occur high availability setnx atomic command to acquire locks. Expiration time to avoid deadlocks. Determine if the lock is your own when you release it. Lua script judgment. Blocking locks self rotation and then sleep prevents CPU idling. Clustering ensures availability.

What’s wrong with the keys line?

Keys can scan a list of specified key patterns. Since Redis is single-threaded, the Keys instruction blocks for a while, and the online service pauses until the instruction completes. The SCAN command can extract the Key list of the specified mode without blocking, but there is a certain probability of repetition, so it only needs to do a repeat on the client. The overall time is longer than keys.

For incremental iteration commands such as SCAN, because keys may be modified during incremental iteration, incremental iteration commands provide only limited guarantees about the elements that are returned.

Redis does message queuing

Using the list structure as a queue, RPUSH produces messages and LPOP consumes messages. When there is no pop message, you need to sleep for a while to prevent the CPU from idling.

List also has a directive called blPOP, which blocks when there is no message until it arrives.

Produce once and consume many times?

Using the PUB/SUB topic subscriber pattern, a 1: N message queue can be implemented.

Cons: Production messages can be lost when the consumer goes offline, using a professional message queue such as RocketMQ.

Redis delay queue

With sortedSet, time stamp is used as score, message content is used as key to call Zadd to produce messages, and consumers use ZrangeByScore command to obtain data polling N seconds ago for processing.

Redis persistence?

RDB image persistence. AOF incremental persistence. When the Redis instance is restarted, memory is rebuilt using the RDB persistence file, and the AOF is used to replay the recent operation instructions for synchronization.

How about a sudden synchronization outage?

Depending on the configuration of the sync property of the AOF log, sync is enabled for every command. If closed, it writes once per second and loses at most 1s of data.

The principle of RDB

The fork and cow. Fork means that Redis creates a child process to perform RDB operations, cow means copy on write. After the child process is created, the parent process shares data segments, and the parent process continues to provide read and write services. The dirty page data is gradually separated from the child process.

Redis master-slave synchronization?

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.

How to guarantee the high availability of Redis cluster?

Redis Sentinal focuses on high availability and automatically promotes slave to Master in the event of a master outage.

Redis Cluster focuses on scalability. When a single Redis memory is insufficient, a Cluster is used to fragment storage.

How to solve the bottleneck of single opportunity?

The deployment mode of the cluster is Redis Cluster, which synchronously separates the master and slave nodes from the read and write, similar to the master and slave synchronization of Mysql. The Redis cluster supports N Redis master nodes, and each master node can mount multiple slave nodes.

This allows Redis to scale horizontally. If you want to support a larger cache, horizontally expand the number of master nodes so that each master node can hold more data.

Redis Sentinel cluster

Sentinels must have three instances to ensure their robustness, and sentinels + master/slave does not guarantee data loss, but high availability of the cluster. There is now a master+ sentry S1 + Sentry s2. The master is down. If either sentry S1 or S2 thinks you are down, they will switch and elect a sentry to perform the failure.

Memory flushing mechanism?

  • Memory limit is reached and the client tries 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-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.

The policies volatile- LRU, volatile- Random, and volatile- TTL are designed to be like noeviction if no key satisfies reclamation prerequisites.

Handwritten LRU?

Leetcode-cn.com/problems/lr…

import java.util.HashMap;

public class LRUCache {

    class Node {

        // Next pointer to the node
        public Node next;

        // Prev pointer to the node
        public Node prev;

        public int key, value;

        public Node(int key, int value) {
            this.key = key;
            this.value = value; }}class DoubleLinkList {

        / / head node
        private Node head;
        / / end nodes
        private Node tail;

        private int size;

        public DoubleLinkList(a) {
            head = new Node(0.0);
            tail = new Node(0.0);
            head.next = tail;
            tail.prev = head;
            this.size = 0;
        }

        // Add nodes to the head of the list
        public void addFirst(Node node) {
            node.prev = head;
            node.next = head.next;
            head.next.prev = node;
            head.next = node;
            size++;
        }

        // Delete the specified node from the list. The node must exist
        public void remove(Node node) {
            node.prev.next = node.next;
            node.next.prev = node.prev;
            size--;
        }

        // Delete the last node in the list and return that node, time O(1)
        public Node removeLast(a) {
            if (head.next == tail) {
                return null;
            }

            Node last = tail.prev;
            remove(last);
            return last;
        }

        // Return the length of the list
        public int size(a) {
            returnsize; }}private HashMap<Integer, Node> hashMap;

    private DoubleLinkList cache;

    private int cap;

    public LRUCache(int capacity) {
        hashMap = new HashMap<>();
        cache = new DoubleLinkList();
        this.cap = capacity;
    }

    // Upgrade a key to the most recently used one
    private void makeRecently(int key) {
        Node node = hashMap.get(key);
        // Delete the node first
        cache.remove(node);
        // Add this node to the queue head
        cache.addFirst(node);
    }

    // Add the most recently used element
    private void addRecently(int key, int val) {
        Node newNode = new Node(key, val);
        // Add nodes to the head of the list
        cache.addFirst(newNode);
        // Add the node to the map
        hashMap.put(key, newNode);
    }

    // Delete a key
    private void deleteKey(int key) {
        Node node = hashMap.get(key);
        cache.remove(node);
        hashMap.remove(key);
    }

    // Remove the oldest unused element
    private void removeLeastRecently(a) {
        // The last element of the list is the one that has not been used for the longest time
        Node node = cache.removeLast();
        hashMap.remove(node.key);
    }

    public int get(int key) {
        if(! hashMap.containsKey(key)) {return -1;
        }

        makeRecently(key);
        return hashMap.get(key).value;
    }

    public void put(int key, int val) {
        // If the key already exists
        if (hashMap.containsKey(key)) {
            deleteKey(key);
            addRecently(key, val);
            return;
        }

        if(cap == cache.size()) { removeLeastRecently(); } addRecently(key, val); }}Copy the code