解读短链系统设计(design tiny url)2022/12/26 17:13:48

哦不明白

同前文一样，用两个哈希表处理长址和短址之间的相互映关系。需额外处理的是用户设定的址与已有冲突时，需返回。注意：若用户设定的和已有恰好相同，则同样应该返回短址。短链系统设计（）如脉脉，不会纵容你发太长的址，会给你转成短链。ip域名查询网的相关知识也可以到网站具体了解一下，有专业的客服人员为您全面解读，相信会有一个好的合作！

1S场景根据一个生成一个。

如:=:1ULQB6

根据还原，并跳转：



需和面试官确认的问题：

和必须一一对应吗

S长时间没人用，需要释放吗

11QPS分析问日活，如微博100M推算产生一条的假设每个用户平均每天01（发10条，有一条有链接）条带URL的微博

平均写QPS=100M*0186400=100

峰值写=100*2=200

推算点击一条的假设每个用户平均点1个

平均写QPS=100M*186400=1

峰值读=1*2=2

每天产生的新URL所占存储100M*01=10M条

每条URL长度平均按100算，共1G

1T硬盘能用3年

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

2S服务-逻辑块聚类与接口设计该系统其很简单，只需要有一个即可：URLS。由于只有一个US：

本身其就是个小的单独应用也需关心其他任何业务功能方法设计：

US(_)：编码方法

US(_)：解码方法

访问端口设计，当前有如下两种常用主流风格：

GETREST风格RREST风格R

POST（不太推荐，不符合REST设计风格，但也有人在用）



那么，你们的短链系统是选择哪种服务设计呢

3S数据存取（比较能体现践经验）选存储结构细化数据表31SQLVSNSQL需要事务吗N，+1

需要丰富的吗，+1

想偷懒吗?需要写的代码不复杂，+1

高吗2，不高。+1

要求多高存储和都不高，单机都能搞定。+1

-需要自己写代码来-，这些都帮你做了是否需要ID取决于你的算法

提供_的ID，即1,2,3的ID不是32算法转成一个6位的。给出一个长址，返回一个短址。

现两个方法：

TS()?把一个长址转换成一个以:开头的短址TL()把一个短址转换成一个长址TL()把一个短址转换成一个长址标准：

短址的的长度应为6（不算域和反斜杠）。可用字符只有[-A-Z0-9]?比如:D9E[-A-Z0-9]?比如:D9E任意两个长的不会对应成同一个短，反之亦然。用两个哈希表：

一个是短址映到长址一个是长址映到短址短址是固定的格式:":"+6个字符,字符可任意。

为避免重复,我们可以按照字典序依次使用,或者在随机生成的基础上用一个集合来记录是否使用过。

使用哈希函数（不可行）

如取的MD5的比较后6位：

难以设计一个哈希冲突的哈希算法随机生成URL+DB去重

随机取一个6位的URL，若没使用过，就绑定到改。

S2S(S){(){SURL=SURL();(!(URL=URL)()){(URL=URL,URL=);URL;}}}TU{TU(){2S=HMS,S();2L=HMS,S();}***@*@:*STS(S){(2SK()){2S();}(){SURL=SURL();(!2LK(URL)){2L(URL,);2S(,URL);URL;}}}***@:*@*STL(S){(!2LK()){;}2L();}SSURL(){SC="0123456789"+""+"ABCDEFGHIJKLMNOPQRSTUVWXYZ";R=R();SURL=":";(=0;6;++){=I(62);URL+=CA();}URL;}}点：现简单

缺点：生成短链接的速度，随着短链接越多而越慢

关系型数据库表：只需S和两列，并分别建立索引

也可使用，但需要建立两张表：

根据查询=列==根据查询=列==







进制转换B32(微博现方案)

B62：

将6位看做一个62进制数（0-9,-,A-Z）每个对应到一个整数该整数对应DB表的主键6位可表示的不同URL：

5位=62^5=09B=9亿6位=62^6=57B=570亿7位=62^7=35T=35000亿点：效率高

缺点：强依赖于全局的自增

TU{GLOBAL_ID=0;HMI,S2=HMI,S();HMS,I2=HMS,I();SSK(S){(":"());}B62(){(='0'='9'){-'0';}(=''=''){-''+10;}-'A'+36;}KID(S_){=0;(=0;_();++){=*62+B62(_A());};}STSK(){S="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";S_="";(0){_=A(%62)+_;=62;}(_()6){_="0"+_;}_;}***@*@:*STS(S){(2K()){":"+TSK(2());}GLOBAL_ID++;2(,GLOBAL_ID);2(GLOBAL_ID,);":"+TSK(GLOBAL_ID);}***@:*@*STL(S){S_=SK();=KID(_);2();}}因为要用到自增，所以只能用关系型DB表：

主键、（索引）

4S如何提高响应速度，和直接打开原链接一样的效率。

明确，这是个读多写少业务。

41缓存提速（CA）缓存需存储两类数据：

2（生成新需要）2（查询时需要）

42CDN利用地理位置信息提速。

化服务器访问速度：

不同地区，使用通不同服务器通过解析不同地区用户到不同服务器化数据访问速度

使用中心化的MSQL+分布式的R一个MSQL配多个R，R跨地区分布

43何时需要多台DB服务器资源不够或命中率低

写操作过多

越来越多请求法通过满足

多台DB服务器可以化什么?

?解决存不下：存储

?解决忙不过：

那么的主要问题是啥存储是没问题的，重点是。那么，如何呢?

垂直拆分：将多张表分别分配给多台机器。对此不适用，只有两列，法再拆分。

横向拆分：

若、URL做分片键：

?2查询时，只能广播给N台都去查询

?为何要查2避免重复创建呀

?若不需要避免重复创建，则这样可行

用做分片键：

2查询时，只能广播给N台DB查询。

431分片键选择

若一个可对应多个

?使用缓存所有2

?在为一个创建时，若，则创建新

若一个只能对应一个

?若使用随机生成算法

?两张表，一张存储2，一张存储2

?每个映关系存两份，则能同时支持22查询

?若使用62进制转换法

?有个严重问题，多台机器之间如何维护一个全局自增的

?一般关系型DB只支持在一台机器上现这台机器上全局自增的

44全局自增441专用一台DB做自增服务

该DB不存储真数据，也不负责其他查询。

为避免单点故障，可能需要多台DB。

442使用

但使用全局自增不是解决比较佳方案。GDSN

45基于62的分片策略H(_)%62作为分片键

并将(_)%62直接放到

若原来的是AB1234，则现在的是

(_)%62+AB1234若(_)%62=0，那就是0AB1234这样，就能同时通过、得到分片键。

缺点：DB的机器数目不能超过62。

所以，比较后比较佳架构：



46还能化吗和之间的通信。

中心化的服务器集群和跨地域的之间通信较慢：如的S需访问美国的DB。

为何不让的S访问的DB呢?

若数据重复写到DB，如何解决一致性问题很难解决！

思考用户的习惯：

用户访问时，会被DNS分配的服务器用户访问的一般都是的所以可按的地域信息来如何获得的地域信息只需将用户常访问的汇总在一张表。用户访问美国咋办?就访问美国，也不会慢太多中访中是用户主流，化系统就是针对主要需求于是，得到比较终架构：



还可以维护一份域白单，访问对应地域的DB。

5用户自定义短链接现一个顾客短址，使得顾客能创立他们自己的短址。即你需要在前文基础上再现一个C。C。

需现个方法：

2S()把一个长址转换成一个以:开头的短址2S()把一个长址转换成一个以:开头的短址2L()把一个短址转换成一个长址2L()把一个短址转换成一个长址C(,)设定一个长址的短址为:+C(,)设定一个长址的短址为:+注意：

2S生成的短址的的长度应该等于6（不算域和反斜杠）。可以使用的字符只有[-A-Z0-9]。如:D9E2S生成的短址的的长度应该等于6（不算域和反斜杠）。可以使用的字符只有[-A-Z0-9]。如:D9E任意两个长的不会对应成同一个短，反之亦然如果C不能完成用户期望的设定,那么应该返回"",反之如果成功将长址与短址对应，应该返回这个短址C不能完成用户期望的设定,那么应该返回"",反之如果成功将长址与短址对应，应该返回这个短址51基于B62在URLT里，直接新增一列_记录对应的是否可行

不可行！对于大部分数据，该列其都为空，就会浪费存储空间。

新增一个表，存储自定义URL：CURLT。



创建自定义短链接：在CURLT中查询和插入

根据长链接创建普通短链接：

先查询CURLT是否存在再在URLT查询和插入同前文一样，用两个哈希表处理长址和短址之间的相互映关系。需额外处理的是用户设定的址与已有冲突时，需返回""。注意：若用户设定的和已有恰好相同，则同样应该返回短址。

TU2{HMS,S2=HMS,S();HMS,S2=HMS,S();=0;SBU=SB(":");S="1234567890QWERTYUIOPASDFGHJKLZXCVBNM";SSU(){SB=SB();(=0,=;6;++,=62)(A(%62));++;U+S();}**@_:*@:*@::*SC(S_,S){S_=U+;(2K(_)){(2(_)(_))_;"";}(2K(_))"";2(_,_);2(_,_);_;}**@_:*@::*STS(S_){(2K(_))2(_);S_=SU();2(_,_);2(_,_);_;}**@_::*@:*STL(S_){(2K(_))2(_);"";}}52基于随机生成算法需做任何改动，直接把当创建即可！

参考：29270034