Redis 和 Memecache 的区别是什么？

1. Redis 不仅仅支持简单的 k/v 类型的数据，同时还提供 list，set，zset，hash 等数据结构的存储。Memecache 支持简单的数据类型 String
2. Redis 支持数据的持久化，可以将内存中的数据保持在磁盘中，重启的时候可以再次加载进行使用,而 Memecache 把数据全部存在内存之中
3. Memcached 没有原生的集群模式，需要依靠客户端来实现往集群中分片写入数据；但是 Redis 目前是原生支持 cluster 模式的
4. Memcached 是多线程，非阻塞 IO 复用的网络模型；Redis 使用单线程的多路 IO 复用模型

Redis 常见数据结构以及使用场景分析？

1. String 字符串
   字符串类型是 Redis 最基础的数据结构，首先键都是字符串类型，而且其他几种数据结构都是在字符串类型基础上构建的。
   常用在缓存、计数、共享 Session、限速等。
2. Hash 哈希
   在 Redis 中，哈希类型是指键值本身又是一个键值对结构，形如 value={{field1，value1}，...{fieldN，valueN}}。
   哈希可以用来存放用户信息，比如实现购物车。
3. List 列表
   列表（list）类型是用来存储多个有序的字符串。
   可以做简单的消息队列的功能。另外，可以利用 lrange 命令，做基于 Redis 的分页功能，性能极佳，用户体验好。
4. Set 集合
   集合（set）类型也是用来保存多个的字符串元素，但集合中不允许有重复元素，并且集合中的元素是无序的，不能通过索引下标获取元素。
   利用 Set 的交集、并集、差集等操作，可以计算共同喜好，全部的喜好，自己独有的喜好等功能。
5. Sorted Set 有序集合
   Sorted Set 多了一个权重参数 Score，集合中的元素能够按 Score 进行排列。
   可以做排行榜应用，取 TOP N 操作

除此之外还有 3 个高级数据结构
1. Bitmaps bitmaps 应用于信息状态统计
2. HyperLogLog 应用于基数统计
3. GEO 应用于地理位置计算

Redis String 的实现原理

Redis 内部 String 类型采用 SDS（simple dynamic string）表示
1
2
3
4
5
6
7
8
9
10
11
struct sdshdr {

    // buf 已占用长度
    int len;

    // buf 剩余可用长度
    int free;

    // 实际保存字符串数据的地方
    char buf[];
};

对比 C 字符串， SDS 有以下特性：
    1. 可以高效地执行长度计算（strlen） // 直接取 len 字段
    2. 防止 buf 存储内容溢出的问题 // 首先判断 free 字段是否足够
    3. 可以高效地执行追加操作（append） // 通过预分配空间，free 字段
    4. 二进制安全 // 不以 \0 做为结尾标识

Redis List 的实现原理

在 Redis 3.2 之前，List 底层采用了 ZipList 和 LinkedList 实现的，在 3.2 之后，List 底层采用了 QuickList。
Redis 3.2 之前，初始化的 List 使用的 ZipList，当以下两个条件任意一个不满足时，则会被转换成 LinkedList：
    1. List 中存储的每个元素的长度小于 64byte（可以通过配置文件修改）
    2. 元素个数小于 512（可以通过配置文件修改）

ZipList 为节省内存而设计，内存是连续的
没有维护双向指针：prev next，而是存储上一个 entry（可以理解为一个数据）的长度和 当前 entry 的长度，通过长度推算下一个元素在什么地方。
最大的缺点是是连锁更新问题，以时间换空间。

属性	类型	长度	用途
zlbytes	uint_32t	4B	记录整个压缩列表占用的内存字节数：在对压缩列表进行内存重分配，或者计算 zlend的位置时使用
zltail	uint_32t	4B	记录压缩列表表尾节点距离压缩列表的起始地址有多少字节：通过这个偏移量，程序无须遍历整个压缩列表就可以确定表尾节点的地址
zllen	uint_16t	2B	记录了压缩列表包含的节点数量：当这个属性的值小于UINT16_ MAX （65535）时，这个属性的值就是压缩列表包含节点的数量；当这个值等于 UINT16_MAX 时，节点的真实数量需要遍历整个压缩列表才能计算得出
entryX	列表节点	不定	压缩列表包含的各个节点，节点的长度由节点保存的内容决定
zlend	uint_8t	1B	特殊值 0xFF （十进制 255 ），用于标记压缩列表的末端

LinkedList 是由一系列不连续的内存块通过指针连接起来的双向链表。
缺点是它的内存开销比较大。首先，它在每个节点上除了要保存数据之外，还要额外保存两个指针。
其次，它的各个节点是单独的内存块，地址不连续，节点多了容易产生内存碎片。

QuickList 是一个 ZipList 组成的双向链表。

Redis Hash 的实现原理

参考：
    1. [渐进式 rehash](http://redisbook.com/preview/dict/incremental_rehashing.html)

Redis 的哈希对象的底层存储可以使用 ZipList 和 HashTable。
当 Hash 对象可以同时满足一下两个条件时，哈希对象使用 ZipList 编码：
    1. 哈希对象保存的所有键值对的键和值的字符串长度都小于 64 字节（可以通过配置文件修改）
    2. 哈希对象保存的键值对数量小于 512 个（可以通过配置文件修改）

HashTable 编码的哈希表对象底层使用字典数据结构。
Redis 解决哈希冲突的方式，是链式哈希。
这里存在一个问题，哈希冲突链上的元素只能通过指针逐一查找再操作。
如果哈希表里写入的数据越来越多，哈希冲突可能也会越来越多，会导致某些哈希冲突链过长，进而导致这个链上的元素查找耗时长。
所以，Redis 会对哈希表做 rehash 操作。

渐进式的 rehash
rehash 使用两个哈希表 1 和哈希表 2。
随着数据逐步增多，Redis 开始执行 rehash，这个过程分为三步：
  1. 给哈希表 2 分配更大的空间，例如是当前哈希表 1 大小的两倍；
  2. 把哈希表 1 中的数据重新映射并拷贝到哈希表 2 中；
  3. 释放哈希表 1 的空间。
在第 2 步 Redis 不是一次性把全部数据 rehash 成功，这样会导致 Redis 对外服务停止，Redis 内部为了处理这种情况采用渐进式的 rehash。
Redis 将所有的 rehash 的操作分成多步进行，直到都 rehash 完成，

Redis Set 的实现原理

Set 集合采用 intset（整数集合）和 HashTable 两种方式来实现，当满足以下两个条件的时候，采用 intset 实现，
一旦有一个条件不满足时则采用 HashTable 来实现：
    1. Set 集合中的所有元素都为整数
    2. Set 集合中的元素个数不大于 512（可以通过配置文件修改）

Redis Sorted Set 的实现原理

参考：
    1. [Redis 为什么用跳表而不用平衡树？](https://juejin.cn/post/6844903446475177998)

Zset 底层同样采用了两种方式来实现，分别是 ZipList 和 SkipList。当同时满足以下两个条件时，采用 ZipList 实现；反之采用 SkipList 实现：
    1. Zset 中保存的元素个数小于 128（可以通过配置文件修改）
    2. Zset 中保存的所有元素长度小于 64byte（可以通过配置文件修改）

采用 ZipList 的实现原理
    和 List 的底层实现有些相似，对于 Zset 不同的是，其存储是以键值对的方式依次排列，键存储的是实际 value，值存储的是 value 对应的分值。

采用 SkipList 的实现原理
    SkipList 编码的 Zset 底层为一个被称为 zset 的结构体，这个结构体中包含一个字典和一个跳跃表。
    跳跃表按 score 从小到大保存所有集合元素，查找时间复杂度为平均 O(logN)，最坏 O(N) 。
    字典保存从 member 到 score 的映射，这样就可以用 O(1) 的复杂度来查找 member 对应的 score 值。
    跳表是一种并联的链表，它在链表的基础上增加了跳跃功能，正是这个跳跃的功能，使得在查找元素时，跳表能够提供 O(logN) 的时间复杂度。

为什么用的跳表不是红黑树?
    根据作者的原话：
    1. 跳表使用的内存不是固定的，可以通过调整参数，使占用的内存低于 btree
    2. Zset 通常是 Zrange 或 Zrevrange 的操作，跳表至少与其他类型的平衡树性能一样好
    3. 跳表实现简单

Redis 压缩采用什么算法?

对 ziplist 使用 LZF 算法进行压缩，可以选择压缩深度。

Redis 中的 Bitmaps

bitmaps 不是一个真实的数据结构。而是 String 类型上的一组面向 bit 操作的集合。
常用命令：
    setbit key offset value
    getbit key offset
场景举例：
    统计活跃用户（用户登陆情况）
        使用日期作为 key，然后用户 id 为 offset，如果当日活跃过就设置为 1
    统计每天某一部电影是否被点播 统计每天有多少部电影被点播 统计每周/月/年有多少部电影被点播 统计年度哪部电影没有被点播
        日期作为 key，然后电影 id 为 offset，如果点播过就设置为 1

Redis 中的 HyperLogLog

Redis HyperLogLog 是用来做基数统计的算法，优点是在输入元素的数量或者体积非常非常大时，计算基数所需的空间总是固定的、并且是很小的。
但是，因为 HyperLogLog 只会根据输入元素来计算基数，而不会储存输入元素本身，所以 HyperLogLog 不能像集合那样，返回输入的各个元素。

比如实现 统计 APP 或网页的一个页面，每天有多少用户点击进入的次数，同一个用户的反复点击进入记为 1 次。
命令有：
    PFADD key element [element ...]
        添加指定元素到 HyperLogLog 中。
    PFCOUNT key [key ...]
        返回给定 HyperLogLog 的基数估算值。
    PFMERGE destkey sourcekey [sourcekey ...]
        将多个 HyperLogLog 合并为一个 HyperLogLog

Redis 客户端和服务器之间通信才用什么协议？

Redis 客户端使用基于 TCP 的 RESP（Redis 的序列化协议，Redis Serialization Protocol）协议与 Redis 的服务器端进行通信。
类型通过首个字节区分（+,-,:,$,*），每一部分结束时，Redis 统一使用“\r\n”表示结束。

Redis 过期策略

1. 定期删除，Redis 默认每隔 100ms 检查，是否有过期的 key，有过期 key 则删除。
   需要说明的是，Redis 不是每隔 100ms 将所有的 key 检查一次，而是随机抽取进行检查(如果每隔 100ms，全部 key 进行检查，Redis 岂不是卡死)。
   因此，如果只采用定期删除策略，会导致很多 key 到时间没有删除。
2. 惰性删除，也就是说在你获取某个 key 的时候，Redis 会检查一下，这个 key 如果设置了过期时间那么是否过期，如果过期了此时就会删除。

过期策略存在的问题，由于 Redis 定期删除是随机抽取检查，不可能扫描清除掉所有过期的 key 并删除，某些 key 由于未被请求，惰性删除也未触发。
这样 Redis 的内存占用会越来越高，此时就需要内存淘汰机制。

Redis 内存淘汰机制

- no-eviction：默认策略，不淘汰数据；大部分写命令都将返回错误（DEL 等少数除外）
- allkeys-lru：从所有数据中根据 LRU 算法挑选数据淘汰
- volatile-lru：从设置了过期时间的数据中根据 LRU 算法挑选数据淘汰
- allkeys-random：从所有数据中随机挑选数据淘汰
- volatile-random：从设置了过期时间的数据中随机挑选数据淘汰
- volatile-ttl：从设置了过期时间的数据中，挑选越早过期的数据进行删除
- allkeys-lfu：从所有数据中根据 LFU 算法挑选数据淘汰（4.0 及以上版本可用）
- volatile-lfu：从设置了过期时间的数据中根据 LFU 算法挑选数据淘汰（4.0 及以上版本可用）

LRU 与 LFU 的区别

LFU：Least Recently Used，最近最少使用
LFU：Least Frequently Used，使用频率最少的（最不经常使用的）
如果一条数据仅仅是突然被访问（有可能后续将不再访问），在 LRU 算法下，此数据将被定义为热数据，最晚被淘汰。
但实际生产环境下，我们很多时候需要计算的是一段时间下 key 的访问频率，淘汰此时间段内的冷数据。

LFU 算法相比 LRU，在某些情况下可以提升 数据命中率，使用频率更多的数据将更容易被保留。

对比项	近似LRU算法	LFU 算法
最先过期的数据	最近未被访问的	最近一段时间访问的最少的
适用场景	数据被连续访问场景	数据在一段时间内被连续访问
缺点	新增 key 将占据缓存	历史访问次数超大的 key 淘汰速度取决于 lfu-decay-time

Redis 的 LRU 实现

Redis 中的 LRU 与常规的 LRU 实现并不相同，常规 LRU 会准确的淘汰掉队头的元素，但是 Redis 的 LRU 并不维护队列，
只是根据配置的策略要么从所有的 key 中随机选择 N 个（N 可以配置）要么从所有的设置了过期时间的 key 中选出 N 个键，
然后再从这 N 个键中选出最久没有使用的一个 key 进行淘汰。

为什么要使用近似 LRU？
1. 性能问题，由于近似 LRU 算法只是最多随机采样 N 个 key 并对其进行排序，如果精准需要对所有 key 进行排序，这样近似 LRU 性能更高
2. 内存占用问题，Redis 对内存要求很高，会尽量降低内存使用率，如果是抽样排序可以有效降低内存的占用
3. 实际效果基本相等，如果请求符合长尾法则，那么真实 LRU 与 Redis LRU 之间表现基本无差异

如何保证 Redis 中存放的都是热点数据

限定 Redis 占用的内存，Redis 会根据自身数据淘汰策略，留下热数据到内存。
所以，计算一下热点数据大约占用的内存，然后设置一下 Redis 内存限制，并根据业务场景修改淘汰策略

Yxd's Blog

Redis 面试知识点总结（上）

Redis 和 Memecache 的区别是什么？

Redis 常见数据结构以及使用场景分析？

Redis String 的实现原理

Redis List 的实现原理

Redis Hash 的实现原理

Redis Set 的实现原理

Redis Sorted Set 的实现原理

Redis 压缩采用什么算法?

Redis 中的 Bitmaps

Redis 中的 HyperLogLog

Redis 客户端和服务器之间通信才用什么协议？

Redis 过期策略

Redis 内存淘汰机制

LRU 与 LFU 的区别

Redis 的 LRU 实现

如何保证 Redis 中存放的都是热点数据