几个系统设计问题的解决思路
四火 2017-10-31 10:22
曾经写过一些系统设计方面的思考（比如这个和这个），但是最近准备面试，又接触了更多系统设计方面的问题。这里我想简单记录一些典型系统设计问题的思路。通过学习常见的系统，在心中形成一些问题解决的套路，以在思考和分析新问题的时候提供一些既定思路。很抱歉时间关系写得很简略，主要是提示一些思路和方向。
设计Tweeter
两种常见模型的trade off：
- Pull on demand: merge x timelines
- Push on change: async, read once to get them
缓存的设计，cache through
设计Web crawler
分布式queue，用来存放不断更新的需要爬虫完成的任务，典型的N个生产者+M个消费者的模型
key value storage，用来存储已经完成的网页，爬下来的数据放在S3上
Quota的使用：用来避免对某一个网站分配过多的资源
设计Type Ahead
核心在于避免从磁盘中实时查询，所有查询必须最快命中内存中的数据结构，并且查询的效率必须是O(1)的
采用Trie树，并且每个节点都要有指向结果集的链接
这样的数据结构的生成和更新必须在一开始就初始化完成
设计邮件系统
核心在于存储层schema的设计，user id作为range key，email id作为primary key，邮件的时间列索引化，以便查询某人最近的邮件
读写分离，收取邮件和发送邮件的服务分开
设计图片上传和访问系统
核心在于CDN的使用，要把静态资源的读取推送到离用户近的节点去。
处理在用户上传图片后，CDN数据还没有最新数据的情况（数据不一致的问题）
设计图像转换服务
典型异步系统的设计：
- 一个分布式queue存放异步任务，
- 另一个key-value storage存放任务状态，用来供另外的系统查询任务状态
两个API设计：上传图像后返回上传成功和任务ID；查询当前任务状态
另外可以考虑Lambda这种serverless的方式
设计分布式文件系统
核心在于怎么存放文件的meta data和实际的data从而分担读写压力，怎么处理文件的更新和删除
比如master上存放粗略的meta data，知道文件的分片在哪个slave服务器上，slave上存放分片具体信息，client读写仅仅通过master定位到slave，余下的工作不通过master完成，以避免master成为瓶颈
chunk和checksum的设计和使用
设计Tiny URL服务
schema的设计，需要解决两个问题：short URL -> long URL（最多被使用）和 long URL -> short URL
short URL的生成，几种方法在分布式系统中生成唯一ID
读基于缓存的优化
设计流量限制系统
- 思路1：Cache TTL on bucket level
- 思路2：Leaky Bucket / Token Bucket
设计Metrics系统
Ring Buffer，根据不同的统计粒度，设定不同的bucket size
根据不同的统计粒度，建立不同的表来持久化和供未来查询
读写模型：写多读少，汇总增量数据后再更新的优化
设计打车系统
核心在于司机和乘客怎样更新地理位置信息，系统怎样存储地理位置信息，已经怎样为乘客寻找最近的司机（geo hash）
读写模型：写多读少，怎样优化系统来应付这种状况，一致性的牺牲
设计即时聊天系统
引入Channel Service，socket push的使用
存储：解耦成消息表和会话表，使得用户可以单独设定每个会话的属性引入Channel Service
用户在线状态的维护：heartbeat
设计联机日志服务
持久化问题，日志client和日志service，减少单点故障造成的日志丢失
尽可能不影响现有业务应用，线程必须独立
引入队列，对于大量日志写入的缓冲
在网络不可用时，日志客户端可以写入本地文件，网络恢复后可以上传本地文件
文章未经特殊标明皆为本人原创，未经许可不得用于任何商业用途，转载请保持完整性并注明来源链接《四火的唠叨》