1. 设计
1.1. 任务系统怎么保证任务完成后发奖一定成功
1.2. 设计一个限流系统怎么做? 令牌桶
1.2.1. 漏桶算法
把请求比作是水, 水来了都先放进桶里, 并以恒定速度出水(处理请求), 当水流量过大会导致桶溢出, 即拒绝服务. 请求的最大出力速度也就是水从漏桶流出的速度.
基于漏桶(桶+恒定处理速度), 可以起到对请求整流效果. 漏桶算法可基于线程池来实现, 线程池用固定容量的阻塞队列+固定个数的处理线程来实现: 最简单且最常见的漏桶实现就是基于 SynchronousQueue 的线程池, 其相当于一个空桶+固定处理线程.
注意:原生的漏桶算法以恒定速度出水(处理请求), 但是实际场景中请求的处理耗时可能不相等, 为了实现恒定速率, 一般都是限定同时处理请求的最大线程数.
1.2.2. 令牌桶算法
滑动时间窗口算法就是根据当前时间获取对应的时间窗口, 时间窗口保存有流量相关的统计值, 根据该统计值判断是否触发流控.
令牌桶算法原理是系统以恒定的速率产生令牌, 然后把令牌放到令牌桶中, 令牌桶有一个容量, 当令牌桶满了的时候, 再向其中放令牌, 那么多余的令牌会被丢弃. 当想要处理一个请求的时候,需要从令牌桶中取出一个令牌,如果此时令牌桶中没有令牌, 则拒绝该请求.
实现方案是: 起一个 Timer 线程以固定频率往桶中放令牌, 桶满时令牌溢出, 业务线程咋获取令牌时直接从桶中获取即可.
1.2.3. 滑动时间窗口算法 (rolling window)
在计数器的基础上细分更多格子, 比如说 1分钟拆分成10个格子, 随着时间的前进10格像窗口一样前行, 每格都有自己的计数器, 窗口总计数是当前时间的流量.
1.2.4. Redis 实现 (计数器)
Redis 实现限流可以使用 lua 脚本原子增加统计数据来实现, 设置过期时间1秒即1秒的限流.
1.3. 现有一个随机数可以生产0到4的数, 现在要用这个生成器生成0到6的随机数, 要保证生成的概率均匀
- 如果是从大到小的生成器, 那么只需要在生成的数不在范围内时, 重新生成即可, 因为每个数生成的概率都是一致的.
// rand8() to rand7()
function rand7() {
$a = 0;
while (true) {
($a = rand8()) === 8;
}
return $a;
}
- 从小到大的生成器, 扩大生成数的范围, 达到上部分的效果再生成.
// rand5() to rand7()
function rand7() {
$a = PHP_INT_MAX;
while ($a > 21) {
$a = 5 * (rand5() - 1) + rand5();
}
return $a % 7 + 1;
}
1.4. (2) 设计秒杀系统, 考虑正确性, 以及服务器不挂机如何设计, 怎么解决大并发
- 流控
- 请求流控: 参与秒杀的人远远大于实际成交的人数, 所以可以通过前端进行拦截, 限制最终流入系统的请求数量.
- 客户端限流: 在客户端限制频繁操作, 比如说按钮5秒只能点击一次
- 后端系统流控: 保证后端系统的压力维持在可正常处理的水平. 超过系统负载的请求, 可以直接拒绝.
- 系统架构优化
- 读取加速: 秒杀一般是读多写少的场景, 所以可以使用缓存分担数据库压力. CDN, 静态文件分离等.
- 异步处理和排队: 通过异步处理任务, 消息队列来隔离前端的压力. 提高用户请求的响应速度.
- 无状态服务设计: 实现无状态化的服务可以在秒杀活动前进行快速扩容. 比如说上云
- 单一职责原则: 使用微服务的设计思想, 秒杀服务单独部署.
- 秒杀链接加盐: URL 动态化, 通过 MD5 之类的加密代码随机字符串做 url, 然后前端通过先获取 url 再调用.
- Redis 集群: 集群, 主从同步, 读写分离, 哨兵
- Nginx 均衡负载, 恶意请求拦截
- 资源静态化: 使用 CDN 来分担压力
- 预加载库存到 Redis 中, 活动结束后再同步到数据库中. 使用 lua 脚本来解决读写分离的问题.
- 限流&降级&熔断&隔离
- 削峰填谷: 消息队列
1.5. 如何设计服务端日志, 需要记录哪些字段?
- 设计
- 日期拆分
- 不同通道拆分
- 定时清理
- 格式统一
- 推荐记录内容
- 系统启动或初始化时记录重要的系统初始化参数
- 记录系统运行过程中所有的错误
- 记录系统运行过程中所有的警告
- 在持久化数据修改时记录修改前和修改后的值
- 记录系统各个主要模块之间的请求和响应
- 重要状态变化
- 系统中一些长期执行的任务的执行进度
- 需要字段
- 环境
- 时间
- 日志级别
- 标题
- 要记录的数据
1.6. 以微博为例，有1个亿的用户，同时用户之间有关注和粉丝，用户的关注和取关操作比较频繁，如何设计架构和API接口
- 数据结构: friend(uid1, uid2)
- 架构设计
- 数据库
- 通过 uid 分库, 建立数据冗余表(friend 的反向), 这样 uid1, uid2 查都不需要遍历多库.
- 水平切分
- 通过 redis hash 储存关注被关注关系
- 模型
- pull: 关注者访问新微博列表时, 查找他的关注者列表, 整理新微博显示出来
- push: 新微博推送到每一个关注者的新微博列表中
- 数据库
1.7. 设计一个定时任务管理器
- web 管理页面
- 秒级设置: 看使用的语言, swoole 可以用定时器实现毫秒级
- 失败重试
- 超时强制结束
- 任务依赖配置
- 账户权限控制
- 任务类型
- shell 任务: 在任务节点上执行 shell 命令, 支持任务同时在多个节点上运行
- http 任务: 访问指定的 URL 地址, 由调度器直接执行, 不依赖节点
- 查看任务执行结果日志
- 任务执行结果通知, 支持邮件, slack, webhook
1.8. 压力测试
- 环境
- 压力测试环境需要和生产环境靠近
- 配置一致
- 程序版本一致
- 网络带宽一致
- 压测
- ab
- wrk
- 瓶颈
- 压测目的是找到系统的瓶颈, 一定要确定在某一方面达到瓶颈了, 压力测试才算完成
- 优化
- 内存换时间
- 增加缓存
- 内存数据库
- 使用 ssd
- 数据库优化
- 利用多核优势
- 使用合适的阻塞模型
- 分布式部署
1.9. 一个只能负载1000qps 怎么让它达到 10000 qps
找到瓶颈针对性优化
1.10. 短连接 (数据库 + 重定向)
- 流程
- 浏览器输入短链接
- DNS 解析到 IP
- 发送 HTTP GET 请求
- 通过短码参数获取对应长 URL
- 请求通过 HTTP 301 转到对应的长 URL
- 为什么用 301 而不是 302? 301 永久定向, 但是没办法统计点击数, 所以有时候会选择 302 来使用.
- 考虑因素
- 短码长度
- 储存数量
- 提供 API 调用
- 算法
- Hash 编码
- 随机生成字符串
- 并发
- 使用锁来限制重复 key 的数据写入
- 超时链接及失效链接清理
- 参考 Redis 内存淘汰策略
- 懒淘汰: 用户访问超时链接时才淘汰
- 定时淘汰: 设置定时器间断淘汰
- 定时器
- 参考 Redis lru 淘汰策略
- 参考 Redis 内存淘汰策略
1.11. 设计一个死锁
- 死锁四条件
- 互斥条件, 同一资源任意时刻是能给你个客户使用
- 不可剥夺条件: 非资源的使用者不能够抢夺资源
- 请求和保持条件: 进程已经保持了至少一个资源, 但又提出了新的请求, 而该资源已经被其它客户占用, 此时请求进程被阻塞, 但对自己已经获得的资源保持不放
- 若干客户间形成首尾等待资源关系.
- 常见场景
- InnoDB引擎下的事务, 在对数据进行查询更新的时候, 读会加上共享锁, 写会加上排他锁, 两个进程同时获取了排他锁, 等待更新时始终等对方释放共享锁, 然后自身获取排它锁, 两个进程之前就会一直等待对方.
- 解决方案
- 降低隔离界别到读已提交, 这个级别下使用 MVCC 来实现的隔离数据
- 插入的时候用
select * for update, 这个情况下会直接加排他锁, 不会加共享锁 - 提前加上分布式锁.
- 解决方案
- InnoDB引擎下的事务, 在对数据进行查询更新的时候, 读会加上共享锁, 写会加上排他锁, 两个进程同时获取了排他锁, 等待更新时始终等对方释放共享锁, 然后自身获取排它锁, 两个进程之前就会一直等待对方.
1.12. 几千万数据的表扩充新的字段如何处理?
- 临时表方法
- 创建临时表, 复制旧表的结构及索引
- 给新表加上新增的字段
- 把旧表的数据复制过来
- 这个时候可能有新数据过来, 所以最好表中有创建时间的字段, 用来对比哪些是新创建的数据. 然后是更新时间的字段, 在同步完成后检查哪些字段变更了, 再同步一次变更的数据.
- 删除旧表, 新表更名为旧表名
- 如果要保证数据的完整性, 最好是停机操作.
- 使用工具来迁移
- 原理: 临时表 + 触发器 (新数据写入时直接写入到新库中), 可以不需要创建时间字段.
1.13. 几千万数据的表如何分页?
- 为什么慢
- MySQL offset 在查询的时候并不是跳过 offset 条数据, 而是取 offset + N 行, 然后放弃前 offset 条, 返回 N 行
- offset 执行顺序在 select 之后, 所以会先取 offset + N 条数据出来, 涉及到很多的磁盘 I/O
- 如何解决
- 子查询:
select * from (select id from test order by id limit 1000000, 10) q join test t on t.id = q.id - 使用上次查询最后的id作为起始点:
select * from test where id > 1000000 limit 10
- 子查询:
1.14. 海量数据如何排序?
- 考虑数据分布
- 学生成绩, 年龄等小范围数量有限的: 使用计数排序
- 随机数: 归并排序
- d位数, 每个数位有k个取值: 基数排序
- 被排序数在某个范围内, 且服从均匀分布: 桶排序
1.15. 如果一个服务端要求只能用快排，但恶意用户就是输入快排最坏情况的数据让其排序，导致服务端负载过大，如何解决
快速排序优化
- 用于比较值的选取, 可以取开始, 中间, 结尾三个数进行比较, 然后取中间值作为比较值
- 处理重复元素问题: 可以将数据分为三块, 比p小, 等于p, 比p大
1.16. 如何实现15分钟内订单未付款则自动取消订单的功能？
- 定时取消
- 查询取消
- 延时队列
1.17. 数据库两张表, 求在其中一个表的数据
select * from a where exists (select id from b where b.name = a.name)
1.18. 两个大文件找共同数据
用哈希取模法分到很多个小文件中, 然后进行对比找到相同数据
1.19. 海量文件找频率
哈希取模分文件, 对小文件进行统计, 最后统计最大频率或最小频率用堆来查
1.20. 大量数中找出不重复的数
- 使用 bitmap 找, 每个数分配 2bit , 01表示出现一次,
- 使用哈希取模分文件
1.21. 微信朋友圈有什么可以改进的地方, 存在什么数据模型
1.22. 前端发送请求没收到响应，怎么查？追问：没有日志呢？不是在开发环境下，不能打断点呢？
- 查看 HTTP 状态码
- 如果是有状态码, 则根据状态码找问题, 说明请求到服务器了
- 无状态码
- 让前端 ping 服务器域名
- 不能 ping 通: 网络问题
- 能 ping 通: 查看端口是否有问题
- 让前端 ping 服务器域名
1.23. 百万人访问我的博客, 如何处理? 数据库如何储存这些数据?
自己的小服务器, 最重要就是借助外部分担压力. 比如说使用 CDN 来分担静态资源压力. 对于数据储存来说, 注册用户使用 MySQL 来储存, 而统计访问量和访问人数使用 Redis 来储存, 其中统计访问量使用 incr 来计数, 访问人数使用 布隆过滤器 + 计数器 来统计.
1.24. 一天爬一千万条文章，怎么做设计？怎么并行协调？100 台服务器怎么尽可能负载均衡？
看这些文章的 url 结构, 一般来说按照机器数量, hash(url) % 100 分到不同的服务器上进行操作, 然后再不同的机器上根据进程数线程数来再次 hash 取模分配任务, 这是分的步骤. 爬取结果使用数据库或者文件的形式保存.
1.25. 设计一个抢红包系统，要注意哪些点
- 超卖
- 数据库锁超时问题
- 使用内存操作代替实时的 DB 事务操作, 在发送完后再异步写回到数据库中
- 事务操作串行化, 避免超卖
- 数据库锁超时问题
高并发
- 分流: 红包唯一标识, 分配到不同的服务器上处理
- DB 并发: 入库时使用队列操作
- DB 数据过多压力: 按时间分库分表
特征
- 分离抢和拆: 拆的业务太重了, 通过抢的过程可以过滤到大部分的请求.
- 算法: 在拆的时候再计算金额, 设置红包每次拆开的上下限, 每次拆的时候以红包id作为种子随机产生金额
- 问题
- 抢的操作是原子减操作 (使用版本号比较来实现, 降低阻塞)
- cache 和 db 挂了怎么办: 主备 + 对账
- 红包最后一个的操作会取所有剩余金额. 发完后会有异步对账操作
- 红包概率是均等的吗? 不是
- 发红包人的钱会冻结吗? 直接扣, 不冻结
- 采用实时计算出金额是出于什么考虑? 实时效率高, 预算需要占额外的储存空间.
- 实时性: 为什么有是有抢到了红包, 点开后却没有? 抢拆分离.
- 并发性处理: 红包如何计算被抢完? 缓存中记录红包个数, 原子操作进行个数递减, 到0表示被抢光
- 如何保证高写入? 数据分片, 水平扩展机器
- 一个红包一个队列? 没有队列, 一个红包一条数据, 数据上有一个计数器字段.
- 每领导一个红包就更新数据吗? 每抢到一个红包, 就 cas 更新剩余金额和红包个数
- 红包如何入库入账? 数据库会累加已经领取的个数和金额, 插入一条领取记录. 入账则是后台异步操作
1.26. 设计一个微博社交系统，怎么更高效，索引怎么设计、提高效率，查询扫描行数，缓存设计
1.27. 使用 PHP 手动实现一个生产者, 消费者模型
1.28. 设计一个视频上传的流程。表设计？文件上传服务器的原理？cdn？高qps怎么处理？上传和请求？缓存怎么加？
1.29. 有什么分布式 id 生成方法？各自的优缺点是什么？
- UUID
- 优点: 独立生成, 性能好
- 缺点: 生成的 ID 比较长, 而且无意义
- 雪花算法
- 使用时间戳+机器码+序列号来生成
- 优点: 有意义, 可排序
- 缺点: 需要不同机器时间是同步的
- Redis incr
- 优点: 不依赖数据库, 有序
- 缺点: 增加复杂度(引入Redis组件)
- 数据库自增
- 优点: 生成有序, 高可用, 实现简单
- 缺点: 有性能瓶颈, 需要单独部署数据库实例
1.30. 反羊毛怎么做？
- 参与活动需要登录, 手机号验证等
- 参加次数限制
- IP 限制
- 对用户在系统中的行为进行画像, 推测是机器人的概率
- 黑号设置
- 收货地址限制
1.31. 设计一个简单的智能家具系统，比如说加湿器和温湿度传感器关联，怎么设计？考虑哪些点？
有中心服务器设备的话, 建立中心服务, 每一个智能设备入网需要在中心服务注册, 并按照协议上报自身的状态数据, 然后还需要对中心服务发送过来的命令进行接收处理.
无中心服务的话, 采用设备互相发现策略, 每一个设备入网后, 将广播自己的地址信息及使用的沟通协议. 其它设备在收到广播信息后加入到自己的的已发现列表中, 并设置定时查询, 当设备离线后, 用列表中移除. 然后设备之间使用特定的沟通协议, 进行交互.
1.32. 设计一个登陆过程。md5 的原理？可逆么？
- 流程
- 前端传入账号密码信息
- 后端进行账号密码校验, 其中密码使用的 hash 加密储存在数据库中
- 成功后返回登录凭据, 后面调用接口都需要使用这个凭据
- MD5
- 不可逆
- 信息摘要
1.33. 12306网站设计架构
- 问题
- 超卖
- 少卖
- 架构
- 负载均衡
- 路由器: OSPF
- LVS
- Nginx
- 轮询
- 加权轮询
- ip hash 轮询
- 负载均衡
- 库存
- 单机本地扣库存, 消息队列异步下订单
- Redis 存总库存, 下单时需要本地和 Redis 库存均减成功才算成功. 每台服务器可以多放一些票, 以避免有服务器宕机导致票少卖
- 分库分表
- 缓存
- 查询队列, 下单队列
- 热备
- 内存数据库
- 读写分离
1.34. 一个电商系统，有id，商品名称字段，问你架构怎么设计，会涉及到模糊查询商品。双写过程会有分布事务问题，如何解决。如果采用最终一致性的思想，那么并发请求来了好几个发现数据不一致怎么办？
- 模糊查询商品
- 用搜索引擎来进行搜索
- MySQL 用 fulltext 索引
- 分布式事务问题
- 尽量避免分布式事务的产生
- 2PC, TCC
- 最终一致性思想, 数据不一致怎么办
- 使用幂等, 这种情况下式可以查询到事务未完成状态, 可以进行等待操作
1.35. 对于一个抢红包的需求，要求每个用户每分钟最多不能超过5次，问你怎么解决这个问题？
- 限流问题
- 滑动窗口
- 令牌桶
1.36. 订单号不能重复，你怎么设计生成订单号？
- 单机
- UUID
- 数据库自增
- 分布式
- 雪花算法
1.37. 分布式锁如何设计？
setnx, 设置过期时间- 删除锁时需要判断是不是自己的锁 (lua 脚本保证原子性)
1.38. 设计一个登录态系统。如何保证密码加密传输。如果你向服务器请求非对称加密的公钥时，请求被拦截篡改你怎么办？
- https 流程
- 中间人攻击: 收到服务器的公钥后, 向第三方证书机构进行证书有效性验证
- 请求被拦截篡改怎么办: 无ca机构验证证书有效性的情况下, 没有办法防范中间人攻击