Redis数据持久化和缓存淘汰机制_redis list淘汰

Redis数据持久化和缓存淘汰机制

1、Redis持久化

• 持久化就是把内存的数据写到磁盘中去，防止服务宕机了内存数据丢失。持久化的话是Redis高可用中比较重要的一个环节，因为Redis数据在内存的特性，持久化必须得有。

• Redis 提供 RDB 和 AOF 两种持久化机制，RDB是Redis默认的持久化方式。

1.1、RDB原理

• RDB持久化产生的RDB文件是一个经过压缩的二进制文件，这个文件被保存在硬盘中，redis可以通过这个文件还原数据库当时的状态。

• RDB文件可以通过两个命令来生成：

  • SAVE：阻塞redis的服务器进程，直到RDB文件被创建完毕。
  • BGSAVE：派生(fork)一个子进程来创建新的RDB文件，记录接收到BGSAVE当时的数据库状态，父进程继续处理接收到的命令，子进程完成文件的创建之后，会发送信号给父进程，而与此同时，父进程处理命令的同时，通过轮询来接收子进程的信号。

• RDB 是把内存中的数据集以快照形式写入磁盘，实际操作是通过 fork 子进程执行，采用二进制压缩存储；使用 fork 的目的最终一定是为了不阻塞主进程来提升 Redis 服务的可用性

快照实现过程

• Redis使用fork函数复制一份当前进程（父进程）的副本（子进程）；
• 父进程继续接收并处理客户端发来的命令，而子进程开始将内存中的数据写入硬盘中的临时文件；
• 当子进程写入完所有数据后会用该临时文件替换旧的RDB文件，至此一次快照操作完成。
• **在执行fork的时候操作系统（类Unix操作系统）会使用写时复制（copy-on-write）策略，即fork函数发生的一刻父子进程共享同一内存数据，当父进程要更改其中某片数据时（如执行一个写命令 ），操作系统会将该片数据复制一份以保证子进程的数据不受影响，**所以新的RDB文件存储的是执行fork一刻的内存数据。

1.2、AOF原理

• AOF持久化是备份数据库接收到的命令，所有被写入AOF的命令都是以redis的协议格式来保存的。

• AOF 是以文本日志的形式记录 Redis处理的每一个写入或删除操作。在AOF持久化的文件中，数据库会记录下所有变更数据库状态的命令，除了指定数据库的select命令，其他的命令都是来自client的，这些命令会以追加(append)的形式保存到文件中。

• redis可以在AOF文件体积变得过大时，自动在后台重写AOF，重写后的新AOF文件包含了恢复当前数据集所需的最小命令集合，整个重写操作是绝对安全的，

• 因为redis在创建新AOF文件的过程中，会继续将命令追加到现有的AOF文件里面，即使重写过程中停机，现有的AOF文件也不会丢失。而一旦新AOF文件创建完毕，redis就会从旧AOF文件切换到新AOF文件，并开始对新AOF文件进行追加操作。

1.3、小结

• RDB 是把内存中的数据集以**快照形式写入磁盘，实际操作是通过 fork 子进程执行，采用二进制压缩存储；AOF 是以文本日志的形式**记录 Redis 处理的每一个写入或删除操作。

• RDB 把整个 Redis 的数据保存在单一文件中，比较适合用来做灾备，但缺点是快照保存完成之前如果宕机，这段时间的数据将会丢失，另外保存快照时可能导致服务短时间不可用。

• AOF对日志文件的写入操作使用的追加模式，有灵活的同步策略，支持每秒同步、每次修改同步和不同步，缺点就是相同规模的数据集，AOF 要大于 RDB，AOF 在运行效率上往往会慢于 RDB。

• Redis本身的机制是 AOF持久化开启且存在AOF文件时，优先加载AOF文件； 因为AOF的数据是比RDB更完整的

2、Redis缓存淘汰机制

2.1、key过期策略

• Redis key的过期时间和永久有效分别EXPIRE和PERSIST命令进行设置

• Redis的过期策略，是有定期过期和惰性过期两种

  • 定期过期：每隔一定的时间，会随机扫描一定数量的数据库的expires字典中一定数量的key，并清除其中已过期的key。默认100ms就随机抽一些设置了过期时间的key，去检查是否过期，过期了就删了。

  • 惰性过期：只有当访问一个key时，才会判断该key是否已过期，过期则清除。

但是仅仅通过设置过期时间还是有问题的。如果定期删除漏掉了很多过期 key，然后你也没及时去查，也就没走惰性删除，此时会怎么样？如果大量过期 key 堆积在内存里，导致 Redis 内存块耗尽了。怎么解决这个问题呢？ Redis 内存淘汰策略

2.2、内存淘汰策略

Redis的内存淘汰策略是指在Redis的用于缓存的内存不足时，怎么处理需要新写入且需要申请额外空间的数据。

• noeviction：当内存不足以容纳新写入数据时，新写入操作会报错。

• allkeys-lru：当内存不足以容纳新写入数据时，在键空间中，移除最近最少使用的key。（这个是最常用的）

• allkeys-random：当内存不足以容纳新写入数据时，在键空间中，随机移除某个key。

  设置过期时间的键空间选择性移除

• volatile-lru：当内存不足以容纳新写入数据时，在设置了过期时间的键空间中，移除最近最少使用的key。

• volatile-random：当内存不足以容纳新写入数据时，在设置了过期时间的键空间中，随机移除某个key。

• volatile-ttl：当内存不足以容纳新写入数据时，在设置了过期时间的键空间中，有更早过期时间的key优先移除。

Redis的内存淘汰策略的选取并不会影响过期的key的处理。

内存淘汰策略用于处理内存不足时的需要申请额外空间的数据；过期策略用于处理过期的缓存数据。

3、常见缓存淘汰算法

FIFO（先入先出）

• FIFO (First In FIrst Out) 是最简单的算法，原理跟名字一样，“如果一个数据最先进入缓存中，则应该最早淘汰掉”。
• 把缓存中的数据看成一个队列，最先加入的数据位于队列的头部，最后加入位于队列的尾部。当缓存空间不足需要执行缓存淘汰操作时，从队列的头部开始淘汰。

LRU（最近最少被使用）

• LRU (Least Recently Used) 的核心思想是基于**“如果数据最近被访问过，它在未来也极有可能访问过”**。
• 同样把缓存看成一个队列，访问一个数据时，如果缓存中不存在，则插入到队列尾部；如果缓存中存在，则把该数据移动到队列尾部。当执行淘汰操作时，同样从队列的头部开始淘汰。
• Java 中可以直接使用 LinkedHashMap 来实现

LFU（最不经常使用）

• LFU （Least Frequently Used）的核心思想是**“如果一个数据在最近一段时间内使用次数很少，那么在将来一段时间内被使用的可能性也很小”**，会记录数据访问的次数，当需要进行淘汰操作时，淘汰掉访问次数最少的数据。
• 如果一开始 1 被连续访问了两次，接下来 2 被访问一次，3 被访问一次，按照访问次数排序，访问次数少的处于队列头部。当 4 加入时，执行缓存淘汰，2 位于队列头部被淘汰。

4、手写LRU

手写LRU是leetcode原题，同时也是我面试腾讯的一面面试真题，请务必会写！！！

4.1、题目描述

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。

• 获取数据 get(key) - 如果关键字 (key) 存在于缓存中，则获取关键字的值（总是正数），否则返回 -1。
• 写入数据 put(key, value) - 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字/值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

4.2 题解

LeetCode原题地址

LRU 缓存算法的核心数据结构就是哈希链表，双向链表和哈希表的结合体。

class LRUCache {
    // key -> Node(key, val)
    private HashMap<Integer, Node> map;
    // Node(k1, v1) <-> Node(k2, v2)...
    private DoubleList cache;
    // 最大容量
    private int cap;
    
    public LRUCache(int capacity) {
        this.cap = capacity;
        map = new HashMap<>();
        cache = new DoubleList();
    }
    
    public int get(int key) {
        if (!map.containsKey(key))
            return -1;
        int val = map.get(key).val;
        // 利用 put 方法把该数据提前
        put(key, val);
        return val;
    }
    
    public void put(int key, int val) {
        // 先把新节点 x 做出来
        Node x = new Node(key, val);
        
        if (map.containsKey(key)) {
            // 删除旧的节点，新的插到头部
            cache.remove(map.get(key));
            cache.addFirst(x);
            // 更新 map 中对应的数据
            map.put(key, x);
        } else {
            if (cap == cache.size()) {
                // 删除链表最后一个数据
                Node last = cache.removeLast();
                map.remove(last.key);
            }
            // 直接添加到头部
            cache.addFirst(x);
            map.put(key, x);
        }
    }

    //定义双向链表节点类 为了简化，key 和 val 都认为是 int 类型
    class Node{
        private int key,value;
        private Node prev, next;
        public Node(int key,int value){
            this.key = key;
            this.value = value;
        }
    }
    // Node 类型构建一个双链表，实现几个需要的 API 这些操作的时间复杂度均为 O(1)
    class DoubleList {  
    	private Node head, tail; // 头尾虚节点
    	private int size; // 链表元素数

    	public DoubleList() {
        	head = new Node(0, 0);
        	tail = new Node(0, 0);
        	head.next = tail;
        	tail.prev = head;
        	size = 0;
    	}

    // 在链表头部添加节点 x
    	public void addFirst(Node x) {
        	x.next = head.next;
        	x.prev = head;
        	head.next.prev = x;
        	head.next = x;
        	size++;
    	}

    // 删除链表中的 x 节点（x 一定存在）
    	public void remove(Node x) {
        	x.prev.next = x.next;
        	x.next.prev = x.prev;
        	size--;
    	}
    
    // 删除链表中最后一个节点，并返回该节点
   		public Node removeLast() {
        	if (tail.prev == head)
            	return null;
        	Node last = tail.prev;
        	remove(last);
        	return last;
    	}
    
    // 返回链表长度
   	 	public int size() { return size; }
	}

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97

末

我是一名后端开发工程师，个人公众号：任冬学编程

如果文章对你有帮助，不妨收藏，转发，在看起来~