Blogs

0%

常见的架构设计面试题

发表于 更新于 分类于
本文字数： 5.8k 阅读时长 ≈ 10 分钟

整理了一些常见的架构设计面试题，主要记录关键点，具体细节就不详细叙述了，案例慢慢补充。目前想起以下问题：

  • 秒杀系统
  • 短链接生成
  • 高并发的红包系统
  • 分布式ID生成
  • 分布式限流
  • 分布式定时任务
  • 新浪微博怎么推送微博
  • 大文件有限内存排序

秒杀系统

秒杀系统基本面试被问烂了，网上资料也很多，基本整理了内容如下：

设计难点：并发量大，应用、数据库都承受不了。另外难控制超卖。

设计要点：

  • 将请求尽量拦截在系统上游，html尽量静态化，部署到cdn上面。按钮及时设置为不可用，禁止用户重复提交请求。
  • 设置页面缓存，针对同一个页面和uid一段时间内返回缓存页面。
  • 数据用缓存抗，不直接落到数据库。
  • 读数据的时候不做强一致性教研，写数据的时候再做。
  • 在每台物理机上也缓存商品信息等等变动不大的相关的数据
    • 像商品中的标题和描述这些本身不变的会在秒杀开始之前全量推送到秒杀机器上并一直缓存直到秒杀结束。
    • 像库存这种动态数据会采用被动失效的方式缓存一定时间（一般是数秒），失效后再去Tair缓存拉取最新的数据。
  • 如果允许的话，用异步的模式，等缓存都落库之后再返回结果。
  • 如果允许的话，增加答题教研等验证措施。

其他业务和技术保障措施：

  • 业务隔离。把秒杀做成一种营销活动，卖家要参加秒杀这种营销活动需要单独报名，从技术上来说，卖家报名后对我们来说就是已知热点，当真正开始时我们可以提前做好预热。

  • 系统隔离。系统隔离更多是运行时的隔离，可以通过分组部署的方式和另外 99% 分开。秒杀还申请了单独的域名，目的也是让请求落到不同的集群中。

  • 数据隔离。秒杀所调用的数据大部分都是热数据，比如会启用单独 cache 集群或 MySQL 数据库来放热点数据，目前也是不想0.01%的数据影响另外99.99%。

另外需要复习缓存穿透、雪崩等等问题，主要的流量都落在了缓存数据库上，需要针对缓存数据库的高可用作保障。

短链接生成

这个应该是比较公认的方案了：

  1. 分布式ID生成器产生ID
  2. ID转62进制字符串
  3. 记录数据库，根据业务要求确定过期时间，可以保留部分永久链接

主要难点在于分布式ID生成。鉴于短链一般没有严格递增的需求，可以使用预先分发一个号段，然后生成的方式。

看了下新浪微博的短链接，8位，理论上可以保存超过200万亿对关系，具体怎么存储的还有待研究。

红包系统

红包系统其实很像秒杀系统，只不过同一个秒杀的总量不大，但是全局的并发量非常大，比如春晚可能几百万人同时抢红包。

主要技术难点也类似，主要在数据库，减库存的时候会抢锁。另外由于业务需求不同，没办法异步，也不能超卖，事务更加严格。

不能采用的方式：

  • 乐观锁：手慢会失败，DB 面临更大压力，所以不能采用。
  • 直接用缓存顶，涉及到钱，一旦缓存挂掉就完了。

建议的方式：

  • 接入层垂直切分，根据红包ID，发红包、抢红包、拆红包、查详情详情等等都在同一台机器上处理，互不影响，分而治之。
  • 请求进行排队，到数据库的时候是串行的，就不涉及抢锁的问题了。
  • 为了防止队列太长过载导致队列被降级，直接打到数据库上，所以数据库前面再加上一个缓存，用CAS自增控制并发，太高的并发直接返回失败。
  • 红包冷热数据分离，按时间分表。

分布式ID

分布式ID生成大概也算老生常谈的问题了，主要关键在于是否需要严格递增，严格递增的话效率必然大降。

不需要递增的话比较简单:

  • 一种方式是预先分片，比如十台机器，每台先分一千个ID，一号机从0开始，二号从1000开始等等。缺点是大致上可以被人看出来业务量。

  • 另一种方式是类似雪花算法，每个机器有个id，然后基于时间算一个id，再加上一个递增id。比如如下美团的方案。缺点是机器的时间戳不能回拨，回拨的话会出现问题。

    image

如果要求严格递增，我没找到现成的很好的方案，大概只能单机生成，不能分布式了，然后都去单机上取号。效率的话，类似Redis的数据库大概能到每秒十几二十几万的速度。

分布式限流

常见的限流方法：

  • 固定窗口计数器：按照时间段划分窗口，有一次请求就+1，最为简单的算法，但这个算法有时会让通过请求量允许为限制的两倍。
  • 滑动窗口计数器：通过将窗口再细分，并且按照时间“滑动”来解决突破限制的问题，但是时间区间的精度越高，算法所需的空间容量就越大。
  • 漏桶：请求类似水滴，先放到桶里，服务的提供方则按照固定的速率从桶里面取出请求并执行。缺陷也很明显，当短时间内有大量的突发请求时，即便此时服务器没有任何负载，每个请求也都得在队列中等待一段时间才能被响应。
  • 令牌桶：往桶里面发放令牌，每个请求过来之后拿走一个令牌，然后只处理有令牌的请求。令牌桶满了则多余的令牌会直接丢弃。令牌桶算法既能够将所有的请求平均分布到时间区间内，又能接受服务器能够承受范围内的突发请求，因此是目前使用较为广泛的一种限流算法。

Google 的开源项目 guava 提供了 RateLimiter 类，实现了单点的令牌桶限流。

分布式环境下，可以考虑用 Redis+Lua 脚本实现令牌桶。

如果请求量太大了，Redis 也撑不住怎么办？我觉得可以类似于分布式 ID 的处理方式，Redis 前面在增加预处理，比如每台及其预先申请一部分令牌，只有令牌用完之后才去 Redis。如果还是太大，是否可以垂直切分？按照流量的来源，比如地理位置、IP 之类的再拆开。

分布式定时任务

任务轮询或任务轮询+抢占排队方案

  • 每个服务器首次启动时加入队列；
  • 每次任务运行首先判断自己是否是当前可运行任务，如果是便运行；
  • 如果不是当前运行的任务，检查自己是否在队列中，如果在，便退出，如果不在队列中，进入队列。

微博推送

主要难点：关系复杂，数据量大。一个人可以关注非常多的用户，一个大 V 也有可能有几千万的粉丝。

先介绍最基本的方案：

  1. 推模式：推模式就是，用户A关注了用户 B，用户 B 每发送一个动态，后台遍历用户B的粉丝，往他们粉丝的 feed 里面推送一条动态。
  2. 拉模式：推模式相反，拉模式则是，用户每次刷新 feed 第一页，都去遍历关注的人，把最新的动态拉取回来。

一般采用推拉结合的方式，用户发送状态之后，先推送给粉丝里面在线的用户，然后不在线的那部分等到上线的时候再来拉取。

另外冷热数据分离，用户关系在缓存里面可以设置一个过期时间，比如七天。七天没上线的可能就很少用这个 APP。

大文件排序

对于远高于内存的文件排序。

外归并排序：

  • 对文件分割，然后分别排序
  • 排好序的文件依次读取一个缓冲区的大小，然后进行排序，输出到输出缓冲区，然后保存到结果文件。

如果是数字，可以用位图排序，但是要求比较苛刻：

  • 数字不重复
  • 知道最大值
  • 相对密集，因为没出现的数字也会占用空间

比较适合电话号之类的。

总结和方法论

架构设计题目远不止这些，我觉得主要从以下几个方面准备：

  • 先了解常用算法，针对解决各种问题能用哪些算法，比如大文件排序用外排序，大量数据中的命中判断用位图/布隆过滤器等等。

  • 注意扩展性、多考虑极端情况，多问自己几个为什么。比如说起单机的限流算法想想分布式的怎么做。

  • 实在不知道怎么弄的叙述自己的思考过程，着重展示自己考虑周全、思维缜密。

    比如之前一个同事面阿里被问整个机房网络挂了/断电了之类的极端问题，相信很多人不可能真的遇到这种情况，而且可用性一般也到不了这个级别。如果是我的话，我会着重考虑数据一致性、数据恢复、脏数据处理之类的问题，是否有其他机房提供服务，如果有的话涉及到网络分区，是不是可以引申谈谈 zab、raft 算法，另外原本两个或者三个机房提供服务，现在瞬间少了一个，其他机房的负载瞬间上升，怎么做削峰、降级，这就有回到我们会的问题上了。另外等到网络恢复了，怎么恢复服务？之前处理到一半的数据怎么处理？这些引申开来都有太多可以聊。

另外有其他人总结的经验如下：

如何答好面试中的系统设计题？@董飞

  • Cache：缓存，万金油，哪里不行优先考虑

  • Queue：消息队列，常见使用Linkedin的kafka

  • Asynchronized：批处理＋异步，减少系统IO瓶颈

  • Load Balance: 负载均衡，可以使用一致性hash技术做到尽量少的数据迁移

  • Parallelization：并行计算，比如MapReduce

  • Replication：提高可靠性，如HDFS，基于位置感知的多块拷贝

  • Partition：数据库sharding，通过hash取摸

如何答好面试中的系统设计题？@罗辑

交流沟通和理解能力 - 跟面试官充分交流理解所设计系统的目标，方便做设计中的tradeoff，在厂里干过的就知道日常工作中这个非常重要

设计和架构能力 - 很多我见过的面试者都只注重在这块而忽略了其他，很可惜

扩展性，容错性，延迟要求 - 跟Opeartion相关的要求，如今Dev和Ops不分家，希望面试者了解系统今后能如何扩展，易于maintain。

资源需求 - 对于我们所要求的QPS和latency，需要多少台机器，其中CPU, 内存，硬盘等资源都是如何配置

如何解决系统设计题

注意陷阱⚠️

千万不要张口就来 。我们上面的分析已经表明，遇到问题，我们必须先明确问题，然后才能给出有效的解决方案，系统设计题也是如此。 而往往面试官会在这里面挖坑，就是，给出一个条件相当模糊的系统设计题。例如：请设计一个短链接系统、请设计一个压测工具。

如果我们张口就来，那么就中了面试官的套路。在工作中也是如此，如果你碰到了一个产品经理，产品经理还没有想清楚，就叫你写代码， 那么后面一定是反复修改需求，作为工程师的你一定是痛不欲生。因此，我们需要做的第一步就是 明确问题，不要张口就来。

千万不要自己一个人闷头想，记得一边想一边把你的思路说出来 由于别人是不知道你咋想什么的，如果你一个人皱着眉头思考，面试官 也很着急，他也不知道你是想不出还是怎么的。所以，一边把你的思路描述出来一边想，这是最好的方式。

明确问题

拿到了问题之后，我们只有一个大概的方向，即我们要做一个什么。但是并不清楚具体条件，而不同的的业务场景所需要的架构也是不一样的。 例如，每天只有10000次访问的短链接系统和每秒钟有10000次访问的短链接系统在技术要求上是不一样的。

因此，第一个我们需要问面试官的问题：

  • 这个系统一天的请求量是多少？面试官回答，一天2万。

虽然现在我们有了更加明确的条件，但是还是不够具体，我们需要进一步确定：

  • 这个短链接系统的峰值是多少？面试官回答：峰值1万/s。

此刻，我们得到的条件已经清晰很多，我们知道，QPS位10k，相对来说，已经算是高并发了，但是我们还需要继续确定。

  • 这个短链系统的短链接是永久保存的吗？面试官回答：是。
  • 生成的锻炼字符长度有要求吗？越短越好。
  • 录入的长链接大概是多少个字符呢？有长有短。
  • 那么，平均是多少个字符呢？假设是50个字节。

通过这些我们可以了解到，我们需要对短链接进行持久化。而到目前为止，我们可以得出一些计算：

  • 峰值QPS为10k
  • 一天的请求量为20k，因此，我们的系统需要为并发考虑，所以我们很可能需要用到缓存
  • 一天为20k，那么一年就是 20k * 365 = 7300k
  • 如果短链接生成的链接长度为 6个字符，那么一年下来，需要的磁盘大小至少是：7300k * (6 + 50) / 1024 = 399.21875M

然后我们需要了解一些常见的性能指标，这是我们需要记在脑子里的：

这些数据是不准确的，因为：

  • 和怎么用关系很大
  • 和硬件配置关系很大

但是我们心里还是要有个大概印象。

现在我们就可以知道了，这个短链系统，并发是10k/s，但是我们还漏掉了一个问题，就是没有明确是读的QPS是10k还是写，还是读+写。 这个时候我们仍然可以向面试官提问。但是，不论读还是写，QPS为10k，只要硬件配置过得去，不加缓存也ok。但是通常来说，我们还是会 选择加上，原因很简单：此刻都有QPS都有10k，保不准半年之后更高了。

到此为止，我们已经知晓了解决系统设计题的一个大概思路流程，但是这远远不够，因为系统设计题对知识的广度要求也很高，因此这里 我还会提供一些常见的知识，希望能够对大家有所帮助。

常见知识

参考资料

这一次，彻底弄懂“秒杀系统”

淘宝大秒杀系统设计详解

百亿级微信红包的高并发资金交易系统设计方案

全面解密QQ红包技术方案：架构、技术实现、移动端优化、创新玩法等

Leaf——美团点评分布式ID生成系统

微信序列号生成器架构设计及演变

分布式定时任务（一）