Package com.apple.foundationdb.async

Class RankedSet

java.lang.Object

com.apple.foundationdb.async.RankedSet

@API(UNSTABLE)
public class RankedSet
extends Object

RankedSet supports the efficient retrieval of elements by their rank as defined by lexicographic order.

Elements are added or removed from the set as byte-array keys.

The fundamental operations are:

• rank: the ordinal position of an element of the set (rank(com.apple.foundationdb.ReadTransactionContext, byte[])).
• select: the element at a given ordinal position in the set (getNth(com.apple.foundationdb.ReadTransactionContext, long)).

The set is implemented as a skip-list with a specified number of levels. Level zero has one entry for each element. Coarser levels have a sampling of values, determined by bits the hash code of their key.

The skip-list is stored as key-value pairs within a given subspace, where the key is a tuple of the form [level, key] and the value is the number of elements between this key and the previous key at the same level, encoded as a little-endian long.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static class	RankedSet.Config	Configuration settings for a RankedSet.
static class	RankedSet.ConfigBuilder	Builder for RankedSet.Config.
protected static class	RankedSet.Consistency
static interface	RankedSet.HashFunction	Function to compute the hash used to determine which levels a key value splits on.
protected static interface	RankedSet.Lookup

Field Summary

Fields

Modifier and Type	Field	Description
protected final RankedSet.Config	config
static final RankedSet.HashFunction	CRC_HASH	Hash using 32-bit CRC.
static final RankedSet.Config	DEFAULT_CONFIG
static final RankedSet.HashFunction	DEFAULT_HASH_FUNCTION	The default hash function to use.
static final int	DEFAULT_LEVELS
protected final Executor	executor
static final RankedSet.HashFunction	JDK_ARRAY_HASH	Hash using the JDK's default byte array hash.
static final int	MAX_LEVELS
static final RankedSet.HashFunction	RANDOM_HASH	Hash using a random number.
protected final Subspace	subspace

Constructor Summary

Constructors

Constructor	Description
RankedSet(Subspace subspace, Executor executor)	Initialize a new ranked set with the default configuration.
RankedSet(Subspace subspace, Executor executor, int nlevels)	Initialize a new ranked set.
RankedSet(Subspace subspace, Executor executor, RankedSet.Config config)	Initialize a new ranked set.
RankedSet(Subspace subspace, Executor executor, RankedSet.HashFunction hashFunction, int nlevels)	Initialize a new ranked set.

Method Summary

Modifier and Type	Method	Description
CompletableFuture<Boolean>	add(TransactionContext tc, byte[] key)	Add a key to the set.
protected CompletableFuture<Void>	addIncrementLevelKey(Transaction tr, byte[] key, int level, boolean orEqual)
protected CompletableFuture<Void>	addInsertLevelKey(Transaction tr, byte[] key, int level)
protected CompletableFuture<Void>	addLevelZeroKey(Transaction tr, byte[] key, int level, boolean increment)
protected RankedSet.Consistency	checkConsistency(ReadTransactionContext tc)
CompletableFuture<Void>	clear(TransactionContext tc)	Clears the entire set.
CompletableFuture<Boolean>	contains(ReadTransactionContext tc, byte[] key)	Checks for the presence of a key in the set.
CompletableFuture<Long>	count(ReadTransactionContext tc, byte[] key)	Count the number of occurrences of a key in the set.
RankedSet.Config	getConfig()	Get this ranked set's configuration.
Executor	getExecutor()	Get executed used by this ranked set.
protected int	getKeyHash(byte[] key)
CompletableFuture<byte[]>	getNth(ReadTransactionContext tc, long rank)	Return the Nth item in the set.
AsyncIterable<byte[]>	getRange(ReadTransaction tr, byte[] beginKey, byte[] endKey)
List<byte[]>	getRangeList(ReadTransactionContext tc, byte[] beginKey, byte[] endKey)	Returns the ordered set of keys in a given range.
Subspace	getSubspace()	Get the subspace used to store this ranked set.
CompletableFuture<Void>	init(TransactionContext tc)
CompletableFuture<Boolean>	initNeeded(ReadTransactionContext tc)	Determine whether init(com.apple.foundationdb.TransactionContext) needs to be called.
protected <T> AsyncIterator<T>	lookupIterator(AsyncIterable<T> iterable)
static RankedSet.ConfigBuilder	newConfigBuilder()	Start building a RankedSet.Config.
protected CompletableFuture<Boolean>	nextLookup(RankedSet.Lookup lookup, ReadTransaction tr)
protected void	nextLookupKey(long duration, boolean newIter, boolean hasNext, int level, boolean rankLookup)
CompletableFuture<Void>	preloadForLookup(ReadTransaction tr)	Read the deeper, likely empty, levels to get them into the RYW cache, since individual lookups may only add pieces, requiring additional requests as keys increase.
CompletableFuture<Long>	rank(ReadTransactionContext tc, byte[] key)	Return the index of a key within the set.
CompletableFuture<Long>	rank(ReadTransactionContext tc, byte[] key, boolean nullIfMissing)	Return the index of a key within the set.
CompletableFuture<Boolean>	remove(TransactionContext tc, byte[] key)	Removes a key from the set.
CompletableFuture<Long>	size(ReadTransactionContext tc)	Count the items in the set.
protected String	toDebugString(ReadTransactionContext tc)

Methods inherited from class java.lang.Object

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

Field Details

JDK_ARRAY_HASH

public static final RankedSet.HashFunction JDK_ARRAY_HASH

Hash using the JDK's default byte array hash. This hash does not have great distribution for certain values with low entropy.

CRC_HASH

public static final RankedSet.HashFunction CRC_HASH

Hash using 32-bit CRC. Although not designed for hashing, this does often give better distribution than JDK_ARRAY_HASH.

RANDOM_HASH

public static final RankedSet.HashFunction RANDOM_HASH

Hash using a random number. The result is actually independent of the key.

DEFAULT_HASH_FUNCTION

public static final RankedSet.HashFunction DEFAULT_HASH_FUNCTION

The default hash function to use. For reasons of compatibility with existing data, this defaults to the JDK's array hash.

MAX_LEVELS

public static final int MAX_LEVELS

See Also:

• Constant Field Values

DEFAULT_LEVELS

public static final int DEFAULT_LEVELS

See Also:

• Constant Field Values

DEFAULT_CONFIG

public static final RankedSet.Config DEFAULT_CONFIG

subspace

protected final Subspace subspace

executor

protected final Executor executor

config

protected final RankedSet.Config config

Constructor Details

RankedSet

public RankedSet(Subspace subspace,
 Executor executor,
 RankedSet.Config config)

Initialize a new ranked set.

Parameters:

subspace - the subspace where the ranked set is stored

executor - an executor to use when running asynchronous tasks

config - configuration to use

RankedSet

public RankedSet(Subspace subspace,
 Executor executor,
 RankedSet.HashFunction hashFunction,
 int nlevels)

Initialize a new ranked set. Although not (yet) deprecated, this constructor is mainly for compatibility and RankedSet(Subspace, Executor, Config) may be superior in new code.

Parameters:

subspace - the subspace where the ranked set is stored

executor - an executor to use when running asynchronous tasks

hashFunction - hash function for new ranked set

nlevels - number of skip list levels for new ranked set

RankedSet

public RankedSet(Subspace subspace,
 Executor executor,
 int nlevels)

Initialize a new ranked set. Although not (yet) deprecated, this constructor is mainly for compatibility and RankedSet(Subspace, Executor, Config) may be superior in new code.

Parameters:

subspace - the subspace where the ranked set is stored

executor - an executor to use when running asynchronous tasks

nlevels - number of skip list levels for new ranked set

RankedSet

public RankedSet(Subspace subspace,
 Executor executor)

Initialize a new ranked set with the default configuration.

Parameters:

subspace - the subspace where the ranked set is stored

executor - an executor to use when running asynchronous tasks

Method Details

newConfigBuilder

public static RankedSet.ConfigBuilder newConfigBuilder()

Start building a RankedSet.Config.

Returns:

a new Config that can be altered and then built for use with a RankedSet

See Also:

• RankedSet.ConfigBuilder.build()

init

public CompletableFuture<Void> init(TransactionContext tc)

initNeeded

public CompletableFuture<Boolean> initNeeded(ReadTransactionContext tc)

Determine whether init(com.apple.foundationdb.TransactionContext) needs to be called.

Parameters:

tc - the transaction to use to access the database

Returns:

true if this ranked set needs to be initialized

getSubspace

public Subspace getSubspace()

Get the subspace used to store this ranked set.

Returns:

ranked set subspace

getExecutor

public Executor getExecutor()

Get executed used by this ranked set.

Returns:

executor used when running asynchronous tasks

getConfig

public RankedSet.Config getConfig()

Get this ranked set's configuration.

Returns:

ranked set configuration

add

public CompletableFuture<Boolean> add(TransactionContext tc,
 byte[] key)

Add a key to the set. If RankedSet.Config.isCountDuplicates() is false and key is already present, the return value is false. If RankedSet.Config.isCountDuplicates() is true, the return value is never false and a duplicate will cause all rank(com.apple.foundationdb.ReadTransactionContext, byte[])s below it to increase by one.

Parameters:

tc - the transaction to use to access the database

key - the key to add

Returns:

a future that completes to true if the ranked set was modified

getKeyHash

protected int getKeyHash(byte[] key)

addLevelZeroKey

protected CompletableFuture<Void> addLevelZeroKey(Transaction tr,
 byte[] key,
 int level,
 boolean increment)

addIncrementLevelKey

protected CompletableFuture<Void> addIncrementLevelKey(Transaction tr,
 byte[] key,
 int level,
 boolean orEqual)

addInsertLevelKey

protected CompletableFuture<Void> addInsertLevelKey(Transaction tr,
 byte[] key,
 int level)

remove

public CompletableFuture<Boolean> remove(TransactionContext tc,
 byte[] key)

Removes a key from the set.

Parameters:

tc - the transaction to use to access the database

key - the key to remove

Returns:

a future that completes to true if the set was modified, that is, if the key was present before this operation

clear

public CompletableFuture<Void> clear(TransactionContext tc)

Clears the entire set.

Parameters:

tc - the transaction to use to access the database

Returns:

a future that completes when the ranked set has been cleared

contains

public CompletableFuture<Boolean> contains(ReadTransactionContext tc,
 byte[] key)

Checks for the presence of a key in the set.

Parameters:

tc - the transaction to use to access the database

key - the key to check for

Returns:

a future that completes to true if the key is present in the ranked set

count

public CompletableFuture<Long> count(ReadTransactionContext tc,
 byte[] key)

Count the number of occurrences of a key in the set.

Parameters:

tc - the transaction to use to access the database

key - the key to check for

Returns:

a future that completes to 0 if the key is not present in the ranked set or 1 if the key is present in the ranked set and duplicates are not counted or the number of occurrences if duplicated are counted separately

getNth

public CompletableFuture<byte[]> getNth(ReadTransactionContext tc,
 long rank)

Return the Nth item in the set. This operation is also referred to as select.

Parameters:

tc - the transaction to use to access the database

rank - the rank index to find

Returns:

a future that completes to the key for the rankth item or null if that index is out of bounds

See Also:

• rank(com.apple.foundationdb.ReadTransactionContext, byte[])

getRangeList

public List<byte[]> getRangeList(ReadTransactionContext tc,
 byte[] beginKey,
 byte[] endKey)

Returns the ordered set of keys in a given range.

Parameters:

tc - the transaction to use to access the database

beginKey - the (inclusive) lower bound for the range

endKey - the (exclusive) upper bound for the range

Returns:

a list of keys in the ranked set within the given range

getRange

public AsyncIterable<byte[]> getRange(ReadTransaction tr,
 byte[] beginKey,
 byte[] endKey)

preloadForLookup

public CompletableFuture<Void> preloadForLookup(ReadTransaction tr)

Read the deeper, likely empty, levels to get them into the RYW cache, since individual lookups may only add pieces, requiring additional requests as keys increase.

Parameters:

tr - the transaction to use to access the database

Returns:

a future that is complete when the deeper levels have been loaded

nextLookup

protected CompletableFuture<Boolean> nextLookup(RankedSet.Lookup lookup,
 ReadTransaction tr)

lookupIterator

protected <T> AsyncIterator<T> lookupIterator(AsyncIterable<T> iterable)

nextLookupKey

protected void nextLookupKey(long duration,
 boolean newIter,
 boolean hasNext,
 int level,
 boolean rankLookup)

rank

public CompletableFuture<Long> rank(ReadTransactionContext tc,
 byte[] key)

Return the index of a key within the set.

Parameters:

tc - the transaction to use to access the database

key - the key to find

Returns:

a future that completes to the index of key in the ranked set or null if it is not present

See Also:

• getNth(com.apple.foundationdb.ReadTransactionContext, long)

rank

public CompletableFuture<Long> rank(ReadTransactionContext tc,
 byte[] key,
 boolean nullIfMissing)

Return the index of a key within the set.

Parameters:

tc - the transaction to use to access the database

key - the key to find

nullIfMissing - whether to return null when key is not present in the set

Returns:

a future that completes to the index of key in the ranked set, or null if it is not present and nullIfMissing is true, or the index key would have in the ranked set

See Also:

• getNth(com.apple.foundationdb.ReadTransactionContext, long)

size

public CompletableFuture<Long> size(ReadTransactionContext tc)

Count the items in the set.

Parameters:

tc - the transaction to use to access the database

Returns:

a future that completes to the number of items in the set

checkConsistency

protected RankedSet.Consistency checkConsistency(ReadTransactionContext tc)

toDebugString

protected String toDebugString(ReadTransactionContext tc)