短链接生成系统的思路 ZK 发号+Base62 唯一 ID 各位觉得可行吗
RedisMasterNode · 2020-02-15 15:56:02 +08:00 · 3551 次点击这是一个创建于 1522 天前的主题，其中的信息可能已经有所发展或是发生改变。
时间：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 是分布式架构，保障单点故障时仍然可以正确地分配计数号码，这样我们不用重复造轮子实现自己的高可用的分发服务。
 |
1
jason0916 2020-02-15 16:15:45 +08:00
zookeeper 随着规模增大 需要同步到更多机器 tps 会下降 ，那么这就意味 zk 的集群不能很大，扛不住很大的 qps。
出现故障的时候是不是需要考虑下降级方案 |
 |
2
RedisMasterNode OP @jason0916 我的理解是因为设想里面 ZK 是负责号码段的分发，按照预定的请求（如 1000/秒）只要业务上将号码段划分得合理，App （也就是生成短链的服务）实际上并不需要特别频繁地向 ZK 索取新号段，得到的号段是由 App 自行管理的（比如丢在 Redis 持续自增到>上限再进行获取）。
假如我划分的号段，每段长度是 10w，按照请求速度预计可以支撑后续的 100 秒内的 ID 生成，如果我的 App 服务一共部署了 20 个，也就是 100 秒内大约只会有 20 次 App 向 ZK 索取号段的请求，这样是否可以忽略 ZK 的问题？ ZK 这块新学，还有很多不懂望多指教 |
|
3
jason0916 2020-02-15 17:12:27 +08:00
@RedisMasterNode 这样确实不用担心 zk 的 qps 问题了，不过我想确认下这个分段，是怎么存储在 zk 内？
1. 是 zk 内只存下一段，某个 app 取走之后进入下一段，app 自己保留自己消费到哪一段信息（可能 app 崩溃会导致多个空段浪费） 2. 还是说在哪里存 app 对于分段的消费进度。 持久化选择 redis 是不可靠的，我理解应该存可以落磁盘的存储。这个场景可以接受极端情况下部分长链接和短链接映射关系的丢失么？（关于 insert_if_not_exists，redis 的 setnx 命令其实是有支持的，如果对别的数据类型，可以实现 lua 脚本做这个事情） |
|
4
RedisMasterNode OP @jason0916 zk 分段是 1 的形式，app 崩溃确实会导致分段浪费，可以看 app 内是否能解决这个问题，例如现在 app 持有某个分段，服务重启后看是否能继续使用；另外也可以优化分段区间，减少浪费的区间长度，具体两个都是业务方案的实现
使用 redis 集群来存储长短链映射关系主要是考虑性能和 Cluster 易于横向扩展，Cluster 的模型主节点如果失效，会切换至从节点（当然抖动是不可避免的），可以一定程度降低风险，但是确实会有丢失写入，以及持久化 buffer 未写进磁盘的问题，这个再想一想好了，没有覆盖到这个问题 如果直接用例如 MySql 这类，性能上可能会需要更大的成本来满足？不同方案各有优劣，可以看业务来定，谢谢建议，很有帮助 |
|
5
jason0916 2020-02-15 17:46:17 +08:00
@RedisMasterNode mysql 做读写分离，过千的 qps 还是可以扛下的，这个场景下我理解读多写少，并且对主从同步消耗的时间容忍比较高，读流量可以从从节点读，扩展性还是可以的。不过对于这些映射记录的分库分表可能要考虑下怎么弄，单表记录过百万会影响性能（实际上有没有这么多存疑）
|
|
6
RedisMasterNode OP @jason0916 这个不是业务需求，是系统设计的一些学习和思考笔记吧（自嗨行为 hhh ），不过问题多一点的话可以多了解一些知识也是很好的。
在我看来因为查询的时候如果按照 unique_id 查询，如果改用 mysql 存储的话，因为数据总量会比较大可能我会考虑按时间分表，这时候 Unique_id 的设计可能会从纯 base62 改为时间前缀标识+base62 来做，切分单表或者库的数据量，也是一种方案。 整个系统都是假设的，需求也是假设的，不过讨论可以学习到东西，thx |
 |
7
levelworm 2020-02-16 10:32:27 +08:00 via Android
我有个傻逼的想法，能不能提前生成比如一千万个，然后每周挑个时间再生成。生成好了就分配了。。。
|
|
8
RedisMasterNode OP @levelworm 虽然听起来可行，首先你的中心节点 /或者说生成器需要做成单实例的，因为不能多个实例同时生成，否则就会有冲突，其次中心节点分发生成后的 ID，也就是一段字符串，会有额外的流量开销（比如分发 1000w 个长度为 7 的字符串），不管大还是小，肯定是不如按号段分发计数器（只需要传输[0, 10000000]这样的范围数据），单点的服务再生成 ID 的
|
 |
9
mengzhuo 2020-02-16 14:35:24 +08:00
其实不用你这么复杂……
随机数跟机器的 mac 地址（或者启动的时候从数据库里拉一个唯一标识）做异或 自己机器保证自增就好 不放心就加个时间前缀，反正才 4 字节 |
|
10
RedisMasterNode OP @mengzhuo 随机数和 mac 地址做异或，如何保证唯一性能解释下吗，个人认为这种生成器里面出现随机数的话思路就已经错掉了。。。不同 mac 地址+随机数可以保证不发生冲突吗？
|
 |
11
daquandiao2 2020-02-16 14:46:45 +08:00
bytedance-hire.me 域名很 6
|
|
12
RedisMasterNode OP @daquandiao2 hhhh 是的特地注册的～ me 后缀还不让备案
|
 |
13
mrlmh00 2020-02-16 19:08:10 +08:00
|
|
14
RedisMasterNode OP @mrlmh00 嗯看到确实是这样，但是这个问题还是非常好解决，只需要想办法将 base62 生成的信息按照特定规则编码出来增加破解难度就可以了？至于其他的生成方案，主楼已经讲过为什么不打算使用了。
当然如果有所谓的''完美''方案，也欢迎提出来交流学习～ |
 |
15
yoyos 2020-02-17 00:00:57 +08:00
是不是可以把全部号段一开始就分配完，每台机子负责的号段范围在配置文件 /配置中心直接指定好。
只有扩容的时候才重新划分号段。 这样只需要保证在单 App 内部递增就行了。 容灾可以考虑磁盘顺序写到文件，就能恢复了。 |
|
16
RedisMasterNode OP @yoyos base62 方案号段会影响输出的长度，如果你要做成一次性分配完的话不方便在固定长度短链（也就是业务要求的 7 位）下水平扩容，而且复杂度并没有降低，还是要实现扩容发号那一套东西。。。
|
 |
17
kayseen 2020-02-26 09:12:54 +08:00
刚刚试了一下`def base62_encode(deci)`方法运行不了,请问关于这种生成方案的程序您有完整版的吗?
|
|
18
RedisMasterNode OP @kayseen
``` def base62_encode(deci): s = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz' hash_str = '' while deci > 0: hash_str = s[deci % 62] + hash_str deci /= 62 return hash_str if __name__ == '__main__': num = 12837912839128347316 print(base62_encode(num)) ``` |
|
19
RedisMasterNode OP |
|
20
RedisMasterNode OP @kayseen 我的思路就是你只要能够保证分发的数字（ deci ）唯一，就能保证 base62 没有冲突，分发唯一这个靠 ZK 和本地库的自增使用来保证，或者自己想思路也可以
|
|
21
kayseen 2020-02-26 16:33:05 +08:00
@RedisMasterNode
非常感谢,学到了很多 |
|
22
kayseen 2020-02-26 16:52:02 +08:00
@RedisMasterNode
请问您考虑到这个 base62 的解码了吗?就是由编码出来的组合推出那个随机数 |
|
23
RedisMasterNode OP @kayseen 这个 base62 可以被反解，你的业务是需要能被反解还是不能被反解的？这套方案主要解决了分布式发唯一号的坑，不过可以反推原来序号这个问题可能还需要额外解决，因为 base62 出来之后不是个随机数，其实应该说是 62 进制的顺序增长的数比较合适
|
Select Language