如何实现一个短链接服务

如何实现一个短链接服务

短链接，通俗来说，就是将长的URL网址，通过程序计算等方式，转换为简短的网址字符串。
大家经常会收到一些莫名的营销短信，里面有一个非常短的链接让你跳转。新浪微博因为限制字数，所以也会经常见到这种看着不像网址的网址。短链的兴起应该就是微博限制字数激起了大家的创造力。
如果创建一个短链系统，我们应该做什么呢？

将长链接变为短链；
用户访问短链接，会跳转到正确的长链接上去。

查找到对应的长网址，并跳转到对应的页面。

短链生成方法

短码一般是由[a - z, A - Z, 0 - 9]这62 个字母或数字组成，短码的长度也可以自定义，但一般不超过8位。比较常用的都是6位，6位的短码已经能有568亿种的组合：(26+26+10)^6 = 56800235584，已满足绝大多数的使用场景。
目前比较流行的生成短码方法有：自增id、摘要算法、普通随机数。

自增id

该方法是一种无碰撞的方法，原理是，每新增一个短码，就在上次添加的短码id基础上加1，然后将这个10进制的id值，转化成一个62进制的字符串。
一般利用数据表中的自增id来完成：每次先查询数据表中的自增id最大值max，那么需要插入的长网址对应自增id值就是 max+1，将max+1转成62进制即可得到短码。
但是短码 id 是从一位长度开始递增，短码的长度不固定，不过可以用 id 从指定的数字开始递增的方式来处理，确保所有的短码长度都一致。同时，生成的短码是有序的，可能会有安全的问题，可以将生成的短码id，结合长网址等其他关键字，进行md5运算生成最后的短码。

摘要算法

摘要算法又称哈希算法，它表示输入任意长度的数据，输出固定长度的数据。相同的输入数据始终得到相同的输出，不同的输入数据尽量得到不同的输出。
算法过程：

将长网址md5生成32位签名串,分为4段, 每段8个字节；
对这四段循环处理, 取8个字节, 将他看成16进制串与0x3fffffff(30位1)与操作, 即超过30位的忽略处理；
这30位分成6段, 每5位的数字作为字母表的索引取得特定字符, 依次进行获得6位字符串；
总的md5串可以获得4个6位串；取里面的任意一个就可作为这个长url的短url地址；

这种算法,虽然会生成4个,但是仍然存在重复几率。
虽然几率很小，但是该方法依然存在碰撞的可能性，解决冲突会比较麻烦。不过该方法生成的短码位数是固定的，也不存在连续生成的短码有序的情况。

普通随机数

该方法是从62个字符串中随机取出一个6位短码的组合，然后去数据库中查询该短码是否已存在。如果已存在，就继续循环该方法重新获取短码，否则就直接返回。
该方法是最简单的一种实现，不过由于Math.round()方法生成的随机数属于伪随机数，碰撞的可能性也不小。在数据比较多的情况下，可能会循环很多次，才能生成一个不冲突的短码。

算法分析

以上算法利弊我们一个一个来分析。
如果使用自增id算法，会有一个问题就是不法分子是可以穷举你的短链地址的。原理就是将10进制数字转为62进制，那么别人也可以使用相同的方式遍历你的短链获取对应的原始链接。打个比方说：http://tinyurl.com/a3300和 http://bit.ly/a3300，这两个短链网站，分别从a3300- a3399，能够试出来多次返回正确的url。所以这种方式生成的短链对于使用者来说其实是不安全的。
摘要算法，其实就是hash算法吧，一说hash大家可能觉得很low，但是事实上hash可能是最优解。比如：http://www.sina.lt/和http://mrw.so/连续生成的url发现并没有规律，很有可能就是使用hash算法来实现。
普通随机数算法，这种算法生成的东西和摘要算法一样，但是碰撞的概率会大一些。因为摘要算法毕竟是对url进行hash生成，随机数算法就是简单的随机生成，数量一旦上来必然会导致重复。
综合以上，我选择最low的算法：摘要算法。


import (
    "crypto/md5"
    "fmt"
    "github.com/spaolacci/murmur3"
)
func Hash(data []byte) uint64 {
    return murmur3.Sum64(data)
}
func Hash32(data []byte) uint32 {
    return murmur3.Sum32(data)
}
func (Short) getShortUrl(key, url string,ct int/*冲突标记*/) string {
    //加密字符传前的混合 KEY
    // 要使用生成 URL 的字符
    // 对传入网址进行 MMH3 加密
    hash32 := Hash32([]byte(key + url))
    if ct !=0{
        hash32 = Hash32([]byte(key + url+string(i)))
    }
    // 把加密字符按照 8 位一组 16 进制与 0x3FFFFFFF 进行位与运算
    lHexLong := 0x3FFFFFFF & hash32
    outChars := ""
    //循环获得每组6位的字符串
    for j := 0; j < 6; j++ {
        // 把得到的值与 0x0000003E 这是62 进行mod运算，取得字符数组 chars 索引(具体需要看chars数组的长度   以防下标溢出，注意起点为0)
        index := lHexLong % 0x0000003E
        // 把取得的字符相加
        outChars += model.Chars[index]
        // 每次循环按位右移 5 位
        lHexLong = lHexLong >> 5
    }
    // 把字符串存入对应索引的输出数组
    return outChars + CreateShortExtra()
}
// 这块可以做分库分表设计
func CreateShortExtra() string {
    x := (getDays() / 62) % 62
    y := getDays() % 62
    return Chars[x] + Chars[y]
}
func getDays() int64 {
    yearMonthDay := time.Date(2021, 01, 01, 0, 0, 0, 0, time.Local)
    return (time.Now().Unix() - yearMonthDay.Unix()) / 3600 / 24
}
var Chars = []string{"a", "b", "c", "d", "e", "f", "g", "h",
    "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t",
    "u", "v", "w", "x", "y", "z", "0", "1", "2", "3", "4", "5",
    "6", "7", "8", "9", "A", "B", "C", "D", "E", "F", "G", "H",
    "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T",
    "U", "V", "W", "X", "Y", "Z"}

是否有分库分表的需要？

对于单条数据10b以内，一亿条数据总容量大约为 953G，单表肯定无法撑住这么大的量，所以有分表的需要，如果你对服务很有信心2年内能达到这个规模，那么你可以从一开始设计就考虑分表的方案。
那么如何定义分表的规则呢？
如果按照单表500万条记录来算，总计可以分为20张表，那么单表容量就是47G，还是挺大，所以考虑分表的 key 和单表容量，如果分为100张表那么单表容量就是10G，并且通过数字后缀路由到表中也比较容易。可以对short_code 做encoding编码生成数字类型然后做路由。

高并发？

需要考虑缓存击穿的默认页面问题。

归档技术

短服务