c# - 如何在分布式系统中生成重复概率低的标识符？

Question

我需要在分布式系统中生成标识符。

系统会检测到重复项，并会导致创建该标识符的操作失败。我需要通过生成具有低冲突概率的标识符来最小化操作失败的概率。

我还希望能够从数学上描述生成重复数字的可能性有多大。我不确定这样的描述会是什么样子，最好我想知道 X 是这样的:

When generating 1000 random numbers per second for 10 years no more than X duplicates should have been generated.

这些随机数只能有 35 个有效位。该系统用 C# 编写，运行在 Microsoft 的 .NET 平台之上。

所以这实际上是两个问题合二为一(但我想它们是相互依赖的):

1. 我应该使用什么组件/模式来生成标识符？

2. 如何计算 X 值？

对于 (1) 我看到以下候选人:

• System.Random
• System.Guid
• System.Security.Cryptography.RNGCryptoServiceProvider

我需要数字有 35 个有效位这一事实在生成值时不是问题，因为生成一个更大的数字然后只提取其中的 35 个位就可以了。但是，它确实会影响我假设的数学计算。

更新

我现在可以看出 35 位对于我上面的描述来说还远远不够。 10 年来，我真的不需要每毫秒 1 个数字。这是夸大其词。

我真正需要的是一种分布式生成具有 35 位有效位且冲突概率尽可能低的标识符的方法。随着时间的推移，系统将“清理”标识符，以便可以再次使用相同的号码而不会导致失败。

我知道我当然可以实现某种集中式计数器。但如果可能的话，我希望能够避免这种情况。我想尽量减少维护标识符所需的网络操作数。

欢迎提出任何建议!

Answer 1

您希望在 10 年内每秒生成 1000 个数字。所以你会生成

1000*60*60*365*10 = 315360000000

您想使用 35 位数字。有

2**35 = 34359738368

您将生成的最小重复项数为 3​​15360000000 - 34359738368，等于 281000261632。这是 X 的下限。这是不言而喻的。假设你设法从 2**35 可用的每个可能值中采样了一些惊人的怪胎。那么您制作的所有其他 sample 都是重复的。

我想我们可以有把握地得出结论，35 位是不够的。

就生成高质量的伪随机数而言，很明显 System.Security.Cryptography.RNGCryptoServiceProvider 是您提供的三个中的最佳选择。

如果您真的想要独特性，我建议您执行以下操作:

1. 为每个分布式节点分配一个唯一的 ID 范围。
2. 让每个节点从该 ID 值池中唯一分配。例如，节点从第一个值开始，并在每次要求生成新值时将 ID 递增 1。

如果唯一性很重要，这确实是最好的策略。但是您可能需要为您的 ID 投入更多的空间。