google-app-engine - 微小的随机 ID 生成

Question

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

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

熟悉 Google App Engine 的人会知道，写入数据存储的开销特别大，如果对同一实体组的写入过多，可能会导致超时。分片计数器是一种常用于避免单个全局计数器上的写入争用以及随之而来的失败事务的方法。

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

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

• 计数器按用户进行分片，因此每个用户都有一个分片。每个计数器对象都有自己的特定于给定用户的计数，当该用户创建新项目时该计数会递增。无论项目是否成功创建，计数都会递增。
• ID 的基础是以下字符串的 MD5 哈希值:“ | ”。
• 然后截断生成的 MD5 哈希值，最初截断为四个字符。
• 维护一个单一的全局“长度”值。每当前面的步骤导致重复键(一开始想象这会很快发生)时，长度的值将增加 1。新 ID 的 MD5 散列现在将被截断为“长度”字符，而不是四个字符。
• 我不想公开用户电子邮件地址，这表明某种散列是一种不错的方法。

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

Answer 1

这样的事情怎么样:

1. 如果您想要使用 a-zA-Z0-9 的 4 个字符键，那么您需要:62^4 = > 1400 万个可能值。

2. 将其分成 N 个分区:0000 ... 1000, 1001 ... 2000 , ... , ZZAA ... ZZZZ

   每个分区由一个实体表示:起始编号结束编号当前id

现在，生成一个 ID:

1. 随机选择一个分区。使用每个分区的开始 key 作为 key 。开始交易:
2. get_or_create() 分区实体。
3. 如果当前id == 结束id，转到第1步
4. 保存当前ID
5. 将当前 ID 加一结束交易

使用保存为您的 ID 的当前 ID。

如果您选择 N 为 140，则每个分区将有 100,000 个值。这将允许相当多的并发插入，同时限制由于选择“空”分区而导致的重试次数。

您可能需要多考虑一下。特别是，当您需要移动到 5 位或 6 位 key 时，您将如何处理？

-戴夫