1
如何实现一个短地址服务
source link: http://blog.pingvim.com/%E7%9F%AD%E5%9C%B0%E5%9D%80%E6%9C%8D%E5%8A%A1/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
如何实现一个短地址服务
短网址服务经常会用到，这是一个看似简单，但内含不少小技巧的服务，想要做好可不太容易。
哈希算法：短网址服务需要重点考虑的问题是哈希算法的计算速度和冲突概率，MurmurHash 算法是一个应用比较广泛的哈希算法，可以选择这个算法
如何更短：将哈希算法随机生成的数字转换为62进制的值，62进制可以用[0-9a-zA-Z]表示，最终生成的链接会更短
如何解决哈希冲突
- 首先从数据库中查询原始网址和短网址的对应关系
- 如果短网址冲突，那么再比较原始网址是否相同
- 如果相同，说明已经生成过，可以直接返回这个短网址
- 如果不同我们可以对原始网址拼接一个特定的字符串标识，进行再次的哈希计算，拿到一个新的短网址存储下来，这样计算哈希冲突的概率是非常低的，取用的时候将特殊字符去掉即可
如何优化哈希算法生成短网址的性能
- 性能损耗的点：冲突查找，加索引加快查找速度即可
- 在大多数时候，哈希计算并不会出现冲突，并且短网址是唯一的，这个时候就可以加唯一索引，不检查是否冲突，直接插入数据，报错捕获后再进行查找处理，这样可以减少大量的查询操作
- 还可以使用布隆过滤器来实现短网址是否冲突的查找操作，十亿的布隆过滤器占用空间也就是125M左右内存空间
使用自增id生成短网址
- 相同的原始网址可能会对应不同的短网址，不想出现这种状况就需要去库里面查询，短网址和原始网址都需要加索引，查到之后将已经生成的短网址返回
- 使用高性能的id生成器
- 给id生成器装多个前置发号器，不断批量的给发号器发送id号码，来应对并发的访问
- 使用多个id生成器，为了保证id不重复，每个生成器的生成规则要略有不同
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK