16. Cache Digests（キャッシュダイジェスト）

Cache Digest はインターネット・オブジェクト・キャッシング・サーバーの中身（コンテンツ）の要約です。それは、特定のURLがキャッシュにあるかどうかを圧縮されたフォーマってで保持しています。
圧縮には"lossy"テクニックが使われます。これは圧縮要因が100%正しい状態ではない圧縮を行うことで高い圧縮性能を持っています。

キャッシュサーバはお互いに定期的にダイジェストの交換を行います。
クライアントからオブジェクト(URL)を要求されたとき、キャッシュはpeer（隣接）のダイジェストも使い、どちらがオブジェクトを持っていないかを調べ持っていればそのオブジェクトを返します。このときキャッシュは最も緊密な隣接キャッシュのオブジェクトを要求します。（このためにSquidは、これを決めるためにNetDBデータベースを使います）

Squidはダイジェストが enabled になっているときだけ、ダイジェストのリクエストを行うことに注意してください。　disable だった場合には、隣接ダイジェストIFFは、隣接のキャッシュからダイジェストを取ってこないでしょう。
ダイジェストのチェックはとても早く、またこれによって隣接へのリクエスト要求が削減されます。結果として：

• 待ち時間が短縮されレスポンスが改善されます。
• ネットワークが有効に利用されます。

キャッシュダイジェスト（仲間のキャッシュへコンテンツを尋ねる）の利用と、キャッシュダイジェストの生成（仲間のキャッシュの為の）は独立している事に注意してください。　この為、キャッシュは自身がダイジェストを使わなくても隣接の仲間の為にダイジェストの作成ができまし、またその逆もあり得ます。

キャッシュダイジェストはBloom Filters（これは検索におけるキーの配置を表している）を基本にしています。
キャッシュ・ダイジェストを構築するときに:

• 最初にすべて0にセットされた m ビットの１次元の整列が割り当てられます。
• ｋ個の独立したハッシュ関数を使って分散された値が、 範囲が1～mの間で h1, h2, hk,として選ばれます。
• キーnが示された処に配置されます。即ち： A={a1, a2, a3 .... an}

■ キーの追加：

aというキーを追加するにあたり、キーは各ハッシュ関数によって計算される。　それは h1(a),h2(a),....,hk(a)というように計算され示されます。
各ハッシュ関数による値は、１がセットされるキーがセットされる配列の為のインデックスを表します。　従って６桁のハッシュ関数を持つダイジェストでは、各キーが6ビットとして追加されます。
多くの異なるキーが、追加の際に複数の１つの特定のビットにセットされる原因になるかもしれない事に注意してください。

■ キーの検索：

キーの存在を検索する場合、配列へのインデックスは上述のハッシュ関数から計算されます。

• もし配列上のビットに0が含まれるならキーは存在しません。
• 配列上のすべてのビットが1ならばキーは存在します。

ダイジェストは衝突が起こる可能性がある事に注意してください。それによって、ダイジェストが示す鍵の存在が不正確なことがあります。衝突の確率が決してゼロになることができませんが、それはコントロールすることができます。ダイジェストのサイズをエントリに対して大きくすることで、確率を低くすることができます。　またハッシュ関数の数は確率に影響します。

■ キーの削除：

キーを削除するために、単純に追加と同じ方法で得られたビットを0にする訳にはいきません。　それゆえ、削除のサポートには、カウンターは配列上のそれぞれのビットポジションに必要です。　プロセスとこれを次のように：

• キーの追加において、該当するビットを１にする際にそれに対応するカウンターに１を増分
• キーの削除においてカウンターから１を減少。この時、カウンターが0になったなら一致するビットをすべて0にする。

初期化時に、容量（capacity）オブジェクトとしてキャッシュに格納できる数のセットです。　これには上限と下限があります。
配列の計算には、以下の式が利用されます。（bits_per_entry は現在は5です）

ダイジェストの数はこれ故以下のようのになります。