唯's Blog

笔者是一个热爱编程的 Java 程序员。

0%

短链接设计

需求描述

撰写两个 API 接口:

  • 短域名存储接口:接受长域名信息,返回短域名信息

  • 短域名读取接口:接受短域名信息,返回长域名信息。

限制:

  • 短域名长度最大为 8 个字符

  • 采用SpringBoot,集成Swagger API文档;

  • JUnit编写单元测试, 使用Jacoco生成测试报告(测试报告提交截图);

  • 映射数据存储在JVM内存即可,防止内存溢出;

设计思路

数据存储

  • 由于项目要求映射数据存储在JVM内存即可,防止内存溢出。因此本次设计为求简化,采用HashMap进行存储(考虑并发可使用ConcurrentHashMap)。

  • 由于涉及从短url获取长url、从长url获取短url的双向操作,因此本项目采用两张哈希表存储,即一张表通过长域名查询存储短域名,另一张表实现短域名读取长域名时。

映射算法

生成短链接的本质是要确认一对短链接和长链接的唯一 KV 关系,也就是所以常见的生成方式有两种:Hash 和 自增 ID。 本项目默认采用自增ID方式。

Hash

此方案是通过 Hash 算法将任意长度的长链接计算输出得到一个固定长度的短码。好处就是实现简单,安全性高。但缺点也显而易见,再好的 Hash 算法也无法解决碰撞问题,且随着数量的增大碰撞概率也随之增大,所以此方案难点是如何处理碰撞冲突问题。

自增ID

自增 ID 可以确保全局唯一性,且市面上已有成熟的实现方案:

  • UUID

  • 数据库自增

  • Redis生成

  • 分布式算法(如雪花)

短链接一般由大小写字母和数字组成,共有 26+26+10 = 62 个字符。在得到一个十进制 Long 型 ID 后,可以通过 62 进制转成字符串。 但如果仅简单使用自增ID,会带来严重的安全问题,因为生成的短链接可以猜测和遍历。 后续可考虑以下方案提高安全性:

  • 可以对 ID 进行跳码计算,防止猜测

  • 结合长链接等信息进行安全位计算,并打乱顺序,防止遍历

  • 同时支持校验,防止恶意尝试直接回落 DB

本次方案设计中,为简化,采用项目中的自增ID实现。步骤如下:

  • 通过长url生成对应的ID

  • 将其转化为62进制的字符串。

后续优化

  • 存储采用redis + mysql

  • 分布式ID/数据库自增ID

  • 映射方案,可考虑策略模式,实现多种策略实现。

  • 优化映射策略的安全性。加入随机码、扰动等等