基础数据结构

SDS

1
2
3
4
5
struct sdshdr {
    int len; // buf中已使用的字节数
    int free; // buf中未使用的字节数
    char buf[];
}

链表

  1. 包含头尾节点，head tail，以及链表长度计数器len
  2. 无环
  3. 多态：链表节点使用void*来保存节点值，可以支持各种不同类型的值

字典

属于k-v结构的映射表。

  1. 字典由两个哈希表构成，当字典处于redhash状态，ht[1]才有数据，当rehash完成之后，数据会全部复制到ht[0]
  2. 哈希表使用链地址法来解决冲突
  3. 采用渐进式rehash，并不是一次性，集中式完成，而是分多次、渐进式完成。rehash会与增删改等操作一起进行：

渐进式hash总结：

在扩容和收缩的时候，如果哈希字典中有很多元素，一次性将这些键全部rehash到ht[1]的话，可能会导致服务器在一段时间内停止服务。所以，采用渐进式rehash的方式，详细步骤如下：

  1. 为ht[1]分配空间，让字典同时持有ht[0]和ht[1]两个哈希表
  2. 将rehashindex的值设置为0，表示rehash工作正式开始
  3. 在rehash期间，每次对字典执行增删改查操作是，程序除了执行指定的操作以外，还会顺带将ht[0]哈希表在rehashindex索引上的所有键值对rehash到ht[1]，当rehash工作完成以后，rehashindex的值+1
  4. 随着字典操作的不断执行，最终会在某一时间段上ht[0]的所有键值对都会被rehash到ht[1]，这时将rehashindex的值设置为-1，表示rehash操作结束

渐进式rehash采用的是一种分而治之的方式，将rehash的操作分摊在每一个的访问中，避免集中式rehash而带来的庞大计算量。

需要注意的是在渐进式rehash的过程，如果有增删改查操作时，如果index大于**rehashindex，访问ht[0]，否则访问**ht[1]。

跳跃表

  • 是一种有序的数据结构，在每个节点中维持多个指向其他的节点指针，通过维持索引层，从而达到快速访问的目的。
  • 一定程度来讲，跳表是简化版的红黑树，平均复杂度为logn，差别是空间复杂度会

应用：有序集合、集群节点中用作内部数据结构

整数集合

整数集合是集合键（set）的实现之一，当集合都是整数，且数目不多时，会使用整数集合作为底层的实现。

1
2
3
4
5
typedef struct intset {
    uint32_t encoding;	// 表明了整数集合的类型，如int16 int32 int64
    uint32_t length;
    int8_t contents[];
}

注：当新增元素超过元素的可表示范围，会将已存储元素进行升级（比如原来是uint32，但是新增元素是uint64,，会把已存储元素都升级为uint64）。优势：

  1. 提供灵活性
  2. 节约内存

压缩列表

按照元素占用大小进行设计的数据结构，每个节点会有一个length字段，通过其可以计算出下一个节点的位置。不同于数组，这么做可以节省内存

应用：列表和哈希，都是其数据量少，且数据占用较小的时候，会使用该数据结构，不然就是链表和字典了。

基础数据类型

Redis是key-value数据库，key的类型只能是String，但是value的数据类型就比较丰富了，主要包括五种：

String：

  1. string类型是二进制安全的
  2. 一个键最大能存储512MB的数据，底层是简单动态字符串（SDS）：内部有个函数checkStringLength会对字符串进行校验，默认就是512MB，可以在配置文件中修改这个值

Hash

是一个键值(key=>value)对集合。 Redis hash是一个string类型的field和value的映射表，hash特别适合用于存储对象。底层使用压缩列表和字典

List

底层使用压缩列表和链表实现

Set

底层使整数集合和字典实现，key不允许重复

Sorted Set

有序集合，不允许重复。相对于set，支持按照score排序，key不允许重复，但是score允许重复，底层实现使用到了压缩列表和跳表

slot

在redis集群内部，采用slot槽位的逻辑管理方式， 集群内部共有16384(2的14次方)个Slot，集群内每个Redis Instance负责其中一部分的Slot的读写。一个Key到底属于哪个Slot，由分片算法：

crc16(key) % 16384

决定。也正是通过此分片算法，将不同的key以相对均匀的方式分配到不同的slot上。

watch：当执行多键值事务操作时，Redis不仅要求这些键值需要落在同一个Redis实例上，还要求落在同一个slot上。

官方介绍MULTI 、 EXEC 、 DISCARD 和 WATCH 是 Redis 事务相关的命令，事务可以一次执行多个命令，但是必须满足2个条件：

事务是一个单独的隔离操作：事务中的所有命令都会序列化、按顺序地执行。事务在执行的过程中，不会被其他客户端发送来的命令请求所打断。
事务是一个原子操作：事务中的命令要么全部被执行，要么全部都不执行。执行和是否成功是2个概念，并不是一个失败报错等，其他就失败。redis对事务是部分支持。如果最开始语法等就有提交错误，就相当于java的编译器都过不了，那么肯定全部不执行。如果在执行过程中报错，已经全部执行了，但是谁报错找谁，其他正常执行放行。各取所需！这里的事务并不是要么全部成功，要么全部失败，全部执行和全部成功（或者都失败）是2个概念。

hashtag

Hash Tag原理是：当一个key包含 {} 的时候，不对整个key做hash，而仅对 {}包括的字符串做hash。

Hash Tag可以让不同的key拥有相同的hash值，从而分配在同一个槽里；这样针对不同key的批量操作(mget/mset等)，以及事务、Lua脚本等都可以支持。不过Hash Tag可能会带来数据分配不均的问题，这时需要：(1)调整不同节点中槽的数量，使数据分布尽量均匀；(2)避免对热点数据使用Hash Tag，导致请求分布不均。

bigkey

  • 涉及到bigkey的操作，网卡会成为瓶颈
  • 若需要删除bigkey，直接del，被操作的实例可能会直接卡死
  • 业务上对bigkey取余，将数据分散，避免生成bigkey

高可用

主从复制

  1. 一台redis服务的数据，复制到多台redis服务器。前者称为主节点，后者为从节点
  2. 数据的复制是单向的，只能从主节点复制到从节点
  • 作用：
  1. 数据冗余：实现了数据的热备份，是持久化之外的数据冗余方式
  2. 故障恢复：主节点失效，丛节点提供服务
  3. 负载均衡：实现读写分离，主节点写，丛节点读
  4. 高可用的基础：主从复制是哨兵和集群模式能够实施的基础
  • 数据同步：
  1. 主从节点连接建立后，便开始数据同步。
  2. 根据主从节点当前状态，分为全量和部分复制
  3. 具体执行方式：从节点朝主节点发送psync命令，开始同步
  • 命令传播：
    主从数据同步完成后，主节点将自己执行的写命令发送给丛节点（该过程是异步的），保证数据的一致性。

哨兵

  1. 能够自动完成故障发现和转移，从而实现高可用
  2. 由一组哨兵节点和一组（或多组）主从复制节点组成
  • 心跳机制
  • 故障转移
  1. 每个 Sentinel 都会定时进行心跳检查，当发现主节点出现心跳检测超时的情况时，此时认为该主节点已经不可用，这种判定称为主观下线。
  2. 哨兵节点开始投票，当超过半数认为该主节点故障，会将其下线：基于raft算法，选取一个哨兵节点来执行该过程
  • 选取一个从节点作为主节点，将其他从节点和该节点绑定
  • 原来的主节点更新为从节点，对其监控，等恢复后，命令其去复制新的主节点

cluster集群

  1. 由多个主从复制的结构组成
  2. 每个主从复制的结构看做一个节点

持久化

RDB

优势：

  1. RDB 是一个非常紧凑（compact）的二进制文件，体积小，因此在传输速度上比较快，因此适合灾难恢复。
  2. 数据恢复速度比aof快

劣势：

  1. rdb出现故障丢的数据会比aof多。你通常会每隔5分钟或者更久做一次完整的保存,万一在 Redis 意外宕机,你可能会丢失几分钟的数据。
  2. rdb需要fork子进程来保存数据到硬盘，当数据集比较大时， fork比较耗时，从而导致redis主线程在一些毫秒级别内无法响应客户端

AOF

优势：

  1. 数据更完整，秒级丢失（无 fsync、每秒 fsync 、每次写的时候 fsync ）
  2. 兼容性高，是基于redis通讯协议而形成的命令追加方式，无论何种版本的redis都兼容，
  3. aof文件是明文的，可阅读性较好。

劣势：

  1. 数据文件大，即使有重写机制（合并命令、删减无用命令），但是同样量级还是比rdb占用大
  2. 数据恢复慢
  3. aof更吃性能（需要频繁同步命令，虽然会先写到内存中，再同步到磁盘里）

混合持久化

混合持久化结合了RDB持久化 和 AOF 持久化的优点, 由于绝大部分都是RDB格式，加载速度快，同时结合AOF，增量的数据以AOF方式保存了，数据更少的丢失。

分布式锁

redis分布式锁

redis实现分布式锁常见的有以很多，官方推荐下面的这种实现（也是我们目前的方式）

set命令加锁，lua脚本释放锁

1
SET key value NX PX milliseconds
  • key: 资源的key,标识一种资源。
  • value: 此值必须在所有进程和所有获取锁的请求中都是唯一的。
  • NX: 该命令仅在key不存在时才设置。
  • PX milliseconds: 过期时间,单位为毫秒。

这里的value,设置为唯一值，主要是为了释放锁，自己只能释放自己加的锁。注意在某些场景下，也可以不释放锁，因为本身设置了有效期。

释放锁一般是通过执行下面的lua脚本：

1
2
3
4
5
if redis.call("get",KEYS[1]) == ARGV[1] then
    return redis.call("del",KEYS[1])
else
    return 0
end

存在的问题：

对于Redis主节点与从节点之间的数据复制是异步复制的，当客户端发送写请求给master节点的时候，客户端会返回OK（这个时候A已经获得锁），然后同步到各个slave节点中。如果此时master还没来得及同步给slave节点时发生宕机，那么master内存中的数据会丢失（这样可能会导致B也能获得锁）。

redlock:

它的基本思路就是为锁准备多个独立的节点，在锁过期时间内只要超过半数获取到锁，就算成功，避免redis主从切换的时候，数据丢失。

  • 问题：
  1. 宕机重启后，两个客户端拿到同一把锁

假设5个节点是A, B, C, D, E，客户端1在A, B, C上面拿到锁，D, E没有拿到锁，客户端1拿锁成功。 此时，C挂了重启，C上面锁的数据丢失（假设机器断电，数据还没来得及刷盘）。客户端2去取锁，从C, D, E 3个节点拿到锁，A, B没有拿到（还被客户端1持有），客户端2也超过多数派，也会拿到锁

解决方案：延迟重启，等待ttl之后再重启。

  1. 时钟跳跃：是指系统时间发生了跳跃

时钟跳跃可能延迟重启机制失效，时钟跳跃可能导致机器挂了立马重启，从而出现上面的问题。时钟跳跃可能导致客户端拿到锁之后立马失效，跟服务器挂掉类似。基于自动过期机制，依然没有解决长时间的gc pause等问题带来的锁自动失效，从而带来的安全性问题

zookeeper分布式锁

  • 使用 ZK 的临时节点和有序节点，每个线程获取锁就是在 ZK 创建一个临时有序的节点，比如在 /lock/ 目录下
  • 创建节点成功后，获取 /lock 目录下的所有临时节点，再判断当前线程创建的节点是否是所有的节点的序号最小的节点
  • 如果当前线程创建的节点是所有节点序号最小的节点，则认为获取锁成功
  • 如果当前线程创建的节点不是所有节点序号最小的节点，则对节点序号的前一个节点添加一个事件监听。

redis zk对比

  • Zookeeper的分布式锁是客户端基于创建临时节点实现的，对于排他锁，每个客户端都尝试创建临时节点，但是只有一个客户端能成功创建，创建成功则相当于获取了锁。对于共享锁，则会按照一定的顺序队列创建带序号的临时节点并尝试获取锁（可以有多个客户端获取共享锁）。Redis的分布式锁则是通过创建一个从未创建过的key并设置其过期时间实现的，创建成功则获得了锁，并且客户端会在一定时间内循环获取锁，比较消耗服务器性能。
  • Zookeeper释放锁时，要么正常执行完业务逻辑后，事务主动释放，要么是检测到与客户端的会话失效后释放。Redis释放锁时，要么正常执行完业务逻辑后，事务主动释放，要么是键超时后释放锁。
  • 对于Redis的主从结构中出现的主服务器宕机情况（单点故障），客户端A已经获取到锁了，但是主服务器还没来得及将键复制到从服务器，并且从服务器晋升为了主服务器，这时客户端B也可以获取锁，锁互斥效果就失效了。可以使用RedLock解决，但是不建议，可以使用Zookeeper。
  • Redis性能更高。