友好的列表作为更改日志
我需要关于数据结构的建议以用作原子更改日志。
我试图实现以下算法。 存在更新内存映射的传入更改流。 在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）。 整个“更新”从任意数量的线程中调用。 由于域语义原因，一些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变更”的数据结构的建议。 我不想使用[更改]，因为它“太有序”，恐怕会有太多的冲突，这会迫使整个事务重试。 如果我在这里错了，请纠正我。
我不能使用Set（https://hackage.haskell.org/package/stm-containers-0.2.10/docs/STMContainers-Set.html），因为我仍然需要保留一些命令，例如事务提交的顺序。 我可以为它使用TChan，它看起来像一个很好的匹配（正是事务提交的顺序），但我不知道如何实现“刷新”功能，以便它可以将整个更改日志的一致视图组合在一起与数据集。
目前的实现是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
-- ...
但我仍然不确定将整个列表作为频道的一个元素是否是一个很好的解决方案。
我可能只是列表，看看它需要多大的性能。 鉴于此，您应该认为，追加到列表末尾并将其倒转为O（n）操作，所以您应该尽量避免这种情况。 也许你可以预先输入如下所示的更改：
update dataSet existingChanges newChange = do
-- ...
return (dataSet, newChange : existingChanges)
另外，你的flush的例子有一个问题，读取和更新状态根本不是原子的。 您必须使用如下所示的单个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：出队可能很适合你的问题，但是出现固定大小会迫使你处理这个问题，即你的作者可能会产生比你的读者可能产生更多变化的问题。 出列可以无限增长，但你的内存可能不是。 矢量的开销很低。
我做了一些（非常简单的）调查https://github.com/lolepezy/rpki-pub-server/tree/add-storage/test/changeLog模拟我想要的负载类型。 我使用相同的STMContainers.Map作为变更日志的数据集和常用列表。 为了跟踪事务重试次数，我使用了Debug.Trace.trace，意思是跟踪打印的行数。 通过跟踪打印的唯一行数量可以提供我承诺的事务数量。
结果在这里（https://github.com/lolepezy/rpki-pub-server/blob/add-storage/test/changeLog/numbers.txt）。 第一列是线程的数量，第二列是总共生成的变更集的数量。 第三列是没有更改日志的情况下跟踪调用的数量，最后一列是包含更改日志的跟踪调用的数量。
显然，大多数时间更改日志会增加一些额外的重试次数，但它几乎不重要。 所以，我猜，可以说任何数据结构都足够好，因为大部分工作都与更新地图有关，并且大部分重试都是因为它而发生的。
链接地址: http://www.djcxy.com/p/81459.html