com.bigdata.quorum
Class AbstractQuorum<S extends Remote,C extends QuorumClient<S>>

java.lang.Object
  com.bigdata.quorum.AbstractQuorum<S,C>

All Implemented Interfaces:

Quorum<S,C>

Direct Known Subclasses:

ZKQuorumImpl

public abstract class AbstractQuorum<S extends Remote,C extends QuorumClient<S>>
extends Object
implements Quorum<S,C>

Abstract base class handles much of the logic for the distribution of RMI calls from the leader to the follower and for the HA write pipeline.

Version:

$Id: AbstractQuorum.java 4069 2011-01-09 20:58:02Z thompsonbry $

Author:

Bryan Thompson

TODO:

Support the synchronization protocol, including joining with the quorum at the next commit point or (if there are no pending writes) as soon as the node is caught up.

Nested Class Summary

protected static class	AbstractQuorum.E Simple event impl.
protected class	AbstractQuorum.QuorumActorBase Base class for QuorumActor implementations.
protected class	AbstractQuorum.QuorumWatcherBase Base class for QuorumWatcher implementations.

Field Summary

protected static String	ERR_BAD_TOKEN Text when an operation is not permitted because the new value for the lastValidToken is not strictly greater than the current value.
protected static String	ERR_CAN_NOT_MEET Text when an operation is not permitted because the quorum can not meet.
protected static String	ERR_NOT_IN_CONSENSUS Text when an operation is not permitted because the service has not cast its vote for a lastCommitTime around which there is a consensus of (k+1)/2 quorum members.
protected static String	ERR_NOT_MEMBER Text when an operation is not permitted because the service is not a quorum member.
protected static String	ERR_NOT_PIPELINE Text when an operation is not permitted because the service is not part of the write pipeline.
protected static String	ERR_QUORUM_MET Text when an operation is not permitted while the quorum is met.
protected ReentrantLock	lock The lock protecting state changes in the remaining fields and used to provide Conditions used to await various states.
protected static org.apache.log4j.Logger	log

Fields inherited from interface com.bigdata.quorum.Quorum

NO_QUORUM

Constructor Summary

protected

AbstractQuorum(int k) Constructor, which MUST be followed by #start() to begin operations.

Method Summary

void	addListener(QuorumListener listener) Add a listener
void	assertLeader(long token) Assert that the token is still valid and that the Quorum.getClient() is the quorum leader.
void	assertQuorum(long token) Assert that the quorum associated with the token is still valid.
void	awaitBreak() Await a met break (blocking).
void	awaitBreak(long timeout, TimeUnit units) Await a met break (blocking).
long	awaitQuorum() Await a met quorum (blocking).
long	awaitQuorum(long timeout, TimeUnit units) Await a met quorum (blocking).
protected void	finalize()
QuorumActor<S,C>	getActor() The object used to effect changes in distributed quorum state on the behalf of the QuorumMember.
Long	getCastVote(UUID serviceId) Return the vote cast by the service.
C	getClient() Return the QuorumClient iff the quorum is running.
UUID[]	getJoined() Return the identifiers for the member services joined with this quorum.
UUID	getLastInPipeline() Return the UUID of the service which is the last service in the write pipeline.
UUID	getLeaderId() The UUID of the leader Quorum leader (non-blocking).
QuorumMember<S>	getMember() Return the QuorumMember iff the quorum is running.
UUID[]	getMembers() Return the identifiers for the member services (all known physical services for the logical service).
UUID[]	getPipeline() Return the service identifiers for the services in the write pipeline in the order in which they will accept and relay writes.
UUID[]	getPipelinePriorAndNext(UUID serviceId) Return the UUIDof the service in the pipeline which is immediately upstream from (prior to) and downstream from (next to) the specified service.
Map<Long,UUID[]>	getVotes() Return an immutable snapshot of the votes cast by the quorum members.
protected QuorumWatcher<S,C>	getWatcher() The QuorumWatcher which informs this AbstactQuorum of changes occurring in the distributed state of the quorum.
boolean	isHighlyAvailable() Return true if Quorum.replicationFactor() is GT ONE (1).
boolean	isQuorumMet() Return true iff the #of services joined with the quorum is GTE (k + 1).
long	lastValidToken() The quorum token which was assigned the last time a leader was elected.
protected abstract AbstractQuorum.QuorumActorBase	newActor(String logicalServiceId, UUID serviceId) Factory method invoked by start(QuorumClient) iff the QuorumClient is a QuorumMember.
protected abstract AbstractQuorum.QuorumWatcherBase	newWatcher(String logicalServiceId) Factory method invoked by start(QuorumClient).
void	removeListener(QuorumListener listener) Remove a listener (the quorum's client is always a listener).
int	replicationFactor() Return k, the target replication factor.
void	start(C client) Begin asynchronous processing.
void	terminate() Terminate any asynchronous processing associated with maintaining the Quorum state.
long	token() The current token for the quorum.
String	toString() Return a human readable representation of the local copy of the distributed quorum state (non-blocking).
String	toStringAtomic() Return a human readable representation of an atomic snapshot of the local copy of the distributed quorum state.

Methods inherited from class java.lang.Object

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

Field Detail

log

protected static final transient org.apache.log4j.Logger log

ERR_NOT_MEMBER

protected static final transient String ERR_NOT_MEMBER

Text when an operation is not permitted because the service is not a quorum member.

See Also:

Constant Field Values

ERR_NOT_PIPELINE

protected static final transient String ERR_NOT_PIPELINE

Text when an operation is not permitted because the service is not part of the write pipeline.

See Also:

Constant Field Values

ERR_NOT_IN_CONSENSUS

protected static final transient String ERR_NOT_IN_CONSENSUS

Text when an operation is not permitted because the service has not cast its vote for a lastCommitTime around which there is a consensus of (k+1)/2 quorum members.

See Also:

Constant Field Values

ERR_BAD_TOKEN

protected static final transient String ERR_BAD_TOKEN

Text when an operation is not permitted because the new value for the lastValidToken is not strictly greater than the current value.

See Also:

Constant Field Values

ERR_QUORUM_MET

protected static final transient String ERR_QUORUM_MET

Text when an operation is not permitted while the quorum is met.

See Also:

Constant Field Values

ERR_CAN_NOT_MEET

protected static final transient String ERR_CAN_NOT_MEET

Text when an operation is not permitted because the quorum can not meet.

See Also:

Constant Field Values

lock

protected final ReentrantLock lock

The lock protecting state changes in the remaining fields and used to provide Conditions used to await various states. This is exposed to concrete implementations of the AbstractQuorum.QuorumWatcherBase.

TODO:

If we make updating the lastValidToken and the current token an atomic action when a leader is elected then we may be able to make this a private lock again.

Constructor Detail

AbstractQuorum

protected AbstractQuorum(int k)

Constructor, which MUST be followed by #start() to begin operations.

Method Detail

finalize

protected void finalize()
                 throws Throwable

Overrides:

finalize in class Object

Throws:

Throwable

start

public void start(C client)

Begin asynchronous processing. The state of the quorum is reset, the client is registered as a QuorumListener, the QuorumActor and QuorumWatcher are created, and asynchronous discovery is initialized for the QuorumWatcher.

Specified by:

start in interface Quorum<S extends Remote,C extends QuorumClient<S>>

terminate

public void terminate()

Description copied from interface: Quorum

Terminate any asynchronous processing associated with maintaining the Quorum state.

Specified by:

terminate in interface Quorum<S extends Remote,C extends QuorumClient<S>>

newActor

protected abstract AbstractQuorum.QuorumActorBase newActor(String logicalServiceId,
                                                           UUID serviceId)

Factory method invoked by start(QuorumClient) iff the QuorumClient is a QuorumMember.

Parameters:

logicalServiceId - The identifier of the logical service corresponding to the highly available quorum.

serviceId - The UUID of the service on whose behalf the actor will act.

Returns:

The QuorumActor which will effect changes in the distributed state of the quorum.

newWatcher

protected abstract AbstractQuorum.QuorumWatcherBase newWatcher(String logicalServiceId)

Factory method invoked by start(QuorumClient).

Note: Additional information can be passed to the watcher factor by derived classes. For example, the UUID of the logical service to

Parameters:

logicalServiceId - The identifier of the logical service whose quorum state will be watched.

Returns:

The QuorumWatcher which will inform this AbstactQuorum of changes occurring in the distributed state of the quorum.

toString

public String toString()

Return a human readable representation of the local copy of the distributed quorum state (non-blocking). The representation may be inconsistent since the internal lock required for a consistent view is NOT acquired.

Overrides:

toString in class Object

toStringAtomic

public String toStringAtomic()

Return a human readable representation of an atomic snapshot of the local copy of the distributed quorum state. This method acquires an internal lock to provide the atomic semantics. Since acquiring lock could cause a deadlock which would not otherwise arise, this method should be used sparingly.

getClient

public C getClient()

Description copied from interface: Quorum

Return the QuorumClient iff the quorum is running.

Specified by:

getClient in interface Quorum<S extends Remote,C extends QuorumClient<S>>

Returns:

The QuorumClient.

getMember

public QuorumMember<S> getMember()

Description copied from interface: Quorum

Return the QuorumMember iff the quorum is running.

Specified by:

getMember in interface Quorum<S extends Remote,C extends QuorumClient<S>>

Returns:

The QuorumMember.

getActor

public QuorumActor<S,C> getActor()

The object used to effect changes in distributed quorum state on the behalf of the QuorumMember.

Specified by:

getActor in interface Quorum<S extends Remote,C extends QuorumClient<S>>

Returns:

The QuorumActor which will effect changes in the distributed state of the quorum -or- null if the client is not a QuorumMember (only quorum members can take actions which effect the distributed quorum state).

Throws:

IllegalStateException - if the quorum is not running.

getWatcher

protected QuorumWatcher<S,C> getWatcher()

The QuorumWatcher which informs this AbstactQuorum of changes occurring in the distributed state of the quorum.

Throws:

IllegalStateException - if the quorum is not running.

addListener

public void addListener(QuorumListener listener)

Description copied from interface: Quorum

Add a listener

Specified by:

addListener in interface Quorum<S extends Remote,C extends QuorumClient<S>>

Parameters:

listener - The listener.

removeListener

public void removeListener(QuorumListener listener)

Description copied from interface: Quorum

Remove a listener (the quorum's client is always a listener).

Specified by:

removeListener in interface Quorum<S extends Remote,C extends QuorumClient<S>>

Parameters:

listener - The listener.

replicationFactor

public int replicationFactor()

Description copied from interface: Quorum

Return k, the target replication factor. The replication factor must be a non-negative odd integer (1, 3, 5, 7, etc). A quorum exists only when (k + 1)/2 physical services for the same logical service have an agreement on state. A single service with k := 1 is the degenerate case and has a minimum quorum size of ONE (1). High availability is only possible when k is GT ONE (1). Thus k := 3 is the minimum value for which services can be highly available and has a minimum quorum size of 2.

Specified by:

replicationFactor in interface Quorum<S extends Remote,C extends QuorumClient<S>>

isHighlyAvailable

public final boolean isHighlyAvailable()

Description copied from interface: Quorum

Return true if Quorum.replicationFactor() is GT ONE (1). High availability exists (in principle) when the Quorum.replicationFactor() k is greater than one. High availability exists (in practice) when the Quorum is met for a Quorum that is configured for high availability.

Specified by:

isHighlyAvailable in interface Quorum<S extends Remote,C extends QuorumClient<S>>

Returns:

true if this Quorum is highly available in principle

lastValidToken

public long lastValidToken()

Description copied from interface: Quorum

The quorum token which was assigned the last time a leader was elected.

Specified by:

lastValidToken in interface Quorum<S extends Remote,C extends QuorumClient<S>>

getMembers

public UUID[] getMembers()

Description copied from interface: Quorum

Return the identifiers for the member services (all known physical services for the logical service).

Specified by:

getMembers in interface Quorum<S extends Remote,C extends QuorumClient<S>>

Returns:

The UUIDs of the member services.

getVotes

public Map<Long,UUID[]> getVotes()

Description copied from interface: Quorum

Return an immutable snapshot of the votes cast by the quorum members.

Specified by:

getVotes in interface Quorum<S extends Remote,C extends QuorumClient<S>>

getCastVote

public Long getCastVote(UUID serviceId)

Description copied from interface: Quorum

Return the vote cast by the service.

Specified by:

getCastVote in interface Quorum<S extends Remote,C extends QuorumClient<S>>

Parameters:

serviceId - The service.

Returns:

The vote cast by that service -or- null if the service has not cast a vote.

getJoined

public UUID[] getJoined()

Description copied from interface: Quorum

Return the identifiers for the member services joined with this quorum. If the quorum was met at the moment the request was processed, then the first element of the array was the quorum leader as of that moment and the remaining elements are followers (non-blocking).

Specified by:

getJoined in interface Quorum<S extends Remote,C extends QuorumClient<S>>

Returns:

The UUIDs of the member services joined with this quorum.

getPipeline

public UUID[] getPipeline()

Description copied from interface: Quorum

Return the service identifiers for the services in the write pipeline in the order in which they will accept and relay writes.

Specified by:

getPipeline in interface Quorum<S extends Remote,C extends QuorumClient<S>>

Returns:

The UUIDs of the ordered services in the write pipeline.

getLastInPipeline

public UUID getLastInPipeline()

Description copied from interface: Quorum

Return the UUID of the service which is the last service in the write pipeline.

Specified by:

getLastInPipeline in interface Quorum<S extends Remote,C extends QuorumClient<S>>

Returns:

The UUID of the last service in the write pipeline or null if there are no services in the write pipeline.

getPipelinePriorAndNext

public UUID[] getPipelinePriorAndNext(UUID serviceId)

Description copied from interface: Quorum

Return the UUIDof the service in the pipeline which is immediately upstream from (prior to) and downstream from (next to) the specified service. These are, respectively, the service from which it receives data (upstream) and to which it sends data (downstream).

Specified by:

getPipelinePriorAndNext in interface Quorum<S extends Remote,C extends QuorumClient<S>>

Parameters:

serviceId - The service id.

Returns:

Either null if the serviceId does not appear in the write pipeline -or- an array of two elements whose values are: [0] The upstream serviceId in the write pipeline, which will be null iff serviceId is the first service in the write pipeline; and [1] The downstream service in the write pipeline, which will be null iff serviceId is the last service in the write pipeline.

getLeaderId

public UUID getLeaderId()

Description copied from interface: Quorum

The UUID of the leader Quorum leader (non-blocking).

Specified by:

getLeaderId in interface Quorum<S extends Remote,C extends QuorumClient<S>>

Returns:

The UUID of the leader Quorum leader -or- null if the quorum is not met.

token

public final long token()

Description copied from interface: Quorum

The current token for the quorum. The initial value before the quorum has met is Quorum.NO_QUORUM. When a leader is elected, it sets the current token as token := lastValidToken() + 1. The current token is cleared to Quorum.NO_QUORUM if the leader leaves the met quorum. It is cleared Quorum.NO_QUORUM if the quorum breaks. While a leader may be elected many times for the same lastCommitTime, a new quorum token is assigned each time a leader is elected.

Specified by:

token in interface Quorum<S extends Remote,C extends QuorumClient<S>>

assertQuorum

public final void assertQuorum(long token)

Description copied from interface: Quorum

Assert that the quorum associated with the token is still valid. The pattern for using this method is to save the Quorum.token() somewhere. This method may then be invoked to verify that the saved token is still valid and, hence, that the quorum is still met.

Specified by:

assertQuorum in interface Quorum<S extends Remote,C extends QuorumClient<S>>

Parameters:

token - The token for the quorum.

assertLeader

public final void assertLeader(long token)

Description copied from interface: Quorum

Assert that the token is still valid and that the Quorum.getClient() is the quorum leader.

Specified by:

assertLeader in interface Quorum<S extends Remote,C extends QuorumClient<S>>

Parameters:

token - A quorum token.

isQuorumMet

public final boolean isQuorumMet()

Description copied from interface: Quorum

Return true iff the #of services joined with the quorum is GTE (k + 1). A service with a met quorum is highly available in practice.

Specified by:

isQuorumMet in interface Quorum<S extends Remote,C extends QuorumClient<S>>

awaitQuorum

public long awaitQuorum()
                 throws InterruptedException,
                        AsynchronousQuorumCloseException

Await a met quorum (blocking). If the Quorumis not met, then this will block until the Quorum meets.

This watches the current token and will return as soon as the token is valid.

Specified by:

awaitQuorum in interface Quorum<S extends Remote,C extends QuorumClient<S>>

Returns:

The current quorum token.

Throws:

AsynchronousQuorumCloseException - if Quorum.terminate() is invoked while awaiting a quorum meet.

InterruptedException

awaitQuorum

public long awaitQuorum(long timeout,
                        TimeUnit units)
                 throws InterruptedException,
                        TimeoutException,
                        AsynchronousQuorumCloseException

Description copied from interface: Quorum

Await a met quorum (blocking). If the Quorumis not met, then this will block until the Quorum meets.

Specified by:

awaitQuorum in interface Quorum<S extends Remote,C extends QuorumClient<S>>

Parameters:

timeout - The timeout.

units - The timeout units.

Returns:

The current quorum token.

Throws:

TimeoutException - if the timeout expired before the quorum met.

AsynchronousQuorumCloseException - if Quorum.terminate() is invoked while awaiting a quorum meet.

InterruptedException

awaitBreak

public void awaitBreak()
                throws InterruptedException,
                       AsynchronousQuorumCloseException

Await a met break (blocking). If the Quorum is met, then this will block until the Quorum breaks.

Specified by:

awaitBreak in interface Quorum<S extends Remote,C extends QuorumClient<S>>

Throws:

AsynchronousQuorumCloseException - if Quorum.terminate() is invoked while awaiting a quorum break.

InterruptedException

TODO:

This triggers when it notices that the quorum is currently broken rather than when it notices that the quorum on entry had broken. It will fail to return if a quorum break is cured before it examines [token] again. Regardless, there is no guarantee that the quorum is still broken by the time the caller looks at the quorum again.

Are these the desired semantics for this public method?

awaitBreak

public void awaitBreak(long timeout,
                       TimeUnit units)
                throws InterruptedException,
                       TimeoutException,
                       AsynchronousQuorumCloseException

Description copied from interface: Quorum

Await a met break (blocking). If the Quorum is met, then this will block until the Quorum breaks.

Specified by:

awaitBreak in interface Quorum<S extends Remote,C extends QuorumClient<S>>

Parameters:

timeout - The timeout.

units - The timeout units.

Throws:

TimeoutException - if the timeout expired before the quorum breaks.

AsynchronousQuorumCloseException - if Quorum.terminate() is invoked while awaiting a quorum break.

InterruptedException