讨论/系统设计/请实现一个「短域名」的系统设计/
请实现一个「短域名」的系统设计

设计一个类似于 TinyURL 的服务,它是一个短域名服务,一个提供可重定向到长域名的短域名移动服务。
如果你还不了解短域名,你可以前往 TinyURL 查看其功能。

image.png

简单来说,我们需要一个一对一映射的原域名和短域名的对应,这会涉及到把数据放入数据库中。
我们应该要检查下面这些:

  • 短域名的传输开销是多少?
  • 映射函数是什么?
  • 单机器还是多机器?
展开讨论
共 8 个讨论

传输开销

我们假设我们要保存超过 1万亿 的域名。如果我们呢用 62 个字符 [AZ,az,09][A-Z, a-z, 0-9] 来保存长度为 nn 的短域名,我们总共会有 62n62^n 个不同的域名。所以我们需要让我们的域名越短越好,且能保存下我们需要数目的域名。在这种情况下,我们使用 n=7n=7,也就是短域名的长度为 7 ,大概可以保存 62762^7 ~= 3万5千亿 个域名。

基本的解法

为了简化问题,我们假设别名形式形如 http://tinyurl.com/ <alias_hash>alias_hash 是一个固定长度的字符串。
一开始,我们把所有的映射用单一的数据库保存起来。一个直接的方法是用 alias_hash 作为每一个映射的 ID ,这一步我们可以用一个长度为 7 的随机字符串产生。
因此,我们首先只需要存储 <ID, URL>。当用户输入了一个长域名 "https://leetcode-cn.com/" 系统创建一个 7 个字符的随机字符串,比如 "abcd213" 作为 ID 并将 <"abcd123", "https://leetcode-cn.com/"> 插入数据库。
在运行时,某个人访问 http://tinyurl.com/abcd123,我们将 ID "abcd123",并重定向到对应的域名 "https://leetcode-cn.com/"。

这个问题的解法

我们不能单纯对长域名生成唯一的哈希值。在哈希方法中,有可能会有冲突(2 个长域名映射到同一个短域名),但我们需要的是每个对域名都唯一对应到一个长域名,而哈希方法是单方向的,从长域名得到短域名,但从短域名无法得到长域名。

一个最简单但也非常有效的方法,是建立一个这样的数据库:

Table Tiny_Url(
ID : int PRIMARY_KEY AUTO_INC,
Original_url : varchar,
Short_url : varchar
)

自增的 ID 可以被用来做转化:(ID, 10) <==> (short_url, BASE)。每当新插入一个域名 original_url,查询语句会返回新插入的 ID,并用它来生成短域名 short_url,保存 short_url 并返回给用户。

方法(将 ID 转成短域名或将短域名转成 ID)

string idToShortURL(long int n){
    // Map to store 62 possible characters
    char map[] = "abcdefghijklmnopqrstuvwxyzABCDEF"
                 "GHIJKLMNOPQRSTUVWXYZ0123456789";
  
    string shorturl;
  
    // Convert given integer id to a base 62 number
    while (n){
        shorturl.push_back(map[n%62]);
        n = n/62;
    }
  
    // Reverse shortURL to complete base conversion
    reverse(shorturl.begin(), shorturl.end());
  
    return shorturl;
}
  
// Function to get integer ID back from a short url
long int shortURLtoID(string shortURL){
    long int id = 0; // initialize result
  
    // A simple base conversion logic
    for (int i=0; i < shortURL.length(); i++){
        if ('a' <= shortURL[i] && shortURL[i] <= 'z')
          id = id*62 + shortURL[i] - 'a';
        if ('A' <= shortURL[i] && shortURL[i] <= 'Z')
          id = id*62 + shortURL[i] - 'A' + 26;
        if ('0' <= shortURL[i] && shortURL[i] <= '9')
          id = id*62 + shortURL[i] - '0' + 52;
    }
    return id;
}

多设备

如果我们用我们的服务在处理大量数据,分布式存储可以增大我们的容量。这个想法很简单,从原域名获得一个哈希值并找到对应的机器,然后当做单设备的情况处理。为了在集群里面找到正确的节点,我们需要使用一致性哈希。
下面是例子的伪代码:

获取短域名

将原域名哈希成 2 个数字作为哈希值 hash_val

  • hash_val 在集群中定位到机器。
  • 将原域名插入数据库,并用函数 getShortURL 获取短域名 short_url
  • hash_valshort_url 结合起来作为我们的最终短域名 final_short_url(长度为 8),并返回给用户。

由短域名获取原域名

final_short_url 的前 2 个字符作为 hash_val

  • hash_val 定位到机器
  • final_short_url 中剩余 6 位作为 short_url 找到表中对应的行
  • 将原域名 original_url 返回给用户

其他因素

这里我想进一步探讨的一个事情是使用 GUID (Globally Unique Identifier) 作为入口 ID,与这题中增量式 ID 相比的优点和缺点是什么呢?
如果你深挖一下插入和查询的过程,你就会注意到使用随机字符串作为 ID 会牺牲一点性能。更具体的,如果你有几百万条记录,插入操作会非常费时。因为 ID 不是时序的,每当一条新的记录被插入时,数据库需要找到一个针对这个 ID 的正确位置。然而如果使用增量式 ID ,插入会变得很简单:只需要找到最后一页。

48
如果做映射,比较有效且简单的方法就是把原域名与一个数做映射关系(64位足够),这样可以将问题转换为如何做一个id的生成器。
数据库和redis都有全局生成id的能力,但是这种性能都有上限,每秒最多在万量级。如果是分布式要求很高的情况下,可以用每次申请分段的方式,也就是每次让数据库自增1万,然后在id生成服务上每次吐出增1(全部用完在去数据库中要求自增),这样可以使得性能突破瓶颈,而且保证全局唯一。
1

就拿n为7来说明,我提出几个点供大家讨论。
1,如何保证,连续生成的码没有规律。
不期望结果 AAAAAA1 AAAAAA2 AAAAAA3 AAAAAA4
期望结果 AA3FFH5 mdN3GSA 31F3fG3

2,如何保证不被猜测,用户随便输一个7位的有没有效呢

1

lc上显示的基础架构题目指哪些呢?

我忽然觉得,力扣账号的竞赛排名是不是专门为了展示一共有多少人参加了周赛啊

短地址服务有个安全问题需要考虑,不论用base62多少字符,怎么保证不被遍历短地址库?

之前面试被问过

之前做的一个短网址系统,采用的另一种方法,ID自增法。

短网址(short URL)系统的原理及其实现

源码

5