分散環境で使えそうな Lock-Free linked list を探している

erlang

いくつか論文を読んで見た。欲しいのは双方向リンクリスト。

  • Lock-Free Linked Lists Using Compare-and Swap
    • 単方向リンクリスト
  • A pragmatic implementation of non-blocking linked-lists
    • 単方向リンクリスト
    • deleted markd
  • "Two-Handed Emulation: How to build non-blocking implementations of complex data-structures using DCAS"
    • non-blocking doubly linked list
    • DCAS を利用して、link 付け替えと、現在作業中 step 番号を一度に更新。
    • 中途半端な状態は別のスレッドが協調フォロー。
    • グローバルな uid 保持場所を必要とするので p2p では使えなそう
  • "Lock-free deques and doubly linked lists"
    • 双方向に正しく traversal できる。（削除されたノード含んでいても良い）
    • link list が常に consistent
    • 各ノードが deleted mark を保持
    • CAS
    • deleted node の回収に参照カウント


一番最後の "Lock-free deques and doubly linked lists" が要件を満たしているのだが実装が大変そう。

  • 参照カウント。
  • prev/next 参照が複雑になる。deleted mark 見るとか。

など。


ふーむ。これは 2 フェーズコミットで普通にロックした方が良い気がしてきた。しかし 2 フェーズコミットも実装が面倒だよなあ。
と思ったら、global:set_lock(key, Nodes) で左右ロックすれば OK ？。