Overview

TytoDB is a high-performance, non-relational column-row database designed with a strong emphasis on ACID compliance. It excels in equality searches involving the primary key and is optimized for speed in database scans, as well as in insert and delete operations.

Containers

In TytoDB, data is stored in containers, which are files where the database data is stored. The disk layout of the containers involves three key components: the metadata layout, the row structure, and tombstones.

Metadata

Container files store metadata at the start of the file, organized as a tuple of two arrays:

• The first array is a string array storing column names.
• The second array is a byte array storing the type ID of each column.

When reading the metadata, the two arrays are interpreted by "matching" both arrays: the first column has the element zero as its name and the first element of the byte array as its type, and so on for the other columns.

Row Layout and Pattern

Rows are stored right after the metadata as an array of elements of the same size (determined by the type size). They are placed as elements in a sequential list (akin to a Vec or Array), which means that reads from the disk can be performed using a relative pointer (index of that pseudo-array).

Tombstones

After deleting a row, the space on the disk is filled with "full" bytes (0xFF, also represented as 255u8), marking that row as a tombstone. Afterwards, the pointer to that row is pushed into an in-memory BTreeSet, called the graveyard, so the space can be recycled later by having new data overwrite it. However, this does not guarantee that the space will be reused with every insert. When a row is inserted, it either gets the index at the end of the file if the graveyard is empty or pops a pointer from the structure. This pointer can be lost if the program rolls back or crashes. An operation called Vacuum is available to clean up the tombstones left behind.

Alba Types

Referring to data types, Alba types is the name given to all the individual types a column can have in the database (Alba was the name of the query language the database once had in its first versions). The table below shows all the types available to be used within the program and their properties.

Indexing

TytoDB performs its indexing with an on-disk hashmap, which stores two-item u64 tuples: the first 64-bit unsigned integer is the primary key (hashed using the ahash algorithm), and the second is the pointer to the row in the container. Indexing is used in most operations like insert, delete, edit, and search. It is employed during an insert to guarantee the uniqueness of a primary key (which is crucial for the indexing to keep working) and, for edit and delete operations, it can sometimes (depending on the query plan) be used to determine which rows must be affected by the operation.

Primary Keys

The primary key is always the first column of any container.

Operations

Create a Container

Creates a container using as arguments a tuple of arrays: the first one being a string array and the second one a byte array for generating the metadata. The last argument is a string that specifies the container name.

Create Row

Creates a row in a container using the following arguments: an array of strings, an array of values, and a string. The first and second arrays implement the row layout; it is not necessary to mention all the values of all columns to create a row. When not mentioned, the value's zero is assigned. This makes the explicit definition of primary keys desirable, although not required.

Edit Row

Makes a search in the specified container and edits the rows (edits go into the MVCC) returned by the search operation. This operation has four parameters: the first is an array of text which contains the names of the columns being edited, the second is the new values, the third is the name of the container that the operation will run on, and the last is a condition set for the search operation to filter the rows that match these conditions and edit only those rows.

Delete Row

Performs a search in the specified container and deletes the rows the search returns. It requires two arguments: the container name to specify where the operation will run, and the condition set for the search.

Delete Container

Deletes a container. It receives a container name as an argument.

Search

Uses the query_type internal function to determine what sort of search must be done based on the condition set; the possible sorts are either scans or indexed searches. An indexed search uses the index hashmap to get a row, while a scan searches the dataset, returning the results of the rows matching the conditions (all rows if no conditions are entered). The operation requires three arguments: the first one is a string array that determines what columns are going to be fetched, the second is a string (container name) that determines the container where the operation will be run.

Commit

The Commit operation flushes data from the MVCC to the container file. It first iterates through the MVCC, gathering the data within it and detecting what must be written. There is a flag on every element in the MVCC structure that determines whether it is a deletion or not. If it is a deletion, the operation will write into the file at the row location an array of "full" bytes (0xFF or 255u8) with the same size as the original data and remove entries from the index file with the same key as the deleted row. Insertions can be either an insertion or an edit (the process is very similar in practice). For insertions, the commit writes the serialized row at the location it must be at and inserts into the hashmap the pointer to that row using the primary key as the key. Edits are similar to insertions; the only difference is that before writing the index into the hashmap, it removes entries with the old primary key to avoid collisions of any sort.

Rollback

Clears the MVCC and graveyard, effectively discarding all pending changes and reverting the database to its state before the transaction began.

Vacuum

Vacuum is a function that, when called by the database, runs in a container and cleans the tombstones in its file. This execution starts by scanning the entire dataset and pushing a boolean value that indicates whether the row is or is not a tombstone into a bitmap. Afterwards, two variables are declared: the first one is "cursor" and the other "back-cursor"; the cursor starts with a value of zero, and the back-cursor starts at N-1, where N is the bitmap length (count of elements). A loop runs until cursor > back-cursor, increasing the cursor value by one until it finds a tombstone in the bitmap at the index the cursor holds. Then, the loop state changes, and it starts decreasing the value of back-cursor until it finds a non-tombstone. After finding both a tombstone and a non-tombstone, both values are pushed into a vector that stores tuples of numbers (cursor and back-cursor positions).

After the loop involving direct interaction with the variables cursor and back-cursor ends, a for loop starts iterating through the vector of tuples, making swaps in the disk and the bitmap. After each swap, the references in the index map are updated, followed by an fsync. Although this slows the process down, it ensures data safety since a crash or power outage during this operation could be catastrophic, especially while there is no backup system like the one commit has with the MVCC.

MVCC

MVCC (Multi-Version Concurrency Control) is a mutex-protected hashmap that every container has in memory. Insertions into this structure are done so that the Commit operation can flush the data changes from it to the container file. After every insertion into the MVCC, appends are made to the MVCC WAL (Write-Ahead Log), which gets an fsync after every append. Both the append and fsync are run asynchronously to avoid blocking the operation that performed the push.

Networking

The database is network-based and listens on a port on a host (configured in the configurations), using TCP to operate. It employs FalcoTCP to handle the low-level networking alongside the cryptography of data being transmitted and connections. When a client sends bytes to the server, it tries to interpret them, and that is how commands are submitted to TytoDB. To handle those "bytes" the database receives and interprets, a connection handler built on top of FalcoTCP must be used. That handler will use an API/UI (whichever method is chosen) to help generate the byte instructions.

Configurations

The configurations change the way the database does certain things. The configuration file is found in the database's directory ($HOME/TytoDB/), named settings.yaml, which contains several elements:

• min_columns: The minimum count of columns every container must have on creation (will not affect existing containers).
• max_columns: The maximum count of columns every container can have on creation (will not affect existing containers).
• ip: The host the database will listen to.
• port: The port on the host the database will be listening to.
• vacuum: The schedule of the "Vacuum" function.

Vacuum Scheduling

This setting in the YAML file is a list where every element is a string tuple. The first item is the container name (where the vacuum will happen), and the second is when the vacuum must happen, which can follow 4 different patterns:

• "X unit": Where X is a number and unit is a unit of time (available units: "seconds", "minutes", "hours", "years", or "decades"). When using this schedule pattern, the function will be run every X * unit. For example, if X is 10 and the unit is "years", then a vacuum will happen every 10 years.
• "HH:MM:SS": Schedules a vacuum to happen every day at the specified hour. For example, if set to "01:00:00", the database will run a vacuum every day at 1 AM.
• "MM/DD HH:MM:SS": Schedules a vacuum to happen every year at the specified month, day, and time of day. For example, if set to "01/01 01:00:00", the database will run a vacuum every year on January 1st at 1 AM.
• "once": Does not schedule a vacuum to happen repeatedly but runs a vacuum once on database startup.

General Example:

vacuum:
- ["users", "once"]
- ["logs", "12:00:00"]
- ["data", "5 minutes"]

Byte Instruction Protocol Specification

This document specifies the low-level binary protocol for TytoDB operations. It is derived directly from the serialization and deserialization logic in the Rust TytoDB Client source code (`commands.rs`, `types.rs`, `dynamic_int.rs`) and is intended for developers creating compatible connection handlers or alternative database implementations.