前几天面试了字节跳动,记录下面试遇到的算法题

题目

输入: 用户日志(time, user_id, login | logout)
输出:同时在线人数的峰值,精确到秒

一开始,想了一分钟左右,想到了一个比较简单粗暴的方式。

使用位图的思想,将一天 分成 86400 秒,每秒单独统计,最后遍历一遍,找最大的值所对应的秒数

总的来说简单粗暴,也是比较容易想到的方式。只是由于按照每秒来统计了,所以写入到这个位图的效率是很低的。如果用户一天都在线, 那么就要写86400 次,明显是很慢的。

面试官一看这么粗暴,问了句,有没有优化的方案?

按照套路来,要么动态规划把历史记录一下,要么二分一下。动态规划明显不适用,二分的思想好像是可行的。

先将一天分成24小时,按照上面的方法统计一遍,找到峰值的小时,然后从这小时里面按照分钟统计一遍,找到峰值的分钟,再将分钟分成60秒,再统计一遍

理论上,每个用户跨越的时间越长,这样统计起来应该是会比第一种方式优秀很多。

但是面试官的问题来了,如果有多个峰值怎么办,最坏情况下每秒都是峰值,这种方式会比第一种方式慢得多

那就得继续想呗,想了几分钟,面试官看我想不出来就放弃了,我的心也凉了下,感觉没戏了

面试结束之后,继续想了下这个问题有没有更好的解法

毕竟同一个坑不能栽进去两次对不对。

可能是最优解的解法来了

跳开之前的统计所有秒数的想法,这个问题的解法就简单多了

我们先来想一下什么时候会有峰值,肯定是在线人数最多的时候。那么某个时间点在线的人数怎么算呢,很明显是 所有在这个时间点之前登入的 - 在这个时间点之前所有登出的。

那么算法也很简单,

  1. 定义三个变量,其中一个记录当前在线人数(currentVal),一个最大值(maxVal),最后一个记录其对应的秒数的数组(seconds)。
  2. 将日志分成 登录,登出 两种状态,并且根据时间进行正向排序
  3. 遍历步骤2得到的日志,如果是登录则 currentVal + 1 并且跟 maxVal 对比,如果比 maxVal 大,则将 maxVal 设置为 currentVal, seconds 设置为 当前秒数, 如果 maxVal == currentVal, 则 seconds 增加当前秒数。如果是登出,则 currentVal - 1 (不过更完美点应该判断下当前是不是maxVal, 如果是则将上一次峰值的秒数,到当前秒数的区间写入到 seconds
  4. 遍历完成之后得到的 maxVal 就是 峰值, seconds 就是对应的秒数列表

比如说,日志长这样

uid        登录时间         登出时间
uid1       00:00:01        00:00:10
uid2       00:00:02        00:00:05
uid3       00:00:03        00:00:05

步骤2中,将其变成

uid     action      时间     
uid1    登入     00:00:01    
uid2    登入     00:00:02
uid3    登入     00:00:03    
uid2    登出     00:00:05  // 到这里的时候需要 将上一次峰值到当前值(00:00:03 到 00:00:04 )写入到 seconds
uid3    登出     00:00:05
uid1    登出     00:00:10

步骤三

`currentVal` -> 1   -> 2   -> 3   -> 2   -> 1   -> 0
`maxVal`     -> 1   -> 2   -> 3   -> 3   -> 3   -> 3
`seconds`    -> [1] -> [2] -> [3] -> [3,4] -> [3,4] -> [3,4] 

最后,好像虽然做不出来,面试还是过了,感谢面试官抬一手。 如果有更好的解法,或者这个解法有问题,也方便留言。

目标

  1. Latency
    多久完成一次请求处理或者操作;
  2. Rate:
    每秒的操作或请求速率;
  3. Throughput
    每秒传输数据大小;
  4. Utilization
    资源随时间繁忙程度;
  5. Cost
    成本,性价比

Resources

linux系统资源

  1. CPU
  2. Memory
  3. I/O
  4. Network

常用linux命令

  • uptime

[root@LinServ-1 ~]# uptime -V #显示uptime命令版本信息
procps version 3.2.7

[root@LinServ-1 ~]# uptime
15:31:30 up 127 days, 3:00, 1 user, load average: 0.00, 0.00, 0.00
说明:
15:31:30 //系统当前时间 up 127 days, 3:00
//主机已运行时间,时间越大,说明你的机器越稳定。 1 user //用户连接数,是总连接数而不是用户数
load average: 0.00, 0.00, 0.00 // 系统平均负载,统计最近1,5,15分钟的系统平均负载

那么什么是系统平均负载呢? 系统平均负载是指在特定时间间隔内运行队列中的平均进程数。

如果每个CPU内核的当前活动进程数不大于3的话,那么系统的性能是良好的。如果每个CPU内核的任务数大于5,那么这台机器的性能有严重问题。

如果你的linux主机是1个双核CPU的话,当Load Average 为6的时候说明机器已经被充分使用了。
  • dmesg

    dmesg | tail 命令可以查看最后10条系统消息,Error消息会给出有用信息,如OOM及TCP丢弃请求等

  • vmstat

    vmstat 1命令每秒打印出虚拟内存相关metric;

    r:表示正运行在CPU的进程数,值大于CPU核数说明系统繁忙了;
    si, so:Swap-ins, swap-outs, 如果值为非零,说明内存不够用了;
    us,sy,id,wa,st:user,kernel,ide,wait I/O及stolen time;

  • mpstat -P ALL 1每秒打印出各个CPU的运行状态

    %waitio:等待I/O时间
    %sys:系统调用时间

  • pidstat

    pidstat 1命令每秒打印出进程跑在哪个CPU核上以及使用率情况

  • iostat

    iostat -xz 1命令每秒打印出每块设备使用情况
    r/s,w/s,rkB/s,wkB/s:每秒完成读写次数及数据大小;
    await:平均等待I/O时间(单位是毫秒);
    Avgqu-sz:发往设备的请求队列平均长度;
    %util:设备使用率,值越大越繁忙;

  • free

    free -m命令查看系统可用内存情况

  • sar

    sar -n DEV 1命令查看网卡收发是否达到上限
    rxkB/s:每秒接收的数据包总数;
    txkB/s:每秒传输的数据包总数;

  • sar2

    sar -n TCP,ETCP 1命令查看网卡收发是否达到上限
    active/s:每秒本地发起的TCP连接数(即调用connect());
    passive/s:每秒远程发起的TCP连接数(即调用accept());
    retrans:每秒TCP重传次数;

  • top

    top命令double check系统和进程运行状态;

1. 简单实现

一般能想到的实现应该是记录一个 current index, 再取mod, 存在的问题是请求不够平滑。
例如, 要对3台机器进行 加权轮询负载均衡, 权重分别是 1,2,3

机器权重
0011
0022
0033

那么结果是

次数indexmod结果命中机器
100001
211002
322002
433003
544003
655003
750001

...

存在的问题,请求会不平滑, 同一台机器的请求会比较集中,比如上面的结果,后面3次集中在 003 的机器。

2. 更好的算法

每个后端peer都有三个权重变量,先解释下它们的含义。

(1) weight

配置文件中指定的该后端的权重,这个值是固定不变的。

(2) current_weight

后端目前的权重,一开始为0,之后会动态调整。那么是怎么个动态调整呢?

每次选取后端时,会遍历集群中所有后端,对于每个后端,让它的current_weight增加它的effective_weight,

同时累加所有后端的weight,保存为total。

如果该后端的current_weight是最大的,就选定这个后端,然后把它的current_weight减去total。

如果该后端没有被选定,那么current_weight不用减小。

 

弄清了三个weight字段的含义后,加权轮询算法可描述为:

1 对于每个请求,遍历集群中的所有可用后端,对于每个后端peer执行:

  peer->current_weight += peer->effecitve_weight。
  同时累加所有peer的effective_weight,保存为total。

2 从集群中选出current_weight最大的peer,作为本次选定的后端。

3 对于本次选定的后端,执行:peer->current_weight -= total。

还是上面 3台机器 , 权重分别是 1,2,3

机器权重
0011
0022
0033

那么结果是
WXWorkCapture_15764984078276.png

请求就稍微平滑些了

参考:
Dubbo加权轮询负载均衡的源码和Bug,了解一下?
Nginx的负载均衡 - 加权轮询 (Weighted Round Robin) 上篇

example:

curl -o /dev/null -s -v --resolve www.baidu.com:443:103.235.46.39 https://www.baidu.com

输出

$ curl -o /dev/null -s -v --resolve www.baidu.com:443:103.235.46.39 https://www.baidu.com
* Added www.baidu.com:443:103.235.46.39 to DNS cache
* Rebuilt URL to: https://www.baidu.com/
* Hostname www.baidu.com was found in DNS cache
*   Trying 103.235.46.39...
* TCP_NODELAY set
* Connected to www.baidu.com (103.235.46.39) port 443 (#0)
* ALPN, offering h2
* ALPN, offering http/1.1
* successfully set certificate verify locations:
*   CAfile: /etc/ssl/certs/ca-certificates.crt
  CApath: /etc/ssl/certs
} [5 bytes data]
* TLSv1.3 (OUT), TLS handshake, Client hello (1):
} [512 bytes data]
* TLSv1.3 (IN), TLS handshake, Server hello (2):
{ [96 bytes data]
* TLSv1.2 (IN), TLS handshake, Certificate (11):
{ [3629 bytes data]
* TLSv1.2 (IN), TLS handshake, Server key exchange (12):
{ [333 bytes data]
* TLSv1.2 (IN), TLS handshake, Server finished (14):
{ [4 bytes data]
* TLSv1.2 (OUT), TLS handshake, Client key exchange (16):
} [70 bytes data]
* TLSv1.2 (OUT), TLS change cipher, Client hello (1):
} [1 bytes data]
* TLSv1.2 (OUT), TLS handshake, Finished (20):
} [16 bytes data]
* TLSv1.2 (IN), TLS handshake, Finished (20):
{ [16 bytes data]
* SSL connection using TLSv1.2 / ECDHE-RSA-AES128-GCM-SHA256
* ALPN, server accepted to use http/1.1
* Server certificate:
*  subject: C=CN; ST=beijing; L=beijing; OU=service operation department; O=Beijing Baidu Netcom Science Technology Co., Ltd; CN=baidu.com
*  start date: May  9 01:22:02 2019 GMT
*  expire date: Jun 25 05:31:02 2020 GMT
*  subjectAltName: host "www.baidu.com" matched cert's "*.baidu.com"
*  issuer: C=BE; O=GlobalSign nv-sa; CN=GlobalSign Organization Validation CA - SHA256 - G2
*  SSL certificate verify ok.
} [5 bytes data]
> GET / HTTP/1.1
> Host: www.baidu.com
> User-Agent: curl/7.58.0
> Accept: */*
> 
{ [5 bytes data]
< HTTP/1.1 200 OK
< Accept-Ranges: bytes
< Cache-Control: private, no-cache, no-store, proxy-revalidate, no-transform
< Connection: Keep-Alive
< Content-Length: 2443
< Content-Type: text/html
< Date: Tue, 03 Dec 2019 02:02:06 GMT
< Etag: "58860411-98b"
< Last-Modified: Mon, 23 Jan 2017 13:24:33 GMT
< Pragma: no-cache
< Server: bfe/1.0.8.18
< Set-Cookie: BDORZ=27315; max-age=86400; domain=.baidu.com; path=/
< 
{ [1448 bytes data]
* Connection #0 to host www.baidu.com left intact