算法 - 如何实现短网址服务

如何实现短网址服务

哈希法

大致思路：对原始网址求哈希值，把这个哈希值作为key，原始网址作为value存在redis或数据库中。用户访问短网址的时候，到库中找，然后302重定向到原始网址。

用什么哈希算法？

你可以用SHA256、MD5、java的String#hashCode都可以。比较著名的是MurmurHash3算法。MurmurHash比SHA和MD5性能高，因为它是非密码学算法，它可以产生32bit和128bit两种哈希值。

如何把哈希值转换成短网址？

虽然你可以采用32bit的版本得到一个int，直接把这个作为短网址，比如shorturl.cn/181338494，但是这样还不够短，可以把把十进制转换成十六进制，也可以转换成62进制，用52个大小写英文字母 + 10个数字来表示。算法代码看进制转换。

哈希值冲突了怎么办？

分析冲突的原因：

1）一种原因，用户用同样的原始网址求了两次短网址，那么哈希值肯定会冲突。解决思路有两个：

• 不管它，冲突消解，生成个新的短网址。优点是简单，容易缺点被攻击，浪费哈希槽位。
• 每次都到redis或数据库中取一下，如果存在那么对比原始网址是否一样，如果一样就直接返回之前的短网址，如果不一样就冲突消解。

2）另一个原因，就是两个不同的原始字符串的哈希值冲突了，没二话直接冲突消解。

冲突消解的思路？

有两个思路：

1. （不推荐）采用开放寻址法，哈希值是32bit也就是一个int，那么把int++，看看有没有冲突。这个方法比较简单，缺点是要避免位溢出变成负数，占用了别人的位置了，哈希的分布不均匀，容易导致需要消解几次冲突。
2. 追加特殊字符，在原始网址后面加上程序自己识别的字符，比如[DUP]，对其取哈希，看看有没有冲突。如果再有冲突则换一个特殊字符[DUP_AGAIN]。这个方法也简单，基本上第一次冲突就消解了，极个别的需要两次。

如何提升服务的性能？

按照追加特殊字符的冲突消解的代码大致如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func shortify(url string) string {
  for  {
    shorturl := hash(url)
    if store.exists(shorturl) {
      existedUrl := store.get(shorturl)
      if existedUrl == url {
        return shorturl
      }
      url = resolveConflict(url) // 修改url追加特殊字符
      continue
    }
    store.save(shorurl, url)
    return shorturl
  }
}

可以看到整个过程必须查询一次store.exists(shorturl)再保存一次store.save(shorturl, url)

如何减少每次判断？

1）可以利用redis的SETNX和数据库中添加唯一索引让这个过程变得只有一次：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

func shortify(url string) string {
  for  {
    shorturl := hash(url)
    if store.save(shorurl, url) {
      return shorturl
    }
    existedUrl := store.get(shorturl)
    if existedUrl == url {
      return shorturl
    }
    url = resolveConflict(url) // 修改url追加特殊字符    
  }
}

2）可以利用布隆过滤器，布隆过滤器是比较节省内存的一种存储结构，长度是 10 亿的布隆过滤器，也只需要 125MB 左右的内存空间。

自增ID法

数据库中自增ID生成作为短网址。

相同的原始网址可能会对应不同的短网址

解决思路：

1. 不解决。反正用户关心的是能够跳转到原始网址。
2. 和哈希法一样，到数据库中查询一下原始网址是否已经有短网址了。在数据库中需要给原始网址和短网址都加上索引，多一个索引会增加性能开销。对于redis来说则是建两套key，一个是 shorturl -> longurl 的，一个是 longurl -> shorturl 的。

如何实现高性能的 ID 生成器？

因为ID不能重复，必须自增，那么它就会加锁，这样会影响性能。

解决思路：

1. 多个ID生成器，每个都有一个号段，号段问一个号段管理器要。号段用完了再要新的号段。这样可以增加并发效率。
2. 多个ID生辰器，他们天然就不会生成相同的ID，比如一个只生成尾号为0的，一个只生成尾号为1的。再比如Twitter的雪花算法。