Redis：独立功能的实现

1. 发布与订阅

Redis 的发布与订阅功能由 PUBLISH、(UN)SUBSCRIBE、PSUBSCRIBE 等命令组成

1
2
3
4
5
6
7
8

struct redisServer {
	
	// 保存所有频道的订阅关系
	dict *pubsub_channels;

	// 保存所有模式的订阅关系
	list *pubsub_patterns;
}

Redis 将所有频道的订阅关系都保存在服务器状态的 pubsub_channels 字典里面, 这个字典的键是某个被订阅的频道, 而键的值则是一个链表, 链表里面记录了所有订阅这个频道的客户端

• 服务器数据结构在 pubsub_channels 字典保存了所有频道的订阅关系: SUBSCRIBE 命令负责将客户端和被订阅的频道关联到这个字典里面, 而 UNSUBCRIBE 命令则负责解除客户端和被退订频道之间的关联

• 服务器数据结构在 pubsub_patterns 链表保存了所有模式的订阅关系: PSUBCRIBE 命令负责将客户端和被订阅的模式记录到这个链表中, 而 PUNSUBSCRIBE 命令则负责移除客户端和被退订模式之间的关联

• PUBLISH 命令通过访问 pubsub_channels 字典来向频道的所有订阅者发送消息, 通过访问 pubsub_patterns 链表来向所有匹配频道的模式的订阅者发送消息

• PUBSUB 命令的三个子命令都是读取通过 pubsub_channels 字典和 pubsub_patterns 链表中的信息来实现的

2. 事务

Redis 通过 MULTI、EXEC、WATCH 等命令来实现事务(transaction)功能

WATCH 命令是一个乐观锁, 它可以在 EXEC 命令执行之前, 监事任意数量的数据库键, 并在 EXEC 命令执行时, 检查被监视的键是否至少有一个已经被修改过了, 如果是的话, 服务器将拒绝执行事务, 并向客户端返回代表事务执行失败的空回复

• 事务在执行过程中不会被中断, 当事务队列中的所有命令都被执行完毕之后, 事务才会结束

• 带有 WATCH 命令的事务会将客户端和被监视的键在数据库的 watched_keys 字典中进行关联, 当键被修改时, 程序会将所有监视被修改键的客户端的 REDIS_DIRTY_CAS 标志打开

• 只有在客户端的 REDIS_DIRTY_CAS 标志未被打开时, 服务器才会执行客户端提交的事务, 否则将拒绝

• Redis 的事务总是具有 ACID 中的原子性、一致性和隔离性, 当服务器运行在 AOF 持久化模式下, 并且 appendfsync 选项的值为 always 时, 事务也具有耐久性

3. 排序

• SORT 命令通过将被排序键包含的元素载入到数组里面, 然后对数组进行排序来完成对键进行排序工作

• 在默认情况下, SORT 命令假设被排序键包含的都是数字值, 并且以数字值的方式来进行排序

• 如果 SORT 命令使用了 ALPHA 选项, 那么 SORT 命令假设被排序键包含的都是字符串值, 并且以字符串的方式来进行排序

• SORT 命令的排序操作由快速排序算法实现

• 当 SORT 命令使用了 BY 选项时, 命令使用其他键的值作为权重来进行排序操作

• 除了 GET 选项之外, 调整选项的摆放位置不会影响 SORT 命令的排序结果

4. 慢查询日志

Reids 的慢日志查询功能用于记录执行时间超过给定时长的命令请求, 用户可以通过这个功能产生的日志来监视和优化查询速度

• Redis 服务器将所有的慢查询日志保存在服务器状态的 slowlog 链表中, 每个链表节点都包含一个 slowlogEntry 结构, 每个 slowlogEntry 结构代表一条慢查询日志

• 打印和删除慢查询日志可以通过遍历 slowlog 链表来完成

• slowlog 链表的长度就是服务器所保存慢查询在日志的数量

• 新的慢查询日志会被添加到 slowlog 链表的表头, 如果日志的数量超过 slowlog-max-len 选项的值, 那么多出来的日志会被删除

5. 监视器

• 客户端可以通过执行 MONITOR 命令转换成监视器, 接收并打印服务器处理的每个命令请求信息

• 当一个客户端变为监视器时, 该客户端的 REDIS_MONITOR 标识会被打开

• 服务器将所有监视器都记录在 monitors 链表中

• 每次处理命令请求时, 服务器都会遍历 monitors 链表, 将相关信息发送给监视器

Redis：多机数据库的实现

1. 复制

1.1 旧版本复制功能的实现(2.8版本以前)

复制功能分为 同步(sync) 和 命令传播(command propagate) 两个操作

SYNC 命令是一个非常耗费资源的操作, 生成 RDB 占据了大量的 CPU, 内存和磁盘 I/O 资源, 传输 RDB 占据了大量的网络资源, 接收并载入 RDB 会导致阻塞, 而旧版本的复制无法高效的完成: 断线重复制的情况, 即从服务器断线后的一致性保证, 哪怕只有几秒的短线, 只能通过 SYNC 来保证

1.2 新版本复制功能的实现(2.8版本以后)

PSYNC 命令, 具备完整重同步(适用于初次复制的情况) 和 部分重同步(适用于断线重复制)

部分重同步功能由以下三个部分构成:

1. 主服务器的复制偏移量(replication offset) 和 从服务器的复制偏移量

2. 主服务器的复制积压缓冲区(replication backlog)

3. 服务器的运行 ID(run ID)

通过对比主从服务器的复制偏移量, 程序可以很容易的指导主从服务器是否处于一致状态

复制积压缓冲区是一个固定长度的FIFO队列, 保存着主服务器的写命令, 如果它里面操作的复制偏移量小于主从不一致的偏移量, 则完整重同步, 反之大于, 则部分重同步, 这个复制积压缓冲区的大小可以配置, 约等于:

service_reready_seconds write_size_per_second 服务平均恢复时长 每秒写命令产生的数据大小

服务器的运行ID是检测 从服务器前后是否连接的是相同的主服务器, 若是的话则部分重同步, 若不是只能完整重同步

• 在复制操作刚开始的时候, 从服务器会成为主服务器的客户端, 并通过向主服务器发送命令请求来执行复制操作, 而在复制操作的后期, 主从服务器会相互成为对方的客户端, 涵盖了: 设置主服务器的地址和端口/建立套接字连接/发送PING命令/身份验证/发送端口信息/同步/命令传播 等操作

• 主服务器通过向从服务器传播命令来更新从服务器的状态, 保持主从服务器一致, 而从服务器则通过向主服务器发送命令来进行心跳检测, 以及命令丢失检测(偏移量校验)

2. Sentinel

Sentinel 是 Redis 高可用性的解决方案: 由一个或多个 Sentinel 实例组成的 Sentinel 系统, 监视着 Redis 的主从服务器, 当发现主服务器下线了, 会从从服务器中选择一个当主服务器, 并继续监控下线的主服务器, 一旦恢复上线, 会设置为新的主服务器的从服务器

启动一个 Sentinel 命令如下:

1
2
3

redis-sentinel /path/to/your/sentinel.conf
or
redis-server /path/to/your/sentinel.conf --sentinel

配置项:

down-after-milliseconds 选项指定了 Sentinel 判断实例进入主观下线所需要的时间长度, 多个 Sentinel 监视同一个主服务器的标准是不同的

主观下线靠 PING 返回无效命令的累计时长, 客观下线靠询问其他 Sentinel 状态

选择 Sentinel 领头羊的算法为: Raft

• Sentinel 只是一个运行在特殊模式下的 Redis 服务器, 它使用了和普通模式不同的命令表, 所以 Sentinel 模式能够使用的命令和普通 Redis 服务器能够使用的命令不同

• Sentinel 会读入用户指定的配置文件, 为每个要被监视的主服务器创建相应的实例结构, 并创建连向主服务器的命令连接和订阅连接, 其中命令连接用于向主服务器发送命令请求, 而订阅连接则用于接收指定频道的消息

• Sentinel 通过向主服务器发送 INFO 命令来获得主服务器属下所有从服务器的地址信息, 并为这些从服务器创建相应的实例结构, 以及连向这些从服务器的命令连接和订阅连接

• 在一般情况下, Sentinel 以每十秒一次的频率向被监视的主服务器和从服务器发送 INFO 命令, 当主服务器处于下线状态, 或者 Sentinel 正在对主服务器进行故障转移操作时, Sentinel 向从服务器发送 INFO 命令的频率会改为每秒一次

• 对于监视同一个主服务器和从服务器的多个 Sentinel 来说, 它们会以每两秒一次的频率, 通过向被监视服务器的 sentinel:hello 频道发送消息来向其他 Sentinel 宣告自己的存在

• 每个 Sentinel 也会从 sentinel:hello 频道中接收其他 Sentinel 发来的信息, 并根据这些信息为其他 Sentinel 创建相应的实例结构, 以及命令连接

• Sentinel 只会与主服务器和从服务器创建命令连接和订阅连接, Sentinel 之间只创建命令连接

• Sentinel 以每秒一次的频率向实例(包括主服务器、从服务器、其他 Sentinel)发送 PING 命令, 并根据实例对 PING 命令的恢复来判断实例是否在线, 当一个实例在指定的时长中连续向 Sentinel 发送无效的回复时, Sentinel 会将这个实例判断为主观下线

• 当 Sentinel 将一个主服务器判断为主观下线时, 它会向同样监视这个主服务器的其他 Sentinel进行询问, 看他们是否同意这个主服务器已经进入主观下线状态

• 当 Sentinel 收集到足够多的主观下线投票时, 它会将主服务器判断为客观下线, 并发起一次针对主服务器的故障转移操作

3. 集群

• 节点通过握手来将其他节点添加到自己所处的集群当中

• 集群中的 16384 个槽截图分别指派给集群中的各个节点, 每个节点都会记录哪些槽指派给了自己, 而哪些槽又被指派给了其他节点

• 节点在接到一个命令请求时, 会先检查这个命令请求要处理的键所在的槽是否由自己负责, 如果不是的话, 节点将向客户端返回一个 MOVED 错误, MOVED 错误携带的信息可以指引客户端转向至正在负责相关槽的节点

• 对 Redis 集群的重新分片工作是由 redis-trib 负责执行的, 重新分片的关键是将属于某个槽的所有键值对从一个节点转移至另一个节点

• 如果节点 A 正在迁移槽 i 至节点 B, 那么当节点 A 没能在自己的数据库中找到命令指定的数据库键时, 节点 A 回向客户端返回一个 ASK 错误, 指引客户端到节点 B 继续查找指定的数据库键

• MOVED 错误表示槽的负责权已经从一个节点转移到了另一个节点, 而 ASK 错误只是两个节点在迁移槽的过程中使用的一种临时措施

• 集群里的从节点用于复制主节点, 并在主节点下线时, 代替主节点继续处理命令请求

• 集群中的节点通过发送和接收消息来进行通信, 常见的消息包括: MEET, PING, PONG, PUBLISH, FAIL 五种

Redis：单机数据库的实现

1. 数据库

通过 SELECT num 命令可以切换客户端使用的数据库, 即让客户端 db 指针指向服务端的某个 db 元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

struct redisServer {

	// 一个数组, 保存着服务器中的所有数据库
	redisDb *db;

	// 服务器的数据库数量: 默认16个
	int dbnum;

	// AOF 缓冲区: 记录写操作
	sds aof_buf;

	// AOF 重写缓冲区: 记录在 AOF 重写机制期间的所有写操作, 用于完成数据一致性
	sds aof_rewrite_buf;

	// 一个链表, 保存了所有客户端状态
	list *clients;
}

struct redisClient {

	// 记录客户端当前正在使用的数据库
	redisDb *db;

	// 输入缓冲区: 用于保存客户端发送的命令请求
	sds querybuf;

	// 命令的实现函数
	struct redisCommand *cmd;
}

Redis 是一个键值对(key-value pair)数据库服务器, 服务器中的每个数据库都由一个 redisDb 结构表示

1
2
3
4
5
6
7
8

struct redisDb {

	// 数据库键空间, 保存着数据库中的所有键值对
	dict *dict;

	// 过期字典, 保存着键的过期时间, EXPIRE 实际上是操作该键值
	dict *expires;
}

主要由 dict 和 expires 两个字典构成, 其中 dict 字典负责保存键值对, 而 expires 字典则负责保存键的过期时间

dict 内容是 < StringObject - 对象 > 的键值对, 当使用 Redis 命令对数据库进行读写时, 服务器不仅会对键空间执行指定的读写操作, 还会执行一些额外的维护操作, 其中包括:

1. 在读取一个键之后, 服务器会根据键是否存在来更新服务器的键空间命中(hit)次数或不命中(miss)次数, 这两个值可以在 INFO stats 命令的 keyspace_hits 属性和 keyspace_misses 属性中查看

2. 在读取一个键之后, 服务器会更新键的 LRU 时间, 用于计算键的闲置时间, 使用 OBJECT idletime 命令可以查看 key 的闲置时间

3. 如果服务器在读取一个键时发现该键已经过期, 那么服务器会先删除这个过期键, 然后才执行余下的其他操作

4. 如果有客户端使用 WATCH 命令监视了某个键, 那么服务器在对被监视的键进行修改之后, 会将这个键标记为 dirty, 从而让事务程序注意到这个键已经被修改过

5. 服务器每次修改一个件之后, 都会对脏键计数器的值增 1, 这个计数器会触发服务器的持久化以及复制操作

6. 如果服务器开启了数据库通知功能, 那么在对键进行修改之后, 服务器将按配置发送相应的数据库通知

当键过期时, Redis 提供了三种删除策略

1. (主动)定时删除: 在设置键的过期时间的同时, 创建一个定时器(timer), 让定时器在键的过期时间来临时, 立即执行对键的删除操作, 省内存, 费CPU

2. (Redis使用)(被动)惰性删除: 放任键过期不管, 当获取的时候, 过期就删除, 未过期就返回, 省CPU, 费内存(expireIfNeeded)

3. (Redis使用)(主动)定期删除: 每隔一段时间, 程序就对数据库进行一次检查, 删除里面的过期键(算法), 折中(serverCron - activeExpireCycle)

AOF 和 RDB 是如何删除过期键的

1. 执行 SAVE 命令或者 BGSAVE 命令所产生的新 RDB 文件不会包含已经过期的键

2. 执行 BGREWRITEAOF 命令所产生的重写 AOF 文件不会包含已经过期的键

3. 当一个过期键被删除之后, 服务器会追加一条 DEL 命令到现有 AOF 文件的末尾, 显式的删除过期键

4. 当主服务器删除一个过期键之后, 它会向所有从服务器发送一条 DEL 命令, 显式的删除过期键

5. 从服务器即使发现过期键也不会自作主张的删除它, 而是等待主节点发来 DEL 命令, 从而保证主从服务器数据一致性

2. RDB 持久化

RDB 持久化操作, 即执行 SAVE/BGSAVE 命令, 是由配置文件中的 save 选项生效的, 由周期性操作函数 serverCron 每个 100ms 检查是否满足持久化条件

1
2
3
4

// default
save 900 1     900秒内对数据库至少1次修改
save 300 10    300秒内对数据库至少10次修改
save 60 10000  60秒内对数据库至少10000次修改

使用 od 命令工具可以查看 RDB 内容

• SAVE 命令由服务器进程直接执行保存操作, 会阻塞服务器

• BGSAVE 命令由子进行执行保存操作, 不会阻塞服务器执行, 但是会拒绝再次服务器进行再次接收的 SAVE, BGSAVE, BGREWRITEAOF 命令防止竞争

• 服务器状态中会保存所有用 save 选项设置的保存条件, 当任意一个保存条件被满足时, 服务器会自动执行 BGSAVE 命令

• RDB 是一个经过压缩的二进制文件, 有多个部分组成

• 对于不同类型的键值对, RDB 文件会使用不同的方式来保存它们

3. AOF 持久化

1. AOF 持久化是通过保存 Redis 服务器所执行的写命令(SET、SADD、RPUSH)来记录数据库状态的, 这个保存的过程是由 serverCron 函数中的 flushAppendOnlyFile 来完成的, 也是由配置文件中的 appendfsync 选项来设置的

2. 随着服务器时间的运行, AOF 中记录的写操作越来越多, 文件体积也越来越大, 使用 AOF 文件来进行数据还原所需的时间也就越多, 因此 AOF 文件重写机制: 通过读取服务器当前的数据库状态, 然后用一条命令去记录键值对, 代替之前记录这个键值对的多条命令

3. AOF 重写机制采用后台子进程的方式来实现, 虽然不阻塞服务器继续处理命令请求, 但随之而来带来了数据同步不一致的问题, 因此 Redis 服务器设置了一个 AOF 重写缓存区, 每次子进程重写完成时, 服务器进程将 AOF 缓冲区的记录追加到新的 AOF 文件末尾, 这也是 BGREWRITEAOF 命令的实现原理

4. 事件

• Redis 服务器是一个事件驱动程序, 服务器处理的事件分为时间事件和文件事件两类

• 文件事件处理器是基于 Reactor 模式实现的网络通信程序

• 文件事件是对套接字操作的抽象: 每次套接字变为可应答(acceptable), 可写(writable)或者可读(readable)时, 相应的文件事件就会产生

• 文件事件分为 AE_READABLE 和 AE_WRITABLE 两类事件

• 时间事件分为定时事件和周期性事件

• 服务器一般情况下只执行 serverCron 函数的一个时间事件, 并且这个事件是周期性事件

• 时间事件的实际处理时间通常比设定的到达时间晚一些

5. 客户端

通过使用由 I/O 多路复用技术实现的文件处理器, Redis 服务器使用单线程单进程的方式来处理命令请求, 并与多个客户端进行网络通信

1
2

127.0.0.1:6379> CLIENT list
id=5 addr=127.0.0.1:58793 fd=8 name= age=0 idle=0 flags=N db=0 sub=0 psub=0 multi=-1 qbuf=0 qbuf-free=32768 obl=0 oll=0 omem=0 events=r cmd=client

通过客户端的标志属性 flags 可以查明客户端的角色, 以及目前客户端所处的状态, 例如

1
2
3
4
5
6
7
8
9

# 客户端是一个主服务器
REDIS_MASTER
# 客户端正在被列表命令阻塞
REDIS_BLOCKED
# 客户端正在执行事务, 但事务的安全性已被破坏
REDIS_MULTI | REDIS_DIRTY_CAS
# 客户端是一个从服务器, 并且版本低于 Redis 2.8
REDIS_SLAVE | REDIS_PRE_PSYNC
...

• 服务器状态结构使用 clients 链表连接多个客户端状态, 新添加的客户端状态会被放到链表的末尾

• 客户端状态的 flags 属性使用不同标志来表示客户端的角色, 以及客户端当前所处的状态

• 输入缓冲区记录了客户端发送的命令请求, 这个缓冲区的大小不能超过 1GB

• 命令参数和参数个数会被记录在客户端状态的 argv 和 argc 属性里面, 而 cmd 属性则记录对了客户端要执行命令是实现函数

• 客户端有固定大小缓冲区和可变大小缓冲区两种缓冲区可用, 其中固定大小缓冲区的最大大小为 16KB, 而可变大小缓冲区的最大大小不能超过服务器设置的硬性限制

• 输出缓冲区限制值有两种, 如果输出缓冲区的大小超过了服务器设置的硬性限制, 那么客户端会被立即关闭; 除此之外, 如果客户端在一定时间内, 一直超过服务器设置的软性限制, 那么客户端也会被关闭

• 当一个客户端通过网络连接上服务器时, 服务器会为这个客户端创建相应的客户端状态, 网络连接关闭、发送了不合协议格式的命令请求、成为 CLIENT KILL 命令的目标、空转时间超时、输出缓冲区的大小超出限制, 以上这些原因都会造客户端被关闭

• 处理 LUA 脚本的伪客户端在服务器初始化时创建, 这个客户端会一直存在, 直到服务器关闭

• 载入 AOF 文件时使用的伪客户端在载入工作开始时动态创建, 载入工作完毕之后关闭

6. 服务器

• 一个命令请求从发送到完成主要包括以下几个步骤: 1) 客户端将命令请求发送给服务器; 2) 服务器读取命令请求; 3） 命令执行器根据参数查找命令的实现函数; 4) 服务器将命令回复给客户端

• serverCron 函数默认每隔 100ms 执行一次, 它的主要工作包括更新服务器状态信息, 处理服务器接收的 SIGTERM 信号, 管理客户端资源和数据库状态, 检查并执行持久化操作

• 服务器从启动到能够处理客户端的命令请求需要执行以下步骤: 1) 初始化服务器状态; 2) 载入服务器配置; 3) 初始化服务器数据结构; 4) 还原数据库状态; 5) 执行事件循环

Java基础知识索引

记录在日常工作中看到的一些浅显易懂的精华帖

• ClassLoader 双亲委派模型, 隔离性

https://www.cnblogs.com/wxd0108/p/6681618.html

• CNAME, A, 重定向的区别

A记录 —— 映射域名到一个或多个IP, 适应于独立主机、有固定IP地址
CNAME——映射域名到另一个域名（子域名）, 适应于虚拟主机、变动IP地址主机
URL转发——重定向一个域名到另一个URL地址，使用HTTP 301状态码, 适应于更换域名又不想抛弃老用户

• 记一次排查JVM OOM的经历

A:

思想类

• 《激荡十年，水大鱼大》 吴晓波

• 《原则》 Roy Dalio

小说类

技术类

• 《Redis 设计与现实》 黄健宏

• 《深入分析 Java Web》 许令波

• 《图解 Http》于均良

• 《图解 Tcp/Ip》于均良

• 《分布式服务框架 原理与实践》 李林峰

• 《Java 并发编程实践》 Doug Lea

Redis：数据结构与对象

1. SDS：简单动态字符串（Simple Dynamic String）

在 Redis 里面，C 语言传统的字符只会作为常量，用在一些无须修改的字符串，其他字符串都用 SDS

1
2
3
4
5
6
7
8
9

struct sdshdr {
	// 记录 buf 数组中已使用字节的数量
	// 等于 SDS 所保存字符串的长度
	int len;
	// 记录buf 数组中未使用字节的数量
	int free;
	// 字节数组，用于保存字符串
	char buf[];
}

SDS 与 C 字符串的区别

1. 获取字符串长度：O(1)， len

   STRLEN key 命令复杂度仅为 O(1)

2. 杜绝缓冲区溢出：buffer overflow

   SDSCAT（SDS API） 在拼接字符串之前会先检查空间是否足够(free)，不够的话先用 SDS 空间分配策略进行分配，再进行拼接

   APPEND key 永远不会抹掉其他字符串的内存空间

3. 减少修改字符串时带来的内存重分配次数

   对于修改 C 字符串而言，拼接操作(append)会扩展底层数组的空间大小，截断操作(trim)会释放不再使用的空间，这两种内存重分配操作前者容易引起缓冲区溢出，后者容易引起内存泄漏，为了解决这两个问题，SDS 采用 空间预分配 和 惰性空间释放 两种优化策略

   a. 空间预分配：当 SDS 需要修改并进行空间扩展时，程序不仅会为 SDS 分配修改所必须的空间，还会为 SDS 分配额外的未使用空间(free)

   a.1 分配后 len > 1M，则给 free 预分配 1M 空间

   a.2 分配后 len < 1M，则给 free 预分配 len 空间
   
   通过这种预分配策略，SDS 将连续增长 N 次字符串所需要的内存重分配次数从必定 N 次降低为 最多 N 次
   
   b. 惰性空间释放：当 SDS 需要缩短保存的字符串时，程序不会立即回收多出来的字节，而是使用 free 属性将这些字节数量记录起来，等待再次使用
   

4. 二进制安全

   buf 长度是 len，决定了结尾，即使 buf 中存在 ‘\0’，也不会被认为是结束

5. 兼容部分 C 字符串函数

   strcasecmp(sds->buf，”hello world”)

   strcat(c_string，sds->buf)

2. LinkedList：链表

在 Redis 中，链表建的操作，底层实现之一的数据结构就是链表，除此之外，发布与订阅、慢查询、监视器等功能也用的是链表

链表节点（listNode）：

1
2
3
4
5
6
7
8
9
10
11
12

typedef struct listNode {
	
	// 前置节点
	struct listNode *prev;
	
	// 后置节点
	struct listNode *next;
	
	// 节点值
	void *value;

} listNode;

链表（list）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

typedef struct list {
	
	// 表头节点
	listNode *head;

	// 表尾节点
	listNode *tail;

	// 链表所包含的节点数
	unsigned long len;

	// 节点值复制函数
	void *(*dup) (void *ptr);

	// 节点值释放函数
	void (*free) (void *ptr);

	// 节点值对比函数
	int (*match) (void *ptr);

} list;

Redis 使用 list 结构持有链表，是 双端、无环、带表头指针和表尾指针，带链表长度计数器、多态（void * 接收各种类型的值） 性质的链表

3. Map：字典

在 Redis 中，字典是哈希键的底层实现之一，字典由哈希表实现，哈希表由哈希表节点实现，哈希表节点就是键值对

哈希表节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

typedef struct dictEntry{
	
	// 键
	void *key;
	
	// 值
	union {
		void *val;
		uint64_t u64;
		int64_t s64;
	} v;
	
	// 指向下个了哈希表节点，形成链表：解决哈希冲突
	struct dictEntry *next;

} dictEntry;

哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

typedef struct dictht {
	
	// 哈希表数组
	dictEntry **table;

	// 哈希表大小
	unsigned long size;

	// 哈希表大小掩码，用于计算哈希值：等于 size - 1
	unsigned long sizemask;

	// 已有节点数量
	unsigned long used;
	
} dictht;

字典

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

typedef struct dict {
	
	// 类型特定函数
	dictType *type;

	// 私有数据
	void *privdata;

	// 哈希表：每个字典由两个哈希表，一个平时使用，一个仅在 rehash 时使用
	dictht ht[2];

	// rehash索引
	int trehashidx;

} dict;

其中，type 和 privdata 是针对不同类型的键值对，为创建多态字典而设置，type 是指向 dictType 结构的指针，每个结构保存了一簇用于操作特定类型键值对的函数，比如：不同类型的哈希函数

ht 属性是一个包含两个项的数组，一般情况下，字典只使用 ht[0] 哈希表，ht[1] 当进行 rehash 时使用

Redis 的哈希算法使用的是 MurmurHash

hash = dict -> type -> hashFunction(key)

index = hash & dict -> ht[x].sizemask

Redis 使用链表地址发来解决冲突，新节点将插入链表表头（O(1)）

重新哈希（rehash）操作对哈希表的大小进行相应的扩展或者收缩，维持负载因子（load factor）在一个合理的范围之内，实际上就是 ht[0] 和 ht[1] 相互替代（比如：扩展 ht[1] - 迁移 0->1 - 释放 ht[0]）

load factor = ht[0].used / ht[0].size

哈希表的扩展与收缩的时机

1. 服务器目前没有执行 BGSAVE 或者 BGREWRITEAOF 命令，并且哈希表的负载因子 >= 1;

2. 服务器目前正在执行 BGSAVE 或者 BGREWRITEAOF 命令，并且哈希表的负载因子 >= 5;

渐进 rehash：为了避免 rehash 对服务器性能造成影响，服务器不是一次性将 ht[0] 里面的所有键值对全部 rehash 到 ht[1]，而是分多次、渐进式的将 ht[0] 里面的键值对慢慢 rehash 到 ht[1]，采用分治的思想，随着操作，随着 rehash，期间新加入的值会直接进入 ht[1]，如果 ht[0] 中 get 不到，会自动去 ht[1] 里面查找

4. Skip List：跳表

• 跳跃表是有序集合的底层实现之一

• Redis 的跳跃表实现由 zskiplist 和 zskiplistNode 两个结构组成, 其中 zskiplist 用于保存跳跃表信息（比如表头、表尾节点、长度）, 而 zskiplistNode 则用于表示跳跃表节点

• 每个跳跃表节点的层高都是 1 至 32 之间的随机数

• 在同一个跳跃表中, 多个节点可以包含相同的分值, 但每个节点的成员对象必须是唯一的

• 跳跃表中的节点按照分值大小进行排序, 当分值相同时, 节点按照成员对象的大小进行排序

5. IntSet: 整数集合

1
2
3
4
5
6
7
8
9
10
11
12

typedef struct intset {

	// 编码方式
	uint32_t encoding;

	// 集合包含的元素数量
	uint32_t length;

	// 保存元素的数组
	int8_t contents[];

} intset;

每次加入新的元素，都有可能引发升级: 1. 扩展空间, 2: 类型统一化, 3: 将新元素和老元素统一加入到扩展后的空间, 需要注意的是: 不支持降级

• 整数集合是集合键的底层实现之一

• 整数集合的底层实现为数组, 这个数组以有序、无重复的方式保存集合元素, 在有需要时, 程序会根据新添加元素的类型, 改变这个数组的类型

• 升级操作为整数集合带来了操作上的灵活性, 并且尽可能的节约了内存

• 整数集合只支持升级操作, 不支持降级操作

6. Zip List: 压缩列表

• 压缩列表是一种为节约内存而开发的顺序型数据结构

• 压缩列表被用作列表键和哈希键的底层实现之一

• 压缩列表可以包含多个节点, 每个节点可以保存一个字节数组或者整数值

• 添加新节点到压缩列表, 或者从压缩列表中删除节点, 可能会引发连锁更新操作, 但这种操作出现的几率并不高

7. Object: 对象

Redis 并没有直接使用这些数据结构来实现键值对数据库, 而是基于这些数据结构创建了一个对象系统, 这个系统包含 字符串对象、列表对象、哈希对象、集合对象和有序集合对象 五种, 根据命令, 判断哪种对象适合就用于执行

• Redis 数据库中的每个键值对的键和值都是一个对象

• Redis 共有字符串、列表、哈希、集合、有序集合五种类型的对象, 每种类型的对象至少都要两种或以上的编码方式, 不同的编码可以在不同的使用场景上优化对象的使用效率

• 服务器在执行某些命令之前, 会先检查给定键的类型能否执行指定的命令, 而检查一个键的类型就是检查键的值对象的类型

• Redis 的对象系统带有引用计数实现的内存回收机制

• Redis 会共享值为 0 到 9999 的字符串对象

• 对象会记录自己的最后一次被访问的时间, 这个时间可以用于计算对象的空转时间

工作中需要使用一种加密算法，来验证消息的来源，故借此了解下这个专题

常见的加密算法可以分为三类：对称加密，非对称加密，哈希

首先是对称加密，即加密和解密使用相同的秘钥（K），优势在于速度快，当 K 很长时候，破解难度异常大，缺点是加密通路有 N 条，比如 Encrypt（A，B）和 Encrypt（B，A）是两条加密通路，则需要 N 个秘钥，其中 A，B 分别获有自己的和对方的秘钥，这就带来了秘钥泄露的风险，如果多个通路公用一个秘钥的话，一旦泄露，保密性也就无从谈起

常见的加密算法有：AES，DES，3DES，Blowfish，IDEA，RC4，RC5，RC6

接下来是非对称加密，即加密和解密使用不同的秘钥（K，K’），又称为公钥和私钥，使用公钥进行加密，使用私钥进行解密，优势在于私钥是唯一的，其他用户除了可以可以通过信息发送者的公钥来验证信息的来源是否真实，还可以确保发送者无法否认曾发送过该信息，缺点在于速度慢

常见的非对称加密算法有：RSA，ECC，DSA，Diffie-Hellman，EI Gamal

最后是哈希算法，它是一种单向的算法，即可以将目标信息通过 Hash 算法生成具有一定长度的 Hash 值，却不能通过这个 Hash 值从新获得目标信息，因此常用于不可还原的密码存储，信息完整性校验等

常见的哈希算法有： MD5，SHA，MD2，MD4，HAVAL

由于项目的本身需要，加密端在 PC，解密端在移动设备，且需要根据加密消息进行相关有效性验证，故最终选择 ECC 算法来

哈希表

又称为散列表（HashTable），应用场景诸如缓存技术（memcached），xxx 等

几种数据机构在新增，查找等基础操作的执行性能

1. 数组，指定下标查找 O(1)，指定值查找 O(n)（有序的情况下二分，插值可以达到 O(logn)），新增 O(n)

2. 线性链表，查找 O(n)，新增 O(1)

3. 二叉树，对一棵相对平衡的有序二叉树，新增和查找操作平均 O(logn)

4. 哈希表，不考虑哈希冲突的情况下，新增和查找平均为 O(1)

哈希表的实质：数组 A + 哈希函数 + 解决哈希冲突的方案

而对于数组的下表，即元素的存储位置是通过哈希函数计算出来的，这个哈希函数就是 f，有以下公式

存储位置 = f(关键字)，f 为哈希函数

哈希表的一切操作前提是通过这个哈希函数，找到元素的存储位置，继而进行操作，可在找存储位置的时候，一旦发现已经先有元素占用了，这就引发了哈希冲突问题

哈希冲突： f(i) = f(j)，i ≠ j

没有完美的哈希函数存在，好的哈希函数会尽可能地保证 计算简单 和 散列地址分布均匀，一旦冲突发生，有以下解决方案：

• 开放定址法（发生冲突，继续寻找下一块未被占用的存储地址），

• 二次散列函数法

• 链地址法（HashMap）也就是数组+链表的方式

HashMap 实现原理：数组 + 链表

数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

static class Node<K,V> implements Map.Entry<K,V> {
	final int hash;
	final K key;
	V value;
	Node<K,V> next;
	
	Node(int hash, K key, V value, Node<K,V> next) {
		this.hash = hash;
		this.key = key;
		this.value = value;
		this.next = next;
	}

	public final K getKey()        { return key; }
	public final V getValue()      { return value; }
	public final String toString() { return key + "=" + value; }

	public final int hashCode() {
		return Objects.hashCode(key) ^ Objects.hashCode(value);
	}

	public final V setValue(V newValue) {
		V oldValue = value;
		value = newValue;
		return oldValue;
	}

	public final boolean equals(Object o) {
		if (o == this)
			return true;
		if (o instanceof Map.Entry) {
			Map.Entry<?,?> e = (Map.Entry<?,?>)o;
			if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue())) 
				return true;
		}
		return false;
	}
   }

HashMap 其实就是一个 以上 Entry 数组，Entry 对象中包含了键和值，其中 next 也是一个 Entry 对象，它就是用来处理 hash 冲突的，形成一个链表

几个重要的因素

1
2
3
4
5
6
7
8

//实际存储的key-value键值对的个数
transient int size;
//阈值，当table == {}时，该值为初始容量（初始容量默认为16）；当table被填充了，也就是为table分配内存空间后，threshold一般为 capacity*loadFactory。HashMap在进行扩容时需要参考threshold，后面会详细谈到
int threshold;
//负载因子，代表了table的填充度有多少，默认是0.75
final float loadFactor;
//用于快速失败，由于HashMap非线程安全，在对HashMap进行迭代时，如果期间其他线程的参与导致HashMap的结构发生变化了（比如put，remove等操作），需要抛出异常ConcurrentModificationException
transient int modCount;

哈希函数

1
2
3
4
5
6
7
8
9
10
11
12

//这是一个神奇的函数，用了很多的异或，移位等运算，对key的hashcode进一步进行计算以及二进制位的调整等来保证最终获取的存储位置尽量分布均匀
final int hash(Object k) {
	int h = hashSeed;
	if (0 != h && k instanceof String) {
		return sun.misc.Hashing.stringHash32((String) k);
	}

	h ^= k.hashCode();

	h ^= (h >>> 20) ^ (h >>> 12);
	return h ^ (h >>> 7) ^ (h >>> 4);
}

注意：

1. 重写 equals 方法需同时重写 hashCode 方法，因为 HashMap 是通过 hashCode 进行映射的，如果不重写则映射不到 value

2. putIfAbsent 是线程安全的，这个方法等价于在key不存在的时候加入一个值，如果key存在就不放入，记得判断返回值

Q：Transient 作用

A：1）一旦变量被transient修饰，变量将不再是对象持久化的一部分，该变量内容在序列化后无法获得访问

2）transient关键字只能修饰变量，而不能修饰方法和类。注意，本地变量是不能被transient关键字修饰的。变量如果是用户自定义类变量，则该类需要实现Serializable接口

3）一个静态变量不管是否被transient修饰，均不能被序列化

4）若实现的是Externalizable接口，则没有任何东西可以自动序列化，需要在writeExternal方法中进行手工指定所要序列化的变量，这与是否被transient修饰无关

Q：接口和抽象类的区别

A：抽象类：

1）抽象方法必须为public或者protected（因为如果为private，则不能被子类继承，子类便无法实现该方法），缺省情况下默认为public。

2）抽象类不能用来创建对象；

3）如果一个类继承于一个抽象类，则子类必须实现父类的抽象方法。如果子类没有实现父类的抽象方法，则必须将子类也定义为为abstract类

接口：

1）接口中的变量会被隐式地指定为public static final变量

2）方法会被隐式地指定为public abstract方法且只能是public abstract方法

继承是一个 “是不是”的关系，而 接口 实现则是 “有没有”的关系，一个类只能继承一个抽象类，而一个类却可以实现多个接口

Q：serialVersionUID 作用

A：Java 的序列化机制是通过在运行时判断类的 serialVersionUID 来验证版本一致性的。在进行反序列化时，JVM 会把传来的字节流中的serialVersionUID 与本地相应实体（类）的 serialVersionUID 进行比较，如果相同就认为是一致的，可以进行反序列化，否则就会出现序列化版本不一致的异常。(InvalidCastException)

1）两端不一致，无法序列化

2）两端一致，增的字段会序列化成默认值

3）两端一致，减的字段会序列化丢失

Q：多线程相关

A：

1） 并行：多个cpu实例或者多台机器同时执行一段处理逻辑，是真正的同时；并发：通过cpu调度算法，让用户看上去同时执行，实际上从cpu操作层面不是真正的同时

2）线程安全：代码在多线程中使用，线程的调度顺序不影响结果

3）线程状态：NEW，RUNNABLE，WAITING，BLOCKED，TERMINATED，TIMED_WAITING

4）sleep 和 wait 区别：前者不会释放锁，后者会

5）三种线程实现方式：Thread，Runnable，Callable（Future），后者可以返回线程执行结果

6）容器类：BlockingQueue、ConcurrentHashMap

7）ConcurrentHashMap 是用 lock 实现并发（锁的方式是稍微细粒度的。将hash表分为16个桶（默认值），诸如get, put, remove等常用操作只锁当前需要用到的桶）而 HashTable 是用 synchronized 实现并发（对整个集合加锁，加锁期间集合不可访问）

Q：String 类是不可变的吗

A：从语法上来讲，是的，因为 String 类是用 final 修饰的，绝对吗？不绝对，因为可以用 UnSafe 来修改 String 值；多个相同值的 String，可以用 intern（） 来返回存储在字符串池的值，需要注意：采用new 创建的字符串对象不进入字符串池，见以下代码

1
2
3
4
5
6
7
8
9
10
11

String str1 = "a";  
	String str2 = "b";  
	String str3 = "ab";  
	String str4 = str1 + str2;  
	String str5 = new String("ab");  
   
	System.out.println(str5.equals(str3));       // true
	System.out.println(str5 == str3);            // false
	System.out.println(str5.intern() == str3);   // true: str3 是直接声明的，进入字符串池  
	System.out.println(str5.intern() == str4);   // false: str5 是 new 声明的，不进入字符串池

TCP 三次握手 和 四次挥手

三次握手

1. Client 发送 SYN 给 Server，Client 状态置为 SYN-SEND

2. Server 发送 SYN + ACK 给 Client，Server 状态置为 SYN-RCVD

3. Client 发送 ACK 给 Server，Server 状态置为 ESTABLISED

四次挥手

1. Client 发送 FIN 给 Server，Client 状态置为 FIN-WAIT-1

2. Server 发送 ACK 给 Client，Server 状态置为 CLOSE-WAIT，Client 收到后置为 FIN-WAIT2

3. Server 发送 FIN 给 Client，Sever 状态置为 LAST-ACK

4. Client 发送 ACK 给 Server，Client 状态置为 TIME-WAIT，Server 收到后状态置为 CLOSE

为什么四次挥手是由客户端发起的

https://blog.csdn.net/Daputao_net/article/details/81255499

Http 和 Https

HTTP是应用层协议，位于HTTP协议之下是传输协议TCP。TCP负责传输，HTTP则定义了数据如何进行包装

HTTP - TCP（明文传输）

HTTPS - TLS/SSL - TCP（密文传输）