すべてのクライアントについて、サーバーはその特定のクライアントのセッションを作成します。セッションの有効期限は1日です。そうすれば、最大10億回のセッションが終了します。膨大な数のセッションを格納するための最も効率的なデータ構造は何ですか？
ハッシュマップを使用すると、クライアントがサーバーと通信するときに検索が高速になるとします。しかし、期限切れのセッションを消去する必要があります（たとえば、1時間に1回）。消去中、膨大な数のために時間がかかることがあり、これによりサーバーはクライアントからの通信を処理できなくなります。
だからこそ高性能のソリューションはありますか？つまり、期限切れの地図を消去するために地図をロックしたくないということです。
私はマップが本当に最高のコレクションだとは思わない。あなたが念頭に置いて言ったことで、私はセット（あなたが注文を必要としないならば順序付けられていないもの）に行きます。あなたは同じセッションを2回も持っていないので、彼らはすべて異なっていて、マップが提供する関連付けが本当に必要ないか、問題を正しく理解できませんでした。
セッション数が非常に多い場合、データ構造を使用するのはおそらく単純すぎます。少し異なる方法が必要です。
Redisまたは別のキー値ストアにセッションデータを格納する方法を調べます。これは、負荷の高いサーバーではより一般的です。レディスやその他のほとんどの人は、永続性を提供し、バックグラウンドで物事をクリアする必要がある場合はロックの問題はありません。
単純な解決策：ハッシュテーブルを使用します。バケットを検索してエントリを探しているときは、期限切れのセッションをすべて削除します。とにかくチェーンを探しているので、これはほとんど無料です。期限切れにセッションがすぐに削除されることは保証されませんが、有効期限が切れたセッションを含むチェーンはその後も検索される可能性が非常に高いです。
ハッシュテーブルを、サーバーの容量となる予定の固定数のバケットに設定する必要があります。これにより、再ハッシュする必要がなくなり、各バケットチェーンを独立してロックすることができます。ただし、チェーンごとにロックは必要ありません。同じロックを複数のチェーンにも使用できます。要求のピーク時に予想されるロック競合が低くなるのに十分な数のロックを選択します。同時にアクティブなハンドラスレッドの数に基づいて適切な数を計算することができます。チェーンがメモリに常駐している場合、チェーン検索にはほとんど時間がかかりません。したがって、ほとんどの場合、コンテキストスイッチの前に完了します。したがって、「同時にアクティブ」とは、カーネルプロセスにマッピングされているだけでなく、実際にCPUにマップされ実行されていることを意味します。したがって、小さなベクトルのロックでも、バケツチェーンの競合を非常に低く抑えることができます。
これを処理する1つの方法は、セッションを保持するためのハッシュマップとMRU（最近使用された）リストを作成することです。 MRUリストは、二重リンクリストとして実装されています。ユーザーがサイトにアクセスすると、そのセッションはMRUリストの先頭に戻されます。また、セッションが作成されるたびに、システムはMRUリスト内の最後の項目をチェックして、最も古いセッションが期限切れになったかどうかを確認し、削除することができます。
また、リストの最後に期限切れのセッションをすべて削除することもできます。
さらに、期限切れのセッションがまだ削除されていない場合は、ルックアップコードでそのセッションを削除する必要があります。だから、
、あなたが要求を取得する際に、一連のイベントは次のようなものになります。あなたが期限切れのセッションをクリーンアップすることは、あまりにも長い間、あなたのハッシュマップをロックすることを心配している場合
session = get session info from user token
if no session
create session
add to front of MRU list
else if session has expired
delete from mru list
remove from hash map
else // session has not expired
move session to front of MRU list
end
// delete expired sessions
p = last item in MRU list
while p has expired
prev = p->prev
remove from MRU list
delete from hash map
p = prev
end
を、制限を設定期限切れのセッションの数を一度に削除します。新しいセッションが追加されたときに期限切れのセッションを2つだけクリーンアップするように設定すると、データ構造がロックされる時間が最小限に抑えられ、期限切れのセッションが長くなりすぎることはありません。
Downvoter？ downvoteの理由を指定するのが通例です。 –
_ "期限切れのものを消去するためにマップをロックしたくありません。" - 消去する必要のあるハッシュを別のコンテナに保存し、単一のリース操作の場合にのみ地図をロックすることができます。 –
これは、C++プログラミングの問題の範囲を超えて、非常に幅広いアーキテクチャ上の質問です。 –
とにかくセッションの状態はどのくらいですか？数十億という数は、外部記憶装置を必要とするようであり、RAMに適しているよりもパフォーマンスのトレードオフやアルゴリズムがかなり異なる場合があります。 – doynax