Redis

Redis相关知识

待进一步完善

Posted by ZBX on March 11, 2020

原理

  • 纯内存操作
  • 单线程操作，避免了频繁的上下文切换，单线程指的是网络请求模块使用了一个线程，即一个线程处理所有网络请求，其他模块仍用了多个线程。（单线程的缺点？？）
  • 采用了非阻塞 I/O 多路复用机制
  • 使用了epoll，epoll中的读、写、关闭、连接都转化成了事件

数据类型

  • String
    • 一个可变的字节数组，String是动态字符串
  • Hash
    • 底层类似Java的HashMap
  • List
    • 存储结构是双向链表。但不是简单的双向链表，是称之为快速链表quicklist，首先在列表元素较少的情况下会使用一块连续的内存存储，这个结构是ziplist，也即是压缩列表。它将所有的元素紧挨着一起存储，分配的是一块连续的内存。当数据量比较多的时候才会改成quicklist。
    • rpush/rpop/lpush/lpop
  • Set
    • 底层同Hash结构，和Java 的HashSet一样，所有的value都指向同一个内部值。
  • Zset
    • 有序集合SortedSet
    • 给每一个元素value赋予一个权重score，另一方面它又类似于TreeSet，内部的元素会按照权重score进行排序，可以得到每个元素的名次，还可以通过score的范围来获取元素的列表。
    • 底层实现使用了Hash和跳表，Hash的作用就是关联元素value和权重score，可以通过元素value找到相应的score值。跳表给元素value排序，根据score的范围获取元素列表。
    • 跳表是基于多指针有序链表实现的，可以看成多个有序链表，是可以实现二分查找的有序链表
    • 命令集
    • zadd命令：添加元素，支持添加多个元素。如果元素存在，则修改score值。
    • zincrby命令：给一个元素的score加上一个值（可以是负数/浮点数）
    • zrem命令：删除元素，支持删除多个。
    • zrank命令：获取元素在有序集合中的排名，根据score从小到大的排名，下标从0开始。
    • zrevrank命令：同zrank，只是z的排序是从大到小
    • zrange命令：获取指定区间（下标的区间）的元素，下标可以是负数。score是从小到大排序。
    • zrevrange命令：同zrange命令，只是score的排序是从大到小
    • zrangebyscore命令：获取score的值在某个区间的元素
    • zcount命令：获取score值在某个区间的元素的数量。
    • zcard命令：获取集合的元素的总数
    • zscore命令：获取元素的score值。
    • zremrangebyrank命令：删除排名在某个区间的元素：
    • zremrangebyscore命令：删除score值在某个区间的元素：

底层数据结构

  • SDS（简单动态字符串）

    • struct sdshdr{
	int len;
    int free; //未使用字节的数量
    char buf[];
}
      • 常数复杂度获取字符串长度
      • 杜绝缓冲区溢出
      • 减少修改字符串的内存重新分配次数
      • 二进制安全
      • 兼容部分c字符串函数
    • SDS除了保存数据库中字符串以外，SDS还可以作为缓冲区（buffer）：包括 AOF 模块中的AOF缓冲区以及客户端状态中的输入缓冲区。

  • 链表 （双向链表）

c typedef struct listNode{ //前置节点 struct listNode prev; //后置节点 struct listNode *next; //节点的值 void *value;
}listNode; typedef struct { listNode *head; listNode *tail; unsigned long len; void *(dup) (void ptr); //节点值复制函数 void *(free) (void ptr); //节点值释放函数 int (match) (void * ptr, void *key); //节点值对比函数 }list;

多态：链表节点使用 void* 指针来保存节点值，可以保存各种不同类型的值。

  • 字典

    • dictht是一个散列表结构，使用拉链法解决哈希冲突

    • typedef struct dictht {
    dictEntry **table;  //哈希表数组
    unsigned long size; //哈希表大小
    unsigned long sizemask; //哈希表大小掩码，用于计算索引值, 等于size-1
    unsigned long used;   //该哈希表已有节点的数量
} dictht;
typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;
typedef struct dict {
    dictType *type;
    void *privdata;
      dictht ht[2];
      long rehashidx; /* rehashing not in progress if rehashidx == -1 */
      unsigned long iterators; /* number of iterators currently running */
  } dict;

      • 解决哈希冲突：链地址法

      • 扩容和收缩：当哈希表保存的键值对太多或者太少时，就要通过 rerehash(重新散列）来对哈希表进行相应的扩展或者收缩

      • 触发扩容的条件：

        　　　1. 服务器目前没有执行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且负载因子大于等于1。

        1. 服务器目前正在执行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且负载因子大于等于5。ps：负载因子 = 哈希表已保存节点数量 / 哈希表大小。

      • 渐近式 rehash

        • Redis 的字典 dict 中包含两个哈希表 dictht，这是为了方便进行 rehash 操作。在扩容时，将其中一个 dictht 上的键值对 rehash 到另一个 dictht 上面，完成之后释放空间并交换两个 dictht 的角色。
        • 渐进式 rehash 通过记录 dict 的 rehashidx 完成，它从 0 开始，然后每执行一次 rehash 都会递增。例如在一次 rehash 中，要把 dict[0] rehash 到 dict[1]，这一次会把 dict[0] 上 table[rehashidx] 的键值对 rehash 到 dict[1] 上，dict[0] 的 table[rehashidx] 指向 null，并令 rehashidx++。
        • 在 rehash 期间，每次对字典执行添加、删除、查找或者更新操作时，都会执行一次渐进式 rehash。采用渐进式 rehash 会导致字典中的数据分散在两个 dictht 上，因此对字典的查找操作也需要到对应的 dictht 去执行

  • 跳跃表

    • typedef struct zskiplistNode {
	// 后退指针
	strcut zskiplistNode *backward;
	// 分值
	double score;
	// 成员对象
	robj *obj;
	// 层
	struct zskipistLevel {
		// 前进指针
		strcut zskiplistNode *forward;
		// 跨度
		unsigned int span;
	} level[];
} zskiplistNode;
typedef struct zskiplist{
     //表头节点和表尾节点
     structz skiplistNode *header, *tail;
     //表中节点的数量
     unsigned long length;
     //表中层数最大的节点的层数
     int level;
     
}zskiplist;

    • 空间复杂度O(n)，查询、插入、删除的时间复杂度为O(log n)，支持范围查询

    • 跳表是有序集合的底层实现之一，由zskiplist和zskiplistNode两个结构组成，其中zskiplist用于保存跳跃表信息（表头节点、表尾节点、长度），每个节点的层高都是1至32之间的随机数。

    • 搜索：从最高层的链表节点开始，如果比当前节点要大和比当前层的下一个节点要小，那么则往下找，也就是和当前层的下一层的节点的下一个节点进行比较，以此类推，一直找到最底层的最后一个节点，如果找到则返回，反之则返回空。

    • 插入：首先确定插入的层数，有一种方法是假设抛一枚，如果是证明就累加，直到遇见反面为止，最后记录正面的次数作为插入的层数。当确定插入的层数k后，则需要将新元素插入到底层到k层。

    • 删除：在各层中找到包含指定值的节点，然后将节点从链表中删除即可，如果删除以后只剩下头尾节点，则删除这一层

  • 整数集合

    • 整数集合作为集合键的底层实现之一，通过数组实现，这个数组以有序、无重复的方式保存集合元素，在有需要时，程序会根据新添加元素的类型，改变这个数组的类型。

    • typedef struct intset {
	uint32_t encoding;
	uint32_t length;
	int8_t contents[];
}intset;
    • 当我们新增的元素类型比原集合元素类型的长度要大时，需要对整数集合进行升级，才能将新元素放入整数集合中。

  • 压缩列表

    • 压缩列表是列表键和哈希键的底层实现之一，当一个列表键只包含少量列表项，并且每个列表项要么就是小整数值，要么就是长度比较短的字符串。

    • 会使用到ziplist的数据结构是Hash与List

    • Hash结构使用ziplist作为底层存储的两个条件是:

      1. 所有的键与值的字符串长度都小于64字节的时候
      2. 键与值对数据小于512个
    • 字节数 表尾节点距离起始地址的字节数 节点数量 各个节点 OxFF，标记末端
      zlbytes zltail zllen entryX zlend

      压缩列表的每个节点构造如下：

      previous_entry_length encoding content

  • 对象的类型和编码

    • typedef struct redisObject {    
	unsigned type:4;        // 对象的类型    
    unsigned encoding:4;    // 对象的编码    
    unsigned lru:LRU_BITS;  // LRU类型    
    int refcount;           // 引用计数    
    void *ptr;              // 指向底层数据结构的指针
} robj;

    • type 包含：string 、list、hash、set、zset

    • encoding

      • 字符串对象的编码可以是int，raw或者embstr。

        1. int 编码：保存的是可以用 long 类型表示的整数值。

        　2. raw 编码：保存长度大于44字节的字符串（redis3.2版本之前是39字节，之后是44字节）。

        　3. embstr 编码：保存长度小于44字节的字符串（redis3.2版本之前是39字节，之后是44字节）。

      • 列表对象的编码可以是 ziplist(压缩列表) 和 linkedlist(双端链表)

        • 当同时满足下面两个条件时，使用ziplist（压缩列表）编码：
          1. 列表保存元素个数小于512个
          2. 每个元素长度小于64字节

      • 哈希对象的编码可以是 ziplist 或者 hashtable。

        • 当同时满足下面两个条件时，使用ziplist（压缩列表）编码：
          1. 列表保存元素个数小于512个
          2. 每个元素长度小于64字节

      • 集合对象的编码可以是 intset 或者 hashtable。

        • 当集合同时满足以下两个条件时，使用 intset 编码：
          1. 集合对象中所有元素都是整数
            1. 集合对象所有元素数量不超过512

      • 有序集合的编码可以是 ziplist 或者 skiplist。

        • 当有序集合对象同时满足以下两个条件时，对象使用 ziplist 编码：

        　　1. 保存的元素数量小于128；

        　　2. 保存的所有元素长度都小于64字节。

        • typedef struct zset{
     //跳跃表
     zskiplist *zsl;
     //字典
     dict *dice;
} zset;

    • refcount（引用计数）

      • 内存回收
        • 引用计数有循环依赖的问题，对象会一直驻留在内存中，造成内存泄露。Redis通过maxmemory-policy解决该问题，即淘汰机制。
      • 内存共享
        • Redis的共享对象目前只支持整数值的字符串对象，判断两个对象是否相等却需要消耗额外的时间

    • lru

      • 记录了对象最后一次被命令程序访问的时间

为什么Redis选择使用跳表而不是红黑树来实现有序集合?

Redis 中的有序集合(zset) 支持的操作：

  1. 插入一个元素
  2. 删除一个元素
  3. 查找一个元素
  4. 有序输出所有元素
  5. 按照范围区间查找元素

其中，前四个操作红黑树也可以完成，且时间复杂度跟跳表是一样的。但是，按照区间来查找数据这个操作，红黑树的效率没有跳表高。按照区间查找数据时，跳表可以做到 O(logn) 的时间复杂度定位区间的起点，然后在原始链表中顺序往后遍历就可以了，非常高效。

特性

  • 持久化
    • RDB持久性以指定的时间间隔执行数据集的时间点快照。
      • 优点
        • RDB最大限度地提高了Redis性能，因为为了保持Redis父进程所需做的惟一工作就是创建一个将完成所有其余工作的子进程。父实例永远不会执行磁盘I/O或类似的操作。
        • 与AOF相比，RDB允许对大数据集进行更快的重启。
      • 缺点
        • 断电后，不能最小化数据丢失，最新的数据容易丢失
        • RDB利用fork()产生子进程来做持久化存储，但是数据集很大时，fork()可能会很耗时。AOF同样需要fork()，但是可以调整重写日志的频率。
    • AOF持久性记录服务器接收到的每个写入操作，这些操作将在服务器启动时重放，重新构建原始数据集。命令使用与Redis协议本身相同的格式记录，以append-only的方式记录。当日志变得太大时，Redis能够在后台重写日志。
      • 缺点
        • 对于相同的数据集，AOF文件通常比等效的RDB文件大。
    • RDB-AOF混合持久化
      • 当开启混合持久化时，主进程先fork出子进程将现有内存副本全量以RDB方式写入aof文件中，然后将缓冲区中的增量命令以AOF方式写入aof文件中，写入完成后通知主进程更新相关信息，并将新的含有 RDB和AOF两种格式的aof文件替换旧的aof文件。
  • 事务
    • Redis通过MULTI、EXEC、WATCH等命令来实现事务功能。
  • Lua脚本

Redis 与 Memcached区别

  • 分布式
    • Memcached 不支持分布式，只能通过在客户端使用一致性哈希来实现分布式存储，这种方式在存储和查询时都需要先在客户端计算一次数据所在的节点。
    • Redis Cluster 实现了分布式的支持。
  • 数据类型
    • Memcached 支持String，二进制类型（新版增加）。Redis支持String、List、Set、Hash、ZSet。
  • 内存管理
    • Memcached 将内存分割成特定长度的块来存储数据，以完全解决内存碎片的问题。但是这种方式会使得内存的利用率不高。
  • 持久化
    • Memcached没有持久化，Redis有RDB和AOF。
  • 查询操作
    • Redis支持批量操作还有事务支持，不同类型的CRUD。
  • 网络IO模型
    • Redis单线程

使用场景

  • 分布式锁实现
  • 消息队列
  • 会话缓存
  • 查找表
  • 计数器
  • 缓存

数据淘汰策略

  1. volatile-lru：从已设置过期时间的数据集（server.db[i].expires）中挑选最近最少使用的数据淘汰
  2. volatile-ttl：从已设置过期时间的数据集（server.db[i].expires）中挑选将要过期的数据淘汰
  3. volatile-random：从已设置过期时间的数据集（server.db[i].expires）中任意选择数据淘汰
  4. allkeys-lru：当内存不足以容纳新写入数据时，在键空间中，移除最近最少使用的key（这个是最常用的）
  5. allkeys-random：从数据集（server.db[i].dict）中任意选择数据淘汰
  6. no-eviction：禁止驱逐数据，也就是说当内存不足以容纳新写入数据时，新写入操作会报错。这个应该没人使用吧！

4.0版本后增加以下两种：

  1. volatile-lfu：从已设置过期时间的数据集(server.db[i].expires)中挑选最不经常使用的数据淘汰
  2. allkeys-lfu：当内存不足以容纳新写入数据时，在键空间中，移除最不经常使用的key

缓存穿透，缓存击穿，缓存雪崩解决方案分析

缓存穿透

缓存穿透是指查询一个一定不存在的数据，由于缓存是不命中时被动写的，并且出于容错考虑，如果从存储层查不到数据则不写入缓存，这将导致这个不存在的数据每次请求都要到存储层去查询，失去了缓存的意义。在流量大时，可能DB就挂掉了，要是有人利用不存在的key频繁攻击我们的应用，这就是漏洞。

解决方案

有很多种方法可以有效地解决缓存穿透问题，最常见的则是采用布隆过滤器，将所有可能存在的数据哈希到一个足够大的bitmap中，一个一定不存在的数据会被 这个bitmap拦截掉，从而避免了对底层存储系统的查询压力。另外也有一个更为简单粗暴的方法（我们采用的就是这种），如果一个查询返回的数据为空（不管是数 据不存在，还是系统故障），我们仍然把这个空结果进行缓存，但它的过期时间会很短，最长不超过五分钟。

缓存雪崩

缓存雪崩是指在我们设置缓存时采用了相同的过期时间，导致缓存在某一时刻同时失效，请求全部转发到DB，DB瞬时压力过重雪崩。

解决方案

缓存失效时的雪崩效应对底层系统的冲击非常可怕。大多数系统设计者考虑用加锁或者队列的方式保证缓存的单线 程（进程）写，从而避免失效时大量的并发请求落到底层存储系统上。这里分享一个简单方案就时讲缓存失效时间分散开，比如我们可以在原有的失效时间基础上增加一个随机值，比如1-5分钟随机，这样每一个缓存的过期时间的重复率就会降低，就很难引发集体失效的事件。

事前：尽量保证整个 redis 集群的⾼可⽤性，发现机器宕机尽快补上。选择合适的内存淘汰策略。 事中：本地ehcache缓存 + hystrix限流&降级，避免MySQL崩掉 事后：利⽤ redis 持久化机制保存的数据尽快恢复缓存。

缓存击穿

对于一些设置了过期时间的key，如果这些key可能会在某些时间点被超高并发地访问，是一种非常“热点”的数据。这个时候，需要考虑一个问题：缓存被“击穿”的问题，这个和缓存雪崩的区别在于这里针对某一key缓存，前者则是很多key。

缓存在某个时间点过期的时候，恰好在这个时间点对这个Key有大量的并发请求过来，这些请求发现缓存过期一般都会从后端DB加载数据并回设到缓存，这个时候大并发的请求可能会瞬间把后端DB压垮。

解决方案

我们的目标是：尽量少的线程构建缓存(甚至是一个) + 数据一致性 + 较少的潜在危险

事件

文件事件

Redis 基于 Reactor 模式开发了自己的网络事件处理器，使用 I/O 多路复用程序来同时监听多个套接字，并将到达的事件传送给文件事件分派器，分派器会根据套接字产生的事件类型调用相应的事件处理器。

时间事件

服务器有一些操作需要在给定的时间点执行，时间事件是对这类定时操作的抽象。

时间事件又分为：

  • 定时事件：是让一段程序在指定的时间之内执行一次；

  • 周期性事件：是让一段程序每隔指定时间就执行一次。

Redis 将所有时间事件都放在一个无序链表中，通过遍历整个链表查找出已到达的时间事件，并调用相应的事件处理器。

FEATURED TAGS
Ethereum EVM BlockChain Security 翻译 SGX Smart Contract MySQL Redis Java 面试 Spring
FRIENDS