Mercurial > hg > blitz_stable

comparison src/org/dancres/blitz/arc/ArcCache.java @ 0:3dc0c5604566

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Initial checkin of blitz 2.0 fcs - no installer yet.
author Dan Creswell <dan.creswell@gmail.com>
date Sat, 21 Mar 2009 11:00:06 +0000
parents
children b7e52953b7a6
comparison
equal deleted inserted replaced
-1:000000000000 0:3dc0c5604566
1 package org.dancres.blitz.arc;
2
3 import java.io.IOException;
4
5 import java.util.Map;
6 import java.util.TreeMap;
7 import java.util.ArrayList;
8 import java.util.HashMap;
9
10 import java.util.logging.Logger;
11 import java.util.logging.Level;
12
13 import org.dancres.blitz.Logging;
14 import org.dancres.blitz.entry.ci.CacheIndexer;
15
16 import org.dancres.blitz.cache.Identifiable;
17 import org.dancres.blitz.cache.Identifier;
18 import org.dancres.blitz.cache.Cache;
19 import org.dancres.blitz.cache.CacheListener;
20 import org.dancres.blitz.cache.CacheListenerSet;
21
22 /**
23 A cache which implements ARC (see "ARC: A Self-Tuning, Low Overhead
24 Replacement Cache" in USENIX FAST '03) or, try,
25 <a href="http://citeseer.nj.nec.com/megiddo03arc.html"> CiteSeer</a>. <p>
26 */
27 public class ArcCache implements Cache {
28 static Logger theLogger =
29 Logging.newLogger("org.dancres.blitz.arc.cache");
30 /**
31 Used for rapid location of a relevant CBD in memory - saves us scanning
32 lists.
33 */
34 private Map theBlockIndex = new HashMap();
35
36 private Lru t1 = new Lru(Lru.T1);
37 private Lru t2 = new Lru(Lru.T2);
38 private Lru b1 = new Lru(Lru.B1);
39 private Lru b2 = new Lru(Lru.B2);
40
41 private int theTargetT1;
42
43 /**
44 Variable <i>c</i> in the ARC algorithmic description
45 */
46 private int theCacheSize;
47
48 private BackingStore theStore;
49
50 private CacheListenerSet theListeners = new CacheListenerSet();
51
52 public ArcCache(BackingStore aStore, int aCacheSize) {
53 theStore = aStore;
54 theCacheSize = aCacheSize;
55 }
56
57 public void add(CacheListener aListener) {
58 theListeners.add(aListener);
59 }
60
61 public int getSize() {
62 return theCacheSize;
63 }
64
65 /**
66 For recovery purposes, we wish to be able to ensure that something
67 has made it to disk and, if it hasn't, re-insert it to the cache.
68 This is different from insert which is used for those entries which
69 we know are not present on disk. We must first check disk and,
70 if there's no entry, populate the cache with a new one.
71 */
72 public RecoverySummary recover(Identifiable anIdentifiable)
73 throws IOException {
74
75 // Try a fetch from disk
76 Identifiable myIdentifiable = theStore.load(anIdentifiable.getId());
77
78 // Did we get it?
79 if (myIdentifiable == null) {
80 // No, we need to establish a copy in cache from passed version
81 return new RecoverySummary(insert(anIdentifiable), false);
82 } else {
83 /*
84 myIdentifiable contains the up-to-date disk image and this
85 must be inserted into the cache rather than anIdentifiable
86 which should only be used when the disk image was missing.
87 */
88 return new RecoverySummary(find(myIdentifiable.getId(),
89 myIdentifiable), true);
90 }
91 }
92
93 /**
94 <p> We achieve insert by adding a new memory-only entry into
95 BackingStore using a specific method like prepareToCache(Entry). We
96 then instruct ArcCache to page-in the Entry which will cause ArcCache to
97 make room and pull the Entry from the BackingStore which, coveniently,
98 has the entry waiting in memory. </p>
99
100 ONLY call this method for adding Entries which should be treated as
101 newly written.
102 */
103 public CacheBlockDescriptor insert(Identifiable anIdentifiable)
104 throws IOException {
105 CacheBlockDescriptor myCBD = find(anIdentifiable.getId(),
106 anIdentifiable);
107
108 theListeners.signal(CacheListenerSet.LOADED, anIdentifiable);
109
110 return myCBD;
111 }
112
113 /**
114 Locate an Identifiable associated with Identifier - loading from
115 disk if necessary.
116
117 @return a CBD with the lock asserted representing the requested entry.
118 Note that the entry may no longer exist but we allow "non-existence" to
119 be cached because that may also be significant to some application.
120 In such cases, this method will return <code>null</code>.
121 */
122 public CacheBlockDescriptor find(Identifier anId) throws IOException {
123 CacheBlockDescriptor myCBD = find(anId, null);
124
125 // If Entry isn't present, release CBD and return null to caller.
126 if (myCBD.isEmpty()) {
127 myCBD.release();
128 return null;
129 } else {
130 return myCBD;
131 }
132 }
133
134 /**
135 @param aPreLoad If the identifiable associated with the identifier is
136 not in the cache, make space in the cache and associate aPreLoad with
137 the identifier.
138
139 @return a CBD with the lock asserted representing the requested entry.
140 Note that the entry may no longer exist but we allow "non-existence" to
141 be cached because that may also be significant to some application.
142 In such cases, getContent() will return null and isEmpty will return
143 true.
144 */
145 private CacheBlockDescriptor find(Identifier anId,
146 Identifiable aPreLoad)
147 throws IOException {
148
149 CacheBlockDescriptor myDesc = null;
150 boolean needsFetch = false;
151
152 synchronized(this) {
153 myDesc = (CacheBlockDescriptor) theBlockIndex.get(anId);
154
155 try {
156 // Is it in cache?
157 if (myDesc != null) {
158 myDesc.acquire();
159
160 /*
161 Consistency check - shouldn't have something in cache
162 already when we're pre-loading for insert
163
164 if (aPreLoad != null)
165 theLogger.log(Level.SEVERE, "Hmmm, we're inserting but we appear to have this in cache already :( " + anId + ", " + aPreLoad + ", " + myDesc.getId(), new RuntimeException());
166 */
167
168 switch(myDesc.getWhere()) {
169 case Lru.T1 :
170 case Lru.T2 : {
171 // System.out.println("Cache hit");
172
173 remove(myDesc);
174 t2.mruInsert(myDesc);
175
176 break;
177 }
178
179 case Lru.B1 :
180 case Lru.B2 : {
181 /* I/O - no dir change */
182 // System.out.println("Cache miss [in dir]");
183
184 if (myDesc.getWhere() == Lru.B1) {
185 theTargetT1 =
186 Math.min(theTargetT1 +
187 Math.max(b2.length() /
188 b1.length(), 1),
189 theCacheSize);
190 } else {
191 theTargetT1 =
192 Math.max(theTargetT1 -
193 Math.max(b1.length() /
194 b2.length(), 1),
195 0);
196 }
197
198 remove(myDesc);
199
200 // Flush an entry from cache
201 replace(); // I/O
202
203 myDesc.setId(anId);
204
205 t2.mruInsert(myDesc);
206
207 needsFetch = true;
208 }
209 }
210 } else {
211 /* I/O - dir updated */
212
213 // System.out.println("Cache miss");
214
215 if ((t1.length() + b1.length()) == theCacheSize) {
216 if (t1.length() < theCacheSize) {
217 myDesc = b1.lruRemove();
218 myDesc.acquire();
219 replace(); // I/O
220 } else {
221 myDesc = t1.lruRemove();
222 myDesc.acquire();
223 destage(myDesc); // I/O
224 }
225 theBlockIndex.remove(myDesc.getId());
226 } else {
227 if ((t1.length() + t2.length() + b1.length() +
228 b2.length()) >= theCacheSize) {
229 if ((t1.length() + t2.length() + b1.length() +
230 b2.length()) == (2 * theCacheSize)) {
231 myDesc = b2.lruRemove();
232 myDesc.acquire();
233 theBlockIndex.remove(myDesc.getId());
234 } else {
235 myDesc =
236 new CacheBlockDescriptor();
237 myDesc.acquire();
238 }
239
240 replace(); // I/O
241 } else {
242 myDesc = new CacheBlockDescriptor();
243 myDesc.acquire();
244 }
245 }
246
247 myDesc.setId(anId);
248
249 t1.mruInsert(myDesc);
250
251 theBlockIndex.put(anId, myDesc);
252
253 needsFetch = true;
254 }
255 } catch (InterruptedException anIE) {
256 theLogger.log(Level.SEVERE, "Couldn't lock CDB", anIE);
257 }
258 }
259
260 if (needsFetch) {
261 myDesc.setContent(fetch(anId, aPreLoad));
262 }
263
264 return myDesc;
265 }
266
267 private void remove(CacheBlockDescriptor aDesc) {
268 switch(aDesc.getWhere()) {
269 case Lru.T1 : {
270 t1.remove(aDesc);
271 break;
272 }
273 case Lru.T2 : {
274 t2.remove(aDesc);
275 break;
276 }
277 case Lru.B1 : {
278 b1.remove(aDesc);
279 break;
280 }
281 case Lru.B2 : {
282 b2.remove(aDesc);
283 break;
284 }
285 }
286 }
287
288 /**
289 Flush out another CDB if necessary. In the original algorithm, we'd also
290 need to rip the discarded CBD's cache page and put it in this CDB. But,
291 our version holds the object directly on the CDB so we don't need to do
292 this. Note we're flushing out a CDB in t1 or t2 which means we're
293 removing an entry from the cache to make room for the new one.
294 The one we're making room for could be a phantom hit or a real miss.
295 */
296 private void replace() throws IOException {
297 CacheBlockDescriptor myDesc;
298
299 try {
300 if (t1.length() >= Math.max(1, theTargetT1)) {
301 myDesc = t1.lruRemove();
302 myDesc.acquire();
303
304 b1.mruInsert(myDesc);
305 } else {
306 myDesc = t2.lruRemove();
307 myDesc.acquire();
308
309 b2.mruInsert(myDesc);
310 }
311
312 destage(myDesc);
313
314 myDesc.setContent(null);
315
316 myDesc.release();
317
318 } catch (InterruptedException anIE) {
319 theLogger.log(Level.SEVERE, "Failed to lock CBD", anIE);
320 }
321 }
322
323 private void destage(CacheBlockDescriptor aCBD) throws IOException {
324 // System.out.println("Flush: " + aCBD.getId());
325
326 theStore.save(aCBD.getContent());
327 }
328
329 public void dump() {
330 dump(t1);
331 dump(t2);
332 dump(b1);
333 dump(b2);
334 }
335
336 private void dump(Lru anLru) {
337 synchronized(anLru) {
338 anLru.dump();
339 }
340 }
341
342 public synchronized void sync() throws IOException {
343
344 long myStart = 0;
345
346 if (theLogger.isLoggable(Level.FINE)) {
347 theLogger.log(Level.FINE, "Syncing: " + theStore.getName());
348
349 myStart = System.currentTimeMillis();
350 }
351
352 t1.sync(theStore);
353 t2.sync(theStore);
354
355 if (theLogger.isLoggable(Level.FINE)) {
356 long myEnd = System.currentTimeMillis();
357
358 theLogger.log(Level.FINE,
359 "Time to scan lists: " + (myEnd - myStart));
360 }
361 }
362
363 private Identifiable fetch(Identifier anId, Identifiable aPreLoad)
364 throws IOException {
365
366 // System.out.println("Fetch: " + anId + ", " + aPreLoad);
367
368 Identifiable myIdent;
369
370 if (aPreLoad != null)
371 myIdent = aPreLoad;
372 else
373 myIdent = theStore.load(anId);
374
375 return myIdent;
376 }
377
378 public void forceSync(CacheBlockDescriptor aCBD) throws IOException {
379 // System.err.println("Expunge");
380
381 destage(aCBD);
382
383 // System.err.println("Expunge done");
384 }
385 }