如何设计Tiny URL

谁践踏了优雅 2022-12-08 14:10 111阅读 0赞

### 文章目录 ###

*   *   *   *  （一）核心
             *  （二）应用举例
             *  （三）短链接的运行原理
             *   *   *  （1）基本运行过程
                     *  （2）301和302的选择
             *  （四）算法设计
             *   *   *  哈希
                     *  哈希冲突
                     *  设计优化
                     *  分布式ID
             *  （五）应用实例

#### （一）核心 ####

1：为什么要设计短链，好处  
2：算法设计选择  
3：将长的URL变短并存储  
4：查找短的URL还原

#### （二）应用举例 ####

1：百度网盘

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L09jdG9wdXMyMQ_size_16_color_FFFFFF_t_70_pic_center]

2：微博发文  
微博发文会限制字数，如果你想要分享几个链接，要是链接都跟下面这样那么就只发俩个链接就不能再写其他文字呢  
![在这里插入图片描述][20200919164157304.png_pic_center]

3：短信  
在一个群发短信的应用里，如果需要写入多个长链接的话而且有需要额外的一些配字，本来一条短信就可以解决的事结果需要发送多条才可以写完，这无疑是浪费资金

#### （三）短链接的运行原理 ####

###### （1）基本运行过程 ######

1：选择一个长链接  
2：将长链接通过短链接服务器生成对应的短链接，此时拿到的短链接格式：  
![在这里插入图片描述][20200919164228557.png_pic_center]  
TinyURL基本格式：短链接服务器域名+随机字符

3：通过短链接进行访问，实际上就是先访问短链接服务器，短链接服务根据拿到的URL请求去数据库中查询对应的长链接，然后进行重定向到长链接的地址

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L09jdG9wdXMyMQ_size_16_color_FFFFFF_t_70_pic_center 1][]

4：此时成功访问到原长链接对应的URL数据地址

###### （2）301和302的选择 ######

301表示的永久跳转，它会存在本地浏览器缓存，减少了服务端的访问压力

302表示的临时跳转，它会存储在服务器端，虽然加大了服务器端压力，但是影响不会很大，资源消耗不会太大

如果使用了301，我们就无法统计到短地址被点击的次数了。而这个点击次数是一个非常有意思的大数据分析数据源。能够分析出的东西非常非常多。所以选择302虽然会增加服务器压力，但是或许是一个更好的选择。

#### （四）算法设计 ####

###### 哈希 ######

Murmur Hash

Murmur哈希是一种非加密散列函数，适用于一般的基于散列的查找。它在2008年由Austin Appleby创建，在Github上托管，名为“SMHasher” 的测试套件。 它也存在许多变种，所有这些变种都已经被公开。 该名称来自两个基本操作，乘法（MU）和旋转（R），在其内部循环中使用。  
与加密散列函数不同，它不是专门设计为难以被对手逆转，因此不适用于加密目的。

特点：  
1：非加密，则所需要做的计算就更好性能也会更好  
2：随机分布性更好

###### 哈希冲突 ######

1：将长链根据选择的哈希算法得到短链  
2：将得到的短链去表（DBMS、NoSQL）进行查询看是否有已存在的短链  
3：如果不存在相同的短链则将直接将当前短链和长链存储映射到表上即可  
4：如果已存在相同的短链，此时可以将长链拼接一个额外的字符串再次进行哈希算法得到短链，然后再次进行映射查询  
5：如果还有重复则继续拼接字符串映射知道不存在重复短链则执行插入，在进行插入到数据表中时需要把拼接的字符串移除，保存原有的长链

###### 设计优化 ######

索引  
对短链设置唯一索引，提高查询匹配的效率

布隆过滤器  
如果数据量较大，按照上面的方式需要多次查询数据库影响性能，可以通过布隆过滤器工具来帮助我们提高查询性能，比如Google的Guava就有成熟的布隆过滤器的实现，在进行数据库短链查重之前，我们先通过布隆过滤器进行筛选，这样虽然需要一些空间内存来布隆过滤器但是内存消耗不会很大，而且对于整体的性能提升是很好的

###### 分布式ID ######

Redis序列  
使用Redis构建自增ID，对于这种方式来说性能好速度快，对于压力过大可以进行水平扩展即增加机器，假如现在部署了10个Redis实例，那么每个Redis可以按照0,1,2,3…9的尾号来进行序列生成，每个Redis实例以10为单位进行迭代。Redis存储需要考虑到持久化的问题还有灾备问题处理。

SnowFlake  
Twitter的SnowFlake是一种应用广泛的分布式id生成算法。雪花算法生成的ID是趋势递增，不依赖数据库等第三方系统，以服务的方式部署，稳定性更高，生成ID的性能也是非常高的，而且可以根据自身业务特性分配bit位，非常灵活。  
但是雪花算法强依赖机器时钟，如果机器上时钟回拨，会导致发号重复或者服务会处于不可用状态。如果恰巧回退前生成过一些ID，而时间回退后，生成的ID就有可能重复。官方对于此并没有给出解决方案，而是简单的抛错处理，这样会造成在时间被追回之前的这段时间服务不可用。

#### （五）应用实例 ####

使用分布式ID的方式生成长串数字，然后转换为\[a-zA-Z0-9\]组合字符串，即62位进制转换

核心：  
生成一个全局唯一的数字和实现进制的转换

代码实例参考

public class TinyURL { 
    
        public static final char[] array =
                { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
                        'q', 'w', 'e', 'r', 't', 'y', 'u', 'i', 'o', 'p', 'a', 's', 'd',
                        'f', 'g', 'h', 'j', 'k', 'l', 'z', 'x', 'c', 'v', 'b', 'n', 'm',
                        'Q', 'W', 'E', 'R', 'T', 'Y', 'U', 'I', 'O', 'P', 'A', 'S', 'D',
                        'F', 'G', 'H', 'J', 'K', 'L', 'Z', 'X', 'C', 'V', 'B', 'N', 'M'};
    
        public static Map<Character, Integer> charValueMap = new HashMap<Character, Integer>();
    
        //初始化map
        static { 
            for (int i = 0; i < array.length; i++) charValueMap.put(array[i], i);
        }
    
    
        public static void main(String[] args) { 
            for (int i = 0; i < 100; i++) { 
                long number = Long.MAX_VALUE - i;
                String decimalStr = numberConvertToDecimal(number, 62);
                System.out.println(number  + " 转换成 " + decimalStr);
                long toNumber = decimalConvertToNumber(decimalStr, 62);
                System.out.println(decimalStr + " 转换成 " + toNumber);
            }
        }
    
    
        /** * 把数字转换成相对应的进制,目前支持(2-62)进制 * * @param number 分布式ID * @param decimal 进制 * @return 短链后缀字符串 */
        public static String numberConvertToDecimal(long number, int decimal) { 
            StringBuilder builder = new StringBuilder();
            while (number != 0) { 
                builder.append(array[(int) (number - (number / decimal) * decimal)]);
                number /= decimal;
            }
            return builder.reverse().toString();
        }
    
        /** * 把进制字符串转换成相应的数字 * @param decimalStr 短链后缀字符串 * @param decimal 进制 * @return 原分布式ID */
        public static long decimalConvertToNumber(String decimalStr, int decimal) { 
            long sum = 0;
            long multiple = 1;
            char[] chars = decimalStr.toCharArray();
            for (int i = chars.length - 1; i >= 0; i--) { 
                char c = chars[i];
                sum += charValueMap.get(c) * multiple;
                multiple *= decimal;
            }
            return sum;
        }
    
    
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L09jdG9wdXMyMQ_size_16_color_FFFFFF_t_70_pic_center 2]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L09jdG9wdXMyMQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/35bf4a41796a454bbac6c61af69511ce.png
[20200919164157304.png_pic_center]: /images/20221123/ccd2cc9519f24f1db639138a90dd0332.png
[20200919164228557.png_pic_center]: /images/20221123/5519b0849451460abe2f1db6403ab564.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L09jdG9wdXMyMQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/c9910953e5694ce1aff85c461320b4f7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L09jdG9wdXMyMQ_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/f95516c9414949638ea73750c0d488b0.png