Redis

哈希表中的哈希桶肯定是比String类型的kv键值对要少很多，所以这就不可避免地会出现哈希冲突的情况，当出现哈希冲突的时候，redis会使用链表组织这些冲突的entry，每个entry里面都有个next指针指向了下一个冲突的entry，类似于HashMap结构

哈希冲突怎么解决？

给哈希表2分配更大的空间，比如是哈希表1的两倍

把哈希表1的数据重新映射并且拷贝到哈希表2中

释放哈希表1的数据

当一个哈希桶中的冲突entry越来越多的时候，此时这个桶的链表就会越来越长，那么如果要查找的key在链表的尾部，时间复杂度就是O（n），所以此时redis就会进行一个rehash的操作，而为了进行rehash操作，redis默认使用了两个全局哈希表

rehash

在第二步把哈希表1的数据拷贝到哈希表2中的过程中会造成redis的线程阻塞无法服务其他请求，所以如果大量数据的话，阻塞时间就会越长，为了解决这个问题，redis引入了渐进式rehash，所谓的渐进式rehash，就是在第二步拷贝数据的时候redis仍然可以处理其他请求，在第一次请求来的时候，redis从哈希表 1 中的第一个索引位置开始，顺带着将这个索引位置上的所有 entries 拷贝到哈希表 2 中；等处理下一个请求时，再顺带拷贝哈希表 1 中的下一个索引位置的entry。  注意点： 1. 因为在进行渐进式 rehash 的过程中， 字典会同时使用 ht[0] 和 ht[1] 两个哈希表， 所以在渐进式 rehash 进行期间， 字典的删除（delete）、查找（find）、更新（update）等操作会在两个哈希表上进行： 比如说， 要在字典里面查找一个键的话， 程序会先在 ht[0] 里面进行查找， 如果没找到的话， 就会继续到 ht[1] 里面进行查找， 诸如此类。2. 另外， 在渐进式 rehash 执行期间， 新添加到字典的键值对一律会被保存到 ht[1] 里面， 而 ht[0] 则不再进行任何添加操作： 这一措施保证了 ht[0] 包含的键值对数量会只减不增， 并随着 rehash 操作的执行而最终变成空表。

对于String类型的键值对，redis采用的是哈希表结构去进行快速寻找到kv对，里面主要是有一个全局哈希表去存放所有的kv键值对，而全局哈希表其实就是一个数组，每个元素就是一个哈希桶，哈希桶里面存放的entry就是key的指针和value的指针，当我们一个key过来的时候，redis会去对这个key进行哈希运算然后找到对应的哈希桶，进而就找到这个key对应的value的指针，由于哈希表结构的最小时间复杂度O（1），所以这个过程redis的速度可以很快

key和value用什么结构组织的？

集合类型

数据结构

redis的操作基本都是基于内存操作的

redis为什么这么快？

基于IO多路复用模型

网络IO模型

当redis写入数据时，会把这条命令以一定的格式存储在一个aof文件中，由于写aof是在redis主线程做的，所以这时会造成线程阻塞

性能消耗较大，但是能保证数据基本不会丢失

同步写回：每个写命令执行完，立马同步地将日志写回磁盘；

Always

性能消耗较小，最多丢失1s的数据

每秒写回：每个写命令执行完，只是先把日志写到 AOF 文件的内存缓冲区，每隔一秒把缓冲区中的内容写入磁盘；

Everysec

性能消耗最小，但是写磁盘的主动权交到了操作系统手上，宕机的时候容易丢失较多数据

操作系统控制的写回：每个写命令执行完，只是先把日志写到 AOF 文件的内存缓冲区，由操作系统决定何时将缓冲区内容写回磁盘。

No

3种写回策略

随着数据的增多，aof文件也会越来越大，这样就会造成一个很影响性能的问题，就是在恢复数据的时候会非常缓慢，所以重写机制就是重写整个aof文件使得aof文件变得更小

比如当有一对kv键值对被多次修改形成了多条更新命令之后，在重写aof文件之后，这对kv键值对对应的命令就是只取当前内存中最新的值生成最新的写入命令，这样在恢复数据的时候就只取按照最新的命令去执行就可以了

如何重写？

答案是不会的，因为redis会开启一个子进程去处理aof的重写操作，首先redis会拷贝一份当前内存最新的数据（这里的拷贝不会拷贝物理内存，而是拷贝父进程内存的虚实映射，也就是能共享父进程的所有数据），然后子进程会根据这份拷贝的内存数据去生成最新的写入操作命令，然后再写入到aof的重写文件中。如果此时有写请求过来了，那么也会写入到原本的aof缓冲区中并且会写入到原来的aof文件，同时也会写入新的aof缓冲区，等到新的aof文件重写成功了，再把新的aof缓冲区的数据追加到新aof文件中，最后就可以替代掉原来旧的aof文件了

aof重写的时候会阻塞主线程吗？

aof文件超过最大定义大小时

执行bgrewriteaof，手动触发

触发时机

重写机制

AOF

对某一个时刻内存中的所有数据生成快照文件（二进制文件，可以直接导入到内存中）

执行该命令生成RDB二进制文件，在主进程中执行，所以主进程会被阻塞

save

bgsave

生成RDB文件的命令

对于快照操作来说，它希望能够得到该时刻所有数据状态的快照版本，所以如果在T时刻执行了快照命令，如果要避免数据被改变的话就需要在此期间暂停写操作了，但是redis肯定不会这么干，redis是怎么做的呢，它利用了操作系统的copy on write（写时复制）技术，在这期间如果有修改操作去修改一块数据的话就拷贝一份这块数据的副本，然后快照的时候就去写入这块副本数据，然后修改操作继续修改原数据

快照时数据能否修改

RDB

使用bgsave命令fork子进程的时候会短暂地阻塞父进程，所以，如果频繁地去生成快照的话肯定会对redis性能造成影响，所以redis4.0新特性就有一个AOF与RDB混合使用，当第一次生成了RDB文件之后，之后对数据的写操作都会写入aof文件，然后到第二次生成RDB文件的时候再把aof文件清空，也就是说aof文件只会写入两次生成RDB文件之间的增量数据，这样，在恢复数据的时候就可以根据RDB文件以及aof文件去恢复数据了，既利用了RDB文件快速恢复数据的好处，也能享受了aof只记录简单操作命令的优势

AOF和RDB混合持久化

数据恢复

持久化

读写分离，读操作主库从库都可以接收，写操作只能在主库接收

第二阶段：主库会使用bgsave命令开启子进程生成RDB快照文件，然后把这个RDB文件发送给从库，从库接收到主库发送过来的RDB文件之后，会把本地内存的数据全部清空，然后完成RDB文件的数据加载

第三阶段：主库在发送RDB文件给从库的时候，主库并不会阻塞，依然可以接收服务请求，所以此时可能会有写请求过来，那么主库会把这些写命令操作放到replication buffer中，在主库完成RDB文件的发送之后会继续把这些写命令操作发送给从库，以达成数据的一致性

主从间如何进行第一次数据同步

如果此时有很多从库都要和主库去进行数据同步的话，那么根据上面主从间数据同步的原理过程可以知道，数据同步的时候主库的性能消耗最大的有两处，一是fork子进程生成RDB文件，二是发送RDB文件给从库，因为fork子进程会阻塞父进程，发送RDB会占用宽带资源，所以我们可以采用“主-从-从”模式，也就是说选出一个从库然后让某几个从库去从选中的从库做数据同步，这样就能减轻主库的压力了

主从级联模式分担全量复制时的主库压力

redis2.8之前当主从重新连接之后，会再做一次全量复制，但是2.8之后就采用了增量复制

这里有个需要注意的点是replication buffer是一个环形的缓冲区，如果它满了主库的写操作会覆盖掉之前写入的数据，主库的所以这个缓冲区的大小设置是需要去研究的，可以调整repl_backlog_size这个参数去改变缓冲区的大小，如果设置得过小的话可能会导致主从库之间数据不一致

当主从之间的网络断开之后，主库接收到的写请求除了会写到replication buffer中，还会写到一个repl_backlog_buffer缓冲区中，主库会记录自己写到的位置，从库则会记录自己已经读到的位置，当主从之间网络恢复连接时，从库会发送psync命令，把自己当前的slave_repl_offset发送给主库，然后主库会去对比slave_repl_offset与master_repl_offset，拿到它们之间相差的操作然后主库再把这些操作发送给从库

主从库间网络断了怎么办？

主从同步

一旦主从库完成了全量复制，它们之间就会一直维护一个网络连接，主库会通过这个连接将后续陆续收到的命令操作再同步给从库，这个过程也称为基于长连接的命令传播，可以避免频繁建立连接的开销。

数据同步

哨兵在运行的时候，会周期性地给所有的主从节点发送ping命令，如果在规定时间没有相应的主库或从库，哨兵就会认为其已经下线了，这里特别是主库，如果主库没有响应就会进入下一个“选主”的任务，但是判断主库是否下线的话并没有那么容易，因为很有可能哨兵会产生误判的情况，比如由于网络拥堵等其他问题导致主库没有及时响应给哨兵，而一旦产生了误判，就会去重新选主，首先哨兵重新选主就会花费时间，之后新主库又要与从库进行数据同步，所以为了避免误判带来的不必要的性能消耗，通常都会使用由多个哨兵实例组成的哨兵集群去判断主库是否下线了。如何判断？很简单，少数服从多数，一个哨兵实例认为这个主库下线的话就会判断为“主观下线”，如果超过一半的实例都认为这个主库是“主观下线”，那么这个主库就会被标记为“客观下线”，这时主库就会真正地被认为是已经下线了

监控

选主

在选出了新主库之后，哨兵就要去通知所有的从库说这个就是新主库，并且从库会向新主库发送replicatof命令成为该主库的从库，然后哨兵还要去发送新主库的连接信息给客户端

通知

redis的哨兵机制解决的主要就是当主库挂了如何对外继续提供服务，所谓的哨兵其实是一个运行在特殊模式的redis进程，它在运行的时候主要有三个任务，分别是监控，选主，通知

在配置哨兵的时候，我们只需要在配置文件中配置下主库的ip+端口就可以了，并没有配置其他哨兵节点的ip，那么哨兵之间是怎么去进行通信的呢？答案就是基于redis的pub/sub机制（发布订阅机制，类似于观察者模式）去实现的，当一个哨兵与主库进行了连接之后，他会去监听一个特定的topic，再发布自己的连接信息，然后其他哨兵节点就订阅信息这样互相之间就可以进行通信了

哨兵之间如何互相获取ip进行通信？

既然哨兵能与主库进行通信，那么它可以向主库发送info命令，主库收到这个命令之后会把从库的ip列表返回给哨兵

哨兵如何获取从库的ip地址？

由于需要拿到半数以上的赞成票，如果只有两个哨兵节点组成的哨兵集群，那么如果其中一个节点挂了，那么是没有办法达到选举新Leader的条件的，所以一般都配置节点数为奇数的。

当一个哨兵认定为这个从库是“主观下线”的时候，它就会向其他哨兵发送是否赞成的投票，其他哨兵会根据自己与该从库的连接情况响应“Y”或“N”，如果获得的票数大于或等于quorum这个配置值，那么这个从库就会被认定为“客观下线”，此时这个哨兵就能够再次发出投票请求，表示希望自己能够成为整个哨兵集群的Leader，只有成为了Leader才能有发起主从切换的权力，如何成为Leader呢？要满足两个条件：第一，拿到半数以上的赞成票；第二，拿到的票数同时还需要大于等于哨兵配置文件中的 quorum 值。

如何确定由哪个哨兵发起主从切换？

哨兵集群

哨兵机制

垂直扩展比较简单且粗暴，就是讲机器的内存等配置加强，但是这种方式上限较高，很容易受硬件的容量成本所限制，并且会造成内存过大使得redis持久化性能下降

垂直扩展

水平扩展就是我们所说的切片集群，采用多台机器去存储数据，每一台都存储一部分数据

redis采用了哈希槽来处理数据和实例之间的映射关系，整个集群一共有16384个槽位，每一个节点实例都占据16384/N个槽位，当一个key过来的时候客户端会对它进行一次CRC16算法进行hash得到一个值，然后再通过这个值去对16384进行取模，得到就是槽位值，再把这个槽位值去对比下是属于集群中的哪个redis节点实例，定位到具体的实例之后进行发送命令

客户端在发送命令的时候首先自己去对一个key进行CRC16的hash运算然后对16384进行取模得到槽位值，分局这个槽位值就可以定位到某一个实例，但是客户端是怎么拿到槽位值与实例的映射关系表的呢？答案就是客户端与集群的任意实例建立连接之后，这个实例就会把槽位的分配信息发送给客户端，客户端再对其进行保存，但是这里就又有一个问题了，每个实例只知道自己所对应的槽位值是多少，它是怎么知道整个集群的槽位值分配信息的呢？原因就在于集群之间的实例会互相进行通信，这样集群中的每个实例都会有整个集群的槽位分配信息了

对于整个redis集群来说，槽位的分配信息不会是一成不变的，主要是可能会有实例的新增和删除，当有实例新增或者删除的时候，实例间的数据会进行重新的调整，这样为了整个集群的负载均衡，redis集群会重新计算整个集群的槽位分配信息，并且通过实例之间的通信各自得到最新的槽位分配信息，但是对于客户端来说它是不知道这个槽位分配信息的改变的，所以此时客户端所拥有的还是一个旧的槽位分配信息，当客户端去根据这个旧的槽位分配信息去定位到某一个实例的时候，发现这个实例的并没有这个数据（比如本来在实例1的时候但是由于集群有实例的新增，所以这个数据重新分配到了实例2），然后这个实例会发送一个MOVED命令给客户端，这个MOVED命令就包含了当前要找的槽位在哪个实例中，然后把这个实例地址返回给客户端，然后客户端就能够直接与这个返回的实例进行连接并发送请求了

如果在重定向的过程中，实例间的数据还在迁移，比如slot1中有key1，key2，key3，key4，现在槽位需要重新分配了，slot1中的数据要从实例1迁移到实例2，其中key1和key2的数据已经从实例1移到了实例2，key3和key4还在实例1，那么当客户端发送key2的请求到实例1中时（客户端还拿着旧的分配信息），实例1会发送一个ASK命令给客户端，表明当前正在数据迁移中，并且还带上了key2所在的实例地址，然后客户端拿到key2的实例地址后需要发送一个ASKING命令给实例2，然后再发送操作命令，这里ASK命令与MOVED命令不同的是，ASK命令是并不会更新客户端的本地槽位分配信息的

客户端重定向机制

客户端如何定位数据？

集群原理

水平扩展

当我们要存储的数据量日渐增多的时候，这时机器内存不够用了，而且当内存数据过多的时候，redis的持久化机制比如生成RDB要fork子进程的时候阻塞的时间就会变长，为了避免这些情况，这时我们通常有两种方案，一是垂直扩展，二是水平扩展

切片集群

架构搭建

string

hash

list

set

sorted set

基本数据类型

统计多个集合的交集，并集和差集

定义

统计手机 App 每天的新增用户数和第二天的留存用户数，利用set结构能够支持交集，并集与差集计算的特点，以时间为key，value为当天App注册的所有用户，当天与前天的差集计算可以算出每天的新增用户，当天与前天的交集计算可以算出两天内的留存用户，但是set的交集，并集与差集的计算复杂化比较高，容易造成redis阻塞，所以推荐从主从集群中选用一台从库进行运算或者是直接把数据读到客户端让客户端进行运算

场景

聚合统计

利用sorted set集合能够给元素赋予权重的特点进行排序，通常用于在面对需要展示最新列表、排行榜等场景时

排序统计

指的是集合元素的取值只有0和1两种，比如签到打卡，用0代表签到带卡，1代表没有签到打卡

利用redis的bitmap数据结构，redis的bitmap结构其实就是一个bit数组，如果我们现在有一个需求，需要统计1亿个用户在10天内的签到情况，那么我们以时间为key，value是1亿个用户的签到状态集合，每一个用户的签到状态用0或1表示然后放到这个bit数组中，最后对这10个bit数组进行与操作就可以知道连续签到10天的用户有多少了，而且使用bitmap结构能够节省空间，所以关于统计二值状态的需求可以尝试去使用bitmap实现

二值状态统计

利用set的默认去重功能统计基数

使用HyperLoglLog也可以去统计，不过HyperLoglLog统计有0.81%的误差率，如果要精确就还是得用set

基数统计

场景：最近的车站、餐馆之类的应用服务，可用使用GEO数据类型实现

位置信息服务LBS

应用场景

Bitmap

HyperLoglLog

面向LBS应用使用得数据类型

GEO

扩展数据类型

实战

Redis