[TOC]
#2 简单动态字符串 SDS
Redis中C字符串只作为不修改的字符串字面量,如日志.其它的用SDS
sds.h/sdshdr
struct sdshdr{
int len; //已使用长度(不包括'\0')
int free; //未使用长度
char buf[]; //与c字符串一样
}
SDS与C串区别:
- 获得长度快O(1)
- 杜绝缓冲区溢出
- 减少修改字符串时的内存重分配(1空间预分配-未超过1M时,使用多少,也会分配出多少未使用的空间;超过1M时,分配1M的未使用空间2惰性空间释放-即默认不释放缩短后多余空间,得手动释放)
- 可以存图片这样的二进制文件信息,因为不会以\0作为结束标志
- 兼容部分C串函数
#3 链表
typedef struct listNode{
struct listNode *prev;
struct listNode *next;
void *value;
}listNode;
typedef struct list{
//表头节点
listNode *head;
//表尾节点
listNode *tail;
//链表包含的节点数
unsigned long len;
//节点值复制函数
void *(*dup)(void *ptr);
//节点值释放函数
void (*free)(void *ptr);
// 节点值对比函数
int (*match)(void *ptr, void *key);
}list;
#4 字典
哈希表
dict.h/dictht
typedef struct dictht{
//哈希表数组
dictEntry **table;
//表大小
unsigned long size;
//用于计算索引值,等于size-1
unsigned long sizemask;
//已有节点数
unsigned long used;
}dictht;
哈希表节点
dict.h/dictEntry
typedef struct dictEntry{
void *key;
//value
union{
void *val;
uint64_t u64;
int64_t s64;
}v;
//下个哈希表节点,用来解决键哈希时冲突的情况
struct dictEntry *next;
}dictEntry;
字典
dict.h/dict
typedef struct dict{
//类型特定函数
dictType *type;
//私有数据
void *privdata;
//哈希表(一般只用ht[0]这张表,只有当rehash时,把新的表放在ht[1]中,结束后就释放0的空间,把1改成0,1重新开辟新的空间)
dictht ht[2];
//rehash索引, 当rehash不在进行时,值为-1
int trehashidx;
}
typedef struct dictType{
//计算哈希值函数
unsigned int (*hashFunction)(const void *key);
//复制键的函数
void *(*keyDup)(void *privdata, const void *key);
....
}
- 索引index=hash&dict->ht[x].sizemask,即保存在ht[x]哈希表的第index位置.当索引值一样时,发生键冲突,采用链表的方式解决冲突
- rehash
- 扩展,ht[1]取第一个>=ht[0].used*2的2^n(条件:1.服务器没执行BGSAVE或者BGREWRITEAOF命令,且负载因子>=1;2.在执行...命令,且负载因子>=5)
- 收缩,取第一个>=ht[0].used的2^n(当负载因子<0.1时)
过程:
- 为ht[1]分配空间
- 把rehashidx设为0
- rehash期间,对字典CURD,会顺带把ht[0]表在rehashidx索引上的所有键值对rehash到ht[1].完成后,rehashidx++
- 随着字典操作的不断执行,0表会全rehash到1表上,rehashidx变为-1,完成rehash
rehash完0表中删去,添加到1表中;新添加的对全放1表中;查询时0表找不到会从1表中找
跳跃表节点
redis.h/zskiplistNode
创建表节点时,会随机生成1-32的值作为level数组大小,越大概率越低
typedef struct zskiplistNode{
//层
struct zskiplistLevel{
//前进指针
struct zskiplistNode *forward;
unsigned int span;
}level[];
struct zskiplistNode *backward;
//根据分值大小排序
double score;
//成员对象
robj *obj;
}zskiplistNode
typedef struct intset{
//编码方式
uint32_t encoding;
uint32_t length;
int8_t contents[];
}
- 有序,不重复
- 当有无素过大时,进行升级,全部替换
- 不支持降级
|z||||
对象类型有:REDIS_STRING字符串, REDIS_LIST列表, REDIS_HASH哈希, REDIS_SET集合, REDIS_ZSET有序集合
- 字符串对象
int编码；大于32字节时,编码为raw;小等于32字节时,编码为embstr(优化的用于保存短字符串的方式:redisObject,sdshdr两块连续内存区域一次分配,也只需要释放一次,能够更好利用缓存带来的优势)
Redis中所有数据库都保存在redisServer.db数组中,数据库由dict和expires两个字典构成
数据库的键是一个字符串对象,值是任意一种Redis对象
- 启动Redis时,若启动RDB,则载入RDB文件时:
- 以主服务器模式运行,过期键不会载入;
- 以从服务器模式,载入所有键,与主服务器同步时删除过期键
- 以AOF持久化模式运行,当过期键被惰性或定期删除时,会向AOF文件append一条DEL命令,显式记录该键已被删除
执行AOF重写时,已过期的键不被重写
- 复制模式
- 主删除过期键后,会向所有从发送DEL命令,告知从删除该键
- 从执行客户端的读命令时,对所有键一致对待
- 从只有收到主的DEL时,才会删过期键
数据库通知:SUBSCRIBE,订阅消息包括两种:对某个键执行什么命令,某个命令被哪些键执行了
SAVE:会阻塞进程,到RDB文件创建完毕,期间无法处理任何命令请求
BGSAVE:会开子进程负责创建,服务器(父进程)继续运行.执行期间,拒绝SAVE,BGSAVE命令,BGREWRITEAOF命令会在GBSAVE命令结束后执行.若BGREWRITEAOF在执行,则BGSAVE会被拒绝
实际执行由rdb.c/rdbSave完成
RDB载入在服务器启动时自动检测载入,载入期间处于阻塞态
AOF更新频率比RDB高,若开启AOF,则优先AOF还原,只有关闭后才会使用RDB还原
###自动间隔性保存
默认每隔100ms执行一次serverCron,满足任一条件就执行保存
服务器默认save条件设置(BGSAVE):900s内至少1次修改,300s内10次修改....
save 900 1
save 300 10
save 60 10000
一次修改三个键算三次修改,dirty+3
struct redisServer{
//记录保存条件的数组
struct saveparam *saveparams;
//修改计数器(距离上次成功SAVE,BGSAVE后进行了多少次修改)
long long dirty;
//上一次执行保存时间(距离上次成功SAVE,BGSAVE的时间)
time_t lastsave;
}
struct saveparam{
time_t seconds;
int changes;
}
###RDB文件结构
| REDIS |
db_version |
databases |
EOF |
check_sum |
| REDIS |
db_version |
databases |
EOF |
check_sum |
普通客户端被关闭原因:
- client进程网络连接关闭
- client向server发送带有不符合协议格式的命令请求
- client成为CLIENT KILL命令的目标
- 设置了timeout选项.当client空转时间超过timeout时.例外情况client是主服务器(打开REDIS_MASTER标志),从服务器(打开REDIS_SLAVE标志),正在被BLPOP等命令阻塞(打开REDIS_BLOCKED标志),或正执行SUBSCRIBE,PSUBSCRIBE等订阅命令,超时也不会关闭
- client发送的命令请求大小超过输入缓冲区限制大小(默认1G)
- 要发送给client的命令回复超过了输出缓冲区的限制大小(hard limit:超过立即关闭;soft limit: 超过后开始监视,如一直超出且持续时间超过设定值,则关闭；如果不再超出,则不被关闭,且obuf_soft_limit_reached_time也会被清零)
AOF伪客户端在载入完成后会被关闭
####服务器命令请求执行过程:
- client把命令请求转换成协议格式,通过socket发送到服务器
- server读取命令,存入clientStatus的输入缓冲区里
- 读取分析命令,提取命令及参数和参数个数放入argv和argc中
- 调用命令执行器执行
####serverCron函数
- 更新服务器时间缓存:redisServer中time_t unixtime; long long mstime;两个字段,每100ms更新一次,精度不高,只在对时间精度要求不高的场景使用
- 更新LRU时钟:redisServer中unsigned lruclock字段,用于计算键的空转时间,10s更新一次;每个redis对象都有的unsigned lru,保存对象最后一次被命令访问的时间.空转时间=lruclock-lru
- 更新服务器每秒执行命令次数,100ms一次,估算
- 更新内存峰值
- 处理SIGTERM信号:处理该信号时打开关闭标识shutdown_asap,serverCron每次都会检查该标识,为1时关闭服务器关闭前会先进行RDB持久化
- 执行clientsCron:客户端连接超时释放;输入缓冲区在上次执行命令请求后超过一定的长度,会被释放,并重新创建一个默认大小的缓冲区
- databaseCron:删除过期键,对字典进行收缩
- 执行被延迟的BGREWRITEAOF:执行BGSAVE期间,发来BGREWRITEAOF命令,会在save结束后执行
- 会检查BGSAVE,BGREWRITEAOF的子进程是否完成操作:若rdb_child_pid和aof_child_pid都为-1,会执行1)是否有BGREWRITEAOF被延迟 2)是否满足自动保存条件,如果有且没有其它持久化操作,则开始新的BGSAVE 3)检查AOF重写条件是否满足,满足且没其它持久化操作,开始新的BGREWRITEAOF
- 将AOF缓冲区中的内容写入AOF文件.若开启AOF,且AOF缓冲区里有待写入的数据
- 关闭异步客户端:输出缓冲区大小超出限制
- 增加cronloops:记录执行serverCron的次数
sentinel监视到主服务器下线时,会自动将从服务器上升为主服务器,若其上线,则会将它转成从服务器
redis.h/redisServer结构
struct sentinelState{
//当前纪元,用于实现故障转移
uint64_t current_epoch;
//保存被监视的服务器,指向sentinelRedisInstance结构(可以是主,从服务器或其它sential)的指针
dict *masters;
//是否进入TILT模式
int tilt;
//目前正在执行的脚本数量
int running_scripts;
//进入TILT时间
mstime_t tilt_start_time;
//最后一次执行时间处理器的时间
mstime_t previous_time;
//包含了所有需要执行的用户脚本
list *scripts_queue;
}sentinel;
####sentinel会
- 与监视的主服务器间创建两个异步网络连接:命令连接(收发命令),订阅连接(订阅_sentinel_:hello频道)
- 默认10s1次向被监视的主服务器发送INFO命令,会返回主服务器及从服务器的信息.会检查sentinelRedisInstance的slaves里是否有对应的从服务器,有则更新,没有新建
- 出现新的从服务器时,会创建连接到从服务器的命令和订阅连接,默认10s一次发送INFO
- 2s1次通过命令连接向所有主从服务器发送PUBLISH sentinel:hello "<s_ip>.....";通过订阅连接向该频道接收信息
- 当sentinel向_sentinel_:hello频道发送消息时,所有订阅该频道的sentinel都会收到该消息,若是自己发出的则丢弃,否则对相应主服务器的实例进行更新
- sentinelRedisInstance中的sentinels保存了除自己以外的所有监视该主服务器的sentinel
- 当发现新的sentinel时则互相建立命令连接
- 检测主观下线状态:1次/s向所有创建了命令连接的服务器(主从及其它sentinel)发送PING,回复有有效回复(+PONG,-LOADING,-MASTERDOWN),及其它无效回复.当超过down-after-milliseconds没有有效回复,则进入主观下线状态.这也成为判断该主服务器的所有从服务器及其它sentinel主观下线的标准
- 检测客观下线:会向其它sentinel询问,若其它认为主观下线的数量超过一定数时,认为客观下线.并会进行选举,并由leader进行主服务器的故障转移,规则如下:
- 进行一次选举,epoch自增一次
- 一个纪元里,所有sentinel都有一次选举的机会,并且在该纪元内不能更改
- 每个发现主服务器客观下线的sentinel都会要求别人把自己设为局部leader
- 当一个sentinel(源)向另一个(目标)发送is-master-down-by-addr时,且runid不是*而是源sentinel的运行ID时,表示源要求目标把前者设为后者的局部leader
- 先到先得,最早发送上述命令的将成为目标的局部leader
- 目标收到is-master-down-by-addr,会回复源自己的局部leader的runid和configuration epoch.
- 源收到回复后,检查与自己的configuration epoch是否相同,相同且leader_runid与源的runid一致,则目标将把源sentinel设置成局部leader
- 如果有半数以上的sentinel把某个设为局部leader,则其成为leader
- 如果一定时间内未选出leader.则一段时间后继续选举直到选出Leader.
一共有16384个slot,节点会与分配的slot对应起来,放在clusterState.slots数组中,每个slot对应一个clusterNode.clusterNode.slots数组中记录了slot指派信息,用一个二进制位来表示,1为使用,0为不使用
clusterState中zskiplist *slots_to_keys,保存slot与数据库key的关系,key先通过CRC生成校验和,再&16384进行哈希,其中跳跃表的score存slot,object存key
MOVED错误会把所有请求转向该错误指向的节点
ASK只是在接下来的一次请求转至指示的节点,之后仍然会把请求转向当前节点
节点分为主从节点:主用于处理slot,从用于复制某个主节点,主下线时,从替代它.
节点成为从节点,并开始复制某主节点这一消息会通过消息发送给所有其它节点.
- 每个节点都会向其它节点定期发送PING,如果没在规定时间内返回PONG,就标记疑似下线(probable fail, PFAIL)
- 当主节点A收到主B认为主C疑似下线消息时,A会在C的clusterNode中添加list *fail_reports
struct clusterNodeFailReport{
//报告目标节点下线的节点,即谁发的此报告,这里为B
struct clusterNode *node;
//最后一次从node节点收到下线报告的时间
//用来判断下线报告是否过期,与当前时间相差太久会被删除
mstime_t time;
}
- 当半数以上负责处理slot的主节点都把某主节点x报告为疑似下线时,它将被标记为已下线FAIL,并通知所有节点,其它节点会立即标记
当从节点发现在复制的主节点下线,会执行:
- 选举一个从节点作为主节点:有投票权的主给第一个发现的从投票,超过半数的成为新的主
- leader执行SLAVEOF no one,成为主
- 把slot指派改成指向自己
- 向集群广播PONG,通知已接管
- 开始接收新的命令请求
- MEET:向接收者发送,请求对方加入集群
- PING:
- 默认每隔1s随机选出5个,找最长时间没发送过的发送,来检测对方是否在线
- A最后一次收到B的PONG消息时间距离现在,超过A的cluster-node-timeout的一半,A也会向B发.(防止长时间没随机选中B导致对B的信息更新滞后)
- 收到PING和MEET时,返回.
- 向集群发送,让其它节点刷新对自己状态的改变.(如故障转移成功后)
- FAIL:只存有下线节点的名字(集群中节点名字唯一)A判断B下线时,广播,收到的立即对B标记下线(因为Gossip协议要等待,传播速度会变慢)
- PUBLISH:节点接收到执行完时会广播,所有接收的点都会执行相同的PUBLISH命令
Gossip协议由MEET,PING,PONG实现,发送时会往clusterMsgDataGossip gossip[1]中添加两个随机的节点信息,接收方收到时,进行更新这两个点的信息
客户端向集群中的点发送PUBLISH 时,接收的节点会向该channel发送message,并广播一条PUBLISH消息,所有其它点也会发送.
struct redisServer{
//保存所有频道的订阅关系
dict *pubsub_channels;
//保存所有模式订阅关系
//其中存放着pubsubPattern结构
list *pubsub_patterns;
}
typedef struct pubsubPattern{
//订阅模式的客户端
redisClient *client;
robj *pattern;
}pubsubPattern;
pubsub_channels的key为频道名,value为客户端链表
MULTI事务开始,输入非EXEC,DISCARD,WATCH,MULTI四个命令入队,EXEC执行事务,执行完把返回结果放到队列中,然后清除事务标记,再返回结果
WATCH是乐观锁,在事务开启后,执行前监视某些数据库键,一旦修改,拒绝执行事务
typedef struct redisDb{
dict *watched_keys;
}
- 其中key为被监视的键,value为记录监视该键的客户端
- 执行修改命令如:SET,LPUSH,SADD,ZREM,DEL,FLUSHDB等后,会调用multi.c/touchWatchKey函数,如果该键被监视,则该客户端的REDIS_DIRTY_CAS被打开
- 服务器收到EXEC命令时,会根据是否有REDIS_DIRTY_CAS来决定执行事务:打开的话拒绝事务
- 原子性:Redis事务不支持事务回滚,中间有命令错误,后续命令也会执行
- 一致性:错误命令不入队;出错命令进行相应处理,不执行;服务器停机:若无持久化,则数据库空白,数据一致.若RDB或AOF,则会恢复还原到一个一致状态,找不到则为空白.
在AOF模式下,appendfsync设为always时,事务具有耐久性.
