浅谈短链的设计

,目前在很多场景下，都需要短链，尤其是涉及到一些 URL 下发的逻辑。为什么需要短链呢？考虑到一个 URL 上有 path、query 等参数，各种参数拼接在一起就成了一个长不拉几的字符串。,在很多社交平台上，对于发送的文本是有长度限制，过长的 URL 很容易被截断，然后触达就无效了。当用户收到一个短链，心情可能更加愉悦：,,知己知彼百战百胜，先来看看一个短链有哪些信息。,,协议 + 域名 + path，协议可以直接忽略。域名是必须的（废话），并且足够短，否则的话就变成了长的短链（挺傻的）。最后 path 的部分才是关键，看起来是一个由 6 个字符组成的字符串，并且字符的范围是大小写字母+数字。,足够短的域名需要什么条件？大概率钱够就行。涉及到钱的部分，这里就不深入探究了。所以来研究一下这个 path 的生成。,Path 的其中一种方式就是通过哈希算法计算得到。常见的哈希函数有 MD5、SHA1 等大家常见的加密型哈希算法，也有 HighwayHash、MurmurHash 等非加密型哈希函数。以 MurmurHash 为例，目前已经迭代到 MurmurHash 3，能够产生 32bit 和 128 bit 的哈希值，并且对于规律性较强的 key，随机分布的特征表现的很不错。,不过哈希冲突是不可控的，我们虽然有 N 种解决哈希冲突的方式，但是会增加整个系统的整体复杂度。,自增 ID,也可以维护一个 ID 自增生成器，对于每一个长链生成1、2、3等自增的序号，然后把长链和序号的映射保存在数据库里面，然后得到如 https://fake.short/1、https://fake.short/2 等短链。考虑到单机容易造成单点故障，所以一般都是分布式的 ID 生成器。,Mysql 自增,假设有 10 台 Mysql 服务器，每一台初始值分别为 0……9，然后每生成一个需要就递增 10，这样确保这 10 台 Mysql 服务器产生的 ID 不重复。但这个方案缺点比较明显，就是 ID 是有迹可循的，爬虫的可以顺着顺序依次请求得到；水平扩展不容易，如之前约定 10 台机器，每台机器生产的步长是 10，如果需要增加一台机器，比较困难；数据库压力还是很大，每次获取ID都得读写一次数据库，只能靠堆机器来提高性能。,基于雪花算法,SnowFlake 是 Twitter 公司采用的一种算法，目的是在分布式系统中产生全局唯一且趋势递增的ID。,,第一位占用 1bit，其值始终是0，没有实际作用。2.时间戳 占用 41bit，精确到毫秒，总共可以容纳约 69 年的时间。3.工作机器id 占用10bit，其中高位 5bit 是数据中心ID，低位 5bit 是工作节点ID，最多可以容纳 1024 个节点。4.序列号 占用12bit，每个节点每毫秒0开始不断累加，最多可以累加到4095，一共可以产生 4096 个ID。,SnowFlake算法在同一毫秒内最多可以生成 1024 X 4096 = 4194304 个全局唯一ID。,国内也有不少基于（类）雪花算法的开源分布式唯一ID生成器：,由百度开源的分布式 UID 生成器。https://github.com/baidu/uid-generator,Leaf 是美团开源的分布式ID生成器，能保证全局唯一，趋势递增，但需要依赖关系数据库、Zookeeper等中间件。https://tech.meituan.com/2017/04/21/mt-leaf.html,如果我们得到『1536389934』这个序号的话，看起来还是有点长，如果想进一步缩短，可以把十进制数转换成62进制数。然后就得到一个比原序号更短的 ID 了。,,为什么要用62进制转换？,众所周知，301 是永久重定向，浏览器会把重定向后的地址缓存下来，下次访问的时候，就不会向原地址发起请求；按理来说通过 301 的重定向性能会更好，对服务的压力也更小。,,但是，正因为 301 会在浏览器中有缓存，所以服务端就没办法知道有多少用户是通过这个短链访问的，在现如今什么数据都可以分析一波的时代，这些数据的缺失，就失去了分析活动的能力。所以一般都通过 302 进行重定向，便于记录使用的数据，稍微增加点 Server 的压力。（没有什么是不能通过加机器解决的