分布式面试【Redis】

关注“Java后端技术全栈”

回复“面试”获取最新资料

回复“加群”邀您进技术交流群

Redis知识整理

1. String 的内部结构及实现原理

Redis 是 C 语言实现的，但是 C 语言中的字符串无法满足 Redis 复杂需求，Redis 自己定义了一种名为 简单动态字符串 simple dynamic string，SDS 的结构体。

内部结构最好扫一眼源码看看，打开 sds.h：

typedef char *sds;

/* Note: sdshdr5 is never used, we just access the flags byte directly.
* However is here to document the layout of type 5 SDS strings. */
struct __attribute__ ((__packed__)) sdshdr5 {
   unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
   char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
   uint8_t len; /* used */
   uint8_t alloc; /* excluding the header and null terminator */
   unsigned char flags; /* 3 lsb of type, 5 unused bits */
   char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
   uint16_t len; /* used */
   uint16_t alloc; /* excluding the header and null terminator */
   unsigned char flags; /* 3 lsb of type, 5 unused bits */
   char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
   uint32_t len; /* used */
   uint32_t alloc; /* excluding the header and null terminator */
   unsigned char flags; /* 3 lsb of type, 5 unused bits */
   char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
   uint64_t len; /* used */
   uint64_t alloc; /* excluding the header and null terminator */
   unsigned char flags; /* 3 lsb of type, 5 unused bits */
   char buf[];
};

可以看到定义了五种不同的结构体 sdshdr5、sdshdr8、sdshdr16、sdshdr32、sdshdr64。

以 sdshdr8 为例来讲解下：

• sds 是 simple dynamic string 的缩写

• hdr 是 header 的缩写。

• 8 表示给字符串分配的长度是 2^8 - 1 =255。

• 根据字符串的不同长度选择不同的 sdshdr。

• 注意 sdshdr5 在实际中未使用。

sdshdr8 内部的变量又都是什么含义呢，加上中文注释？

struct __attribute__ ((__packed__)) sdshdr8 {
   uint8_t len; /* 实际字符串占用长度 */
   uint8_t alloc; /* 分配的空间长度 */
   unsigned char flags; /* 区分是 sdshdr8 还是 sdshdr16 ...... */
   char buf[];/* 存放的位置 */
};

以字符串 HelloWorld 为例，长度 < 255，选择了 sdshdr8：

• len = 10

• alloc = 255

• flags = 1

• buf[] 指向具体位置

flag = 1 是一件很迷惑人的事，原理是什么？

一共有 5 种结构体，取的二进制来区分不同类型：

二进制	具体类型
000	sdshdr5
001	sdshdr8
010	sdshdr16
011	sdshdr32
100	sdshdr64

代码内部根据不同情况使用不同的 sdshdr，于是下面的 case-when 随处可见：

   switch(type&SDS_TYPE_MASK) {
       case SDS_TYPE_5:
           return sizeof(struct sdshdr5);
       case SDS_TYPE_8:
           return sizeof(struct sdshdr8);
       case SDS_TYPE_16:
           return sizeof(struct sdshdr16);
       case SDS_TYPE_32:
           return sizeof(struct sdshdr32);
       case SDS_TYPE_64:
           return sizeof(struct sdshdr64);

Redis 作为一个缓存中间件，最重要的就是读取数据的速度。更简单的说法就是尽量不要每次修改字符串，就重新申请释放内存空间，这点 C 语言原生的字符串做不到，sds 可以做到。

buf 的内存分配策略如下：

• 当 SDS 的 len 属性长度小于 1 MB 时，Redis 会分配 2*len 的空间。短期你再使用时，如果不超过 len，不必申请内存。

• 当 SDS 的 len 属性长度大于 1 MB 时，Redis 会分配 len+1 MB 的空间。这时候翻倍的代价太大，就预留 1 MB。

内存回收策略如下：

• Redis 的内存回收采用惰性回收，空闲先不释放，免得你一会用时还得分配，折腾内存，折腾内存就是折腾自己。

#define SDS_MAX_PREALLOC (1024*1024)

sds sdsMakeRoomFor(sds s, size_t addlen) {
......
   if (newlen < SDS_MAX_PREALLOC)
       newlen *= 2;
   else
       newlen += SDS_MAX_PREALLOC;
......
}

2. List 的内部结构及实现原理

List 老版本是 ZipList 和 LinkedList 切换，二者总是取其一，后来两者相结合的实现方式。

打开源码文件 quicklist.h，quicklist 有 head 和 tail 首尾指针，是一个双向链表，也就是 LinkedList，内部节点是 quicklistNode。

typedef struct quicklist {
   quicklistNode *head;
   quicklistNode *tail;
   unsigned long count;        /* total count of all entries in all ziplists */
   unsigned long len;          /* number of quicklistNodes */
   int fill : 16;              /* fill factor for individual nodes */
   unsigned int compress : 16; /* depth of end nodes not to compress;0=off */
} quicklist;

quicklistNode 除了前后指针，还有一些压缩信息，也就是 ZipList。

typedef struct quicklistNode {
   struct quicklistNode *prev;
   struct quicklistNode *next;
   unsigned char *zl;
   unsigned int sz;             /* ziplist size in bytes */
   unsigned int count : 16;     /* count of items in ziplist */
   unsigned int encoding : 2;   /* RAW==1 or LZF==2 */
   unsigned int container : 2;  /* NONE==1 or ZIPLIST==2 */
   unsigned int recompress : 1; /* was this node previous compressed? */
   unsigned int attempted_compress : 1; /* node can't compress; too small */
   unsigned int extra : 10; /* more bits to steal for future usage */
} quicklistNode;

疑问：为什么 quicklistNode 也有 count 属性？

答：因为一个 quicklistNode 会包含多个元素。

疑问：为什么要用双向链表？

答：因为提供了 LPOP、RPOP 这类左侧入队出队，右侧入队出队这样的操作。

疑问：为什么要用压缩链表？

答：ZipList 使用的连续内存，存储效率高，这样又不利于修改，所以和双向链表结合最好。而且压缩链表不益太长，所以，最合理的方案，就是每个节点用压缩链表，整体用双向链表。

3. Map 的内部结构及实现原理

Redis 的 map 使用了两种实现方式，数据量很小使用前面写过的 ZipList，数据量大使用 HashTable，读到这有没有一种感觉，Redis 底层总是采用多个数据结构来切换、结合使用，没有最好的数据结构，只有最适合它的场景。

熟悉 Java 的人一定会记得 HashMap 是标准的散列表 = 数组 + 链表，key 通过 hash 取模定位到数组的索引上，如果冲突加入链表，当然后续优化还有红黑树，Redis 没用树，我们这里也不提它。

打开源码文件 dict.h，dictht 就是 HashMap 的数组。

typedef struct dictht {
   dictEntry **table;
   unsigned long size;
   unsigned long sizemask;
   unsigned long used;
} dictht;

dictEntry 是每个节点，它包含 key 和 val，同时 next 指针表明它就是那个链表。

typedef struct dictEntry {
   void *key;
   union {
       void *val;
       uint64_t u64;
       int64_t s64;
       double d;
  } v;
   struct dictEntry *next;
} dictEntry;

前面两个结构已经可以实现 HashMap 了，但是 Hash 还有一些复杂的操作，比如扩容、缩容，这些操作由 dict 辅助完成。

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;

4. Set 的内部结构及实现原理

打开源码文件 inset.h：

typedef struct intset {
   uint32_t encoding;
   uint32_t length;
   int8_t contents[];
} intset;

编码、长度、数组，intset 可以说就是一个简单的整形数组。

我不说，你也会猜到，底层依然是两种数据结构，如果都是整数就用 inset，如果还有其他类型就用 hashtable。

特殊：inset 是排序的，从小到大排列。

数组最重要的就是扩容。

5. SortedSet 的内部结构及实现原理

排序：

前面 inset 是根据大小排序的，条件是元素都是整数，那 SortedSet 可以存储所有元素，如何比较大小呢？答案是分数，用户存入元素时，需要指定分数，也就是说用户告诉 SortedSet 怎么排序。

底层实现：

依然是多种数据结构，ziplist 或者 skiplist + hashtable，这里主要讲讲跳跃表 skiplist。

跳跃表：

顾名思义，可以跳着遍历链表。我们知道链表的缺点是遍历时只能一个一各遍历，哪怕是排序的，也没法像数组那样使用索引访问，毕竟链表的空间不是连续的。

跳跃表很抽象，需要看图帮助大家理解一下：

说白了，一些节点不只一个 next 指针，链表内部一些不挨着的节点可以通过指针连接在一起。最层面即 level = 1 的链表节点是最全面的。

打开源码文件 server.h，可以看到三个定义。

• dict 这个字典是辅助 API 功能的，zscore 通过元素得到对应的分数。

• zskiplist 就是跳跃表的实现。

typedef struct zset {
   dict *dict;
   zskiplist *zsl;
} zset;

跳跃表定义了首尾节点、链表长度、层数。这里的层数表示跳跃表的最大层数，层数的概念需要解释下：

• level = 1 的节点

• level = 2 的节点

• level = 3 的节点

typedef struct zskiplist {
   struct zskiplistNode *header, *tail;
   unsigned long length;
   int level;
} zskiplist;    

跳跃表的节点，这个节点可以有多个 level，所以这里用数组定义 level。

typedef struct zskiplistNode {
   sds ele;
   double score;
   struct zskiplistNode *backward;
   struct zskiplistLevel {
       struct zskiplistNode *forward;
       unsigned long span;
  } level[];
} zskiplistNode;

那么一个节点，到底需要多少个 level 呢？数据分布并不均匀，跳跃表采用随机算法定义一个节点的 level。

/* Returns a random level for the new skiplist node we are going to create.
* The return value of this function is between 1 and ZSKIPLIST_MAXLEVEL
* (both inclusive), with a powerlaw-alike distribution where higher
* levels are less likely to be returned. */
int zslRandomLevel(void) {
   int level = 1;
   while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
       level += 1;
   return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

6. Redis 有 timeout 机制，请问到了过期时间，数据是否真的被删除了？

答案是：不一定。

Redis 针对删除有两种机制：

• 消极方法（passive way）：在主键被访问时如果发现它已经失效，那么就删除它。

• 积极方法（active way）：周期性地从设置了失效时间的主键中选择一部分失效的主键删除

对于那些从未被查询的 key，即便它们已经过期，被动方式也无法清除。因此 Redis 会周期性地随机测试一些 key，已过期的 key 将会被删掉。Redis 每秒会进行 10 次操作，具体的流程：

1. 随机测试 20 个带有 timeout 信息的 key

2. 删除其中已经过期的 key

也就是说了，无论是消极方法还是消极方法，到了过期时间，数据依然可能还在。只是逻辑上访问不到，对用户来说和删除了一样。

7. Redis 的持久化机制

两种方式：

• RDB：全量备份。当符合条件时，Redis fork 一个子线程，数据写入临时文件，生成 dump.rdb。不会对主进程操作影响。

• AOF：增量事务日志，记录每次的操作。

RDB 文件大，备份频率不可能太高，AOF 文件小，但是小文件太多，数据恢复会非常慢。

所以，需要二者结合，定期 RDB，然后两次的 RDB 之间使用 AOF。

8. Redis 是单进程单线程？性能为什么这么快

单线程和多线程：

多线程解决的什么问题，对多核 CPU 的利用，但是 Redis 官方提到，Redis 的瓶颈不是 CPU，而是内存和网络。这样使用单线程，并不影响速度，反而因为没有多线程的上下文频繁的切换，提高了性能。

内存：

Redis 把数据都加载到内存中，后续操作都在内存中，也是速度快的一个原因。

IO 多路复用：

IO 多路复用也叫异步阻塞 IO。多路是指多个网络连接，复用是指复用一个线程，大家经常搞混同步非阻塞和异步阻塞，这里画图区分下。

区别：

1. 同步非阻塞：直接返回，不断主动轮询。

2. 异步阻塞：我不去轮询，太费 CPU，有结果你通知我下。

注意，异步不等于多线程，多线程是一种异步实现，监听也是一种异步实现。

9. Redis 的集群

解决单点的故障方案：

主从复制 master-slave，之前的 MongDB 和 MySQL 都是这种方式。那么是不是存储，都是这种方式更好。

集群就要面对一致性的问题，还有选举。（主从可以实现读写分离）

选举：

有了主从，就得有选举，如果主宕机了，那么从就应该通过选举上台继续做主的工作。还记得 ZooKeeper 通过 ZAB 协议自己选举。

选举的方式：

1. 内部选举 ZooKeeper

2. 外部选举 Redis

Redis 自己没有选举的能力，只能依靠外部的哨兵节点帮助自己选举。

10. Redis 的哨兵

哨兵有两个作用：

1. 监控 master 和 slave 是否正常运行。

2. 当 master 出现故障时，从 slave 中选举一个新的 master。

问题：如果哨兵节点挂了怎么办？

答：哨兵也得用集群，哨兵之间相互感知，pub/sub 所有哨兵都会订阅，sub(channel:sentinel:hello)。

新哨兵加入，会发布消息给 master，master 收到消息，订阅消息的其他哨兵都会收到信息，这样新哨兵就和其他哨兵建立了连接。

问题：多个哨兵节点，具体哪个哨兵去协助选举呢？

答：哨兵也有 Leader，通过分布式一致性算法 Raft 选举的。

11. Redis-Cluster，希望相应的数据都落在同一台机器上，怎么做？

Cluster 是做数据分片的，因为 Redis 的数据都存放在内存中，那么数据量终究会受到单机内存的限制，分片可以均匀的将数据打到不同的节点上。但是问题来了，希望某类数据在同一个节点，该怎么？

Redis 的架构师很聪明，在设计时就想到了这种场景。

HashTag

举个例子，假设存了用户的一些信息 name、phone，那么 key 可能是这样的：

user:userId:name
user:userId:phone

我们当然希望，同一个用户的信息，落在同一个节点，换句话说能否以 userId 作为分片的依据呢，可以，只需要一个 {}。

user:{userId}:name

Redis 做 hash 时，发现 key 有大括号 {}，就会提取内容 userId，并且只对 userId 做 hash 去分片。

12. Redis 缓存与数据一致性的问题

强一致性：

首先，Redis 的数据和数据库的数据，毕竟是两个不同服务，还隔着网络，是百分百不能做到事务级别的强一致性了。

最终一致性：

我们能做到的就是让 Redis 的数据最终和数据库保持一致，最终就意味着有一小段时间，数据不一致，那该如何权衡下面两个问题：

1. 更新缓存，还是让缓存失效？

• 如果更新过程很复杂，有很多前置操作，比如查询多个接口，那么就应该让缓存失效

• 如果更新缓存代价小，就更新缓存

2. 先操作数据库还是先操作缓存？

• 先操作哪个都是不一致的，看哪个对业务最合适，就选择哪个

13. 缓存雪崩

同一时刻，缓存大面积失效，大量请求同时到了数据库，缓存雪崩最受伤的是数据库。

如何避免雪崩：

1. 从缓存中取不到值，加锁访问数据库，放入缓存，必须要排队，保证只有一个线程访问到数据库。

2. 过期时间，加入随机值，不让数据同时大量过期。

3. 缓存如果挂了，不要直接就进入数据，建立多级缓存。比如 Redis 缓存失效，下一步就去读 Memcached，而不是 MySQL。

14. 缓存击穿

请求的 key 不存在，就去在 Redis 查一次，MySQL 查一次。如果有大量这样的请求进来，Redis 不会有事，但是 MySQL 很快就会挂掉。

如何避免击穿：

1. key 不存在，就给一个默认值，去 Redis 缓存。

2. 利用布隆过滤器，所有存在的数据哈希到一个足够大的过滤器中，不存在的数据请求会被拦掉。

15. Redis 的内存回收策略

Java 内存不足时，JVM 会把没有用的对象都从内存中淘汰掉。Redis 也是一样，内存中数据越来越多，超过了限制怎么办？容量不足，也就有了淘汰策略。

最大内存策略：

• noeviction：没有策略，默认值。

• volatile-random：从已设置过期时间的数据集中任意选择数据淘汰。

• volatile-lru：从已设置过期时间的数据集中挑选最近最少使用的数据淘汰。

• volatile-ttl：从已设置过期时间的数据集中挑选将要过期的数据淘汰

疑问：如何保证 Redis 存的都是热点数据？

答：选择 volatile-lru，把用得少都淘汰了，留下的都是热点。

采样：

为了保证性能，Redis 没有采用全轮询的方式，而是用的采样的方式，每次删除部分数据。

16. 管道和 Lua 脚本

批量连接：

每一次网络连接，都是一笔开销，批量的请求怎么办，管道技术可以一次连接处理多次命令。但是 Redis 的管道和 Linux 的管道不一样，后边命令拿到前边命令的处理结果。

Lua 脚本：

有多个命令，如果希望后边命令拿到前边命令的处理结果，可以通过 Lua 脚本实现。比如事务性的请求。

Lua 脚本如何保证原子性？

如果 Lua 脚本操作 key = user:1 时，其他客户端再操作这个 key 时，会被 Redis 阻塞，知道 Lua 脚本执行完毕。

17. 一致性哈希算法

数据存储，必然会有分片，因为一个节点容量是有上限的。有了分片，必然又会有数据分片均衡的话，否则新增或者减少节点，会影响大量的请求。

• 正常的操作就是取模，有 3 个节点，就模 3，结果无非就是 0，1，2。

• 如果现在增了一个节点 4，那么他也只能分担 一个节点的压力，这个是不能接受的。

放开思路：

假设节点 4 很有的基地，分散在世界各地，那么它能分担的数据，就会影响所有的节点。

一致性哈希，对 2^32 取模，得到的结果是远远大于 3 的数字，没关系，映射过去。这样每个节点都会环上大量的不同的位置。带来的结果，就是新增节点，减少节点。数据都会比较均衡。

18. 手写一个 LRU 算法

LRU，Least Recently Used，最近最少使用。

Redis 淘汰数据时涉及到的概念，而 LRU 的应用可不仅仅是 Redis。操作系统很早就使用它了。

下面代码借用了 LinkedHashMap 实现 LRU。

为什么 LinkedHashMap 可以实现，他是一个特殊的 Map，塔有顺序性，插入顺序和访问顺序。

import java.util.LinkedHashMap;
import java.util.Map;


public class LRU {
   private volatile Map<String, String> map;
   private int cacheSize;

   public LRU(int initSize) {
       this.cacheSize = initSize;

       this.map = new LinkedHashMap<String, String>(initSize, 0.75f, true) {
           @Override
           protected boolean removeEldestEntry(Map.Entry eldest) {
               return size() > LRU.this.cacheSize;
          }
      };
  }

   public String get(String inKey) {
       if (inKey.isEmpty()) {
           return null;
      }
       for (String key : map.keySet()) {
           if (key.equals(inKey)) {
               return map.get(key);
          }
      }
       return null;
  }

   public synchronized boolean put(String key, String value) {
       map.put(key, value);
       return true;
  }

下面很重要的一点，访问后，会重新处理节点。

   public V get(Object key) {
       Node<K,V> e;
       if ((e = getNode(hash(key), key)) == null)
           return null;
       if (accessOrder)
           afterNodeAccess(e);
       return e.value;
  }

这个方法把节点的顺序进行了改变，把节点 e 移动到了最后一位。这个 e 就是刚刚访问的节点。

   void afterNodeAccess(Node<K,V> e) { // move node to last
       LinkedHashMap.Entry<K,V> last;
       if (accessOrder && (last = tail) != e) {
           LinkedHashMap.Entry<K,V> p =
              (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
           p.after = null;
           if (b == null)
               head = a;
           else
               b.after = a;
           if (a != null)
               a.before = b;
           else
               last = b;
           if (last == null)
               head = p;
           else {
               p.before = last;
               last.after = p;
          }
           tail = p;
           ++modCount;
      }
  }

19. Redis 版的分布式锁

Redis 实现锁需要考虑的几点：

1. 释放锁的必须是那个加锁的人。

2. 释放锁的过程必须是原子操作，通过 Lua 脚本。

3. 加锁要设置超时时间。

public class DistributedLock {
   /**
    * 获得锁
    */
   public String acquireLock(String lockName, long acquiredTimeout, long lockTimeout){
       String id = UUID.randomUUID().toString();//保证释放锁的时候是 owner 释放。
       String lockKey = "Redislock:"+lockName;

       int lockExpire = (int )(lockTimeout/1000);

       Jedis jedis = null;

       try {
           jedis = JedisConnectionUtils.getJedis();

           long end = System.currentTimeMillis() +acquiredTimeout;
           while (System.currentTimeMillis() < end){

               Long value = jedis.setnx(lockKey, id);
               if(value == 1){
                   //设置成功
                   jedis.expire(lockKey, lockExpire);//设置超时时间
                   return id;

              }

               //程序的健壮性
               if(jedis.ttl(lockKey) == -1){
                   jedis.expire(lockKey, lockExpire);
              }

               //保证不是立马重试，立刻重试 CPU 压力大，间隔 100ms。
               try {
                   Thread.sleep(100);
              } catch (InterruptedException e) {
                   e.printStackTrace();
              }

          }
      } catch (Exception e) {
           e.printStackTrace();
      }finally {
           jedis.close();
      }
       return null;
  }

   /**
    * 释放锁
    */
   public boolean releaseLockWithLua(String lockName, String id){
       String lockKey = "lock:"+lockName;
       Jedis jedis = JedisConnectionUtils.getJedis();
       String lua = "if Redis.call(\"get\", KEYS[1]) == ARGV[1] then return Redis.call(\"del\", KEYS[1]) " +
               "else return 0 end";
       Long rs = (Long) jedis.eval(lua, 1, new String[]{lockKey, id});
       if(rs.intValue() > 0){
           return true;
      }else{
           return false;
      }
  }

}

最后大概总结一下：

关注我，获取更多干货