January 29, 2018

ShortURL系统实现

在知乎上看了一个很有启发的回答,因此实际动手来实现短URL生成系统。

在知乎上看了一个很有启发的回答,因此实际动手来实现短URL生成系统。贴上链接: 知乎 - 短URL系统是如何设计的。其中提到了,要实现短URL生成系统要解决的问题有:

  • 如何优雅的实现?
  • 怎么基本实现长对短、一对一?
  • 如何实现分布式,高并发,高可用?
  • 储存选用?

基本原理

数据库自增ID转换62进制

  1. 使用自增ID不会产生重复的短链接。
  2. 为了解决自增ID超长和不便记忆,对ID进行62进制编码。所谓62进制就是0-9,a-z,A-Z。

简单计算下:

62 ^ 4 = 14,776,336
62 ^ 5 = 916,132,832
62 ^ 6 = 56,800,235,584 // 已经足够使用了

总体结构及处理流程

服务结构

长链接处理流程

  1. 获取参数,调用shortURL服务
  2. 尝试从缓存中获取,如果命中,则读取短链接(重置过期时间)。跳转第4步
  3. 将长链接存储到Mysql数据库,根据ID进行base62编码,组装Domain+Encoded字符串并更新数据库
  4. 返回生成的短链接

短链接处理流程

  1. 解析短链接为ID
  2. 查询ID对应的长链接
  3. 以301方式跳转到长链接

长链接与短链接的对应关系

一对多,一个长链接可能对应多个短链接。数据表存储结构如下:

+-----------+--------------+------+-----+---------+----------------+
| Field     | Type         | Null | Key | Default | Extra          |
+-----------+--------------+------+-----+---------+----------------+
| id        | int(64)      | NO   | PRI | NULL    | auto_increment |
| long_url  | varchar(100) | NO   |     | NULL    |                |
| short_url | varchar(40)  | YES  |     | NULL    |                |
+-----------+--------------+------+-----+---------+----------------+

分布式和高并发设计

###注:这部分未实现。我的思路如下:

集群部署

分布式部署会遇到的问题"ID重复",关于这一点在回答中也提示了:根据node数来配置自增step。譬如说,有1000个node:

|节点|1st-URL-ID|2nd-URL-ID|3th-URL-ID|…|Nth-URL-ID| |—|—|—|—-|—-| |node-1|0|1000|2000|…| 0 + (N-1) * 1000| |||||….|| |node-1000|999|1999|2999|…|999 + (N-1) * 1000|

测试

单元测试(不写单元测试不准push!!)

➜  _shorturl git:(master) ✗ go test -v
=== RUN   Test_Encode
--- PASS: Test_Encode (0.00s)
=== RUN   Test_Decode
--- PASS: Test_Decode (0.00s)
=== RUN   Test_ProcessEncodeThenDecode
--- PASS: Test_ProcessEncodeThenDecode (0.00s)
=== RUN   Test_SetUrlCache
--- PASS: Test_SetUrlCache (0.01s)
=== RUN   Test_LoadConfig
--- PASS: Test_LoadConfig (0.00s)
=== RUN   Test_GetInstance
--- PASS: Test_GetInstance (0.00s)
=== RUN   Test_Insert
--- PASS: Test_Insert (0.08s)
=== RUN   Test_QueryUrl
--- PASS: Test_QueryUrl (0.02s)
=== RUN   Test_Update
--- PASS: Test_Update (0.00s)
=== RUN   Test_RegRouter
--- PASS: Test_RegRouter (0.00s)
=== RUN   Test_ShortenAndParse
2018/02/01 11:23:28 deal with url:  http://www.baidu.com
--- PASS: Test_ShortenAndParse (0.02s)
=== RUN   Test_ConnectDB
--- PASS: Test_ConnectDB (0.00s)
=== RUN   Test_GetDB
--- PASS: Test_GetDB (0.00s)
=== RUN   Test_CloseConnection
--- PASS: Test_CloseConnection (0.00s)
PASS
ok  	shorturl/_shorturl	0.157s

功能测试

{% dplayer “url=/mov/演示短链接功能.mov” “loop=no” “theme=#FADFA3” “autoplay=false” “token=tokendemo” %}

性能测试

未使用分布式测试结果截图如下(没有达到最大吞吐量): Wrk性能测试结果

存储选用

选择Mysql用于存储数据,Redis作为缓存。

源码

github.com/yeqown/shorturl