edu.umass.cs.utils

Class DiskMap<K,V>

java.lang.Object

edu.umass.cs.utils.DiskMap<K,V>

Type Parameters:

K -

V - DiskMap implements the ConcurrentMap interface and allows applications to maintain very large maps limited only by the available disk space by automatically stowing away infrequently used map entries to disk. DiskMap is not a database and does not try to guarantee durability under crashes. However, if the map is closed gracefully, it will ensure durability by committing entries to disk before closing. DiskMap itself does not implement any disk I/O but relies on the application that must implement commit(Map) and restore(Object) methods that respectively write to and read from the disk. DiskMap is nearly indistinguishable in performance from ConcurrentHashMap when all map entries fit in memory. If not, its performance depends on how frequently entries are reused. If entries are rarely reused, e.g., a sweep over a very large number of map entries, then every access will on average force a disk read (to unpause the entry being accessed) and a write (to pause long idle entries). Normally, only entries that have been idle for at least idleThreshold paused to disk, so the caller must use setIdleThreshold(long) so as to ensure that either no more than sizeThreshold entries are accessed in that interval or there is sufficient memory to hold all entries accessed in the last idleThreshold time. If not, a random fraction of entries, including possibly recently used entries, will be paused to disk in order to make room in memory. DiskMap can use MultiArrayMap as its underlying in-memory map if that is supplied in the constructor. Although not necessary, the use of MultiArrayMap makes the map more compact because of its cuckoo hashing design, but it requires values to implement the Keyable interface. If values additionally also implement Pausable, DiskMap incurs just ~6B overhead per value as it does not have to maintain its own stats for last active times for map entries. Note: There is no way to ensure that the value pointed to in the map is not modified after it has been paused to disk. It does not help to verify that the value pointed to is the same as the serialized value paused to disk as the value pointed to in the map could be modified by a caller even after its serialized form has been paused to disk. As a result, we can not support the "expectation" that modifications to the value object by the caller will be reflected in the map. So, the caller is forced to reckon with the possibility that any modifications to the value object may be lost unless the caller explicitly invokes a put subsequently.

All Implemented Interfaces:

Diskable<K,V>, java.util.concurrent.ConcurrentMap<K,V>, java.util.Map<K,V>

public abstract class DiskMap<K,V>
extends java.lang.Object
implements java.util.concurrent.ConcurrentMap<K,V>, Diskable<K,V>

Author:

arun

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
class	DiskMap.LastActive

Nested classes/interfaces inherited from interface java.util.Map

java.util.Map.Entry<K,V>

Field Summary

Fields

Modifier and Type	Field and Description
static int	DEFAULT_CAPACITY

Constructor Summary

Constructors

Constructor and Description
DiskMap(java.util.concurrent.ConcurrentMap<K,V> map) The supplied map will be used as the underlying in-memory map.
DiskMap(long inMemoryCapacity)

Method Summary

Modifier and Type	Method and Description
void	clear()
void	close()
void	close(boolean commitAll) Will stop the GC thread but will have no other effect.
void	commit() Commits all in-memory entries in the map.
protected java.util.Set<K>	commit(K key)
abstract java.util.Set<K>	commit(java.util.Map<K,V> toCommit) This method should return only after successfully persisting the key,value pair, otherwise it should throw an exception.
boolean	containsKey(java.lang.Object key)
boolean	containsValue(java.lang.Object value)
void	enablePriorityQueue()
java.util.Set<java.util.Map.Entry<K,V>>	entrySet() This method only returns the in-memory entry set.
V	get(java.lang.Object key)
protected void	hintRestore(K key, V value)
boolean	isEmpty()
java.util.Set<K>	keySet() This method only returns the in-memory key set.
V	put(K key, V value)
void	putAll(java.util.Map<? extends K,? extends V> m)
V	putIfAbsent(K key, V value)
V	remove(java.lang.Object key)
boolean	remove(java.lang.Object key, java.lang.Object value)
V	replace(K key, V value)
boolean	replace(K key, V oldValue, V newValue)
abstract V	restore(K key)
void	setIdleThreshold(long idleTime) Minimum idle time in order to be pausable.
void	setPauseThreadPeriod(long period) Period after which a pausing attempt is made by the GC thread.
int	size()
java.lang.String	toString()
java.util.Collection<V>	values() This method only returns the in-memory value set.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.util.concurrent.ConcurrentMap

compute, computeIfAbsent, computeIfPresent, forEach, getOrDefault, merge, replaceAll

Methods inherited from interface java.util.Map

equals, hashCode

Field Detail

DEFAULT_CAPACITY

public static final int DEFAULT_CAPACITY

See Also:

Constant Field Values

Constructor Detail

DiskMap

public DiskMap(long inMemoryCapacity)

Parameters:

inMemoryCapacity - Capacity for in-memory map. If the in-memory map size reaches this value, GC forcibly kicks in.

DiskMap

public DiskMap(java.util.concurrent.ConcurrentMap<K,V> map)

The supplied map will be used as the underlying in-memory map. From this point onwards, making direct modifications to this underlying map is unsafe.

Parameters:

map -

Method Detail

setIdleThreshold

public void setIdleThreshold(long idleTime)

Minimum idle time in order to be pausable.

Parameters:

idleTime -

enablePriorityQueue

public void enablePriorityQueue()

setPauseThreadPeriod

public void setPauseThreadPeriod(long period)

Period after which a pausing attempt is made by the GC thread.

Parameters:

period -

commit

public abstract java.util.Set<K> commit(java.util.Map<K,V> toCommit)
                                 throws java.io.IOException

This method should return only after successfully persisting the key,value pair, otherwise it should throw an exception.

Specified by:

commit in interface Diskable<K,V>

Returns:

Set of successfully committed keys.

Throws:

java.io.IOException

restore

public abstract V restore(K key)
                   throws java.io.IOException

Specified by:

restore in interface Diskable<K,V>

Parameters:

key -

Returns:

Value for key restored from persistent store.

Throws:

java.io.IOException

size

public int size()

Specified by:

size in interface java.util.Map<K,V>

isEmpty

public boolean isEmpty()

Specified by:

isEmpty in interface java.util.Map<K,V>

containsKey

public boolean containsKey(java.lang.Object key)

Specified by:

containsKey in interface java.util.Map<K,V>

containsValue

public boolean containsValue(java.lang.Object value)

Specified by:

containsValue in interface java.util.Map<K,V>

get

public V get(java.lang.Object key)

Specified by:

get in interface java.util.Map<K,V>

put

public V put(K key,
             V value)

Specified by:

put in interface java.util.Map<K,V>

remove

public V remove(java.lang.Object key)

Specified by:

remove in interface java.util.Map<K,V>

putAll

public void putAll(java.util.Map<? extends K,? extends V> m)

Specified by:

putAll in interface java.util.Map<K,V>

clear

public void clear()

Specified by:

clear in interface java.util.Map<K,V>

keySet

public java.util.Set<K> keySet()

This method only returns the in-memory key set. There is currently no method to get the on-disk keys.

Specified by:

keySet in interface java.util.Map<K,V>

values

public java.util.Collection<V> values()

This method only returns the in-memory value set. There is currently no method to get the on-disk values.

Specified by:

values in interface java.util.Map<K,V>

entrySet

public java.util.Set<java.util.Map.Entry<K,V>> entrySet()

This method only returns the in-memory entry set. There is currently no method to get the on-disk entries.

Specified by:

entrySet in interface java.util.Map<K,V>

hintRestore

protected void hintRestore(K key,
                           V value)

putIfAbsent

public V putIfAbsent(K key,
                     V value)

Specified by:

putIfAbsent in interface java.util.concurrent.ConcurrentMap<K,V>

Specified by:

putIfAbsent in interface java.util.Map<K,V>

remove

public boolean remove(java.lang.Object key,
                      java.lang.Object value)

Specified by:

remove in interface java.util.concurrent.ConcurrentMap<K,V>

Specified by:

remove in interface java.util.Map<K,V>

replace

public boolean replace(K key,
                       V oldValue,
                       V newValue)

Specified by:

replace in interface java.util.concurrent.ConcurrentMap<K,V>

Specified by:

replace in interface java.util.Map<K,V>

replace

public V replace(K key,
                 V value)

Specified by:

replace in interface java.util.concurrent.ConcurrentMap<K,V>

Specified by:

replace in interface java.util.Map<K,V>

commit

protected java.util.Set<K> commit(K key)
                           throws java.io.IOException

Throws:

java.io.IOException

commit

public void commit()

Commits all in-memory entries in the map.

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

close

public void close(boolean commitAll)

Will stop the GC thread but will have no other effect. The map can continue to be used with the same semantics.

Parameters:

commitAll -

close

public void close()