短网址服务

1. 生成短网址，将原始的长网址转化为短网址
2. 访问短网址，当用户点击短网址时，重定向到原始网址

生成短网址

1. 哈希算法
   • 使用哈希算法，将长网址转化成一个固定长度的哈希值
   • 哈希算法的选择，不需要考虑反向解密，只需要关心哈希算法的计算和冲突概率，选用 MurmurHash 算法，可以得到 32 bits 或 128 bits 长度的哈希值
   • 如何让短网址更短
     • 将 MurmurHash 算法得到的哈希值，转化为更高进制的哈希值，如 62 进制，即包含了 0～9、a～z、A～Z 的 62 个字符
   • 解决哈希冲突
     • 当新的原始网址需要生成短网址的时候，先通过哈希算法得到短网址
     • 在存储数据库中查找是否已经存在此短网址，如果存在，且原始网址一样，则返回短网址，如果存在，且原始网址不一样，可以将原始网址后拼接一个特殊字符串，再计算哈希值，如果仍旧冲突，则换一个拼接字符串继续尝试
   • 优化
     • 可以借助数据库的唯一索引，来减少从数据库中获取原始网址的次数，当出现唯一索引冲突时，再去执行“查询、写入”的过程
     • 使用布隆过滤器来判断短网址是否有冲突
2. ID 生成器
   • 通过维护一个 ID 自增生成器，生成原始网址对应的自增 ID，再转化为 62 进制，并将短网址和对应的原始网址存储在数据库中
   • 优化

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

       • 不做处理
       • 当需要生成短网址时，现在数据库中查找原始网址是否已经存在，如果存在则直接返回之前生成的短网址，在数据库中对原始网址、短网址都添加索引

     • 提高 ID 生成器的性能

       • 利用数据库的自增字段
       • ID 生成器添加多个前置发号器，给多个前置发号器发送 ID 号码，当接收到短网址生成请求时，选择某一个前置发号器来生成号码

       

     • 多个 ID 生成器同时服务，每个 ID 生成器按照一定的规则生成 ID 号码