设计

任务系统怎么保证任务完成后发奖一定成功

设计一个限流系统怎么做? 令牌桶

漏桶算法

把请求比作是水, 水来了都先放进桶里, 并以恒定速度出水(处理请求), 当水流量过大会导致桶溢出, 即拒绝服务. 请求的最大出力速度也就是水从漏桶流出的速度.

基于漏桶(桶+恒定处理速度), 可以起到对请求整流效果. 漏桶算法可基于线程池来实现, 线程池用固定容量的阻塞队列+固定个数的处理线程来实现: 最简单且最常见的漏桶实现就是基于 SynchronousQueue 的线程池, 其相当于一个空桶+固定处理线程.

注意:原生的漏桶算法以恒定速度出水(处理请求), 但是实际场景中请求的处理耗时可能不相等, 为了实现恒定速率, 一般都是限定同时处理请求的最大线程数.

令牌桶算法

滑动时间窗口算法就是根据当前时间获取对应的时间窗口, 时间窗口保存有流量相关的统计值, 根据该统计值判断是否触发流控.

滑动时间窗口算法 (rolling window)

在计数器的基础上细分更多格子, 比如说 1分钟拆分成10个格子, 随着时间的前进10格像窗口一样前行, 每格都有自己的计数器, 窗口总计数是当前时间的流量.

Redis 实现 (计数器)

Redis 实现限流可以使用 lua 脚本原子增加统计数据来实现, 设置过期时间1秒即1秒的限流.

现有一个随机数可以生产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;
}

(2) 设计秒杀系统, 考虑正确性, 以及服务器不挂机如何设计, 怎么解决大并发

如何设计服务端日志, 需要记录哪些字段?

以微博为例，有1个亿的用户，同时用户之间有关注和粉丝，用户的关注和取关操作比较频繁，如何设计架构和API接口

设计一个定时任务管理器

压力测试

一个只能负载1000qps 怎么让它达到 10000 qps

找到瓶颈针对性优化

短连接 (数据库 + 重定向)

设计一个死锁

几千万数据的表扩充新的字段如何处理?

几千万数据的表如何分页?

海量数据如何排序?

如果一个服务端要求只能用快排，但恶意用户就是输入快排最坏情况的数据让其排序，导致服务端负载过大，如何解决

快速排序优化

  1. 用于比较值的选取, 可以取开始, 中间, 结尾三个数进行比较, 然后取中间值作为比较值
  2. 处理重复元素问题: 可以将数据分为三块, 比p小, 等于p, 比p大

如何实现15分钟内订单未付款则自动取消订单的功能？

  1. 定时取消
  2. 查询取消
  3. 延时队列

数据库两张表, 求在其中一个表的数据

select * from a where exists (select id from b where b.name = a.name)

两个大文件找共同数据

用哈希取模法分到很多个小文件中, 然后进行对比找到相同数据

海量文件找频率

哈希取模分文件, 对小文件进行统计, 最后统计最大频率或最小频率用堆来查

大量数中找出不重复的数

  1. 使用 bitmap 找, 每个数分配 2bit , 01表示出现一次,
  2. 使用哈希取模分文件

微信朋友圈有什么可以改进的地方, 存在什么数据模型

前端发送请求没收到响应，怎么查？追问：没有日志呢？不是在开发环境下，不能打断点呢？

  1. 查看 HTTP 状态码
    1. 如果是有状态码, 则根据状态码找问题, 说明请求到服务器了
    2. 无状态码
      • 让前端 ping 服务器域名
        • 不能 ping 通: 网络问题
        • 能 ping 通: 查看端口是否有问题

百万人访问我的博客, 如何处理? 数据库如何储存这些数据?

自己的小服务器, 最重要就是借助外部分担压力. 比如说使用 CDN 来分担静态资源压力. 对于数据储存来说, 注册用户使用 MySQL 来储存, 而统计访问量和访问人数使用 Redis 来储存, 其中统计访问量使用 incr 来计数, 访问人数使用 布隆过滤器 + 计数器 来统计.

一天爬一千万条文章，怎么做设计？怎么并行协调？100 台服务器怎么尽可能负载均衡？

看这些文章的 url 结构, 一般来说按照机器数量, hash(url) % 100 分到不同的服务器上进行操作, 然后再不同的机器上根据进程数线程数来再次 hash 取模分配任务, 这是分的步骤. 爬取结果使用数据库或者文件的形式保存.

设计一个抢红包系统，要注意哪些点

设计一个微博社交系统，怎么更高效，索引怎么设计、提高效率，查询扫描行数，缓存设计

使用 PHP 手动实现一个生产者, 消费者模型

设计一个视频上传的流程。表设计？文件上传服务器的原理？cdn？高qps怎么处理？上传和请求？缓存怎么加？

有什么分布式 id 生成方法？各自的优缺点是什么？

反羊毛怎么做？

设计一个简单的智能家具系统，比如说加湿器和温湿度传感器关联，怎么设计？考虑哪些点？

有中心服务器设备的话, 建立中心服务, 每一个智能设备入网需要在中心服务注册, 并按照协议上报自身的状态数据, 然后还需要对中心服务发送过来的命令进行接收处理.

无中心服务的话, 采用设备互相发现策略, 每一个设备入网后, 将广播自己的地址信息及使用的沟通协议. 其它设备在收到广播信息后加入到自己的的已发现列表中, 并设置定时查询, 当设备离线后, 用列表中移除. 然后设备之间使用特定的沟通协议, 进行交互.

设计一个登陆过程。md5 的原理？可逆么？

12306网站设计架构

一个电商系统，有id，商品名称字段，问你架构怎么设计，会涉及到模糊查询商品。双写过程会有分布事务问题，如何解决。如果采用最终一致性的思想，那么并发请求来了好几个发现数据不一致怎么办？

对于一个抢红包的需求，要求每个用户每分钟最多不能超过5次，问你怎么解决这个问题？

订单号不能重复，你怎么设计生成订单号？

分布式锁如何设计？

设计一个登录态系统。如何保证密码加密传输。如果你向服务器请求非对称加密的公钥时，请求被拦截篡改你怎么办？

在面对未知的流量暴增，可以预先怎么处理

如何限流，限流算法，对于ddos攻击怎么处理