51工具盒子

依楼听风雨
笑看云卷云舒,淡观潮起潮落

10 亿级短 URL 生成方案,拿去可以直接重写短 URL 系统了

需求背景

在开始正文前,我们先弄清楚需求背景,以及我们本次需要完成目标。在营销测,运营人员会将内容生成 URL 链接,通过广告平台、短信平台、web平台等将内容投放出去,触达更多用户给自己带来收益。

内容制作->生成 URL,URL 会带一些特定的参数;另外,分配的域名有长有短,整个链接会很长,导致下面问几个问题

  1. 广告平台、营销短信大多都是有输入限制的,URL 超长发不出去;

  2. 长 URL 不美观,容易被当做不安全链接。

所以,短 URL 就登场了。下面是长 URL 和短 URL 对比,一目了然。

长URL
https://www.baidu.com/s?ie=utf-8&f=8&rsv_bp=1&rsv_idx=1&tn=baidu&wd=%E7%9F%AD%E9%93%BE&fenlei=256&rsv_pq=0x9b4642bf000d3f66&rsv_t=c4651MiLIQvma%2BAMNyeubwin1x2nr6R7MRKFkSKPaYCqgn6%2FTQ80TgsDQLz7&rqlang=en&rsv_enter=1&rsv_dl=tb&rsv_sug3=21&rsv_sug1=1&rsv_sug7=100&rsv_sug2=0&rsv_btype=i&prefixsug=%25E7%259F%25AD%25E9%2593%25BE&rsp=3&inputT=3252&rsv_sug4=3252

短URL
https://sourl.cn/mWHYhJ

短 URL 系统用例图 对象存储治理-第 7 页.png ❝

  1. 用户通过浏览器访问短 URL 前端页面,输入长 URL 生成短 URL,系统存储数据;

  2. 用户访问短 URL,短 URL 系统找到 mapping 关系,重定向长 URL ,即访问目标服务;

  3. 未来用户可自定义域名、CODE 生成规则、用量查看、购买增值服务;

  4. 管理员查看用量分析,制定收费策略;

  5. 系统视角,存储近2年数据,定期清理数据。

名词解释

短URL

通俗点讲就是将长URL转换为较短 URL,用于投放。

重定向方案有以下 2 种

301 重定向

永久重定向,用户浏览器访问了某短 URL,将重定向后的原始长 URL 缓存在本地,如果用户再次访问该短 URL,直接根据缓存在浏览器的长 URL 路径进行访问,避免了多次请求短 URL 应用,降低服务器压力。

302 重定向

临时重定向,每次访问短 URL 都需要访问服务器,服务器重定向长 ULR,访问对应的目标服务器。

我个人理解使用 302 或 301,要多方面考虑

  1. 同一个用户、同一短 URL 访问频率真的高吗?

  2. 你设计的架构是否完全能承受这些压力?

  3. 产品未来是否考虑监控、统计、收费类需求?(根据短 URL 生成、访问流量来收取费用)

如果你没有统计、收费类需求,完全可以用 301 重定向。反之,你对架构比较自信,且后续考虑收费模式,那用 302 重定向。

下面讲讲这次涉及数据模型。

短链模型

「短 URL 模型记录 When(时间) Who(谁) 通过 How(方式、场景) 将 What (什么长 URL) 生成了短 URL。」

触达模型

「触达,记录 When(时间) Who(谁) where (在哪里) 访问了What(什么短 URL)。」

触达模型记录了明细数据,未来根据明细数据通过大数据方案清洗结果即可。

资源预估

对于基础、高频使用系统,建议设计阶段提前预估资源使用情况,我整理了下面几个原因

  1. 成本考虑,只有 2w 预算,上线后成本 10w 超出了预期;

  2. 利于技术选型、架构设计,是否加缓存、分库分表、预生成 CODE?都依赖容量和 QPS 预估;

  3. 这类系统测试肯定不会放过压测的,预估指标同样有利于压力测试;

  4. 找老板申请资源,如果被老板怼过的应该都知道。

有人会问了我怎么预估呢,如果系统上线了,可以根据线上一些流量、数据作为依据,满足现状且上浮 20%-40% 即可;

如果是新系统,可以看看同行的数据或对用户数据量调研。上限还是要高一些,出现性能问题周期会拉长,有更多时间处理,避免影响客户使用。

短 URL 业界的方案基本都是保存 2 年,2 年前数据自动删除,后面根据 2 年为基线设计系统。

数据行数预估

预估每天生成的短 URL 300w,短 URL 有效期是 2 年,每个月按30天来算,短 URL 总条数为 21 亿+。

计算公式:300W*30天*12月*2年=21亿+
数据库存储预估

按照我的模型设计,单条数据 0.6k 左右,总容量约为 1201 GB。ps:存储是没有算触达记录的(访问记录)

计算公式:21亿*0.6k=1201GB
短 URL CODE 预估

短 URL 的 CODE 用的 base62(其实也可以 base64,后面我会讲),长度选择 6 个字符(也可以是7个),我希望整个长度越短越好,6 个字符生成的量要少一些。

CODE 长度是 6 个字符:每一个字符都可以是 62 个字符中的任何一个的组合方式,所以 CODE 数量是 62 的 6 次方大约是 568 亿。

CODE 长度是 7 个字符:62 的 7 次方大约是 3.52 万亿。

按照数据行数的预估,2 年的数据是 21 亿,所以,采用 6 个字符是完全够用的。

QPS 预估

全平台有 21 亿短 URL,2 年内,每个 URL 平均被访问 300 次,每秒平均 QPS 为 9988 qps/s,高峰期 qps 会更高一些,预估翻 1.5 倍,qps 为 14982 qps/s。

计算公式:
1、总请求总量:21 亿 * 300 约等于 6300 亿
2、年转换为妙:730 天 × 24 小时/天 × 3600 秒/小时 = 63072000 秒
3、平均QPS:总请求量/时间=6300亿/63072000妙=9988 qps/s
4、业务高峰期QPS:平均QPS*1.5=9988*1.5=14982 qps/s
带宽预估

一次 http 请求占用带宽有下面几种因素决定。

  1. 请求头部大小:包括请求行、各种头部字段(如User-Agent、Accept、Cookie等)、空行等。

  2. 请求体大小:如果是POST请求,并且包含了请求体数据,那么请求体的大小也需要考虑在内。

  3. 响应头部大小:与请求头部类似,响应头部也包括状态行、各种头部字段等。

  4. 响应体大小:实际的响应数据大小,例如HTML页面、图片、JSON数据等。

长 URL 大小预估 200 字节 (B) 左右;加上请求头、请求体,响应头等,预估 800 字节 (B)左右,单次请求小于 1 kb。QPS 每秒 9988 ,平均每秒带宽为 9.5 Mb,业务高峰期每秒带宽为 14.2 MB。

计算公式:
平均带宽:1000 字节 (B) * 9988=9.5 兆字节 (MB)
业务高峰期带宽:平均带宽*1.5=9.5*1.5=14.25兆字节 (MB)
Redis 存储预估

平均 qps 预估是 9988 qps/s,业务高峰期翻1.5倍 14982 qps/s ,不可能把所有流量都打到数据库,redis 至少抗 90% 流量,数据库才比较安全。但是我们不可能把所有的短链都缓存起来(1000gb+,redis 也扛不住啊)。

如果有线上/业界数据,根据这些数据来定。根据我的经验,刚生成的短 URL 才是热点链接,所以,决定保留 7 天数据。另外,缓存 miss 从数据库加载也会被保存在 redis 中。

7 天短 URL 生成量为 2100W,再加历史短 URL 缓存预热 500 W,所以,redis 总缓存数量 2600W,redis 只保留 CODE 和长 URL,预估 800 字节 (B),总容量为 19.3 千兆字节 (GB)

计算公式
1、7 天短 URL 生成量 :300W*7=2100W
2、缓存预热:缓存 miss,从数据库加载预估=500W
3、redis容量消耗:2600W*800 字节 (B)=19.3 千兆字节 (GB)

架构图

短 URL 架构图比较简单

关键路径概述

  1. 前端输入长 URL,短链服务生成 CODE,mapping 长 URL,数据落库,同时返回完整短 URL;

  2. 前端访问短 URL,短链服务通过CODE 查询长 URL,302/301 重定向长 URL 访问目标服务即可。

架构拆解

CODE 算法

我只讲 base62 算法,其它算法网上一大堆。标准的 base64 应该有64 个字符。但,网上算法都是 base62,但是没有给具体原因,随手百度下 base64 标准表编码。

| 索引 | 对应字符 | 索引 | 对应字符 | 索引 | 对应字符 | 索引 | 对应字符 | |----|------|----|------|----|------|----|------| | 0 | A | 17 | R | 34 | i | 51 | z | | 1 | B | 18 | S | 35 | j | 52 | 0 | | 2 | C | 19 | T | 36 | k | 53 | 1 | | 3 | D | 20 | U | 37 | l | 54 | 2 | | 4 | E | 21 | V | 38 | m | 55 | 3 | | 5 | F | 22 | W | 39 | n | 56 | 4 | | 6 | G | 23 | X | 40 | o | 57 | 5 | | 7 | H | 24 | Y | 41 | p | 58 | 6 | | 8 | I | 25 | Z | 42 | q | 59 | 7 | | 9 | J | 26 | a | 43 | r | 60 | 8 | | 10 | K | 27 | b | 44 | s | 61 | 9 | | 11 | L | 28 | c | 45 | t | 62 | + | | 12 | M | 29 | d | 46 | u | 63 | / | | 13 | N | 30 | e | 47 | v | | | | 14 | O | 31 | f | 48 | w | | | | 15 | P | 32 | g | 49 | x | | | | 16 | Q | 33 | h | 50 | y | | |

有 2 个字符(+/),url 会被转义,如下

| + | URL 中+号表示空格 | %2B | |----|------------------|-----| | 空格 | URL中的空格可以用+号或者编码 | %20 | | / | 分隔目录和子目录 | %2F | | ? | 分隔实际的URL和参数 | %3F | | % | 指定特殊字符 | %25 | | # | 表示书签 | %23 | | & | URL 中指定的参数间的分隔符 | %26 | | = | URL 中指定参数的值 | %3D |

原来如此,base62 算法是这么来的,好家伙。

赶紧百度,被转义字符如下:

";", "/", "?", ":", "@", "&", "=", "+", "$", ",", "%", "#", "%", 换行, 空格, 制表符

不会转义字符如下:

"-"(连字符或破折号)
"_"(下划线)
"."(句点)
"~"(波浪线)

波浪线和句点生成 CODE 会很奇怪,下划线和连字符我觉得是 OK 的。将 base62 算法改成 base64 ,按 6 位字符,CODE 可以生成 64 的 6 次方了,大约是 680 亿多点。如果你觉得"下划线"和"连字符或破折号"有点突兀用 base62 即可。

好了,讲完 base64 和 base62 区别,接下来讲讲如何生成 6 个字符了。下面介绍 2 种方案

  1. 生成 int64 唯一ID(可以用雪花ID,但是要解决唯一性问题),雪花ID%62(或64),即可拿到 11 个字符的字符串,将字符串截取成 6 个即可。

  2. 长 URL 做 md5,再通过 base64 编码,再截断 6 个字符即可。

后面会贴代码

CODE 碰撞兜底

不知道你们发现了没?不管是雪花ID 还是长 URL md5 的方式,最终生成的 CODE 都可能会发生冲突。

两种方案都会截断字符串,所以在生成的时候,需要先校验该短 URL 是否已经映射了其它长 URL,如果重复,需要重新计算,重新计算得到的短 URL 依然可能冲突,需要再重新计算。

短链表数据量很大,若多次查找数据库,短 URL 服务很难保证性能了,提供下面几个方案。

  1. code 加索引,利用覆盖索引减少回表;

  2. code 加上唯一索引,insert 失败,重新计算,避免查询;

  3. 预生成 code,技术方案比较复杂;

前 2 个方案不能解决 CODE 重新计算问题。

短 URL 生成时序图

image.png

关键路径概述 有几个重要点简单概述下

  1. CODE 生成是同步的,并且数据落库并没有同步写入 Redis;

  2. 用户访问优先访问 Reids,缓存 Miss 再查数据库,数据查回来后同步写 Redis;

  3. 用户访问短 URL,触达事件投递 kafka,A服务移步消费 kafka 事件落库。

那有人会问了,CODE 是同步生成,现在每天生成 300W,未来持续增长 500W、1000W ...,同步生成方案有问题吧?我想说你想的真远,不过也有解决方案。

预生成CODE

剥离 CODE 生成逻辑在新应用,假设为「A应用」吧,在业务低峰期比如:半夜生成第二天需要的 CODE,再或者业务上线就把所有的 CODE 都生成了。

但也带来了问题,预生成的 CODE 需要额外的存储成本,也会引入技术复杂度。CODE 预生成了,使用时需要去查吧?不可能实时从数据库查询,所以需要提前预热,「A应用」会提前加载一批写入 Redis 或者 POD 内存,需要的时候能从内存中快速查询返回就行,另外,已使用的 CODE 需要标记处理,防止被多次预热,造成数据异常。

另外,还有人会问了,怎么防止重复的长 URL 生成短 URL?重复生成浪费资源呀。当然也有方案。

生成短 URL 拦截机制

先搞清楚为什么同一个长 URL 会重复生成短 URL?一般有下面几个原因

  1. 有人搞你系统,消耗你硬件资源;

  2. 用户在浏览器无意操作(重复点生成或同一个长 URL 多次生成,可能相隔几天)。

前端拦截

对于用户在浏览器行为可以前端拦截,比如:首次长 URL 生成短 URL 返回给前端时,前端存储在浏览器缓存中,客户下次生成先查浏览器缓存,若缓存中存在即不用请求服务器(可以加过期时间)。

后端拦截

对于想搞你系统消,耗你资源的玩家来讲,前端拦截不起作用了。我简单介绍几种方案吧

  1. 长 URL 生成短 URL 接口做认证,可以防止非你用户的玩家瞎搞你;

  2. 增加过拦截策略。

    a. redis 缓存,做法很简单,长 URL MD5 映射 CODE,如果存在直接返回即可(冲突的情况暂时不考虑)。

    b. 布隆过滤器(我觉得没啥必要)。

另外,一般是前几天的长 URL 最容易被重复生成短 URL。所以,前端缓存或者后端缓存都可以设置一个过期时间,比如:针对最近 1 天长 URL 做拦截。

数据模型

名词解释讲了短链模型和触达模型,直接上图。

关键字段描述

现有字段不过多解释了,都非常简单。

  1. 未来可以根据需求扩展字段,比如:增加投放渠道,不同投放渠道对应不同的域名、短链规则等。

  2. 未来跟踪短链业务效果,利用数据平台清洗短链记录、触达到记录模型就可以了。

DROP TABLE IF EXISTS `short_link`;
CREATE TABLE `short_link` (
   `id`         varchar(255) NOT NULL COMMENT '主键id',
   `user_id`    varchar(255) NOT NULL COMMENT '用户id',
   `device`     varchar(20)  NOT NULL COMMENT '用户设备',
   `ip`         varchar(20)  NOT NULL COMMENT '用户ip',
   `partition_key` int(11)   NOT NULL COMMENT '分区键',
   `url`        varchar(4096) NOT NULL COMMENT '原始链接',
   `md5`        varchar(255) NOT NULL COMMENT '原始链接md5',
   `code`       varchar(255) NOT NULL COMMENT '短链code',
   `expires_at` bigint(255) DEFAULT 0 COMMENT '过期时间',
   `create_at`  bigint(255) DEFAULT 0 COMMENT '创建时间',
   PRIMARY KEY (`code`,`partition_key`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_bin
PARTITION BY HASH(partition_key) -- 指定分区规则
PARTITIONS 105;-- 指定分区数量

触达记录这里不建表了,主要用于内部统计分析、收费模式支撑、对用户展示,我觉得没有必要做实时,可以用更便宜的存储,最终大数据平台预聚合数据就可以了。

数据库选型

一如既往选择 tidb,看过往期文章的都知道,这里不赘述。下面2篇文章讲了分区表、sql优化,感兴趣可以阅读。

亿级表优化「TIDB 分区篇」,值得收藏 - 掘金

亿级表优化思路之 SQL 篇,值得收藏 - 掘金

分区表

分区还是采用 hash ,hash 分区需要一个 int 字段,对应 partition_key 字段,这个字段可以根据 code 字段来生成。hash 分区能保证分区更均匀一些,数据倾斜没有那么高。

2 年数据 21 亿,期望每个分区最多 2000 w 数据,分区数=21亿/2000w 是 105 个分区。

过期数据清理

前面讲过,数据保留 2 年,2 年前的数据要删除处理,如果要备份过期数据就采用更便宜存储吧。

数据清理有 2 种方案。

  1. 方案一:定时调度清理数据(这也是网上主流方案,不推荐)。

    a. 如果是自己开发的中间件分库分表,用定时任务扫你的找到规则吧?可能会很复杂;

    b. 如果是分区表,比如 tidb 分区,如果用的 hash 分区,根据过期时间删除数据?等着被锤吧,全分区扫描。

  2. 方案二:利用数据库自身能力(推荐)

    a. tidb 提供了定期删除数据的能力,我看腾讯云的数据库也支持了。使用 TTL (Time to Live) 定期删除过期数据 | PingCAP 文档中心

OK,删除数据完美解决。如果有备份数据需求提前想办法备份咯。或者 binglog 事先同步好。

核心代码

import (
	"crypto/md5"
	"encoding/base64"
	"github.com/bwmarrin/snowflake"
	"io"
	"strings"
)

type Shortener interface {
	Generate(url string) (string, error)
}

var base64Factory = []string{
	"0", "1", "2", "3", "4", "5", "6", "7", "8", "9",
	"a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k",
	"l", "m", "n", "o", "p", "q", "r", "s", "t", "u",
	"v", "w", "x", "y", "z", "A",
	"B", "C", "E", "F", "D", "G", "H", "I", "J", "K", "L", "M",
	"N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z", "-", "_",
}

const (
	size = 6
)

type snowflakeGenerate struct {
}

func (s *snowflakeGenerate) Generate(url string) (string, error) {
	node, err := snowflake.NewNode(1)
	if err != nil {
		return "", err
	}

	id := node.Generate().Int64() // todo 高并发情况下可能会有冲突
	l := int64(len(base64Factory))
	sb := strings.Builder{}
	for ; id/l > 0; id /= l {
		index := id % l
		sb.WriteString(base64Factory[index])
	}

	return sb.String()[:size], nil // 截断字符串
}

type md5Generate struct {
}

func (s *md5Generate) Generate(url string) (string, error) {
	hash := md5.New()
	_, err := io.WriteString(hash, url)
	if err != nil {
		return "", err
	}

	b := hash.Sum(nil)
	es := base64.RawURLEncoding.EncodeToString(b) // url base64编码,已经过滤转义字符

	return es[:size], nil // 截断字符串
}

测试代码

func TestSnowflakeGenerate(t *testing.T) {
	s := &snowflakeGenerate{}
	code, err := s.Generate("")
	if err != nil {
		panic(err)
	}
	fmt.Println(code)
}

func TestMD5Generate(t *testing.T) {
	s := &md5Generate{}
	code, err := s.Generate("https://docs.pingcap.com/zh/tidb/stable/time-to-live")
	if err != nil {
		panic(err)
	}
	fmt.Println(code)
}

结尾

短 URL 系统,存储 21 亿+数据、高 qps 但是技术方案看起来并不算复杂。只要保证 CODE 生成和长 URL 的映射正确;

数据量其实都不算大,现在分布式数据库存储这点量是完全没问题的;

提升 QPS 可以考虑 Redis 存储,极端情况还可以上内存缓存,能有效提升系统的 QPS;

另外,短 URL 服务都是多 POD,高可用这块完全没问题。

写作不易各位看官动动发财小手点点赞。

点击******关注******公众号,"技术干货***" 及时达!***


赞(2)
未经允许不得转载:工具盒子 » 10 亿级短 URL 生成方案,拿去可以直接重写短 URL 系统了