本文 redis 基于 3.0
单机 redis/ 内存数据结构
对象类型
编码方式
选择条件
编码详情
string
int
long 类型整数
ptr 直接指向整数
embstr 动态字符串
长度 <=44
数组形式组织 sds，len/ 内存预分配 / 结尾有 \0
动态字符串
长度 >44
链表形式组织 sds
列表
压缩列表
长度 <64&& 元素数 <512
数组形式组织 ziplist
双端链表
长度 >=64&& 元素数 >=512
双端链表
quicklist
3.2 版本后
xx
哈希
压缩列表
长度 <64&& 元素数 <512
字典
长度 >=64&& 元素数 >=512
两个 table/ 若干桶
集合
整数集合
元素数 <512
字典
元素数 >=512
有序集合
压缩列表
长度 <64&& 元素数 <128
分支最小元素 / 分值
跳表
长度 >=64&& 元素数 >=128
字典 + 跳表
sds
保持 0 仍然可以使用部分 C 语言字符串的一些函数 Len 获取长度，保证二进制安全；多出剩余空间，每次检查 free 预分配内存，杜绝缓冲区溢出，惰性释放，减少修改字符串带来的内存重分配次数
struct sdshdr {
len = 11;
free = 0;
buf = “hello world\0”; // buf 的实际长度为 len + 1
};
分配内存，删除才释放
# 预分配空间足够，无须再进行空间分配
if (sdshdr.free >= required_len):
return sdshdr
# 计算新字符串的总长度
newlen = sdshdr.len + required_len
# 如果新字符串的总长度小于 SDS_MAX_PREALLOC
# 那么为字符串分配 2 倍于所需长度的空间
# 否则就分配所需长度加上 SDS_MAX_PREALLOC（1M）数量的空间
if newlen < SDS_MAX_PREALLOC:
newlen *= 2
else:
newlen += SDS_MAX_PREALLOC
# 分配内存
newsh = zrelloc(sdshdr, sizeof(struct sdshdr)+newlen+1)
ziplist
压缩列表使用特殊的编码来标识长度，再加上连续的内存，非常节约空间
area |<———————————————– entry ———————–>|
size 5 byte 2 bit 6 bit 11 byte
+——————————————-+———-+——–+—————+
component | pre_entry_length | encoding | length | content |
| | | | |
value | 11111110 00000000000000000010011101100110 | 00 | 001011 | hello world |
+——————————————-+———-+——–+—————+
Pre_entry_length1 字节：如果前一节点的长度小于 254 字节，便使用一个字节保存它的值。5 字节：如果前一节点的长度大于等于 254 字节，那么将第 1 个字节的值设为 254，然后用接下来的 4 个字节保存实际长度。encodinng/length/content 以 00、01 和 10 开头的字符数组的编码方式如下：
编码
编码长度
content 部分保存的值
00bbbbbb
1 byte
长度小于等于 63 字节的字符数组。
01bbbbbb xxxxxxxx
2 byte
长度小于等于 16383 字节的字符数组。
10____ aaaaaaaa bbbbbbbb cccccccc dddddddd
5 byte
长度小于等于 4294967295 的字符数组。
具体如何省内存：相比如双向，指针加 sds 的 len,free 结尾空，2*4+1+2*4（32 位指针和 Int 都是 4 字节）；压缩链表 2 / 6 字节。
添加节点在前面，要更新 pre_entry_length，next 的 pre_entry_length 只有 1 字节长，但编码 new 的长度需要 5 字节的时候可能连锁更新。next 的 pre_entry_length 有 5 字节长，但编码 new 的长度只需要 1 字节不做处理。
dict
MurmurHash2 32 bit 算法：这种算法的分布率和速度都非常好
当插入元素要检查是否应该 rehash。渐进式 rehash 或在 rehash 中直接操作 Ht[1]，否则 ht[0]
rehash 触发条件：
ratio=used/size 自然 rehash：ratio >= 1，且变量 dict_can_resize 为真（非持久化中）。强制 rehash：ratio 大于变量 dict_force_resize_ratio（目前版本中，dict_force_resize_ratio 的值为 5）当字典的填充率低于 10% 时，程序就可以对这个字典进行收缩操作
rehash 过程
ht[1] 大小为 0 的两倍，rehashidx 记录 ht[0] 的 rehash 索引位置。渐进式：在 rehash 开始进行之后（d->rehashidx 不为 -1），每次执行一次添加、查找、删除操作，_dictRehashStep 都会被执行一次。每次执行 _dictRehashStep，ht[0]->table 哈希表第一个不为空的索引上的所有节点就会全部迁移到 ht[1]->table。当 Redis 的服务器常规任务执行时，dictRehashMilliseconds 会被执行，在规定的时间内，尽可能地对数据库字典中那些需要 rehash 的字典进行 rehash，从而加速数据库字典的 rehash 进程（progress）。
整数集合
这里的 encoding 是针对整个 intset 的。当某元素长度超过时要整体升级编码方式。全存 Int 因此不需要 length。只会升级不会降级。升级过程：
扩展内容。从后开始移动，将新值插入
bit 0 15 31 47 63 95 127
value | 1 | 2 | 3 | ? | 3 | ? |
| ^
| |
+————-+
int16_t -> int32_t
跳表
相比于平衡二叉树，不需要严格的平衡，随机层数 https://www.cl.cam.ac.uk/teac…
int zslRandomLevel(void) {
int level = 1;
while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF)) // 这里取小于 0xffff 的数，有 0.25 的概率 level+1，因此 level 有 1 / 4 概率为 2, 1/16 的概率为 3 等等
level += 1;
return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}
ZSKIPLIST_MAXLEVEL=32
ZSKIPLIST_P=1/4
一个节点的平均层数 = 1/（1-p），Redis 每个节点平均指针数为 1.33
平均时间复杂度：O(logn)
zscan 在 rehash 的算法
若进行了 rehash, 先遍历小 hash 表的 v & t0->sizemask 索引指向的链表，再遍历大 hash 表中该索引 rehash 后的所有索引链表。因为 sizemask=sizehash- 1 因此低位全是 1，索引取决于 hashkey 的低 K 位，同一个节点的 hashkey 不变，若原来为 8 位 hash，hashkey 为…abcd，原索引计算为 bcd，扩展到 16 位 hash, 索引变为 abcd，若要找出所有原 bcd 索引的链表，需要在新的 hash 中找 0bcd,1bcd。因为要循环高位，所以这样从高位到低位反向来，例如：000 –> 100 –> 010 –> 110 –> 001 –> 101 –> 011 –> 111 –> 000 0000 –> 1000 –> 0100 –> 1100 –> 0010 –> 1010 –> 0110 –> 1110 –> 0001 –> 1001 –> 0101 –> 1101 –> 0011 –> 1011 –> 0111 –> 1111 –> 0000 当 rehash 时，可能会有重复，但不会有遗漏
do {
/* Emit entries at cursor */
de = t1->table[v & m1];
while (de) {
fn(privdata, de);
de = de->next;
}
/* 这里 v 从 0 开始，加 1 只取前 m1-m0 位，再与后 m0 位合并 */
v = (((v | m0) + 1) & ~m0) | (v & m0);
/* Continue while bits covered by mask difference is non-zero */
} while (v & (m0 ^ m1)); // 这里异或前 m1-m0 位全是 1，直到 while 中的 v 为全 1 后加 1 变为全 0 这里为 0 退出。因此若原来 v 为 110，8 到 32，rehash 的表将遍历 00110，01110，10110，11110
然后是下一个 v 的确认
v |= ~m0; //m0 低位全是 0，>m0 全是 1，将超出 m0 的置 1，只保留低 m0 位
v = rev(v); // 二进制翻转
v++; // 加 1，正常进位
v = rev(v); // 二进制翻转，这步之后相当于将 v 从高位 + 1 向低位进位
过期 key 删除
惰性删除：在每次获取键或 setnx 时，调用 expireIfNeeded，过期删除
定期删除：遍历每个数据库，随机从 db->expires 中最多检查 n 个 Key，过期删除。每次遍历最多 16 个库，记录断点对于利用率低于 1% 数据库跳过检查，等待缩容后处理 运行超过时长退出每个数据库连续随机抽样过期 key 个数 <n/4，则执行下一个数据库
定期删除位置：redis 的 crontab 执行过程中，删除执行时长，一般不超 cpu 的 1 / 4 时间（时间可以设置 ) 事件驱动循环中执行，间隔 20ms 执行，超过 10ms 退出（时间可以设置）持久化中过期键处理：RDB 已过期键不会保存到新创建的 EDB 文件中，载入时主服务器模式过滤过期键，从服务模式不过滤；AOF 生成无影响，重写过滤过期键；复制时 主服务器删除过期键后会给从服务器发 DEL, 从服务器除遇到 DEL 不会删除过期键
cache 淘汰机制
Redis 用来当做 LRU cache 的几种策略 (使用内存已达到 maxmemory):
noeviction：无策略，直接返会异常 allkeys-lru：所有 key 进行 LRU，先移除最久使用的（当前时间，减去最近访问的时间）allkeys-random：随机移除 volatile-random：只随机移除有过期时间的 keyvolatile-tt: 优先移除最短 ttl 的有过期时间的 key 近似的 LRU。采样逐出（默认 5 个里淘汰一个）。https://redis.io/topics/lru-c…4.0 后引入 LFU（least frequently）：大概原理是次数达到一个阶段给个计数器初始值，随时间递减。采样取最小淘汰 (源码 LFULogIncr)
单机 redis/ 持久化
RDB
存储：将 redis 的内存状态保存到磁盘里面，三种方式：save（阻塞）；bgsave（子进程负责创建 RDB，不阻塞，期间拒绝 save,bgsave, 延迟 bgrewriteaof）；自动保存设置 saveparams(校验 dirty 与 saveparam.changes，lastsave 与 saveparam.seconds)
载入：启动时自动执行，已开启 AOF 载入 AOF, 否则载入 RDB
RDB 文件结构：REDIS | db_version | database(SELECTDB | db_number | [EXPIRETIME_MS | ms] TYPE | key | value) | EOF | check_sum，value 根据 TYPE 和 ENCODING 结构不一样，比如无压缩字符串 5 hello, 压缩后字符串 REDIS_RDB_ENC_LZF 6 21 “?AA”
AOF
存储：AOF 持久化功能打开时，执行完一个写命令后，会以协议格式将命令追加到 aof_buf 缓冲区末尾。
写入：在每个外层循环，处理过文件事件和时间事件后将缓冲区内容写入 AOF 文件
同步：是否同步由 appendfsync（always,everysec,no）决定，
载入：创建伪客户端重新执行一遍 AOF 文件中的命令
重写：BGREWRITEAFO 命令，整合为不浪费空间的命令。原理：遍历数据库，读取键值，用一条 set 命令代替记录当前键值对。当键值超过了 redis.h/REDIS_AOF_REWITE_ITEMS_PER_CMD 常量的值，此键值对用多条命令来存储。非阻塞实现：为了避免使用锁保证数据安全性，用子进程进行 AOF 重写，父进程继续处理命令，用重写缓冲区解决 AOF 文件与重写时间段后数据库状态不一致问题，在创建子进程后，所有写命令即写入 AOF 缓冲区又写入重写缓冲区，将重写缓冲区内容也写入 AOF 文件，缓冲区和信号等通过管道穿传递。
集群
主从模式 复制 SLAVEOF
接收到 SLAVEOF 命令执行步骤：
设置 masterhost,masterport
发送 OK 给客户端
创建 socket connect 到主服务器，主服务器 accept
发送 ping 给主服务器，收到 PONG 继续否则断开重连
主服务器 requirepass, 从服务器 masterauth
发送端口给主服务器 REPLCONF listening-pot <port-number>
同步 SYNC/PSYNC
命令传播
1.SYNC 主服务器 BGSAVE 命令生成一个 RDB 文件，并使用缓冲区开始记录写命令 BGSAVE 结束后后发送 RDB 文件给从服务器从服务器载入主服务器将和缓冲区中写命令发送给从服务器，从服务器执行 2. 命令传播主服务器将所有写命令传播给从服务器每秒一次频率向主服务器发送 REPLCONF ACK <replication_offset> 进行心跳检测。检测网络和命令丢失主服务器配置 min-slaves-to-write n, min-slaves-max-lag m 当从服务器数量少于 3 个，或者延迟大于等于 10 将拒绝执行写命令根据 replication_offset 检测是否丢失命令，补发命令 3. 断线后重复制的优化 PSYNC 2.8 版本以上 redis 使用 PSYNC 命令代替 SYNC，断线后使用部分重同步，其他使用 SYNC 从服务器向主服务器发送命令：首次 PSYNC？-1，断线后重复制 PSYNC <runid> <offset>。主服务器返回：+FULLERSYNC <runid> <offset>，+CONTINUE , -ERR 无法识别从服务器重发 SYNC 命令 4. 上面 2 / 3 都是 2.8 以上才支持，需要用到 replication_offset，复制积压缓冲区，服务运行 ID
主服务器每次向从服务器传播 N 个字节，将自己的复制偏移量加 N。从服务器每次收到 N 个字节，将自己的复制偏移量加 N
主服务器进行命令传播时，不仅会将写命令发送给从服务器，还会将写命令写入复制积压缓冲区，先进先出
从服务器会记录正在复制的主服务器的运行 ID，网络断开后，从服务器向主服务器发送这个 ID，主服务器根据自己运行 ID 决定是部分重同步还是完全同步
哨兵
哨兵系统也是一个或多个特殊的 redis 服务器，监视普通服务器，负责下线主服务器和故障转移 1. 启动（1）初始化服务器 sentinel 不适用数据库，不再如 RDB/AOF（2）将普通 redis 服务器使用的代码替换成 sentinel 专用代码 使用不同端口，命令集（只有 PING,SENTINEL,INFO.SUBSCRIBE,UNSUBSCRIBE,PSUBSCRIBE,PUNSUBSCRIBE）（3）初始化 sentinel 状态（4）根据给定的配置文件，初始化 sentinel 的监视主服务器列表（5）创建连向主服务器的网络连接 命令连接，订阅连接（在建立后发送 SUBSCRIBE __sentinel__:hello，sentinel 需求通过接收其他服务器发来的频道信息发现未知的 sentinel）2. 获取主服务器信息 sentinel 默认 10s 一次向主服务器发 INFO 命令，获取更新 sentinelRedisInstance 的 run_id,role,slaves 的等 3. 获取从服务器信息 sentinel 会对主服务器的从服务器建立命令连接和订阅连接，也是 10s/ 次发送 INFO，更新 slaves 的 sentinelRedisInstance4. 向主服务器和从服务器发送信息 sentinel 默认 2s/ 次用命令连接向主服务器和从服务器发送 PUBLISH __sentinel__:hello “<s_ip>,<s_port>,<s_runid>,<s_epoch>,<m_name>,<m_ip>,<m_port>,<m_epoch>” 对每个与 sentinel 连接的服务器，即发送信息到频道又订阅频道接收信息。收到信息后提取参数检查若是自己的丢弃，否则根据信息更新主服务 sentinelRedisInstance 中的 sentinels，创建连接向其他 sentinel 的命令连接 5. 检测主观下线状态 sentinel 默认 1s/ 次的频率向所有主 / 从 /sentinel 服务器发送 PING 命令，有效回复为 +PONG,-LOADING,-MASTERDOWN。当一个实例在 down-after-milliseconds 内，连续向 sentinel 返回无效回复，sentinel 修改实例中 flags 加入 |SRI_S_DOWN 标识主观下线 6. 检查客观下线状态如果被 sentinel 判断为主观下线，sentinel 当前配置纪元为 0，将向其他 sentinel 发送命令 SENTINEL is-master-down-by-addr <ip> <port> <current_epoch> <runid> 返回
<down_state>
<leader_runid> // * 代表命令仅用于检测主服务器的下线状态
<leader_epoch> // 前一个只为 * 则为 0
当接收到认为下线的 sentinel 数量超过 quorum(sentinel moniter 127.0.0.1 6379 2 中 2 设置) 则 flags 加 |SRI_O_DOWN7. 选举领头 Sentinel（raft）也通过 SENTINEL is-master-down-by-addr 看来是要分开进行，带 runid。每个发现主服务器进入客观下线的 sentinel 向其他 sentinal 发送命令在一个配置 epoch 中将先到的设为局部领头，不能再更改。接收回复检查 epoch 的值和自己的相同就取出 leader_runid，如果发现自己被半数以上选择，则成为领头，epoch+ 1 如果在规定时间内未选举成功，epoch+ 1 重新选举 8. 故障转移领头进行故障转移 1）选出新的主服务器
在线的，5s 内回复过 INFO 的，与主服务器断开连接时间足够短，优先级高，复制偏移量大，runid 最小
发送 SLAVEOF no one
以 1s/ 次（其他是 10s/ 次）的频率向该服务器发送 INFO。当 role 变为 master 时继续 2
2）向下线的主服务的其他从服务器发送 SLAVEOF 命令 3）向旧的主服务器发送 SLAVEOF 命令
集群
一个集群由多个 node 组成，通过分片进行数据共享，CLUSTER MEET <ip> <port> 将各阶段加入到 cluster1. 启动一个 node 就是运行在集群模式下的 redis 服务器，在启动时若 cluster-enabled 是 yes，则开启服务器的集群模式。节点继续使用单机模式的服务器组件，只是 serverCron 函数会调用集群模式特有的 clusterCron 函数，执行集群的常规操作，例如向集群的其他节点发送 Gossip 消息，检查节点是否断线，或者检查是否需要对下线的节点进行故障转移操作等。节点数据库和单机完全相同除了智能使用 0 号出具库这和个限制，另外除了将键值对保存在数据库里边之外，节点还会用 clusterState 中的 slots_to_keys 跳跃表来保存槽和键，方便对属于某槽所有数据库键进行批量操作 2. 客户点向 A 发送 CLASTER MEET <B.ip> <B.port>A 创建 B 的 clusterNode 加入到 clusterState.nodes 中发送 MEET 给 BB 返回 PONGA 发送 PING, 握手完成 A 将 B 的信息通过 Gossip 传播给急群众其他节点 3. 槽指派，向节点发送 CLUSTER ADDSLOTS <slot> [slot …] 遍历所有输入槽，如果有已经指派的返回错误，如果都没有指派，再遍历一次：更新当前 lusterState.slots[i] 设为 Myself 更新自己 clusterNode 的 slots,numslots 属性将自己的 slots 数组通过消息发送给集群中其他节点，A 收到 B 后会把自己的 clusterState.nodes 中查找 B 对应的 clusterNode 结构，更新其中的 slots 数组；更新 clusterNode 中的 slots,numslots 属性维护整体 slots 目的：查某个槽被哪个节点处理维护单个节点 slots 目的：将某节点的所有槽指派信息发送给其他。4. 执行命令在所有的槽都指派完毕之后，集群就会进入上线状态，这是客户端就可以向集群中的节点发送数据命令了。客户端向节点发送与数据库键相关的命令时，如果键所在的槽正好就指派给了当前节点，那么节点就直接执行命令；如果键所在的槽并没有指派给当前节点，那么节点返回一个 MOVED 错误，指引客户端（redirect）至正确节点，并再次发送之前想要执行的命令。1）计算键属于哪个槽 CLUSTER KEYSLOT [key]
CRC16(KEY) & 16383
2) 若计算的 i 不对应 Myself 返回 MOVED <slot> <ip>:<port>3) 客户端根据 MOVED 错误，转向节点重新发送命令 5. 重新分片 redis 集群的重新分片操作可以将任意数量已经指派给某个节点的槽改为指派给另一个节点，并且相关的槽所属的键值对也会从源节点转移到目标节点。可以 online 下。redis 的重新分片操作时由 redis 的集群管理软件 redis-trib 负责执行的，redis 提供了进重新分片所需的所有命令，而 redis-trib 则通过向源节点和目标节点发送命令来进行重新分片操作。步骤如下：1）redis-trib 对目标节点发送 CLUSTER SETLOT < slot > IMPORTING < source_id> 准备好导入 2）redis-trib 对源节点发送 CLUSTER SETLOT < slot> MIGRATING < target_id > 准备好迁移 3）redis-trib 对源节点发送 CLUSTER GETKEYSINSLOT < slot > < count > 获得最多 count 个属于槽 slot 的键值对的键名 4）对 3 中每个键名，redis-trib 对源节点发送 MIGRATE < key_name> 0 < timeout> 迁移 5）重复 3 和 4，知道槽中的键值对迁移到目标节点 6）redis-trib 向任意节点发送 CLUSTER SETLOT < slot> NODE < target_id>，将槽指派给目标节点，并通过消息告知整个集群，最终所有节点都会知道槽 slot 已经指派给了目标节点。6.ASK 错误 处理正在迁移中槽错误接到 ASK 错误的客户端会根据错误提供的 IP 地址和端口号，转向至正在导入槽的目标节点，然后向目标节点发送一个 ASKING 命令，再重新发送原本想要执行的命令。ASKING 命令加 client.flags|=REDIS_ASKING。正常客户端发送一个关于槽 i 的命令，而槽 i 又没有指派给这个节点的话，会返回 MOVED 错误，设置了 REDIS_ASKING 后，则会破例执行 MOVED 错误代表槽的负责权已经从一个节点转移到另一个，每次遇到都自动发到 MOVED 指向的节点。而 ASK 只是迁移槽中临时的，下次对下次有影响 7. 复制与故障转移 1）复制 redis 集群中的节点分为主节点和从节点，其中主节点用于处理槽，而从节点则用于复制主节点，并在被复制的主节点下线之后代替下线的主节点继续处理命令请求。设置从节点：CLUSTER REPLICATE < node_id> 让接收命令的节点成为 node_id 的从节点接收到该命令的节点首先会在自己的 clusterState.nodes 字典里面找到 node_id 对应的节点 clusterNode 结构，并将自己的 clusterState.myself.slaveof 指针指向这个结构；节点会修改自己 clusterState.myself.flags 中的属性，关闭原来的 REDIS_NODE_MASTER 标识，打开 REDIS_NODE_SLAVE 标识；调用复制代码，相当于向从节点发送 SLAVEOF <master_ip> <master_port>。2）故障检测集群中的每个节点都会定期地向集群中的其他节点发送 PING 消息，如果规定时间内没有返回 PONG，发送消息的节点就会把接受消息的节点标记为疑似下线 PFAIL。clusterNode 的 flags 标识（REDIS_NODE_PFAIL）集群中各节点通过互相发送消息的方式交换集群中各个节点的状态信息，当 A 通过消息得知 B 认为 C 进入疑似下线，A 在自己 clusterState.nodes 中找到 C 对应的 clusterNode 结构将 B 的下线报告添加到该 clusterNode 的 fail_reports 中半数以上主节点都报告 x 意思下线，则标记为 FAIL，将主节点 x 标记为下线的节点向集群广播 FAIL 消息，所有接受者都将 x 标记为 FAIL3）故障转移当一个从节点发现自己复制的主节点进入了下线状态的时候，从节点将开始对下线主节点进行故障转移，步骤如下：
选举新的主节点
新的主节点执行 SLAVEOF no one 命令，成为新的主节点
新的主节点将下线主节点的槽指派给自己
新的主节点向集群广播 PONG 消息，表明自己接管了原来下线节点的槽
新的节点开始接收和自己复制处理槽有关的命令请求。
选举新的主节点
同样基于 Raft 实现
从节点广播 CLUSTERMSG_TYPE_FAILOVER_AUTH_REQUEST，未投过票的主节点返回 CLUSTERMSG_TYPE_FAILOVER_AUTH_ACK。配置纪元自增，半数以上。
8. 消息消息由消息头（header）和消息正文（data）组成。cluster.h/clusterMsg 结构表示消息头，cluster.h/clusterMsgData 联合体指向消息的正文。节点消息分为 5 类：1）MEETA 接到客户端发送的 CLUSTER MEET B 命令后，会向 B 发送 MEET 消息，B 加入到 A 当前所处的集群里 2）PING 每个节点默认 1s/ 次从已知节点随机选 5 个，对最长时间未发送 PING 的节点发送 PING，或当有节点超过 cluster-node-timeout 的一半未收到 PONG 也发送 PING，检查节点是否在线 3）PONG 确认 MEET,PING; 或主动发送让集群中其他节点立即刷新该节点信息，比如故障转移操作成功后以上三种消息都使用 Gossip 协议交换各自不同节点的信息，三种消息的正文都是由两个 cluster.h/clusterMsgDataGossip 结构组成发送者从自己已知节点列表中随机选择两个节点 (主、从), 保存在两个 clusterMsgDataGossip 结构中。接收者发现节点不在已知节点列表则与节点握手，否则更新信息。注意 PONG 也会带两个回去 4）FAIL 主节点判断 FAIL 状态，广播 clusterMsgDataFail。（gossip 随机会慢）5）PUBLISH 当节点收到一个 PUBLISH，会执行这个命令并向集群中广播一条 PUBLISH。即向集群中某个节点发送 PUBLISH <channel> <message> 将导致集群中所有节点都向 channel 频道发送 message 消息。要让集群所有节点都执行相同命令，可以广播，但还要用 PUBLISH 发是因为直接广播这种做法，不符合 redis 集群的“各个节点通过发送和接收消息来进行通信”这一规则。clusterMsgDataPublish
原生 Gossip 过程是由种子节点发起，当一个种子节点有状态需要更新到网络中的其他节点时，它会随机的选择周围几个节点散播消息，收到消息的节点也会重复该过程，直至最终网络中所有的节点都收到了消息。这个过程可能需要一定的时间，由于不能保证某个时刻所有节点都收到消息，但是理论上最终所有节点都会收到消息，因此它是一个最终一致性协议。每次散播消息都选择尚未发送过的节点进行散播（有冗余）
codis
Codis 3.x 由以下组件组成：
Codis Server：基于 redis-3.2.8 分支开发。增加了额外的数据结构，以支持 slot 有关的操作以及数据迁移指令。具体的修改可以参考文档 redis 的修改。
Codis Proxy：客户端连接的 Redis 代理服务, 实现了 Redis 协议。除部分命令不支持以外 (不支持的命令列表)，表现的和原生的 Redis 没有区别（就像 Twemproxy）。对于同一个业务集群而言，可以同时部署多个 codis-proxy 实例；不同 codis-proxy 之间由 codis-dashboard 保证状态同步。Codis Dashboard：集群管理工具，支持 codis-proxy、codis-server 的添加、删除，以及据迁移等操作。在集群状态发生改变时，codis-dashboard 维护集群下所有 codis-proxy 的状态的一致性。这里和 zk 交互保证一致，数据迁移，主从增加等都通过这个对于同一个业务集群而言，同一个时刻 codis-dashboard 只能有 0 个或者 1 个；所有对集群的修改都必须通过 codis-dashboard 完成。Codis Admin：集群管理的命令行工具。可用于控制 codis-proxy、codis-dashboard 状态以及访问外部存储。Codis FE：集群管理界面。多个集群实例共享可以共享同一个前端展示页面；通过配置文件管理后端 codis-dashboard 列表，配置文件可自动更新。Storage：为集群状态提供外部存储。提供 Namespace 概念，不同集群的会按照不同 product name 进行组织；目前仅提供了 Zookeeper、Etcd、Fs 三种实现，但是提供了抽象的 interface 可自行扩展。
整个集群总共 1024 个 slot (槽) 每个 redis group 对应着 个 slot range (如: 0~127)，slot range 存储在 zk 中每个 key 请求时，crc32(key) % 1024 映射到 个 slot_id，proxy 通过 slot_id 找到对应的 redis group 读写 数据集群的扩容缩容，都是通过 slot 迁移来实现，是 个两 段式提交的过程。迁移时并不 影响线上单 key 读写访问 1. 数据迁移 migrateslot(slotid,from,dest) 一台机器上有很多 redis 实例（一个实例一个 groupid），迁移：sid=>gid, 多个迁移会创建任务队列放 zkzookeeper 同步配置，放迁移队列，提供可靠的多 rpc, 每个 codis-proxy 中有配置，sid=>gid/gid=>sid 的，zk 除了存储路由信息，同时还作为一个事件同步的媒介服务，比如变更 master 或者数据迁移这样的事情，需要所有的 proxy 通过监听特定 zk 事件来实现。可以说 zk 被我们当做了一个可靠的 rpc 的信道来使用。因为只有集群变更的 admin 时候会往 zk 上发事件，proxy 监听到以后，回复在 zk 上，admin 收到各个 proxy 的回复后才继续。dash 专门开启一个协程从 zk 的任务队列中获取 slot 迁移，一个一个进行迁移有两个阶段，第一阶段状态改为 pre_m。若 proxy 都确认，将状态改 m。向所在的 redis-server 发送迁移命 dash 修改到 zk,proxy 监听回复到 zk，dash 监听 zk 进行状态机的变更，同步配置做配置的下发同步
三次配置更改同步：第一次 fillslot 将 BackendAddr 由 OriginGroupMaster 改写为 TargetGroupMaster，这一步操作相当于读写临界区资源 BackendAddr，所以必须带写锁，而 MigrateFrom 只是顺便改了而已第二次 fillslot 相当于取消了第一次的写锁，但是如果 Promoting 在执行的话，不应该取消 Promoting 设置的锁第三次 fillslot 取消了 MigrateFrom
迁移过程中读写请求：分发请求时存在一个 prepare 方法，这一步会获取到该 key 对应的 slot 是否有 MigrateFrom 如果有的话，会使用 SLOTSMGRTTAGONE 将这个 key 从 MigrateFrom 代表的 redis 强制迁移到 Backend 代表的 redis 里去，迁移完成以后再去访问 Backend 获得这个 ke 这样就能解决，如果被迁移的 slot 中的 key，刚好被访问时，产生的一致性问题了
迁移与主从切换的冲突：migrate 基本上不依赖 lock，当发生数据冲突时，由强制迁移这个 key 来解决一致性问题，和 lock 基本上没太大关系，lock 主要是针对 promote 设计的
2. 主从切换哨兵模式 3. 自平衡算法
1. 使用自动负载均衡需要满足一个前提：所有 codis-server 的分组 master 必须配置 maxmemory。
2. 各组 codis-server 分配多少个 slot 是由其 maxmemory 决定。比如：A 组 maxmemory 为 10G, B 组 maxmory 为 1G，进行自动均衡处理后，A 组分配的 slot 会是 B 组的 10 倍。
3. 自动负载均衡并不会达到绝对意义上的均衡，其只做到 maxmemory 与分配的 slot 个数的比例均衡。无法达到操作次数的均衡。
4. 自动负载均衡的处理过程中，如果发现存在 maxmemory 与分配的 slot 个数比例不均衡时，则会进行发起 slot 迁移的操作。达到均衡目的的前提下，此过程中会做到尽量减少 slot 的迁移。
codis 和 twemproxy 最大的区别有两个：一个是 codis 支持动态水平扩展，对 client 完全透明不影响服务的情况下可以完成增减 redis 实例的操作；一个是 codis 是用 go 语言写的并支持多线程而 twemproxy 用 C 并只用单线程。后者又意味着：codis 在多核机器上的性能会好于 twemproxy；codis 的最坏响应时间可能会因为 GC 的 STW 而变大，不过 go1.5 发布后会显著降低 STW 的时间；如果只用一个 CPU 的话 go 语言的性能不如 C，因此在一些短连接而非长连接的场景中，整个系统的瓶颈可能变成 accept 新 tcp 连接的速度，这时 codis 的性能可能会差于 twemproxy。
某自研集群
数据量的限制。1024. 变更比想象的频繁 zk 依赖，zk 出问题，路由错误无法发现，redis 没有路由信息 => 某自研集群基于 redis 集群加一层 proxy，客户端与集群连接，单进程单线程（mget 岂不是很慢 =》用了异步 epoll 的模式，发完了不等）1. 建立链接模块。与客户端和 redis-clsuster 建立链接。2. 命令处理模块。区分单次操作命令和多次操作命令（Mget/Mset）。3. 路由模块。维护 redis-cluster 的 nodes 路由信息。（原来 client 随便打，错了 moved 这记录了下）基本都靠 redis-cluster
关于双活
方案 1：方案 2：codis 收到命令后发送给两个机房的 redis 方案 3：
redis 一些优化和问题
白名单动能可以用 Bit-array/bitmaps 代替 set 实现
setex 代替 set,expire，有两次网络
内存提出策略：近似 lru, 对性能妥协，qps 太大时也淘汰不过来，可能会有一些写不进来
大 key 无法分片导致无法水平扩容来解决问题。所以一个 key 不要存特别大的数据，原则上一个 key<100k
同一个实例，同一个 Key,QPS 特别大的时候，仍然扛不住，要避免热 key，静态配置类的 Key 迁出 redis 放代码里，其他热 key 要考虑高并发写入的问题。4 万的 pks 针对同一 key 扛不住，可以转为双缓存或者改一个有常驻内存的语言写。Php 的双缓存可以通过 fpm 的 apcu，redis,mysql 来做。
应用 redis 时要预测 qps, 数据容量，内存中的量和磁盘代码可能还不一致。
热 key
请求多，部分 key 集中于同一机器，无法通过增加机器解决 =》1. 读：本地缓存（客户端本地 redis/ 程序 /mysql 服务端本地 就是副本扩展多份多机器）需要提前获取热点，容量有限，不一致时间长，热点 key 遗漏。写：取租约，限流 2. 读写分离。读复制多份，负载均衡未知热 key 热点 key 的采样。线程抢锁开始采样，外层 N 次，分 1024 个桶，看每个桶中是否有热点，用标准差。再对桶进行 M 此采样，选出热点 key. 客户端从服务器获取这批 key 进行本地缓存写操作删除本地缓存。根据容量或者过期淘汰，在过期淘汰时为防止击穿，首次发现过期后延长一点过期时间，只有首次的去获取新的 key 更新。