如果平时留意，各种业务短信上的链接也会变成极短的:

这个极短的URL就是一个短链接。

为什么需要URL短链接

URL短链接用于为长URL创建较短的别名。我们称这些缩短的别名为“短链接”；当用户点击这些短链接时，会被重定向到原来的网址；。短链接可以在显示、打印和发送消息时节省大量的空小时。

例如，如果我们通过sourl缩短以下URL:

juejin.cn/user/211951…

我们可以得到一个简短的链接:

sourl.cn/R99fbj

缩短的URL几乎是实际URL大小的三分之一。

URL缩写通常用于优化设备之间的链接，跟踪单个链接以分析受众，衡量广告活动的效果，或隐藏相关的原始URL。

如果你以前没有用过sourl，你可以试着创建一个新的url短链接，花些时间浏览他们服务提供的各种选项。可以帮助你更好的理解这篇文章。

系统的要求和目标

在完成一个功能或者开发一个系统的时候，先确定系统的定位和要达到的目标是一个很好的习惯，可以让你在设计开发的过程中有更清晰的思路。

我们的短链路系统应满足以下要求:

功能要求:

给定一个URL，我们的服务应该为它生成一个简短且唯一的别名，称为短链接。这个链接应该足够短，以便复制并粘贴到应用程序中。

当用户访问短链接时，我们的服务应该将他们重定向到原始链接；

用户应该能够有选择地为他们的URL选择一个自定义的短链接；

链接可以在指定的时间间隔后过期，用户应该能够指定过期时间。

非功能性需求:

系统必须高度可用。如果我们的服务被关闭，所有的URL重定向将开始失败。

URL重定向的延迟应该足够小；

短链接应该是不可预测的。

扩展要求:

支持和统计，比如短链接的访问次数；

其他服务也应该能够通过RESTAPI访问我们的服务。

容量要求和限制

我们的系统会有很大的流量。将有一个短链接的读取请求和一个创建短链接的写入请求。假设阅读和写作的比例是100: 1。

估计访问次数:

假设我们每月有5亿个新的短链接，读写比为100: 1，我们可以预计同时有500亿次重定向:

00 * 5亿= >五百亿

我们系统的QPS(每秒查询次数)是多少？每秒新增的短链接有:

5亿/(30天* 24小时* 3600秒)≈ 200个URLs秒

考虑到100: 1的读写比率，每秒的URL重定向将为:

100 * 200个网址/秒= 20000个/秒

存储估计值:

假设我们将每个URL缩短请求(以及相关的缩短链接)存储5年。因为我们预计每个月会有5亿个新的URL，所以我们预计存储的对象总数为300亿:

5亿* 5年* 12月= 300亿

假设每个存储的对象大约有500字节(这只是一个估计)。我们将需要15TB的总存储空间:

30亿* 500字节≈15TB

带宽估计:

对于写请求，因为我们预计每秒会创建200个新的短链接，所以我们服务的总传入数据是每秒100KB:

200 * 500字节≈100 kb/秒

对于读取请求，估计每秒将有大约20，000次URL重定向，因此我们服务的总传出数据将为每秒10MB:

20000 * 500字节≈10 MB/秒

内存估计:

对于一些热门网址，为了提高访问率，我们需要缓存。我们需要多少内存来存储它们？如果按照“28”的原则，即20%的网址产生80%的流量，我们要缓存这20%的热门网址。

因为我们每秒有20，000个请求，所以我们每天会收到17亿个请求:

2000 * 24 * 3600≈17亿

要缓存其中20%的请求，我们需要170 GB的内存:

17亿* 0.2 * 500字节≈ 170GB

这里需要注意的一点是，因为会有很多来自同一个URL的重复请求，所以我们的实际内存使用量可能不会达到170 GB。

综合来看，假设每月新增5亿个网址，读写比为100: 1，我们估算的数据大致如下:

类型

测定值

添加短链接

200/秒

短链接重定向

20000/秒

输入数据

100千字节/秒

传出数据

10 MB/秒

5年存储容量

15 TB

内存容量

170 GB

系统API设计一旦我们最终确定了需求，就可以定义系统API了。这里，我们需要清楚地定义我们的系统可以提供什么服务。

我们可以使用REST API来公开我们服务的功能。以下是用于创建和删除URL的API的定义:

创建短链接接口

Creatureurl (API _ dev _ key，original _ URL，custom _ alias = none，user _ name = none，expire _ date = none) 参数列表:

Api_dev_key:分配给注册用户的开发者密钥，根据该密钥可以限制用户创建的短链接数量；

Original_url:需要生成短链接的原始URL；

Custom_alias:用户定义的URL名称；

User_name:可用于编码的用户名；

Expire_date:短链接的到期时间；

返回值:

成功的短链接生成将返回短链接URL；否则，将返回一个错误代码。

删除短链接接口

删除URL (API _ dev _ key，url_key)其中URL _ key是要删除的短链接字符串；成功删除将返回删除成功。

如何发现和防止短链接被滥用？

恶意用户可以通过使用当前设计中的所有URL键来攻击我们。为了防止滥用，我们可以通过用户的api_dev_key来限制用户。每个api_dev_key可以在每个时间段内限制创建一定数量的URL和重定向(可以根据开发者key设置不同的持续时间)。

数据模型设计

在开发之前完成数据模型的设计将有助于理解各种组件之间的数据流。

我们的短链接服务系统中的数据具有以下特征:

需要存储十亿条数据记录；

存储在中的每个对象都很小(不到1k)；

除了存储哪个用户创建了URL之外，记录之间没有任何关系；

我们的服务将有大量的读取请求。

我们需要创建两个表，一个用于存储短链接数据，一个用于存储用户数据；

应该使用怎样的数据库？

因为我们期望存储数十亿行，并且我们不需要使用对象之间的关系——所以像mongoDB和Cassandra这样的NoSQL存储是更好的选择。选择NoSQL也更容易扩展。

基本系统设计与算法

现在要解决的问题是如何为一个给定的URL生成一个简短且唯一的密钥。有两种主要的解决方案:

编码原始URL

提前离线生成密钥

对原URL编码

您可以计算给定URL的唯一哈希值(例如，MD5或SHA256等。).然后可以对散列进行编码以供显示。编码可以是base36([a-z，0-9])或base62([a-z，A-Z，0-9])。如果加上+和/，就可以用Base64编码了。需要考虑的一个问题是短链接的长度应该是多少？6、8或10个字符？

使用Base64编码，一个6个字母长的键将生成64.6≈687亿个可能的字符串；使用Base64编码，一个8个字母的密钥将产生64 8 ≈ 281万亿个可能的字符串。

根据我们估算的数据，687亿对我们来说足够了，所以可以选择6个字母。

如果我们使用MD5算法作为我们的散列函数，它将产生一个128位的散列值。经过Base64编码后，我们将得到一个超过21个字符的字符串(因为每个Base64字符编码一个6位哈希值)。

现在，每个短链接只有6(或8)个字符空，那么我们如何选择我们的密钥呢？

我们可以将前6个(或8个)字母作为关键字，但这会导致重复链接；为了解决这个问题，我们可以从编码的字符串中选择一些其他的字符或者交换一些字符。

我们的解决方案存在以下问题:

如果多个用户输入同一个网址，可以得到同一个短链接，这是不应该允许的。

如果URL本身的某些部分是URL编码的，该怎么办？例如，除了url编码，https://juejin.cn/user/2119514147536087和https://juejin.cn/user/2119514147536087%3Fid%3D是一样的。

解决方案:

我们可以给每个输入URL附加一个递增的序列号，使其唯一，然后生成它的散列。但是，我们不需要将这个序列号存储在数据库中。这种方法可能存在的问题是序列号增加会导致溢出。递增的序列号也会影响服务的性能。

另一个解决方案可能是将用户ID附加到输入URL上。但是，如果用户还没有登录，我们将要求用户选择一个唯一的密钥。即便如此，也可能存在冲突，需要不断地生成冲突，直到获得唯一的密钥。

离线生成秘钥

可以有一个独立的密钥生成服务，我们称之为KGS(密钥生成服务)。它预先生成随机的六个字母的字符串，并将它们存储在数据库中。每当我们想要生成一个短链接时，我们就去KGS获取一个生成的密钥并使用它。这种方法更简单快捷。我们不仅不需要编码URL，而且也不必担心重复或冲突。KGS将确保插入数据库的所有密钥都是唯一的。

会有并发问题吗？

密钥一旦被使用，就应该在数据库中进行标记，以确保不会被再次使用。如果多个服务器同时读取密钥，我们可能会遇到两个或更多的服务器试图从数据库中读取同一个密钥。如何解决这个并发问题？

kg可以使用两个表来存储密钥:一个表存储未使用的密钥，另一个表存储所有使用过的密钥。

一旦KGS向其中一个服务器提供了密钥，它就可以将它们移动到已用密钥表中；您可以总是在内存中保存一些键，以便在服务器需要时快速提供它们。

为简单起见，一旦KGS将一些密钥加载到内存中，它就可以将它们移动到Used密钥表中。这确保了每台服务器都获得一个唯一的密钥。

如果KGS在所有加载的密钥被分配给一个服务器之前重启或者死亡，我们会浪费这些密钥，考虑到我们有很多密钥，这是可以接受的。

还必须确保KGS不会向多个服务器提供相同的密钥。因此，在将密钥提供给服务器之前，需要同步或锁定kg将密钥加载到内存并将密钥移动到used表的操作。

KGS中是否存在单点故障？

为了解决KGS的单点故障，我们可以使用KGS的备份副本。当主服务器崩溃时，备用服务器可以接管生成和提供密钥。

每个应用服务器可以用一些密钥代替吗？

是的，这可以减少接触公斤。但是，在这种情况下，如果应用服务器在使用所有密钥之前就死亡了，我们最终会丢失这些密钥。但是因为我们有大量的键，这是可以接受的。

如何完成键搜索？

我们可以在数据库中查找关键字来获得完整的URL。如果它存在于数据库中，一个“HTTP302 Redirect”状态被发送回浏览器，存储的URL被传递到请求的Location字段。如果密钥不在我们的系统中，它将发出HTTP 404 Not Found状态或将用户重定向回主页。

数据分区和复制

因为我们要存储十亿的URL数据，一个数据库节点可能达不到存储要求，单个节点无法支持我们的读取需求。

因此，我们需要开发一个分区方案，将数据分区存储在不同的数据库服务中。

基于范围的分区:

我们可以根据短链接的首字母将URL存储在不同的分区中。因此，我们把所有的字母& # 39；a/a & # 39；第一个URL保存在一个分区中，以字母' b/'B/b '开头的URL保存在另一个分区中，依此类推。这种方法称为基于范围的分区。我们甚至可以将一些不常用的字母合并到一个数据库分区中。

基于哈希值的分区:

在这个方案中，我们对要存储的对象进行哈希运算。然后，我们根据哈希结果计算使用哪个分区。在我们的例子中，我们可以使用短链接的哈希值来确定存储数据对象的分区。

哈希函数将URL随机分配给不同的分区(例如，哈希函数总是可以将任何“键”映射到[1...256]，它将代表我们存储对象的分区。

这种方法可能会导致部分分区数据过载，可以通过一致哈希算法解决。

缓存

我们可以缓存经常访问的热点网址。缓存方案可以使用现成的解决方案，如memcached、Redis等。因此，应用服务器可以在搜索数据库之前快速检查缓存是否有所需的URL。

如果确定了缓存容量？

您可以从每天20%的流量开始，并根据客户端的使用模式调整所需的缓存服务器数量。如上所述，我们需要170 GB的内存来缓存20%的日常流量。几个较小的服务器可以用来存储所有这些流行的网址。

你选择哪种淘汰策略？

剔除策略是指当缓存满了，要用更热的URL替换链接怎么办？

最近最少使用(LRU)是我们系统的合理策略。在这个策略下，我们首先丢弃最近最少使用的URL；我们可以使用短链接或短链接的哈希值作为键或类似数据结构的哈希表来存储URL和访问时间。

如何更新缓存？

每当出现缓存缺失，我们的服务器就会命中后端数据库。每当这种情况发生时，我们可以更新缓存并将新条目传递给所有缓存的副本。每个副本都可以通过添加新条目来更新其缓存。如果副本已经有这个条目，它可以简单地忽略它。

负载均衡

您可以在系统的三个位置添加负载平衡层:

在客户端和应用服务器之间；

在应用服务器和数据库服务器之间；

在应用服务器和缓存服务器之间。

可以使用一种简单的循环调度方法在后端服务器之间平均分配传入的请求。这种负载平衡方法实现简单，不会带来任何开销。这种方法的另一个优点是，如果服务器崩溃，负载平衡可以使它退出轮换，并停止向它发送任何流量。

循环调度的一个问题是它没有考虑服务器过载。因此，如果服务器过载或运行缓慢，它不会停止向服务器发送新请求。为了处理这个问题，可以采用一种更智能的解决方案，定期查询后端服务器的负载，并根据负载调整流量。

数据清除策略

数据应该永久保存，还是应该擦除？如果到了用户指定的过期时间，短链接怎么办？

继续扫描数据库以清除过期数据。

懒惰删除策略

如果选择连续删除过期链接，会给数据库带来很大压力。可以慢慢删除过期链接，用懒人的方式清理。确保只删除过期的链接。虽然一些过期的链接可以在数据库中保存更长时间，但它们永远不会返回给用户。

每当用户试图访问过期的链接时，我们可以删除该链接并向用户返回一个错误。

的单独清理服务可以定期运行，从存储和缓存中删除过期的链接；

该服务应该是非常轻量级的，并且计划只在预期的用户流量较低时运行；

我们可以为每个短链接设置默认的过期时间(比如两年)；

删除过期的链接后，我们可以将密钥放回KGS数据库以供重用。

结语

以上是开发短链接服务系统要做的各个方面。可能还有一些小黑没有考虑到的地方。欢迎在留言区交流！如果对你有一点帮助，请给我一个赞，鼓励我。

作者:小黑说Java
链接:https://juejin.cn/post/7034325565431611406