URL简化

[zshuangyan]

Requirements

假设我们要做一个功能，支持把用户输入的URL映射成我们网站根域名下的子路径，子路径的长度有限制——最长只能有6个字符。现在要支持URL个数范围为[1, 100,000,000,000)。

Version 1.0

针对这个问题，如果不约束子路径的长度，那么直接把原始的URL作为子路径即可，不需要做任何额外的操作，但是这种情况也没有对URL的任何简化。

如果要简化URL，我们首先想到的是把用户输入的URL保存到MySQL数据库中，然后返回数据库中的自增ID，把自增ID作为子路径。简化的目标是达到了，但是用十进制来表示上面的数量级至少需要11个字符。

Version 1.1

那么问题就是，如果要使用6位来表达[0，100,000,000,000)之间的数字，每一位应该是多少进制呢？估算了一下，发现每一位至少要能够表达47个不同的值。

我们知道英文有26个字母，如果包含大小写形式那么可以有52个不同的可能，对于上述的要求是足够了的（如果我们想表达更大的数量级，可以把数字也进来）。

因此我们就可以使用6个ascii字符来映射100,000,000,000种不同的URL了，如果不考虑存储空间限制，我们可以直接保存映射关系到Redis数据库中，支持高效的插入和删除操作。

Version 1.2

但是我们要考虑到保存100,000,000,000个字符串到redis数据库中占据的空间大小，假设原始URL最大长度为10个字符，不计算其他额外开销，仅仅用来保存这些字符内容就需要(6+10)*100,000,000,000字节，大约为1.6TB，我们都知道内存是非常昂贵的，目前大多数主机能支持的内存只能达到G的数量级，因此排除使用基于内存来存储映射关系。

我们可以把映射关系存储到关系型数据库MySQL集群中，利用MySQL数据库的分片机制实现分布式存储来解决存储空间不够的问题。

Version 1.3

如果我们直接把简化的URL和原始的URL存储在MySQL的一张表中url_map(short_url char(6) primary key, origin_url varchar(30))，通过简化的URL查询原始的URL是比较慢的，即使查询过程中使用了B树索引，查询的复杂度也是O(log(100,000,000,000))的级别。

我们知道INT类型的主键的查找效率是远远高于字符串类型的主键的，如果我们可以找到一种方法，可以把INT类型和6位字符进行高效的可逆运算，就可以极大地减少查询范围了。 1）当我们要保存新的URL时，直接把它插入到表中，然后得到自增主键ID，利用ID的值来生成对应的简化URL并返回给用户 2）当用户根据简化的URL查找原始的URL时，把简化URL计算成数据库的ID，然后使用ID在数据库中查找到原始的URL返回给用户

我们知道怎样把10进制转化为16进制，那么把十进制转化为52进制也是同样的道理。

import string
char_space = string.ascii_letters
decimal = len(char_space)

def int_to_char(n):
    return chr(n + ord("A"))

def char_to_int(c):
    return ord(c) - ord("A")

def num_to_string(num: int) -> string:
    result = []
    while num:
        value, num = num % decimal, num // decimal
        char = int_to_char(value)
        result.insert(0, char)
    return "".join(result)

def string_to_num(s: string) -> int:
    result = 0
    total_len = len(s)
    for index, c in enumerate(s):
        result += char_to_int(c) * pow(decimal, total_len - 1 - index)
    return result