org.jgroups.protocols.pbcast

Class Digest

Implemented Interfaces:
Externalizable, Streamable

public class Digest
extends java.lang.Object
implements Externalizable, Streamable

A message digest, which is used by the PBCAST layer for gossiping (also used by NAKACK for keeping track of current seqnos for all members). It contains pairs of senders and a range of seqnos (low and high), where each sender is associated with its highest and lowest seqnos seen so far. That is, the lowest seqno which was not yet garbage-collected and the highest that was seen so far and is deliverable (or was already delivered) to the application. A range of [0 - 0] means no messages have been received yet.

April 3 2001 (bela): Added high_seqnos_seen member. It is used to disseminate information about the last (highest) message M received from a sender P. Since we might be using a negative acknowledgment message numbering scheme, we would never know if the last message was lost. Therefore we periodically gossip and include the last message seqno. Members who haven't seen it (e.g. because msg was dropped) will request a retransmission. See DESIGN for details.

Author:
Bela Ban

Nested Class Summary

static class
Digest.Entry
Class keeping track of the lowest and highest sequence numbers delivered, and the highest sequence numbers received, per member

Field Summary

protected static Log
log

Constructor Summary

Digest()
Digest(int size)

Method Summary

void
add(Address sender, long low_seqno, long high_seqno)
void
add(Address sender, long low_seqno, long high_seqno, long high_seqno_seen)
void
add(Digest d)
void
clear()
boolean
contains(Address sender)
Digest
copy()
boolean
equals(Object obj)
Digest.Entry
get(Address sender)
long
highSeqnoAt(Address sender)
long
highSeqnoSeenAt(Address sender)
void
incrementHighSeqno(Address sender)
Increments the sender's high_seqno by 1.
long
lowSeqnoAt(Address sender)
void
merge(Address sender, long low_seqno, long high_seqno, long high_seqno_seen)
Similar to add(), but if the sender already exists, its seqnos will be modified (no new entry) as follows:
  1. this.low_seqno=min(this.low_seqno, low_seqno)
  2. this.high_seqno=max(this.high_seqno, high_seqno)
  3. this.high_seqno_seen=max(this.high_seqno_seen, high_seqno_seen)
If the sender doesn not exist, a new entry will be added (provided there is enough space)
void
merge(Digest d)
Adds a digest to this digest.
String
printHighSeqnos()
String
printHighSeqnosSeen()
void
readExternal(ObjectInput in)
void
readFrom(DataInputStream in)
Read the state of the current object (including superclasses) from instream Note that the input stream must not be closed
void
replace(Digest d)
void
resetAt(Address sender)
Resets the seqnos for the sender at 'index' to 0.
boolean
sameSenders(Digest other)
Compares two digests and returns true if the senders are the same, otherwise false.
long
serializedSize()
boolean
set(Address sender, long low_seqno, long high_seqno, long high_seqno_seen)
void
setHighSeqnoAt(Address sender, long high_seqno)
void
setHighSeqnoSeenAt(Address sender, long high_seqno_seen)
void
setHighestDeliveredAndSeenSeqnos(Address sender, long high_seqno, long high_seqno_seen)
int
size()
String
toString()
void
writeExternal(ObjectOutput out)
void
writeTo(DataOutputStream out)
Write the entire state of the current object (including superclasses) to outstream.

Field Details

log

protected static final Log log

Constructor Details

Digest

public Digest()

Digest

public Digest(int size)

Method Details

add

public void add(Address sender,
                long low_seqno,
                long high_seqno)

add

public void add(Address sender,
                long low_seqno,
                long high_seqno,
                long high_seqno_seen)

add

public void add(Digest d)

clear

public void clear()

contains

public boolean contains(Address sender)

copy

public Digest copy()

equals

public boolean equals(Object obj)

get

public Digest.Entry get(Address sender)

highSeqnoAt

public long highSeqnoAt(Address sender)

highSeqnoSeenAt

public long highSeqnoSeenAt(Address sender)

incrementHighSeqno

public void incrementHighSeqno(Address sender)
Increments the sender's high_seqno by 1.

lowSeqnoAt

public long lowSeqnoAt(Address sender)

merge

public void merge(Address sender,
                  long low_seqno,
                  long high_seqno,
                  long high_seqno_seen)
Similar to add(), but if the sender already exists, its seqnos will be modified (no new entry) as follows:
  1. this.low_seqno=min(this.low_seqno, low_seqno)
  2. this.high_seqno=max(this.high_seqno, high_seqno)
  3. this.high_seqno_seen=max(this.high_seqno_seen, high_seqno_seen)
If the sender doesn not exist, a new entry will be added (provided there is enough space)

merge

public void merge(Digest d)
Adds a digest to this digest. This digest must have enough space to add the other digest; otherwise an error message will be written. For each sender in the other digest, the merge() method will be called.

printHighSeqnos

public String printHighSeqnos()

printHighSeqnosSeen

public String printHighSeqnosSeen()

readExternal

public void readExternal(ObjectInput in)
            throws IOException,
                   ClassNotFoundException

readFrom

public void readFrom(DataInputStream in)
            throws IOException,
                   IllegalAccessException,
                   InstantiationException
Read the state of the current object (including superclasses) from instream Note that the input stream must not be closed
Specified by:
readFrom in interface Streamable

replace

public void replace(Digest d)

resetAt

public void resetAt(Address sender)
Resets the seqnos for the sender at 'index' to 0. This happens when a member has left the group, but it is still in the digest. Resetting its seqnos ensures that no-one will request a message retransmission from the dead member.

sameSenders

public boolean sameSenders(Digest other)
Compares two digests and returns true if the senders are the same, otherwise false.
Parameters:
other -
Returns:
True if senders are the same, otherwise false.

serializedSize

public long serializedSize()

set

public boolean set(Address sender,
                   long low_seqno,
                   long high_seqno,
                   long high_seqno_seen)

setHighSeqnoAt

public void setHighSeqnoAt(Address sender,
                           long high_seqno)

setHighSeqnoSeenAt

public void setHighSeqnoSeenAt(Address sender,
                               long high_seqno_seen)

setHighestDeliveredAndSeenSeqnos

public void setHighestDeliveredAndSeenSeqnos(Address sender,
                                             long high_seqno,
                                             long high_seqno_seen)

size

public int size()

toString

public String toString()

writeExternal

public void writeExternal(ObjectOutput out)
            throws IOException

writeTo

public void writeTo(DataOutputStream out)
            throws IOException
Write the entire state of the current object (including superclasses) to outstream. Note that the output stream must not be closed
Specified by:
writeTo in interface Streamable

Copyright B) 1998-2005 Bela Ban. All Rights Reserved.