[翻译]设计Pastebin.com(or Bit.ly)系统

设计Pastebin.com (or Bit.ly)系统

注：本文档直接链接到系统设计主题中的相关领域，以避免重复。请参考链接内容来了解总体的讨论要点、利弊权衡以及替代方案。

**设计Bit.ly**是一个类似的问题。只是Pastebin还具有一个额外的功能，即存储粘贴的内容，而不是原始的未缩短过的url。

第一步：列出用例和约束的大纲

确定应用场景：收集需求和范围问题；提问来弄清阐明用例和约束，讨论来作出假设。

在没有面试官来阐明清这些问题的情况下，我们将定义一些用例和约束。

用例

我们将确定问题的范围，只处理以下使用情况

• 用户：输入一段文本后，获得一个随机生成的链接
  • 过期
    • 默认设置是不会过期的
    • 可以选择一个时间过期
• 用户：输入一个paste的url链接，便可以看到内容
• 用户：是匿名的
• 服务：可以追踪得到页面分析结果
  • 每月的访问数据
• 服务：删除过期的pasten内容
• 服务：具有高可用性

范围之外

• 用户：注册一个帐户
  • 用户：认证邮箱
• 用户：登录注册账户
  • 用户：编辑文档
• 用户：可以设置可见性
• 用户：可以设置短链接

约束和假设

情况假设

• 流量不是均匀分布的
• 产生一个短链接应该是快速的
• 粘贴paste内容只能是文本
• 页面浏览分析不需要是实时的
• 1000万用户
• 每月1000万次的粘贴paste写入量
• 每月1亿次的粘贴paste阅读
• 10:1的读与写比例

计算用量

向你的面试官说明你是否应该对用量进行粗略估计。

• 每次粘贴paste的大小
  • 每次粘贴的内容为1KB
  • shortlink- 7 bytes
  • expiration_length_in_minutes - 4 bytes
  • created_at - 5 bytes
  • paste_path - 255 bytes
  • total = ~1.27 KB
• 每月12.7GB的新粘贴内容
  • 每个1.27 KB 的粘贴paste * 每月1000万个paste
  • 3年内约有450GB的新粘贴内容
  • 3年内有3.6亿个短链接
  • 假设大多数是新的粘贴内容，而不是对现有内容的更新
• 平均每秒钟写4次粘贴内容
• 平均每秒40次读取请求

方便的转换指南：

• 每月250万秒
• 每秒1个请求=每月250万个请求
• 每秒40个请求=每月1亿个请求
• 每秒400个请求=每月10亿个请求

第二步: 创建一个高水平的设计

勾勒出一个包含所有重要组成部分的高层次设计。

第三步：设计核心组件

用例: 用户输入一段文本后，获得一个随机生成的链接

我们可以使用一个关系数据库作为一个大的哈希表，将生成的url映射到文件服务器和包含粘贴paste文件的路径。

我们不采用管理文件服务器的方式，而是使用一个可管理的对象存储，如Amazon S3或NoSQL文档存储。

作为一个大型哈希表的关系数据库的替代品，我们可以使用NoSQL键值存储。我们应该讨论选择SQL或NoSQL之间的利弊权衡。下面的讨论使用了关系型数据库的方法。

• 客户端向作为反向代理的web服务器发送一个创建粘贴paste请求
• web服务器将该请求转发给 Write API 服务器
• Write API 服务器做以下工作。
  • 生成一个唯一的url
    • 通过查看SQL数据库是否有重复的网址，来检查该网址是否是唯一的。
    • 如果url不是唯一的，它将生成另一个网址
    • 如果我们支持自定义url，我们可以使用用户提供的url（也检查是否有重复的）。
  • 保存到SQL数据库中的粘贴paste表
  • 将粘贴的数据保存到对象存储中
  • 返回url

与你的面试官明确说明你要写多少代码

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列的索引，数据库会使用这个索引来强制执行唯一性。我们将在creative_at上创建一个额外的索引，以加快查询速度（用日志时间代替扫描整个表），并将数据保存在内存中。从内存中连续读取1MB的数据需要250微秒，而从SSD中读取需要4倍，从磁盘中读取需要80倍的时间。¹

为了生成唯一的url，我们可以:

• 对用户的ip_address + 时间戳进行MD5 哈希
  • MD5是一个广泛使用的散列函数，产生一个128位的哈希值
  • MD5是均匀分布的
  • 另外，我们也可以取随机生成的数据的MD5哈希值
• 使用Base62对MD5哈希结果值进行编码
  • Base 62 编码字符为[a-zA-Z0-9]，不需要转义特殊字符，这对Urls来说很有效。
  • 原始输入只有一个哈希结果，而且Base 62是确定性的（不涉及随机性）。
  • Base 64 是另一种流行的编码，但由于有额外的+和/字符，所以对urls有问题。
  • 下面的Base 62伪代码在O(k)时间内运行，其中k=7。

def base_encode(num, base=62):
    digits = []
    while num > 0
      remainder = modulo(num, base)
      digits.push(remainder)
      num = divide(num, base)
    digits = digits.reverse

• 取输出的前7个字符，结果是62^7个可能的值，应该足以处理我们3年内3.6亿个短链接的约束。

url = base_encode(md5(ip_address+timestamp))[:URL_LENGTH]

我们将使用一个公共REST API。

$ curl -X POST --data '{ "expiration_length_in_minutes": "60", \
    "paste_contents": "Hello World!" }' https://pastebin.com/api/v1/paste

Response:

{
    "shortlink": "foobar"
}

对于内部通信，我们可以使用远程过程调用。

用例：用户输入一个paste url并查看其内容

• 客户端向web服务器发送一个获取粘贴paste的请求
• Web服务器将该请求转发给 Read API 服务器
• Read API服务器做以下工作。
  • 检查SQL数据库中生成的url
    • 如果url在SQL数据库中，则从对象存储中获取粘贴内容
    • 否则，给用户返回一个错误信息

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"
}

用例：网页跟踪分析服务

由于实时分析不是一个要求，我们可以简单地对Web服务器的日志进行 MapReduce 以生成点击数。

与你的面试官明确说明你要写多少代码。

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)

用例：删除过期paste的服务

要删除过期的粘贴，我们可以直接扫描SQL数据库中所有过期时间戳大于当前时间戳的条目。然后，所有过期的条目将被从表中删除（或标记为过期）。

第四步：扩展设计

鉴于约束条件，识别并解决瓶颈问题。

重要：不要简单地从最初的设计直接跳到最终的设计中去!

说明你会迭代地做这件事。1) 基准测试/负载测试；2) 剖析瓶颈；3) 解决瓶颈问题，同时评估替代方案和利弊权衡；4) 重复。参看设计一个可以在AWS上扩展到数百万用户的系统，作为一个如何对初始设计进行迭代扩展的样例。

讨论初始设计可能遇到的瓶颈以及如何解决每个瓶颈是很重要的。例如，通过添加一个带有多个Web服务器的负载平衡器、CDN、主从复制，可以解决哪些问题？各自的替代方案和利弊权衡是什么？

我们将介绍一些组件来完成设计并解决可扩展性问题。内部负载均衡器没有显示，以减少混乱。

为了避免重复讨论，请参考下面的系统设计主题来了解主要的论文要点、利弊权衡和替代方案。

• DNS
• CDN
• Load balancer
• Horizontal scaling
• Web server (reverse proxy)
• API server (application layer)
• Cache
• Relational database management system (RDBMS)
• SQL write master-slave failover
• Master-slave replication
• Consistency patterns
• Availability patterns

数据库分析可以使用数据仓库解决方案，如亚马逊 Redshift 或谷歌 BigQuery。

像亚马逊S3这样的对象存储可以从容地处理每月12.7 GB 的新内容的约束。

为了解决每秒40次的平均读取请求（高峰时更高），热门内容的流量应该由内存缓存而不是数据库来处理。内存缓存对于处理分布不均的流量和流量高峰也很有用。SQL Read 多副本应该能够处理缓存的缺失，只要副本没有被副本写入所拖累。

对于单个SQL Write 主从来说，每秒平均4次粘贴写（高峰时更多）应该是可以做到的。否则，我们就需要采用额外的SQL扩展模式。

• Federation
• Sharding
• Denormalization
• SQL Tuning

我们还应该考虑将一些数据转移到NoSQL数据库。

额外的讨论要点

根据问题的范围和剩余时间，可以深入研究其他的话题。

NoSQL

• Key-value store
• Document store
• Wide column store
• Graph database
• SQL vs NoSQL

缓存

• 缓存到哪里？
  • Client caching
  • CDN caching
  • Web server caching
  • Database caching
  • Application caching
• 缓存什么？
  • Caching at the database query level
  • Caching at the object level
• 何时更新缓存？
  • Cache-aside
  • Write-through
  • Write-behind (write-back)
  • Refresh ahead

异步性和微服务

• Message queues
• Task queues
• Back pressure
• Microservices

通信

• 对利弊权衡进行讨论：
  • 与客户的外部通信 - HTTP APIs following REST
    • 内部通信 - RPC
• 服务发现

安全

见 security section.

延迟数

见 每个程序员应该知道的延迟数字。

持续推进

• 继续对你的系统进行基准测试和监测，以解决出现的瓶颈问题
• 扩展是一个反复的过程