Skip to content

Latest commit

 

History

History
211 lines (156 loc) · 13.3 KB

TINYURL.md

File metadata and controls

211 lines (156 loc) · 13.3 KB

Index

短连接设计
 1. 资料
 2. 确定问题及业务需求
 3. 短链接设计要点
  3.1. 方案一: 摘要hash算法
   3.1.1. 确定短连接长度
   3.1.2. 使用hash算法 + bash 62位转换
   3.1.3. hash冲突解决
   3.1.4. 唯一性判断
   3.1.5. 唯一性检测重复查库问题
  3.2. 方案二: 使用UUID的发号器服务方案
   3.2.1. mysql自增ID
   3.2.2. 发号器存在的问题
  3.3. 数据库映射
   3.3.1. 短连接永久有效
   3.3.2. 短连接存在过期时间
   3.3.3. 数据库表设计
   3.3.4. 分库分表
 4. 短链接跳转，301还是302重定向
 5. 预防攻击
 6. 思考问题

短连接设计[Top]

资料[Top]

相关视频：

相关文章：

确定问题及业务需求[Top]

  1. 数据量：增长数据量。
  2. 时效性：永久短连接还是具有过期时间的短连接。
  3. 存储：使用数据库或不使用数据库保存。正常的短链接服务都是会落数据库的，用于数据分析。
  4. 唯一性：长链接是否与短链接一一对应，还是在一段时间内一一对应就满足需求。

关键短链接的思想为短链接的生成逻辑，而以上需求问题，在不同的设定下解决方案多种多样，区别主要在唯一性、存储这两大块。

短链接设计要点[Top]

方案一: 摘要hash算法[Top]

确定短连接长度[Top]

  1. 使用大小写字母+数字的62进制方案，取6~8位便可以支持上亿的不同短连接

62^6 = 568,00235584 62^7 = 35216,14606208

  1. 使用32进制小写字母+数字 36位 36^8 = 3w亿

使用hash算法 + bash 62位转换[Top]

hash算法使用MD5 或者 MurmurHash(非加密型哈希函数，效率比MD5高)

  1. 使用hash算法进行长URL加密(分为16位和32位)，
  2. 使用base 62位，转换md5 结果获取前8个字符或者后八位，当成短连接地址。

对于 urls，使用 Base 62 编码 [a-zA-Z0-9] 是比较合适的, 对于每一个原始输入只会有一个 hash 结果，Base 62 是确定的（不涉及随机性） Base 64 是另外一个流行的编码方案，但是对于 urls，会因为额外的 + 和 - 字符串而产生一些问题

hash冲突解决[Top]

使用hash函数不可避免的会出现hash冲突的情况，解决方案如下：

  1. 可以对原有的url进行加减字符重新加密(如在长连接前添加固定字符randomSalt)。
  2. 对于加密后的地址，拼接再url头上，变成动态salt进行再加密
  3. 使用url+时间戳生成，生成失败后获取新的时间戳生成。

唯一性判断[Top]

长链接生成短链接后，落数据库可以使用如下表设计：

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;

每次生成短链接之后，去数据库进行查询，如果冲突再重新生成短链接。

这是一个数据库简单的方案，更多时候我们可能会将同一个地址根据不同的用户生成不同的短链接，实际见下文

唯一性检测重复查库问题[Top]

为了检验唯一性，而进行重复的查询数据库，会导致性能较低，可以引入Redis的布隆过滤器解决。利用布隆过滤器存储效率及判空的效率的解决重复查库问题。

参考知乎码海回答

image

方案二: 使用UUID的发号器服务方案[Top]

使用发号器的好处就是，可以天生保证唯一性，不存在冲突问题

发号器策略如下：

  1. 使用如雪花主键的UUID当成长链接对应的键
  2. 维护一个keyGenerate 服务
  3. 随机生成数
  4. mysql自增ID

B站视频有完整解说

mysql自增ID[Top]

在高并发下，db 的写压力会很大，可以设计一个专门的发号表解决，每插入一条记录，为短链 id 预留 （主键 id * 1000 - 999） 到 (主键 id * 1000) 的号段，

当长链转短链的请求打到某台机器时，先看这台机器是否分配了短链号段，未分配就往发号表插入一条记录，则这台机器将为短链分配范围在 tmp_start_num 到 tmp_end_num 之间的 id。从 tmp_start_num 开始分配，一直分配到 tmp_end_num，如果发号 id 达到了 tmp_end_num，说明这个区间段的 id 已经分配完了，则再往发号表插入一条记录就又获取了一个发号 id 区间。

1.最简单的用数据库自增，把步长设置为1000就可以了 2.每个发号器发的号是不重复的，所以他挂了其他的也不会发出重复的号来，比如第一个发号器发1，1001，2001，3001，第二个发2，1002，2002，3002

发号器存在的问题[Top]

发号器虽然避免了冲突，对应存在的问题有可能被黑客破解短链接的生成直接通过数字枚举破解。

可以使用用户Id的部分信息与发号器组成短链接，进行混淆。

数据库映射[Top]

区分短连接的用途进行设计，主要有以下两种：

  1. 短连接永久有效，无需对短连接进行数据分析。
  2. 短连接存在过期时间
    1. 无需对短连接进行数据分析。
    2. 需要根据生成链接的用户等信息，对短连接进行数据分析，

短连接永久有效[Top]

短连接永久有效，正常就需要落数据库表。

短连接需要进行数据分析，那么数据需要存储到数据库中：

  1. 若长链接需要区分分享的用户，地点，时间等信息，长链接与短链接以1对多的方式存储。可用于后序的数据分析。
  2. 若长连接无需区分用户的类型，可直接公用相同的短链接。

结合Redis，使用布隆过滤器进行短连接的判空。使用String的数据结构判断，短连接是否存在。

短链接数据表中，为了查找长链接是否生成过短链接，那么就需要建立索引便于快速查找。

  1. 直接使用长链接建索引，字段占用太多数据页空间且无序，索引效率太低。（废弃）
  2. 使用短链接建立索引，针对于长链接转短链接冲突或者使用发号器的方案的情况，均难以查找直接根据短链接查找长链接是否已经生成。（废弃）
  3. 冗余一个hash字段，hash字段为长链接使用数据库hash函数生成，如crc32()，再该字段上建立普通索引，对于hash函数冲突的情况再使用长链接判断。

select * from short_url_map where crc_origin_url = crc32('长链接入参') and origin_url = '长链接入参'

短连接存在过期时间[Top]

若短链接无需进行数据分析，那么可以直接选用NoSql的数据库，如Redis。

  1. 长连接与短连接直接使用String数据结构，长连接K - 短连接V 加上过期时间
  2. 如何判断短连接是否已经生成，使用Redis的布隆过滤器。

若短链接需进行数据分析，还是需要落数据库，数据表可以参考下文设计

  1. 如何判断短连接是否已经生成，使用Redis的布隆过滤器。
  2. 生效的长链接可以以userId+origin_url作为Key，short_url作为value，加上过期时间。键过期可以监听redis的过期事件，更新数据库记录。

由于存在短链接存在过期时间，那么布隆过滤器的判重逻辑会存在问题，可能已经过期的键妨碍的新的短链接生成。
redis不支持清除布隆过滤器中已经添加的键，可以将布隆过滤器的name做成可配置的，使用定时任务扫描生效的短链接记录，重新new一个新的布隆过滤器，再修改布隆过滤器的name

数据库表设计[Top]

  1. 直接使用shortlink 当成主键，便于分库分表，但是数据插入的效率较慢。唯一主键为了保证数据唯一，需要将数据读入内存判断是否唯一，用不上change buffer的优化机制
  2. 自增ID充当主键，针对短链接不建立唯一索引，而是在代码层面做唯一性逻辑判断。如使用redis set nx的操作，做一个简单的并发控制。
create table if not exists `short_url_map` (
  `id` int(11) not null,
  `short_link` varchar(128) not null comment '短链接',
  `origin_link` varchar(256) not null comment '原始长链接',
  `crc_origin_link` varchar(256) not null comment 'hash原始长链接',
  `user_id` varchar(128)  not null comment '用户id',
  `deleted` tinyint(0) not null DEFAULT 0,
  `created_time` datetime not null,
  `modified_time` datetime not null,
  `version` int(11) not null default '1',
  primary key (`id`),
  key `crc_origin_link_idx` (`crc_origin_link`)
) engine=innodb default charset=utf8;

分库分表[Top]

由于短链接可直接做进制转换，并具有唯一性

使用短连接作为sharding key，进行水平分库拆分。

另外可以基于一季度做数据归档。

短链接跳转，301还是302重定向[Top]

这个问题主要是考察你对301和302的理解，以及浏览器缓存机制的理解。

301是永久重定向，302是临时重定向。短地址一经生成就不会变化，所以用301是符合http语义的。但是如果用了301， Google，百度等搜索引擎，搜索的时候会直接展示真实地址(即短链接对应的长连接地址，浏览器缓存)，那我们就无法统计到短地址被点击的次数了，也无法收集用户的Cookie, User Agent 等信息，这些信息可以用来做很多有意思的大数据分析，也是短网址服务商的主要盈利来源。

所以，正确答案是302重定向。

预防攻击[Top]

  1. 频繁生成短链接的 使用ip黑名单屏蔽。
  2. 使用redis建立长链接 ->ID的缓存。

思考问题[Top]

短连接永久有效，使用Mysql关系型存储数据，如何判断该长链接已经生成过短链接？

  1. 长链接建立索引？

错，字段随机性过大，且索引树节点存储的数据少。

  1. 长链接生成短连接后，通过短连接查询？

若短连接使用发号器生成，该方法失效。
若长链接使用Hash算法生成，需保证同一个Key处理Hash冲突的流程及结果一致，才能查到是否已经转换过短链接。如冲突时加上同样的字段再hash
上述方法问题点：短连接过于随机，数据插入时候，可能导致插入过程中短连接索引树调整的效率问题。
冗余一个hash索引字段为较优的一个解决方案。