write throughというのは、Cacheへの書き込み時にCacheのsourceにも書き込んでしまうことです。読み出し時はキャッシュにデータがあればそれを読み、無ければCacheのsourceから読み込みます。容易に解るように、読み出しではcache hitするほど高速動作が期待できますが、書き込みではオーバーヘッド分だけ確実に遅くなります。多くのコンピュータシステムの場合、書き込みよりも読み出しの方が圧倒的に多いので、これでも充分意味のあるシステムになります。ちなみにCacheへの書き込み時より後でゆっくりとCacheのsourceに書きに行く方式はwrite backと呼びます。
さて、何もしないCacheと違って、write through cacheは内部にcache dataを保持する仕組みが必要です。keyに対してvalueを高速に見つけ出す必要があるので、java.util.Mapが使えます。
import java.util.Map;
import java.util.HashMap;
public class WriteThroughCache implements Cache {
private CacheSource source;
private Map cacheMap;
public WriteThroughCache(CacheSource source) {
this.source = source;
this.cacheMap = new HashMap();
}
...
}
Mapの実装としてHashMapを使っています。HashMapは同期化されていませんので、thread safeになっていません。これは後で検討が必要です。
readの処理では最初にcacheMapを見に行き、なければCacheのsourceから読み出すことになります。読み出した内容はcacheMapに保存した上で、呼び出し側に返します。
public Object read(Object key) throws CacheException {
if (cacheMap.containsKey(key)) {
return cacheMap.get(key);
} else {
Object value = this.source.read(key);
cacheMap.put(key, value);
}
}
ただ良く見ると、keyが新しいものになる度にcacheMapが大きくなってゆくことが予想できます。keyの数が予め制限されていることが判っていれば、これでも構わないのですが、通常は記憶領域の無駄遣いになってしまいます。あまり使うことのないkeyとvalueのペアは適宜cacheMapから追い出してしまいたいですね。
サイズの限られたCacheから不要と思われるkeyとvalueのペアを取り除く場合、理想的にはキャッシュの中にあるキーの中で「将来、最も後で使われるkeyとvalueのペア」を取り除くのが最も効率的であることが判っています(理論上の上限)。しかし個々の状況においてどのkeyが、将来、最も後で使われるのかを決定することは通常不可能であり、実質的に理想に近いアルゴリズムが検討されています。そのなかで最もポピュラーなものがLRU(Least Recent Used)アルゴリズムです。
LRUアルゴリズムは、将来を予想するのに過去の情報を使います。過去使われたのが一番古いkeyとvalueのペアが将来、最も後で使われると考えるわけです。これはデータの時間的局所性から導かれる予想です。いつもうまく行くとは限りませんが、多くのケースで理想に比較的近いことが知られています。
さて、WriteThroughCacheクラスでLRUを組み込むには、どうすれば良いでしょう。LRUでは、最後に使われたのが一番古いkeyを見つけ、そのエントリを破棄して、新しいkeyとvalueのペアに明渡すという処理が出来なければなりません。従ってkeyとvalueのペアが使用された時(つまりreadやwriteされた時)にそれを監視し、最後に使われたのがいつかを基にした順序を保持する構造が必要です。その順序構造に対して、最後に使われたkeyとvalueのペアを抜き出して最後尾に持ってゆくという処理を続ければ、順序構造の先頭が破棄する第一候補となります。
手っ取り早くkeyのListを作ることにしましょう。エントリを抜き出して最後尾に持っていったり、先頭を取ったりしますので、LinkedListを利用するのが良いと思われます。ちょっと書いてみます。
import java.util.Map;
import java.util.HashMap;
import java.util.List;
import java.util.LinkedList;
/**
* @author PoisonSoft
*
* Write Throughキャッシュの実装
*/
public class WriteThroughCache implements Cache {
public static final int MIN_CACHE_SIZE = 4;
private CacheSource source = null;
private int cacheSize = MIN_CACHE_SIZE;
private Map cacheMap = null;
private List usedList = new LinkedList();
/**
* Method WriteThroughCache.
* @param source
*/
public WriteThroughCache(CacheSource source, int size) {
this.source = source;
if (size < MIN_CACHE_SIZE) {
size = MIN_CACHE_SIZE;
}
this.cacheSize = size;
this.cacheMap = new HashMap(size);
}
/**
* @see Cache#read(Object)
*/
public synchronized Object read(Object key) throws CacheException {
Object value = null;
if ((value = getEntry(key)) != null) {
return value;
} else {
try {
value = source.read(key);
} catch (CacheSourceException e) {
throw new CacheException(e);
}
if (cacheMap.size() < cacheSize) {
addEntry(key, value);
} else {
replaceEntry(key, value);
}
return value;
}
}
/**
* @see Cache#write(Object, Object)
*/
public synchronized void write(Object key, Object value) throws CacheException {
if (getEntry(key) != null) {
replaceEntry(key, value);
try {
source.write(key, value);
} catch (CacheSourceException e) {
throw new CacheException(e);
}
} else {
if (cacheMap.size() < cacheSize) {
addEntry(key, value);
} else {
replaceEntry(key, value);
}
try {
source.write(key, value);
} catch (CacheSourceException e) {
throw new CacheException(e);
}
}
}
/**
* @see Cache#delete(Object)
*/
public synchronized void delete(Object key) throws CacheException {
if (cacheMap.containsKey(key)) {
deleteEntry(key);
}
try {
source.delete(key);
} catch (CacheSourceException e) {
throw new CacheException(e);
}
}
/**
* Method getEntry.
* @param key
* @return Object
*/
private Object getEntry(Object key) {
if (cacheMap.containsKey(key)) {
Object value = cacheMap.get(key);
if (usedList.contains(key)) {
usedList.remove(key);
}
usedList.add(key);
return value;
}
return null;
}
/**
* Method replaceEntry.
* @param key
* @param value
*/
private void replaceEntry(Object key, Object value) {
if (usedList.size() == 0) {
addEntry(key, value);
}
Object topKey = usedList.get(0);
usedList.remove(topKey);
cacheMap.remove(key);
cacheMap.put(key, value);
usedList.add(key);
}
/**
* Method addEntry.
* @param key
* @param value
*/
private void addEntry(Object key, Object value) {
cacheMap.put(key, value);
usedList.add(key);
}
/**
* Method deleteEntry.
* @param key
*/
private void deleteEntry(Object key) {
if (cacheMap.containsKey(key)) {
cacheMap.remove(key);
}
if (usedList.contains(key)) {
usedList.remove(key);
}
}
}
これで簡単なCacheは実現できます。thread safeにするにはcacheMapとusedListの2つのオブジェクトをロックするのはいやなので、read、write、deleteのメソッド自身をsynchronized指定してみました。