请谈谈限流器的设计
互联网秒杀场景下，很多接口的峰值流量非常非常陡峭，必须做好限流不然会把内部系统打挂。请设计一个分布式限流器，能实现这个功能。
- 限流器能work，精确度达到 99% 以上
- 限流阈值大小可设置，大的达到1000w级QPS，小的小到10QPS级别
- 通用的限流器，不局限于某一业务领域
答案：
- 利用redis的原子自增和过期淘汰策略
- 限流器的计数存放在redis中，用redis的过期淘汰策略实现限流器的计数的定期更新
- 例如针对 接口A 限流 10000 QPS。redis的key为：“接口A”，value为计数值
- 每次接口调用Redis用INC原子自增命令，自增1，并设置过期时间为1s
- 初次调用时，因为redis中该key没有，就直接设置为1，并设置过期时间为1s
- 在这一秒以内的后续调用，每次都自增1 - 客户端拿到自增后的值如果没有超过限制10000，就放行 - 如果超过 10000 限制，就不放行，说明超限了
- 细节实现：为避免超限后无谓的redis调用，第一次发现超限时可以记录该值的TTL时间，例如只过去100ms就有1w个请求过来，剩下的900ms就不用请求redis而是直接返回超限即可。不然这种情况会给redis带去额外无谓的流量，例如前面的例子，不做这个细节逻辑的话，redis的请求量是 10w QPS。
- 精度可调节。假如限流阈值很大，比如100w，可以把INC自增步进/步长调整大一些，例如100，那么redis的QPS直接降低100倍，为1w QPS。
- 按时间窗口限制访问次数，保存一个访问队列，定期删除过期的访问，维护一个当前时间窗口内的总访问次数。
- Token Bucket思想，控制Bucket的总容量和留入令牌速率，考虑到burst rate问题。
- 基于方案3还能考虑到平台话的动态配置，熔断策略等
扩展： 此题目给的解法相当于限流器中的固定窗口，固定窗口应对流量尖刺不理想，可以引申一步讨论 滑动窗口、令牌桶、漏桶 的实现，另外有一个现成的redis module使用漏桶实现了限流器
请设计短网址系统
- 分为两个接口
- 从一个长网址生成一个短网址。需要考虑：同一个长网址，多次创建的短网址是否相同
- 用户访问短网址时，需要能跳回到原始的长网址
- 需要考虑跨机房部署问题
- 加分项：考虑跨海域全球部署问题
- 加分项：考虑统计某个域名下的URL/host访问uv和pv
答案：
- 一开始需要能考虑系统承载容量，例如：
- 每天100亿访问量
- 每天生成1000w条短网址记录
- 然后考虑短网址的生成算法，方案有很多种
- 最简单实现：自增id实现，这个不可逆，同一个长网址会生成多个短网址
- hash+序号冲突
- 使用kv存储双向对应关系，可逆，但存储用量比较大
- 302跳转问题，附带可以讨论网址访问量计数问题
- 加分项1：需要考虑跨机房部署问题
- 加分项2：考虑跨海域全球部署问题
- 加分项3：能给出合理的统计需求，例如用hadoop做MR
计数系统设计
头条里有各种计数需求，希望能够有一个统一的计数服务来满足该需求，主要功能要求根据业务需求查询指定的文章的计数统计（播放数，阅读数，评论数等），要求：支持实时更新各种计数，支持高并发查询，需要给出系统存储设计方案，对外输出接口设计；
答案:
- 方案一：直接使用数据库+cache的方案，方案简单有效，数据量大之后采用分库方案，扩展性有限，但开发和运维成本低，性能方面通过cache优化，存在热点数据（可能导致cache经常被清理）；
- 方案二：采用redis作为kv存储，查询效率足够高，但需要考虑资源使用问题，假设有10亿的文章，帖子和评论，如何保证以更低的成本满足该需求；主要问题需要较多资源，成本较高，如何设计更好数据结构；（3+）
- 方案三：可以自己开发counter模块，需要考虑kv存储方案，value的设计，保证使用更少内存；还需要考虑的点：容灾备份机制；数据扩展问题；（3.5）
- 方案四：可能业务方经常新增计数需求，需要考虑counter服务的列扩展性，故设计的数据结构需要考虑列扩展问题；（3.5）
- 其他：业务写入QPS可能比较高，考虑写入压力问题，数据写入去重问题，即同一个用户转发之类操作需要幂等性（一定程度保证即可）
请尝试实现直播间消息服务设计
背景: 消息服务是直播产品中一个非常核心的服务。直播间内的聊天、弹幕、礼物等消息，都是通过消息服务发送。
问题:
- 设计一个消息服务，支持直播间内的用户进行聊天、发弹幕等操作。
- 衡量一个消息服务的核心指标有哪些？
- 基于候选者的方案，如何监控和优化这些核心指标？
- （深入）拉模型的分布式方案
方案设计
主流设计主要有两种：推模型和拉模型。（任何一种都是合适的设计） 推模型简述： 基于长连接，直播间内的观众发的消息，异步通过长连接发送给房间内的其他观众。 深入的问题（言之有理即可）：
- 长连接的架构（协议、鉴权、扩容、重连、到达率等）
- 消息放大问题如何解决（比如一个有1万人的房间，任何一个人发的消息，都会产生1万个消息，相当于放大了1万倍） 消息聚合、消息多级推送（类似CDN的方式）
- 直播间用户列表怎么存储和优化 推送消息时，需要房间内所有用户消息，对于观众比较多的房间，需要考虑数据分片、本地缓存等手段进行优化。
拉模型简述： 拉模型类型类似于一个消息队列的模型。每个房间会有一个消息列表，直播间内用户发的消息会放在相应的消息列表中。直播间内的观众通过前端轮询拉消息接口， 把消息拉到客户端展示。 深入的问题（言之有理即可）：
- 房间的消息如何存储（由于消息有时效性，所以只需要存储最近一段时间的数据）
- 轮询方式如何优化
- 拉接口如何优化（local cache等）
核心指标 消息每秒吞吐量、消息到达率、消息延时（像稳定性这种，属于通用的基本指标）。
核心的优化方式（提供一些方式，其它的只要合理即可）： 监控方式：
- 吞吐量（类似于qps，打metrics等都可以）
- 到达率：对于推模型，基本等价于长连接的到达率监控；对于拉模型，性价比较高的是只监控主播的（因为只有主播是全程在直播间的）
- 延时：需要关注手机和服务端的时间不一致的问题
优化：
- 吞吐量：批量发送、多级推送等
- 到达率：一般推模型需要重点关注，主要是对于长连接的到达率优化，包含死连接检测等。
- 延时：一般拉模型需要重点关注，对于每次都拉到消息的房间，减少轮询间隔和长连接拉模式等。
拉模型的分布式方案： 类似于一个分布式存储系统，解决水平和垂直扩展的问题。
秒杀系统设计
“米粉节”3000万人抢购，峰值QPS100万，请设计抢购系统的技术架构，保证可靠性并且不能超卖。
设计要点：
- 可以支撑QPS 100万，能分析系统的瓶颈
- 如何尽快把商品卖完，但不能超卖
- 考察系统扩展性、容灾能力
设计思路：限流+策略+反作弊，一般情况下候选人想不到完善的设计，我们主要看其设计能否满足前面的需求。 参考：http://www.tuicool.com/articles/e2YVRvA
- 可以满足业务需求，抗住压力，不会超卖 3分
- 能考虑到到各种情况下的灾备方案，系统易于对商品种类，抢购规模进行扩展，3.5分
