微小的随机ID生成

Question

我正在尝试生成用于Google App Engine应用程序的唯一ID,并希望获得有关我正在考虑使用的方法的可行性的反馈(最后的问题).我已经阅读了很多关于这个主题的问题,但我不记得遇到过这种特殊的方法.

我想要随机查看ID,例如MD5哈希,但我也希望它们很小.沿着tinyurl线的四到六个字符将是理想的.在我的应用程序的上下文中,ID将用于用户生成的内容,例如人们将要编写的测试问题.这些ID不一定是随机的(如果它们看起来像序列ID就没问题),但我正在考虑使用的方法适用于此,所以它并不是真正的问题.

熟悉Google App Engine的人会知道,对数据存储的写入特别昂贵,并且如果对同一实体组中存在过多的写入,则会导致超时.分片计数器是一种常用于避免单个全局计数器上的写入争用以及与之一起的失败事务的方法.

除了获得短ID和避免写入争用,我还试图避免生日悖论.我想为有数百万个ID的可能性做准备,即使这有点过分.

我正在考虑沿着以下几行使用分片计数器:

• 计数器在用户上分片,因此每个用户都有一个分片.每个计数器对象都有自己的特定于给定用户的计数,当该用户创建新项目时,该计数会递增.无论是否成功创建项目,计数都会递增.
• ID的基础是以下字符串的MD5哈希:"<user-email-address> | <latest-counter-value>".
• 然后截断生成的MD5哈希,最初为四个字符.
• 保持单个全局"长度"值.只要前面的步骤导致重复键(一个想象这将在一开始就相当快地发生),长度的值将增加一.现在,新ID的MD5哈希值将以"长度"字符截断,而不是四个字符.
• 我不想公开用户的电子邮件地址,这表明某种哈希值是一种好方法.

我的问题是:我是否正确地认为这将在很大程度上避免由于重复密钥导致的写入争用,并且长度字段上的写入争用可能不会成为问题,特别是在长度较长的情况下？谁能描述这里涉及的数学？长度是否会迅速增加到接近MD5哈希的长度,从而质疑整个方法的价值？为了让事情更容易维护,仅仅使用完整(更长)的MD5哈希会更好吗？有什么我可以忽略的吗？

Answer 1

这个算法很聪明，确实可以最大限度地减少写操作。因此，长度值将收敛到最短长度和不存在碰撞之间的平衡。

您可以通过使用哈希表中使用的策略来放松不存在冲突的约束。在回退到增加长度之前尝试一些其他唯一 ID。

因此，我建议您在初始化为 0 的哈希字符串末尾添加一个测试计数器。如果生成的 ID 已被使用，请增加计数器并重试，直到在增加长度后达到最大计数器值。

您最终将更有效地使用 ID 地址空间，并且长度增量的频率会大大降低。

关于你关于MD5长度限制的问题我认为MD5的选择有点矫枉过正。您实际上并不需要加密（伪）安全哈希。您需要的是一个随机位生成器，您可以使用 crc32 （或更快的 adler）。特别是如果代码要在手机上运行。要使用 crc32 实现随机位生成器，请在要散列的字符串前面添加一个 32 位值，并使用您选择的常量值（种子）对其进行初始化。然后计算该字符串的 crc32。如果需要更多字节，请将得到的crc32值写入字符串前面的32bits中，并重新计算crc32。迭代直到有足够的位。您可以将 crc32 替换为您选择的算法。这产生了一个廉价且快速的随机位生成器，其中初始常数是种子。

使用此算法，您可以最大限度地减少生成的随机位的数量，并且长度没有上限。

关于编码，您没有指定约束。您可以使用大小写字母和数字吗？您的示例使用包含 36 个不同 ASCII 值的字母表。一旦您有了上述可以生成所需数量字节的伪随机数生成器，只需将长度定义为 ID 的字母数，并以下一个随机字节为模来选择下一个字母。然后您就会确切地知道一次要生成多少字节，并且生成 ID 是微不足道的。