共计 7181 个字符，预计需要花费 18 分钟才能阅读完成。
作者：rickiyang
www.cnblogs.com/rickiyang/p/12178644.html
短链接，艰深来说，就是将长的 URL 网址，通过程序计算等形式，转换为简短的网址字符串。
大家常常会收到一些莫名的营销短信，外面有一个十分短的链接让你跳转。新浪微博因为限度字数，所以也会常常见到这种看着不像网址的网址。短链的衰亡应该就是微博限度字数激发了大家的创造力。
如果创立一个短链零碎，咱们应该做什么呢？
- 将长链接变为短链；
- 用户拜访短链接，会跳转到正确的长链接下来。
查找到对应的长网址，并跳转到对应的页面。
短链生成办法
短码个别是由 [a - z, A - Z, 0 - 9] 这 62 个字母或数字组成，短码的长度也能够自定义，但个别不超过 8 位。比拟罕用的都是 6 位，6 位的短码曾经能有 568 亿种的组合：(26+26+10)^6 = 56800235584，已满足绝大多数的应用场景。
目前比拟风行的生成短码办法有：自增 id、摘要算法 、 一般随机数。分布式 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 的算法：摘要算法。
实现
存储计划
数据库存储计划
短网址根底数据采纳域名和后缀离开存储的模式。另外域名须要辨别 HTTP 和 HTTPS，hash 计划针对整个链接进行 hash 而不是除了域名外的链接。域名独自保留能够用于剖析以后域名下链接的应用状况。
减少以后链接有效期字段，个别有短链需要的可能是相干流动或者热点事件，这种短链在一段时间内会很沉闷，过了肯定工夫热潮会继续消退。所以没有必要将这种链接永恒保留减少每次查问的累赘。
对于过期数据的解决，能够在新增短链的时候判断以后短链的生效日期，将每天达到生效日期的数据在 HBase 独自建一张表，有新增的时候判断生效日期放到对应的 HBase 表中即可，每天只用解决当天 HBase 表中的生效数据。
数据库根底表如下:
字段释义：
base_url：域名
suffix_url：链接除了域名外的后缀
full_url：残缺链接
shot\_code：以后 suffix\_url 链接的短码
expiration_date：生效日期
total\_click\_count：以后链接总点击次数
expiration_date：以后链接生效工夫
缓存计划
- 查问需要
集体认为对于几百个 G 的数据量都放在缓存必定是不适合的，所以有个折中的计划：将最近 3 个月内有查问或者有新增的 url 放入缓存，应用 LRU 算法进行热更新。这样最近有应用的发概率会命中缓存，就不必走库。查不到的时候再走库更新缓存。
- 新增需要
对于新增的链接就先查缓存是否存在，缓存不存在再查库，数据库曾经分表了，查问的效率也不会很低。
- 缓存的设计
查问的需要是用户拿着短链查问对应的实在地址，那么缓存的 key 只能是短链，能够应用 KV 的模式存储。
番外
其实也能够思考别的存储计划，比方 HBase，HBase 作为 NOSQL 数据库，性能上仅次于 redis 然而存储老本比 redis 低很多个数量级，存储基于 HDFS，写数据的时候会先先写入内存中，只有内存满了会将数据刷入到 HFile。
关注微信公众号：Java 技术栈，在后盾回复：redis，能够获取我整顿的 N 篇最新 Redis 教程，都是干货。
读数据也会快，起因是因为它应用了 LSM 树型构造，而不是 B 或 B+ 树。HBase 会将最近读取的数据应用 LRU 算法放入缓存中，如果想加强读能力，能够调大 blockCache。
其次，也能够应用 ElasticSearch，适合的索引规定成果不输缓存计划。
是否有分库分表的须要？
对于单条数据 10b 以内，一亿条数据总容量大概为 953G，单表必定无奈撑住这么大的量，所以有分表的须要，如果你对服务很有信念 2 年内能达到这个规模，那么你能够从一开始设计就思考分表的计划。举荐：大厂在用的分库分表计划，看这篇就够了。
那么如何定义分表的规定呢？
如果依照单表 500 万条记录来算，总计能够分为 20 张表，那么单表容量就是 47G，还是挺大，所以思考分表的 key 和单表容量，如果分为 100 张表那么单表容量就是 10G，并且通过数字后缀路由到表中也比拟容易。能够对 short_code 做 encoding 编码生成数字类型而后做路由。
如何转跳
当咱们在浏览器里输出 http://bit.ly/a3300 时
- DNS 首先解析取得 http://bit.ly 的
IP地址 - 当
DNS取得IP地址当前（比方：12.34.5.32），会向这个地址发送HTTP`GET申请，查问短码a3300` - [http://bit.ly 服务器会通过短码
a3300获取对应的长 URL - 申请通过
HTTP 301转到对应的长 URL http://www.theaustralian.news…
这里有个小的知识点，为什么要用 301 跳转而不是 302 呐？
知识点：为什么要应用 302 跳转，而不是 301 跳转呢？
301 是永恒重定向，302 是长期重定向。短地址一经生成就不会变动，所以用 301 是合乎 http 语义的。然而如果用了 301，Google，百度等搜索引擎，搜寻的时候会间接展现实在地址，那咱们就无奈统计到短地址被点击的次数了，也无奈收集用户的 Cookie, User Agent 等信息，这些信息能够用来做很多有意思的大数据分析，也是短网址服务商的次要盈利起源。
引自：https://www.zhihu.com/questio…
附上两个算法：
摘要算法：
import org.apache.commons.lang3.StringUtils;
import javax.xml.bind.DatatypeConverter;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.concurrent.atomic.AtomicLong;
import static com.alibaba.fastjson.util.IOUtils.DIGITS;
/**
* @author rickiyang
* @date 2020-01-07
* @Desc TODO
*/
public class ShortUrlGenerator {public static void main(String[] args) {
String sLongUrl = "http://www.baidu.com/121244/ddd";
for (String shortUrl : shortUrl(sLongUrl)) {System.out.println(shortUrl);
}
}
public static String[] shortUrl(String url) {
// 能够自定义生成 MD5 加密字符传前的混合 KEY
String key = "dwz";
// 要应用生成 URL 的字符
String[] chars = new 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"
};
// 对传入网址进行 MD5 加密
String sMD5EncryptResult = "";
try {MessageDigest md = MessageDigest.getInstance("MD5");
md.update((key + url).getBytes());
byte[] digest = md.digest();
sMD5EncryptResult = DatatypeConverter.printHexBinary(digest).toUpperCase();} catch (NoSuchAlgorithmException e) {e.printStackTrace();
}
String[] resUrl = new String[4];
// 失去 4 组短链接字符串
for (int i = 0; i < 4; i++) {
// 把加密字符依照 8 位一组 16 进制与 0x3FFFFFFF 进行位与运算
String sTempSubString = sMD5EncryptResult.substring(i * 8, i * 8 \+ 8);
// 这里须要应用 long 型来转换，因为 Inteper .parseInt() 只能解决 31 位 , 首位为符号位 , 如果不必 long，则会越界
long lHexLong = 0x3FFFFFFF & Long.parseLong(sTempSubString, 16);
String outChars = "";
// 循环取得每组 6 位的字符串
for (int j = 0; j < 6; j++) {// 把失去的值与 0x0000003D 进行位与运算，获得字符数组 chars 索引(具体须要看 chars 数组的长度 以防下标溢出，留神终点为 0)
long index = 0x0000003D & lHexLong;
// 把获得的字符相加
outChars += chars[(int) index];
// 每次循环按位右移 5 位
lHexLong = lHexLong >> 5;
}
// 把字符串存入对应索引的输入数组
resUrl[i] = outChars;
}
return resUrl;
}
}数字转为 base62 算法：
/**
* @author rickiyang
* @date 2020-01-07
* @Desc TODO
* <p>
* 进制转换工具，最大反对十进制和 62 进制的转换
* 1、将十进制的数字转换为指定进制的字符串；* 2、将其它进制的数字（字符串模式）转换为十进制的数字
*/
public class NumericConvertUtils {public static void main(String[] args) {String str = toOtherNumberSystem(22, 62);
System.out.println(str);
}
/**
* 在进制示意中的字符汇合，0- Z 别离用于示意最大为 62 进制的符号示意
*/
private static final char[] digits = {'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',
'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'};
/**
* 将十进制的数字转换为指定进制的字符串
*
* @param number 十进制的数字
* @param seed 指定的进制
* @return 指定进制的字符串
*/
public static String toOtherNumberSystem(long number, int seed) {if (number < 0) {number = ((long) 2 \* 0x7fffffff) \+ number + 2;
}
char[] buf = new char[32];
int charPos = 32;
while ((number / seed) > 0) {buf[--charPos] = digits[(int) (number % seed)];
number /= seed;
}
buf[--charPos] = digits[(int) (number % seed)];
return new String(buf, charPos, (32 \- charPos));
}
/**
* 将其它进制的数字（字符串模式）转换为十进制的数字
*
* @param number 其它进制的数字（字符串模式）* @param seed 指定的进制，也就是参数 str 的原始进制
* @return 十进制的数字
*/
public static long toDecimalNumber(String number, int seed) {char[] charBuf = number.toCharArray();
if (seed == 10) {return Long.parseLong(number);
}
long result = 0, base = 1;
for (int i = charBuf.length - 1; i >= 0; i--) {
int index = 0;
for (int j = 0, length = digits.length; j < length; j++) {
// 找到对应字符的下标，对应的下标才是具体的数值
if (digits[j] == charBuf[i]) {index = j;}
}
result += index * base;
base *= seed;
}
return result;
}
}近期热文举荐：
1.600+ 道 Java 面试题及答案整顿(2021 最新版)
2. 终于靠开源我的项目弄到 IntelliJ IDEA 激活码了，真香！
3. 阿里 Mock 工具正式开源，干掉市面上所有 Mock 工具！
4.Spring Cloud 2020.0.0 正式公布，全新颠覆性版本！
5.《Java 开发手册（嵩山版）》最新公布，速速下载！
感觉不错，别忘了顺手点赞 + 转发哦！
