本地唯一标识符

Question

问题：当你有一个.NET GUID要插入数据库时，它的结构应该像这样：

60 bits of timestamp, 
48 bits of computer identifier,
14 bits of uniquifier, and
 6 bits are fixed, 
----
128 bits total

现在我遇到了一个GUID问题，因为它是一个128位数，而我使用的一些数据库只支持64位数。

我不想通过使用自增的bigint值来解决这个困境，因为我想能够进行离线复制。

所以我想到了创建一个本地唯一标识符类，它基本上是将GUID缩小到64位值。

我想出了以下方法：

day  9 bit (12*31=372 d)
year 8 bit (2266-2010 = 256 y)
seconds  17 bit (24*60*60=86400 s)
hostname 12 bit (2^12=4096)
random 18 bit (2^18=262144)
------------------------
          64 bits total

现在我的问题是：时间戳基本上固定为34位，留下了30位用于主机名+随机数。

现在我的问题是： 1）您更愿意增加主机名哈希位大小并减少随机位大小还是增加随机位大小并减少主机名哈希位大小？ 2）是否存在一种哈希算法，将每个字符串缩减到n位？ 其中n理想情况下为12或尽可能接近。

- Stefan Steiger

Answer 1

实际上，.NET生成的GUID由6位固定位和122位随机位组成。

你可以考虑只使用64位随机位，但由于位数较小，碰撞的可能性增加。但这仍然比哈希更好。

- Stephen Cleary

---

有各种不同的方法，我也喜欢用带时间戳的“节点ID”的想法（没有随机性）。通过异或加密哈希（例如SHA1），您可以轻松地创建任意数量位的节点ID。当然，位数越少，节点ID冲突的可能性就越高。您提到的“唯一标识符”实际上被其他GUID算法用于处理系统时钟倒退，以保持时间戳在每个节点ID中的唯一性。但说到底，很难找到一种解决方案能够保证比纯随机性更少的碰撞。请记住，这就是.NET GUID所做的一切... - Stephen Cleary

虽然1/2^64的概率仍然非常小，但我不喜欢纯随机数的想法。但是我考虑过完全省略主机名哈希，只增加随机数到30位。但这不是一个好主意，因为对于n个离线客户端，这将使碰撞的几率达到2^30*n。对于100个客户端，这只有大约一千万分之一的几率。如果运气不好，可能会中头彩... - Stefan Steiger

1/2^64等于18千万亿分之一（1千万亿等于1万亿的平方，或1百万的平方）。如果你采用完全随机的方式... - Stephen Cleary

不，这是因为生日效应而产生的1/2^32。 - erikkallen

@erikkallen：实际上，碰撞的概率一开始非常小（1/2^64），随着id的生成而增加。你所考虑的是在预期发生碰撞之前生成的id数量（碰撞概率超过50%的标志）。在2^32（超过40亿）个id时，碰撞的概率为50%。不过，谢谢你提出生日效应，我确实忽略了它。 :) - Stephen Cleary

Answer 2

如果空间不是问题，为什么不使用两个64位宽的列，然后将guid一分为二，每个部分使用8字节，然后将它们转换为64位数字并存储在两个列中。这样，如果您需要升级到另一个系统，您仍将保持唯一性，只需要考虑重新组合这两列。

- Paul Farry

---

那么我将不得不为每个连接比较两个数字。这样做会不会降低性能太多？ - Stefan Steiger

你会在你的键中涉及一个额外的列[我假设guid是一个键]，所以你会有一个轻微的变化，但是这样你不会失去能够支持它的系统中的Guid，并且你也有一个解决方法来解决那些不支持的系统。 - Paul Farry

Answer 3

为什么要编写自己的随机数生成器？ 为什么不只是生成一个均匀分布的随机数呢？ 它可以很好地完成工作。 只需获取您想要的任何大小的第一个X位数字... 比如64位。

在SQL Server中，请参见此处了解有关RAND（）与NEWID（）的信息，这实际上是GUID与随机数生成器的控告。 此外，如果您需要比System.Random更随机的内容，请参见此处。

- mattmc3

---

完全随机的数字不是一个好主意，以我个人的看法。随着数据库越来越大，我不想担心重复和奇怪的错误。至少需要以某种方式集成一个时间戳。虽然考虑一下，最明智的做法可能是省略秒数，只增加随机整数的大小。这样我就可以有一个相当长的主机名哈希和一个相当长的随机数。 - Stefan Steiger