Mercurial > hg > blitz_stable
comparison src/org/dancres/blitz/arc/ArcCache.java @ 0:3dc0c5604566
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 } |