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

java.lang.Object
  extended by org.apache.hadoop.hbase.regionserver.LruHashMap<K,V>
All Implemented Interfaces:
Map<K,V>, HeapSize

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
protected static class LruHashMap.Entry<K extends HeapSize,V extends HeapSize>
          Entry to store key/value mappings.
 
Constructor Summary
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
 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>


Copyright © 2011 The Apache Software Foundation. All Rights Reserved.