短链接生成系统的思路 ZK 发号+Base62 唯一 ID 各位觉得可行吗

时间：2020-02-15
博客：bytedance-hire.me

困在家里久了还是要翻翻书 orz 多学习一下~

抛砖引玉，欢迎讨论其他的短链方案，谢谢各位大牛指点~！

准备设计

设计一个系统之前，我们应该对系统的需求有所了解。对于短链系统，首先应该有以下思考：

• 我们需要什么样的短链接，具体是多短？
• 短链系统的请求量有多大？
• 这是个单实例还是分布式系统？

首先我们可以做一些假设，例如参考 Twitter 有 3 亿访问 /月，我们假设有它的 10%，也就是 3 千万 /月，平均每日 100 万。

然后再来假设生成的短链，一般格式为domain/unique_id，例如s-url.com/D28CZ63，我们假设 Unique ID 的长度最多为 7 位。

下面我们根据这些假设条件来完成这个系统的设计。

数据量计算

根据上面的假设，首先每个原始 URL 可以按照 2KB 估算（ 2048 字符），而短 URL 可以按照 17Byte 估算；我们可能还需要记录创建时间和过期时间，分别是 7Byte。因此可以大致估算每行记录的大小应该为 2.031KB。

我们一共有 30M 月访问，30M * 2.031KB = 60.7GB，每月约 60GB 数据，因此一年内估算为0.7TB，5 年 3.6TB数据量。

唯一 ID 算法

我们需要的是一个短的（ 7 位）唯一 ID 生成方案。考虑 Base62 和 MD5，Base62 即使用 0-9A-Za-z 一共 62 个字符，MD5 使用 0-9a-z，一般输出长度为 32 的字符串。

使用 MD5 的话，因为输出长度固定，我们可能需要截取其前 7 位来作为唯一 ID，这种情况下，首先不同的输入可能会输出相同的 MD5，其次，不同的 MD5 的前 7 位也可能是相同的。这样的话会产生不少的 Collision，需要业务上进行保障。而使用 MD5 的好处，也恰恰是如果不同用户提交相同输入，那么可以得到相同的 ID 而不需要重复生成新的短链 ID，但是同样需要业务进行处理和保证。

对于 Base62，每一位有 62 个可能字符串，7 位则是62^7=3521614606208种组合，每秒产生 1000 个 ID 的话也足够使用 110 年。同时在短 URL 的要求上，Base62 接受输入，产生的输出长度会根据输入变化，因此不需要进行截取，而只需要想办法将 7 位 ID 的所有情况消耗完毕就可以满足大部分场景的要求。Base62 伪代码如下：

def base62_encode(deci):
	s = '0-9A-Za-z'
	hash_str = ''
	while deci > 0:
		hash_str = s[deci % 62] + hash_str
		deci /= 62
	return hash_str

存储选择

一般我们会考虑使用 RDBMS 比如 MySQl，或者 NoSQL 比如 Redis。在关系型数据库中，横向扩展会比较麻烦，例如 MySQL 进行分表和分库，我们可能需要多个实例，而扩展需要一开始就设想好，但是这一点在 NoSQL 中会相对比较容易，例如使用一个 Redis 的 Cluster，或许向里面添加节点会相对容易一点。而使用 NoSQL 我们可能需要考虑数据的最终一致性，还有数据的持久化等问题。

同时根据业务场景，从性能上考虑如果在高峰期有大量短链生成请求需要写入到 MySQL 或许表现会比 Redis 差一些。

对于将“长 URL-短 URL”的映射关系写入数据库的步骤，重点是确保这个短 URL 没有被其他长 URL 使用过。如果使用过，那么你需要想办法使用新的字符串生成这个短 URL。

先来想一下，这是一个两步操作，首先查询是否存在，然后写入。如果这是个串行，那么是可行的。如果这是一个并行操作，很显然，你可能查询的时候发现没有存在这个短 URL，而其他 Session 也查到了同样的结果，最后大家都认为可以写入，然后写入过程中晚写的一方就会出问题。

在 RDBMS 中我们可能可以通过一些提供的方法来解决这个问题，例如INSERT_IF_NOT_EXISTS，但是在 NoSQL 中是没有这些方法的，因为它的设计是要实现最终一致性，所以不会提供这种支持。

基于以上分析和假设的方案

我们需要确定的内容主要是：

• 生成算法
• 存储选择

目前罗列出来的方案主要包括：MD5，Base62，以及 MySQL 和 Redis。

如果使用 MD5 的话，需要使用能够解决哈希冲突的 RDBMS，因为这个步骤在 NoSQL 上处理比较麻烦，所以会有 MD5+MySQL 的组合。这套组合实际上性能并不太满足需求，并且在扩展上会相对另外一组组合难度大些。

那么另外一种就是我们打算使用的方案：Base62+Redis。如何将 7 位 Base62 的所有情况都用尽，我们可以采用一个计数器，从 0-62^7 的数字转为 Base62，作为短链 ID 使用。这个方案在单实例上是很容易的，并且可以保证冲突问题。那么如何实现它的可扩展性呢？

在接入大流量的情况下，我们必然需要部署多点的 ID 生成服务，那么根据思路，我们需要对应的计数来转换成 Base62 的唯一 ID，如果不同的服务拿到了同样的计数，那么就会生成相同的 ID，造成冲突，且因为分布式的部署，仍然能够正常写入。

因此现在问题转化为如何让不同的服务拿到正确的计数。因为总的数字段是已知的（ 0-62^7 ），一个很简单的方法就是我们提前将这些数字进行分段，每个 ID 生成服务都拿到不同段的数字本地使用。例如：

0-100000
100001-200000
200001-300000
300001-400000
400001-500000
500001-600000
...

当服务的计数消耗完毕后，继续向计数分配的服务请求下一段可用的数字。例如目前有 3 个 ID 生成服务 A、B、C，在最初的分配中 A 拿到了 0-100000 号码段，B 拿到了 100001-200000，C 拿到了 200001-300000。当 A 使用完之后，询问分配服务，拿到下一段 300001-400000。如此即可解决计数器分布式部署的问题。

在数字段分配的业务场景，很容易想到使用 ZooKeeper 实现，因为 ZooKeeper 是分布式架构，保障单点故障时仍然可以正确地分配计数号码，这样我们不用重复造轮子实现自己的高可用的分发服务。