0

我已经阅读并观看了许多 youtube 视频和链接，它们都提供了相同的解决方案，即：

  1. 使用像 zookeeper 这样的分布式计数器
  2. 计数器最大限制可以是 3.5 万亿
  3. 将 Counter 值转换为 Base62

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

但是当计数器提供较大的计数器值时，例如低于 base62 值的长度也会增加。生成的计数器值：120003658=> base62 值 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

4

2 回答 2

0

鉴于您不是散列每个url，而是一个模糊可预测的数字，您可以散列结果并取前 N 位

但是，有很多解决方案可以解决碰撞问题

  • 忽略它们-它们将很少见（理想情况下）
  • 选择下一个值
  • 再次散列结果（使用您的输入）
  • 增加返回字符串的大小
  • ...

这是关于杜鹃散列的精彩视频（这是与此处相关的散列结构）：
https ://www.youtube.com/watch?v=HRzg0SzFLQQ

这是 Python 中的一个示例，它从哈希中找到一个 8 个字符的字符串，该字符串应该是相当唯一的（然后可以将其收集到一个排序的数据结构中，将其映射到一个 URL）

这首先使用雪崩散列 ( SHA-265 ) 对值进行散列，然后循环查找它的最小值（从十六进制字符串的前面切片）以形成一个 8 字符的 base62 字符串

这可以变得更加有效（甚至，例如通过bisecting），但可能更清晰，并且很大程度上取决于未指定的算法要求

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

如何使用 Python3 修复 base62 编码的代码中的 base62逻辑？

于 2021-01-14T06:00:41.430 回答
0

第一：绝对有压缩限制。如果您选择的表示具有最大长度，则会对您的密钥空间施加硬性限制。

让我们稍微拆开包装。假设您有 80 位客人参加聚会，并且您想给每位客人一个独特的标签（用于他们的饮料杯或其他东西）。如果您决定每个标签都是英文字母表中的一个字母，那么您只有足够的唯一标签来容纳 26 位客人。

第二：FMJQmhBR不是表示数字的最有效方式120001。它需要 17 位二进制：（11101010011000001不确定是哪种字节序）。16 位只是两个 ASCII 字符，三个 ASCII 字符可以容纳近 1700 万个唯一值。这没有任何特殊的、类似 ZIP 的压缩。

--

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

不过，这很粗糙。由于各种原因，他们不想按顺序分发这些 ID。但是，如果他们知道他们希望标识符有多长，那么以随机顺序分发这些 ID 并不难：

  • 当有人提交 URL 时，系统会在 0 和可能的最高 ID 之间选择一个随机数。如果 URL 标识符都应该是 8 个 ASCII 字符，这意味着它们会选择一个介于 0 和 2^(8*8) = 之间的随机数1.844674407e19。
  • 然后他们检查他们的数据库，看看他们是否已经分发了那个 ID。如果有，他们会选择一个不同的随机数。他们重复此操作，直到他们选择一个尚未分发的 ID。（我认为有更有效的算法，但效果是一样的，这是最容易理解的。）
于 2021-01-14T06:04:41.557 回答