Lozizol 0.5

Extensible and efficient serialization protocol.

Aiming at both wire and storage, multiplexed streams, concatenation, event sourcing...

Event sourcing? History is immutable and only it's interpretation may change between application versions. On the down side, the application needs to know how to interpret the records of all previous versions. On the up side, there is no need for migrations or data updates on application upgrade.

Definitions

• sequence - a Lozizol sequence of entries with properties:
  • id (uuid) - a UUID of the sequence.
  • version (semver2) - a Lozizol protocol version of "major.minor.patch" format.
• entry - an item of a sequence with following properties:
  • sequence - a reference to the containing Lozizol sequence
  • type - entry type that identifies the meaning of the entry
  • data - the binary data carried by the entry
• type - the meaning of the serialized entry data identified by a URI

These entry types are implied and default by Lozizol:

• Lozizol header (URI urn:lozizol:header) is an entry to be placed at the beginning of the sequence to convey Lozizol version, identifier and diagnostic information. it implies removal of all explicit entry type assignemnts. The implied type assignment is 111 (0x6F)
• Type assignment (URI urn:lozizol:type) is a reservation of a type number and assigned to a URI identifying the type of entry and perhaps providing detailed information. Empty URI indicates that a type assignment is removed from the sequence. The implied type assignment is 1
• Deleted entry (URI urn:lozizol:deleted) is an entry that should be considered removed form sequence. The fixed type assignment is 0

Other entry types are defined by applications with a URI and assigned in a Lozizol sequence using the type assignment entry. Type assignment can be assigned, reassigned or removed even in the middle of a Lozizol sequence. A type must be assigned or implied before it can be used in a Lozizol sequence.

The higher level implementations must work with the type URIs, rather than type IDs. As a result, one can assign the same type under multiple type IDs and they will all be treated equally.

Binary definitions

• byte: a sequence of 8 bits
• vuint: variable length encoded size (non-negative integer).
  • It is stored in a big endian byte order - the most significant byte first.
  • Bytes with the most significant bit set (1) indicate follow up byte.
  • A byte with the most significant bit unset (0) ends the binary representation.
  • To extract the integer value from the binary representation, concatenate the 7 lower bits from each byte. For example, representing a two byte integer value abcd efgh ijkl mnop in binary vuint becomes 1000 00ab 1cde fghi 0jkl mnop.
  • This scheme is essential to enable safe wiping of entries and padding handling.
  • Empty leading bytes (0x80) are invalid. Implementations must treat the sequence as corrupt on encountering this.
  • See also VLQ.
• uri: sequence of bytes representing a valid URI string per RFC 3986
• record: the binary representation of an entry:
  • size (vuint): the serialized type and data size (really - type vuint length included)
  • type (vuint): the entry type
  • data: binary representation of the entry according to type
• padding: all bytes in Lozizol sequence are either of records or padding. Since a record by definition must have at least two bytes (size and type), a null (0x00) byte outside of a record would become a record of zero length and no type and is therefore considered a single byte padding. Padding can be used to align records to a boundary or can be a result of wiping of deleted records.

The Vuint binary representation choice

• There are many schemes to represent integer values. Variable lenght was chosen to save space and to be flexible and future proof regarding uint size (8, 16, 32, 64, 128, ...).
• A scheme was chosen that is easy to reason about by humans. Individual bits are easy to correlate. Try lozizol serialize vuint 16777215 | xxd -b and comare that with echo -n -e '\xFF\xFF\xFF' | xxd -b. While this introduces some redundancy (vuint 0x8011 is the same as 0x11), it is for the benefit of humans and easier implementation. Other schemes subtract/add 1 in the process of encoding/decoding, but that means the 0s and 1s cannot be checked visually and it adds some computing overhead.
• Big endian was also chosen with humans comprehension and visual comparison in mind.
• A scheme similar to UTF-8 which puts all the marker 1s in the first byte is more efficient to compute, but would break the wiping/padding semantics. If the first byte was deleted and other's not, there would be no way to tell what the byte means. Spreading the marker bit is essential.

Lozizol header (111)

• "lozizol " marker of which
  • 'l' or 0x6C is also a vuint length 108, the full header size is thus 109 (1 + 108) bytes
  • 'o' or 0x6F is the predefined entry type 111
  • "zizol" is just a nice part of "lozizol"
  • " " is a space (0x20)
• "0.5": the current Lozizol semver2 version
• " ": a space again :)
• sequence identifier (UUID per RFC 4122 in string form - 36 bytes)
• " ": and one more space =D giving us three universes in total to start with
• remaining 60 bytes (109 - 1 - 1 - 5 - 1 - 3 - 1 - 36 - 1 = 60) of undefined data, which can be used by Lozizol writers to drop in some diagnostic information if desired, such as software and version. It should be ignored by readers or at best used for diagnostics and must not be used for any application data or logic. Such should be carried by other entries.

Since the Lozizol header would typically be the first record stored in a file, it allows for magic bytes based file type detection. It is deliberately human readable so that unsuspecting explorers can learn about the nature of the stored and/or transferred data.

Without the Lozizol header the implementation must either:

• assume the file is not a Lozizol sequence - consider it corrupt, or
• assure that it knows precisely which sequence (and state) it belongs to:
  • sequence (potentially nested)
  • starting position in the sequence
  • type definitions and context

Try

try_lozizol () {
  data="zizol 0.5 039343bb-9019-4d6e-825e-631aa578ff7f lozizol-cli 0.0.1-preview and what not ....................."
  lozizol serialize entry 111 "$data" | xxd
  # lozizol magic:
  lozizol serialize entry 111 "$data" | dd bs=1 count=109 status=none | cut -d ' ' -f1
  # lozizol version:
  lozizol serialize entry 111 "$data" | dd bs=1 count=109 status=none | cut -d ' ' -f2
  # sequence ID:
  lozizol serialize entry 111 "$data" | dd bs=1 count=109 status=none | cut -d ' ' -f3
  # diagnostic info:
  lozizol serialize entry 111 "$data" | dd bs=1 count=109 status=none | cut -d ' ' -f4-
}
try_lozizol

A Lozizol sequence is initialized with the header. The header sets the sequence id and protocol version. It resets all type assignments in the given sequence do default (unassign all and assign only the ones implied by lozizol).

Note: The Lozizol header type id 111 can be reassigned once the sequence is initialized.

Type assignment (1)

• size (vuint): the length of type + typeid + typeuri
• entry_type (vuint): type assignment entry type (0x01 by Lozizol default unless reassigned)
• assigned_type (vuint): new type assignment non-zero number
• uri (uri): a URI string of the type

Try

lozizol serialize vuint 63 | xxd # find that 63 serializes as 0x3F ('?')
lozizol serialize entry 1 "?urn:my-awesome-type" | xxd

or a specific shortcut

lozizol serialize type 1 63 urn:my-awesome-type | xxd

Note: The type assignment type id 1 can be reassigned.

Deleted entry (0)

• size (vuint): 1 + the size of the deleted data
• null (0x00): entry deleted entry type
• deleted / undefined data

Warning: The deletion type id 0 MUST NOT be reassigned as it would break the padding semantics.

Operations

The protocol anticipates aggressive forward only readers following a forward only writer to be the most common scenario. This fits for both file operations and network streaming. Fast seeking forward is supported by prefixing the entries with length.

Multiplexing or random write access can be accommodated too with some caution applied by the application. Lazy cleanup and indexing writes can take place without affecting integrity and reads. Indexing can be built on top of Lozizol to enable random read access.

Blocking

• Append-only writes need not be blocked as long as it is a single-threaded, single-task appender that is in charge of the appending. Concurrent appenders must be synchronized on record level.
• Reads need not be blocked by append-only writes other than waiting for more data.
• Random access writes
  • Reads/Writes positioned after the intended random access write modification need not be blocked.
  • Reads/Writes positioned before the intended random access write modification must be blocked or the application needs to block on record level.

Forward only reads and writes

Use case: all the data required to serialize the entry is available. In other words it will not block excessively by waiting for serialized data to manifest (IO or intense serialization).

Write

Examples:

• Recording a TCP stream, the writer only persists the immediately available buffer as is without much overhead for serialization.
• Recording a user action, all the data is available in memory and serialization is trivial.

The writer:

1. writes the entry type record if it hasn't been written to this Lozizol sequence yet,
2. writes the entry record - size, type, data,

Record is considered committed when all data according to size is written.

Read

The reader simply eagerly reads all available data. When it reaches the end of the record it produces the entry.

The reader:

1. reads vuint as long as the first bit is set, learning the size of the record,
2. reads entry type as long as the first bit is set, learning and using this information,
3. reads remaining data (size of the record - type vuint length) into a buffer,
4. produces the entry

Parallel approach is that the reader skips through the records by their length. actual record reading is delegated to asynchronous record readers by giving them the byte range to munch on.

Deletions

Use case: the application needs to mark an already written record as deleted.

The aplication should have its own semantics of labeling data structures redundant, such as adding an entry that an entity has been deleted, in the spirit of event sourcing. Still, for archiving/cleanup purposes, the application should be able mark a record as deleted. See also Wiping and Secure erasure.

The deleted entry type (0) is intended to be applied to already writen records to mark them as deleted. As long as the single byte write operation can be considered atomic, the deletion can be combined with reads and writes and is safe for the readers as the reader is either before the type ID and will see it as deleted, or is behind the type ID and will see the original record.

The data does not change, but with the entry type being reset, it is no longer possible to interpret it's meaning reliably. Readers should skip deleted records unless they are in the business of reclaiming unused space for compression or executing data erasure.

Deletion is a single byte write operation. To mark a record as deleted, put null (0x00) byte at the position immediately following the record length. If this operation cannot be executed in atomic fashion, deletions must block readers and random access writers on the given record to ensure consistency.

Wiping

Lozizol sequence can be compressed as a whole, like any other stream. A fitting optimization is to wipe all deleted records with null (0x00) bytes beforehand.

This can be done as a background job on a stored Lozizol sequence or passing through a wiping process.

The background wiping process:

1. asserts that random access reads and writes have been stopped where applicable (append only writes can continue),
2. locates the next deleted record,
3. writes null (0x00) bytes in place of type,
4. writes null (0x00) bytes in place of data,
5. writes null (0x00) bytes in place of size.

This will effectively create padding. It should be safe to fail at any moment.

The background wiping process can optionally optimize subsequent reads by creating deleted entry records to span the continuous blocks of padding.

The pass through (streaming) wiping process:

1. simply replaces all deleted records with null (0x00) bytes.

Secure erasure

Sensitive applications may require secure erasure of stored and deleted records. This can be accomplished similarly to the background wiping process except that before null (0x00) filling the data, the secure erasure process runs adequate measures to eliminate residual data traces from the storage media.

Random access writes

Before even considering random access asynchronous writes, think about your model. Can these writes be expressed as smaller entries written forward only? For example, rather than writing down the whole e-mail as it comes from the wire, which would beg an asynchronous write optimization, write each header block and each body block as a record tagged with the common mail ID and close with a terminating record (a.k.a. event sourcing).

Alternatively, simple parallelism can be achieved by partitioning the Lozizol sequences into multiple streams.

Still, there may be situations where asynchronous random access writes are desirable. For instance in case of UDP transfers, or intense serialization.

Use case: I really want to write asynchronously

There should be one authority over each Lozizol sequence that allocates records to be written. It will only write down the record length and type and hand over the byte range to an asynchronous writer. Immediately after that it can skip to the next available position and allocate the next record write request.

Since the integrity of the record cannot be asserted by reaching the end of data in this case, there must be a commit mechanism built into the application - either a hash as part of the record that will invalidate dirty reads or a separate commit record. Writing the commit record must block the authority. One simple commit mechanism would be to use one type for dirty records and another for fully written records. After writing, flushing, syncing, the writer would then update the record type. This is tricky because the type vuint length must not change. IDs of the same vuint length must be chosen.

For now it is left to the application do define suitable entry types and the rules for handling asynchronous writes with integrity guarantees.