haskell - STM 友好列表作为更改日志

Question

我需要有关用作原子更改日志的数据结构的建议。

我正在尝试实现以下算法。有流量传入更改更新内存中的映射。在类似 Haskell 的伪代码中它是

    update :: DataSet -> SomeListOf Change -> Change -> STM (DataSet, SomeListOf Change)
    update dataSet existingChanges newChange = do
      ...
      return (dataSet, existingChanges ++ [newChange])

其中 DataSet 是一个映射(当前它是 stm-containers 包中的映射 https://hackage.haskell.org/package/stm-containers-0.2.10/docs/STMContainers-Map.html )。整个“更新”是从任意数量的线程调用的。由于域语义，某些更改可能会被拒绝，我使用 throwSTM 来丢弃事务的效果。如果成功提交，“newChange”将添加到列表中。

存在调用以下函数的单独线程:

    flush :: STM (DataSet, SomeListOf Change) -> IO ()

这个函数应该获取 DataSet 的当前快照以及更改列表(它必须是一致的对)并将其刷新到文件系统，即

    flush data = do
      (dataSet, changes) <- atomically $ readTVar data_
      -- write them both to FS
      -- ...
      atomically $ writeTVar data_ (dataSet, [])

我需要有关用于“SomeListOf Change”的数据结构的建议。我不想使用[Change]，因为它“太有序”，我担心会出现太多冲突，从而迫使整个事务重试。如果我这里错了，请纠正我。

我无法使用 Set ( https://hackage.haskell.org/package/stm-containers-0.2.10/docs/STMContainers-Set.html )，因为我仍然需要保留一些顺序，例如事务提交的顺序。我可以使用 TChan，它看起来很匹配(正是事务提交的顺序)，但我不知道如何实现“刷新”功能，以便它能够提供整个更改日志的一致 View 与数据集。

当前的实现在这里 https://github.com/lolepezy/rpki-pub-server/blob/add-storage/src/RRDP/Repo.hs ，分别在函数 applyActionsToState 和 rrdpSyncThread 中。它使用 TChan，但似乎以错误的方式进行。

提前谢谢您。

更新:合理的答案似乎是这样的

    type SomeListOf c = TChan [c] 

    update :: DataSet -> TChan [Change] -> Change -> STM DataSet
    update dataSet existingChanges newChange = do
      ...
      writeTChan changeChan $ reverse (newChange : existingChanges)
      return dataSet

   flush data_ = do
      (dataSet, changes) <- atomically $ (,) <$> readTVar data_ <*> readTChan changeChan
      -- write them both to FS
      -- ...

但我仍然不确定将整个列表作为 channel 元素传递是否是一个巧妙的解决方案。

Answer 1

我可能只是按照这个列表看看它在性能方面需要多远。鉴于此，您应该考虑到追加到列表末尾和反转列表都是 O(n) 操作，因此您应该尽量避免这种情况。也许您可以像这样添加传入的更改:

update dataSet existingChanges newChange = do
  -- ...
  return (dataSet, newChange : existingChanges)

此外，您的刷新示例存在读取和更新状态根本不是原子的问题。您必须使用单个原子调用来完成此操作，如下所示:

flush data = do
  (dataSet, changes) <- atomically $ do
    result <- readTVar data_
    writeTVar data_ (dataSet, [])
    return result

  -- write them both to FS
  -- ...

然后，您可以按相反的顺序写出它们(因为现在 changes 包含从最新到最旧的元素)，或者如果将它们从最旧到最新写出很重要，则可以在此处反转一次。如果这很重要，我可能会选择一些允许 O(1) 元素访问的数据结构，就像一个好的旧向量一样。

当使用固定大小的向量时，你显然必须处理它可能变得“满”的问题，这意味着你的编写者必须等待flush来完成它的工作，然后再添加新鲜的变化。这就是为什么我个人会首先选择简单的列表，看看它是否足够或需要改进的地方。

PS:A dequeue可能也很适合您的问题，但是固定大小会迫使您处理这样的问题:您的作者可能会产生比读者可以冲出的更多的更改。出队可以无限增长，但你的 RAM 可能不会。而且向量的开销相当低。