分布式面试【Redis】

面试专栏 2021-06-28
175


Redis知识整理(想要获取Redis知识图,关注公众号,回复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 种结构体,取的二进制来区分不同类型:

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

代码内部根据不同情况使用不同的 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;
      }
  }

}

最后大概总结一下:

关注我,获取更多干货

文章转载自面试专栏,如果涉嫌侵权,请发送邮件至:contact@modb.pro进行举报,并提供相关证据,一经查实,墨天轮将立刻删除相关内容。

评论