生成具有 6 个字符的唯一 ID - 当已使用过多 ID 时处理

Question

在我的程序中你可以预订一个项目。此项目的 ID 包含 32 个可能字符中的 6 个字符。

所以我的可能性是 32^6。每个id都必须是唯一的。

func tryToAddItem {
 if !db.contains(generateId()) {
   addItem()
 } else {
   tryToAddItem()
 }
}

例如，我 90% 的 ID 都被使用了。所以我调用 tryToAddItem 5 次的概率是 0,9^5 * 100 = 59% 不是吗？

所以这是相当高的。这是对大量数据的 5 个数据库查询。

当概率如此之高时，我想实现一个前缀“A-xxxxxx”。什么是好的条件？我什么时候需要前缀？

在我的示例中，使用了 90% 的 ID。剩下的呢？我把它扔掉了吗？当我调用 tryToAddItem 5 次时，数据库性能如何？我可以想象这不是最佳做法。

Answer 1

For example 90% of my ids are used. So the probability that I call tryToAddItem 5 times is 0,9^5 * 100 = 59% isn't it?

不完全是。让我们用随机变量 X 来表示您进行的调用次数，并让我们调用 id 冲突的概率 p。您希望您拨打电话的概率最多次，或者通常最多 k 次：

P(X≤k) = P(X=1) + P(X=2) + ... + P(X=k)
= (1-p) + (1-p)*p + (1-p)*p^2 +... + (1-p)*p^(k-1)
= (1-p)*(1 + p + p^2 + .. + p^(k-1))

如果我们将其展开，除两项取消外，我们得到：

= 1- p^k

我们希望大于某个概率，x:

1 - p^k > x

或者用 p 表示 k 和 x:

p < (1-x)^(1/k)

您可以根据自己的具体需要调整 x 和 k。

如果您希望 5 次或更多次调用的概率低于 50%，则不应超过 (1-0.5)^(1/5) ≈ 87% 的 ID。

首先确保您要查找的 id 列上有一个索引。然后我会建议更多地考虑将非常糟糕的事件发生的概率设置得非常低。例如，可能进行 20 次调用会使数据库运行时间过长，因此我们希望将这种情况发生的概率设置为 <0.1%。使用上面的公式我们发现不应该超过 70% 的 ids。

但是您还应该考虑其他解决方案。将所有 ID 重新映射到更大的 space 一次只是一种可能性吗？

或者，如果添加带前缀的 ID 不是什么大问题，那么您可以为所有新项目生成更长的带前缀的 ID，而不必担心冲突。

Answer 2

感谢您的回复。我搜索了替代方案并希望展示三种可能性。

第一种可能性：创建一个UpcomingItemIdTable，有200（或多或少）有效itemIds。后台任务可以每分钟（或您需要的）计算它们。所以动作 tryToAddItem 总是会得到一个有效的 itemId.

第二种可能

Is remapping all ids to a larger space one time only a possibility?

就我而言是的。我认为对于其他问题，答案将是：视情况而定。

第三种可能性：尝试生成一个itemId，当发生碰撞时再试一次。

可能的碰撞处理：之前做一些测试。当 table 中已经有 1000,10.000,100.000,1.000.000 等条目时，测量生成 itemIds 的时间。当 tryToAddItem 方法需要超过 100 毫秒（或您喜欢的）时，请将长度从 6 个字符增加到 7、8、9 个字符。

一些想法

TLDR：就我而言，每种可能性都有效。通常这取决于问题。感谢您的输入。

Generated unique id with 6 characters - handling when too much ids already used