Cryville Meta Database Framework Version 1

Introduction

Overtime, databases have been using tables to store data. The structures of the records, or the columns of a table, are predefined, which leads to good performance, but sometimes bad flexibility. CMDF is a database framework designed to focus more on flexibility, meanwhile without losing too much performance.

The main difference between CMDF and traditional database frameworks is the way how they store data. While traditional databases store data in tables, CMDF stores data in nodes and connect them with each other, forming a relational network. Compared to traditional database frameworks, CMDF should provide the following features:

• Fast relational lookup;
• Fast searching and sorting;
• Dynamic modification on data structures;
• Fast and flexible data exchange.

Main Database File Data Structure

The main database file contains all the records in the database. It is made up of a header and a data body. Although the database structure represents a network, it is still stored in a file or a number of files in linear form.

General Data Structures

There are a number of data structures commonly used across the database file.

String

A string is a sequence of characters encoded in UTF-8. Strings are serialized in three different forms: padded, zero-terminated, and sized. Padded strings are padded to the specified length with null control characters \0. Zero-terminated strings are terminated with a null control character \0, preventing applications from skipping the string. Sized strings are serialized with its length in bytes before it, allowing applications to skip over this string.

The length of a sized string is limited by the size of the length record.

string padded_str[7]       = "CMDF"; // Bytes:    43 4D 44 46 00 00 00
string zero_terminated_str = "CMDF"; // Bytes:    43 4D 44 46 00
string sized_str<0..2^8-1> = "CMDF"; // Bytes: 04 43 4D 44 46

Pointer

A pointer is an unsigned 64-bit integer pointing to an address in the file. A zero value indicates that the pointer is null.

When the main database is stored in a number of files, the significant bits of a pointer MAY be used to point to different files.

Timestamp

A timestamp is the time elapsed since the Unix epoch (00:00:00 UTC on 1970-01-01) excluding leap seconds in milliseconds. It is serialized as a 64-bit unsigned integer.

Tree pair

struct {
	pointer ptr_content_root;
	pointer ptr_revision_root;
} TreePair; /* 16 bytes */

The database file contains a number of AVL nodes making up AVL trees. AVL tree is a self-balancing binary search tree, enabling fast node searching, insertion, and deletion. Trees are paired as tree pairs, with one being the content tree and the other being the revision tree, both null pointers when initialized. The revision tree records the timestamps when the content nodes are inserted, moved, or deleted.

Header

struct {
	string   magic[4] = "CMDF"; /*   4 bytes */
	uint32   version  = 0;      /*   4 bytes */
	TreePair tp_obj;            /*  16 bytes */
	pointer  ptr_fc;            /*   8 bytes */
	byte     reserved[214];     /* 214 bytes */
	pointer  ptr_ext_header;    /*   8 bytes */
	byte     reserved;          /*   1 byte  */
	byte     flag     = 0xFF;   /*   1 byte  */
} HeaderBase; /* 256 bytes */

magic

A 4-byte magic word used to identify the file format.

version

CMDF version, currently 0 (Version 1).

tp_obj

The object tree pair.

ptr_fc

The free chunk tree.

reserved

A chunk reserved for possible use in the future. It pads the whole header up to 256 bytes.

ptr_ext_header

A pointer reserved for possible use in the future, in case the reserved chunk is not sufficient for the header. SHOULD be null in the current version.

flag

A flag to distinguish the header from the nodes.

Body and Data

enum {
	is_free_chunk (0x01),
	(0xFF)
} NodeFlag;

struct {
	pointer   ptr_l;
	pointer   ptr_r;
	uint64    lh_weight;
	byte      height;
	NodeFlag  flag;
	timestamp rev;
	opaque    data;
	byte      padding_size;
	byte      padding[padding_size];
	NodeFlag  flag;
} Node; /* 36 bytes + sizeof(data) + padding_size */

ptr_l, ptr_r

The left/right child node.

lh_weight

The count of all descending nodes on the left. This is used to calculate the index of a node and the total node count in a tree.

height

The height of the sub-tree, excluding the node itself.

rev

Last revision timestamp of the node, when data is modified. It is also used to locate the RevisionData when the node is deleted. Nodes with FreeChunkData SHOULD have this field set to 0.

data

The data stored in this node.

padding

A field that pads the size of the ObjectData to the preferred size or to the whole span of the free chunk.

The preferred size of a node is the smallest multiple of 16 not less than the size of data plus 36 (in bytes.)

When writing a Node, it is RECOMMENDED to skip over the padding field without writing any data.

Revision data

struct {
	pointer ptr;
} RevisionData; /* 8 bytes */

ptr

(AVL key) The target.

Object data

struct {
	byte     id[16];
	TreePair tp_comps;
	TreePair tp_ents;
	TreePair tp_props;
	TreePair tp_vals;
	MetaName name;
} ObjectData; /* 80 bytes + sizeof(name) */

id

(AVL key) The ID of the object. The first 8 bytes (64 bits) represent an object identifier. The other 8 bytes represent an object discriminator.

Uncomparable objects are defined with the root object identifier as the object identifier and their representing object identifier as the object discriminator. The root object is defined with the root object identifier as both the root object identifier and the object discriminator.

The root object identifier is 00 00 00 00 00 00 00 00. Object identifiers for other uncomparable objects are the value of a counter which is initially 0 and increases every time before a new uncomparable object is added.

tp_comps

The components in LinkData of the object. The object inherits all properties from its components, and MUST be listed as an entity of all its components.

tp_ents

The entities in LinkData of the object. The entities of an object inherits all properties from the object. The object MUST be listed as a component of all its entities.

tp_props

The property definitions in LinkData of the object. The object that a property points to MUST have a property points back. For example, if object A has object B as one of its properties, then object B must have object A as one of its properties as well.

tp_vals

The property key value pairs in PropertyData of the object. The object MUST have all of its property keys defined in tp_props of its components. The object that a property value points to MUST have a property value points back. For example, if object A with component B has a property key C set to value D, object D must have a component C and a property key B set to value A.

name

The meta name of the object.

Meta name is a list of name parts describing the name of the object. A name part contains a name string, with the information of its language.

Meta name is designed to eliminate the problem of multiple languages in a single name. Meanwhile it gives the database potential to store or automatically generate different aliases and transcriptions of an object, thus later the object can be looked up faster and more conveniently.

struct {
	MetaNamePart name_part[1..2^8-1];
} MetaName;

struct {
	string language;
	string name;
} MetaNamePart;

language

The language of the name part.

This field consists of at least two subtags in lowercase letters, separated by hyphens -. The first subtag is an ISO 639-3 code indicating language. The second one is an ISO 15924 code indicating script. The third and the fourth one, both optional, are an ISO 3166-1 alpha-2 code and an ISO 3166-2 code respectively indicating region.

For those pairs of equivalent codes in ISO 3166-1 alpha-2 and ISO 3166-2, the one in ISO 3166-1 alpha-2 is used. See Appendix A for these pairs of equivalents.

name

The name.

meta_name: [
	("jpn-jpan","\x8679\x8272")
	("eng-latn","Passions")
	("jpn-jpan","\xFF01")
]
meta_name: [("eng-latn-gb","colour")]
meta_name: [("eng-latn-us","color")]
meta_name: [("jpn-jpan","\x7A7A")]
meta_name: [("zho-hans","\x7A7A")]
meta_name: [("zho-hant","\x7A7A")]

Property Data

Property data store the property of the object in key value pairs.

struct {
	pointer ptr_key;
	pointer ptr_value;
} PropertyData; /* 16 bytes */

ptr_key

(AVL main key) The key object.

ptr_value

(AVL sub key) The value object.

Link data

struct {
	pointer ptr;
} LinkData; /* 8 bytes */

ptr

(AVL key) The target.

Free chunk data

struct {
	uint32 size;
	byte   discard[size];
	uint32 size;
} FreeChunkData; /* 8 bytes + sizeof(discard) */

size

(AVL main key) The size of the free chunk.

The AVL sub key is the start position of this node. The flag of the node is marked is_free_chunk.

There MUST be at least one node in the free chunk tree, which is the never used chunk located after all the existing nodes. Its size MUST be the maximum value of uint32. This node MUST only have the first size field with the other two fields absent.

The size of a node with FreeChunkData MUST span over the whole free chunk. It is only padded with the discard field and the size of the padding field MUST be 0.

When writing FreeChunkData, it is RECOMMENDED to skip over the discard field without writing any data.

Operations

In CMDF, an operation refers to an action or a series of actions that write the database file. An operation functions as a whole. If an operation can be broken down into sub-actions, the sub-actions do not function individually and MUST function with the operation.

A recovery file is used to protect write operations. A flag in the recovery file indicates if the database is writing data to the database file. While preforming write operations, the original bytes that would be overwritten later as well as their spans are first copied to the recovery file. The flag is then set to true. Next, the database starts to copy new data to the database file. After it is finished, the flag is reset to false.

Upon startup, the database checks if the flag in the recovery file is true, which indicates an interruption during a write operation. The database can then recover the original data from the recovery file. After recovery is done, the flag is reset to false.

All the data MUST be flushed or have been flushed into the file immediately after the flag is toggled.

Create database

The free chunk tree is created with the only essential node upon the creation of a database. The object tree pair stays null.

Subaction: Insert new node into a tree

When inserting a new node into a tree, the preferred size of the node is computed and the smallest free chunk whose size is not less than the preferred size is found. Then the node is inserted in this chunk and the free chunk is removed from the free chunk tree. If the difference between the preferred size and the size of the free chunk is not less than 44 bytes, the leftover free chunk is reinserted into the free chunk tree. If the difference is less than 44 bytes, the discard field of the node is used to pad the node over the whole free chunk.

If the free chunk found is the last free chunk, and the database file has no more sufficient space for the preferred size, the file is resized or a new database file is created to extend the storage.

Insert new node into a tree pair

When inserting a new node into a tree pair, a Node with specific data is created and inserted into the content tree of the tree pair. Meanwhile a Node with RevisionData is created with the current timestamp and inserted into the revision tree of the tree pair. If the tree pair is in the data of another node, the rev field of that node is set to the same timestamp as well.

If a node with the same AVL key has already existed, the operation fails.

Insert object

The id and the name is determined when the object is inserted and MUST NOT be modified. The four TreePairs are null pointers.

Delete node

When deleting a node, the node is not actually removed from the database file, but its flag is set to deleted.

Queries