com.bigdata.rwstore

Class FixedAllocator

java.lang.Object

com.bigdata.rwstore.FixedAllocator

All Implemented Interfaces:

Allocator, Comparable

public class FixedAllocator
extends Object
implements Allocator

FixedAllocator Maintains List of AllocBlock(s)

Method Summary

Methods

Modifier and Type	Method and Description
void	abortAllocationContext(IAllocationContext context, RWWriteCacheService writeCacheService) Unwinds the allocations made within the context and clears the write cache of any associated data
void	addAddresses(ArrayList addrs)
boolean	addressInRange(int addr)
void	addToRegionMap(HashMap<Integer,FixedAllocator> map)
int	alloc(RWStore store, int size, IAllocationContext context) The introduction of IAllocationContexts has added some complexity to the older concept of a free list.
void	appendShortStats(StringBuilder str, RWStore.AllocationStats[] stats)
static int	calcBitSize(boolean optDensity, int alloc, int minReserve, int modAllocation) This determines the size of the reservation required in terms of the number of ints each holding bits for 32 slots.
boolean	canImmediatelyFree(int addr, int size, IAllocationContext context) If the context is this allocators context AND it is not in the commit bits then we can immediately free.
int	compareTo(Object o)
void	computeDigest(Object snapshot, MessageDigest digest) Add the committed allocated slot contents to the digest FIXME: First version is correct rather than optimal, need to consider if there is any benefit to
boolean	equals(Object o)
boolean	free(int addr, int size)
boolean	free(int addr, int size, boolean overideSession) Need to check if address to be freed was 'live' for any shadowed allocator to determine if we need to adjust the 'savedLive' data.
int	getAllocatedBlocks()
long	getAllocatedSlots() Computes the amount of storage allocated using the freeBits count.
protected AllocBlock	getBlockFromLocalOffset(int offset)
int	getBlockSize()
int	getDiskAddr() Return the bit in metabits for the last persisted version of this allocator.
long	getFileStorage()
int	getIndex()
long	getPhysicalAddress(int offset)
long	getPhysicalAddress(int offset, boolean nocheck) Return the byte offset on the file corresponding to a bit index into this FixedAllocator.
int	getPhysicalSize(int offset)
int	getRawStartAddr() returns the raw start address
int	getSlotSize()
long	getStartAddr()
String	getStats(AtomicLong counter)
String	getSummaryStats()
protected int	grabAllocation(RWStore store, int blockSize)
boolean	hasFree()
boolean	isAllocated(int offset)
boolean	isCommitted(int offset)
void	postCommit() Update the historical commit bits only once confirmed
void	read(DataInputStream str)
int	removeFreedWrites(FixedAllocator xfa, ConcurrentWeakValueCache<Long,ICommitter> externalCache)
void	setAllocationContext(IAllocationContext context)
void	setBucketStats(StorageStats.Bucket b)
void	setDiskAddr(int addr) Set the bit in metabits for this allocator.
void	setFreeList(ArrayList list)
void	setFreeList(ArrayList list, boolean force) The force parameter is set to true when the allocator is being moved from one free list to another.
void	setIndex(int index)
boolean	verify(int addr)
boolean	verifyAllocatedAddress(long addr) Determines if the provided physical address is within an allocated slot
byte[]	write() write called on commit, so this is the point when "transient frees" - the freeing of previously committed memory can be made available since we are creating a new commit point - the condition being that m_freeBits was zero and m_freeTransients not.

Methods inherited from class java.lang.Object

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

Method Detail

setIndex

public void setIndex(int index)

Specified by:

setIndex in interface Allocator

getStartAddr

public long getStartAddr()

Specified by:

getStartAddr in interface Allocator

compareTo

public int compareTo(Object o)

Specified by:

compareTo in interface Comparable

equals

public boolean equals(Object o)

Overrides:

equals in class Object

getDiskAddr

public int getDiskAddr()

Return the bit in metabits for the last persisted version of this allocator. This bit can be translated into the actual byte offset on the file by RWStore.metaBit2Addr(int).

Specified by:

getDiskAddr in interface Allocator

setDiskAddr

public void setDiskAddr(int addr)

Set the bit in metabits for this allocator.

Specified by:

setDiskAddr in interface Allocator

Parameters:

addr - A bit obtained from RWStore.metaAlloc().

getPhysicalAddress

public long getPhysicalAddress(int offset,
                      boolean nocheck)

Return the byte offset on the file corresponding to a bit index into this FixedAllocator.

The tweak of 3 to the offset is to ensure 1, that no address is zero and 2 to enable the values 1 & 2 to be special cased (this aspect is now historical).

Parameters:

offset - The bit index into the FixedAllocator.

Returns:

The byte offset on the backing file.

getPhysicalSize

public int getPhysicalSize(int offset)

Specified by:

getPhysicalSize in interface Allocator

getBlockSize

public int getBlockSize()

Specified by:

getBlockSize in interface Allocator

setFreeList

public void setFreeList(ArrayList list)

Specified by:

setFreeList in interface Allocator

setFreeList

public void setFreeList(ArrayList list,
               boolean force)

The force parameter is set to true when the allocator is being moved from one free list to another.

setAllocationContext

public void setAllocationContext(IAllocationContext context)

abortAllocationContext

public void abortAllocationContext(IAllocationContext context,
                          RWWriteCacheService writeCacheService)

Unwinds the allocations made within the context and clears the write cache of any associated data

Parameters:

writeCacheService -

write

public byte[] write()

write called on commit, so this is the point when "transient frees" - the freeing of previously committed memory can be made available since we are creating a new commit point - the condition being that m_freeBits was zero and m_freeTransients not.

Specified by:

write in interface Allocator

read

public void read(DataInputStream str)

Specified by:

read in interface Allocator

calcBitSize

public static int calcBitSize(boolean optDensity,
              int alloc,
              int minReserve,
              int modAllocation)

This determines the size of the reservation required in terms of the number of ints each holding bits for 32 slots. The minimum return value will be 1, for a single int holiding 32 bits. The maximum value will be the number of ints required to fill the minimum reservation. The minimum reservation will be some multiple of the address multiplier that allows alloction blocks to address large addresses with an INT32. For example, by setting a minimum reservation at 128K, the allocation blocks INT32 start address may be multiplied by 128K to provide a physical address. The minReserve must be a power of 2, eg 1K, 2k or 4K.. etc A standard minReserve of 16K is plenty big enough, enabling 32TB of addressable store. The logical maximum used store is calculated as the maximum fixed allocation size * MAX_INT. So a store with a maximum fixed slot size of 4K could only allocated 8TB. Since the allocation size must be MOD 0 the minReserve, the lower the minReserve the smaller the allocation may be required for larger slot sizes. Another consideration is file locality. In this case the emphasis is on larger contiguous areas to improve the likely locality of allocations made by a FixedAllocator. Here the addressability implied by the reserve is not an issue, and larger reserves are chosen to improve locality. The downside is a potential for more wasted space, but this reduces as the store size grows and in large stores (> 10GB) becomes insignificant. Therefore, if a FixedAllocator is to be used in a large store and locality needs to be optimised for SATA disk access then the minReserve should be high = say 128K, while if the allocator is tuned to ByteBuffer allocation, a minallocation of 8 to 16K is more suitable. A final consideration is allocator reference efficiency in the sense to maximise the amount of allocations that can be made. By this I mean just how close we can get to MAX_INT allocations. For example, if we allow for upto 8192 allocations from a single allocator, but in practice average closer to 4096 then the maximum number of allocations comes down from MAX_INT to MAX_INT/2. This is also a consideration when considering max fixed allocator size, since if we require a large number of Blobs this reduces the amount of "virtual" allocations by at least a factro of three for each blob (at least 2 fixed allocations for content and 1 more for the header). A variation on the current Blob implementation could include the header in the first allocation, thus reducing the minimum Blob allocations from 3 to 2, but the point still holds that too small a max fixed allocation could dramatically reduce the number of allocations that could be made.

Parameters:

alloc - the slot size to be managed

minReserve - the minimum reservation in bytes

Returns:

the size of the int array

getStats

public String getStats(AtomicLong counter)

Specified by:

getStats in interface Allocator

getSummaryStats

public String getSummaryStats()

verify

public boolean verify(int addr)

Specified by:

verify in interface Allocator

addressInRange

public boolean addressInRange(int addr)

Specified by:

addressInRange in interface Allocator

free

public boolean free(int addr,
           int size)

Specified by:

free in interface Allocator

free

public boolean free(int addr,
           int size,
           boolean overideSession)

Need to check if address to be freed was 'live' for any shadowed allocator to determine if we need to adjust the 'savedLive' data. This is critical since otherwise we will not be able to reset any unisolated alloc/frees.

alloc

public int alloc(RWStore store,
        int size,
        IAllocationContext context)

The introduction of IAllocationContexts has added some complexity to the older concept of a free list. With AllocationContexts it is possibly for allocator to have free space available but this being restricted to a specific AllocationContext.

In addition to the standard free allocation search we want to add a "density" restriction for small slots to encourage the aggregation of writes (by increasing the likelihood of sibling slot allocation).

There is some "Do What I mean" complexity here, with difficulty in determining a good rule to identify an initial allocation point. There is a danger of significantly reducing the allocation efficiency of short transactions if we too naively check committed bit density. We should only do this when identifying the initial allocation, and when the allocIndex is incremented.

Specified by:

alloc in interface Allocator

grabAllocation

protected int grabAllocation(RWStore store,
                 int blockSize)

hasFree

public boolean hasFree()

Specified by:

hasFree in interface Allocator

addAddresses

public void addAddresses(ArrayList addrs)

Specified by:

addAddresses in interface Allocator

getRawStartAddr

public int getRawStartAddr()

returns the raw start address

Specified by:

getRawStartAddr in interface Allocator

getIndex

public int getIndex()

Specified by:

getIndex in interface Allocator

appendShortStats

public void appendShortStats(StringBuilder str,
                    RWStore.AllocationStats[] stats)

Specified by:

appendShortStats in interface Allocator

getAllocatedBlocks

public int getAllocatedBlocks()

getFileStorage

public long getFileStorage()

Returns:

the amount of heap storage assigned to this allocator over all reserved allocation blocks.

getAllocatedSlots

public long getAllocatedSlots()

Computes the amount of storage allocated using the freeBits count.

Returns:

the amount of storage to alloted slots in the allocation blocks

isAllocated

public boolean isAllocated(int offset)

Specified by:

isAllocated in interface Allocator

isCommitted

public boolean isCommitted(int offset)

getBlockFromLocalOffset

protected final AllocBlock getBlockFromLocalOffset(int offset)

canImmediatelyFree

public boolean canImmediatelyFree(int addr,
                         int size,
                         IAllocationContext context)

If the context is this allocators context AND it is not in the commit bits then we can immediately free.

Specified by:

canImmediatelyFree in interface Allocator

setBucketStats

public void setBucketStats(StorageStats.Bucket b)

getPhysicalAddress

public long getPhysicalAddress(int offset)

Specified by:

getPhysicalAddress in interface Allocator

getSlotSize

public int getSlotSize()

computeDigest

public void computeDigest(Object snapshot,
                 MessageDigest digest)

Add the committed allocated slot contents to the digest FIXME: First version is correct rather than optimal, need to consider if there is any benefit to

Parameters:

snapshot -

digest -

postCommit

public void postCommit()

Update the historical commit bits only once confirmed

removeFreedWrites

public int removeFreedWrites(FixedAllocator xfa,
                    ConcurrentWeakValueCache<Long,ICommitter> externalCache)

verifyAllocatedAddress

public boolean verifyAllocatedAddress(long addr)

Determines if the provided physical address is within an allocated slot

Parameters:

addr -

Returns:

addToRegionMap

public void addToRegionMap(HashMap<Integer,FixedAllocator> map)