微URL系统设计

Question

我看过很多youtube视频和链接，它们都提供了相同的解决方案，即：

1. 使用像动物园管理员这样的分布式计数器
2. 计数器最大极限可达3.5万亿
3. 将计数器值转换为Base62

当计数器值很小时，这一切都很好。生成的计数器值: 120001 => base62 value FMJQmhBR

但是，当计数器提供较大的计数器值，如低于base62值时，长度也会增加。生成的计数器值: 120003658=> base62 value HRGZF8RiHC6y

因此，这怎么可能是一个精确的8长度的微小url的解决方案。

https://www.linqz.io/2018/10/how-to-build-a-tiny-url-service-that-scales-to-billions.html https://www.youtube.com/watch?v=eCLqmPBIEYs https://www.youtube.com/watch?v=JQDHz72OA3c&t=1862s

Answer 1

考虑到您并不是在散列每个url，而是一个模糊可预测的数字，您可以散列结果并获取第一个N位。

然而，对于如何处理碰撞，有许多解决方案。

• 忽略它们--它们将是罕见的(理想情况下)
• 选择下一个值
• 再次散列结果(用您的输入)
• 增加返回字符串的大小。
• ..。

这里有一个很棒的关于杜鹃散列的视频(这是一个与此相关的散列结构)：

https://www.youtube.com/watch?v=HRzg0SzFLQQ

下面是Python中的一个示例，它从散列中找到一个8个字符的字符串，该字符串应该是非常唯一的(然后可以将其收集到一个排序的数据结构中，将其映射到一个URL中)

首先使用雪崩散列(沙265)对值进行散列，然后循环找到最小值(从十六进制字符串的前面切分)，形成一个8字符的base62字符串。

这可以使效率更高(即使是通过分切)，但可能更加清晰，并且在很大程度上取决于未指定的算法需求。

import hashlib

BASE62 = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"

m = hashlib.sha256()
m.update("https://stackoverflow.com/questions/65714033/tiny-url-system-design".encode())
digest  = m.digest()    # hash as bytes       b',\xdb3\x8c\x98g\xd6\x8b\x99\xb6\x98#.\\\xd1\x07\xa0\x8f\x1e\xb4\xab\x1eg\xdd\xda\xd6\xa3\x1d\xb0\xb2`9'
hex_str = digest.hex()  # string of hex chars 2cdb338c9867d68b99b698232e5cd107a08f1eb4ab1e67dddad6a31db0b26039

for hashlen in range(100, 1, -1):
    number = int(hex_str[:hashlen], 16)  # first_n_chars(str(hex)) -> decimal
    val = ""
    while number != 0:
        val = "{}{}".format(BASE62[number % 62], val)  # append new chars to front
        number = number // 62  # integer division
    if len(val) <= 8:
        break

print(val)  # E0IxW0zn

来自base62的如何用base62修复Python3编码的代码？逻辑

Answer 2

首先:绝对有压缩限制。如果您选择的表示具有最大长度，则对您的键空间施加硬限制。

让我们把它打开一点。假设你在一个聚会上有80位客人，你想给每一位客人一个独特的标签(比如他们的酒杯之类的)。如果你已经决定每个标签将是一个字母从英语字母，那么你只有足够的独特标签26位客人。

第二：FMJQmhBR并不是表示数字120001最有效的方法。它需要17位二进制代码：11101010011000001 (不确定是哪个痴呆症 )。16位只是两个ASCII字符，三个ASCII字符可以容纳近1700万个唯一值。这没有任何特殊的，类似ZIP的压缩。

--

我认为大多数URL缩短器的工作本质上是通过为某人缩短的每个URL分配一个计数号。因此，提交的第一个URL将被赋予ID=1:他们将整个URL保存在数据库中，并将其与该数字相关联。第二个URL获取ID=2等。

不过，这还挺粗俗的。出于各种原因，他们不想按顺序分发这些ID。但是，如果他们知道他们想要的标识符是多长时间，那就不是硬性地按随机顺序发出这些in了：

• 当有人提交一个URL时，系统会在0和最高可能的ID之间选择一个随机数。如果URL标识符都应该是8个ASCII字符，这意味着它们会选择0到2^(8*8) = 1.844674407e19之间的随机数。
• 然后他们检查他们的数据库，看看他们是否发了那个ID。如果他们有，他们会选择一个不同的随机数。他们会重复这些直到他们找到一个还没发出去的身份证。(我认为有更有效的算法，但效果是一样的，这是最容易理解的。)