经典问题

比如要求设计,

  1. Chat Messenger
  2. Twitter Feed
  3. Distributed Key-Value
  4. Global Object ID

典型流程

解答这样的问题, 可以这样一步步边确认边回答,

1. Data model/schema - 设计多种单体数据模型, 数据库关联关系

关键要考虑的数据特征是,

例子1 - 设计一个屏蔽词查询系统

这可以理解为就是一个 超大 Set.

例子2 - 设计一个电子银行系统

至少我们需要 User, Account, Transaction.

2. Traffic estimate - 系统中所有的数据流动

这个关系到我们的系统有多复杂. 比如设计一个淘宝系统因为其巨量的订单, 双 11 的爆发, 并发性, 稳定性的要求会撑爆我们的系统设计.

关键要考虑的是,

例子1 - 设计一个屏蔽词查询系统

呼应我们数据模型设计中提到的, 依次回答,

可以参考 https://www.educative.io/courses/grokking-the-system-design-interview, 包括了更详细的 do the math 的流程.

例子3 - 设计一个全国温度收集系统

这个是我在亚麻面试中遇到的, 也很有趣. 就是说我们在全国分布了上百万个温度 sensor, 现在需要设计一个系统收集这些数据并且实时展示出来 + 历史查询功能.

3. 设计关键 APIs

这步也可以放在第二步. 就非常和需求耦合了, 就是设计所有增删改查的 API.

例子1 - 设计一个屏蔽词查询系统

因为我们提到因为单个 request 太小, 可以支持多个 key 在一个 request 中,

例子3 - 设计一个全国温度收集系统

4. 考虑核心算法和业务性质主导的 Distribution

这个指的是, 当我们通过设计 API 把需求抽象到代码层面之后, 下面可以用数据结构和算法, 分布式设计来进一步细化我们的设计.

例子3 - 设计一个全国温度收集系统

其实对于这个例子, 刚刚已经在数据模型和数据流动中提到了关键的几点,

  1. 数据的汇总是 push model 方便 scalabile
  2. 使用分级汇报的方式. 二级节点把 sensor 节点的数据都汇总一遍, 把 1000 个数据点 reduce 成一个 pkg 再 push 给中心节点, 于是中心节点每秒只需要支持 1000 次 put() API 的调用
  3. 因为读实时是最常用的 API, 直接在中心节点放个实时的cache.
  4. cronjob 的计算下平均值把数据放在单独的数据库中, 避免重复计算.

顺便, 我们可以分离读写的两个 server, 因为他们的特征差距很大, 天然完全分离 - sensor -> put_server -> DB <- get_server <- user.

例子4 - Global Object ID

这是一个超经典的问题. 即给每个 Object 分配一个全局唯一的 ID. 比如淘宝中, 每个产品一个 ID, 每个订单一个 ID. 在 Twitter 中, 每条 Twitte 一个 ID. ShortenURL 每个 ID 一个 URL. 关键是,

  1. 显然在一个分布式系统中, 会有多个服务器同时分配 ID, 那么怎么保证多服务器分配不冲突的 ID?
  2. ID 可以有意义吗, 有意义的 ID 做主键好搜索好排序啊. 是不是要求时间上后面分配的 ID 一定要大于前面的?
  3. 不是绝对随机的 ID 分配会影响存取么? 如果 ID 和数据库节点绑定的话, 是不是会导致数据库节点被访问的频率不均匀? 如何设定 cache/batch?
  4. 分配之后呢, 在数据关联上, 有没有数据 affinity, 什么样的数据会同时被读取/搜索?
  5. 在分布上, 这些 ID 是都等读等写的吗? 比如有没有特别高频被读/写的?

这个问题的算法就很重要了.

  1. 通过 Object 的属性 hash 出来 ID. 比如 Shorten Original URL - base64(url). 或者订单 ID == userid_productid_timestamp. 不过也许我们并不想让 ID 是一个有逻辑的 ID, 可能会暴露数据本身, 有时我们并不想让 ID 可以被预测
  2. increasing sequence number. 这对于单个 server 是最简单的方法了.
  3. 随机数字. 这个当然很简单, 不过有一些问题,
    1. ID 长度必然有限制, 那么随机就会产生碰撞 (如果数据域太小的话,比如 8 位随机数字,其实 10000 个 ID 就很大概率出现碰撞了), 而对于关键系统, 比如订单, 任何碰撞都是受不了的. 
    2. 再比如我们要求时间上后分配的 ID 要比前面的 ID 大方便 query. 随机无法满足这样的要求.
  4. 提前准备好批量取用. 这个是很棒的主意. 我们抽象出一个 Key Generation Service (KGS).
    1. 直接生成大量 Key 放在数据库准备好. 就可以让一个进程完成, 于是没有冲突问题.
    2. 一开始每个 API server 有一个 Key pool, 启动时去数据库里申领几千几万个 unique ID. 创建新的订单时在自己的 pool 里面拿一个. 当用完了, 比如 30min, 再去拿一次. 这样其实每个 server 的休息时间也很短.
    3. cornor case. 即便 server 突然断电, 也不过是浪费了一些 ID, which 是可接受的.

5. 各种通用优化

基本上所有的系统都可以加上.

Load Balancing

For single point of failure, uniform, consistent, scale-up.

  1. 系统内部的 LB - 在 database 和 app 之间, 在 API server 之间, 在 worker 和 API server 之间, etc. 比如数据库是抽象出来的, 数据库可以有多个地址. API server 之间可以用 service-mesh 服务发现来让每个组件都是高可用的.
  2. 系统整体对用户间的 LB - 可以按网络模型安排多层 LB.
    1. 首先单个 API server 必然是有多个进程/线程的, 前面可以先有个 HTTP-Level LB 比如 Nginx 调度.
    2. 然后多个 server 间可以用 Nginx 或者 HAProxy 做 API gateway.
    3. 那么又要给多个 L4/7 的 API gateway 前面加上 L3 的 float IP 的 LB, 用 MACVLAN, IPVLAN 什么的.
    4. 再前面又可以有 DNS 层的 LB. DNS 直接 round-robin 或者高级的 Consul.io 提供的自带健康监测/有状态 LB 算法 (Least Connection/Response time/Traffic/Round robin/Hashing) 的 DNS.

Stand-by

不至于/不方便上 LB 的地方统统来个 stand-by server, 比如上面提到的 Key Generation Service 因为一致性的原因, 上 LB 太麻烦. 那就 Stand-by 一下吧.

Cache

只要感觉费劲就加一层 Cache. 除了数据 Cache, 还有比如数据库的连接池也是 Cache. 花时间的地方, 大都可以用空间复杂度换时间复杂度.

数据爆炸

随着系统用下去, 怎么保证在 10 年后系统数据超级多的时候还能顺畅运转?

Data partition 一下, 比如

分两类,

  1. 横向分, 分段分块
    • 比如屏蔽词检索. 按开头首字母各自有各自的 server.
    • 比如订单搜索. 按不同年份有不同的 server.
  2. 纵向分, 分层分级 - 一层指向一层, 指针, 指针组, 指向指针组的指针, 像 B+ Tree. 或者 Abstract metadata 数据表树形再分布.
    • 比如订单. 2020 年的一层, 每月的一层, 每日的一层, 每小时的… etc. 于是在 query 的时候, 一个请求会一步步转发到下一个 server. 当然也可以把这样的转发关系放在一个单独的 mapping service 里, 这个 server 的内存里就有这棵树, 可以根据时间戳直接返回应该去找哪个数据库节点. API server 直达那个节点, 避免层层转发.
    • 比如屏蔽词检索. T 开头的一个问一个 server, 再看是 TM 开头的, 再转发, 再转发负责 TMD 开头的 server, 一个 Tire 一样的服务器分配.

6. 收尾 Bonus - 业务性质导致可以牺牲的地方

  1. 实时性/一致性/可用性 的 trade off. 比如是不是可以给用户展示 5 分钟前的数据?
  2. 顶级功能/次级功能, 高感知属性/次感知属性. 用户常用的功能优化下?
  3. 精确. 比如在温度查询的例子里. 我们想要平均值可以需要计算一天 86400 个数据的平均, 或者, 只抽取每小时第一秒的数据计算平均值. 鉴于温度不会忽上忽下, 这样稍微牺牲了精度但是只要计算 24 个数据即可.
  4. 性能. 那些地方运算多?
  5. 稳定. LB 和 Stand-by 太贵的地方放弃下?
  6. 备份. 冷备, 热备, 多地备
  7. 可以异步做的高计算/高延迟步骤就异步做. 比如提前计算好每日的平均温度.
  8. 感觉冲突/互相影响就分开, 中间加个同步机制.
  9. 服务间 或 服务和 client 间的同步问题. pull model, push model, 或者混合.

Refs.

  1. https://leetcode.com/discuss/interview-question/system-design
  2. https://www.educative.io/courses/grokking-the-system-design-interview