windtreeland

Appearance

数据结构 ​

string ​

  • Redis 的字符串是动态字符串，是可以修改的字符串，内部结构实现上类似于 Java 的 ArrayList，采用预分配冗余空间的方式来减少内存的频繁分配，内部为当前字 符串实际分配的空间 capacity 一般要高于实际字符串长度 len。当字符串长度小于 1M 时， 扩容都是加倍现有的空间，如果超过 1M，扩容时一次只会多扩 1M 的空间。需要注意的是 字符串最大长度为 512M。
  • bitmap
  • incr
  • 源码: Redis 的字符串叫着「SDS」，也就是 Simple Dynamic String。它的结构是一个带长度信 息的字节数组。

list ​

  • Redis 的列表相当于 Java 语言里面的 LinkedList，注意它是链表而不是数组。
  • 慢操作
  • Redis 底层存储的还不是一个简单的 linkedlist，而是称之为 快速链表 quicklist 的一个结构
    • 首先在列表元素较少的情况下会使用一块连续的内存存储，这个结构是 ziplist，也即是 压缩列表。它将所有的元素紧挨着一起存储，分配的是一块连续的内存。当数据量比较多的 时候才会改成 quicklist。因为普通的链表需要的附加指针空间太大，会比较浪费空间，而且 会加重内存的碎片化。

set ​

hash ​

渐进式rehash 策略

zset ​

跳跃列表

应用 ​

分布式锁 ​

  • setnx + expire
  • 性能问题
    • 轮训cas方式，去抢锁
    • 基于redis的发布订阅，订阅redis的自身时间
  • 超时
    • 重复锁问题
      • Redis 分布式锁不要用于较长时间的任务。如果真的偶尔出现了，数据出现的小波错乱可能需要人工介入解决
      • watch dog 线程去续期
    • 有一个更加安全的方案是为 set 指令的 value 参数设置为一个随机数，释放锁时先匹配 随机数是否一致，然后再删除 key。但是匹配 value 和删除 key 不是一个原子操作，Redis 也 没有提供类似于 delifequals 这样的指令，这就需要使用 Lua 脚本来处理了，因为 Lua 脚本可 以保证连续多个指令的原子性执行。
  • 可重入性问题
    • 不推荐使用可重入锁，它加重了客户端的复杂性，在编写业务方法时注意在逻辑结构上进行调整完全可以不使用可重入锁
    • 使用hash set，多一个表示锁了多少次的字段，需要用lua保证过期时间的原则性
  • 单点故障问题
    • 高可用，使用哨兵->主从同步，会有延迟不一致，出现重复锁问题
    • 分片集群解决压力问题
    • redlock，红锁算法，实现是在client，性能可能还不如zk
      1. client连接x台相互独立的redis，过半通过的机制
      2. 并发抢锁失败，如每一个client都抢到一个锁，会进行retry
      3. retry会优化，有序抢锁，但还是可能发生 cap--p,

缓存问题 ​

  • 缓存穿透：redis & db 都没有
    1. set key null， 会有内存压力问题
    2. 布隆过滤器，将已存在的放入
  • 缓存击穿：redis 没有
  • 雪崩： 同时多个key redis没有
  • 热点key：分布式锁

双写一致性 ​

  1. 先写缓存，写数据库：不一致
  2. 先写数据库，写缓存：两个线程并发可能会导致不一致
  3. 先写数据库，删除缓存，一定带着过期时间：cache 不是强一致的，属于ap;或者加全局锁
  4. 先写数据库，canal同步：无法识别热点key，可能会导致加载全部；一般会加逻辑，mq，会有延迟

缓存存什么 ​

  1. 静态的字典类，纬度类数据
    1. 不要设置过期时间
    2. 淘汰策略设置成基于过期类数据的LRU/LFU
  2. 存热点数据
    1. 写扩散：写完数据库，就要写redis，已知未来一定会有并发产生，以及修改的是静态类字典数据
    2. 读扩散：read过程出现cache-misses，也要识别，redis 是cache应该存热数据

消息队列 ​

  1. 异步消息队列 Redis 的 list(列表) 数据结构常用来作为异步消息队列使用，使用rpush/lpush操作入队列， 使用 lpop 和 rpop 来出队列。

    可是如果队列空了，客户端就会陷入 pop 的死循环，不停地 pop，没有数据，接着再 pop， 又没有数据。这就是浪费生命的空轮询。空轮询不但拉高了客户端的 CPU，redis 的 QPS 也 会被拉高，如果这样空轮询的客户端有几十来个，Redis 的慢查询可能会显著增多。 通常我们使用 sleep 来解决这个问题，让线程睡一会，睡个 1s 钟就可以了。不但客户端 的 CPU 能降下来，Redis 的 QPS 也降下来了。

    • 队列延迟
      • 阻塞读在队列没有数据的时候，会立即进入休眠状态，一旦数据到来，则立刻醒过来。消息的延迟几乎为零。用 blpop/brpop 替代前面的 lpop/rpop，就完美解决了上面的问题
      • 空闲连接自动断开：Redis 的客户端连接就成了闲置连接，闲置过久，服务器一般会主动断开连接，减少闲置资源占用。这个时候 blpop/brpop 会抛出异常来。 所以编写客户端消费者的时候要小心，注意捕获异常，还要重试。

  2. 延时队列的实现

    • 延时队列可以通过 Redis 的 zset(有序列表) 来实现。我们将消息序列化成一个字符串作 为 zset 的 value，这个消息的到期处理时间作为 score，然后用多个线程轮询 zset 获取到期 的任务进行处理，多个线程是为了保障可用性，万一挂了一个线程还有其它线程可以继续处 理。因为有多个线程，所以需要考虑并发争抢任务，确保任务不能被多次执行。
    • Redis 的 zrem 方法是多线程多进程争抢任务的关键，它的返回值决定了当前实例有没有抢到任务， 因为 loop 方法可能会被多个线程、多个进程调用，同一个任务可能会被多个进程线程抢到，通过 zrem 来决定唯一的属主。
    • 同时，我们要注意一定要对 handle_msg 进行异常捕获，避免因为个别任务处理问题导致循环异常退出。
    • 可以考虑使用 lua scripting 来优化一下这个逻辑，将 zrangebyscore 和 zrem 一同挪到服务器端进行原子化操作，这样多个进程之间争抢任务时就不 会出现这种浪费了

位图 ​

  1. 统计和查找 Redis 提供了位图统计指令 bitcount 和位图查找指令 bitpos，bitcount 用来统计指定位 置范围内 1 的个数，bitpos 用来查找指定范围内出现的第一个 0 或 1 如果指定了范围参数[start, end]，就可以统计在某个时间范围内；start 和 end 参数是字节索引，也就是说指定的位范围必须是 8 的倍数， 而不能任意指定
  2. bitfield incrby 出现溢出，默认的处理是折返；bitfield 指令提供了溢出策略子指令 overflow，用户可以选择溢出行为，默认是折返 (wrap)，还可以选择失败 (fail) 报错不执行，以及饱和截断 (sat)，超过了范围就停留在最大 最小值。overflow 指令只影响接下来的第一条指令，这条指令执行完后溢出策略会变成默认 值折返 (wrap)。

HyperLogLog ​

它需要占据 一定 12k 的存储空间，所以它不适合统计单个用户相关的数据。

  1. HyperLogLog 提供了两个指令 pfadd 和 pfcount，网页每天的 UV 数据；HyperLogLog 除了 pfadd 和 pfcount 之外，还提供了第三个指令 pfmerge，用于 将多个 pf 计数值累加在一起形成一个新的 pf 值。
  2. HyperLogLog 实现原理
    1. 给定一系列的随机整数，我们记录下低位连续零位的最大长度 k，通 过这个 k 值可以估算出随机数的数量，N=2^K
    2. 如果 N 介于 2^K 和 2^(K+1) 之间，用这种方式估计的值都等于 2^K，这明显是不合 理的。这里可以采用多个 BitKeeper，然后进行加权估计，就可以得到一个比较准确的值。
    3. Redis 的 HyperLogLog 实现中用到的是 16384 个桶，也就是 2^14，每个桶的 maxbits 需要 6 个 bits 来存储，最 大可以表示 maxbits=63，于是总共占用内存就是 2^14 * 6 / 8 = 12k 字节

布隆过滤器 ​

简单限流 ​

zset 滑动窗口

漏斗限流 ​

GeoHash ​

Scan ​

  1. 用法
    1. 复杂度虽然也是 O(n)，但是它是通过游标分步进行的，不会阻塞线程;
    2. 提供 limit 参数，可以控制每次返回结果的最大条数，limit 只是一个 hint，返回的结果可多可少;
    3. 同 keys 一样，它也提供模式匹配功能;
    4. 服务器不需要为游标保存状态，游标的唯一状态就是 scan 返回给客户端的游标整数;
    5. 返回的结果可能会有重复，需要客户端去重复，这点非常重要;
    6. 遍历的过程中如果有数据修改，改动后的数据能不能遍历到是不确定的;
    7. 单次返回的结果是空的并不意味着遍历结束，而要看返回的游标值是否为零;
  2. 原理
    1. 字典的结构
      1. scan 指令返回的游标就是第一维数组的位置索引，我们将这个位置索引称为槽 (slot)。
      2. limit 参数就表示需要遍历的 槽位数，之所以返回的结果可能多可能少，是因为不是所有的槽位上都会挂接链表，有些槽位可能是空的，还有些槽位上挂接的链表上的元素可能会有多个。
    2. scan 遍历顺序 & 字典扩容 scan 的遍历顺序非常特别。它不是从第一维数组的第 0 位一直遍历到末尾，而是采用了高位进位加法来遍历。之所以使用这样特殊的方式进行遍历，是考虑到字典的扩容和缩容 时避免槽位的遍历重复和遗漏。
    3. 渐进式 rehash 对与 rehash 中的字典，它需要同时扫描新旧槽位，然后将结果融合后返回给客户端。
  3. 定位大 key Redis 官方已经在 redis-cli 指令中提供 了这样的扫描功能：
    shell
    # 如果你担心这个指令会大幅抬升 Redis 的 ops 导致线上报警，还可以增加一个休眠参数。
redis-cli -h 127.0.0.1 -p 7001 –-bigkeys
#下面这个指令每隔 100 条 scan 指令就会休眠 0.1s，ops 就不会剧烈抬升，但是扫描的时间会变长。
redis-cli -h 127.0.0.1 -p 7001 –-bigkeys -i 0.1

原理 ​

线程IO模型 ​

  • 事件轮询 (多路复用)

  • 定时任务

    Redis 的定时任务会记录在一个称为最小堆的数据结构中。这个堆中，最快要执行的任 务排在堆的最上方。在每个循环周期，Redis 都会将最小堆里面已经到点的任务立即进行处 理。处理完毕后，将最快要执行的任务还需要的时间记录下来，这个时间就是 select 系统调 用的 timeout 参数。因为 Redis 知道未来 timeout 时间内，没有其它定时任务需要处理，所以可以安心睡眠 timeout 的时间。

持久化 ​

快照原理 ​

  1. 快照是一次全量备份
  2. 快照是内存数据的二进制序列化形式，在存储上非常紧凑
  3. 多进程 COW(Copy On Write) 机制来实现快照持久化
    1. Redis 在持久化时会调用 glibc 的函数 fork 产生一个子进程，快照持久化完全交给子进 程来处理，父进程继续处理客户端请求。子进程刚刚产生时，它和父进程共享内存里面的代 码段和数据段。这时你可以将父子进程想像成一个连体婴儿，共享身体。这是 Linux 操作系统的机制，为了节约内存资源，所以尽可能让它们共享起来。在进程分离的一瞬间，内存的增长几乎没有明显变化。
    2. 当父进程对其中一个页面的数据进行修改时，会将被共享的页面复 制一份分离出来，然后对这个复制的页面进行修改。这时子进程相应的页面是没有变化的， 还是进程产生时那一瞬间的数据。

AOF ​

  1. AOF 日志是连续的增量备份
  2. AOF 日志记录的是内存数据修改的指令记录文本。AOF 日志在长期的运行过程中会变的无比庞大，数据库重启时需要加载 AOF 日志进行指令重放，这个时间就会无比漫长。 所以需要定期进行 AOF 重写，给 AOF 日志进行瘦身。
  3. fsync: Linux 的 glibc 提供了 fsync(int fd)函数可以将指定文件的内容强制从内核缓存刷到磁 盘。
  4. AOF 重写: Redis 提供了 bgrewriteaof 指令用于对 AOF 日志进行瘦身。其原理就是开辟一个子进 程对内存进行遍历转换成一系列 Redis 的操作指令，序列化到一个新的 AOF 日志文件中。 序列化完毕后再将操作期间发生的增量 AOF 日志追加到这个新的 AOF 日志文件中，追加完毕后就立即替代旧的 AOF 日志文件了，瘦身工作就完成了

混合持久化 ​

将 rdb 文 件的内容和增量的 AOF 日志文件存在一起。这里的 AOF 日志不再是全量的日志，而是自持久化开始到持久化结束的这段时间发生的增量 AOF 日志，通常这部分 AOF 日志很小

运维 ​

Redis 的主节点是不会进行持久化操作，持久化操作主要在从节点进行。从节点是备份节点，没有来自客户端请求的压力，它的操作系统资源往往比较充沛 但是如果出现网络分区，从节点长期连不上主节点，就会出现数据不一致的问题，特别是在网络分区出现的情况下又不小心主节点宕机了，那么数据就会丢失，所以在生产环境要做好实时监控工作，保证网络畅通或者能快速修复。另外还应该再增加一个从节点以降低网络分区的概率，只要有一个从节点数据同步正常，数据也就不会轻易丢失。

管道 ​

事务 ​

  • multi/exec/discard。multi 指示事务的开始，exec 指示事务的执行，discard 指示事务的丢弃。
  • 因为 Redis 的单线程特性，它不用担心自己在执行队列的时候被其它指令打搅，可以保证他们能得到的「原子性」执行。
    • 事务在遇到指令执行失败后，后面的指令还继续执行
    • Redis 的事务根本不能算「原子性」，而仅仅是满足了事务的「隔离性」，隔离性中的串行化——当前执行的事务有着不被其它事务打断的权利。
  • 优化: Redis 事务在发送每个指令到事务缓存队列时都要经过一次网络读写，当一个事务内部的指令较多时，需要的网络 IO 时间也会线性增长。所以通常 Redis 的客户端在执行 事务时都会结合 pipeline 一起使用，这样可以将多次 IO 操作压缩为单次 IO 操作
  • Watch: 乐观锁
    • watch 会在事务开始之前盯住 1 个或多个关键变量，当事务执行时，也就是服务器收到 了 exec 指令要顺序执行缓存的事务队列时，Redis 会检查关键变量自 watch 之后，是否被 修改了 (包括当前事务所在的客户端)。如果关键变量被人动过了，exec 指令就会返回 null 回复告知客户端事务执行失败，这个时候客户端一般会选择重试

消息多播 ​

缺点: PubSub 的生产者传递过来一个消息，Redis 会直接找到相应的消费者传递过去。如果一个消费者都没有，那么消息直接丢弃。如果开始有三个消费者，一个消费者突然挂掉了，生产者会继续发送消息，另外两个消费者可以持续收到消息。但是挂掉的消费者重新连上的时候，这断连期间生产者发送的消息，对于这个消费者来说就是彻底丢失了。 如果 Redis 停机重启，PubSub 的消息是不会持久化的，毕竟 Redis 宕机就相当于一个消费者都没有，所有的消息直接被丢弃。

小对象压缩 ​

  • ziplist
    • 如果它存储的是 hash 结构，那么 key 和 value 会作为两个 entry 相邻存在一起。
    • 如果它存储的是 zset，那么 value 和 score 会作为两个 entry 相邻存在一起。
  • Redis 的 intset 是一个紧凑的整数数组结构，它用于存放元素都是整数的并且元素个数 较少的 set 集合。Redis 支持 set 集合动态从 uint16 升级到 uint32， 再升级到 uint64。
  • 存储界限 当集合对象的元素不断增加，或者某个 value 值过大，这种小对象存储也会 被升级为标准结构
  • 内存回收机制
    • 如果当前 Redis 内存有 10G，当你删除了 1GB 的 key 后，再去观察内存，你会发现 内存变化不会太大。原因是操作系统回收内存是以页为单位，如果这个页上只要有一个 key 还在使用，那么它就不能被回收。Redis 虽然删除了 1GB 的 key，但是这些 key 分散到了 很多页面中，每个页面都还有其它 key 存在，这就导致了内存不会立即被回收。
    • 不过，如果你执行 flushdb，然后再观察内存会发现内存确实被回收了。原因是所有的 key 都干掉了，大部分之前使用的页面都完全干净了，会立即被操作系统回收。
  • 内存分配算法
    • Redis 为了保持自身结构的简单性，在内存分配这里直接做了甩手掌柜，将内存分配的 细节丢给了第三方内存分配库去实现。目前 Redis 可以使用 jemalloc(facebook) 库来管理内 存，也可以切换到 tcmalloc(google)。因为 jemalloc 相比 tcmalloc 的性能要稍好一些，所以 Redis 默认使用了 jemalloc。

主从同步 ​

  • CAP 原理
  • 最终一致: Redis 保证「最终一致性」，从节点会努力追赶主节点，最终从节点的状态会和主节点 的状态将保持一致。如果网络断开了，主从节点的数据将会出现大量不一致，一旦网络恢 复，从节点会采用多种策略努力追赶上落后的数据，继续尽力保持和主节点一致。
  • 增量同步:
    1. Redis 同步的是指令流，主节点会将那些对自己的状态产生修改性影响的指令记录在本 地的内存 buffer 中，然后异步将 buffer 中的指令同步到从节点，从节点一边执行同步的指 令流来达到和主节点一样的状态，一遍向主节点反馈自己同步到哪里了 (偏移量)。
    2. Redis 的复制内存 buffer 是一个定长的环形数组，如果数组内容满了，就会从头开始覆 盖前面的内容。
    3. 如果因为网络状况不好，从节点在短时间内无法和主节点进行同步，那么当网络状况恢 复时，Redis 的主节点中那些没有同步的指令在 buffer 中有可能已经被后续的指令覆盖掉 了，从节点将无法直接通过指令流来进行同步，这个时候就需要用到更加复杂的同步机制 — — 快照同步。
  • 快照同步
    1. 快照同步是一个非常耗费资源的操作，它首先需要在主库上进行一次 bgsave 将当前内 存的数据全部快照到磁盘文件中，然后再将快照文件的内容全部传送到从节点。从节点将快照文件接受完毕后，立即执行一次全量加载，加载之前先要将当前内存的数据清空。加载完毕后通知主节点继续进行增量同步
    2. 在整个快照同步进行的过程中，主节点的复制 buffer 还在不停的往前移动，如果快照同 步的时间过长或者复制 buffer 太小，都会导致同步期间的增量指令在复制 buffer 中被覆盖，这样就会导致快照同步完成后无法进行增量复制，然后会再次发起快照同步，如此极有可能会陷入快照同步的死循环。
  • 增加从节点: 当从节点刚刚加入到集群时，它必须先要进行一次快照同步，同步完成后再继续进行增量同步。
  • 无盘复制: 无盘复制是指主服务器直接通过套接字 将快照内容发送到从节点，生成快照是一个遍历的过程，主节点会一边遍历内存，一遍将序列化的内容发送到从节点，从节点还是跟之前一样，先将接收到的内容存储到磁盘文件中， 再进行一次性加载。
  • Wait 指令: Redis 的复制是异步进行的，wait 指令可以让异步复制变身同步复制，确保系统的强一致性 (不严格)。
  • Sentinel: 它负责持续监控主从节点的健康，当主节点挂掉时，自动选择一个最优的从节点切换为 主节点。客户端来连接集群时，会首先连接 sentinel，通过 sentinel 来查询主节点的地址， 然后再去连接主节点进行数据交互。当主节点发生故障时，客户端会重新向 sentinel 要地址，sentinel 会将最新的主节点地址告诉客户端。
  • 限制主从延迟过大:
    shell
      # 主节点必须至少有一个从节点在进行正常复制，否则就停止对外写服务，丧失可用性
  min-slaves-to-write 1
  # 它的单位是秒，表示如 果 10s 没有收到从节点的反馈，就意味着从节点同步不正常，要么网络断开了，要么一直没 有给反馈。
  min-slaves-max-lag 10

扩展 ​

  1. Info 指令
    1. Server 服务器运行的环境参数
    2. Clients 客户端相关信息
    3. Memory 服务器运行内存统计数据
    4. Persistence 持久化信息
    5. Stats 通用统计数据
    6. Replication 主从复制相关信息
    7. CPU CPU 使用情况
    8. Cluster 集群信息
    9. KeySpace 键值对统计数量信息
    shell
    # Redis 每秒执行多少次指令
redis-cli info stats |grep ops
# Redis 内存占用多大
redis-cli info memory | grep used | grep human
# 复制积压缓冲区多大
redis-cli info replication |grep backlog
  2. 过期
    • 定时删除
      • redis会将每个设置了过期时间的key放到一个独立的字典中，以后会定时遍历这个字典来删除到期的key。
      • 定时扫描策略:默认会每秒进行十次过期扫描，过期扫描不会遍历过期字典中所有的 key，而是采用了一种简单的贪心策略。
        1. 从过期字典中随机 20 个 key
        2. 删除这 20 个 key 中已经过期的 key;
        3. 如果过期的 key 比率超过 1/4，那就重复步骤 1;
        4. 同时，为了保证过期扫描不会出现循环过度，导致线程卡死现象，算法还增加了扫描时间的上限，默认不会超过 25ms。
    • 惰性删除: 客户端访问这个key的时候，redis对过期时间进行检查，如果过期来就立即删除
    • 从库的过期策略
  3. LRU
    1. 策略
      1. noeviction 不会继续服务写请求 (DEL 请求可以继续服务)，读请求可以继续进行。这样可以保证不会丢失数据，但是会让线上的业务不能持续进行。这是默认的淘汰策略。
      2. volatile-lru 尝试淘汰设置了过期时间的 key，最少使用的 key 优先被淘汰。没有设置过期时间的 key 不会被淘汰，这样可以保证需要持久化的数据不会突然丢失。
      3. volatile-random 跟上面一样，不过淘汰的 key 是过期 key 集合中随机的 key。
      4. allkeys-lru 区别于 volatile-lru，这个策略要淘汰的 key 对象是全体的 key 集合，而不只是过期的 key 集合。这意味着没有设置过期时间的 key 也会被淘汰。
      5. allkeys-random 跟上面一样，不过淘汰的策略是随机的 key。
    2. 近似 LRU 算法
      1. 之所以不使用 LRU算法，是因为需要消耗大量的额外的内存，需要对现有的数据结构进行较大的改造
      2. 给每个 key 增加了一个额外的小字段，这个字段的长度是 24 个 bit，也就是最后一次被访问的时间戳。
      3. 当 Redis 执行写操作时，发现内存超出 maxmemory，就会执行一次 LRU 淘汰算法。随机采样出 5(可以配置) 个 key，然后淘汰掉最旧的 key，如果淘汰后内存还是超出 maxmemory，那就继续随机采样淘汰，直到内存低于 maxmemory 为止。
      4. 淘汰池是一个数组，它的大小是 maxmemory_samples，在每一次淘汰循环中，新随机出 来的 key 列表会和淘汰池中的 key 列表进行融合，淘汰掉最旧的一个 key 之后，保留剩余 较旧的 key 列表放入淘汰池中留待下一个循环。
      5. volatile-ttl 跟上面一样，除了淘汰的策略不是 LRU，而是 key 的剩余寿命 ttl 的值，ttl越小越优先被淘汰。
  4. 异步
    • 删除指令 del 会直接释放对象的内存，大部分情况下，这个指令非常快，没有明显延迟。不过如果删除的 key 是一个非常大的对象，比如一个包含了千万元素的 hash，那么删 除操作就会导致单线程卡顿。Redis 为了解决这个卡顿问题，在 4.0 版本引入了 unlink 指令，它能对删除操作进行懒 处理，丢给后台线程来异步回收内存
    • Redis 提供了 flushdb 和 flushall 指令，用来清空数据库，这也是极其缓慢的操作。 Redis 4.0 同样给这两个指令也带来了异步化，在指令后面增加 async 参数就可以将整棵大树连根拔起，扔给后台线程慢慢焚烧。
    • AOF Sync 也很慢: Redis 需要每秒一次(可配置)同步 AOF 日志到磁盘，确保消息尽量不丢失，需要调用 sync 函数，这个操作会比较耗时，会导致主线程的效率下降，所以 Redis 也将这个操作移到 异步线程来完成。执行 AOF Sync 操作的线程是一个独立的异步线程，和前面的懒惰删除线程不是一个线程，同样它也有一个属于自己的任务队列，队列里只用来存放 AOF Sync 任务。