10 亿级短 URL 生成方案，拿去可以直接重写短 URL 系统了
=================================
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 系统用例图
- 用户通过浏览器访问短 URL 前端页面，输入长 URL 生成短 URL，系统存储数据；
- 用户访问短 URL，短 URL 系统找到 mapping 关系，重定向长 URL ，即访问目标服务；
- 未来用户可自定义域名、CODE 生成规则、用量查看、购买增值服务；
- 管理员查看用量分析，制定收费策略；
- 系统视角，存储近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)。
触达模型记录了明细数据，未来根据明细数据通过大数据方案清洗结果即可。
资源预估
对于基础、高频使用系统，建议设计阶段提前预估资源使用情况，我整理了下面几个原因
- 成本考虑，只有 2w 预算，上线后成本 10w 超出了预期；
- 利于技术选型、架构设计，是否加缓存、分库分表、预生成 CODE？都依赖容量和 QPS 预估；
- 这类系统测试肯定不会放过压测的，预估指标同样有利于压力测试；
- 找老板申请资源，如果被老板怼过的应该都知道。
有人会问了我怎么预估呢，如果系统上线了，可以根据线上一些流量、数据作为依据，满足现状且上浮 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 请求占用带宽有下面几种因素决定。
- 请求头部大小：包括请求行、各种头部字段（如User-Agent、Accept、Cookie等）、空行等。
- 请求体大小：如果是POST请求，并且包含了请求体数据，那么请求体的大小也需要考虑在内。
- 响应头部大小：与请求头部类似，响应头部也包括状态行、各种头部字段等。
- 响应体大小：实际的响应数据大小，例如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 架构图比较简单
关键路径概述
- 前端输入长 URL，短链服务生成 CODE，mapping 长 URL，数据落库，同时返回完整短 URL；
- 前端访问短 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 服务很难保证性能了，提供下面几个方案。
- code 加索引，利用覆盖索引减少回表；
- code 加上唯一索引，insert 失败，重新计算，避免查询；
- 预生成 code，技术方案比较复杂；
前 2 个方案不能解决 CODE 重新计算问题。
短 URL 生成时序图
关键路径概述
有几个重要点简单概述下
- CODE 生成是同步的，并且数据落库并没有同步写入 Redis；
- 用户访问优先访问 Reids，缓存 Miss 再查数据库，数据查回来后同步写 Redis；
- 用户访问短 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 返回给前端时，前端存储在浏览器缓存中，客户下次生成先查浏览器缓存，若缓存中存在即不用请求服务器（可以加过期时间）。
后端拦截
对于想搞你系统消，耗你资源的玩家来讲，前端拦截不起作用了。我简单介绍几种方案吧
- 长 URL 生成短 URL 接口做认证，可以防止非你用户的玩家瞎搞你；
- 增加过拦截策略。
a. redis 缓存，做法很简单，长 URL MD5 映射 CODE，如果存在直接返回即可（冲突的情况暂时不考虑）。
b. 布隆过滤器（我觉得没啥必要）。
另外，一般是前几天的长 URL 最容易被重复生成短 URL。所以，前端缓存或者后端缓存都可以设置一个过期时间，比如：针对最近 1 天长 URL 做拦截。
数据模型
名词解释讲了短链模型和触达模型，直接上图。
关键字段描述
现有字段不过多解释了，都非常简单。
- 未来可以根据需求扩展字段，比如：增加投放渠道，不同投放渠道对应不同的域名、短链规则等。
- 未来跟踪短链业务效果，利用数据平台清洗短链记录、触达到记录模型就可以了。
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 种方案。
- 方案一：定时调度清理数据（这也是网上主流方案，不推荐）。
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，高可用这块完全没问题。
写作不易各位看官动动发财小手点点赞。
祝：大家周末愉快。
原文链接: https://juejin.cn/post/7367635686936559667
文章收集整理于网络，请勿商用，仅供个人学习使用，如有侵权，请联系作者删除，如若转载，请注明出处：http://www.cxyroad.com/17005.html
良月柒 