|
|||||||||||
| PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||||
| SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD | ||||||||||
java.lang.Object | +--ostore.archive.Erasure
the Erasure class is an abstract class (interface) for all
erasure codes For example,
Cauchy-Reed-Solomon,
Interleaved-Reed-Solomon,
or Tornado codes.
Erasure codes are a form of Error Correction Codes (ECC), except that
you can detect an entire erasure and correct for it.
Erasure codes and self-verifying fragments are the cornerstone of
the archival layer's fault tolerance and automatic repair. An erasure code
treats input data as a series of m Fragments,
which it transforms into n Fragments, where
n > m. The resulting code's essential perperty is
that any m of the coded Fragments
are sufficient to reconstruct the original data.
The rate of encoding is r = m/n<1. The
storage overhead is 1/r. The system can adjust the
durability of information by selecting the rate (and hence
storage overhead).
Fragment,
Cauchy,
Interleaved| Field Summary | |
|---|---|
protected int |
_fragmentDataLength
fragmentDataLength is the Fragment length in bytes
of each Fragment excluding the overhead for storing the index. |
protected int |
_fragmentIndexLength
fragmentIndexLength is the overhead for storing the index. |
protected int |
_fragmentTotalLength
fragmentTotalLength is the Fragment length in bytes
including the overhead for storing the index
after encoding. |
protected int |
_inverseRate
_inverseRate is the inverse rate of encoding |
protected NodeId |
_node_id
_node_id is the NodeId of the local
server where this class is running. |
protected int |
_numFragments
_numFragments is the total number of
Fragments to be sent after encoding. |
protected int |
_numMessageFragments
_numMessageFragments is the number of message
Fragments to be sent after encoding. |
protected int |
_numRedundantFragments
numRedundantFragments is the number of redundant
Fragments to be sent after encoding. |
protected int |
_size
_size is size of message in bytes |
protected boolean |
_verify
Verify the results produced by the encode or decode routines. |
static int |
sizeOfLong
sizeOfLong is the symbol size (we use the native machine
size. |
| Constructor Summary | |
|---|---|
Erasure(int size)
CONSTRUCTOR: initializes the the erasure class according to the specified parameters. |
|
Erasure(int size,
int fragmentDataLength)
CONSTRUCTOR: initializes the the erasure class according to the specified parameters. |
|
Erasure(int size,
int numFragments,
int inverseRate,
boolean verify,
NodeId node_id)
CONSTRUCTOR initializes the the erasure class according to the specified parameters. |
|
| Method Summary | |
|---|---|
boolean |
compareMsg(int[] orig_msg,
int[] rec_msg,
int size)
compareMsg compares the original msg with the
encoded/decoded message. |
abstract void |
decode(int[] rec_pckts,
int Nrec,
int[] rec_message,
byte[] data,
Stats procTime)
decode decodes an object
using an erasure code. |
abstract void |
encode(byte[] byteMsg,
int[] msg,
int[] intFrags,
Stats stat)
encode encodes a object
using an erasure code. |
abstract int |
fragmentDataLength()
fragmentDataLength is the Fragment length in
bytes of each Fragment excluding the overhead for storing the
index. |
abstract int |
fragmentIndexLength()
fragmentIndexLength |
abstract int |
fragmentTotalLength()
fragmentTotalLength is the Fragment length in bytes
including the overhead for storing the index after encoding. |
abstract int |
getBlockSize(int blockSize,
int numFragments,
int inverseRate)
getBlockSize returns the message size corresponding to the
input blockSize, numFragments, and
inverseRate. |
static int |
getBlockSize(int blockSize,
int numFragments,
int inverseRate,
int type)
getBlockSize computes the block size corresponding
to the input blocksize, numFragments, inverseRate, and erasureType. |
abstract int |
getEncodeType()
getEncodeType returns the encode type of this Erasure coder. |
static Erasure |
getErasure(Erasure oldE,
int blockSize,
int numFragments,
int inverseRate,
int erasureType,
boolean verify,
NodeId node_id,
SecureHash guid)
getErasure creates and initializes a new
Erasure coder if the current passed in one is
null or does not support the correct
blockSize; otherwise, getErasure
will return the original Erasure coder unchanged. |
abstract int |
getFragmentArrayLength()
getFragmentArrayLength returns the length of the
Fragment array divisible by sizeOfLong. |
int |
getInverseRate()
getOmverseRate returns the inverse rate of encoding. |
int[] |
getMsg(int len)
getMsg initializes array message with a fake message
(string of bytes) up to len bytes long. |
abstract int |
getMsgArrayLength()
getMsgArrayLength returns the length of the msg
array divisible by sizeOfLong. |
abstract int |
getNumFragments()
numFragments returns the number of
Fragments after encoding (without loss of
Fragments). |
int |
getSize()
getSize returns the size of the msg that can be encoded. |
protected static Random |
instanceRandom(NodeId node_id)
instanceRandom returns an instance of a
Random variable. |
protected static boolean |
instanceRandomContains(NodeId node_id)
instanceRandomContains returns true if map of instance
instance variables contains node_id, false otherwise. |
protected static void |
instanciateRandom(int seed,
NodeId node_id)
instanciateRandom creates an instance of a
Random associated with NodeId and
instanciated with the seed. |
int |
loseFragments(int[] fragments,
int[] rec_fragments,
double keepRate,
int[] pNrec)
loseFragments decide which Fragments to
keep randomly. |
abstract int |
numMessageFragments()
numMessageFragments returns the number of number of messge
Fragments. |
abstract int |
numRedundantFragments()
numRedundantFragments returns the redundant number of
Fragments. |
| Methods inherited from class java.lang.Object |
|---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
| Field Detail |
public static final int sizeOfLong
sizeOfLong is the symbol size (we use the native machine
size. In this case an int or 4 bytes).
protected NodeId _node_id
_node_id is the NodeId of the local
server where this class is running.
protected int _size
_size is size of message in bytes
protected int _inverseRate
_inverseRate is the inverse rate of encoding
protected int _numFragments
_numFragments is the total number of
Fragments to be sent after encoding.
protected int _numMessageFragments
_numMessageFragments is the number of message
Fragments to be sent after encoding.
protected int _numRedundantFragments
numRedundantFragments is the number of redundant
Fragments to be sent after encoding.
protected int _fragmentDataLength
fragmentDataLength is the Fragment length in bytes
of each Fragment excluding the overhead for storing the index.
protected int _fragmentIndexLength
fragmentIndexLength is the overhead for storing the index.
protected int _fragmentTotalLength
Fragment length in bytes
including the overhead for storing the index
after encoding.
protected boolean _verify
| Constructor Detail |
public Erasure(int size)
size - = size of msg in bytes.
public Erasure(int size,
int fragmentDataLength)
size - = size of msg in bytes.fragmentDataLength - = Fragment length (in bytes) of
each Fragment excluding the overhead for storing
the index.
public Erasure(int size,
int numFragments,
int inverseRate,
boolean verify,
NodeId node_id)
size - = size of msg in bytes.numFragments - = number of total Fragments desired.inverseRate - = inverse rate of encoding.| Method Detail |
protected static void instanciateRandom(int seed,
NodeId node_id)
instanciateRandom creates an instance of a
Random associated with NodeId and
instanciated with the seed.
seed - = seed to instanciate Random variable with.node_id - = NodeId to associate with
Random variable.protected static Random instanceRandom(NodeId node_id)
instanceRandom returns an instance of a
Random variable.
Random variable associated with
NodeId.protected static boolean instanceRandomContains(NodeId node_id)
instanceRandomContains returns true if map of instance
instance variables contains node_id, false otherwise.
node_id - = NodeId to test.
node_id, false otherwise.
public static Erasure getErasure(Erasure oldE,
int blockSize,
int numFragments,
int inverseRate,
int erasureType,
boolean verify,
NodeId node_id,
SecureHash guid)
getErasure creates and initializes a new
Erasure coder if the current passed in one is
null or does not support the correct
blockSize; otherwise, getErasure
will return the original Erasure coder unchanged.
oldE - current Erasure coder.blockSize - block size to be supported.numFragments - number of fragments to be produced per
blockSize.inverseRate - inverse rate of coding to use.erasureType - type of Erasure
coder to use.node_id - NodeId of local machine
conducting fragmentation process.guid - GUID of local machine
conducting fragmentation process.
Erasure coder which supports blockSize.
public static int getBlockSize(int blockSize,
int numFragments,
int inverseRate,
int type)
getBlockSize computes the block size corresponding
to the input blocksize, numFragments, inverseRate, and erasureType.
blockSize - Size of block in bytes.numFragments - Total number of fragments for block.inverseRate - InverseRate of encoding.type - Type of erasure coding.
public abstract void encode(byte[] byteMsg,
int[] msg,
int[] intFrags,
Stats stat)
throws ErasureEncodeException
encode encodes a object
using an erasure code.
byteMsg - = original msg before encoding (in array of byte form).msg - = original msg before encoding (in array of int form).stat - = a Stats object which contains the time to encode object
in milliseconds.
intFrags from encoding
msg (in an array of int form).
ErasureEncodeException
public abstract void decode(int[] rec_pckts,
int Nrec,
int[] rec_message,
byte[] data,
Stats procTime)
throws ErasureDecodeException
decode decodes an object
using an erasure code.
rec_pckts - = Fragments (in int array form) to be
decoded back into a msg.Nrec - = number of Fragments received.procTime - = time to encode object in milliseconds.
ErasureDecodeExceptionpublic abstract int getFragmentArrayLength()
getFragmentArrayLength returns the length of the
Fragment array divisible by sizeOfLong.
Fragment array divisible by
sizeOfLong.public abstract int getMsgArrayLength()
getMsgArrayLength returns the length of the msg
array divisible by sizeOfLong.
sizeOfLong.
public boolean compareMsg(int[] orig_msg,
int[] rec_msg,
int size)
compareMsg compares the original msg with the
encoded/decoded message.
orig_msg - = original msg before encoding.rec_msg - = received msg after reception and decoding.size - = size of the original msg
public int loseFragments(int[] fragments,
int[] rec_fragments,
double keepRate,
int[] pNrec)
loseFragments decide which Fragments to
keep randomly.
fragments - = original msg before encoding.rec_fragments - = received msg after reception and decoding.keepRate - = percentage of Fragments to keep
after reception.pNrec - = number of received Fragments, this is
returned.
Fragments.public int[] getMsg(int len)
getMsg initializes array message with a fake message
(string of bytes) up to len bytes long.
len - = length of message (in bytes) to create.
public int getSize()
getSize returns the size of the msg that can be encoded.
public abstract int getEncodeType()
getEncodeType returns the encode type of this Erasure coder.
public abstract int getBlockSize(int blockSize,
int numFragments,
int inverseRate)
getBlockSize returns the message size corresponding to the
input blockSize, numFragments, and
inverseRate.
blockSize - = target blockSize (this is the size in bytes of the
data to be encoded).numFragments - = total number of fragments to encode
data.inverseRate - = inverse rate of encoding to encode data.
blockSize, numFragments, and
inverseRate.public abstract int getNumFragments()
numFragments returns the number of
Fragments after encoding (without loss of
Fragments).
Fragments.public abstract int numMessageFragments()
numMessageFragments returns the number of number of messge
Fragments. This number is m from class
description.
Fragments.public abstract int numRedundantFragments()
numRedundantFragments returns the redundant number of
Fragments. This number is n - m from
the class description.
Fragments.public abstract int fragmentDataLength()
fragmentDataLength is the Fragment length in
bytes of each Fragment excluding the overhead for storing the
index. This number is strictly dataLength/
Fragment in bytes.public abstract int fragmentIndexLength()
fragmentIndexLength is the overhead for storing the index
in bytes
- Returns:
- length of index for each
Fragment in bytes.
public abstract int fragmentTotalLength()
fragmentTotalLength is the Fragment length in bytes
including the overhead for storing the index after encoding. This
number is
dataLength/indexLength in
bytes.
Fragment in bytes.public int getInverseRate()
getOmverseRate returns the inverse rate of encoding.
|
|||||||||||
| PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||||
| SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD | ||||||||||