1 /***
2 * Copyright 2003-2009 Terracotta, Inc.
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 package net.sf.ehcache.store;
18
19 import net.sf.ehcache.CacheEntry;
20 import net.sf.ehcache.CacheException;
21 import net.sf.ehcache.Ehcache;
22 import net.sf.ehcache.Element;
23 import net.sf.ehcache.Status;
24 import net.sf.ehcache.writer.CacheWriterManager;
25 import org.slf4j.Logger;
26 import org.slf4j.LoggerFactory;
27
28 import java.util.Iterator;
29 import java.util.Map;
30
31
32 /***
33 * An implementation of a LruMemoryStore.
34 * <p/>
35 * This uses {@link java.util.LinkedHashMap} as its backing map. It uses the {@link java.util.LinkedHashMap} LRU
36 * feature. LRU for this implementation means least recently accessed.
37 *
38 * @author <a href="mailto:gluck@thoughtworks.com">Greg Luck</a>
39 * @version $Id$
40 */
41 public class LruMemoryStore implements Store {
42
43 private static final Logger LOG = LoggerFactory.getLogger(LruMemoryStore.class.getName());
44
45 /***
46 * The cache this store is associated with.
47 */
48 protected Ehcache cache;
49
50 /***
51 * Map where items are stored by key.
52 */
53 protected Map map;
54
55 /***
56 * The DiskStore associated with this MemoryStore.
57 */
58 protected final Store diskStore;
59
60 /***
61 * status.
62 */
63 protected Status status;
64
65 /***
66 * The maximum size of the store (0 == no limit)
67 */
68 protected int maximumSize;
69
70
71 /***
72 * Constructor for the LruMemoryStore object
73 * The backing {@link java.util.LinkedHashMap} is created with LRU by access order.
74 */
75 public LruMemoryStore(Ehcache cache, Store diskStore) {
76 status = Status.STATUS_UNINITIALISED;
77 this.maximumSize = cache.getCacheConfiguration().getMaxElementsInMemory();
78 this.cache = cache;
79 this.diskStore = diskStore;
80 map = new SpoolingLinkedHashMap();
81 status = Status.STATUS_ALIVE;
82 }
83
84
85 /***
86 * Puts an item in the cache. Note that this automatically results in
87 * {@link net.sf.ehcache.store.LruMemoryStore.SpoolingLinkedHashMap#removeEldestEntry} being called.
88 *
89 * @param element the element to add
90 */
91 public final boolean put(Element element) throws CacheException {
92 return putInternal(element, null);
93 }
94
95 /***
96 * {@inheritDoc}
97 */
98 public final boolean putWithWriter(Element element, CacheWriterManager writerManager) throws CacheException {
99 return putInternal(element, writerManager);
100 }
101
102 private synchronized boolean putInternal(Element element, CacheWriterManager writerManager) throws CacheException {
103 boolean newPut = true;
104 if (element != null) {
105 newPut = map.put(element.getObjectKey(), element) == null;
106 if (writerManager != null) {
107 writerManager.put(element);
108 }
109 doPut(element);
110 }
111 return newPut;
112 }
113
114 /***
115 * Allow specialised actions over adding the element to the map.
116 *
117 * @param element
118 */
119 protected void doPut(Element element) throws CacheException {
120
121 }
122
123 /***
124 * Gets an item from the cache.
125 * <p/>
126 * The last access time in {@link net.sf.ehcache.Element} is updated.
127 *
128 * @param key the cache key
129 * @return the element, or null if there was no match for the key
130 */
131 public final synchronized Element get(Object key) {
132 return (Element) map.get(key);
133 }
134
135 /***
136 * Gets an item from the cache, without updating statistics.
137 *
138 * @param key the cache key
139 * @return the element, or null if there was no match for the key
140 */
141 public final synchronized Element getQuiet(Object key) {
142 return get(key);
143 }
144
145 /***
146 * Removes an Element from the store.
147 *
148 * @param key the key of the Element, usually a String
149 * @return the Element if one was found, else null
150 */
151 public final Element remove(Object key) {
152 return removeInternal(key, null);
153 }
154
155 /***
156 * {@inheritDoc}
157 */
158 public final Element removeWithWriter(Object key, CacheWriterManager writerManager) throws CacheException {
159 return removeInternal(key, writerManager);
160 }
161
162 private synchronized Element removeInternal(Object key, CacheWriterManager writerManager) throws CacheException {
163
164 Element element = (Element) map.remove(key);
165 if (writerManager != null) {
166 writerManager.remove(new CacheEntry(key, element));
167 }
168 if (element != null) {
169 return element;
170 } else {
171 return null;
172 }
173 }
174
175 /***
176 * Remove all of the elements from the store.
177 */
178 public final synchronized void removeAll() throws CacheException {
179 clear();
180 }
181
182 /***
183 * Clears any data structures and places it back to its state when it was first created.
184 */
185 protected final void clear() {
186 map.clear();
187 }
188
189 /***
190 * Prepares for shutdown.
191 */
192 public final synchronized void dispose() {
193 if (status.equals(Status.STATUS_SHUTDOWN)) {
194 return;
195 }
196 status = Status.STATUS_SHUTDOWN;
197 flush();
198
199
200 cache = null;
201 }
202
203
204 /***
205 * Flush to disk only if the cache is diskPersistent.
206 */
207 public final void flush() {
208 if (cache.getCacheConfiguration().isDiskPersistent()) {
209 if (LOG.isDebugEnabled()) {
210 LOG.debug(cache.getName() + " is persistent. Spooling " + map.size() + " elements to the disk store.");
211 }
212 spoolAllToDisk();
213 }
214
215
216 if (cache.getCacheConfiguration().isClearOnFlush()) {
217 clear();
218 }
219 }
220
221
222 /***
223 * Spools all elements to disk, in preparation for shutdown.
224 * <p/>
225 * This revised implementation is a little slower but avoids using increased memory during the method.
226 */
227 protected final void spoolAllToDisk() {
228 boolean clearOnFlush = cache.getCacheConfiguration().isClearOnFlush();
229 Object[] keys = getKeyArray();
230 for (Object key : keys) {
231 Element element = (Element) map.get(key);
232 if (element != null) {
233 if (!element.isSerializable()) {
234 if (LOG.isDebugEnabled()) {
235 LOG.debug("Object with key " + element.getObjectKey()
236 + " is not Serializable and is not being overflowed to disk.");
237 }
238 } else {
239 spoolToDisk(element);
240
241
242 if (clearOnFlush) {
243 remove(key);
244 }
245 }
246 }
247 }
248 }
249
250 /***
251 * Puts the element in the DiskStore.
252 * Should only be called if isOverflowToDisk is true
253 * <p/>
254 * Relies on being called from a synchronized method
255 *
256 * @param element The Element
257 */
258 protected void spoolToDisk(Element element) {
259 diskStore.put(element);
260 if (LOG.isDebugEnabled()) {
261 LOG.debug(cache.getName() + "Cache: spool to disk done for: " + element.getObjectKey());
262 }
263 }
264
265 /***
266 * Gets the status of the MemoryStore.
267 */
268 public final Status getStatus() {
269 return status;
270 }
271
272 /***
273 * Gets an Array of the keys for all elements in the memory cache.
274 * <p/>
275 * Does not check for expired entries
276 *
277 * @return An Object[]
278 */
279 public final synchronized Object[] getKeyArray() {
280 return map.keySet().toArray();
281 }
282
283 /***
284 * Returns the current cache size.
285 *
286 * @return The size value
287 */
288 public final int getSize() {
289 return map.size();
290 }
291
292 /***
293 * Returns nothing since a disk store isn't clustered
294 *
295 * @return returns 0
296 */
297 public final int getTerracottaClusteredSize() {
298 return 0;
299 }
300
301
302 /***
303 * An unsynchronized check to see if a key is in the Store. No check is made to see if the Element is expired.
304 *
305 * @param key The Element key
306 * @return true if found. If this method return false, it means that an Element with the given key is definitely not in the MemoryStore.
307 * If it returns true, there is an Element there. An attempt to get it may return null if the Element has expired.
308 */
309 public final boolean containsKey(Object key) {
310 return map.containsKey(key);
311 }
312
313
314 /***
315 * Measures the size of the memory store by measuring the serialized size of all elements.
316 * If the objects are not Serializable they count as 0.
317 * <p/>
318 * Warning: This method can be very expensive to run. Allow approximately 1 second
319 * per 1MB of entries. Running this method could create liveness problems
320 * because the object lock is held for a long period
321 *
322 * @return the size, in bytes
323 */
324 public final synchronized long getSizeInBytes() throws CacheException {
325 long sizeInBytes = 0;
326 for (Iterator iterator = map.values().iterator(); iterator.hasNext();) {
327 Element element = (Element) iterator.next();
328 if (element != null) {
329 sizeInBytes += element.getSerializedSize();
330 }
331 }
332 return sizeInBytes;
333 }
334
335
336 /***
337 * Evict the <code>Element</code>.
338 * <p/>
339 * Evict means that the <code>Element</code> is:
340 * <ul>
341 * <li>if, the store is diskPersistent, the <code>Element</code> is spooled to the DiskStore
342 * <li>if not, the <code>Element</code> is removed.
343 * </ul>
344 *
345 * @param element the <code>Element</code> to be evicted.
346 */
347 protected final void evict(Element element) throws CacheException {
348 boolean spooled = false;
349 if (cache.getCacheConfiguration().isOverflowToDisk()) {
350 if (!element.isSerializable()) {
351 if (LOG.isDebugEnabled()) {
352 LOG.debug(new StringBuilder("Object with key ").append(element.getObjectKey())
353 .append(" is not Serializable and cannot be overflowed to disk").toString());
354 }
355 } else {
356 spoolToDisk(element);
357 spooled = true;
358 }
359 }
360
361 if (!spooled) {
362 cache.getCacheEventNotificationService().notifyElementEvicted(element, false);
363 }
364 }
365
366 /***
367 * Before eviction elements are checked.
368 *
369 * @param element
370 */
371 protected final void notifyExpiry(Element element) {
372 cache.getCacheEventNotificationService().notifyElementExpiry(element, false);
373 }
374
375
376 /***
377 * An algorithm to tell if the MemoryStore is at or beyond its carrying capacity.
378 */
379 protected final boolean isFull() {
380 return maximumSize > 0 && map.size() > maximumSize;
381 }
382
383 /***
384 * Expire all elsments.
385 * <p/>
386 * This is a default implementation which does nothing. Expiry on demand is only
387 * implemented for disk stores.
388 */
389 public void expireElements() {
390
391 }
392
393 /***
394 * Memory stores are never backed up and always return false
395 */
396 public boolean bufferFull() {
397 return false;
398 }
399
400
401 /***
402 * Package local access to the map for testing
403 */
404 Map getBackingMap() {
405 return map;
406 }
407
408 /***
409 * An extension of LinkedHashMap which overrides {@link #removeEldestEntry}
410 * to persist cache entries to the auxiliary cache before they are removed.
411 * <p/>
412 * This implementation also provides LRU by access order.
413 */
414 public final class SpoolingLinkedHashMap extends java.util.LinkedHashMap {
415 private static final int INITIAL_CAPACITY = 100;
416 private static final float GROWTH_FACTOR = .75F;
417
418 /***
419 * Default constructor.
420 * Will create an initial capacity of 100, a loading of .75 and
421 * LRU by access order.
422 */
423 public SpoolingLinkedHashMap() {
424 super(INITIAL_CAPACITY, GROWTH_FACTOR, true);
425 }
426
427 /***
428 * Returns <tt>true</tt> if this map should remove its eldest entry.
429 * This method is invoked by <tt>put</tt> and <tt>putAll</tt> after
430 * inserting a new entry into the map. It provides the implementer
431 * with the opportunity to remove the eldest entry each time a new one
432 * is added. This is useful if the map represents a cache: it allows
433 * the map to reduce memory consumption by deleting stale entries.
434 * <p/>
435 * Will return true if:
436 * <ol>
437 * <li> the element has expired
438 * <li> the cache size is greater than the in-memory actual.
439 * In this case we spool to disk before returning.
440 * </ol>
441 *
442 * @param eldest The least recently inserted entry in the map, or if
443 * this is an access-ordered map, the least recently accessed
444 * entry. This is the entry that will be removed it this
445 * method returns <tt>true</tt>. If the map was empty prior
446 * to the <tt>put</tt> or <tt>putAll</tt> invocation resulting
447 * in this invocation, this will be the entry that was just
448 * inserted; in other words, if the map contains a single
449 * entry, the eldest entry is also the newest.
450 * @return true if the eldest entry should be removed
451 * from the map; <tt>false</t> if it should be retained.
452 */
453 @Override
454 protected final boolean removeEldestEntry(Map.Entry eldest) {
455 Element element = (Element) eldest.getValue();
456 return element != null && removeLeastRecentlyUsedElement(element);
457 }
458
459 /***
460 * Relies on being called from a synchronized method
461 *
462 * @param element
463 * @return true if the LRU element should be removed
464 */
465 private boolean removeLeastRecentlyUsedElement(Element element) throws CacheException {
466
467 if (element.isExpired()) {
468 notifyExpiry(element);
469 return true;
470 }
471
472 if (isFull()) {
473 evict(element);
474 return true;
475 } else {
476 return false;
477 }
478
479 }
480 }
481
482
483 /***
484 * @return the current eviction policy. This may not be the configured policy, if it has been
485 * dynamically set.
486 * @see #setEvictionPolicy(Policy)
487 */
488 public Policy getEvictionPolicy() {
489 return new LruPolicy();
490 }
491
492 /***
493 * Sets the eviction policy strategy. The Store will use a policy at startup. The store may allow changing
494 * the eviction policy strategy dynamically. Otherwise implementations will throw an exception if this method
495 * is called.
496 *
497 * @param policy the new policy
498 */
499 public void setEvictionPolicy(Policy policy) {
500 throw new UnsupportedOperationException("This store is LRU only. It does not support changing the eviction" +
501 " strategy.");
502 }
503
504 /***
505 * {@inheritDoc}
506 */
507 public Object getInternalContext() {
508 return null;
509 }
510
511 /***
512 * {@inheritDoc}
513 */
514 public void waitUntilClusterCoherent() {
515 throw new UnsupportedOperationException();
516 }
517
518 /***
519 * {@inheritDoc}
520 */
521 public void setNodeCoherent(boolean coherent) {
522 throw new UnsupportedOperationException();
523 }
524
525 /***
526 * {@inheritDoc}
527 */
528 public boolean isNodeCoherent() {
529 return false;
530 }
531
532 /***
533 * {@inheritDoc}
534 */
535 public boolean isClusterCoherent() {
536 return false;
537 }
538
539 /***
540 * {@inheritDoc}
541 */
542 public boolean isCacheCoherent() {
543 return false;
544 }
545 }
546