ハッシュマップへの同時読み込み/書き込みのための最も速い解決策は何ですか？

Question

生のパケットを受信して​​変換してキューに入れるネットワークサービスを作成しています。変換されたパケットをキューから取り出し、いくつかのルールに基づいてハッシュマップを更新するワーカースレッドもあります。異なるワーカースレッドからのハッシュマップの同時更新を防ぐために、私はmutexを使用する必要があります。残念なことにmutexを使用するとパフォーマンスが大幅に低下します。私はこのために回避策を見つける必要があります。 EDITED

： 変換されたパケットは、このSESSION_IDは、ハッシュマップキーとして使用され、を sessio_id含みます。 SESSION_IDが最初である任意の挿入前または更新を検索し、存在する場合に何SESSION_IDは、新しいエントリがSESSION_IDは、すでに私はちょうど更新が存在するそうでない場合は、が、これはまさに私がmutexロックを使用する場所ですとを追加で見つからなかっ既存の値であり、単なる値の更新に使用されるmutexロックはありません。 boost :: unordered_mapを基になるハッシュマップとしてを使用していることを知るのに役立つかもしれません。以下

は、私が使うロジックのpsudoコードです：

if hash.find(session_id) then 
     hash.update(value) 
    else 
     mutex.lock() 
     hash.insert(value) 
     mutex.unlock() 
    end 

あなたの提案は何か？道による

これは私の作業環境やツールである：

コンパイラ：C++（GCC）

スレッドライブラリ：pthreadの

OS：Ubuntuの14.04

Answer 1

最速のソリューションは次のようになり各スレッドが独自のデータセットを使用するようにデータを分割するため、ロックを一切必要としません。おそらく、いくつかの重要なデータに基づいてスレッド間でメッセージを配布することでそこに到達することができます。

第二に最善の解決策は、通常、複数、並列の読み取りアクセスを許可しますが、一つだけhttps://gcc.gnu.org/onlinedocs/gcc-4.1.0/gcc/Atomic-Builtins.html
読み書きスピンロックを参照して、リード・ライト・スピンロックは、CライブラリからC++ 11のアトミックまたは機能のいずれかを使用して実装持っているだろう（もちろん、すべての読み取りアクセスもブロックします）。

Linuxには読み書き可能なmutexもありますが、手作りの実装よりもわずかに遅いことがわかりました。

Answer 2

ロックフリーのデータ構造を調べましたか？ Andrei AlexandrescuとMaged Michaelの興味深い論文を参照することができます。Lock-Free Data Structures with Hazard Pointers類似のアイデアを使用する実装の例は、libcds Githubリポジトリにあります。

Facebookのfolly AtomiHashMapとIntelのTBBは、ロッキングをある程度使用しますが、高性能の同時ハッシュマップも提供します。

もちろん、これらのアプローチでは読み込みと統合の作業を少し必要としますが、現在のロック戦略がボトルネックであると判断した場合は、コストに見合う価値があります。