ClickHouse中rand64()函数碰撞概率咨询：Int64主键场景

一、rand64()的碰撞概率计算 #

Int64的取值范围是[0, 2^64-1]，总共有约1.8e19个可能值。根据生日悖论，生成N个随机值时的碰撞概率近似公式为：

P ≈ N² / (2 * 2^64)

针对数十亿行的规模：

• 当N=1e9（10亿）时，碰撞概率≈(1e9)²/(2*1.8e19)≈2.78%，这个概率已经不可忽视，意味着每36次10亿规模的生成就可能出现一次碰撞；
• 当N=2e9（20亿）时，碰撞概率飙升至≈11.1%，碰撞风险显著提升。

需要注意的是，这是基于"真随机"假设的计算，而rand64()作为线性同余生成器（LCG）是伪随机，如果其周期短于你的数据规模，碰撞是必然发生的，概率直接变为100%。

二、与UUID的碰撞风险对比 #

广泛使用的UUIDv4基于122位随机数（剩余6位为版本和变体标识），总可能值约为5.3e36。同样代入生日悖论公式：

• 当N=1e9时，碰撞概率≈(1e9)²/(2*5.3e36)≈9.4e-20，这个概率低到在人类可观测的范围内几乎不可能发生。

UUID的缺点是需要128位存储（比Int64多一倍），但在碰撞风险上完全碾压rand64()，这也是UUID成为分布式主键首选的核心原因之一。

三、LCG（rand64()）的周期与参数影响 #

你提到rand64()采用线性同余生成器，但缺少关键参数。LCG的周期长度由三个参数决定：模数m、乘数a、增量c，对于64位LCG（m=2^64）：

• 若要达到最大周期2^64，必须满足三个条件：c与m互质（即c为奇数）、a-1是4的倍数、a-1能被m的所有质因数整除（这里m的质因数只有2，所以只需满足前两个条件）；
• 如果参数不满足上述要求，周期会大幅缩短，比如c为偶数时，周期可能只有2^62甚至更短。

如果rand64()的周期小于你的数据规模（比如数十亿），生成器一定会重复之前的值，碰撞无法避免。在不知道参数的情况下，你无法确认其周期是否足够覆盖数据量，这是极大的风险点。

四、可行替代方案 #

如果必须使用Int64主键且不能用UUID，推荐以下几种方案：

• 自增/序列生成器：使用全局唯一的自增ID（比如数据库自增列、分布式ID生成器如雪花算法变种），完全避免碰撞，缺点是需要维护全局唯一的生成逻辑，分布式场景下可能需要协调；
• 加密安全随机数+唯一性校验：使用加密安全的随机数生成器（而非LCG）生成64位值，插入数据库时依赖唯一约束校验，若插入失败则重试生成新值。这种方式可以规避LCG的周期问题，同时通过重试解决低概率的碰撞；
• 时间戳+随机数组合：将64位拆分为时间戳（比如高40位，可覆盖约34年的毫秒级时间）和低24位随机数，同一毫秒内最多生成2^24=1677万唯一值，只要并发量不超过这个阈值，就能保证无碰撞，同时保留一定的随机性。

内容的提问来源于stack exchange，提问作者Ivan Longin