微小的随机 ID 生成
https://stackoverflow.com/questions/815622
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
我正在尝试生成用于 Google App Engine 应用程序的唯一 ID，并且希望获得有关我正在考虑使用的方法的可行性的反馈（问题在最后）。我读过很多关于这个主题的问题，但我不记得遇到过这种特殊的方法。
我想要看起来随机的 ID，例如 MD5 哈希值，但我也希望它们很小。理想的情况是四到六个字符（类似于tinyurl）。在我的应用程序的上下文中，ID 将用于用户生成的内容，例如人们将编写的测试问题。ID 不一定是随机的（如果它们看起来像序列 ID 就很好），但我正在考虑使用的方法适合于此，所以这并不是真正的问题。
熟悉 Google App Engine 的人会知道，对数据存储的写入特别昂贵，如果同一实体组的写入次数过多，可能会导致超时。分片计数器是一种经常用于避免单个全局计数器上的写入争用以及随之而来的失败事务的方法。
除了获得短 ID 和避免写争用之外，我还试图避免生日悖论。我想为可能有数百万个 ID 做好准备，即使这有点过头了。
我正在考虑按照以下方式使用分片计数器：
- 计数器按用户进行分片，因此每个用户都有一个分片。每个计数器对象都有其自己的特定于给定用户的计数，当该用户创建新项目时，该计数会递增。无论项目是否成功创建，计数都会递增。
- ID 的基础是以下字符串的 MD5 哈希值：“<用户电子邮件地址>|<最新计数器值>”。
- 然后，生成的 MD5 哈希值将被截断，最初为四个字符。
- 维护单个全局“长度”值。每当前面的步骤产生重复的键时（人们想象这一开始会很快发生），长度的值就会增加一。新 ID 的 MD5 哈希现在将被截断为“长度”字符，而不是四个字符。
- 我不想公开用户的电子邮件地址，这表明某种哈希值是一个好方法。
我的问题是：我是否正确地认为这将在很大程度上避免由于重复键而导致的写入争用，并且长度字段上的写入争用可能不会成为问题，尤其是在较长的长度下？谁能描述一下这里涉及的数学？长度是否会迅速增加到接近 MD5 哈希值的长度，从而使整个方法的价值受到质疑？为了让事情更容易维护，使用完整的（更长的）MD5 哈希会更好吗？有什么是我忽略的吗？
解决方案
这个算法很聪明，确实可以最大限度地减少写操作。因此长度值将收敛到最短长度和 缺席 的碰撞。
您可以通过使用哈希表中使用的策略来放松不存在冲突的约束。在回退到增加长度之前尝试一些其他唯一 ID。
因此，我建议您在初始化为 0 的哈希字符串末尾添加一个测试计数器。如果生成的 ID 已被使用，请增加计数器并重试，直到在增加长度后达到最大计数器值。
您最终将更有效地使用 ID 地址空间，并且长度增量的频率会大大降低。
关于你关于MD5长度限制的问题我认为MD5的选择有点矫枉过正。您实际上并不需要加密（伪）安全哈希。您需要的是一个随机位生成器，您可以使用 crc32 （或更快的 adler）。特别是如果代码要在手机上运行。要使用 crc32 实现随机位生成器，请在要散列的字符串前面添加一个 32 位值，并使用您选择的常量值（种子）对其进行初始化。然后计算该字符串的 crc32。如果需要更多字节，请将得到的crc32值写入字符串前面的32bits中，并重新计算crc32。迭代直到有足够的位。您可以将 crc32 替换为您选择的算法。这产生了一个廉价且快速的随机位生成器，其中初始常数是种子。
使用此算法，您可以最大限度地减少生成的随机位的数量，并且长度没有上限。
关于编码，您没有指定约束。您可以使用大小写字母和数字吗？您的示例使用包含 36 个不同 ASCII 值的字母表。一旦您有了上述可以生成所需数量字节的伪随机数生成器，只需将长度定义为 ID 的字母数，并以下一个随机字节为模来选择下一个字母。然后您就会确切地知道一次要生成多少字节，并且生成 ID 是微不足道的。
其他提示
像这样的事情怎么样：
如果您想要使用 a-zA-Z0-9 的 4 个字符键，那么您将拥有：62^4 = > 1400 万个可能的值。
将其分成 N 个分区：0000 ...1000、1001……2000年，...，ZZAA...ZZZZ
每个分区由一个实体表示：启动ID结束ID当前ID
现在，生成一个 ID：
- 随机选择一个分区。使用每个分区的开始键作为键。开始交易：
- get_or_create() 分区实体。
- 如果当前id ==结束id，则转至步骤1
- 保存当前id
- 增量当前ID通过一端事务
使用保存为您的 ID 的当前 ID。
如果您选择 N 作为 140，则每个分区将有 100,000 个值。这将允许相当多的并发插入，同时限制由于选择“空”分区而导致的重试次数。
您可能需要更多地考虑这一点。特别是，当您需要转移到 5 或 6 位数字密钥时，您将如何处理？
-戴夫
只是为了向上面的问题添加一些硬数字，我实现了一个小程序来按照问题中提到的方式生成 id，这些是其中一次试运行的结果：
Length Count MD5 Base 62
4 400 3d0e 446
5 925 4fc04 1Myi
6 2434 0e9368 40V6
7 29155 e406d96 GBFiA
8 130615 7ba787c8 2GOiCm
9 403040 75525d163 YNKjL9
10 1302992 e1b3581f52 H47JAIs
Total: 1869561
每次哈希长度增加都是由于冲突造成的，因此本例中发生了六次冲突。计数是在碰撞之前生成的给定长度的密钥的数量。MD5 列显示在出现重复密钥错误之前成功添加的最后一个截断密钥。最右边的列显示以 62 为基数的密钥（如果我正确完成了转换）。
看起来每个附加字符都会生成越来越多的密钥，这就是您所想象的。我希望这种方法能够适应用户生成的内容。
对于任何感兴趣的人，以下是我如何获取最后一列的 62 进制表示形式：
def base_62_encode(input):
"Inspired by code at http://en.wikipedia.org/wiki/Base_36."
CLIST="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
rv = ""
while input != 0:
rv = CLIST[input % 62] + str(rv)
input /= 62
return rv
base62_id = base_62_encode(long(truncated_hash, 16))
（稍后补充：）
下面是一个类，负责处理与在 Google App Engine 上下文中生成这些 ID 相关的一些事情。默认情况下，此类生成的密钥不是纯粹的基数 62，因为 GAE 密钥名称的第一个字符必须是字母。此处已通过对第一个字符使用基数 52 来解决该要求。
通过更改已传递到构造函数中（或从构造函数中省略）的“clist”值，可以将主基数更改为 62 以外的值。人们可能想要删除容易混淆的字符，例如“1”、“l”、“i”等。
用法：
keygen = LengthBackoffIdGenerator(SomeClass, initial_length=5)
small_id, modified = keygen.small_id(seed_value_from_sharded_counter)
这是课程：
class LengthBackoffIdGenerator(object):
"""Class to generate ids along the lines of tinyurl.
By default, ids begin with a alphabetic character. Each id that is created is checked against previous ones
to ensure uniqueness. When a duplicate is generated, the length of the seed value used is increased by one
character.
Ids become gradually longer over time while remaining relatively short, and there are very few retries in
relation to the number of keys generated.
"""
ids = set()
def __init__(self, cls, clist='0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ', alpha_first=False,
initial_length=5, check_db=False):
self.clist = clist
self.alpha_first = alpha_first
if self.alpha_first:
import re
alpha_list = re.sub(r'\d', '', clist)
if len(alpha_list) < 1:
raise Exception, 'At least one non-numeric character is required.'
self.alpha_list = alpha_list
self.cls = cls
self.length = initial_length
self.check_db = check_db
def divide_long_and_convert(self, radix, clist, input, rv):
"Inspired by code at http://en.wikipedia.org/wiki/Base_36."
rv += clist[input % radix]
input /= radix
return (input, rv)
def convert_long(self, input):
rv = ""
if self.alpha_first:
input, rv = self.divide_long_and_convert(len(self.alpha_list), self.alpha_list, input, rv)
while input != 0:
input, rv = self.divide_long_and_convert(len(self.clist), self.clist, input, rv)
return rv
def hash_truncate_and_binify(self, input, length):
"""Compute the MD5 hash of an input string, truncate it and convert it to a long.
input - A seed value.
length - The length to truncate the MD5 hash to.
"""
from assessment.core.functions import md5_hash
input = md5_hash(input)[0:length]
return long(input, 16)
def _small_id(self, input):
"""Create an ID that looks similar to a tinyurl ID.
The first letter of the ID will be non-numeric by default.
"""
return self.convert_long(self.hash_truncate_and_binify(input, self.length))
def small_id(self, seed):
key_name = self._small_id(seed)
increased_length = False
if self.check_db and not self.cls.get_by_key_name(key_name) is None:
self.ids.add(key_name)
if key_name in self.ids:
self.length += 1
increased_length = True
key_name = self._small_id(seed)
self.ids.add(key_name)
return (key_name, increased_length)
