在Haskell中为多线程提供高性能的独特时间戳ID

Question

我有多个线程处理事件。我想为每个事件分配一个纳秒级时间戳。这必须是唯一的ID。因此，在两个事件到达并被分配相同的时间戳的奇怪情况下，我希望其中一个事件时间戳增加一纳秒。考虑到实际精确度不在纳秒级别，就系统时间戳性质而言，这是可以接受的。

在一个线程中，这是一个微不足道的问题。但跨越多个线程，它变得更具挑战性。性能绝对至关重要，因此像典型的ID生成器之类的简单同步思路似乎会阻塞太多。

是否有一些方法可以在最小或没有锁定的情况下解决这个问题？

- mentics

Answer 1

为什么不将时间戳和唯一ID生成的任务分开呢？例如，有标准模块Data.Unique，它在IO中提供全局唯一值的供应，对于大多数情况来说应该足够快。或者，如果您需要更高级的东西，concurrent-supply包提供了一个高性能的并发唯一ID供应，并具有纯接口。

话虽如此，您可能可以使用POSIX单调时钟来实现这个目的，例如使用clock包：

import Control.Monad
import qualified System.Posix.Clock as Clock

main :: IO ()
main = replicateM_ 100 $ do
  time <- Clock.getTime Clock.Monotonic
  print (Clock.sec time, Clock.nsec time)

- ehird

---

@augustss：POSIX单调时钟？我不确定。如果它不够快，那就是将时间戳和ID生成分离的另一个很好的理由。 - ehird

@ehird，在所有情况下，以时间b创建的唯一ID是否比以时间a（更早）创建的唯一ID具有更高的值？ - J Fritsch

@JFritsch: Unique是基于一个原子增加的Integer，所以是的。（尽管从技术上讲，你只能得到一个Int，所以只有Eq和Ord实例可以区分前后环绕的值，但在64位机器上这不会成为问题。） - ehird

Answer 2

你是否可以使用两个信息作为唯一标识符？如果是这样的话，给每个线程赋予一个唯一的标识符，并且记录每个事件的纳秒级时间戳和分配时间戳的线程的ID。然后，问题就简化为在单线程情况下保证时间戳的唯一性所要做的任何事情。而且在初始化之后完全没有同步。

- Ben

Answer 3

你可以使用atomicModifyIORef来实现原子计数器。在GHC中，它是使用原子操作实现的，而不是锁定。

import Data.IORef
import System.IO.Unsafe

counter :: IO Int
counter = unsafePerformIO $ newIORef 0

getUnique :: IO Int
getUnique = atomicModifyIORef counter $ \x -> let y = x + 1 in (y, y)

- Dietrich Epp

---

@ehird：请不要对我的帖子进行重大更改，如果您有什么要补充的，请发表评论。 - Dietrich Epp

抱歉，我认为我所做的更改足够微不足道，但在保存之前又发现了另外两个错误。目前，“getUnique”始终返回“⊥”，而“counter”可以内联到其他表达式中，重复变量并破坏代码。此外，如果这两个问题都得到解决，那么“getUnique”将会有一个空间泄漏，因为thunk在连续执行时会不断增加。（顺便说一下，标准的“Data.Unique”模块已经提供了这个API。） - ehird

@ehird：这正是我想知道的信息，谢谢。 - Dietrich Epp

Answer 4

在基于C的语言中，我们通常会使用原子计数器来实现这一点——不需要锁定。如果您还想要一个时间戳，那将是一个单独的值。我对Haskell不确定，因为我不用它编写代码（尽管听起来很有趣）。

- justin

Answer 5

• http://hackage.haskell.org/package/greg-client 可能是吗？

- none

---

欢迎来到Stack Overflow！虽然这理论上可能回答了问题，但最好在此包含答案的要点，并提供参考链接。 - oers