ostore.archive
Class Fragment

java.lang.Object
  |
  +--ostore.archive.Fragment

All Implemented Interfaces:

Cacheable, Cloneable, Disseminatable, QuickSerializable, ostore.archive.repair.RepairStage.PersistantObject

public class Fragment

extends Object

implements Disseminatable

The Fragment class is a class to store Erasure encoded fragments.

Fragments are the main mechanism that provides durability in OceanStore. Each Fragment is self-verifying and the cornerstone of the archival layer's fault tolerance and automatic repair. A Fragment is produced from an Erasure coding process, where the Erasure code treats input data as a series of m Fragments, which it transforms into n Fragment, 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).

We append to the data portion of the Fragment object the fragment verification hashes (i.e. VHashTree and QSArray), the size of the original object, the encoding type (e.g. Cauchy, Interleaved, or Tornado), the number of total fragments, the inverse rate of encoding, and the index of particular fragment.

Version:

$Id: Fragment.java,v 1.29 2003/11/17 23:52:43 emilong Exp $

Author:

Hakim Weatherspoon

See Also:

Erasure, Cauchy, Interleaved, VHashTree, QSArray

Field Summary

static int	blockSizeOffset Offset of block_size in the _data field.
static int	dataOffset Offset of data in the _data field.
static int	encodeTypeOffset Offset for the type of encoding used to generate this fragment.
static int	indexOffset Offset of index in the _data field.
static int	inverseRateOffset Offset of rate of encoding in the _data field.
static int	numberOfFragmentsOffset Offset of number of fragments in the _data field.
static int	OVERHEAD Overhead storage requirement for a fragment (in bytes).

Constructor Summary

Fragment()
Default constructor: The Fragment has no data, and no verification info.

Fragment(byte[] header, int header_off, int header_len, int[] intData, int intData_off, int intData_len)
Constructor: FIXME: This comment needs filling in.

Fragment(Erasure e, int[] intFrags, int index, int blockSize)
Constructor: Initializes a Fragment with all of its data.

Fragment(InputBuffer buffer)
Constructs a Fragment from its serialized form.

Fragment(int size)
Constructor.

Method Summary

Object	clone() This is the clone routine for Disseminatable.
SecureHash	computeGuid() computeGuid Compute and return the guid of the disseminatable.
SecureHash	computeGuid(SecureHashBuffer buffer) computeGuid Compute and return the guid of the disseminatable.
static int	computeMemoryRequirement(int bSize, int numFrags, int inverseRate, int type) computMemoryRequirement computes the memory requirement for a single disseminatable.
int	getBlockSize() Gets the block_size of this Fragment.
SecureHash	getBlockVHash() Get the hash of the corresponding block in the verification information.
static Object	getBucket(Object key)
byte[]	getData() getData returns the Fragment in byte array form.
void	getData(byte[] data, int data_offset, int offset, int length) Gets a portion of this Fragment's data.
int	getDataLength() Calculates and returns the length of a fragment's data in bytes (not including the index), based on block_size, numFrags, and rate.
int	getEncodeType() Gets the encodeType.
SecureHash	getFHash() Get the hash of the corresponding to the top of the fragment vhash tree (hash adjacent to blockVHash.
int	getIndex() getIndex get the index of this object.
int	getInverseRate() Gets the rate field from this fragment.
int	getNumberOfFragments() Gets the number of fragments field from this Fragment.
SecureHash	getVerify(int index) Get one of the hashes in the verification information.
int	getVerifyLength() Return the length of the verification array.
static Object	putBucket(Object key, Object value)
int	putData(int[] buffer, int offset) putData copies this fragmet's index and data into the integer array.
void	serialize(OutputBuffer buffer) Specified by ostore.util.QuickSerializable
void	setBlockSize(int blockSize) Sets the block_size of this Fragment.
static void	setBlockSize(int blockSize, byte[] data) Sets the block_size of this Fragment.
void	setData(byte[] data, int data_offset, int offset, int length) Sets a portion of this Fragment's data.
void	setEncodeType(int encodeType) Sets the encodeType.
static void	setEncodeType(int encodeType, byte[] data) Sets the encodeType.
void	setFragmentMetadata(byte[] header, int offset, int length) Sets the index of this Fragment.
void	setIndex(int index) Sets the index of this Fragment.
static void	setIndex(int index, byte[] data) Sets the index of this Fragment.
void	setInverseRate(int inverseRate) Sets the rate field in this Fragment.
static void	setInverseRate(int inverseRate, byte[] data) Sets the rate field in this Fragment.
void	setNumberOfFragments(int numFrags) Sets the number of fragments field in this Fragment.
static void	setNumberOfFragments(int numFrags, byte[] data) Sets the number of fragments field in this Fragment.
void	setSize(int size) Sets the size of the data array, erasing all data.
void	setVerify(SecureHash hash, int index) Sets one of the hashes in the verification information.
void	setVerifySize(int size) Sets the size of the verification information (in other words, how many levels of the verification tree exist between this Fragment's hash and the top-most hash.
String	toString() Specified by java.lang.Object
boolean	verifyGuid(SecureHash other) verifyGuid returns whether disseminatable verified or not.
boolean	verifyGuid(SecureHash other, SecureHashBuffer buffer) verifyGuid returns whether disseminatable verified or not.

Methods inherited from class java.lang.Object

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

Field Detail

OVERHEAD

public static final int OVERHEAD

Overhead storage requirement for a fragment (in bytes). This has the following format:
4 bytes = block_size (size of the block which was encoded)
4 bytes = encoding type
4 bytes = number of fragments
4 bytes = inverse rate of encoding
4 bytes = index (index of this fragment)

See Also:

Constant Field Values

blockSizeOffset

public static int blockSizeOffset

Offset of block_size in the _data field.

encodeTypeOffset

public static int encodeTypeOffset

Offset for the type of encoding used to generate this fragment.

numberOfFragmentsOffset

public static int numberOfFragmentsOffset

Offset of number of fragments in the _data field.

inverseRateOffset

public static int inverseRateOffset

Offset of rate of encoding in the _data field.

indexOffset

public static int indexOffset

Offset of index in the _data field. NOTE-WARNING: indexOffset and dataOffset need to be next to each other always due to the fact the Fragment class is just a wrapper around a cauchy fragment from the cauchy class

dataOffset

public static int dataOffset

Offset of data in the _data field. NOTE-WARNING: indexOffset and dataOffset need to be next to each other always due to the fact the Fragment class is just a wrapper around a cauchy fragment from the cauchy class

Constructor Detail

Fragment

public Fragment()

Default constructor: The Fragment has no data, and no verification info. Initializes the array members of this class to be arrays of length 0.

Fragment

public Fragment(int size)

Constructor. Initializes the data in this Fragment to have the input size, leaving room for the block size and index. It initializes _verify of this object to be an array of length 0.

Parameters:

size - size of the data portion of a fragment (i.e. excludes fragment overhead.

Fragment

public Fragment(Erasure e,
                int[] intFrags,
                int index,
                int blockSize)

Constructor: Initializes a Fragment with all of its data. It converts a segment of an integer array into a Fragment.

Parameters:

e - Erasure object which created the fragments.

intFrags - integer representation of the fragments.

index - index of the Fragment to create.

Fragment

public Fragment(byte[] header,
                int header_off,
                int header_len,
                int[] intData,
                int intData_off,
                int intData_len)

Constructor: FIXME: This comment needs filling in.

Fragment

public Fragment(InputBuffer buffer)
         throws QSException

Constructs a Fragment from its serialized form.

Parameters:

buffer - serialized form of object.

Method Detail

computeMemoryRequirement

public static int computeMemoryRequirement(int bSize,
                                           int numFrags,
                                           int inverseRate,
                                           int type)

computMemoryRequirement computes the memory requirement for a single disseminatable.

Parameters:

bSize - size of block in bytes.

numFrags - total number of fragments for block.

inverseRate - inverseRate of encoding.

type - type of erasure coding.

Returns:

return the fragment size corresponding to the input parameters.

putBucket

public static Object putBucket(Object key,
                               Object value)

getBucket

public static Object getBucket(Object key)

getData

public byte[] getData()

getData returns the Fragment in byte array form.

Returns:

the Fragment in a byte array form.

verifyGuid

public boolean verifyGuid(SecureHash other)

Description copied from interface: Disseminatable

verifyGuid returns whether disseminatable verified or not.

Specified by:

verifyGuid in interface Disseminatable

Returns:

true iff this object self-verifies.

verifyGuid

public boolean verifyGuid(SecureHash other,
                          SecureHashBuffer buffer)

Description copied from interface: Disseminatable

verifyGuid returns whether disseminatable verified or not.

Specified by:

verifyGuid in interface Disseminatable

Returns:

true iff this object self-verifies.

computeGuid

public SecureHash computeGuid()

Description copied from interface: Disseminatable

computeGuid Compute and return the guid of the disseminatable.

Specified by:

computeGuid in interface Disseminatable

Returns:

the guid of the disseminatable.

computeGuid

public SecureHash computeGuid(SecureHashBuffer buffer)

Description copied from interface: Disseminatable

computeGuid Compute and return the guid of the disseminatable.

Specified by:

computeGuid in interface Disseminatable

Returns:

the guid of the disseminatable.

setVerifySize

public void setVerifySize(int size)

Sets the size of the verification information (in other words, how many levels of the verification tree exist between this Fragment's hash and the top-most hash.

setVerify

public void setVerify(SecureHash hash,
                      int index)

Sets one of the hashes in the verification information.

Parameters:

hash - hash to set.

index - index/position to set hash.

getVerify

public SecureHash getVerify(int index)

Get one of the hashes in the verification information.

Parameters:

index - index/position to get hash.

getVerifyLength

public int getVerifyLength()

Return the length of the verification array.

Returns:

verify hash array length.

getBlockVHash

public SecureHash getBlockVHash()

Get the hash of the corresponding block in the verification information.

Returns:

corresponding block vhash.

getFHash

public SecureHash getFHash()

Get the hash of the corresponding to the top of the fragment vhash tree (hash adjacent to blockVHash.

Returns:

corresponding to the top of the vhash tree.

setSize

public void setSize(int size)

Sets the size of the data array, erasing all data.

Parameters:

size - size of the data portion of a fragment (i.e. excludes fragment overhead.

setData

public void setData(byte[] data,
                    int data_offset,
                    int offset,
                    int length)

Sets a portion of this Fragment's data.

Parameters:

data - data to copy into data portion of fragment.

data_offset - offset of data being copied.

offset - offset of fragment data portion which to copy into.

length - length of data to copy.

getData

public void getData(byte[] data,
                    int data_offset,
                    int offset,
                    int length)

Gets a portion of this Fragment's data.

Parameters:

data - array where data portion of fragment will be copyied into.

data_offset - offset into array holding copied data.

offset - offset of fragment data portion which to start copying.

length - length of data to copy.

setBlockSize

public void setBlockSize(int blockSize)

Sets the block_size of this Fragment.

Parameters:

blockSize - size of block (in bytes).

setBlockSize

public static void setBlockSize(int blockSize,
                                byte[] data)

Sets the block_size of this Fragment.

Parameters:

blockSize - size of block (in bytes).

data - byte array to place blockSize into.

setEncodeType

public void setEncodeType(int encodeType)

Sets the encodeType.

Parameters:

encodeType - type of encoding.

setEncodeType

public static void setEncodeType(int encodeType,
                                 byte[] data)

Sets the encodeType.

Parameters:

encodeType - type of encoding.

data - byte array to place encodeType into.

setNumberOfFragments

public void setNumberOfFragments(int numFrags)

Sets the number of fragments field in this Fragment.

Parameters:

numFrags - total number of fragments.

setNumberOfFragments

public static void setNumberOfFragments(int numFrags,
                                        byte[] data)

Sets the number of fragments field in this Fragment.

Parameters:

numFrags - total number of fragments.

data - byte array to set numFrags into.

setInverseRate

public void setInverseRate(int inverseRate)

Sets the rate field in this Fragment.

Parameters:

inverseRate - inverse of the rate.

setInverseRate

public static void setInverseRate(int inverseRate,
                                  byte[] data)

Sets the rate field in this Fragment.

Parameters:

inverseRate - inverse of the rate.

data - byte array to set inverseRate into.

setIndex

public void setIndex(int index)

Sets the index of this Fragment.

Parameters:

index - index of fragment.

setIndex

public static void setIndex(int index,
                            byte[] data)

Sets the index of this Fragment.

Parameters:

index - index of fragment.

data - byte array to put index into.

setFragmentMetadata

public void setFragmentMetadata(byte[] header,
                                int offset,
                                int length)

Sets the index of this Fragment.

Parameters:

header - byte array representing Fragment metadata _EXCEPT_ index.

offset - position in byte array where header begins.

length - length of header. header length should _NOT_ include index of fragment.

getDataLength

public int getDataLength()

Calculates and returns the length of a fragment's data in bytes (not including the index), based on block_size, numFrags, and rate.

Returns:

length of data portion of fragment (i.e. excluding overHead.

getBlockSize

public int getBlockSize()

Gets the block_size of this Fragment.

Returns:

return == size of block.

getEncodeType

public int getEncodeType()

Gets the encodeType.

Returns:

type of encoding.

getNumberOfFragments

public int getNumberOfFragments()

Gets the number of fragments field from this Fragment.

Returns:

total number of fragments.

getInverseRate

public int getInverseRate()

Gets the rate field from this fragment.

Returns:

the inverse rate.

getIndex

public int getIndex()

Description copied from interface: Disseminatable

getIndex get the index of this object.

Specified by:

getIndex in interface Disseminatable

Returns:

return = index of this object.

putData

public int putData(int[] buffer,
                   int offset)

putData copies this fragmet's index and data into the integer array.

Parameters:

buffer - integer array to copy this Fragment's data into

offset - offset in the array to start copying.

Returns:

the number of integers copied into buffer

clone

public Object clone()
             throws CloneNotSupportedException

Description copied from interface: Disseminatable

This is the clone routine for Disseminatable. It deeply clones a disseminatable (meaning that it copies all of the data, not just references).

Specified by:

clone in interface Disseminatable

Overrides:

clone in class Object

Returns:

clone of Disseminatable.

CloneNotSupportedException

serialize

public void serialize(OutputBuffer buffer)

Specified by ostore.util.QuickSerializable

Specified by:

serialize in interface QuickSerializable

Parameters:

buffer - the output buffer to add the object to

toString

public String toString()

Specified by java.lang.Object

Overrides:

toString in class Object