分享一道后端的负载均衡面试题和我自己的做法。使用 java 实现。
根据 nodes 写一个 SLB（负载均衡），按 weight 来做粗略划分，注意 nodes 并不是固定的，给出的代码为了说明才固定了 3 个值。nodes 结构如下：
nodes = [
{
'id': 1,
'weight': 100, # 32 core
'count': 0 # 5000, 5151
},
{
'id': 2,
'weight': 50, # 16 core
'count': 0 # 2500, 2350
},
{
'id': 3,
'weight': 50, # 16 core
'count': 0 # 2500, 2450
}
.......
]
- id 就是 id，weight 是权重，count 是node 被调用了多少次（用来评估结果）
- 后续要求要
O(1)的时间复杂度
有两种思路：
-
将其按照 weight 大小在一条线段上面画好，然后产生 (0,所有weight的总和) 上面的随机数，落在哪个区间就调用哪个线程。
但是这种方法复杂度比较高。
-
按照 weight 的比例分配进 HashMap， 之后对 hashMap 进行处理。
这一步可以先将其按照比例来缩短，比如上面这种100，50，50 的情况就可以变成 2，1，1 这种。这样节省了整个 HashMap 之中的空间分配。
下面是我的代码：
import java.util.*;
public class Main {
public static void main(String[] args) {
int[][] nodes=这里是输入，但是提示 githubPage 有错误，所以输入部分删掉了。我使用的是一个二维数组来存储
HashMap<Integer,Integer> hashMap=new HashMap<>();
int sum_weight=0;
int sum_proceed=0;
for(int[] i:nodes)
{
sum_weight=i[1]+sum_weight;
}
for(int[] i:nodes)
{
i[1]=i[1]*4/sum_weight;
}
for(int[] i:nodes)
{ int top=i[1];
for(int j=0;j<top;j++){
hashMap.put(sum_proceed,i[0]);
sum_proceed+=1;}
}
for(int i=0;i<10000;i++)
{
Random rand=new Random();
int r=rand.nextInt(sum_proceed);
int index=hashMap.get(r);
nodes[index-1][2]=nodes[index-1][2]+1;
}
System.out.println(nodes.toString());
}
}
下面是一些相关知识点的自我复习：
参照：
https://blog.csdn.net/ythunder/article/details/65664309
1.Left Join
select Users.UserName,EventOrder.EventID,EventOrder.OrderID From Users left join EventOrder on EventOrder.UserID=Users.Id Order by users.Id
上面这一句会将 Users 之中的所有条目全都列出来，在 EventOrder 的表之中将其匹配后，如果没有匹配到的条目，就将 EventOrder.EventID 和 EventOrder.OrderID 两个列置空。
下面这个是一个示例。可以看到其中很多信息为空。
2. TCP
之前专门写了一篇针对 TCP 和 HTTPS 的博文：梳理TCP,HTTP,HTTPS,HTTP/2
下面是 TCP 的报文头的内容：
- 16位源端口号和16位目的端口号：标识端口的信息
- 32位序号和32位确认号：确认本次传输的字节流的编号，通过这个来确保来往的数据有序：比如之前的序号是1000，发送了1000，下一次的序号就是2000。确认号的作用是用于响应 TCP 报文段，收到的 TCP 报文段的序号 +1 就是确认号。
- 4位头部长度：标示该头部有多少个4字节，一共表示最长15*4=60 字节，同 IP 头部。4 bytes=4*8=32 bits
- 6位保留，6位标志符：
- URG：紧急指针
- ACK：确认号是否有效
- PSH：接收端应该立即从TCP缓冲区读走数据
- RST：对方要求重新连接
- SYN：请求建立一个链接
- FIN：通知对方本端要关闭连接
- 16位窗口大小：告诉对方TCP缓冲区还可以容纳多少字节
- 16位校验和：检验TCP包是否发生损坏
- 16位紧急指针：其和序号段的值相加之后表示最后一个紧急数据的下一个字节的序号
里面主要针对了 TCP 的三次握手和四次挥手进行了梳理。下面对于 TCP 的流量控制和拥塞控制进行一点解析：
2.1 流量控制
流量控制是让发送方的速率不要过快，要让接收方来得及接受。
使用方法为：滑动窗口机制。
下面这张图之中大写的 ACK 是我们上面所提到过的 ACK 标志符，下面的 ack 是确认字段的值 ack，rwnd是receiver window，即接收窗口。
这张图之中可以看到 B 进行了三次流量控制，其所有手段即将 rwnd 的值不断减小直至为0，这样到最后就不允许发送方再发送数据了。这种使发送方暂停发送的状态将持续到主机 B 重新发出一个新的窗口值为止。
B 在对 A 发送的三个报文段都设置了 ACK=1，只有在 ACK = 1的时候确认号字段才有意义。
2.2 拥塞控制
2.2.1 拥塞定义
即对资源的需求超过了可用的资源。
拥塞控制：防止过多的数据注入到网络之中，这样可以使网络之中的路由器不至于过载。
2.2.2 拥塞控制方法
2.2.2.1 慢启动(slow-start) 和 拥塞避免 (congestion avoidance)
发送方维持一个拥塞窗口 cwnd (congestion window) 的状态变量，其大小取决于网络的拥塞程度，且动态的变化。发送方使自己的发送窗口等于拥塞。
发送方控制拥塞窗口的原则是：网络如果没有出现拥塞，拥塞窗口就大一点，但是只要出现了拥塞，拥塞窗口就小一点，以减少注入到网络之中的分组数。
一个传输轮次的是按就是往返时间 RTT。
2.2.2.2 快重传和快恢复
快重传要求接收方对每个失序的报文段之后就立刻发出重复确认（使发送方及早知道报文段没有到达对方），而不需要等待自己发送数据的时候进行捎带的确认。
与快重传算法配合使用的还有快恢复算法，有以下几点：
<1>. 当发送方连续收到三个重复确认，就执行“乘法减小”算法，把慢开始门限ssthresh减半。这是为了预防网络发生拥塞。请注意：接下去不执行慢开始算法。
<2>. 由于发送方现在认为网络很可能没有发生拥塞，因此与慢开始不同之处是现在不执行慢开始算法（即拥塞窗口cwnd现在不设置为1），而是把cwnd值设置为慢开始门限ssthresh减半后的数值，然后开始执行拥塞避免算法（“加法增大”），使拥塞窗口缓慢地线性增大。
3. HTTPS
下面主要是对 HTTPS 的设计和过程进行一定的梳理。尤其是对其 CA 的传递部分进行比较具体的叙述。
3.1 加密算法
3.1.1 对称加密(Symmetric-key algorithm)
加密和解密使用的是同一个密钥
例如：DES、AES-GCM、ChaCha20-Poly1305等
3.1.2 非对称加密（Public-key cryptography）
加密和解密使用的密钥是完全不同的，分为公钥和私钥。公钥和算法都是公开的，任何人都可以使用公钥进行加密，但是只有公钥是没有办法解密的。解密的话需要私钥，私钥是保密的。
公钥用来加密/验章使用的。
私钥用来解密/盖章使用的。
例如：RSA、DSA、ECDSA、 DH、ECDHE。最常用的是 RSA 体制
3.1.3 哈希算法
其仅仅可以用来加密，没法逆向将算法加密之前的内容放出来。
例如：MD5、SHA-1、SHA-2、SHA-256 等
3.2 HTTPS 的过程
首先做一点自己对于不对称加密的总结：
在 Client 和 Server 通信的过程之中，Server 所持有的是私钥， Client 持有的是公钥。
-
当 Client 要对 Server 发送信息的时候，其使用公钥加密，Server 使用私钥解密。这个过程之中的信息只有 Server 才能读取，其他人没法读取。
-
当 Server 回复 Client 的消息的时候，其首先对自己发送的消息进行数字摘要(digest)，之后将摘要使用私钥 进行签名之后发送回去。Client 在接受之后使用公钥来解密对照 digest 的信息是否正确。
注意：所有有这个公钥的 Client 都可以解密这个 Server 发送的消息，也就是从 Server 发送到 Client 的过程之中的信息是不保密的，能做到的也就是确认这个信息是由当前 Server 所传递出来的。
剩下的部分都在之前的博文之中，不再赘述。
