org.apache.hadoop.hbase.regionserver

Class LruHashMap<K extends HeapSize,V extends HeapSize>

java.lang.Object

org.apache.hadoop.hbase.regionserver.LruHashMap<K,V>

All Implemented Interfaces:

Map<K,V>, HeapSize

@InterfaceAudience.Private
public class LruHashMap<K extends HeapSize,V extends HeapSize>
extends Object
implements HeapSize, Map<K,V>

The LruHashMap is a memory-aware HashMap with a configurable maximum memory footprint.

It maintains an ordered list of all entries in the map ordered by access time. When space needs to be freed becase the maximum has been reached, or the application has asked to free memory, entries will be evicted according to an LRU (least-recently-used) algorithm. That is, those entries which have not been accessed the longest will be evicted first.

Both the Key and Value Objects used for this class must extend HeapSize in order to track heap usage.

This class contains internal synchronization and is thread-safe.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
protected static class	LruHashMap.Entry<K extends HeapSize,V extends HeapSize> Entry to store key/value mappings.

Constructor Summary

Constructors

Constructor and Description
LruHashMap() Constructs a new, empty map with the default initial capacity, load factor and maximum memory usage.
LruHashMap(int initialCapacity) Constructs a new, empty map with the specified initial capacity and with the default load factor and maximum memory usage.
LruHashMap(int initialCapacity, float loadFactor) Constructs a new, empty map with the specified initial capacity and load factor, and default maximum memory usage.
LruHashMap(int initialCapacity, float loadFactor, long maxMemUsage) Constructs a new, empty map with the specified initial capacity, load factor, and maximum memory usage.
LruHashMap(long maxMemUsage) Constructs a new, empty map with the specified maximum memory usage and with default initial capacity and load factor.

Method Summary

Methods

Modifier and Type	Method and Description
void	clear() Clears all entries from the map.
boolean	containsKey(Object key) Checks whether there is a value in the map for the specified key.
boolean	containsValue(Object value) Checks whether this is a mapping which contains the specified value.
List<LruHashMap.Entry<K,V>>	entryLruList() Debugging function that returns a List sorted by access time.
Set<Map.Entry<K,V>>	entrySet() Intentionally unimplemented.
Set<LruHashMap.Entry<K,V>>	entryTableSet() Debugging function that returns a Set of all entries in the hash table.
boolean	equals(Object o) Intentionally unimplemented.
long	freeMemory(long requestedAmount) Free the requested amount of memory from the LRU map.
V	get(Object key) Retrieves the value associated with the specified key.
LruHashMap.Entry	getHeadPtr() Get the head of the linked list (least recently used).
long	getHitCount() Get the number of hits to the map.
double	getHitRatio() Get the hit ratio.
long	getMemFree() Get the currently available memory for this LRU in bytes.
long	getMemMax() Get the maximum memory allowed for this LRU in bytes.
long	getMemUsed() Get the currently used memory for this LRU in bytes.
long	getMissCount() Get the number of misses to the map.
LruHashMap.Entry	getTailPtr() Get the tail of the linked list (most recently used).
int	hashCode() Intentionally unimplemented.
long	heapSize() The total memory usage of this map
boolean	isEmpty() Checks whether the map is currently empty.
Set<K>	keySet() Intentionally unimplemented.
V	put(K key, V value) Insert a key-value mapping into the map.
void	putAll(Map<? extends K,? extends V> m) Intentionally unimplemented.
V	remove(Object key) Deletes the mapping for the specified key if it exists.
int	size() Gets the size (number of entries) of the map.
Collection<V>	values() Intentionally unimplemented.

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

LruHashMap

public LruHashMap(int initialCapacity,
          float loadFactor,
          long maxMemUsage)

Constructs a new, empty map with the specified initial capacity, load factor, and maximum memory usage.

Parameters:

initialCapacity - the initial capacity

loadFactor - the load factor

maxMemUsage - the maximum total memory usage

Throws:

IllegalArgumentException - if the initial capacity is less than one

IllegalArgumentException - if the initial capacity is greater than the maximum capacity

IllegalArgumentException - if the load factor is <= 0

IllegalArgumentException - if the max memory usage is too small to support the base overhead

LruHashMap

public LruHashMap(int initialCapacity,
          float loadFactor)

Constructs a new, empty map with the specified initial capacity and load factor, and default maximum memory usage.

Parameters:

initialCapacity - the initial capacity

loadFactor - the load factor

Throws:

IllegalArgumentException - if the initial capacity is less than one

IllegalArgumentException - if the initial capacity is greater than the maximum capacity

IllegalArgumentException - if the load factor is <= 0

LruHashMap

public LruHashMap(int initialCapacity)

Constructs a new, empty map with the specified initial capacity and with the default load factor and maximum memory usage.

Parameters:

initialCapacity - the initial capacity

Throws:

IllegalArgumentException - if the initial capacity is less than one

IllegalArgumentException - if the initial capacity is greater than the maximum capacity

LruHashMap

public LruHashMap(long maxMemUsage)

Constructs a new, empty map with the specified maximum memory usage and with default initial capacity and load factor.

Parameters:

maxMemUsage - the maximum total memory usage

Throws:

IllegalArgumentException - if the max memory usage is too small to support the base overhead

LruHashMap

public LruHashMap()

Constructs a new, empty map with the default initial capacity, load factor and maximum memory usage.

Method Detail

getMemFree

public long getMemFree()

Get the currently available memory for this LRU in bytes. This is (maxAllowed - currentlyUsed).

Returns:

currently available bytes

getMemMax

public long getMemMax()

Get the maximum memory allowed for this LRU in bytes.

Returns:

maximum allowed bytes

getMemUsed

public long getMemUsed()

Get the currently used memory for this LRU in bytes.

Returns:

currently used memory in bytes

getHitCount

public long getHitCount()

Get the number of hits to the map. This is the number of times a call to get() returns a matched key.

Returns:

number of hits

getMissCount

public long getMissCount()

Get the number of misses to the map. This is the number of times a call to get() returns null.

Returns:

number of misses

getHitRatio

public double getHitRatio()

Get the hit ratio. This is the number of hits divided by the total number of requests.

Returns:

hit ratio (double between 0 and 1)

freeMemory

public long freeMemory(long requestedAmount)
                throws Exception

Free the requested amount of memory from the LRU map. This will do LRU eviction from the map until at least as much memory as requested is freed. This does not affect the maximum memory usage parameter.

Parameters:

requestedAmount - memory to free from LRU in bytes

Returns:

actual amount of memory freed in bytes

Throws:

Exception

heapSize

public long heapSize()

The total memory usage of this map

Specified by:

heapSize in interface HeapSize

Returns:

memory usage of map in bytes

get

public V get(Object key)

Retrieves the value associated with the specified key. If an entry is found, it is updated in the LRU as the most recently used (last to be evicted) entry in the map.

Specified by:

get in interface Map<K extends HeapSize,V extends HeapSize>

Parameters:

key - the key

Returns:

the associated value, or null if none found

Throws:

NullPointerException - if key is null

put

public V put(K key,
    V value)

Insert a key-value mapping into the map. Entry will be inserted as the most recently used. Both the key and value are required to be Objects and must implement the HeapSize interface.

Specified by:

put in interface Map<K extends HeapSize,V extends HeapSize>

Parameters:

key - the key

value - the value

Returns:

the value that was previously mapped to this key, null if none

Throws:

UnsupportedOperationException - if either objects do not implement HeapSize

NullPointerException - if the key or value is null

remove

public V remove(Object key)

Deletes the mapping for the specified key if it exists.

Specified by:

remove in interface Map<K extends HeapSize,V extends HeapSize>

Parameters:

key - the key of the entry to be removed from the map

Returns:

the value associated with the specified key, or null if no mapping exists.

size

public int size()

Gets the size (number of entries) of the map.

Specified by:

size in interface Map<K extends HeapSize,V extends HeapSize>

Returns:

size of the map

isEmpty

public boolean isEmpty()

Checks whether the map is currently empty.

Specified by:

isEmpty in interface Map<K extends HeapSize,V extends HeapSize>

Returns:

true if size of map is zero

clear

public void clear()

Clears all entries from the map. This frees all entries, tracking memory usage along the way. All references to entries are removed so they can be GC'd.

Specified by:

clear in interface Map<K extends HeapSize,V extends HeapSize>

containsKey

public boolean containsKey(Object key)

Checks whether there is a value in the map for the specified key. Does not affect the LRU.

Specified by:

containsKey in interface Map<K extends HeapSize,V extends HeapSize>

Parameters:

key - the key to check

Returns:

true if the map contains a value for this key, false if not

Throws:

NullPointerException - if the key is null

containsValue

public boolean containsValue(Object value)

Checks whether this is a mapping which contains the specified value. Does not affect the LRU. This is an inefficient operation.

Specified by:

containsValue in interface Map<K extends HeapSize,V extends HeapSize>

Parameters:

value - the value to check

Returns:

true if the map contains an entry for this value, false if not

Throws:

NullPointerException - if the value is null

entryLruList

public List<LruHashMap.Entry<K,V>> entryLruList()

Debugging function that returns a List sorted by access time. The order is oldest to newest (first in list is next to be evicted).

Returns:

Sorted list of entries

entryTableSet

public Set<LruHashMap.Entry<K,V>> entryTableSet()

Debugging function that returns a Set of all entries in the hash table.

Returns:

Set of entries in hash

getHeadPtr

public LruHashMap.Entry getHeadPtr()

Get the head of the linked list (least recently used).

Returns:

head of linked list

getTailPtr

public LruHashMap.Entry getTailPtr()

Get the tail of the linked list (most recently used).

Returns:

tail of linked list

entrySet

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

Intentionally unimplemented.

Specified by:

entrySet in interface Map<K extends HeapSize,V extends HeapSize>

equals

public boolean equals(Object o)

Intentionally unimplemented.

Specified by:

equals in interface Map<K extends HeapSize,V extends HeapSize>

Overrides:

equals in class Object

hashCode

public int hashCode()

Intentionally unimplemented.

Specified by:

hashCode in interface Map<K extends HeapSize,V extends HeapSize>

Overrides:

hashCode in class Object

keySet

public Set<K> keySet()

Intentionally unimplemented.

Specified by:

keySet in interface Map<K extends HeapSize,V extends HeapSize>

putAll

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

Intentionally unimplemented.

Specified by:

putAll in interface Map<K extends HeapSize,V extends HeapSize>

values

public Collection<V> values()

Intentionally unimplemented.

Specified by:

values in interface Map<K extends HeapSize,V extends HeapSize>