Design a TinyURL

---

title: Notes of System Design No.02 — Design a TinyURL
date: 2022-05-05 13:23:57
tags: 系统设计
categories:

• 系统设计

description: " Design a TinyURL"

---

1.Functional Requirements

• 1.长链接->短链接(写)

• 2.短链接->长链接(读)

• 3.可以设置超时时间

• 4.相同的长链接映射到不同的短链接上

• 5. 短链接的长度应该尽量短

• 6.短链接应该不可预测

2.Non-Functional Requirements

一般系统设计的非功能性指标都会从这几方面来考量

• 1.高可用性 ：不能有单点失败
• 2.可扩展性 ：能够方便的针对大量请求扩充
• 3.低延迟性： 读写的延迟尽量低
• 4.强一致性：

强一致性：系统中的某个数据被成功更新后，
后续任何对该数据的读取操作都将得到更新后的值；

弱一致性：系统中的某个数据被更新后，
后续对该数据的读取操作可能得到更新后的值，
也可能是更改前的值。但经过“不一致时间窗口”这段时间后，
后续对该数据的读取都是更新后的值；

最终一致性：是弱一致性的特殊形式，
存储系统保证在没有新的更新的条件下，
最终所有的访问都是最后更新的值。
1
2
3
4
5
6
7
8
9
10
11

在这个系统里面，要求的是强一致性。也就是说每次写请求更新完数据以后，进行读请求立马就能得到更新完的数据

• 5.持久性：不能丢数据
• 6.Read Heavy: 读写比例= 100:1

3.Assumption

• 假定短URL的字符组成->7个字符的Base64构成
• 假定每秒写100K次->1.4年可以耗尽7个字符长度的URL-> 89.6年可以耗尽8个字符构成的URL
• 假定长URL 最多有2083个字符长度构成

按照以上假设

• 在数据库中整个长短链接映射数据长度为2095(8个字符长度的短URL+ 2083个字符长度的长URL+4个字符长度的超时时间设定)
• 每秒100K次写请求 则每年会写入6599TB的数据
• 这么大的数据需要做Partition

4. API

5. High Level Design

写请求(长URL->短URL)

• 请求过来以后，负载均衡LB把请求分配到期中的一台App Server。为保证不会单点失败，App Server至少需要三台，因为如果是两台的话 如果其中一台正在升级维护，那么请i去就会全部的发到另外一台机器上 造成那台机器的过载.

• Monitor监控每台App Server 的CPU 内存 网络 磁盘等等 ，达到某一个阈值的时候 动态的增加或者减少某一个机器的请求

• DB存储长短链接映射的数据。需要对数据做Prtition，每个partition还需要做Replica复制备份，保证高可用

• MemCache缓存数据库中产常见数据 减少延迟

• App Server中由短链接映射生成长链接(Key Generation)的方式可以有以下几种

1. Random String
随机生成八位的字符串

问题1：不同的AppServer处理相同的长URL的时候有可能会生成相同的字符串

措施2： 可以对不同的App Server 分配一个两位不同的前缀，后六位随机生成。

缺点： 相同的App Server
重复处理相同的长URL的时候 有可能已经生成过了存在数据库里了 这个时候需要先检查数据库，再不断的重新用随机生成算法 直到生成一个不同的字符串
1
2
3
4
5
6
7
8
9

2.MD5
Long URL-->MD5-->128bits number -->base64-->21char string -->Sub string -->  前8 chars strign 

如果产生冲突 就在长URL的前面或者后面随机的增加一些字符，重新的走一遍这个过程
1
2
3
4

Ref:

MD5

Base64

先用MD5算法 处理原来的长链接 得到128bit的二进制数据

再用Base64编码这个128bit 二进制 ，得到一个大于21个字符的数据

在从这21左右字符里面 挑头6个或者8个作为最终的短链接编码

缺点：和上面一样 如果生成以后 检查数据库发现有冲突 那么就需要重新走一遍流程 再次生成随机串 直到没有冲突 ，增加了延迟

3. 维护一个专门的 Key Generation服务
用来专门生成短URL key
1
2

机制：

• 这个服务会提前在线下生成一堆短URL 存在数据库中，当App Server 需要一个新短URL的时候 就从这个数据库中获取 标记为已使用
• 这里增加的App Server也需要LB负载均衡和多个App Server 还有数据库也需要Partition和Replica.
  优势：
• 这种方式把冲突放到了线下 而不是线上 减少了延迟

改进：

• 可以设定App Server 每次从Key Generation模块取短URL的时候 ，每次取批量的URL 存在自己的内存里 一直到它把自己的url用完才重新去 Key Generation模块取

4.维护一个全局的计数器
1

机制：

• 每一个App Server读取全局的计数器，更新计数。
• 然后在App Server里面
  把读取到的计数器转换为64进制数，把64进制串作为新的短链
• App Server 操作全局计数器的时候要加锁
• 这样的方式全局计数器的QPS比较高

改进：

• App Server每一次不是取一个数，而是取一个范围.在某一个App Server
  要素：
• 某一个App Server宕机了，损失了一部分范围数怎么半？

不用担心，因为只是损失一部分 损失不大

• 每个App server 读取时候设定的范围是多大呢？

可以用每秒写的次数/App server的机器数，比如每秒100000writes,有20个App server 则设定的范围可以是 100000/20=5000

• 这种方式生成的短url是可被预测的吗？

不是的 因为在用户发送请求到LB负载均衡的时候，分发到的App server是不确定的。不同的App server维护的计数范围是不同的

要实在担心会出现可预测的问题，可以在App server读取全局计数器生成范围的时候 用洗牌算法 把范围打乱，这样就不会按照顺序依次分配

全局计数器的实现方法：

• 关系型数据库

要保证读写串行化 以及加锁解锁方法 可以用关系型数据库实现。

• ZooKeeper

Zookeeper有分布式的配置管理，可以实现上述的功能需求

对比
1

6. Low Level Design

DB Schema

• 只需要一张表 三个字段就可以

• 关系型数据库和非关系型数据库的比较

• 选择非关系型数据库的理由

Workflow

• 由长URL创建一个短URL的流程

• 由短URL读取一个长URL的流程

7. Dive Deep