Data Structures

To support the transport of messages from senders to receivers a number of data structures are required. These data structures need to conform to a number of design principles for the common transport path, exceptional cases can be afforded an exceptional path, e.g. large messages:

1. Copy-Free: The send and receive buffer is directly used.
2. Allocation-Free: The send and receive buffer is pre-allocated so that the transport path is free from the allocation or reclamation of memory.
3. Lock-Free: Lock-free techniques are employed to manage concurrent access.
4. Wait-Free: Concurrent algorithms will complete within a finite number of steps.
5. Persistent/Immutable: Message buffers for send and receive record immutable history to allow replay and resend semantics.
6. O(1) Cost: All operations are constant time regardless of buffer size, senders, receivers, contention, etc.

Source Archive

The source needs to be able to support the efficient retransmission of messages. Messages may need to be retransmitted to cope with loss or late joiners to a communications stream. Each archive represents a term in the communication history from the source.

 Source Archive - Memory Mapped File
+-------------------------------------------+---------------------+---------------+
|   Message buffer (64-byte aligned size)   | Index (msg offsets) | State Trailer |
+-------------------------------------------+---------------------+---------------+

Messages are stored to the buffer in preparation for transmission as a sequential stream on a FIFO basis. The next n bytes of the buffer are claimed by performing an atomic increment of the tail counter stored in the state trailer.

The producers of message call send(bytes) on a source object passing the bytes to be sent. The send call then follows the following algorithm:

1. IF message is bigger than transmission frame size THEN
   1. Send in chunks
2. END IF
3. WHILE next capacity claim < message size
   1. Mark claimed capacity with tombstone
   2. Move on to next term
4. END WHILE
5. Copy in message
6. Mark record in archive as complete

A transmission thread observes the send buffer and repeatedly performs the following algorithm:

1. Assign message sequence
2. Update index for message sequence offset
3. Send message on underlying network layer

Message Index

Each archive contains an index of messages that can be used for the fast lookup of messages from sequence numbers.

State Trailer