ruby-on-rails - Ruby on Rails 中 Postgresql 的线性同余生成器，用于生成唯一的、不重复的随机数？

Question

我可以使用 LCG(又名线性同余生成器)为我的员工提供一个9 位数字、唯一但不重复的工作 ID。

该算法应使用 BSD rand() 公式，初始种子(状态 0)为 111,111,111，但将 mod 2^31 更改为 mod 999,999,937:

但是我是否必须始终从最后添加的员工中检索工作 ID 才能计算下一个员工？

请帮忙!

Answer 1

Can I use LCG, aka Linear Congruent Generator, to give my staff a 9-digit, unique but non-repeating work ID.

这取决于你如何使用它。

如果您想为每个请求生成一个工作 ID，那么不，您不能，因为

LCGs are not suitable for parallel programming. Multiple threads may access the currently stored state simultaneously causing a race condition. In implementations which use same initialization for different threads, equal sequences of random numbers may occur on simultaneously executing threads. Random number generators, particularly for parallel computers, should not be trusted.

(参见 Wikipedia )

但是你可以预先生成一堆工作 ID，对于每个员工，只需将第一个未使用的工作 ID 分配给他/她即可。

例如，您可以使用 db/seed.rb 预先生成工作 ID(假设您有一个 AR 模型 WorkId)

db/seed.rb

total_work_ids = 10_000  # based on how many potential employees
state = 111_111_111      # the seed

total_work_ids.times do
  state = (1_103_515_245 * state + 12345) % 999_999_937
  WorkId.create(value: '%09d' % state)
end

更新

使用数据库存储工作 ID 可能仍然存在竞争条件，因为每次获取新的工作 ID 时，都会执行一个查询 (SELECT id, value FROM work_ids WHEREused = 0 LIMIT 1) 并需要一次更新(UPDATE work_ids SETused = 1 WHERE id = ?)，它不是原子的。

我认为最好的解决方案是在 Rails 应用程序外部实现外部服务，该服务以先进先出的方式提供工作 ID。该服务应该很快，因为所有 Rails 线程/进程都会访问它并阻止它们。

我认为redis set是存储那些未使用的工作 id 的好地方，因为它确保其中元素的唯一性，并且它的 spop 是原子的。