STM友好列表作为更改日志

Question

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

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

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

其中DataSet是一个映射(目前它是来自stm-containers包的Map,https: //hackage.haskell.org/package/stm-containers-0.2.10/docs/STMContainers-Map.html ).从任意数量的线程调用整个"更新".由于域语义,一些Change可以被拒绝,我使用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"的数据结构的建议.我不想使用[更改],因为它"太有序"而且我担心会有太多冲突,这将迫使整个事务重试.如果我错了,请纠正我.

我不能使用Set(https://hackage.haskell.org/package/stm-containers-0.2.10/docs/STMContainers-Set.html),因为我仍然需要保留一些订单,例如事务提交的顺序.我可以用TChan它,它看起来像一个很好的匹配(准确的交易秩序提交),但我不知道如何实现"刷新"功能,使得它会给整个更改日志的统一视图在一起使用DataSet.

当前的实现是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
      -- ...

但我仍然不确定将整个列表作为频道元素传递是否是一个简洁的解决方案.

Answer 1

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

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

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

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：出队可能也很适合您的问题，但是固定大小会迫使您处理这样的问题：您的编写者可能会产生比读者可以冲出的更多的更改。出队可以无限增长，但你的 RAM 可能不会。而且向量的开销相当低。