Algorithm
128. 最长连续序列
func longestConsecutive(nums []int) (result int) {
numMap := make(map[int]bool, 0)
for _, v := range nums {
numMap[v] = true
}
result = 0
for k, _ := range numMap {
currentNum := k
currentResult := 1
if _, ok := numMap[k-1]; !ok {
for {
_, ok := numMap[currentNum+1]
if ok {
currentNum += 1
currentResult += 1
} else {
break
}
}
if currentResult > result {
result = currentResult
}
}
}
return
}
Review
Common Problems in Message Queues [With Solutions]
文章讲述了使用MQ可能遇到的问题，以及给出对应的一些解决方案。
- 解决不可用/坏消息：使用死信队列来存储无法处理的坏消息，并且在需要/消费者解决问题的时候再从死信队列中将消息重新发送。
- 怎么避免消息丢失：
- 通过消费者消费成功回复ACK的方式，来避免消息端消息丢失。
- MQ服务端实现消息可持久化来避免异常情况下服务端消息丢失。
- MQ服务端实例之间消息复制来避免其中一个服务实例挂死之后的消息丢失。
- 通过编码将消息发送、消费作为一个事务，来彻底解决消息丢失问题。
- 消息有序性保障：
- 每个消息里面带上时间戳，消费端识别时间戳来实现有序消费。
- 每个消息里面带上序列号。
- 使用自带offset的MQ中间件（比如kafka）
TIP
并查集从入门到出门
Share
学习mysql 45讲
24 | MySQL是怎么保证主备一致的？
MySQL主备的基本原理
备库B跟主库A之间维持了一个长连接。 主库A内部有一个线程， 专门用于服务备库B的这个长连接。一个事务日志同步的完整过程是这样的：
- 在备库B上通过change master命令， 设置主库A的IP、 端口、 用户名、 密码， 以及要从哪个位置开始请求binlog， 这个位置包含文件名和日志偏移量。
- 在备库B上执行start slave命令， 这时候备库会启动两个线程， 就是图中的io_thread和sql_thread。其中io_thread负责与主库建立连接。
- 主库A校验完用户名、 密码后， 开始按照备库B传过来的位置， 从本地读取binlog， 发给B。
- 备库B拿到binlog后， 写到本地文件， 称为中转日志（relaylog）。
- sql_thread读取中转日志， 解析出日志里的命令， 并执行。
binlog的三种格式
同样是删除表里面一行数据，不同格式的binlog记录的内容是不一样的：
- statement格式下：记录到binlog里的是语句原文。因此可能会出现这样一种情况： 在主库执行这条SQL语句的时候， 用的是索引a； 而在备库执行这条SQL语句的时候， 却使用了索引t_modified。 因此， MySQL认为这样写是有风险的。
- row格式：binlog里面记录了真实删除行的主键id， 这样binlog传到备库去的时候， 就肯定会删除id=4的行， 不会有主备删除不同行的问题。比如你用一个delete语句删掉10万行数据，如果用row格式的binlog，就要把这10万条记录都写到binlog中。 这样做， 不仅会占用更大的空间， 同时写binlog也要耗费IO资源， 影响执行速度。
- mixed格式：基于statement和row格式各自的优缺点，MySQL就取了个折中方案， 也就是有了mixed格式的binlog。 mixed格式的意思是， MySQL自己会判断这条SQL语句是否可能引起主备不一致， 如果有可能， 就用row格式，否则就用statement格式。
循环复制问题
双M结构：2个mysql server互为主备。
双M结构存在一个问题需要解决：业务逻辑在节点A上更新了一条语句， 然后再把生成的binlog 发给节点B， 节点B执行完这条更新语句后也会生成binlog。 如果节点A同时是节点B的备库， 相当于又把节点B新生成的binlog拿过来执行了一次， 然后节点A和B间， 会不断地循环执行这个更新语句， 也就是循环复制了。
解决方案：
- 规定两个库的server id必须不同， 如果相同， 则它们之间不能设定为主备关系；
- 一个备库接到binlog并在重放的过程中， 生成与原binlog的server id相同的新的binlog；
- 每个库在收到从自己的主库发过来的日志后， 先判断server id， 如果跟自己的相同， 表示这个日志是自己生成的， 就直接丢弃这个日志
25 | MySQL是怎么保证高可用的？
主备延迟
- 主库A执行完成一个事务， 写入binlog， 我们把这个时刻记为T1;
- 之后传给备库B， 我们把备库B接收完这个binlog的时刻记为T2;
- 备库B执行完成这个事务， 我们把这个时刻记为T3。
所谓主备延迟， 就是同一个事务， 在备库执行完成的时间和主库执行完成的时间之间的差值， 也就是T3-T1
主备延迟的来源
- 有些部署条件下， 备库所在机器的性能要比主库所在的机器性能差。
- 备库的压力大。 一般的想法是， 主库既然提供了写能力， 那么备库可以提供一些读能力。 或者一些运营后台需要的分析语句， 不能影响正常业务， 所以只能在备库上跑。
- 大事务。
主备切换策略
可靠性优先策略
- 判断备库B现在的seconds_behind_master， 如果小于某个值（比如5秒） 继续下一步， 否则持续重试这一步；
- 把主库A改成只读状态， 即把readonly设置为true；
- 判断备库B的seconds_behind_master的值， 直到这个值变成0为止；
- 把备库B改成可读写状态， 也就是把readonly设置为false；
- 把业务请求切到备库B
可用性优先策略
如果强行把步骤4、 5调整到最开始执行， 也就是说不等主备数据同步， 直接把连接切到备库B， 并且让备库B可以读写， 那么系统几乎就没有不可用时间了。代价， 就是可能出现数据不一致的情况。
26 | 备库为什么会延迟好几个小时？
并行复制：原来的sql_thread不再直接更新数据了， 只负责读取中转日志和分发事务。 真正更新日志的， 变成了worker线程。 而work线程的个数， 就是由参数slave_parallel_workers决定的。
coordinator在分发的时候， 需要满足以下这两个基本要求：
- 不能造成更新覆盖。 这就要求更新同一行的两个事务， 必须被分发到同一个worker中。
- 同一个事务不能被拆开， 必须放到同一个worker中。
MySQL 5.5版本的并行复制策略
按表分发策略
按表分发事务的基本思路是， 如果两个事务更新不同的表， 它们就可以并行。 因为数据是存储在表里的， 所以按表分发， 可以保证两个worker不会更新同一行。当然， 如果有跨表的事务， 还是要把两张表放在一起考虑的。具体实现就是：
- 每个worker线程对应一个hash表， 用于保存当前正在这个worker的“执行队列”里的事务所涉及的表。 hash表的key是“库名.表名”， value是一个数字， 表示队列中有多少个事务修改这个表。
- 在有事务分配给worker时， 事务里面涉及的表会被加到对应的hash表中。 worker执行完成后， 这个表会被从hash表中去掉。
每个事务在分发的时候， 跟worker的冲突关系包括以下三种情况：
- 如果跟所有worker都不冲突， coordinator线程就会把这个事务分配给最空闲的woker;
- 如果跟多于一个worker冲突， coordinator线程就进入等待状态， 直到和这个事务存在冲突关系的worker只剩下1个；
- 如果只跟一个worker冲突， coordinator线程就会把这个事务分配给这个存在冲突关系的worker
按行分发策略
要解决热点表的并行复制问题， 就需要一个按行并行复制的方案。 按行复制的核心思路是： 如果两个事务没有更新相同的行， 它们在备库上可以并行执行。 显然， 这个模式要求binlog格式必须是row。
基于行的策略， 事务hash表中还需要考虑唯一键， 即key应该是“库名+表名+索引a的名字+a的值”。
MySQL 5.6版本的并行复制策略
官方MySQL5.6版本， 支持了并行复制， 只是支持的粒度是按库并行。用于决定分发策略的hash表里， key就是数据库名。这个策略的并行效果， 取决于压力模型。 如果在主库上有多个DB， 并且各个DB的压力均衡， 使用这个策略的效果会很好。
MariaDB的并行复制策略
在实现上， MariaDB是这么做的：
- 在一组里面一起提交的事务， 有一个相同的commit_id， 下一组就是commit_id+1；
- commit_id直接写到binlog里面；
- 传到备库应用的时候， 相同commit_id的事务分发到多个worker执行；
- 这一组全部执行完成后， coordinator再去取下一批。
MySQL 5.7的并行复制策略
MySQL 5.7并行复制策略的思想是：
- 同时处于prepare状态的事务， 在备库执行时是可以并行的；
- 处于prepare状态的事务， 与处于commit状态的事务之间， 在备库执行时也是可以并行的。
MySQL 5.7.22的并行复制策略
在2018年4月份发布的MySQL 5.7.22版本里， MySQL增加了一个新的并行复制策略， 基于WRITESET的并行复制。所以有了3中策略模式：
- COMMIT_ORDER， 表示的就是前面介绍的， 根据同时进入prepare和commit来判断是否可以并行的策略。
- WRITESET， 表示的是对于事务涉及更新的每一行， 计算出这一行的hash值， 组成集合writeset。 如果两个事务没有操作相同的行， 也就是说它们的writeset没有交集， 就可以并行。这个hash值是通过“库名+表名+索引名+值”
- WRITESET_SESSION， 是在WRITESET的基础上多了一个约束， 即在主库上同一个线程先后执行的两个事务， 在备库执行的时候， 要保证相同的先后顺序。
27 | 主库出问题了， 从库怎么办？
基于位点的主备切换
取同步位点的方法是这样的：
- 等待新主库A’把中转日志（relaylog） 全部同步完成；
- 在A’上执行show master status命令， 得到当前A’上最新的File 和 Position；
- 取原主库A故障的时刻T；
- 用mysqlbinlog工具解析A’的File， 得到T时刻的位点。
GTID
GTID的全称是Global Transaction Identifier， 也就是全局事务ID， 是一个事务在提交的时候生成的， 是这个事务的唯一标识。mysql通过维护GTID来自动选择主从同步的位点。
28 | 读写分离有哪些坑？
一主多从的架构下，业务层很容易遇到主备延迟导致的读写分离问题，简单点描述就是客户端执行完一个更新事务后马上发起查询， 如果查询选择的是从库的话， 就有可能读到刚刚的事务更新之前的状态。本篇文章介绍的是解决主从延迟的几种解决方案
强制走主库方案
强制走主库方案其实就是， 将查询请求做分类：
- 对于必须要拿到最新结果的请求， 强制将其发到主库上
- 对于可以读到旧数据的请求， 才将其发到从库上
Sleep 方案
主库更新后， 读从库之前先sleep一下，很不精准就不展开说了。。
配合semi-sync
semi-sync是半同步复制， 也就是semi-sync replication。semi-sync做了这样的设计：
- 事务提交的时候， 主库把binlog发给从库；
- 从库收到binlog以后， 发回给主库一个ack， 表示收到了；
- 主库收到这个ack以后， 才能给客户端返回“事务完成”的确认。
semi-sync有一个缺陷就是semi-sync+位点判断的方案， 只对一主一备的场景是成立的。 在一主多从场景中， 主库只要等到一个从库的ack， 就开始给客户端返回确认。 这时， 在从库上执行查询请求， 就有两种情况：
- 如果查询是落在这个响应了ack的从库上， 是能够确保读到最新数据；
- 但如果是查询落到其他从库上， 它们可能还没有收到最新的日志， 就会产生过期读的问题；
等主库位点方案
select master_pos_wait(file, pos[, timeout]);这条命令的逻辑如下：
- 它是在从库执行的；
- 参数file和pos指的是主库上的文件名和位置；
- timeout可选， 设置为正整数N表示这个函数最多等待N秒。
等主库位点方案的逻辑如下：
- trx1事务更新完成后， 马上执行show master status得到当前主库执行到的File和Position；
- 选定一个从库执行查询语句；
- 在从库上执行select master_pos_wait(File, Position, 1)；
- 如果返回值是>=0的正整数， 则在这个从库执行查询语句；
- 否则， 到主库执行查询语句。
GTID方案
select wait_for_executed_gtid_set(gtid_set, 1);这条命令的逻辑是：
- 等待， 直到这个库执行的事务中包含传入的gtid_set， 返回0；
- 超时返回1。
等GTID方案的执行流程就变成了：
- trx1事务更新完成后， 从返回包直接获取这个事务的GTID， 记为gtid1；
- 选定一个从库执行查询语句；
- 在从库上执行 select wait_for_executed_gtid_set(gtid1, 1)；
- 如果返回值是0， 则在这个从库执行查询语句；
- 否则， 到主库执行查询语句