实现一个短链服务器

短链服务器，即将长链接转换为短链接的服务器，本文记录实现一个短链服务器的过程。

背景

将长链接转换成短链接有几个显而易见的好处：

1. 方便记忆
2. 便于分享
3. 在需要生成二维码时，能降低二维码的复杂度

以及一些其他用途，例如可以基于短链服务做一些流量统计，增加链接过期等功能。

构思

实现短链的转换，存储及跳转是非常容易的，但是在实际实现过程中，还是有一些需要考虑的问题：

短链编码生成方式的选择

短链编码，即短链中唯一变化的部分。可选的方式不止一种，但是有一个共同点，就是如果生成了一个10进制的数字，则可以将其进行进一步进行base62编码，因为base62可以使用包括数字，小写字母，大写字母在内的62个字符（有些短网址方案还包含-和_），可以进一步缩短短链的长度。

1. 自增ID

使用各种方式（程序内存内自增，数据库自增，Redis自增等）生成一个自增的ID，然后将这个ID转换为62进制的字符串作为短链的编码。这种处理方式的好处是因为基于现有的自增逻辑，只要能够保证自增机制的可靠以及唯一性，就可以保证短链的生成无碰撞。

但缺点也很明显，首先这样生成的编码是有序的，很容易被其他人遍历到所有的短链；其次，生成的短链和原长链接本身不具有任何关联性，这意味着如果希望不对一个长链接重复生成短链，就需要在每次生成短链之前，用当前这个长链接查询是否已经生成过短链，考虑到原链接可能会非常长，这样产生的查询开销显然是不低的；另外，如果借助的是数据库主键自增的方式，数据库逐渐自增的速率也可能会成为瓶颈。

2. 随机数

直接在程序内使用普通随机数作为短链编码，然后将其转换为62进制的字符串。这种方式的好处是生成的短链是无序的，不容易被遍历到所有的短链。缺点是随机数的生成本身是有碰撞的，在生成速度比较快的情况下，这个碰撞的几率可能会非常大，这样一来，可能需要重复几次随机过程才能生成一个新的短链，另外如果希望不重复，和自增ID的方式一样，也需要在生成短链之前，用当前这个长链接查询是否已经存在短链。

3. HASH算法

使用HASH算法，例如MD5，SHA1等，将长链接转换为一个固定长度的字符串。这样生成的短码是无序的，而且生成的短码和原长链接具有一定的关联性，这样一来，只需要在HASH之后直接验证当前生成的HASH值有没有生成过短链即可，而不需要再使用长链本身进行查询。

HASH算法的缺点在于虽然碰撞概率较低，但是还是存在碰撞的可能性，而且如果使用的是MD5，SHA1等算法，生成的短链长度也会比较长，不利于短链的使用。

最终选型

综合考虑，最终选型为使用HASH算法，因为它兼具了无序性以及和原链接有关联的特点。

目前需要解决的问题主要是HASH值过长的问题，参考了其他实现之后，决定采用非加密HASH算法，例如MurmurHash，xxHash，CityHash等。

非加密HASH算法和加密HASH算法最大的区别¹是，这类算法的初衷往往只是为了防止数据被意外修改（比如CRC），或者将数据分散到不同的桶中，而不是为了防止数据被恶意修改，因此这类算法的设计目标是尽可能快地计算出HASH值，而不是尽可能难以被破解²。

鉴于目前的场景，显然非加密HASH函数更适合我们，因为我们需要更短的HASH值，而许多非加密HASH都提供生成32位HASH值的选项。而具体到选择哪种非加密HASH函数，在参考了一些其他人的测试结果，综合性能，生成质量（离散性，随机性），以及社区活跃度（参考了其在Github上的活跃程度以及各语言实现库的数量）³，最终选择采用xxHash（XXH32）作为我们的HASH函数。

至于碰撞的问题，显然只能通过假如碰撞了就在原字符串后追加一些内容，再重新生成的方式。

存储方式的选择

对于当前业务场景，我选取存储方式的标准主要有：

1. 读写性能，短链的存取速度应该尽可能快，至少存储不能成为瓶颈
2. 较少的依赖，短链服务应该尽可能独立，不应该依赖于其他服务
3. 对于我们将要使用的语言及框架（C# on dotnet 6），有成熟的可用支持库

综合考虑，最终排除了SQLite，Redis，LevelDB三种存储方式，他们的缺点分别对应上面的三点

最终，我选择了FASTER KV作为存储方案，其作为一个嵌入式，支持持久化的key-value存储库，在支持基本key-value操作的同时，还拥有非常优秀的性能（根据官方的基准测试，在单台服务器的ops达到了惊人的1.6亿，而我在自己的电脑上直接运行官方的基准测试，也达到了接近4000万的ops），并且其具有原生的C#实现，非常适合在当前项目中使用。

状态码的选择

选择302临时重定向，因为301永久重定向的结果会被浏览器缓存，导致无法应对后续的访问信息（访问数，User-Agent等）统计，短链过期等需求。

总览

经过上述的技术选型，我们可以直接得到一个简单的构建短链请求的流程图：

代码实现

https://github.com/KamenRiderKuuga/UrlShorter

1. What is the difference between a Hash Function and a Cryptographic Hash Function? ↩

2. 像MD5这样的算法，虽然已经被证实存在安全缺陷，但是由于它的初衷是为了安全，目前仍然愿意将其归类为加密HASH函数，因为是否会在一种HASH函数中出现这种情况是很难预测的 ↩

3. 参考了漫谈非加密哈希算法，xxHash#benchmarks ↩