短链系统设计-存储设计

女爷i 2024-04-07 15:29 115阅读 0赞

### 3 Storage 数据存取（最能体现实践经验） ###

1.  select 选存储结构
2.  scheme 细化数据表

#### 3.1 SQL V.S NoSQL ####

需要事务吗？No，nosql+1

需要丰富的 sql query 吗？no，nosql+1

想偷懒吗?tiny url需要写的代码不复杂，nosql+1

qps高吗？2k，不高。sql+1

scalability 要求多高？存储和 qps 都不高，单机都能搞定。sql+1

- sql 需要自己写代码来 scale
    - nosql，这些都帮你做了

是否需要 sequential ID？取决于你的算法

*  sql 提供 auto\_increment 的 sequencetial ID，即 1,2,3
 *  nosql 的 ID 不是 sequential

#### 3.2 算法 ####

long ur 转成一个 6 位的 short url。给出一个长网址，返回一个短网址。

实现两个方法：

*  `longToShort(url)` 把一个长网址转换成一个以`http://tiny.url/`开头的短网址
 *  `shortToLong(url)` 把一个短网址转换成一个长网址

标准：

1.  短网址的key的长度应为6 （不算域名和反斜杠）。 可用字符只有 `[a-zA-Z0-9]`. 比如: `abcD9E`
2.  任意两个长的url不会对应成同一个短url，反之亦然。

用两个哈希表：

*  一个是短网址映射到长网址
 *  一个是长网址映射到短网址

短网址是固定的格式: “http://tiny.url/” + 6个字符, 字符可任意。

为避免重复, 我们可以按照字典序依次使用, 或者在随机生成的基础上用一个集合来记录是否使用过。

##### 使用哈希函数（不可行） #####

如取 long url的 MD5 的最后 6 位：

*  快
 *  难以设计一个无哈希冲突的哈希算法

##### 随机生成 shortURL+DB去重 #####

随机取一个 6 位的 shortURL，若没使用过，就绑定到改 long url。

public String long2Short(String url) {
        
      while(true) {
        
        String shortURL = randomShortURL();
        if (!databse.filter(shortURL=shortURL).exists()) {
        
          database.create(shortURL=shortURL, longURL=url);
          return shortURL;
        }
      }
      
    }
    
    public class TinyUrl {
        
        
        public TinyUrl() {
        
            long2Short = new HashMap<String, String>();
            short2Long = new HashMap<String, String>();
        }
    
        /**
         * @param url a long url
         * @return a short url starts with http://tiny.url/
         */
        public String longToShort(String url) {
        
            if (long2Short.containsKey(url)) {
        
                return long2Short.get(url);
            }
    
            while (true) {
        
                String shortURL = generateShortURL();
                if (!short2Long.containsKey(shortURL)) {
        
                    short2Long.put(shortURL, url);
                    long2Short.put(url, shortURL);
                    return shortURL;
                }
            }
        }
    
        /**
         * @param url a short url starts with http://tiny.url/
         * @return a long url
         */
        public String shortToLong(String url) {
        
            if (!short2Long.containsKey(url)) {
        
                return null;
            }
    
            return short2Long.get(url);
        }
    
        private String generateShortURL() {
        
            String allowedChars = "0123456789" + "abcdefghijklmnopqrstuvwxyz" + "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    
            Random rand = new Random();
            String shortURL = "http://tiny.url/";
            for (int i = 0; i < 6; i++) {
        
                int index = rand.nextInt(62);
                shortURL += allowedChars.charAt(index);
            }
    
            return shortURL;
        }
    }

优点：实现简单

缺点：生成短链接的速度，随着短链接越多而越慢

关系型数据库表：只需Short key和 long url两列，并分别建立索引

也可使用 nosql，但需要建立两张表：

*  根据 long 查询 short  
    key=longurl 列=shorturl value=null or timestamp
 *  根据 short 查询 long  
    key=shorturl 列=longurl value=null or timestamp  
    ![86909cb3afbd434b9c680d58683a2068.png][]  
    ![846199b122a14acebc814c9a1ad4dd7a.png][]

##### 进制转换 Base32(微博实现方案) #####

Base62：

*  将 6 位 short url 看做一个 62 进制数（0-9,a-z,A-Z）
 *  每个 short url 对应到一个整数
 *  该整数对应 DB 表的主键

6 位可表示的不同 URL：

*  5 位 = 62^5=0.9B= 9亿
 *  6 位 = 62^6=57B= 570亿
 *  7 位 = 62^7=3.5T= 35000亿

优点：效率高

缺点：强依赖于全局的自增 id

public class TinyUrl {
        
        public static int GLOBAL_ID = 0;
        private HashMap<Integer, String> id2url = new HashMap<Integer, String>();
        private HashMap<String, Integer> url2id = new HashMap<String, Integer>();
    
        private String getShortKey(String url) {
        
            return url.substring("http://tiny.url/".length());
        }
    
        private int toBase62(char c) {
        
            if (c >= '0' && c <= '9') {
        
                return c - '0';
            }
            if (c >= 'a' && c <= 'z') {
        
                return c - 'a' + 10;
            }
            return c - 'A' + 36;
        }
    
        private int shortKeytoID(String short_key) {
        
            int id = 0;
            for (int i = 0; i < short_key.length(); ++i) {
        
                id = id * 62 + toBase62(short_key.charAt(i));
            }
            return id;
        }
    
        private String idToShortKey(int id) {
        
            String chars = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
            String short_url = "";
            while (id > 0) {
        
                short_url = chars.charAt(id % 62) + short_url;
                id = id / 62;
            }
            while (short_url.length() < 6) {
        
                short_url = "0" + short_url;
            }
            return short_url;
        }
    
        /**
         * @param url a long url
         * @return a short url starts with http://tiny.url/
         */
        public String longToShort(String url) {
        
            if (url2id.containsKey(url)) {
        
                return "http://tiny.url/" + idToShortKey(url2id.get(url));
            }
            GLOBAL_ID++;
            url2id.put(url, GLOBAL_ID);
            id2url.put(GLOBAL_ID, url);
            return "http://tiny.url/" + idToShortKey(GLOBAL_ID);
        }
    
        /**
         * @param url a short url starts with http://tiny.url/
         * @return a long url
         */
        public String shortToLong(String url) {
        
            String short_key = getShortKey(url);
            int id = shortKeytoID(short_key);
            return id2url.get(id);
        }
    }

因为要用到自增 id，所以只能用关系型 DB 表：

id主键、long url（索引）

[86909cb3afbd434b9c680d58683a2068.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/32676858ca60483297da2b2bd731ed33.png
[846199b122a14acebc814c9a1ad4dd7a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/926c139491994cf982a4faf9662fab07.png