4

我正在做一个需要每天添加/更新大约 100 万个网址的项目。有些日子主要是更新，有些日子主要是添加，有些日子是混合的。

因此，在每个查询中，都需要在 url 表中查找 url 的唯一性。

如何查找 url 可以非常快，因为目前索引设置在 url 列并且效果很好，但是在接下来的几周内，如果索引保持在同一列上并且新记录将以数百万计添加，那么 RAM 将不够用。

这就是为什么我正在寻找一种解决方案，以便当总共有 150+ 百万个 url 时，它的查找应该很快。我正在考虑在 md5 上创建索引，但随后担心碰撞机会。一位朋友提示我也计算 crc32 哈希并与 md5 连接以使冲突可能性为零并将其存储在 binary(20) 中，这样只有 20 个字节将被视为索引，而不是当前 varchar(255) 设置为 url 列数据的 255 个字节类型。

目前总共有大约 5000 万个 url，并且使用 8GB ram 可以正常工作。

昨天，我问了一个问题url 文本压缩（不是缩短）并存储在与同一项目相关的 mysql 中。

[编辑] 我想到了另一种解决方案，将 crc32 哈希仅以十进制形式放置以加快查找速度。并在应用程序级别移植检查返回的记录数。如果返回超过 1 条记录，则还应匹配准确的 url。这样，通过为每行存储 4 个字节而不是 20 个字节 (md5+crc32) 来保持 RAM 和磁盘空间的低负载也可以避免冲突。你说的话？

4

1 回答 1

6

在阅读了您的所有问题（唯一约束使哈希无用？，512 位哈希与 4 128 位哈希和url 文本压缩（不缩短）并存储在 mysql 中）之后，我了解到您的问题或多或少如下：

“我需要在 mySQL 中存储 +150M 的 URL，使用 8GB 的​​ RAM，并且在将它们全部写入和检索它们方面仍然具有良好的性能，因为我每天都会更新它们，所以我会检索很多 URL，检查它们对数据库。实际上它有 5000 万个 URL，并且在接下来的 3 个月内每天会增长约 100 万个。

是这样吗？

以下几点很重要： 您将保存的 URL 的格式如何？您是否需要回读 URL，或者只是更新有关它的信息，但从不基于部分 URL 等进行搜索？

假设 URL =“ http://www.somesite.com.tv/images/picture01.jpg ”并且您想要存储所有内容，包括文件名。如果不同，请提供更多详细信息或更正我的答案假设。

  1. 如果可以通过替换 URL 中的某些字符组来节省空间。并非所有 ASCII 字符在 URL 中都有效，如您在此处看到的：RFC1738，因此您可以使用它们来表示（和压缩）URL。例如：使用字符 0x81 表示“http://”可以节省 6 个字符，0x82 表示“.jpg”可以节省 3 个字节等。

  2. 有些词可能很常见（如“图像”、“图片”、“视频”、“用户”）。如果您选择用户字符 0x90 到 0x9f + 任何其他字符（例如，0x90 0x01、0x90 0x02、0x90 0xfa）来编码这些单词，则可以有 16 * 256 = 4,096 个“字典条目”来编码最常用的单词。您将使用 2 个字节来表示 4 - 8 个字符。

编辑：正如您在上面提到的 RFC 中所读到的，在 URL 中您只能有可打印的 ASCII 字符。这意味着只应使用字符 0x20 到 0x7F，并在 RFC 中进行了一些观察。因此，不应使用 0x80 之后的任何字符（十六进制表示法，在 ASCII 表中将是十进制字符 128）。因此，如果可以选择一个字符（比如说 0x90）作为一个标志来指示“以下字节是字典中的指示，我将使用的索引”。1 个字符 (0x90) * 256 个字符（0x00 到 0xFF）= 字典中的 256 个条目。但是您也可以选择使用字符 0x90 到 0x9f（或十进制的 144 到 159）来表示它们是字典的标志，从而为您提供 16 * 256 种可能性...

这两种方法可以为您节省大量数据库空间并且是可逆的，无需担心冲突等。您只需在应用程序中创建一个字典并使用它对 URL 进行编码/解码，速度非常快，您的数据库要轻得多。

由于您已经拥有 +50M URL，您可以根据它们生成统计信息，以生成更好的字典。

使用哈希：在这种情况下，哈希是大小和安全性之间的权衡。如果发生碰撞会有多糟糕？在这种情况下，您可以使用生日悖论来帮助您。

阅读文章以了解问题：如果所有输入（URL 中可能的字符）都是等价的，则可以估计发生冲突的概率。并且可以计算相反的结果：考虑到您可接受的碰撞概率和文件数量，您的范围应该有多宽？而且由于您的范围与哈希函数生成的位数完全相关......

编辑：如果你有一个给你 128 位的散列函数，你将有 2^128 个可能的结果。所以，你在生日悖论中的“范围”是 2^128：就像你的一年有 2^128 天，而不是 365 天。所以，你计算碰撞的概率（“两个文件在同一天出生，一个有 2^128天而不是 365 天的年份）。如果您选择使用提供 512 位的哈希，则您的范围将从 0 到 2^512...

并且，请再次记住 RFC：并非所有字节（256 个字符）在 Internet/URL 世界中都是有效的。因此，碰撞的概率会降低。对你更好 ：）。

于 2011-09-15T17:15:58.867 回答