akka.remote.artery.compress

Class TopHeavyHitters<T>

java.lang.Object

akka.remote.artery.compress.TopHeavyHitters<T>

public final class TopHeavyHitters<T>
extends java.lang.Object

INTERNAL API

Mutable, open-addressing with linear-probing (though naive one which in theory could get pathological) heavily optimised "top N heavy hitters" data-structure.

Keeps a number of specific heavy hitters around in memory.

See also Section 5.2 of http://dimacs.rutgers.edu/~graham/pubs/papers/cm-full.pdf for a discussion about the assumptions made and guarantees about the Heavy Hitters made in this model. We assume the Cash Register model in which there are only additions, which simplifies HH detecion significantly.

This class is a hybrid data structure containing a hashmap and a heap pointing to slots in the hashmap. The capacity of the hashmap is twice that of the heap to reduce clumping of entries on collisions.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	TopHeavyHitters.HashCodeVal Value class to avoid mixing up count and hashCode in APIs.
static class	TopHeavyHitters.HashCodeVal$

Constructor Summary

Constructors

Constructor and Description
TopHeavyHitters(int max, scala.reflect.ClassTag<T> classTag)

Method Summary

Modifier and Type	Method and Description
int	capacity()
scala.collection.Iterator<T>	iterator() Iterates over the current heavy hitters, order is not of significance.
long	lowestHitterWeight() Weight of lowest heavy hitter, if a new inserted item has a weight greater than this, it is a heavy hitter.
int	mask()
int	max()
java.lang.String	toDebugString()
java.lang.String	toString()
boolean	update(T item, long count) Attempt adding item to heavy hitters set, if it does not fit in the top yet, it will be dropped and the method will return false.

Methods inherited from class java.lang.Object

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

Constructor Detail

TopHeavyHitters

public TopHeavyHitters(int max,
                       scala.reflect.ClassTag<T> classTag)

Method Detail

max

public int max()

capacity

public int capacity()

mask

public int mask()

iterator

public scala.collection.Iterator<T> iterator()

Iterates over the current heavy hitters, order is not of significance. Not thread safe, accesses internal heap directly (to avoid copying of data). Access must be synchronised externally.

Returns:

(undocumented)

toDebugString

public java.lang.String toDebugString()

update

public boolean update(T item,
                      long count)

Attempt adding item to heavy hitters set, if it does not fit in the top yet, it will be dropped and the method will return false.

WARNING: It is only allowed to *increase* the weight of existing elements, decreasing is disallowed.

Parameters:

item - (undocumented)

count - (undocumented)

Returns:

true if the added item has become a heavy hitter.

lowestHitterWeight

public long lowestHitterWeight()

Weight of lowest heavy hitter, if a new inserted item has a weight greater than this, it is a heavy hitter. This gets the index of the lowest heavy hitter from the top of the heap (lowestHitterIndex) if there is any and looks up its weight. If there is no entry in the table (lowestHitterIndex returns a negative index) this returns a zero weight.

Returns:

(undocumented)

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object