系统设计学习笔记

通用模板

系统设计的面试题是一个开放式的对话,大体可以分成四个步骤:

第一步:明确需求

  • 需求是无止境的,需要明确一个范畴,专注讨论范畴内的需求用例
  • 目标用户是谁,用户规模大概多大
  • 有哪些功能,核心功能的输入输出是什么
  • 有哪些边界情况需要注意
  • 预期的数据量和处理速度

第二步:设计架构

  • 做一个高层次设计,画出核心组件的架构
  • 用连线代表核心组件之间的交互

第三步:细化实现

  • 具体到每个系统组件,提供具体的解决方案
  • 演示所有功能的交互流程和解决方案

第四步:扩展设计

  • 不用直接得出最终设计,通过 benchmark/load/profile 迭代分析瓶颈
  • 可参考方案:DNS、CDN、负载均衡、水平扩展、反向代理、应用层、缓存、主从复制
  • 论述可能的解决办法和代价,每件事情需要权衡利弊做出取舍
  • 重要的是讨论在初始设计中可能遇到的瓶颈,以及如何解决每个瓶颈

一些常见的优化方案:

  • DNS:根据地理位置分流
  • CDN:内容分发加速,客户端访问速度更快
  • Load Balancer:反向代理层做负载均衡,缓解单个 web server 的访问压力
  • Memory Cache:高频数据放在内存缓存中,缓解数据库查询压力
  • SQL Write Master-Slave & Read Replicas:主从分离提高数据安全性和可用性,slave 上做查询可以缓解生产服务器访问压力过大的问题。
  • SQL Analytics:分析 SQL 的执行耗时,优化应用层的 SQL 语句性能
  • Graph Service:解决复杂的关系网络,比如社交系统的用户关注
  • Object Store:通过 S3 之类的云服务存储图片等多媒体对象
  • Queue:通过队列解决异步任务

案例一:粘贴板分享平台

第一步:明确需求

我们将问题的范畴限定在如下用例:

  • 用户:输入文本,保存后得到一个随机链接
    • 默认不会过期
    • 设置过期时间
  • 用户:输入一个链接,可以查看分享的内容
  • 服务:用户行为统计与分析,可以使用外部服务(Google Analytics)
  • 服务:自动删除过期的内容
  • 服务:高可用,冗余+自动故障转移

范畴之外的用例:

  • 用户:可以注册、登录、查看历史记录
  • 用户:可以设置可见性、过期时间

状态假设:

  • 访问流量不是均匀分布的
  • 打开一个短链接应该是很快的
  • pastes 只能是文本
  • 页面访问分析数据可以不用实时
  • 一千万的用户量,每个月一千万的 paste 写入量,一亿的 paste 读取量,读写比例在 10:1

估算使用情况:

  • 每个 paste 的大小,每条数据大约 2kb
  • 每个月新的 paste 内容在 20GB
  • 平均 4 paste/s 的写入频率
  • 平均 40 paste/s 的读取频率

第二步:设计架构

第三步:细化实现

  • 用一个关系型数据库作为哈希表,用来把生成的 url 映射到一个包含 paste 文件的文件服务器和路径上
  • 为了避免托管一个文件服务器,我们可以用一个托管的对象存储,比如 Amazon 的 S3

用例:输入文本,保存后得到一个随机链接

  • Client 发送一个创建 paste 的请求到 Reverse Proxy
  • Reverse Proxy 转发请求给 Write API Server
  • Write API 执行如下操作:
    • 生成一个唯一的 url
      • MD5 做哈希,Base62 做编码
      • 检查这个 url 在 SQL 数据库 里面是否是唯一的
      • 如果这个 url 不是唯一的,生成另外一个 url
      • 如果我们支持自定义 url,我们可以使用用户提供的 url(也需要检查是否重复)
    • 把生成的 url 存储到 SQL 数据库 的 pastes 表里面
    • 存储 paste 的内容数据到 对象存储 里面
    • 返回生成的 url

用例:输入一个链接,可以查看分享的内容

  • Client 发送一个获取 paste 的请求到 Reverse Proxy
    Reverse Proxy转发请求给 Read API Server
  • Read API 执行如下操作:
    • 在 SQL 数据库 检查这个生成的 url
    • 如果这个 url 在 SQL 数据库 里面,则从 对象存储 获取这个 paste 的内容
    • 否则,返回一个错误页面给用户

用例:用户行为统计与分析
非实时分析的功能可以通过 MapReduce 之类的服务来计算点击率之类的数据

第四步:扩展设计

案例二:设计 Twitter 时间轴线和搜索

第一步:明确需求

我们将问题的范畴限定在如下用例:

  • 用户:发布推文
    • 服务:推送通知给关注的人
  • 用户:浏览用户的时间线
  • 用户:浏览自己主页的时间线
  • 用户:搜索关键词
  • 服务:高可用

范畴之外的用例:

  • 服务:推送推文到热门数据流
  • 服务:一些定制化的可见性功能
  • 服务:数据分析

状态假设:

  • 流量不是均匀分布的
  • 发布推文、浏览时间线的速度要快
  • 1 亿的活跃用户
  • 每天 5 亿的推文
  • 每个月 2500 亿的浏览量
  • 每个月 100 亿的搜索量

估算使用情况:

  • 一条推文大约 10kb
  • 每个月大约是 150TB 的数据量
  • 每秒 10 万次读取请求
  • 每秒 6000 个推文
  • 每秒 4000 次搜索

第二步:设计架构

第三步:细化实现

用例:用户发表推文

  • Client 发送请求到 Reverse Proxy
  • Reverse Proxy 分发请求到 Write API Server
  • Write API 把数据写进用户的时间线,存储在 SQL DB 里
  • Write API 通知 Fan Out Service,进行如下操作:
    • 查询 User Graph Service 服务,在 Memory Cache 中找到该用户的关注者
    • 将该信息通过 Memery Cache 存储在关注者的主页时间线里
    • 将该信息存储在 Search Index Service,方便快速搜索
    • 媒体资源存储在 Object Store
    • 用 Notification Service 推送通知,可以用 Queue 来异步发送通知

用例:用户浏览自己主页的时间线

  • 客户端发送浏览请求到 Reverse Proxy
  • Reverse Proxy 分发请求到 Read API Server
  • Read API 联系 Timeline Service ,进行如下操作:
    • 从 Memory Cache 中获取时间线数据,包括 ID 和 User ID
    • 从 Post Info Server 获取这些 ID 的信息
    • 从 User Info Server 获取这些用户的信息

用例:用户浏览其他用户的时间线

  • 客户端发送浏览请求到 Reverse Proxy
  • Reverse Proxy 分发请求到 Read API Server
  • Read API 从 SQL DB 中获取用户的时间线数据

用例:用户搜索某个关键词

  • 客户端发送浏览请求到 Reverse Proxy
  • Reverse Proxy 分发请求到 Search API Server
  • Search API 联系 Search Service,进行如下操作:
    • 格式化输入,明确搜索内容,包括:移除符号、拆分词组、修正笔误、规范化大小写
    • 查询 Search Cluster,对查询结果做进一步聚合排序处理

第四步:扩展设计

一些额外优化的点:

  • Memory Cache 中每个时间线只保存几百条数据
  • Memory Cache 只存储活跃用户的时间线
  • Tweet Info 和 User Info 都只缓存储活跃用户

案例三:设计一个网页爬虫

案例四:设计一个理财网站

案例五:设计一个社交网站

案例六:设计一个键值存储的搜索引擎

案例七:通过分类特性设计电商平台的销售排名

案例八:设计一个百万用户级别的系统


附录一:如何实现高可用

方法论上,高可用是通过冗余+自动故障转移来实现的。
整个互联网分层系统架构的高可用,又是通过每一层的冗余+自动故障转移来综合实现的,具体的:

(1)【客户端层】到【反向代理层】的高可用,是通过反向代理层的冗余实现的,常见实践是keepalived + virtual IP自动故障转移
(2)【反向代理层】到【站点层】的高可用,是通过站点层的冗余实现的,常见实践是 nginx 与 web-server 之间的存活性探测与自动故障转移
(3)【站点层】到【服务层】的高可用,是通过服务层的冗余实现的,常见实践是通过 service-connection-pool 来保证自动故障转移
(4)【服务层】到【缓存层】的高可用,是通过缓存数据的冗余实现的,常见实践是缓存客户端双读双写,或者利用缓存集群的主从数据同步与 sentinel 保活与自动故障转移;更多的业务场景,对缓存没有高可用要求,可以使用缓存服务化来对调用方屏蔽底层复杂性
(5)【服务层】到【数据库读】的高可用,是通过读库的冗余实现的,常见实践是通过 db-connection-pool 来保证自动故障转移
(6)【服务层】到【数据库写】的高可用,是通过写库的冗余实现的,常见实践是 keepalived + virtual IP 自动故障转移

附录二:常用的优化方案和原理

  • DNS:加权轮询调度、基于延迟路由、基于地理位置路由
  • CDN:从靠近用户的位置提供内容,加速静态资源的加载速度
  • Load Balance 负载均衡:将传入的请求分发到应用服务器
    • 优点:
      • 防止请求进入不好的服务器
      • 防止过载
      • 帮助消除单一的故障点
    • 缺点:
      • 如果没有足够的资源配置或配置错误,负载均衡器会变成一个性能瓶颈
      • 引入负载均衡器以帮助消除单点故障但导致了额外的复杂性
      • 单个负载均衡器会导致单点故障,但配置多个负载均衡器会进一步增加复杂性
  • 垂直扩展:提升单机处理能力。垂直扩展的方式分为两种:
    • 增强单机硬件性能,例如:升级 CPU、内存、硬盘、网卡等等
    • 提升单机架构性能,例如:使用缓存来减少IO次数,使用异步来增加单服务吞吐量,使用无锁数据结构来减少响应时间
  • 水平扩展
    • 缺点:
      • 水平扩展引入了复杂度并涉及服务器复制
      • 服务器应该是无状态的:它们也不该包含像 session 或资料图片等与用户关联的数据。
      • session 可以集中存储在数据库或持久化缓存(Redis、Memcached)的数据存储区中。
      • 缓存和数据库等下游服务器需要随着上游服务器进行扩展,以处理更多的并发连接。
  • 反向代理(web 服务器)
    • 优点:
      • 增加安全性:隐藏后端服务器的信息,屏蔽黑名单中的 IP,限制每个客户端的连接数
      • 提高可扩展性和灵活性:客户端只能看到反向代理服务器的 IP,这使你可以增减服务器或者修改它们的配置
      • 本地处理 SSL 会话
      • 压缩、缓存、直接提供静态内容等优化
  • 应用层
    • 服务层和应用层分离,可以单独扩展和配置这两层
    • 通过微服务和服务发现技术对业务进行解耦
  • 数据库
    • 主从复制:主库写入复制,从库只读,如果主库离线,系统可以以只读模式运行,直到某个从库被提升为主库或有新的主库出现
    • 主主复制:两个主库都负责读操作和写操作,写入操作时互相协调。如果其中一个主库挂机,系统可以继续读取和写入
    • 联合:将数据库按对应功能分割
    • 分片:将数据分配在不同的数据库上,使得每个数据库仅管理整个数据集的一个子集
    • 非规范化:以写入性能为代价来换取读取性能。在多个表中冗余数据副本,以避免高成本的联结操作
    • SQL 调优:利用基准测试和性能分析来模拟和发现系统瓶颈,比如 CHAR、索引、拆分、避免 BLOB
  • 缓存:缓存可以提高页面加载速度,并减少服务器和数据库的负载,可以解决热门访问导致读取不均匀的问题

参考资料: