短链系统

予早 2025-02-21 01:08:24
Categories： Tags：

短链接系统

https://blog.csdn.net/gu_wen_jie/article/details/119250339

https://www.51cto.com/article/802019.html

https://mp.weixin.qq.com/s?__biz=Mzg3NjU1NzM1Mw==&mid=2247490066&idx=1&sn=d133a358dbc79f2ca9293dae57f31532

2.1 短链接生成算法

短链接的生成是短链系统

读写QPS及存储分析评估，以微博场景为例：

微博，产品定位是微型博客，曾经对发文有长度限制，不超过140字，所以对长链接不友好，引入短连接服务，随后由于短链接被用于违禁内容网站跳转的泛滥，由于平台监管责任，微博引入白名单机制，仅允许指定域名可跳转，并取消了发文长度140字限制。

微博 2024 年第二季度财报显示，其月活跃用户数（MAU）达到5.83亿，平均日活跃用户数（DAU）为2.56亿。

日活用户按照3亿计算，假定平均每个用户每天发1个帖子，每10个帖子包含一个短链接，假定平均每个用户每天点击3个短链接（不是浏览帖子，要点击短链接跳转）

[!TIP]

读多写少场景，读写比例受长链接业务场景影响，例如短链接平台专用于电商促销，用户群体更大，这种读写比例在1000:1以及更高，若短链接仅用于一般转换，用户群体不大，这样读写比例在10:1甚至更低，当然若是综合短链接平台，各种短链接目的差异很大，热点短链接和非热点短链接就会存在明显差异

QPS 分析

写

平均 QPS：$300M \times 1 \div 10 \div 86400 \approx 347.22$

中位 QPS：

90% QPS：

峰值 QPS：按平均十倍预估，3472.22

读：

平均 QPS：$300M \times 3 \div 86400 \approx 10416.67$

中位 QPS：

90% QPS：

峰值 QPS：按平均十倍预估，104166.67

网络带宽分析

假定长链接平均大小为512B，则：

写：

平均占用：$347.22/s \times 512B = 173.61KB/s$

峰值占用：按峰值 QPS预估，1.70MB/s

读：

平均占用：$10416.67/s \times 512B \approx 5.09MB/s$

峰值占用：按峰值 QPS预估，50.86MB/s

存储分析

日

数据条数：$300M \times 1 \div 10 = 30M$，一天等同于一张MySQL表

数据存储占用：$300M \times 1 \div 10 \times 512B \approx 14.30GB$

月

季

年

可以先规划5年，五个数据库，每个数据库62 * 62 张表，每张表容纳3000万左右数据，另外要考虑用户数量增长，可以额外增加几台数据库

内存缓存分析

一天中所有访问过的短链接不超过当前读接口访问次数$900M$，基于28原则，20%的数据产生80%的流量，反之，20%的流量由80%的数据产生，20%的流量为$900M \times 0.2 =180M$，假定20%的流量中访问的每个短链接都不同（按最多估计，实际上会有很多重复，只是不如另外20%重复的多），即80%的短链接最多为$180M$个，则贡献了80%流量的20%短链接数量最多为$180M \div 4 = 45M$，假定每个短链接相关信息占用512B，则总内存占用量不超过$45M \times 512B = 21.46GB$内存

由2、3 分析可知，并不需要分布式或者 sharding，支持 2k QPS，一台 SSD MySQL 即可。

读写特点：读多写少，大量用户情况下，读写接口均要求高并发

好的，大体功能定了

整体目的，是通过短链接项目创建我的一个开发环境，建立docker环境，熟悉go语言生态

CREATE TABLE `url_map`
(
    `id`               BIGINT UNSIGNED NOT NULL PRIMARY KEY AUTO_INCREMENT COMMENT '主键',
    `short_url`        VARCHAR(32)     NOT NULL COMMENT '短链URL',
    `long_url`         VARCHAR(768)    NOT NULL COMMENT '长链URL',
    `short_url_digest` VARCHAR(128)    NOT NULL COMMENT '短链摘要',
    `long_url_digest`  VARCHAR(128)    NOT NULL COMMENT '长链摘要',
    `compression_code` VARCHAR(16)     NOT NULL COMMENT '压缩码',
    `description`      VARCHAR(256) COMMENT '描述',
    `url_status`       TINYINT         NOT NULL DEFAULT 1 COMMENT 'URL状态,1:正常,2:已失效',
    `create_time`      DATETIME        NOT NULL DEFAULT CURRENT_TIMESTAMP COMMENT '创建时间',
    `edit_time`        DATETIME        NOT NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP COMMENT '更新时间',
    `creator`          VARCHAR(32)     NOT NULL DEFAULT 'admin' COMMENT '创建者',
    `editor`           VARCHAR(32)     NOT NULL DEFAULT 'admin' COMMENT '更新者',
    `deleted`          TINYINT         NOT NULL DEFAULT 0 COMMENT '软删除标识',
    `version`          BIGINT          NOT NULL DEFAULT 1 COMMENT '版本号',
    UNIQUE uniq_compression_code (`compression_code`),
    INDEX idx_short_url (`short_url`),
    INDEX idx_short_url_digest (`short_url_digest`),
    INDEX idx_long_url_digest (`long_url_digest`)
) COMMENT 'URL映射表';

短链接系统是什么？

一个将长链接转换为短链接，访问短链接就可以达到与长链接相同效果的系统，同时提供了一些短链接的访问统计。

短链接系统用于解决什么问题？

短链系统的核心功能是将一个长链接转变为一个短链接。

短链接与长链接的在浏览器中最终都会访问到同一个页面，但短链接的价值在于：

短链接系统基本原理

短链系统基本原理

短链系统本身是一个”哈希表“，第一步是根据长链接生成一个短链接，然后将短链接到长链接的映射存入”哈希表“。客户端访问短链接时会请求到短链系统，然后短链系统通过短链接查找到长链接，给客户端返回长链接，客户端访问长链接最终获取到目的资源。

以上涉及两个核心接口，一读一写：

  1. 通过短链接获取长链接接口，读接口
  2. 短链接生成接口，写接口

下面解决这两个问题

短链接获取及跳转方案，对应读接口

一句话总结，基于HTTP的重定向。

采用302

短链接生成及存储方案，对应写接口

给定一个长链接，要对应生成一个短链接。

短链接一定是全局唯一的，因为访问短链接要唯一重定向到一个长链接，短链接不唯一就会映射到多个长链接，这与业务功能不符。

反之，长链接需要保证全局唯一吗？长链接不唯一，也就是多个短链接可以跳转到同一个长链接，这并不与短链接基本功能冲突，所以，可以让长链接不唯一，若需要保证长链接唯一，那么就需要为长链接增加额外约束和校验。

当生成的短链接到长链接映射足够多时，单表会有性能和存储上的瓶颈，这时需要进行分库分表，引入分库分表后如何保证短链接唯一（给定一个短链接就可以唯一确认某库某表某条记录），以及长链接唯一（在所有库的所有表中，同一个长链接最多仅允许存在一个）呢？

总结，短链接生成及存储方案需要针对如下场景展开：

单表存储：必须实现短链接唯一性约束，可选长链接唯一性约束

多表存储：必须实现短链接唯一性约束，可选长链接唯一性约束

单表场景

单表场景下短链接生成及存储方案关键点在于生成方案上

短链接生成方案

  1. 长链接哈希方案
  2. 唯一自增ID方案

长链接哈希方案

将长链接由哈希函数生成的哈希值作为压缩码，短链系统域名+压缩码即为短链接

这里哈希函数的作用在于将长链接哈希为短的串，分析如下：

  1. 是否需要双向映射，长链接变为短链接，然后短链接还可以还原为长链接，不必，因为长变短一定会导致信息载体变少，会出现不同长链接计算出相同短链接的情况，此时无法双向映射，双向映射就是加密算法，加密算法需要相比于单向映射更加多的计算资源消耗，有损接口性能。整体上，使用纯粹的单项映射，及哈希函数即可
  2. 前面提到，由于长链接哈希为短链接，会出现哈希碰撞问题，这个不可避免，所以哈希函数应尽可能保证哈希函数碰撞率低
  3. 哈希函数应当有着比较高的性能，不必向加密算法一样是双向映射，也不必像md5一样做信息摘要
  4. 对于相似的长链接能保证哈希结果均匀分布

总结，使用哈希函数就行，碰撞率低点、性能高点、哈希结果均匀一点即可，当前最佳实践为 MurmurHash 哈希算法。

唯一自增ID方案

直接由ID生成器生成唯一ID，将唯一ID作为短链接。

ID生成方案：

分布式id天然可以防止id重复，根据分布式id，在一些非常极端情况下会重复，这里可以做一次重试（当然直接报错也可以）

单表实现方案

单表，短链接唯一，长链接不唯一

单表，短链接唯一，长链接唯一

方案一：单表，基于长链接哈希方案生成压缩码，压缩码会极低概率碰撞，使用DUPLITE_SLAT 进行加盐规避碰撞，保证短链接唯一性，不保证长链接唯一性，具体过程：

  1. 单表短链接列加唯一索引
  2. 根据长链接计算压缩码，随后插入数据库
    1. 若没有碰撞，成功，接口返回结果
    2. 若碰撞，使用DUPLITE_SLAT在长链接开头加盐，获取加盐后的长链接，返回第2步直至插入数据库成功或累计失败5次

方案二：单表，基于长链接哈希哈希方案生成压缩码，压缩码会已极低概率碰撞，使用DUPLITE_SLAT 进行加盐规避碰撞，保证短链接唯一性，保证长链接唯一性，具体过程：

  1. 单表短链接列加唯一索引，单表长链接额外记录一列md5，对md5列加普通索引（本身应当对长链接加唯一索引，但长链接过长建索引索引会很大，所以额外计算md5列加唯一索引，但md5理论上也会冲突，所以加普通索引）
  2. 根据长链接计算压缩码，随后插入数据库
    1. 若没有碰撞，成功，接口返回结果（因为压缩码也是长链接的一个摘要，压缩码没有碰撞，则长链接一定没有重复）
    2. 若碰撞，对md5加分布式锁，查询所有md5以及长链接内容匹配的数据，如有则表示长链接已存在，接口返回，若没有，则说明长链接不存在，仅仅是压缩码碰撞，使用DUPLITE_SLAT在长链接开头加盐，获取加盐后的长链接，重新插入数据库，重新分析压缩码是否碰撞，直至插入数据库成功或者累计失败5次

方案三：单表，基于唯一自增ID方案生成压缩码，压缩码极难重复，使用重试一次生成的方式规避异常情况，保证短链接唯一性，不保证长链接唯一性，具体过程：

  1. 单表短链接列加唯一索引
  2. 获取唯一自增ID，随后插入数据库
    1. 若ID没有碰撞，成功，接口返回结果
    2. 若碰撞，重试获取一个新的ID，随后插入数据库，再次失败就抛出异常

方案四：单表，基于唯一自增ID方案生成压缩码，压缩码极难重复，使用重试一次生成的方式规避异常情况，保证短链接唯一性，保证长链接唯一性，具体过程：

  1. 单表短链接列加唯一索引，单表长链接额外记录一列md5，对md5列加普通索引（本身应当对长链接加唯一索引，但长链接过长建索引索引会很大，所以额外计算md5列加唯一索引，但md5理论上也会冲突，所以加普通索引）
  2. 根据md5和长链接内容查询数据库中是否存在该长链接
    1. 若存在，接口返回
    2. 若不存在，对md5加分布式锁，再次查询检查是否存在（这里要用当前读）
      1. 若存在，接口返回
      2. 若不存在，获取一个唯一id，然后插入数据库
        1. 若id碰撞，重新获取一个id，重试
        2. 若不碰撞，插入数据库

显然，通过以上分析，单表情况下：

分库分表方案

如果需要分库分表，库和表的 PartitionKey 该如何选择？

**方法一：压缩码取模方案

如下算法，确认库和表的路由规则：

复制

库ID = 短链的 hash值 % 库数量
表ID = 短链的 hash值 / 库数量  % 表数量1.2.

该方法需要根据业务的数据量以及库表设计需要支持几年的数据总量来评估出库的数量和表的数量，另外，因为短链数据绝大多数都是一次性的，所以可以对存量数据进行归档，这样可以解决数据过多需要扩容的问题。

该方案的优缺点：

优点：

缺点：

那么，有没有一种好的方式，可以支持动态扩容而且尽量不牵涉到数据的迁移呢？这里我们就要看第二种方案。

方法二：随机映射方案

通过方法一，我们可以知道，库和表是动态计算出来的，能不能我们固定设置库和表的标号呢？基于这个想法，我们设计了如下的方案，在随机码的前面增加一位代表库的标号，在随机码的后面增加一位代表表的标号，如下图：

这样数据库可以支持62个，每个库的表可以支持62张表，按照每张表 2000万条数据，支持的总数据 = 62 * 62 * 2000w = 768.8亿，如果还不够用的话，那可以在随机码的前后各增加两位来表示库和表，这样就足够了。

实现细节：

预先配置分库分表中库和表的标号，比如：库标号 [0,1,2]，表标号 [0,1,2,3]，通过上面的方法获取到一个随机码之后，然后从库标号 [0,1,2]随机获取一个标号，拼接在随机码的前面作为库标识，从表标号 [0,1,2,3]随机获取一个标号，拼接在随机码的后面作为表，然后在做分库分表路由的时候，分别截取第一位和最后一位作为库和表的路由编号。注意，这里是随机获取，也可以使用轮询算法获取库标号和表标号。

扩容：

假如，需要对库标号 [0,1,2]，表标号 [0,1,2,3]进行扩容，只需要将标号添加进去，比如：库标号[0,1,2,3]，表标号 [0,1,2,3,4,5]，这样原始的数据不需要进行迁移就完成了库容操作。

该方案的优缺点：

优点：

缺点

多表实现方案

多表实现方案基于压缩码生成方案和分库分表方案

多表，短链接唯一，长链接不唯一

方案一：压缩码取模方案+长链接哈希方案，过程：

  1. 每个库每张表对压缩码列加唯一索引
  2. 根据长链接计算压缩码
  3. 根据压缩码及取模运算，获取某库某表，向该表插入数据
    1. 若碰撞，使用DUPLITE_SLAT在长链接开头加盐，获取加盐后的长链接，返回第2步直至插入数据库成功或累计失败5次
    2. 若没有碰撞，接口返回

方案二，随机映射方案+长链接哈希方案，过程：

  1. 每个库每张表对压缩码列加唯一索引
  2. 根据长链接计算压缩码，随机映射到一张表，插入
    1. 若碰撞，随机选择一个表，并且使用DUPLITE_SLAT 进行加盐规避碰撞，重新写入表，直至写入成功或失败3次
    2. 若没有碰撞，接口返回

方案三，压缩码取模方案+唯一自增ID方案（等价于自增id分段），过程：

1. 每个库每张表对压缩码列加唯一索引
2. 获取一个唯一自增ID，取模确定某库某表，插入
 	1. 若碰撞，概率极低，重试一次
 	2. 若无碰撞，接口返回结果

方案四，随机映射方案+唯一自增ID方案，过程：

  1. 每个库每张表对压缩码列加唯一索引
  2. 获取一个唯一自增ID，随机获取一个映射，确定某库某表，插入
    1. 若碰撞，概率极低，重试一次
    2. 若无碰撞，接口返回结果

总结，四种方案都能实现，整体上随即映射方案比压缩码取模方案更灵活，所以在方案二和方案四中选择，随后就取决于长链接哈希和唯一自增id的性能问题，哪个快用哪个（长链接哈希耗时稳定，优化程度有限且大数据量容易造成碰撞，唯一自增ID在分布式环境下需要中间件支持，有网络消耗，优化方案多一点，具体谁快要实际试一下）

多表，短链接唯一，长链接唯一

方案一：压缩码取模方案+长链接哈希方案，过程：

  1. 每个库每张表对压缩码列加唯一索引，每个库每张表增加长链接md5列并加普通索引
  2. 根据长链接计算压缩码
  3. 根据压缩码及取模运算，获取某库某表，向该表插入数据
    1. 若没有碰撞，接口返回
    2. 若碰撞，根据md5及长链接查询是否该表存在长链接
      1. 存在，则接口返回
      2. 不存在，说明压缩码碰撞，使用DUPLICATE_SLAT在长链接开头加盐，获取加盐后的长链接，返回第2步直至插入数据库成功或累计失败5次

方案二，随机映射方案+长链接哈希方案，无法保证长链接唯一，pass

方案三，压缩码取模方案+唯一自增ID方案，无法保证长链接唯一，pass，（可以基于此优化，见方案五）

方案四，随机映射方案+唯一自增ID方案，无法保证长链接唯一，pass

方案五：有方案一获得启示，要想知道长链接是否已存在，需要将长链接md5相同的数据放到一个表才好处理，于是在方案三的基础上可以优化，方案三中，压缩码是唯一自增ID，压缩码取模决定是某库某表，根据前文所述，决定某库某表的值应当与长链接内容相关，所以这里可以考虑使用长链接md5，不过考虑到离散型，不如使用长链接哈希然后取模，随后使用唯一id，这样方案五相当于结合方案一和方案三进行设计

总结

方案一：压缩码取模方案+长链接哈希方案

方案五：长链接哈希取模方案+唯一自增ID方案

本质上两者均使用长链接哈希取模进行分库分表，区别在于一个用长链接哈希一个用唯一自增id，就看哪个性能更高

所以，无论要不要保证长链接唯一，都需要分析长链接哈希和唯一自增哪个性能更高的问题，不过，在两者性能差别不大的情况下，根据奥卡姆剃刀原则，可以考虑使用长链接哈希，因为唯一自增id方案更复杂一些

综上，还是推荐使用多表短链接唯一长链接唯一的方案一。

给出表设计

使用如下表接口存储

CREATE TABLE `short_url_map` (
  `id` int(11) unsigned NOT NULL AUTO_INCREMENT,
  `lurl` varchar(160) DEFAULT NULL COMMENT '长地址',
  `surl` varchar(10) DEFAULT NULL COMMENT '短地址',
  `gmt_create` int(11) DEFAULT NULL COMMENT '创建时间',
  PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

生成短链接后，需要保证数据库中没有这个短链接，所以不妨在surl建立唯一索引，直接往表里面插入，当数据库报错键重复时，可以给短链接拼接一个额外特定字符串即可生成一个新的字符串，整体上，由于哈希函数碰撞率整体比较低，所以这个方案是可以接受的。

另外，当数据量到一定级别时，可以基于布隆过滤器进行优化，

当然，布隆过滤器无法删除，这个可以根据通过离线脚本进行更新

CREATE  TABLE  `short_url_map` (
`id` int(11) unsigned  NOT  NULL AUTO_INCREMENT COMMENT '短链 id', 
`lurl` varchar(10) DEFAULT  NULL  COMMENT '长链', 
`md5` char(32) DEFAULT  NULL  COMMENT '长链md5', 
`gmt_create` int(11) DEFAULT  NULL  COMMENT '创建时间', 
PRIMARY KEY (`id`)) ENGINE=InnoDB  DEFAULT  CHARSET=utf8;

基于本方案，若需要保证长链接唯一，如何操作呢

方案一：md5唯一索引

若在创建短链接时，不允许数据库中长链接重复，可以在长链接上设置唯一索引，但由于长链接过长，会导致唯一索引过长。所以该方案不合适，可以计算长链接md5，然后对md5建立普通索引即可，这里不建立唯一索引的原因是，在非常小概率下会重复，普通索引就够用了

方案二：md5普通索引，每次创建，先查询是否存在，存在就返回，不存在加md5分布式锁，然后再次查询，随后创建

Base62

对生成的哈希值或者自增ID做Base64编码，可以进一步缩小长度。

id可以进行base62编码变的更短

-

采用第二种方案

在分库分表的情况下，由于是基于短链接进行的分库分表，如何保证长链接的唯一呢

方案一，哈希值生成方案+哈希分库分表：可以保证唯一，根据哈希后的库进行插入，重复则有可能说明造成冲突，

方案二，唯一id生成方案+哈希分库分表：不能保证唯一，

缓存方案

有效期功能

字段释义：

base_url：域名

suffix_url：链接除了域名外的后缀

full_url：完整链接

shot_code：当前 suffix_url 链接的短码

expiration_date：失效日期

total_click_count：当前链接总点击次数

expiration_date：当前链接失效时间

缓存方案

个人认为对于几百个G的数据量都放在缓存肯定是不合适的，所以有个折中的方案：将最近3个月内有查询或者有新增的url放入缓存，使用LRU算法进行热更新。这样最近有使用的发概率会命中缓存，就不用走库。查不到的时候再走库更新缓存。

再提高性能

在电商公司，经常有很多活动，秒杀，抢红包等等，在某个时间点的 QPS 会很高

考虑到这种情况，我们引入了 openResty，它是一个基于 Nginx 与 Lua 的高性能 Web 平台，由于 Nginx 的非阻塞 IO 模型，使用 openResty 可以轻松支持 100 w + 的并发数

一般情况下你只要部署一台即可，不过为了避免单点故障，两台为宜，同时 openResty 也自带了缓存机制，集成了 redis 这些缓存模块，也可以直接连 mysql。不需要再通过业务层连这些中间件，性能自然会高不少

增

删

改，暂不支持

查

重定向

多租户方案

分析一下

https://www.c1n.cn/

https://suowo.cn/

API文档

MySQL

Redis

全了

表结构设计

CREATE TABLE `url_map`
(
    `id`               BIGINT UNSIGNED NOT NULL PRIMARY KEY AUTO_INCREMENT COMMENT '主键id',
    `long_url`         VARCHAR(1024)    NOT NULL COMMENT '长链URL',
    `long_url_digest`  VARCHAR(128)    NOT NULL COMMENT '长链摘要',
    `short_url`        VARCHAR(32)     NOT NULL COMMENT '短链URL',
    `compression_code` CHAR(8)     NOT NULL COMMENT '压缩码，Base62编码，第一位为库编码，第二位为表编码，后六位为长链接经哈希函数处理后的Base62编码',
    `description`      VARCHAR(256) COMMENT '描述',
    `is_deleted`		TINYINT         NOT NULL DEFAULT 1 COMMENT 'URL状态,1:正常,2:已失效',
    `created_time`      DATETIME        NOT NULL DEFAULT CURRENT_TIMESTAMP COMMENT '创建时间',
    `updated_time`      DATETIME        NOT NULL DEFAULT CURRENT_TIMESTAMP COMMENT '创建时间',
    UNIQUE uniq_compression_code (`compression_code`),
    INDEX idx_short_url (`short_url`),
    INDEX idx_short_url_digest (`short_url_digest`),
    INDEX idx_long_url_digest (`long_url_digest`)
) COMMENT 'URL映射表';

POST /api/v1/url/short_urls
GET /api/v1/url/short_urls
GET /api/v1/url/*

短网址创建接口

URL：/api/v1/url/short_urls

HTTP方法：POST

入参

字段名称 字段类型 是否必须 示例值 描述 备注
long_url string 是 长链接

出参

字段名称 字段类型 示例值 描述 备注
short_url string 短链接

短网址还原接口

URL：/api/v1/url/short_urls

HTTP方法：GET

入参

字段名称 字段类型 是否必须 示例值 描述 备注
short_url string 是 短链接

出参

字段名称 字段类型 示例值 描述 备注
long_url string 长链接 
【京东买菜】快查收新人券！24盒整箱德国进口全脂牛奶39.9元，5斤爱媛果冻橙28.8元，速来 3.cn/v/1iO1YU-0 拒收请回复R

https://tr.jd.com/jump/transfer?jump_kid=769&jump_klid=3181869&jump_uuid=B22C5C496F011D5CC0039199AE26A0F5&jump_gatewayurl=3&jump_to=https%3A%2F%2Fmini-app-static.jd.com%2Fapps%2Fmpshare%2Findex.html
概述
Untitled