需求描述
撰写两个 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
映射方案,可考虑策略模式,实现多种策略实现。
优化映射策略的安全性。加入随机码、扰动等等