设计一个短链接生成系统

设计一个类似bit.ly的短连接生成系统。原文链接

1. 描述使用场景和约束

主要问题：

• 用户输入一个长文本（不单单是url），得到一个相对较短的链接
  • 过期策略：
    • 可选过期时间，默认永不过期
• 用户通过链接获取到原有内容
• 用户可以匿名（未登录用户）使用
• 提供页面分析功能

使用场景：

• 用户注册、登录
• 用户上传内容，获取响应短链接

约束和假设：

• 流量不均匀分布
• 短链接访问应该尽量快速
• 只支持文本内容
• 页面分析不需实时
• 千万级用户
• 月千万级写操作
• 月亿级读操作

大致估算：
每次生成操作大致占用空间：

• 1kb文本内容
• shortlink 7字节
• expiration_length_in_minutes 4字节
• created_at 5字节
• paste_path 255字节

合计大约1.27kb

每月大致12.7gb的文本内容，平均每秒4次写请求，40次读请求。

2. 创建系统设计

系统设计图

3. 设计关键组件

使用场景：用户上传文本得到生成的url
可以使用关系型数据库维护一个映射，保存文本文件与文件路径的对应关系。
在文件存储上，可以使用云文件存储（比如AWS S3）。

• 客户端将文本内容发送到反向代理上
• 反向代理将服务转发给服务器
• 写操作进行以下过程
  • 生成唯一连接
    • 数据库查询连接是否已经存在
    • 如果连接不唯一，重新生成
  • 数据存储到pastes表中
  • 将文本文件存储到文件服务器中
  • 返回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)

创建关于created_at和shortlink的索引，以提高查找速度。
生成唯一url的过程：

• 对 用户ip+时间戳 进行md5哈希
• 对上面的哈希内容进行base62转码
• 返回转码结果的前7位数作为链接token参数，总共支持62^7的容量

使用场景：用户访问链接，得到数据内容

• 客户端访问服务器的反向代理
• 反向代理把请求转发到对应服务器
• 读请求服务需要坐下面的事：
  • 去数据库查询token是否存在，如果存在，则按路径信息获取文本内容，否则返回报错信息

使用场景：页面分析
使用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)

使用场景：定期清除过期链接和内容
一般使用crontab定期清除过期内容，和访问链接时惰性清除两种方式。

4.完善设计

最终设计图

系统设计的完善过程

1. 压力测试
2. 根据链路不同操作耗时占比，确定系统瓶颈
3. 根据瓶颈寻找替代方案，做权衡
4. 再从第一点开始