変更ログとしてのSTMにやさしいリスト

Question

アトミック変更ログとして使用するには、データ構造に関するアドバイスが必要です。

私は次のアルゴリズムを実装しようとしています。メモリ内のマップを更新するために入ってくる の変更の流れがあります。 Haskellのような擬似コードでは、DataSetがマップされ

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

（現在はそれがSTM-コンテナパッケージから地図、https://hackage.haskell.org/package/stm-containers-0.2.10/docs/STMContainers-Map.htmlである）です。 「更新」全体は任意の数のスレッドから呼び出されます。ドメインセマンティクスのために変更の一部が拒否される可能性があるため、トランザクションの影響を排除するためにthrowSTMを使用します。成功したコミットの場合、 "newChange"がリストに追加されます。この関数は変化する（それが一致ペアに有している）のリストと共に、データセットの現在のスナップショットを取り、それをフラッシュすることになっている

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

：

は、以下の関数を呼び出す別のスレッドが存在します

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

"SomeListOf Change"に使用するデータ構造についての助言が必要です。私は[あまりにも注文されている]ため、[変更]を使用したくないし、あまりにも多くの競合があり、トランザクション全体を再試行することが懸念される。私がここで間違っているなら、私を修正してください。

私はまだオーダーを保存する必要があるため、セット（https://hackage.haskell.org/package/stm-containers-0.2.10/docs/STMContainers-Set.html）を使用できません。トランザクションの順序がコミットされます。私はTChanを使用することができますが、それは良い一致（トランザクションのコミットの順番）のように見えますが、 "flush"関数を実装する方法がわからないので、変更ログ全体を一貫して見ることができますDataSetを使用します。

現在の実装は、applyActionsToState関数とrrdpSyncThread関数でそれぞれhttps://github.com/lolepezy/rpki-pub-server/blob/add-storage/src/RRDP/Repo.hsです。それは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) 

また、フラッシュのためのあなたの例では、読んで状態を更新することは全くアトミックではないという問題があります。あなたは（今changesがnewestからの要素が含まれているため、最も古いの）そしてちょうど逆の順序でそれらを記述するか、それは書くことが重要だ場合は、一度ここで逆転できる

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

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

：あなたはそうのような単一atomicallyコールを使用してこれを実現しなければなりませんそれらを最も古いものから最新のものに変えます。それが重要なのであれば、O（1）要素のアクセスが良い古いベクトルのようにできるいくつかのデータ構造に行くと思います。

固定サイズのベクトルを使用する場合、明らかに、「完全」になる可能性があるという問題に対処する必要があります。これは、作成者が新しく変更を追加する前に仕事をするのを待たなければならないことを意味します。だから私は個人的に単純なリストを探して、それが十分であるか、改善が必要なのかを確認するのです。

PS：dequeueでも問題には適しているかもしれませんが、一定のサイズになると、あなたの作家があなたの読者よりも多くの変更をもたらす可能性があるという問題に対処する必要があります。デキューは無限に成長することができますが、RAMはおそらくそうではありません。そしてベクトルはかなり低いオーバーヘッドを持っています。

Answer 2

私はいくつかの（非常に単純化した）調査をしました。私はおそらく私が持っていると思われる負荷のタイプを模倣しています。私は同じSTMContainers.Mapをデータセットと通常の変更ログのリストに使用しました。トランザクションの再試行回数を追跡するために、Debug.Trace.traceを使用しました。つまり、トレースによって出力された行数です。そして、という数字の行がトレースで表示されていると、コミットされたトランザクションの数がわかります。

結果は（https://github.com/lolepezy/rpki-pub-server/blob/add-storage/test/changeLog/numbers.txt）です。最初の列はスレッドの数、2番目の列は合計で生成されたチェンジセットの数です。 3番目の列は、変更ログのない場合のトレース呼び出しの数であり、最後の列は変更ログを含むトレース呼び出しの数です。

明らかに、ほとんどの時間変更ログでは余分な再試行が追加されていますが、それはかなり重要ではありません。だから、ほとんどの作業はマップの更新に関連しており、再試行の大半はそのために起こっているので、どのデータ構造でも十分だと言えるのは間違いないと思います。