Dawn's Blogs

分享技术 记录成长

0%

另一个树的子树

另一个树的子树

解题思路

root的每一个节点上,判断以这个节点为根的树是否与subRoot相同。

判断两个树是否相等的三个条件是的关系,即:

  1. 当前两个树的根节点值相等;
  2. 并且,root1的左子树和root2的左子树相等;
  3. 并且,root1的右子树和root2的右子树相等。

而判断 一棵树是否是另一棵树的子树的三个条件是的关系,即:

  1. 当前两棵树相等;
  2. 或者,subRootroot的左子树中;
  3. 或者,subRootroot的右子树中。
阅读全文 »

问题优化

如何防止消息丢失

  • 生产者:把ACK设置为1(等待leader的ACK)或者ALL(leader及其follower同步之后返回ACK)

  • 消费者:把自动提交设置为手动提交offset

如何防止消息重复消费

在防止消息丢失的⽅案中,如果生产者发送完消息后,因为网络抖动,没有收到ACK,但实际上broker已经收到了。此时生产者会进行重试,于是broker就会收到多条相同的消息,从而造成消费者的重复消费

或者消费者已经消费了数据,但是offset没来得及提交,会导致重复消费。

解决方案,消费者保证幂等性:

  • 在数据库中使用业务id作为唯一约束

顺序消费

  • 生产者:在发送时将ACK不能设置0,关闭重试,使用同步发送,等到发送成功再发送下⼀条。确保消息是顺序发送的。
  • 消费者:消息是发送到⼀个分区中,只能有⼀个消费组的消费者来接收消息。

在Kafka中若要实现顺序消费,会牺牲性能,但是Rocket MQ有专门的功能实现顺序消费。

解决消息积压问题

  • 在⼀个消费者中启动多个线程,让多个线程同时消费。
  • 可以创建多个消费组,创建多个消费者,部署在不同的服务器上。
  • 创建⼀个消费者,该消费者另建一个主题,分配多个分区和多个消费者。消费者收到消息后,立即发往这个新的topic,此时,新的主题的多个分区的多个消费者就开始⼀起消费了。

延迟队列

订单创建后,超过30分钟没有⽀付,则需要取消订单,这种场景可以通过延时队列来实现。

具体方案

  • Kafka中创建多个主题,每个topic表示延时的间隔,如topic_30m表示延时30分钟的延时队列
  • 消费者消费该主题的消息
  • 消费者消费消息时判断消息的创建时间和当前时间是否超过30分钟(前提是订单没支付):
    • 若超过了30分钟,去数据库中修改订单状态为已取消
    • 若没有超过30分钟,记录当前消息的offset,并不再继续消费之后的消息。等待X分钟后,再次向kafka拉取该offset及之后的消息,继续进行判断,以此反复。

Controller

什么是Controller

在Kafka中,需要有一个管理者,称为Controller,它在ZooKeeper的帮助下管理和协调整个Kafka集群。Controller本身也是一台Broker节点,只不过需要负责一些额外的工作(追踪集群中的其他Broker,并在合适的时候处理新加入的和失败的Broker节点、Rebalance分区、分配新的leader分区等)。

Kafka集群中始终只有一个Controller Broker。

如何被选举出来

Broker 在启动时,会尝试去 ZooKeeper 中创建/controller临时序号节点,获得的序号最小的那个broker将会作为集群中的controller。

Controller作用

Controller的作用:

  • 当集群中有broker新增或减少,controller会同步信息给其他broker
  • 当集群中有分区新增或减少,controller会同步信息给其他broker

处理下线的Broker

Controller可以依据ZooKeeper的Watch机制,来监听Broker的变化。

每个 Broker 启动后,会在zookeeper的/Brokers/ids下创建临时znode。当Broker宕机或主动关闭后,该Broker与ZooKeeper的会话结束,这个znode会自动删除。

ZooKeeper的Watch机制会将节点的变化情况推送给Controller,这样Controller就知道某个Broker宕机了,可以采取行动决定哪些Broker上的分区成为leader分区(选择isr列表中最靠前的作为新的leader)。然后,它会通知每个相关的Broker。

处理新加入到集群中的Broker

大部分情况下,Broker的失败很短暂,这意味着Broker通常会在短时间内恢复。所以当节点离开群集时,与其相关联的元数据并不会被立即删除。

当Controller注意到Broker已加入集群时,它将使用Broker ID来检查该Broker上是否存在分区,如果存在,则Controller通知新加入的Broker和现有的Broker,新的Broker上面的follower分区再次开始复制现有leader分区的消息。为了保证负载均衡,Controller会将新加入的Broker上的follower分区选举为leader分区。

脑裂问题

如果controller Broker 挂掉了,Kafka集群必须找到可以替代的controller,集群将不能正常运转。这里面存在一个问题,很难确定Broker是挂掉了,还是仅仅只是短暂性的故障。但是,集群为了正常运转,必须选出新的controller。如果之前被取代的controller又正常了,他并不知道自己已经被取代了,那么此时集群中会出现两台controller。

比如,某个controller由于GC而被认为已经挂掉,并选择了一个新的controller。在GC的情况下,在最初的controller眼中,并没有改变任何东西,该Broker甚至不知道它已经暂停了。因此,它将继续充当当前controller。现在,集群中出现了两个controller,它们可能一起发出具有冲突的命令,就会出现脑裂的现象。

epoch number

Kafka种,使用使用epoch number(纪元编号)来避免脑裂问题。epoch number只是单调递增的数字,第一次选出Controller时,epoch number值为1,如果再次选出新的Controller,则epoch number将为2,依次单调递增。

每个新选出的controller通过Zookeeper获得获得一个全新的、数值更大的epoch number 。其他Broker 在知道当前epoch number 后,如果收到由controller发出的包含较小epoch number的消息,就会忽略它们。

HW机制

LEO(Log End Offset)是某个副本最后消息的消息位置。

HW(High Watermark)高水位,是指已完成同步的位置。消费者最多只能消费到HW所在的位置。

image-20230704105213113

另外,每一个leader和follower各⾃负责更新自己的HW的状态。对于leader新写⼊的消息,consumer不能立刻消费,leader会等待该消息被所有ISR中的副本同步后更新HW,此时消息才能被consumer消费。这样就保证了如果leader所在的broker失效,该消息仍然可以从新选举的leader中获取。

用 Rand7() 实现 Rand10()

用 Rand7() 实现 Rand10()

解题思路

原理

1
2
3
4
5
6
已知 rand_N() 可以等概率的生成[1, N]范围的随机数
那么:
(rand_X() - 1) × Y + rand_Y() ==> 可以等概率的生成[1, X * Y]范围的随机数,即实现了rand_XY()


rand_N() % Y +1 ==> 只要N是Y的倍数,就可以实现利用rand_N()实现rand_Y()

要实现rand10(),就需要实现rand_N(),并且保证N大于10且是10的倍数。这样就可以通过rand_N() % 10 + 1得到[1, 10]范围内的随机数了。

(rand7()-1) × 7 + rand7() ==> rand49(),但是49不是10的倍数。这里就涉及到了“拒绝采样”的知识了,也就是说,如果某个采样结果不在要求的范围内,则丢弃它。

解题代码

1
2
3
4
5
6
7
8
func rand10() int {
for {
num := (rand7()-1) * 7 + rand7() // rand49()
if num <= 40 { // 拒绝采样
return num % 10 + 1
}
}
}
  • 优化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func rand10() int {
for {
a := rand7()
b := rand7()
num := (a-1) * 7 + b // rand49
if num <= 40 { // 拒绝采样
return num % 10 + 1
}

a = num - 40 // rand9
b = rand7()
num = (a-1) * 7 + b // rand63
if num <= 60 {
return num % 10 + 1
}

a = num - 60 // rand3
b = rand7()
num = (a-1) * 7 + b // rand21
if num <= 20 {
return num % 10 + 1
}
}
}
阅读全文 »

生产者

选择Partition原则

在kafka中,一个topic指定了多个partition,生产者选择partition的方式:

  1. partition在写⼊的时候可以指定需要写⼊的partition,如果有指定,则写⼊对应的partition。
  2. 如果没有指定partition,但是设置了数据的key,则会根据key的值hash出⼀个partition。
  3. 如果既没指定partition,⼜没有设置key,则会采⽤轮询⽅式,即每次取⼀小段时间的数据写⼊某个partition,下⼀⼩段的时间写⼊下⼀个partition。

同步发送和异步发送

同步发送

⽣产者同步发消息,在收到kafka的ACK告知发送成功之前⼀直处于阻塞状态。

异步发送

⽣产者发消息,发送完后不用等待broker给回复,直接执⾏下面的业务逻辑。

注意:异步发送可能会丢失消息。

生产者ACK机制

同步发送的前提下,生产者向集群发送消息时,关于ACK应答机制有3个配置:

  • 0代表producer往集群发送数据不需要等待集群的返回。也就是说,集群不需要任何broker收到消息,就立刻返回ACK给生产者。不确保消息发送成功。安全性最低但是效率最⾼。
  • 1代表producer往集群发送数据只要leader应答(Leader将消息写入本地日志中)就可以发送下⼀条,只确保leader发送成功。默认选项。
  • all代表producer往集群发送数据需要所有的follower都完成从leader的同步才会发送下⼀条,确保leader发送成功和所有的副本都完成备份。安全性最⾼,但是效率最低。
阅读全文 »

副本

副本是为了为主题中的分区创建多个备份,多个副本在kafka集群的多个broker中,会有⼀个副本作为leader,其他是follower。

下图是拥有2个分区,3个副本的主题:

副本

  • leader:kafka的写和读的操作,都发⽣在leader上。leader负责把数据同步给follower。当leader挂了,经过主从选举,从多个follower中选举产⽣⼀个新的leader。
  • follower:接收leader同步的数据,在leader宕机后参与选举。
  • isr:可以同步和已同步的节点会被存入到isr集合中。如果isr中的节点性能较差,会被踢出isr集合(不能参与选举)。

集群消费

集群消费

图中Kafka集群有两个broker,每个broker中有多个partition。

  • 一个partition只能被一个消费组里的某一个消费者消费,从而保证消费顺序

  • Kafka只在partition的范围内保证消息消费的局部顺序性,不能在同⼀个topic中的多个partition中保证总的消费顺序性。

  • 一个消费者可以消费多个partition,但是消费者组中的消费者数量不能比一个topic中的partition数量多,否则多出来的消费者消费不到消息。

  • 如果消费者宕机,会触发rebalance机制,让其他消费者来消费该分区。

对角线遍历

对角线遍历

解题思路

划分为两种遍历形式:朝着右上方遍历和朝着左下方遍历。

解题代码

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
39
40
41
42
43
44
45
46
func findDiagonalOrder(mat [][]int) []int {
m := len(mat)
n := len(mat[0])
res := make([]int, m*n) // 记录遍历序列
count := 0 // 记录已经遍历的元素个数
row, col := 0, 0 // 待遍历元素所在行、列
for count < m*n {
if row == m-1 && col == n-1 {
// 遍历到最后一个元素(右下角的元素)
res [count] = mat[row][col]
break
}
// 向斜右上方遍历
for row >= 0 && col < n {
res[count] = mat[row][col]
count++
row--
col++
}
if col < n {
// 在遍历矩阵的左上部分
row++
} else {
// 在遍历矩阵的右下部分
row += 2
col--
}
// 向斜左下方遍历
for row < m && col >= 0 {
res[count] = mat[row][col]
count++
row++
col--
}
if row < m {
// 在遍历矩阵的左上部分
col++
} else {
// 在遍历矩阵的右下部分
col += 2
row--
}
}

return res
}

长度最小的子数组

长度最小的子数组

解题思路

利用滑动窗口的思想,start指向窗口的起始位置,end指向窗口的终止位置的后一位,sum为窗口内数字之和:

  • 如果sum < targetend需要向后移动
  • 如果sum > targetstart需要向前移动

解题代码

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
func minSubArrayLen(target int, nums []int) int {
start, end := 0, 0 // 滑动窗口的起始位置、终止位置的后一位
minLen := math.MaxInt64 // 连续子数组的最小长度
sum := 0
for end < len(nums) {
// end向后移动
for sum < target && end < len(nums) {
sum += nums[end]
end++
}
// start向前移动
for sum >= target {
if end-start < minLen {
minLen = end-start
}
sum -= nums[start]
start++
}
}

if minLen == math.MaxInt64 {
// 不存在符合条件的子数组
return 0
} else {
// 存在
return minLen
}
}

删除二叉搜索树中的节点

删除二叉搜索树中的节点

解题思路

  • 当待删除节点是叶子节点时,直接删除

  • 待删除节点只有一个分支时,用其分支节点代替待删除的节点

  • 待删除节点的左右子树均存在时:

    • 找到其后继节点,交换后继节点和当前待删除节点的值
    • 删除右子树中值为key的节点

解题代码

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func deleteNode(root *TreeNode, key int) *TreeNode {
if root != nil {
if root.Val == key {
// 找到待删除节点
if root.Left == nil && root.Right == nil {
// 叶子节点直接删除
return nil
}
if root.Left != nil && root.Right == nil {
// 只有左子树,用左子树代替
return root.Left
}
if root.Right != nil && root.Left == nil {
// 只有右子树,用右子树代替
return root.Right
}
// 左右子树都存在
// 找到后继节点
next := nextNode(root)
// 交换后继节点与当前节点的值
root.Val, next.Val = next.Val, root.Val
// 在右子树中删除值为key的节点
root.Right = deleteNode(root.Right, key)
} else if root.Val > key {
// 进入左子树查找
root.Left = deleteNode(root.Left, key)
} else {
// 进入右子树查找
root.Right = deleteNode(root.Right, key)
}
}

return root
}

// 返回以root为根节点,中序遍历中的后继节点
func nextNode(root *TreeNode) *TreeNode {
// 后继节点为root右子树的最左边的节点
next := root.Right
for next.Left != nil {
next = next.Left
}
return next
}

CAP理论

CAP定理

CAP理论为:⼀个分布式系统最多只能同时满足⼀致性(Consistency)、可用性(Availability)和分区容错性(Partition tolerance)这三项中的两项。

  • 一致性(Consistency):即更新操作成功并返回客户端后,所有节点在同一时间的数据完全一致。
  • 可用性(Availability):服务⼀直可用,而且是正常响应时间。
  • 分区容错性(Partition tolerance):分布式系统在遇到某节点或网络分区故障的时候,仍然能够对外提供满足一致性或者可用性的服务。

BASE理论

BASE理论是对CAP理论的延申,核心思想就是即使无法做到强一致性(CAP的一致性就是强一致性),但可以采取适当的方式达到最终一致性。

  • 基本可用(Basically Available):指分布式系统在出现故障的时候,允许损失部分可用性,即保证核心可用。
  • 软状态(Soft State):允许系统存在中间状态,而该中间状态不会影响系统整体可⽤性。分布式存储中⼀般⼀份数据至少会有三个副本,允许不同节点间副本同步的延时就是软状态的体现。
  • 最终一致性(Eventual Consistency):指系统中的所有数据副本经过⼀定时间后,最终能够达到⼀致的状态。

ZooKeeper追求的一致性

ZooKeeper保证的最终一致性又叫做顺序一致性,即每个结点的数据都是严格按事务的发起顺序生效的。

ZooKeeper如何保证事务的顺序

zookeeper中的事务ID为ZXID,ZXID由Leader节点生成,有新写入事件时,Leader生成新ZXID并随提案一起广播,每个结点本地都保存了当前最近一次事务的ZXID,ZXID是递增的,所以谁的ZXID越大,就表示谁的数据是最新的。

ZXID的生成规则如下:

ZXID

ZXID由两部分组成:

  • 任期:完成本次选举后,直到下次选举前,由同一Leader负责协调写入
  • 事务计数器:单调递增,每生效一次写入,计数器加一

ZXID的低32位是计数器,所以同一任期内,ZXID是连续的,每个结点又都保存着自身最新生效的ZXID,通过对比新提案的ZXID与自身最新ZXID是否相差1,来保证事务严格按照顺序生效的。

消息队列

应用场景

  • 缓存/消峰:将消息暂存在消息队列中,以生产消息和消费消息的处理速度不一致的情况。
  • 解耦:可以修改或者扩充生产者和消费者,只需要遵守消息格式的一致即可。

消息队列解耦

  • 异步通信:允许用户把一个消息放入队列,但并不立即处理它,然后在需要的时候再去处理它们。

消息队列异步通信

消息队列两种模式

点对点模式

类似于队列,消费者消费消息后会清除消息。

发布/订阅模式

消息⽣产者(发布)将消息发布到topic中,同时有多个消息消费者(订阅)消费该消息。和点对点⽅式不同,发布到topic的消息会被所有订阅者消费。

Kafka介绍

Kafka是一种高吞吐量的分布式发布订阅消息系统。

同时Kafka结合点对点模型和发布订阅模型

  • 对于同一个消费者组Consumer Group,一个message只有被一个consumer消费 - 点对点模型
  • 同一个消息可以被广播到不同的Consumer Group中 - 发布订阅模型

架构

Kafka架构

  • Producer:Producer即⽣产者,消息的产⽣者,是消息的⼊⼝。
  • kafka cluster:kafka集群,⼀台或多台服务器组成
    • Broker:Broker是指部署了Kafka实例的服务器节点。每个服务器上有⼀个或多个kafka的实例,我们姑且认为每个broker对应⼀台服务器。每个kafka集群内的broker都有⼀个不重复的编号。
    • Topic:消息的主题,可以理解为消息的分类,kafka的数据就保存在topic。在每个broker上都可以创建多个topic。实际应⽤中通常是⼀个业务线建⼀个topic。
    • Partition:Topic的分区,每个topic可以有多个分区,分区的作⽤是做负载,提⾼kafka的吞吐量。同⼀个topic在不同的分区的数据是不重复的,partition的表现形式就是⼀个⼀个的⽂件夹。为了提高可靠性,提出分区的副本,分为Leader和Follower,生产和消费只针对Leader。
    • Replication:每⼀个分区都有多个副本,副本的作⽤是做备份。当主分区(Leader)故障的时候会选择⼀个备胎(Follower)上位,成为Leader。在kafka中默认副本的最⼤数量是10个,且副本的数量不能⼤于Broker的数量,follower和leader绝对是在不同的机器,同⼀机器对同⼀个分区也只可能存放⼀个副本(包括自己)。
  • Consumer:消费者,即消息的消费⽅,是消息的出⼝。
    • Consumer Group:我们可以将多个消费组组成⼀个消费者组,在kafka的设计中同⼀个分区的数据只能被消费者组中的某⼀个消费者消费同⼀个消费者组的消费者可以消费同⼀个topic的不同分区的数据,这也是为了提⾼kafka的吞吐量!
阅读全文 »

zookeeper集群中的节点共有三种角色:

  • Leader:处理集群中的所有事务请求,包括读和写,集群中只有一个Leader
  • Follower:只处理请求,可以参与Leader选举
  • Observer:只处理请求,但是不能参与Leader选举

ZAB协议

介绍

zookeeper作为⾮常重要的分布式协调组件,需要进行集群部署,集群中通常会以一主多从的方式进行部署。zookeeper为了保证数据的一致性,使用ZAB(zookeeper atomic broadcast)协议,这一协议解决了zookeeper的崩溃恢复和主从数据同步的问题。

zookeeper集群

ZAB协议的四种节点状态

ZAB中协议定义了四种节点状态:

  • Looking:选举状态
  • Following:Follower节点的状态
  • Leading:Leader节点的状态
  • Observing:Observer节点的状态

Leader选举过程

集群上线时的Leader选举

若进行Leader选举,则至少需要两台机器,这里选取3台机器组成的服务器集群为例。在集群初始化阶段,当有一台服务器Server1启动时,其单独无法进行和完成Leader选举,当第二台服务器Server2启动时,此时两台机器可以相互通信,每台机器都试图找到Leader,于是进入Leader选举过程。选举过程如下:

  1. 每个Server发出一个投票。由于是初始情况,Server1和Server2都会将自己作为Leader服务器来进行投票,每次投票会包含所推举的服务器的myid和ZXID,使用(myid, ZXID)来表示,其中myid为服务器的唯一标识,ZXID为事务号。此时Server1的投票为(1, 0),Server2的投票为(2, 0),然后各自将这个投票发给集群中其他机器。

  2. 接受来自各个服务器的投票。集群的每个服务器收到投票后,首先判断该投票的有效性,如检查是否是本轮投票、是否来自LOOKING状态的服务器。

  3. 处理投票。针对每一个投票,服务器都需要将别人的投票和自己的投票进行PK,PK规则如下:

    • 优先检查ZXID。ZXID比较大的服务器优先作为Leader。
    • 如果ZXID相同,那么就比较myid。myid较大的服务器作为Leader服务器。

    对于对于Server1而言,它的投票是(1, 0),接收Server2的投票为(2, 0),首先会比较两者的ZXID,均为0,再比较myid,此时Server2的myid最大,于是更新自己的投票为(2, 0),然后重新投票,对于Server2而言,其无须更新自己的投票,只是再次向集群中所有机器发出上一次投票信息即可。

  4. 统计投票。每次投票后,服务器都会统计投票信息,判断是否已经有过半机器接受到相同的投票信息,对于Server1、Server2而言,都统计出集群中已经有两台机器接受了(2, 0)的投票信息,此时便认为已经选出了Leader。

  5. 改变服务器状态。一旦确定了Leader,每个服务器就会更新自己的状态。

崩溃恢复时的Leader选举

Leader建立完成后,Leader会周期性的不断向Follower发送心跳。当Leader崩溃后,Follower会进入Looking状态,重新进行Leader选举,此时集群不能对外服务。

主从服务器之间的数据同步

  1. 客户端向Leader节点写数据
  2. Leader节点把数据写到自己的数据文件中,并给自己返回一个ACK
  3. Leader把数据发送给Follower
  4. Follower将数据写到本地数据文件中
  5. Follower返回ACK给Leader节点
  6. Leader收到半数以上的ACK后,向Follower发送Commit
  7. 从节点收到Commit后把数据文件中的数据写到内存中

zookeeper数据同步