注意: 为了避免重复,当前文档会直接链接到系统设计主题的相关区域,请参考链接内容以获得综合的讨论点、权衡和替代方案。
设计 Bit.ly - 是一个类似的问题,区别是 pastebin 需要存储的是 paste 的内容,而不是原始的未短化的 url。
收集这个问题的需求和范畴。 问相关问题来明确用例和约束。 讨论一些假设。
因为没有面试官来明确这些问题,所以我们自己将定义一些用例和约束。
向面试官说明你是否应该粗略计算一下使用情况。
shortlink
- 7 bytesexpiration_length_in_minutes
- 4 bytescreated_at
- 5 bytespaste_path
- 255 bytes简单的转换指南:
概述一个包括所有重要的组件的高层次设计
深入每一个核心组件的细节
我们可以用一个 关系型数据库作为一个大的哈希表,用来把生成的 url 映射到一个包含 paste 文件的文件服务器和路径上。
为了避免托管一个文件服务器,我们可以用一个托管的对象存储,比如 Amazon 的 S3 或者NoSQL 文档类型存储。
作为一个大的哈希表的关系型数据库的替代方案,我们可以用NoSQL 键值存储。我们需要讨论选择 SQL 或 NoSQL 之间的权衡。下面的讨论是使用关系型数据库方法。
pastes
表里面向面试官阐明你需要写多少代码
pastes
表可以有如下结构:
shortlink char(7) NOT NULL
expiration_length_in_minutes int NOT NULL
created_at datetime NOT NULL
paste_path varchar(255) NOT NULL
PRIMARY KEY(shortlink)
我们将在 shortlink
字段和 created_at
字段上创建一个数据库索引,用来提高查询的速度(避免因为扫描全表导致的长时间查询)并将数据保存在内存中,从内存里面顺序读取 1MB 的数据需要大概 250 微秒,而从 SSD 上读取则需要花费 4 倍的时间,从硬盘上则需要花费 80 倍的时间。 1
为了生成唯一的 url,我们可以:
[a-zA-Z0-9]
是比较合适的+
和 -
字符串而产生一些问题def base_encode(num, base=62):
digits = []
while num > 0
remainder = modulo(num, base)
digits.push(remainder)
num = divide(num, base)
digits = digits.reverse
url = base_encode(md5(ip_address+timestamp))[:URL_LENGTH]
我们将会用一个公开的 REST 风格接口:
$ curl -X POST --data '{"expiration_length_in_minutes":"60", \"paste_contents":"Hello World!"}' https://pastebin.com/api/v1/paste
Response:
{
"shortlink": "foobar"
}
用于内部通信,我们可以用 RPC。
REST API:
curl https://pastebin.com/api/v1/paste?shortlink=foobar
Response:
{
"paste_contents": "Hello World",
"created_at": "YYYY-MM-DD HH:MM:SS",
"expiration_length_in_minutes": "60"
}
因为实时分析不是必须的,所以我们可以简单的 MapReduce Web Server 的日志,用来生成点击次数。
class HitCounts(MRJob):
def extract_url(self, line):
"""Extract the generated url from the log line."""
...
def extract_year_month(self, line):
"""Return the year and month portions of the timestamp."""
...
def mapper(self, _, line):
"""Parse each log line, extract and transform relevant lines.
Emit key value pairs of the form:
(2016-01, url0), 1
(2016-01, url0), 1
(2016-01, url1), 1
"""
url = self.extract_url(line)
period = self.extract_year_month(line)
yield (period, url), 1
def reducer(self, key, values):
"""Sum values for each key.
(2016-01, url0), 2
(2016-01, url1), 1
"""
yield key, sum(values)
为了删除过期的 pastes,我们可以直接搜索 SQL 数据库 中所有的过期时间比当前时间更早的记录, 所有过期的记录将从这张表里面删除(或者将其标记为过期)。
给定约束条件,识别和解决瓶颈。
重要提示: 不要简单的从最初的设计直接跳到最终的设计
说明您将迭代地执行这样的操作:1)Benchmark/Load 测试,2)Profile 出瓶颈,3)在评估替代方案和权衡时解决瓶颈,4)重复前面,可以参考在 AWS 上设计一个可以支持百万用户的系统这个用来解决如何迭代地扩展初始设计的例子。
重要的是讨论在初始设计中可能遇到的瓶颈,以及如何解决每个瓶颈。比如,在多个 Web 服务器 上添加 负载平衡器 可以解决哪些问题? CDN 解决哪些问题?Master-Slave Replicas 解决哪些问题? 替代方案是什么和怎么对每一个替代方案进行权衡比较?
我们将介绍一些组件来完成设计,并解决可伸缩性问题。内部的负载平衡器并不能减少杂乱。
为了避免重复的讨论, 参考以下系统设计主题获取主要讨论要点、权衡和替代方案:
分析存储数据库 可以用比如 Amazon Redshift 或者 Google BigQuery 这样的数据仓库解决方案。
一个像 Amazon S3 这样的 对象存储,可以轻松处理每月 12.7 GB 的新内容约束。
要处理 平均 每秒 40 读请求(峰值更高),其中热点内容的流量应该由 内存缓存 处理,而不是数据库。内存缓存 对于处理分布不均匀的流量和流量峰值也很有用。只要副本没有陷入复制写的泥潭,SQL Read Replicas 应该能够处理缓存丢失。
对于单个 SQL Write Master-Slave,平均 每秒 4paste 写入 (峰值更高) 应该是可以做到的。否则,我们需要使用额外的 SQL 扩展模式:
我们还应该考虑将一些数据移动到 NoSQL 数据库。
是否更深入探讨额外主题,取决于问题的范围和面试剩余的时间。
参考安全。
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。