Redis

Redis

为什么要使用redis做缓存？

• 高性能，用户直接访问数据库会比较慢，因为数据库是存放在硬盘上的。如果将数据放在redis缓存中，下次再访问的时候直接从缓存中获取，速度会非常快。因为redis数据库是放在内存中的。

Redis的应用场景

• 缓存
• 共享session
• 消息队列
• 分布式锁

redis为什么这么快

• (1) 纯内存操作，Redis采用的是基于内存的单线程模型的Key-Value数据库，由C语言编写。可以达到10万+的QPS
  (2) 采用单线程，避免了不必要的上下文切换和竞争条件，也不存在多进程或者多线程导致的切换，不用去考虑各种锁的问题。
  (3) 采用多路IO复用模型，非阻塞IO，可以让单个线程高效的处理多个网络连接请求。
  (4) 高效的数据结构，底层做了大量优化。比如zset的底层跳跃表，map的渐进式hash等。

redis的线程模型

• redis内部使用文件处理器，这个文件处理器是单线程的，所以redis是单线程的模型。它采用IO多路复用机制同时监听多个socket,根据socket上的事件来选择对应的事件处理器进行处理。

• 文件处理器的结构包含4个部分：

  • 多个socket
  • IO多路复用程序
  • 文件事件分派器
  • 事件处理器
• 多个socket可能会并发产生不同的操作，每个操作对应不同的文件事件，但是IO多路复用程序会监听多个socket,将socket产生的事件放入队列中排队，事件分派器每次从队列中取出一个事件，把该事件交给对应的事件处理器去执行。

Redis为什么使用单线程?

• Redis是内存数据库,对redis的操作不涉及I/O操作,所以不存在浪费CPU的现象,可见其性能瓶颈不是CPU,所以没必要设计成多线程模型.
• Redis的性能瓶颈是机器内存大小和网络带宽.

redis的删除策略

• 定期删除

  • 默认每隔100ms就随机抽取一些设置了过期时间的key,检查其是否过期，如果过期就删除。

• 惰性删除

  • 定期删除可能会导致很多过期key到了时间并没有被删除掉，除非使用的时候才去检查，才会被redis删除。

redis的内存淘汰机制

• redis内存数据集大小上升到一定大小的时候，就会施行数据淘汰策略，redis提供了六种数据淘汰策略：

  • volatile-lru 从已经设置过期时间的数据集中挑选最近最少使用的数据淘汰。
  • volatile-ttl 从已设置过期时间的数据集中挑选将要过期的数据淘汰
  • volatile-random 从已经设置过期时间的数据集中选择任意数据进行淘汰。
  • allkeys-lru 从数据集中挑选最近最少使用的数据淘汰
  • allkeys-random 从数据集中选择任意数据淘汰
  • no-eviction 禁止驱逐数据

五种数据结构底层实现

• String类型，底层是Redis构建的名为SDS的数据结构，可以用来存放微博数,粉丝数
• List链表, 底层是双向链表,可以存放粉丝列表等.
• Hash, 底层是字典,可以存放用户对象.
• Set 底层是HashTable,通过交并差等集合操作求出共同关注等.
• ZSet,底层是跳跃表,存放礼物排行榜等.

redis中的SDS数据结构和C中的字符串相比有什么优势?

• (1) C语言使用了一个长度为N+1的字符数组来表示长度为N的字符串，并且字符数组的最后一位总是\0,这种简单的表示不符合redis对字符串在安全性和效率方面的要求。

• (2) C中的字符串可能会造成的问题：
  ① 获取字符串长度为O（N）级别的操作
  ② 不能很好杜绝缓冲区溢出的问题。
  ③ 只能保存文本数据。

• (3) Redis中的解决：
  ① 增加len字段表示当前字符串的长度。
  ② 自动扩展空间。
  ③ 使用空间预分配和惰性空间释放机制，有效降低内存分配次数。
  ④ 二进制安全，读入什么就是什么。

redis的字典数据结构是如何实现的?

• (1) Redis的字典相当于java的HashMap,都是通过“数组+链表”的链地址法解决部分哈希冲突。字典结构内部包含了两个哈希表，通常只有一个哈希表有值，但在字典扩容和缩容时，需要分配新的哈希表，然后进行rehash操作，将旧的哈希表的键值对全部rehash到新的哈希表中，操作结束后，旧的哈希表将会被删除。

redis的压缩列表

• 压缩列表是redis为了节约内存而使用的一种数据结构，zset 和 hash 容器对象会在元素个数较少的时候，采用压缩列表（ziplist）进行存储。压缩列表是 一块连续的内存空间，元素之间紧挨着存储，没有任何冗余空隙。

跳跃表数据结构

• 组成：层，跳跃表节点，表头，表尾
• 由很多层组成，层数是随机的。（因为跳表的删除和添加节点是不可预测的，很难有算法保证索引部分始终均匀）。
• 每一层都是一个有序的链表，至少包含两个节点，分别是head和nil节点。
• 最底层的链表包含所有元素。
• 如果某个元素出现在某一层链表中，那么在该层下的链表也会全部出现。
• 链表中的每个节点都包含两个指针，一个指向同一层的下一个链表节点，另一个指向下一层的同一个节点。
• 查找，插入，删除的时间复杂度为O(logN),
• 时间复杂度分析：最底层n个元素，每次提取一半元素作为上一层，这样就是折半查找。
• redis中的跳表，每个节点包括层，前进指针、后退指针、分数和值。

为什么redis使用跳跃表而不使用红黑树？

• 在做范围查找的时候，红黑树树比跳跃表操作要复杂
• 平衡树的插入和删除操作可能引发子树的调整，逻辑复杂，而skiplist的插入和删除只需要修改相邻节点的指针，操作简单又快速。
• 查找单个key，skiplist和平衡树的时间复杂度都为O(log n)大体相当；

Redis的hash和java的HashMap有何异同?

• ① Redis的hash采用数组+链表的实现方式，而Java的HashMap在1.7的实现方式与redis相同。1.8进行了优化，变成数组+链表/红黑树。
  ③ Redis的rehash采用渐进式的方式，对大数据量的rehash操作性能提升明显。
  ④ Redis的单链表在冲突的时从表头插入，时间复杂度为O(1)，而HashMap采用尾插法,时间复杂度为O(n)。

Redis的一致性hash算法

• ① 首先将Hash值在 0 到232进行取模，最后得到各个服务器在哈希环上的位置。
  ② 接下来将数据使用相同的hash函数计算出哈希值，并确定此数据在环上的位置，从此位置沿环顺时针行走，第一个遇到的服务器就是其应该定位的服务器。
  ③ 在一致性哈希算法中，如果增加一台服务器，则受影响的数据仅仅是新服务器到其环空间中前一台服务器（即沿着逆时针方向行走遇到的第一台服务器）之间数据，其它数据也不会受到影响，具有较好的容错性和可扩展性。
  ④ 另外，一致性哈希算法在服务节点太少时，容易因为节点分布不均匀而造成数据倾斜问题。

一致性哈希算法的优缺点

• (1) 适用场景：redis分布式集群中。
  (2) 为什么要对2^32取余？因为IPV4的地址是32位，这样可以保证所有的ip地址在进行取余时不会重复。
  (3) 先把服务器映射到环上，分布在不同位置。然后对某对象也使用一致性哈希算法，从它在环上的位置开始，顺时针找到的第一个位置就是它应该被缓存到的服务器。
  (4) 优点：如果某台服务器出现故障，一致性哈希可以让本应该存储到该服务器上的对象存储到它在顺时针方向的下一个服务器中。对于其他服务器，不会被影响。如果是普通的hash算法，在服务器数量发生改变时，所有服务器缓存在同一时间都失效了。而使用一致性哈希算法，在服务器数量改变时，只有部分缓存失效。
  (5) 缺点：容易出现hash环偏斜问题。服务器数量较小时，不是均匀分布在hash环上的，那么被缓存的对象有可能大部分集中缓存到某一台服务器上。造成缓存分布极度不均匀，在极端情况下会出现系统崩溃问题。
  (6) 解决办法：引入虚拟节点。

Redis的Sorted set底层实现原理

• ① 底层是跳表的数据结构，每个节点包括层、前进指针、后退指针、分数和值。
  ② Skiplist不要求上下相邻两层链表之间的节点个数有严格对应关系，而是为每个节点随机出一个层数。新插入一个节点不会影响到其他节点的层数。插入操作只需要修改节点前后的指针，而不需要对很多节点都进行调整，降低了插入操作的复杂度。

Redis的Cluster是怎么做到高可用的?

• ① Redis主从架构，一主多从，master负责写，并且将数据复制到其他slave节点。从节点负责读。即使其中一个slave宕机，其他服务器依然可以提供服务，实现redis的高可用以及数据冗余备份。
  ② Redis哨兵集群可以实现高可用。当master服务器宕机时，哨兵就会通过投票机制来选择新的mater并将所有slave连接到新的master.

Redis实现延迟队列

① ZeSet结构实现。通过zadd命令向队列中添加元素，并设置score值表示元素过期时间。按照score排序，轮询任务每秒只轮询score大于当前时间的key即可。

② 优点：简单实用，缺点是不能支持太多的任务需求。异常情况需要自己处理，同时消息处理失败的回滚方案，也要自己处理。

Redis中缓存雪崩的解决办法?

• 缓存雪崩是指缓存同一时间大面积失效，所以后面的请求都会落到数据库上，造成数据库短时间内承受大量请求而崩掉。

• ① 增加多个redis服务器，即使个别节点宕机，依然可以提供服务.
  ② 缓存预热：对不同的key设置不同的过期时间。
  ③ 限流或降级：通过加锁或队列来控制访问数据库的线程数量。

Redis中缓存击穿的解决办法?

• 缓存击穿是一个key非常热点，在承受大量的高并发，当它失效的一瞬间，大量请求落到数据库上，造成数据库崩掉。

• ① 设置热点数据永不过期。
  ② 接口限流与熔断，降级。
  ③ 加互斥锁，每次只允许一个线程去访问数据库，其他线程等待。比如分布式锁。

Redis中缓存穿透的解决办法？

• 缓存穿透是黑客故意请求缓存中不存在的数据，导致所有请求都落到数据库上，造成数据库短时间内承受大量 请求而崩掉。

• ① 缓存无效key:如果一个查询返回的数据为空（不管是数据不存在，还是系统故障），我们仍然把这个空结果进行缓存，但它的过期时间会很短，最长不超过五分钟。
  ② 布隆过滤器：将所有可能存在的数据哈希到一个足够大的bitmap中，一个一定不存在的数据会被这个bitmap拦截掉，从而避免了对底层存储系统的查询压力。

Redis的大key问题

• ① 就是存储本身的key值空间太大，或hash，list，set等存储中value值过多。

redis的集群模式

• 主从同步

  • 在复制的概念中，数据库分为两类，一类是主数据库（master），另一类是从数据库(slave）。主数据库可以进行读写操作，当写操作导致数据变化时会自动将数据同步给从数据库。而从数据库一般是只读的，并接受主数据库同步过来的数据。一个主数据库可以拥有多个从数据库，而一个从数据库只能拥有一个主数据库。

• 哨兵模式

  • 集群监控：负责监控主副数据库是否正常工作。
  • 消息通知：负责将故障消息报警给运维人员。
  • 故障转移：负责将主节点转移到从节点上。
  • 配置中心：通知客户端更新主节点地址。
  • 主数据库遇到异常中断服务后，哨兵模式可以实现自动化的系统监控和故障恢复功能。

• cluster集群

  • 至少三主三从
    

  • 集群介绍

    • 采用无中心节点的方式实现，每个主节点都会与其他主节点保持连接。节点间通过gossip协议交换彼此的信息，同时每个主节点又有一个或多个从节点。
    • 客户端连接集群时，直接与redis集群中的每个主节点连接，根据hash取模将key存储在不同的哈希槽。
    • 集群中采用数据分片的方式，将redis集群分为16384个哈希槽。这些哈希槽分别存储于三个主节点中。
    • 每个节点会保存一份数据分布表，节点将自己的slot信息发送给其他节点，节点间不停传递数据分布表。
    • 客户端连接集群时，通过集群中某个节点地址进行连接。客户端尝试向这个节点执行命令，比如获取某个key值，如果key所在的slot刚好在该节点上，则能够执行成功。如果slot不在该节点，则节点会返回MOVED错误，同时把该slot对应的节点告诉给客户端，客户端可以去对应节点执行命令。

  • 扩容问题

    • 当集群中加入新节点时，会与集群中的某个节点进行握手，该节点会把集群内的其他节点信息通过gossip协议发送给新节点，新节点与这些节点握手后加入到集群中。然后集群中的节点会各取一部分哈希槽分配给新节点。
      

    • 集群中要删除节点时，只需要将节点中所有哈希槽移动到其他节点，然后移除空白节点即可。

redis哈希槽

• redis集群选用的是哈希槽而不是一致性哈希。因为一致性哈希对数据分布，节点控制并不是很友好（哈希环偏斜）

• redis cluster的hash算法是crc16算法，一种校验算法。cluster集群方案采用的是虚拟槽分区，包含了16384个槽，范围是0~16383。每个节点负责维护一部分槽。

• 槽是集群内数据管理和迁移的基本单位。比如上述的三个主节点，每个结点大致负责5500个槽的读写5500个槽的读写，节点会维护自身负责的虚拟槽。

• 对于客户端请求的key，需要根据一下公式计算存在哪个槽上,然后redis会去对应的节点进行操作。

  slot = CRC16（key）& 16383

• 使用哈希槽的好处在于可以方便的添加或移除节点

  • 当需要增加节点时，只需要把其他节点的某些哈希槽挪到新节点。
  • 当需要移除节点时，只需要把移除节点上的哈希槽挪到其他节点。

• 为什么有16384个槽？

  • CRC16算法产生的hash值有16bit, 该算法可以产生个值。
  • 消息头中有一个myslots的char数组，长度为16383/8，这块的大小是16384/8/1024=2kb,
  • 如果槽位为65536，发送心跳信息的消息头达8k,发送的心跳包过于庞大，浪费带宽。
  • redis的集群主节点数量基本不可能超过1000个。对于节点数在1000以内的redis cluster集群，16384个槽位够用了。
  • 槽位越小，节点少的情况下，压缩比高。

Redis主从同步机制的原理

• 全量同步

  1. 从服务器向主服务器发送sync命令。

  2. 收到sync命令后，主服务器执行bgsave命令，用来生成rdb文件，并在一个缓冲区中记录从现在开始执行的写命令。

  3. bgsave执行完成之后，将生成的rdb文件发送给从服务器，用来给从服务器更新数据。

  4. 主服务器再将缓冲区记录的写命令发给从服务器，从服务器执行完这些命令后，状态就和主服务器一致。

• 增量同步
  slave初始化后正常工作时，主服务器发送的写操作同步到从服务器的过程。增量复制的过程主要是主服务器每执行一个写命令就会向从服务器发送相同的写命令，从服务器接收并执行收到的写命令。

Redis哨兵模式

• ① 哨兵是一个独立的进程，通过发送命令，等待redis服务器响应，从而监控运行的多个redis实例。
  ② 两个作用：监控服务器是否正常运行。当哨兵检测到master宕机，会自动将slave切换为master,然后通过发布订阅模式通知其他的从服务器，修改配置文件，切换主机。
  ③ 故障切换（failover)过程：假设master宕机，哨兵1先检测到这个结果，仅仅是哨兵1认为master不可用，该现象称为主观下线。当后面的哨兵也检测到主服务器不可用，并且数量达到一定值时，那么哨兵之间就会进行一次投票，投票的结果由一个哨兵发起，进行failover操作。切换成功后，就会通过发布订阅模式，让各个哨兵把自己监控的从服务器实现切换主机，这个过程称为客观下线。这样对于客户端而言，一切都是透明的。

布隆过滤器

• ① 结构是bit数组，要映射一个值到布隆过滤器中，需要使用多个不同的哈希函数生成多个哈希值，并对每个生成的哈希值指向的位置置一。若某个值有一个位置的值不为一，那么就判定该值不存在。
  ② 只能判断数据是否一定不存在，无法判断数据是否一定存在。当bit数组过小，输入数据过多时，存在一定的误判。

Redis锁机制

(1) Redis能使用的加锁命令分别是incr,setnx,set。

(2) Incr加锁思路是若key不存在，那么key的值会被先初始化为0，然后再执行INCR操作+1，如果其他线程再执行incr操作时，返回值大于1，说明这个锁正在被占用。锁使用完毕后需要进行删除。

(3) Setnx加锁思路是如果key不存在，将key关联到value,如果key已经存在，则setnx不做任何操作。

(4) Set加锁思路是如果key不存在，就将key关联到value,若key已经存在，就要覆盖旧的value值。

分布式锁

(1) 基于数据库实现。 排他锁或乐观锁。缺点：数据库操作性能比较差，没有锁失效机制，非阻塞，操作失败后，需要轮询占用CPU资源。

• 排他锁：对某个字段进行唯一性约束，如果有多个字段提交到数据库，保证只有一个操作可以成功。
• 乐观锁，操作中认为不会发生并发冲突，只有在版本更新失败后才察觉到。

(2) 基于redis实现，使用setnx，expire和delete。缺点:超时时间不好控制，非阻塞，操作失败后需要轮询占用cpu资源。

• ① 获取锁的时候，使用setnx加锁，并使用expire命令为锁添加一个超时时间，超过该时间则自动释放锁，锁的value值为一个随机生成的UUID，通过此在释放锁的时候进行判断（确保加锁和解锁是同一个客户端）。

• ② 获取锁的时候还设置一个获取的超时时间，若超过这个时间则放弃获取锁。

• ③ 释放锁的时候，通过UUID判断是不是该锁，若是该锁，则执行delete进行锁释放。

(3) 基于zookeeper实现。优点:具备高可用，可重入，阻塞锁等特性。缺点：需要频繁创建和删除节点，性能上不如redis方式。

• ① 创建一个目录mylock
• ② 线程A想获取锁就在mylock目录下创建临时顺序节点；。
• ③ 线程A获取mylock目录下所有的子节点，然后获取比自己小的兄弟节点，如果不存在，则说明当前线程顺序号最小，获得锁；
• ④ 线程B获取所有节点，判断自己不是最小节点，设置监听比自己次小的节点；
• ⑤ 线程A处理完毕后删除自己的节点。线程B监听到变更事件，判断自己是不是最小节点，是则获得锁。

Setnx分布式锁的缺点

• (1) Setnx分布式锁的缺点，setnx和expire这两个操作不是原子操作，如果执行setnx之后获得锁，但此时客户端宕机，这样无法执行expire设置过期时间导致锁一直无法被释放。后面在setnx中增加了参数扩展，使得setnx和expire具备原子性。
  (2) 在单master-slave的redis系统中，正常情况下客户端向master获取锁之后master节点宕机，并未将该锁同步到salve，之后在哨兵模型下，salve升级为master，但没有之前未同步的锁的信息，如果此时有新的客户端要在新master获取锁，那么将可能出现两个客户端持有同一把锁的问题。
  (3) 解决办法：redlock算法。

RedLock算法

• (1) 是Redis分布式锁的更高级的实现方式，是基于多redis节点的。而setnx只能基于单redis节点。

• (2) 在redis的分布式环境中，假设有N个完全独立的redis主节点(N为奇数，假设为5），获取锁和释放锁的过程中，客户端会执行以下操作：
  ① 获取当前系统时间。
  ② 依次尝试从5个实例，使用相同的key和具有唯一性的value获取锁。当向redis请求获取锁时，客户端应该设置一个获取的超时时间，超过这个时间则放弃获取锁。
  ③ 客户端使用当前时间减开始获取锁的时间得到获取锁使用的时间。当前仅当从半数以上的redis节点获取锁，并且获取锁使用时间小于锁的失效时间，锁才算获取成功。
  ④ 如果获取到了锁，key真正有效时间等于锁有效时间减去获取锁使用的时间。
  ⑤ 若因为某些原因获取锁失败，客户端应该在所有的redis实例上进行解锁，无论redis实例是否加锁成功。

Redis的Rehash

• (1) 在redis中，扩展或收缩哈希表需要将 ht[0] 里面的所有键值对 rehash 到 ht[1] 里面， 但是， 这个 rehash 动作并不是一次性、集中式地完成的， 而是分多次、渐进式地完成的。为了避免 rehash 对服务器性能造成影响， 服务器不是一次性将 ht[0] 里面的所有键值对全部 rehash 到 ht[1] ， 而是分多次、渐进式地将 ht[0] 里面的键值对慢慢地 rehash 到 ht[1] 。

• (2) 以下是哈希表渐进式 rehash 的详细步骤：
  ① 为 ht[1] 分配空间， 让字典同时持有 ht[0] 和 ht[1] 两个哈希表。
  ② 在字典中维持一个索引计数器变量 rehashidx ， 并将它的值设置为 0 ， 表示 rehash 工作正式开始。
  ③ 在 rehash 进行期间， 每次对字典执行添加、删除、查找或者更新操作时， 程序除了执行指定的操作以外， 还会顺带将 ht[0] 哈希表在 rehashidx 索引上的所有键值对 rehash 到 ht[1] ， 当 rehash 工作完成之后， 程序将 rehashidx 属性的值增一。
  ④ 随着字典操作的不断执行， 最终在某个时间点上， ht[0] 的所有键值对都会被 rehash 至 ht[1] ， 这时程序将 rehashidx 属性的值设为 -1 ， 表示 rehash 操作已完成。
  ⑤ 渐进式 rehash 的好处在于它采取分而治之的方式， 将 rehash 键值对所需的计算工作均滩到对字典的每个添加、删除、查找和更新操作上， 从而避免了集中式 rehash 而带来的庞大计算量。

Redis的持久化方式

• (1) RDB持久化是指在指定时间间隔内将内存中的数据集快照写入磁盘，即将内存中的数据以快照的方式写入二进制文件中，默认文件名是dump.rdb。
• (2) RDB提供了三种机制：save,bgsave和自动化。

• ① Save会阻塞当前redis服务器，执行save命令期间，redis不能处理其他命令，直到RDB过程完成为止。

  • ② 执行bgSave，reids会在后台异步进行快照操作，并能够正常响应客户端请求。具体操作是redis进程执行fork创建子进程，RDB持久化过程由子进程负责，完成后自动结束，主进程继续提供服务以供客户端调用。
• ③ 自动触发，在redis.conf配置文件中设置save second changes,表示限定时间范围内key的变化数量达到指定数量即进行持久化，自动触发bgsave。
• (3) RDB方式的优缺点：

• ① 体积更小。RBD文件紧凑，全量备份，非常适合用于数据集备份和灾难恢复。

  • ② 性能更高。生成RDB文件时，redis主进程会fork()一个子进程来处理所有保存工作。父进程不需要做任何IO操作，故能够最大化redis的性能。

• ③ 速度更快。RDB在恢复大数据集的速度要快于AOF。

  • ④ 故障丢失。RDB快照是一次全量备份，存储的是内存数据的二进制序列化形式，在快照持久化期间修改的数据不会被保存，会丢失数据。
• ⑤ 耐久性差。由于rdb的复制是全量的，即使是fork()的子进程来进行备份，当数据量很大的时候对磁盘的消耗也是不容忽视的。尤其是在访问量很高的时候，fork的时间也会延长，导致cpu吃紧，耐久性相对较差。
• (4) AOF机制，redis会将每个收到的写命令追加到AOF文件的末尾，redis默认是不开启AOF持久化的，需要设置appendonly yes来开启。直接追加会导致AOF文件变得越来越大，为了压缩AOF文件，redis提供了bgrewriteaof命令，将内存中数据以命令方式保存到临时文件中，同时会fork出一条新进程来将文件重写。
• (5) AOF的三种触发机制：always,everysec，no.

• ① Always表示每次发生数据变更就会被立即记录到磁盘，性能较差，但不会丢失数据。

  • ② Everysec表示每秒一次将多个写命令记录到磁盘，可能会丢失一秒的数据。
• ③ No 由操作系统觉得什么时候来同步数据。
• (6) AOF机制的优缺点

• ① 数据保证。AOF可以更好的保护数据不丢失，默认同步策略是everysec，最多丢失1秒的数据。

  • ② 自动缩小。AOF文件大小达到一定容量时，后台会自动进行aof重写。这个过程不会影响主进程。重写完成后，新的写入会写入到新aof文件中，旧的aof会被删除掉。

• ③ 紧急恢复。AOF文件适合做灾难性的误删除的紧急恢复。比如某人不小心用flushall命令清空了所有数据，只要这个时候后台rewrite还没有发生，那么就可以立即拷贝AOF文件，将最后一条flushall命令给删了，然后再将该AOF文件放回去，就可以通过恢复机制，自动恢复所有数据。

  • ④ 体积更大。对于同一份数据来说，AOF日志文件通常比RDB文件更大。
• ⑤ 性能相对较差，恢复速度更慢.

Redis如何实现LRU？

• (1) 如果按照HashMap和双向链表实现，需要额外的存储存放 next 和 prev 指针，牺牲比较大的存储空间，显然是不划算的。所以Redis采用了一个近似的做法，随机抽取出若干key,按照访问时间排序后,淘汰掉不常用的.
  (2) 具体做法是redis创建了一个名为redisObject的结构体,在结构体中定义了一个lru字段用来记录对象最后一次被访问的时间,随机选5个key,将lru字段值最小的key移除.后面的改进做法是利用缓冲池.首先第一次随机选取的key会放入缓冲池中,缓冲池中的key是按lru大小排序的.接下来每次随机选取的key的lru值必须要小于池中的最小lru才会继续放入缓冲池.直到池满,放满后,如果有新的key需要放入,就将池中lru最大的key取出.淘汰的时候直接从池中选择一个lru最小值进行淘汰.
  (3) 可以使用reids的数据结构zset来实现,通过zadd向集合中添加元素value,并设置score为当前系统时间.按照score排序,score最小的就是最久未使用的,最大的就是最近使用的.当某个value被访问到,就更新它的socre为当前系统时间,如果集合中元素个数超过一定范围,就删除score最小的value值.

Redis实现消息队列的原理

• (1) Redis提供了两种方式来实现消息队列，一个是使用生产者消费者模式，另外一个是发布订阅模式。前者会让一个或多个消费者监听消息队列，一旦消息到达，谁先抢到谁就可以消费（加分布式锁），如果队列中没有消息，则消费者线程会阻塞等待。具体实现方式是redis的list结构，生产者线程使用lpush向列表发送消息，消费者线程使用brpop从列表中取消息，如果列表中没有消息就一直阻塞直到新的消息过来。缺点：没有ACK机制，不能重复消费，不能做广播模式。
• (2) 发布订阅模式是多个消费者可以同时订阅多个消息频道，只要生产者将消息发布到对应频道，所有订阅该频道的消费者都能够收到消息。缺点：如果客户端不在线，消息会丢失，不适合做消息存储。

redis扩容和缩容的条件

• (1) 当hash表中元素个数等于第一维数组的长度时，就开始扩容，扩容的新数组大小是原数组大小的2倍。如果redis正在做bgsave，redis尽量不去扩容，但当hash表的元素个数达到了第一维数组长度的5倍就会强制扩容。
  (2) 当hash表元素个数低于数组长度的10%，就会进行缩容。

Redis的hyperLogLog

• (1) redis统计PV（浏览量，每点击一次就记录一次），给每个页面配置一个独立的redis计数器，把计数器的key后缀加上当天的日期，每来一个请求，就执行incrby指令一次。
  (2) Redis统计uv(独立访客，每个用户每天只记录一次），每个网页请求都需要带上用户的ID，如果为每个页面设置一个set集合来存储当天访问过的用户ID，会产生存储空间巨大以及统计复杂的问题。解决方案有两种：一种是bitmap,将每个元素对应到bit数组的一位，通过异或操作还可以轻松合并多个统计结果，但对于页面数量巨大时也不适用。HperLogLog是一种概率统计方法，不直接存储数据本身，而是通过算法来预估基数值，可以大大节约内存，并将误差控制在一定范围内。Redis 中实现的 HyperLoglog 也只需要 12 K 内存，在 标准误差 0.81% 的前提下，能够统计 2^64 个数据！

假如Redis里面有1亿个key，其中有10w个key是以某个固定的已知的前缀开头的，如何将它们全部找出来？

• (1) 使用 keys 指令可以扫出指定模式的 key 列表。但是要注意 keys 指令会导致线程阻塞一段时间，线上服务会停顿，直到指令执行完毕，服务才能恢复。这个时候可以使用 scan 指令，scan 指令可以无阻塞的提取出指定模式的 key 列表，但是会有一定的重复概率，在客户端做一次去重就可以了，但是整体所花费的时间会比直接用 keys 指令长。