浅谈短链接设计

发表于 更新于 分类于 阅读次数：

浅谈短链接设计

文章主要框架

  • 短链接介绍
  • 基本原理和设计
  • 功能优化和附属功能
  • 总结
  • 参考资料

前言

为什么会写这篇文章

前段时间，客户提出了一个需要将二维码链接放在短信里发送给用户的需求。依照最简单的思路即长链hash后转62进制短链，很快实现了功能便交付了，需求的并发量也不高，并没有产生什么性能问题。如今，再回想一下当时设计的功能，还有诸多可以改进的地方，这里就写一篇文章把想到的点拿出来讨论一下。

为什么要用短链接

当我们在日常生活和工作中分享链接时，长链接可能会带来一些不便。这种不便主要体现在以下几个方面：

  1. 便于分享： 长链接通常包含大量字符，不仅难以记忆，而且在一些字符限制的场景（比如微博、短信）中可能无法完整显示。生成短链接可以有效缩短字符长度，使得分享更加方便和顺畅。
  2. 提升美观性： 在一些场合，长串字符的链接可能显得杂乱，不够美观。通过转换成短链接，我们可以使得外观更整洁，更符合审美，从而提升用户体验。
  3. 易于记录： 无论是口头传递还是手写记载，短链接更容易被记录和传递。人们可以迅速记住短链接，而无需费心记忆冗长的字符序列。
  4. 监测和统计： 使用短链接服务通常可以提供链接点击统计和监测功能，帮助发布者了解链接的点击情况、受众行为等信息。这对于推广、营销和数据分析非常重要。
  5. 防止链接截断： 在一些应用中，长链接可能因为字符数限制而被截断，导致链接无法正常跳转，如短信内容过长导致分两条短信发送，此时链接正好被截断便无法直接点开。通过使用短链接，可以规避这个问题，确保链接的有效性。

基本原理和功能设计

哈希算法——生成短链

首先说一下通用的需求：

  1. 短链接的内容包括两个部分：固定域名+短链接参数（n位数字或字母的组合）
  2. 一个长链接唯一对应一个短链接，一个短链接唯一对应一个长链接。

要把长链压缩成短链，大家很容易想到要使用Hash算法，常见的可以使用MD5或SHA算法进行Hash计算，这里我们采用MurmurHash算法。

相比于一些传统的哈希算法，MurmurHash有以下优势：

  1. 速度快： MurmurHash算法设计简单，运算效率高，适用于需要快速生成哈希值的场景。在长链接转短链接的应用中，迅速生成短链接对于用户体验至关重要。
  2. 低碰撞率： 碰撞是指两个不同的输入映射到相同的哈希值的情况。MurmurHash在设计上考虑到了降低碰撞率，使得生成的短链接更有唯一性，减少了因碰撞导致的问题。
  3. 均匀分布： MurmurHash在混合运算时能够更好地保持输入数据的随机性，使得生成的哈希值分布更加均匀。这对于生成短链接时能够提高数字和字母的组合均匀性，避免过于集中的情况。

在长链接生成短链接的应用中，MurmurHash算法的高效性和哈希质量的优良表现使得它成为一个理想的选择。

在生成短链时，考虑到短链的长度，我们使用32位的Hash。32位Hash能生成的不同Hash就有42亿，而6位62进制更是达到了568亿，已经能够满足一定规模的使用。

1
2
3
4
5
6
7
import com.google.common.hash.Hashing;

public String shortenString(String str) {
    long hashLong = Hashing.murmur3_32_fixed().hashBytes(
        (str).getBytes(StandardCharsets.UTF_8)).padToLong();
    ...
}

为了进一步缩短生成的32位Hash值长度，可以将值转换成62进制字符串，即0-9，a-z，A-Z的数字和字符组合。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public String shortenString(String str) {
	...
	// 统一短链接位数为6位，直接加上62^5=916,132,832
	// 由于6位62位数最大可表示62^6-1=56,800,235,583，而32位散列（无符号位）最大为2^32-1=4,294,967,295即使加上62^5也不会超过6位
	hashLong += 916132832;
	return hex10To62(hashLong);
}

/**
 * 六十二进制字符表
 */
private static final char[] CHAR_SET = "qwertyuiopasdfghjklzxcvbnm0123456789QWERTYUIOPASDFGHJKLZXCVBNM"
    .toCharArray();

/**
 * 十进制 -> 六十二进制
 *
 * @param num 需要转换的十进制数
 * @return 六十二进制字符串
 */
public static String hex10To62(long num) {
	StringBuilder result = new StringBuilder();
	while (num > 0) {
		result.append(CHAR_SET[(int) (num % 62)]);
		num /= 62;
	}
	return result.reverse().toString();
}

这样生成的短链接可以使用更短的字符表示相同的信息，同时又能够包含数字和字母，增强了短链接的可读性。

采用了哈希算法，那么一定会带来哈希冲突的问题。如果在极小的概率下发生了哈希冲突，我们应该如何处理？

回答这个问题之前，我们再看一眼通用需求：长短链接一一对应。既然需要根据生成出来的短链接跳转到长链接，那么这个关联关系我们是肯定要保存下来的。这边展示一下MySql表结构：

1
2
3
4
5
6
7
CREATE TABLE `short_url_mapping` (
  `id` bigint(20) NOT NULL,
  `short_url` varchar(10) CHARACTER SET utf8 NOT NULL,
  `raw_url` varchar(500) CHARACTER SET utf8 NOT NULL,
  `generate_date` datetime NOT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4

每当生成一条短链，我们把短链接和长链接的对应关系保存到这张表中，于是在解决哈希冲突的时候就有了一下设计思路：

  1. 根据长链接在表中查询数据，如果查到了数据，那么直接返回短链接。
  2. 如果库里不存在，将长链接进行哈希之后得到短链。
  3. 根据短链接在表中查询数据，如果查到了数据，那么将长链接加上一个固定字符串"_su_"后重新哈希，直到短链接不存在，返回该短链接。要知道本身哈希冲突的概率就很低，所以使用循环判断是可以接受的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 判断长链接是否存在
ShortUrlMapping shortUrlMappingEntity = shortUrlMappingMapper.findByRawUrl(url);
if (shortUrlMappingEntity != null) {
    return shortUrlConfiguration.getUrlPrefix() + shortUrlMappingEntity.getShortUrl()
}
// 生成短链接
String result = shortenString(url);
StringBuilder urlBuilder = new StringBuilder(url);
while (shortUrlMappingMapper.findByShortUrl(result) != null) {
    urlBuilder.append(shortUrlConfiguration.getSalt());
    result = shortenString(urlBuilder.toString());
}
// 入库数据
shortUrlMappingEntity = new ShortUrlMapping();
shortUrlMappingEntity.setRawUrl(url);
shortUrlMappingEntity.setCalculateUrl(urlBuilder.toString());
shortUrlMappingEntity.setShortUrl(result);
shortUrlMappingEntity.setGenerateDate(new Date());
shortUrlMappingEntity.setLimitTimes(limitTimes);
shortUrlMappingEntity.setExpireDate(expireDate);
shortUrlMappingEntity.setVisitTimes(0L);
shortUrlMappingMapper.insert(shortUrlMappingEntity);

请求重定向——跳转长链

在生成了短链之后，用户就要使用短链来访问并最终请求到所需要的长链。

很简单，获取到短链接之后根据短链接去库里查询对应长链接，然后给浏览器返回重定向响应，浏览器请求到新的长链接地址。这里使用302临时重定向，虽然会导致每次请求都请求短链接服务器，但是可以便于数据统计。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
@RequestMapping("/s/{shorturl}")
public String getRawUrl(HttpServletResponse response, @PathVariable("shorturl") String shorturl) throws IOException {
    Assert.hasText(shorturl, "传入短链不能为空");
    ShortUrlServiceDto shortUrlServiceDto = shortUrlService.getRawUrl(shorturl);
    if (shortUrlServiceDto.getCode() == ShortUrlServiceDtoEnum.ShortUrlServiceCode.SUCCESS.getCode()) {
        // 返回重定向
        response.sendRedirect(shortUrlServiceDto.getUrl());
        return "";
    }
    return shortUrlServiceDto.getMsg();
}

public ShortUrlServiceDto getRawUrl(String shortUrl) {
    // 从库中查询短链
    ShortUrlMapping frameShortUrl = shortUrlMappingMapper.findByShortUrl(shortUrl);
    if (frameShortUrl != null) {
        result = new ShortUrlValue(frameShortUrl);
    }
    if (result == null) {
        return new ShortUrlServiceDto(ShortUrlServiceCode.FAIL.getCode(), null, "链接不存在");
    }
    return new ShortUrlServiceDto(ShortUrlServiceCode.SUCCESS.getCode(), result.getRawUrl(), "");
}

小结

完成了这两个功能，短链接系统的雏形就已经完成了，达到了“能用”这个水平。如果要想满足“好用”的条件，那么还需要更多的优化。

功能优化和附属功能

高可用

Redis缓存

Redis缓存是最容易想到的缓存方式也是实现起来比较容易的缓存方式。

我们想象一下两种常用使用场景：一种是生成短链之后马上分享给朋友看，一种是生成短链之后到特定时间打开使用。后者的使用时间是不确定的，而前者我们可以使用Redis来做缓存加快响应速度并减少数据库压力。

生成短链接时，如果开启Redis缓存，那么同时把短链接数据插入Redis。

1
2
3
4
// 如果启用redis那么往redis中也插入数据
if (shortUrlConfiguration.isUseRedis() && redisTemplate != null) {
    redisTemplate.opsForValue().set(REDIS_KEY_PREFIX + REDIS_KEY_SPLIT + result, new ShortUrlValue(url, expireDate, limitTimes).getValueString(), shortUrlConfiguration.getRedisExpireTimeByMinute(), TimeUnit.MINUTES);
}

短链接请求时，先去Redis中获取数据，如果Redis中没有数据，那么再从数据库中查询。

1
2
3
4
// 如果启用redis那么从redis取
if (shortUrlConfiguration.isUseRedis() && redisTemplate != null) {
    result = new ShortUrlValue((String) redisTemplate.opsForValue().get(REDIS_KEY_PREFIX + REDIS_KEY_SPLIT + shortUrl));
}

每次短链接请求后我们认为该用户可能还会再次请求，所以可以重新往Redis中插入该数据或延长过期时间。

MySql读写分离

由于短链接的使用场景大多是读多写少的情况，并且Redis中不可能保存所有数据，所以在请求量很大情况下需要对数据做高可用。

OpenResty代替Java

整个系统其实根据“基本原理和功能设计”中所说可以分为两个部分，一个是生成短链接，可以使用Java编写，支持增加各种扩展功能，另一个是短链接跳转长链接，这个可以用OpenResty替代Java。

OpenResty是一个基于Nginx与Lua的高性能Web平台，对于只需要实现查询缓存、查询数据库功能绰绰有余，并且在性能上相比Java提升不少。

布隆过滤器

布隆过滤器可以拦截垃圾请求。如果有人恶意使用不存在的短链接请求服务器，那么所有请求都将不会在缓存命中，需要去数据库进一步校验是否存在，此时使用布隆过滤器过一次筛选就显得非常有必要了。

布隆过滤器能够保证布隆过滤器中不存在的数据，一定不存在；布隆过滤器中存在的数据不一定真实存在。也就是说，有效的短链接一定能通过布隆过滤器，并且在参数设置妥当的情况下能够大概率拦截无效的链接。同时，根据布隆过滤器的原理，使用比特位存储能够大量节约内存，可以将全部数据保存在过滤器中。

CDN加速

在写这篇文章的时候去网上调研各短链接服务商提供的功能中发现了这个功能，但是不太清楚是怎么实现的。猜测是将短链接访问重定向到一个html页面，然后加载被cdn加速的文件，这个文件中预先写好了短链接和长链接的对应关系。如果有了解的朋友可以讨论一下。

其他功能

链接有效期

每一个链接可以设置自己的有效期，如果有效期已过，那么跳转过期页面即可。

有效使用次数

每一个链接可以设置自己的有效次数，如果有效次数耗尽，那么跳转次数不够页面即可。

统计功能

大数据时代做统计功能非常有必要，所有链接的使用情况例如点击次数、访问设备等可能都是使用短链接用户关心的内容。在我写这篇文章的时候去网上调研了多个短链接生成服务商所提供的服务，每一个都有统计分析功能。

短链跳转不同长链

在基本原理和功能设计中我们假设的需求是长链接和短链接一一对应，其实短链也可以根据访问地区、访问设备型号、访问浏览器等做不同的跳转。

一个长链生成不同短链

某一个短链失效了，是需要新生成一个短链还是沿用原来的短链并增加有效期（或有效次数）？在打破了长链接和短链接一一对应的限制后，似乎代码中需要兼容的情况变得非常多。如果需要考虑这种情况，那么在根据已有长链接生成短链的时候就不需要强制使用库中存在的那一条数据了，可以灵活的让用户选择使用新的还是旧的。

总结

这篇文章主要是根据之前项目上已经实现的需求编写的，回顾当时的需求设计还有很多可以优化的地方。在网上找了许多短链接服务商的服务内容，查找相关资料，看了几个开源的项目的代码之后，觉得有必要把想到的内容记录一下，等有空的时候把这些想法动手实现一下，那时候就是一篇浅谈短链接项目实战了。

项目地址：short-url

参考资料

七喜阳光/短链接(https://gitee.com/www.iamooc.com/short-url)

短 URL 系统是怎么设计的？(https://www.zhihu.com/question/29270034)