高性能短链设计

原文链接：高性能短链设计 - 掘金 (juejin.cn)

介绍

将长连接转为一个短连接，并且再访问时再转换回来

短链：

image-20240318150323802

最终长链

image-20240318150335744

可以看到，短信中的是短链，但最后变成了长链；使用短链的好处

  1. 再具有文字限制的地方（微博），用短链可以占据更少的文字
  2. 短链对应转的二维码不密集，更容易识别

跳转的基本实现：请求短链时，会返回状态码302（临时重定向：每次都使用短链请求，易于点击数统计）以及长链的地址

生成算法

1.HASH

生成hash

将长信息转为断信息，最简单有效的方式就是hash

  1. 加密哈希函数（Cryptographic Hash Functions）：这些函数被设计为具有一系列加密属性，包括抗碰撞性（collision-resistant）、隐藏性（hiding）和抗篡改性（tamper-evident）。它们用于密码学安全、数据完整性验证等场合。常见的加密哈希算法有SHA-256、SHA-3、MD5（现在被认为是不安全的）等。
  2. 非加密哈希函数（Non-cryptographic Hash Functions）：这些函数主要用于数据结构（如哈希表）中快速数据检索、数据压缩、负载均衡等非安全相关的场合。它们的设计重点在于速度和效率，而不是安全性。常见的非加密哈希函数包括MurmurHash、CityHash等。

这里我们当然选择非加密的Hash算法，例如MurmurHash

MurmurHash 提供了两种长度的哈希值，32 bit，128 bit，为了让网址尽可通地短，我们选择 32 bit 的哈希值，32 bit 能表示的最大值近 43 亿，对于中小型公司的业务而言绰绰有余。对上文提到的极客长链做 MurmurHash 计算，得到的哈希值为 3002604296

缩短长度：

这里的数字都是十进制的表示，我们可以将10进制转为62进制（10+26+26；比base64少 + 和 /，以及填充字符=）

image-20240318151541698

解决哈希冲突并存储

短链映射长链：使用mysql 或 redis，配合唯一索引

此外，为了同一个长链不重复生成短链，需要将长链建议索引，为了索引不要太长使用长链的MD5建索引

1
2
3
4
5
6
7
8
CREATE TABLE `short_url_map` (
  `id` int(11) unsigned NOT NULL AUTO_INCREMENT,
  `lurl` varchar(160) DEFAULT NULL COMMENT '长地址',
   `md5` char(32) DEFAULT NULL COMMENT '长链md5',
  `surl` varchar(10) DEFAULT NULL COMMENT '短地址',
  `gmt_create` int(11) DEFAULT NULL COMMENT '创建时间',
  PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

  1. 查询长链的MD5是否已经存在，存在直接返回

  2. 将长链（lurl）经过 MurmurHash 后得到短链。

  3. 将长短链对应关系插入 db 中，如果 db 里不含有此短链的记录，则插入，如果包含了，说明违反了唯一性索引，此时只要给长链再加上我们上文说的自定义字段「DUPLICATE」,重新 hash 再插入即可，看起来在违反唯一性索引的情况下是多执行了步骤，但我们要知道 MurmurHash 发生冲突的概率是非常低的，基本上不太可能发生，所以这种方案是可以接受的。

此外，快速有效判断一个元素是否存在可以使用布隆过滤器，先经过布隆过滤器再插入数据库

image-20240318152646488

2.自增序列

方案选择

image-20240318154514607

  1. uuid

    UUID(Universally Unique Identifier)全局唯一标识符,是指在一台机器上生成的数字，它保证对在同一时空中的所有机器都是唯一的，但这种方式生成的 id 比较长，且无序，在插入 db 时可能会频繁导致页分裂，影响插入性能。无需中心化管理

  2. redis

    INCR：性能好，单机可支撑 10 w+ 请求，还可以做分布式

    缺点：需要考虑持久化（短链 ID 总不能一样吧），灾备，成本有点高。

    image-20240318153824226

  3. Snowflake

    时钟回拨：抛出异常；延时等待（阻塞3ms）；序列号（增加序列号避免冲突）

  4. Mysql 自增

    简单方便

mysql优化

如果用 Mysql 自增 id 作为短链 ID，在高并发下，db 的写压力会很大，这种情况该怎么办呢。

考虑一下，一定要在用到的时候去生成 id 吗，是否可以提前生成这些自增 id ?

发号表：代表已经发出去的id，每行为一个区间，给一台机器

image-20240318154839222

image-20240318155037597

或者直接一行为一个业务

1
2
3
4
5
6
7
8
9
10
CREATE TABLE `sequence_id_generator` (
  `id` int(10) NOT NULL,
  `current_max_id` bigint(20) NOT NULL COMMENT '当前最大id',
  `step` int(10) NOT NULL COMMENT '号段的长度',
  `version` int(20) NOT NULL COMMENT '版本号',
  `biz_type`    int(20) NOT NULL COMMENT '业务类型',
   PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

current_max_id ~ current_max_id + step已经被取走了

获取唯一ID

1
SELECT `current_max_id`, `step`,`version` FROM `sequence_id_generator` where `biz_type` = 101

分配新的区间，version实现并发管理

1
2
UPDATE sequence_id_generator SET current_max_id = 0+100, version=version+1 WHERE version = 0  AND `biz_type` = 101
SELECT `current_max_id`, `step`,`version` FROM `sequence_id_generator` where `biz_type` = 101

高性能短链设计今天，我们来谈谈如何设计一个高性能短链系统，短链系统设计看起来很简单，但每个点都能展开很多知识点，也是在面 - 掘金 (juejin.cn)

  1. 高性能短链设计 ↩
  2. 分布式ID介绍&实现方案总结 | JavaGuide ↩