google-app-engine - AppEngine，数据存储 : Preallocating normally-distributed IDs (*not* monotonically incrementing)

Question

在数据存储实体上设置 ID 的方案有以下三种:

1. 提供您自己的字符串或 int64 ID。
2. 不要提供它们，让 AE 为您分配 int64 ID。
3. 预先分配一个 int64 ID block 。

documentation关于 ID 生成有这样的说法:

这 (1):

Cloud Datastore can be configured to generate auto IDs using two different auto id policies:

1. The default policy generates a random sequence of unused IDs that are approximately uniformly distributed. Each ID can be up to 16 decimal digits long.

2. The legacy policy creates a sequence of non-consecutive smaller integer IDs.

If you want to display the entity IDs to the user, and/or depend upon their order, the best thing to do is use manual allocation.

和这个 (2):

Note: Instead of using key name strings or generating numeric IDs automatically, advanced applications may sometimes wish to assign their own numeric IDs manually to the entities they create. Be aware, however, that there is nothing to prevent Cloud Datastore from assigning one of your manual numeric IDs to another entity. The only way to avoid such conflicts is to have your application obtain a block of IDs with the datastore.AllocateIDs function. Cloud Datastore's automatic ID generator will keep track of IDs that have been allocated with this function and will avoid reusing them for another entity, so you can safely use such IDs without conflict.

和这个 (3):

Cloud Datastore generates a random sequence of unused IDs that are approximately uniformly distributed. Each ID can be up to 16 decimal digits long.

System-allocated ID values are guaranteed unique to the entity group. If you copy an entity from one entity group or namespace to another and wish to preserve the ID part of the key, be sure to allocate the ID first to prevent Cloud Datastore from selecting that ID for a future assignment.

我有一个与祖先一起存储的特定实体类型。但是，我希望拥有全局唯一的 ID，并且 AE 的 ID(通过 datastore.AllocateIDs 使用 Go 分配)在存储在祖先(实体组中)下时不会是全局唯一的。因此，预分配可以解决这个问题(它们与祖先无关)。但是，很明显，您会得到一个响应间隔……已保留的连续 ID 范围。

有没有办法预先分配那些漂亮的、不透明的、均匀分布的 ID？

当我们讨论这个主题时，我曾假设来自 AE 的不透明 ID 是某些伪随机数生成器的结果，每个实体类型都有一个持久状态，但 (2) 中的“track”一词似乎这意味着乐观地生成和缓冲可能不会使用的 ID 是有代价的。如果有人能澄清这一点，那就太好了。

Answer 1

简单的解决方案是执行以下操作:

尝试为实体分配新 ID 时:

重复以下内容:

• 生成一个随机的 K 位整数。将其用于实体 ID 字段。 [使用均匀随机分布]。
• 创建 Cloud Datastore 事务。
• 插入新实体。 [如果交易因为实体已经存在而中止，请使用新的随机数重试]。

如果您使 K 足够大(例如 128)并且具有适当的种子随机数生成器，那么在统计上不可能生成 ID 冲突并且您可以删除重试循环。

如果您使 K 足够大，请停止在实体键中使用整数 id 字段，而是使用字符串 1。 Base64 URL 将随机数编码为字符串。