Package it.unimi.di.law.bubing.util

Class ByteArrayDiskQueues

java.lang.Object

it.unimi.di.law.bubing.util.ByteArrayDiskQueues

All Implemented Interfaces:

Size64, java.io.Closeable, java.lang.AutoCloseable

public class ByteArrayDiskQueues
extends java.lang.Object
implements java.io.Closeable, Size64

A set of memory-mapped queues of byte arrays.

An instance of this class handles a database of FIFO queues. Each queue is associated with a key (which is looked up by reference, for efficiency). Users can enqueue and dequeue elements associated with a key in FIFO order. It is also possible to remove all elements associated with a key.

The ratio between the used and allocated space can be checked periodically, and the method collect(double) can be used to compact elements until a target ratio is reached.

Note that the metadata associated with all queues must fit into memory. The caching of the content of the log files is performed at the operating system level by the memory-mapping system, however, and does not use the Java heap.

Internals

Queues are stored using a set of memory-mapped append-only log files. When garbage collection frees completely a file, it is deleted. Each element contains a pointer to the position of the next element.

Garbage collection is performed without keeping track of the free space beforehand. Keys are kept in a queue prioritized by the pointer to the last element of the associated FIFO queue that has been read (initially, the first element). As we advance each pointer, we discover free space and we compact the structure.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static class	ByteArrayDiskQueues.QueueData	Metadata associated with a queue.

Field Summary

Fields

Modifier and Type	Field	Description
long	allocated	The overall number of bytes allocated (a multiple of logFileSize).
long	appendPointer	The current pointer at which new elements can be appended.
ObjectArrayList<java.nio.ByteBuffer>	buffers	For each log-file index, the associated ByteBuffer.
static int	DEFAULT_LOG2_LOG_FILE_SIZE	By default, we use 64 MiB log files.
ObjectArrayList<java.io.RandomAccessFile>	files	For each log-file index, the associated RandomAccessFile.
Reference2ObjectOpenHashMap<java.lang.Object,ByteArrayDiskQueues.QueueData>	key2QueueData	For each key, the associated ByteArrayDiskQueues.QueueData.
protected int	log2LogFileSize	The base 2 logarithm of the byte size of a log file.
protected int	logFilePositionMask	The mask to extract the position inside a log file from a pointer.
protected int	logFileSize	The byte size of a log file.
long	size	The overall number of elements in the queues.
long	used	The overall number of bytes used by elements in the queues.

Constructor Summary

Constructors

Constructor	Description
ByteArrayDiskQueues(java.io.File dir)	Creates a set of byte-array disk queues in the given directory using log files of size 226.
ByteArrayDiskQueues(java.io.File dir, int log2LogFileSize)	Creates a set of byte-array disk queues in the given directory using the specified file size.

Method Summary

Modifier and Type	Method	Description
void	close()	Closes all files.
void	collect(double targetRatio)	Performs garbage collection until ratio() is greater than the specified target ratio.
long	count(java.lang.Object key)	Returns the number of elements associated with the given key.
protected int	decodeInt()	Decodes using vByte a nonnegative integer at the current pointer.
byte[]	dequeue(java.lang.Object key)	Dequeues the first element available for a given key.
protected int	encodeInt(int value)	Encodes using vByte a nonnegative integer at the current pointer.
void	enqueue(java.lang.Object key, byte[] array)	Enqueues an element (specified as a byte array) associated with a given key.
void	enqueue(java.lang.Object key, byte[] array, int offset, int length)	Enqueues an element (specified as a byte-array fragment) associated with a given key.
int	numKeys()	Returns the number of keys.
long	pointer()	Returns the current pointer.
void	pointer(long pointer)	Sets the current pointer.
double	ratio()
protected int	read()	Reads a byte at the current pointer.
protected void	read(byte[] b, int offset, int length)	Reads a specified number of bytes at the current pointer.
protected long	readLong()	Reads a long at the current pointer.
void	remove(java.lang.Object key)	Remove all elements associated with a given key.
int	size()	Deprecated.
long	size64()	Returns the overall number of elements in the queues.
protected void	write(byte b)	Writes a byte at the current pointer.
protected void	write(byte[] b, int offset, int length)	Writes a specified number of bytes at the current pointer.
protected void	writeLong(long l)	Writes a long at the current pointer.

Methods inherited from class java.lang.Object

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

Field Detail

DEFAULT_LOG2_LOG_FILE_SIZE

public static final int DEFAULT_LOG2_LOG_FILE_SIZE

By default, we use 64 MiB log files.

See Also:

Constant Field Values

log2LogFileSize

protected final int log2LogFileSize

The base 2 logarithm of the byte size of a log file.

logFileSize

protected final int logFileSize

The byte size of a log file.

logFilePositionMask

protected final int logFilePositionMask

The mask to extract the position inside a log file from a pointer. A pointer is formed by a position in the lowest log2LogFileSize bits and a log-file index in the remainig upper bits.

key2QueueData

public final Reference2ObjectOpenHashMap<java.lang.Object,ByteArrayDiskQueues.QueueData> key2QueueData

For each key, the associated ByteArrayDiskQueues.QueueData. If a key is present, there is at least one associated element in the queue.

files

public final ObjectArrayList<java.io.RandomAccessFile> files

For each log-file index, the associated RandomAccessFile. An entry might be null if the log file has been deleted or it has not been opened yet.

buffers

public final ObjectArrayList<java.nio.ByteBuffer> buffers

For each log-file index, the associated ByteBuffer. An entry might be null if the log file has been deleted or it has not been opened yet.

size

public long size

The overall number of elements in the queues.

used

public long used

The overall number of bytes used by elements in the queues.

allocated

public long allocated

The overall number of bytes allocated (a multiple of logFileSize).

appendPointer

public long appendPointer

The current pointer at which new elements can be appended.

Constructor Detail

ByteArrayDiskQueues

public ByteArrayDiskQueues(java.io.File dir)

Creates a set of byte-array disk queues in the given directory using log files of size 2²⁶.

Parameters:

dir - a directory.

ByteArrayDiskQueues

public ByteArrayDiskQueues(java.io.File dir,
                           int log2LogFileSize)

Creates a set of byte-array disk queues in the given directory using the specified file size.

Parameters:

dir - a directory.

log2LogFileSize - the base-2 logarithm of the size of a log file.

Method Detail

enqueue

public void enqueue(java.lang.Object key,
                    byte[] array)
             throws java.io.FileNotFoundException,
                    java.io.IOException

Enqueues an element (specified as a byte array) associated with a given key.

The element is a sequence of bytes specified as an array fragment.

Parameters:

key - a key.

array - a byte array.

Throws:

java.io.FileNotFoundException

java.io.IOException

enqueue

public void enqueue(java.lang.Object key,
                    byte[] array,
                    int offset,
                    int length)
             throws java.io.FileNotFoundException,
                    java.io.IOException

Enqueues an element (specified as a byte-array fragment) associated with a given key.

Parameters:

key - a key.

array - a byte array.

offset - the first valid byte in array.

length - the number of valid elements in array.

Throws:

java.io.FileNotFoundException

java.io.IOException

dequeue

public byte[] dequeue(java.lang.Object key)
               throws java.io.IOException

Dequeues the first element available for a given key.

Parameters:

key - a key.

Returns:

the first element associated with key.

Throws:

java.io.IOException

remove

public void remove(java.lang.Object key)

Remove all elements associated with a given key.

Note that this is a constant-time operation that simply deletes the metadata associated with the specified key.

Parameters:

key - a key.

count

public long count(java.lang.Object key)

Returns the number of elements associated with the given key.

This method can be called by multiple threads.

Parameters:

key - a key.

Returns:

the number of elements currently associated with key.

numKeys

public int numKeys()

Returns the number of keys.

Returns:

the number of keys.

read

protected int read()
            throws java.io.IOException

Reads a byte at the current pointer.

Returns:

the byte at the current pointer.

Throws:

java.io.IOException

readLong

protected long readLong()
                 throws java.io.IOException

Reads a long at the current pointer.

Returns:

the long at the current pointer.

Throws:

java.io.IOException

read

protected void read(byte[] b,
                    int offset,
                    int length)
             throws java.io.IOException

Reads a specified number of bytes at the current pointer.

Parameters:

b - the buffer into which the data will be read.

offset - the start offset in array b at which the data will be written.

length - the number of bytes to read.

Throws:

java.io.IOException

write

protected void write(byte b)
              throws java.io.IOException

Writes a byte at the current pointer.

Parameters:

b - the byte to be written.

Throws:

java.io.IOException

writeLong

protected void writeLong(long l)
                  throws java.io.IOException

Writes a long at the current pointer.

Parameters:

l - the long to be written.

Throws:

java.io.IOException

write

protected void write(byte[] b,
                     int offset,
                     int length)
              throws java.io.IOException

Writes a specified number of bytes at the current pointer.

Parameters:

b - the data.

offset - the start offset in b.

length - the number of bytes to write.

Throws:

java.io.IOException

pointer

public long pointer()

Returns the current pointer.

Returns:

the current pointer.

pointer

public void pointer(long pointer)
             throws java.io.FileNotFoundException,
                    java.io.IOException

Sets the current pointer. The associated log file is opened if necessary.

Throws:

java.io.FileNotFoundException

java.io.IOException

ratio

public double ratio()

collect

public void collect(double targetRatio)
             throws java.io.IOException

Performs garbage collection until ratio() is greater than the specified target ratio.

Parameters:

targetRatio - a ratio() to reach.

Throws:

java.io.IOException

encodeInt

protected int encodeInt(int value)
                 throws java.io.IOException

Encodes using vByte a nonnegative integer at the current pointer.

Parameters:

value - a nonnegative integer.

Throws:

java.io.IOException

decodeInt

protected int decodeInt()
                 throws java.io.IOException

Decodes using vByte a nonnegative integer at the current pointer.

Returns:

a nonnegative integer decoded using vByte.

Throws:

java.io.IOException

size64

public long size64()

Returns the overall number of elements in the queues.

Specified by:

size64 in interface Size64

Returns:

the overall number of elements in the queues.

size

@Deprecated
public int size()

Deprecated.

Specified by:

size in interface Size64

close

public void close()
           throws java.io.IOException

Closes all files.

Specified by:

close in interface java.lang.AutoCloseable

Specified by:

close in interface java.io.Closeable

Throws:

java.io.IOException