3

時間の経過とともに変更が加えられる、単一タイプのアイテムの 1 つのプライマリ コレクションが必要です。定期的に、いくつかのスレーブ コレクションがプライマリ コレクションと同期されます。プライマリ コレクションは、アイテムのデルタをスレーブ コレクションに送信する必要があります。

Primary Collection: A, C, D
Slave Collection 1: A, C    (add D)
Slave Collection 2: A, B    (add C, D; remove B)

スレーブ コレクションは独自にアイテムを追加または削除することはできず、別のプロセスに存在する可能性があるため、おそらくパイプを使用してデータをプッシュします。

コレクションが非常に大きくなる可能性があるため、必要以上のデータをプッシュしたくありません。

これには、どのようなデータ構造と戦略が理想的でしょうか?

4

2 に答える 2

1
  • すべてのデータをプッシュしない場合は、パイプ帯域幅を使用する代わりに、メイン メモリを使用する一種のログが必要です。CPU とメモリの使用量の適切なバランスを見つけるためのパラメーターは、「プッシュ」頻度です。
  • あなたの質問から、複数のスレーブプロセスがあると思います。この場合、マスター プロセスでダブル バッファリングを使用する一部の共有メモリまたはCMA (Linux) アプローチは、同期中の全体的なパイプ スループットを最適化するために使用されるマルチスレッド プッシュを必要としないため、複数のパイプよりもはるかに優れたパフォーマンスを発揮するはずです。
    スレーブ プロセスは、マスターが masterCollectionB (masterCollectionA からのコピーで初期化される) を変更している間、コピーせずに masterCollectionA から読み取るためのグローバル同期バリアを使用して通知することができ、その逆も同様です。コレクションへのアクセスは、スレーブとマスターの間で連動する必要があります。スレーブは、マスターからの次の更新の試みを過ぎてそれをブロックする場合、そのコレクション (スナップショット) をコピーして、続行できるようにすることができます。スレーブ プロセスの変更は、単一要素のコピー オン ライト戦略で実装できます。この協調的なアプローチは実装がかなり簡単で、スレーブ プロセスが毎回スナップショット全体をコピーしない場合、全体的なメモリ消費量は低くなります。
于 2013-11-16T15:26:51.910 に答える
1

そのために、差分実行を使用します。

(ちなみに、「奴隷」という言葉は一部の人にとっては不快ですが、それには理由があります。)

リモート サイトごとに、リモート サイトに存在するものを表すシーケンシャル ファイルがプライマリ サイトにあります。

プライマリ コレクションをウォークスルーするプロシージャがプライマリ サイトにあり、ウォーク中に対応するファイルを読み取り、リモート サイトに現在存在するものと存在すべきものの違いを検出します。これらの違いによってデルタが生成され、リモート サイトに送信されます。同時に、プロシージャは、デルタが処理された後にリモート サイトに存在するものを表す新しいファイルを書き込みます。

これの利点は、プライマリ コレクションでの変更イベントの検出に依存しないことです。これらの変更イベントは信頼性が低く、自己キャンセルされたり、他の変更によって無関係になったりすることが多いため、リモート サイトへの不要な送信を削減できます。 .

コレクションがモノの単純なリストである場合、これはリモート コレクションのローカル コピーを保持しdiff、デルタを取得するアルゴリズムを実行することになります。以下に、そのようなアルゴリズムをいくつか示します。

コレクションを並べ替えることができる場合 (A、B、C の例のように)、マージ ループを実行するだけです。

while(ix<nx && iy<ny){
  if (X[ix] < Y[iy]){
    // X[ix] was inserted in X
    ix++;
  } else if (Y[iy] < X[ix]){
    // Y[iy] was deleted from X
    iy++;
  } else {
    // the two elements are equal. skip them both;
    ix++; iy++;
  }
}
while(ix<nx){
  // X[ix] was inserted in X
  ix++;
}
while(iy<ny>){
  // Y[iy] was deleted from X
  iy++;
}

コレクションを並べ替えることができない場合 (レーベンシュタイン距離との関係に注意してください)、

Until we have read through both collections X and Y,
  See if the current items are equal

  else see if a single item was inserted in X
  else see if a single item was deleted from X

  else see if 2 items were inserted in X
  else see if a single item was replaced in X
  else see if 2 items were deleted from X

  else see if 3 items were inserted in X
  else see if 2 items in X replaced 1 items in Y
  else see if 1 items in X replaced 2 items in Y
  else see if 3 items were deleted from X

  etc. etc. up to some limit

プロシージャは頻繁に実行する必要がないため、通常、パフォーマンスは問題になりません。

この概念を示す大まかなビデオと、ユーザー インターフェイスを動的に変更するために使用されるソース コードがあります。

于 2013-11-16T15:27:11.007 に答える