面试题解析之设计短网址服务

在微信上看到篇短网址系统实现分析, 因为正好也碰到过类似题目, 手痒来分析下.

问题描述

实现一个短网址接口, 提供以下功能:

1. 将任意长度网址缩短为 n 位字符
2. 将该 n 位字符解析为长网址, 没有对应的短网址可返回 undefined

附注:

1. 不要过度设计
2. 设计给出理由, 尽量保证每行代码都有意义

问题分析

算法分析

短网址问题本质上是要建立长文本到 n 位字符空间的映射, 在该问题模型下, 算法上需要考虑的有以下几点

1. n 位字符表征的空间有多大(最大可以容纳多少条记录)
2. 如何将任意长文本映射到 n 位字符表征的空间中
   1. **进阶:**当映射出现冲突后, 如何处理.
   2. **进阶:**如果期望系统 99.99%的情况下均可用(经过限定次数的运算后可以给出结果), 系统最大可以接收多少条记录.

算法分析一: n 位字符表征的空间有多大

首先第一个问题, 每个状态可以容纳一条记录, n 位字符最多可以提供多少种"状态". 这其实是数学上的排列组合问题. 假设每一位可选 m 个字符, 那么一位字符可以表征 m 个状态, 2 位 m * m, 3 位 m * m * m, n 位则可以表征 m 的 n 次方个状态.

那么下一个问题, 一共有多少个 m 可选. 答案是 m 应是合法的 url 非保留字符, 因为这些字符可以安全的出现在 url 的任何地方, 适合作为短网址参数. 查阅RFC3986后可知非保留字符为ALPHA / DIGIT / "-" / "." / "_" / "~", 共26 * 2 + 10 + 4 = 66 个. 当字符空间 n = 10 时, 总共可以保存 66^10 约等于1.56*10^18条记录, 1 亿是10^8, 10^18条记录可以供 100 亿地球人每人提交 1 亿条记录. 事实上, n = 5 时状态空间就有66^5=1252332576, 12.5 亿, 为方便描述方案, 我们后续使用 n=5 进行演算.

算法分析二: 如何将任意长文本映射到对应的状态空间

已经提到, 5 位字符可以容纳 12.5 亿条长网址记录. 但问题是, 如何将用户提交的长网址添加到状态空间中, 以便充分利用该状态空间.

最简单的办法是从 0 开始对录入的每一条长网址进行编号, 这样可以不重不漏的使用全部 12.5 亿状态空间. 但按顺序编码会导致短网址内容可遍历, 存在相当高的安全风险, 不是一个好方案.

为避免遍历, 我们需要对记录 id 进行随机化. 目前主流方案为使用类似 md5/sha 算法作为 hash 函数, 目标是将长网址均匀的映射到状态空间中. 但这里存在两个潜在的问题. 首先, 没有经验的同学会选择直接取 md5/sha 输出结果的前 5 位作为 id, 但 md5/sha 函数的结果实际是一串 16 进制字符, 只取前五位意味着可使用的状态空间由66^5=1252332576降到了16^5=1048576, 状态空间缩小了 100 倍. 正确的方法是将运算结果作为数字取出, 然后对 12.5 亿取模, 这样才能尽量均匀的将结果分散到整个状态空间(之所以是尽量, 是因为 md5/sha 结果的状态空间并不是 12.5 亿状态空间的整数倍. 类似 10 对 9 取模, 10 和 1 都会落到 1 这个槽上, 导致分配到 1 的概率比分配到其他槽更高). 另外, md5/sha 作为专业的 hash 算法, 在追求安全性的同时必然导致性能上会有所牺牲. 所以网上也有方案提到可以用速度更快的MurmurHash/FNV/雪花算法算法或其他算法, 但这些 hash 方法都有优化空间.

优化的关键点在于意识到我们的目标只是将 id 随机化, 只要求每次获取的 id 尽可能随机, 而与其他任何因素都没有关系. 所以基于长字符串内容求 hash 由于需要读取字符串内容, 一定并不是最好的方案. 在本题中, 更好的方案应该是利用Math.random直接求取随机数, 然后将随机结果通过取模的方式映射到 12.5 亿的状态空间中即可. 在随机数方案下, 若出现 id 冲突, 则重新获取一次. 由于整体空间足够大, 新增一条记录对于整体状态空间而言可以忽略不记, 因此当已使用状态空间占比为 m 时, 重复执行 n 次即可获取有效 id 的概率为 1 - m^-n, 列表如下

m	1 次	5 次	10 次	20 次	25 次	50 次	100 次
10%	0.9	0.99999	≈1	≈1	≈1	≈1	≈1
25%	0.75	0.999023438	0.999999046	≈1	≈1	≈1	≈1
50%	0.5	0.96875	0.999023438	0.999999046	0.99999997	≈1	≈1
75%	0.25	0.762695313	0.943686485	0.996828788	0.999247457	0.999999434	≈1
90%	0.1	0.40951	0.65132156	0.878423345	0.928210201	0.994846225	0.999973439

可以看到, 在使用 90%的容量(记录了 11 亿条数据)后, 仍能保证在 99.99% 的情况下在 100 次运算以内取到唯一 id, 是目前性能最好的方案. 作为对比, 一轮 md5 需要执行 64 轮循环, sha-2 则需要 64/80 轮循环, 性能上显然不如随机数方案.

PS: 扩展点, 为什么将获取随机数视为和加减乘除同等级, 性能最优的原子操作

答: 通过查阅 V8 的 Math.random 实现易知, 生成每一位随机数耗时固定(8 次操作), v8 从实现层面上保证了获取随机数为 o(1)的操作且常数项非常小----至少远小于对长文本字符串的操作成本. 因此即使考虑随机数生成成本, 利用 Math.random 进行随机化在性能上依然优于常见 hash 算法

// https://chromium.googlesource.com/v8/v8/+/refs/heads/master/src/base/utils/random-number-generator.h#111

// Static and exposed for external use.
static inline double ToDouble(uint64_t state0) {
  // Exponent for double values for [1.0 .. 2.0)
  static const uint64_t kExponentBits = uint64_t{0x3FF0000000000000};
  uint64_t random = (state0 >> 12) | kExponentBits;
  return bit_cast<double>(random) - 1;
}

// Static and exposed for external use.
static inline void XorShift128(uint64_t* state0, uint64_t* state1) {
  uint64_t s1 = *state0;
  uint64_t s0 = *state1;
  *state0 = s0;
  s1 ^= s1 << 23;
  s1 ^= s1 >> 17;
  s1 ^= s0;
  s1 ^= s0 >> 26;
  *state1 = s1;
}

方案实现

数字转 n 位字符

将数字 id 转为字符串, 对应的数学概念是进制转换----从 10 进制转为 66 进制. 可以手写转换方案, 但性能&稳定性更好的方法则是直接使用编程语言的内置函数----例如, JavaScript 内置的进制转换函数最大支持到 36 进制.

// js
console.log(Number(200).toString(36));

前面说过, 由于状态空间足够大, 可以支持我们"浪费"一些状态空间以获取更好的性能和可维护性. 不过 36 进制下, 5 位字符只能产生36^5=60466176个状态, 有点少, 所以我们把 n 扩展到 6 位, 36^6=2176782336, 可以获得 21.7 亿的状态空间, 这样就够我们使用了.

然后还剩下最后一个问题, 如果期望系统经过限定次数的运算, 在 99.99%的情况下均可给出结果, 那么系统最大可以存储多少条记录.

这其实是个数学问题, 不妨设限定次数为 100 次求随机数运算, 那么进行列式计算:

$\\ \left [ 1 \right ] \hspace{60px} 1 - m^{n} = 0.9999, n=100 \\ \left [ 2 \right ] \hspace{60px} m^{100}=0.0001 \\ \left [ 3 \right ] \hspace{60px} 100\lg{m}=\lg{0.0001}=-4 \\ \left [ 4 \right ] \hspace{60px} \lg{m}=-0.04 \\ \left [ 5 \right ] \hspace{60px} m=10^{-0.04}=0.912 \\ \space$

易知, 如果要期望 99.99%情况下运算不多于 100 次可以结束整个流程的话, 容量可以使用到 91.2%, 考虑到 21.7 亿的总容量空间, 也就是说最大可以容纳21.7*0.912=19.79亿条数据.

数据结构

极简状态

由于这是一道面试题, 需要在有限时间内完成且数据量不大, 因此可以将数据直接作为 key-value 保存在内存中. 基础情况下对每一次提交新增一条记录即可, 使用对象保存 id 和长链接的对应关系{[key:string]:string}. 进一步优化可以使用专门的 key-value 数据对象: Map.

再进一步的优化则是在内存中保存 2 个 Map 对象, 一个是根据 id 寻找长链接, 另一个是根据长链接寻找对应 id, 避免重复添加记录. 具体代码略过

正式应用, 但请求量不大

当 qps 低于 3000 , 总记录数不大于 1000 万时(阿里云性能压测显示最低配机器跑 MySQL 数据库每秒大约可执行 3000 次查询请求), 可以认为是简单应用. 可以通过建立数据库表来持久化存储短链和长链的对应关系. 字段使用 varchar 即可.

正式应用, 但请求量大

此时需要使用 Redis 前置承接流量. 必要时可以通过添加前缀字符的方式将流量分配到不同集群上进行分别处理. 考虑到每增加一位字符可以将支持的集群数提升 36 倍, 或者将数据压力减少 36 倍, 且长短链转换为无状态服务. 因此最多额外使用 3 位字符, 即可将最大服务能力从 3000 qps 提升到到 3000 * 36^3 = 139968000, 即 1.3 亿 qps.

具体实现

略

总结

这个题可考察的点非常多, 堪比经典问题"浏览器从输入 url 到显示网页中间发生了什么". 前置的算法分析部分考察能否透过表象分析出状态空间和随机化分配id的本质, 后边的方案实现则考察系统设计功底: 对于大流量业务可以考察分库分表/一致性 hash 等概念, 对于稳定性可以考察灾备方案/服务分级管控设计, 对网络安全则可考察针对恶意攻击的实现与防范. 不过这些都是通用性的技能, 前面的短网址系统只是抛砖引玉, 后续具体考察的内容则要看具体工作要求而定

参考资料

1. URL 编码的奥秘, 介绍了 url 中的保留/未保留及受限的字符的概念
2. 你知道 33 进制吗？- 余晟以为, 提到了使用系统内置函数执行进制转换以扩展记录空间的思路
3. javascript 中 Number.toString 中 radix 的说明
4. 深入 JS getRandomValues 和 Math.random 方法
5. 阿里云 云数据库 RDS 性能白皮书 - MySQL 版 MySQL 5.6 测试结果