1

興味のある方へ:探している動作のコードを実装し、google-code でオープンソース化しました。ここで手に入れよう！pojo-mvcc

--

こんにちは、みんな、

長期キャッシュから作成された短期キャッシュを多数含むフレームワークを作成しようとしています。これらの短期間のキャッシュは、元の長期間のキャッシュからのクローンであるコンテンツ全体を返すことができる必要があります。

私が実際に構築しようとしているのは、短期間のキャッシュのトランザクション分離のレベルです。ユーザーは短期キャッシュのコンテンツを変更できる必要がありますが、長期キャッシュへの変更は反映されるべきではありません (キャッシュの種類によっては、変更をプッシュスルーする必要がある場合もあります)。

説明するために最善を尽くします。

master-cache contains: [A,B,C,D,E,F] 状態 [A,B,C,D,E,F] で作成された一時キャッシュ

1) 一時キャッシュはアイテム G を追加します: [A,B,C,D,E,F] 2) 一時キャッシュはアイテム B を削除します: [A,C,D,E,F]

master-cache の内容: [A、B、C、D、E、F]

3) マスターキャッシュは項目 [X,Y,Z] を追加します: [A,B,C,D,E,F,X,Y,Z]

一時キャッシュの内容: [A,C,D,E,F]

アイテムの値が変更される可能性があり、常に更新されるべきではない場合、事態はさらに難しくなります (そのため、基になるオブジェクト インスタンスを共有することさえできず、クローンを使用する必要があります)。

ArrayList で標準の Collection コンストラクターを使用して List の新しいインスタンスを作成するという単純なアプローチを実装しましたが、項目が約 200,000 になると、システムはメモリ不足になります。200,000 という値が反復するには大きすぎることはわかっていますが、コードに少し負荷をかけようとしています。

どういうわけかリストを「プロキシ」できるのではないかと考えていたので、一時キャッシュはマスターキャッシュを使用し、すべての変更を保存します (事実上、変更のメメント)。一時キャッシュを反復するか、特定のインデックスでアイテムを取得します。また、リストの内容にいくつかの変更を加えたい場合 (「自動更新」であるかどうかにかかわらず、一時キャッシュのタイプに応じて)、完全に自分の深さから抜け出します。

技術やデータ構造、または試して研究するための一般的な概念へのポインタは大歓迎です。

乾杯、

アイドス

4

1 に答える 1

2

これがあなたがしたいことです。MVCC、Multi Version Currency Control として知られているものに似たもの。

簡単に言えば、トランザクション ID をキャッシュ要素に関連付ける必要があります。

したがって、キャッシュ エントリは次のようになります。

public class CacheEntry {
    long transactionId;
    boolean deleted;
    Object value;
}

キャッシュ エントリは、transactionid の逆順でリストに格納されます。

キャッシュ要素を取得するときは、(ハッシュ マップで) リストを調べます。次に、YOUR トランザクションのトランザクション ID よりも小さいか等しい最大のトランザクション ID を持つ値を検索します。

それでは、DELETE の問題を考慮に入れましょう。

「ABC」を探しているトランザクション 10 があります。ABC は既にキャッシュにあり、トランザクション 5 によって入れられたと仮定します。

したがって、T10 は ABC のエントリのリストを取得し、リストを下方向に検索して、T5 に値「123」があることを発見します。T5 は、T10 以下の最高のトランザクションです。T10 は、ABC の値を 123 から 456 に変更します。

今度は T12 がやってきて、ABC を探します。T10 から値が 456 であることがわかります。T12 は ABC を削除することを決定したため、T12 の「削除された」キャッシュ エントリがキャッシュ エントリ リストに配置されます。T10 が ABC を再度検索しようとすると、456 が見つかります。これは、12 > 10 であり、最高のトランザクション <= 10 が T10 であるため、削除が表示されないためです。

T14 がやって来て、ABC を検索しますが、それを見つけることができず (「削除済み」であるため)、789 という新しい値を挿入します。

したがって、最終的に、キャッシュ リストは次のようになります。

{tid: 14 deleted: false value: 789}
{tid: 12 deleted: true  value: nul}
{tid: 10 deleted: false value: 456}
{tid:  5 deleted: false value: 123}

次に発生する問題は、開いているトランザクション全体の可視性を扱うことです。つまり、別のトランザクションは、コミットされていない別の開いているトランザクションからのデータを見ることができます。ただし、バージョンのリストをスキャンして適切な候補を探すときに基準を調整するだけなので、それほど難しくはありません。また、トランザクション ID とそのステータス (オープン、コミット済み、ロールバック) のリストを保持できます。

最後に、ルーズエンドをクリーンアップするメカニズムを考え出す必要があります。2 つのトランザクションをコミットした後、他に開いているトランザクションがない場合は、古いレコードを削除できます。

たとえば、T5 と T10 のデータがあり、両方がコミットされている場合、T10 は現在「現在」の状態であるため、誰も T5 のデータを再び「見る」ことはできません。したがって、T5 行を削除できます。

これはおそらく、単純にキャッシュを反復処理し、古いトランザクション エントリを削除することによって行うのが最適です。

それが要点です。明らかに悪魔は細部に宿ります。

于 2010-04-10T15:48:54.843 に答える