Checkpoints

Not Supported

Checkpoints are not supported by Tokyo Cabinet.

Compression

Naïve (Page-Level) Naïve (Record-Level) Prefix Compression

A Tokyo Cabinet database file is not globally compressed. Compression is done at the record (key and value) level or the page level (for a B+ Tree-based store) using the Burrows–Wheeler transform or the Lempel–Ziv compression algorithm.

Concurrency Control

Not Supported

Tokyo Cabinet implements transactions with ACID properties. It supports serializable isolation for transactions using a global latch (only one transaction is active at a time). Therefore, Tokyo Cabinet does not support concurrent transactions.

Further, Tokyo Cabinet supports multiple threads or processes using the database file at a time using latching at different levels. At the highest level, processes or threads open the database file for reading or writing. There can be multiple concurrent readers. However, concurrent readers and writers are not allowed: whenever the database file is opened for writing, other writers and readers are blocked.

Data structures, including the fixed-size array and the hash table, in the storage layer are protected using fine-grained latching. The B+ tree implementation, however, does not support fine-grained latching: each process or thread acquires a global latch over the entire tree for operations on it.

Data Model

Key/Value

Tokyo Cabinet is not a relational database management system; It is a dedicated key-value store. Applications need to use a custom non-SQL API to invoke insert, delete, update operations on data and other management functions.

Tokyo Cabinet also implements a thin "table" abstraction which simulates columns over a key-value store. Schemas and data types are not supported, and therefore, a Tokyo Cabinet table can contain tuples with a different kind and number of columns. In the table abstraction, a key and a column index (a non-negative integer) together serve as a pointer to a value, unlike a standard key-value record, where only the key serves as such a pointer.

Foreign Keys

Not Supported

Foreign keys are not supported by Tokyo Cabinet.

Indexes

B+Tree Hash Table Inverted Index (Full Text)

Tokyo Cabinet's key-value store is built on top of three fundamental index data structures: (1) a static hash table with separate chaining (every bucket is a binary search tree), (2) a non-concurrent B+ tree, and, (3) a fixed-size array. Necessary data retrieval and management functions -- get, put, delete, update, range queries -- are supported by all three data structures, albeit with specific properties. Which data structure the database utilizes is configured through the initialization functions of the API.

Tokyo Cabinet implements a thin "table" abstraction which simulates columns over a key-value store. In this table abstraction, a key and a column index (a non-negative integer) together serve as a pointer to a value. Records in a table can have different schemas. The user can create indices (e.g., a B+ tree index) on any column, in which case any conditional queries on the column will be able to use the index for greater efficiency.

Indices of n-grams are also supported.

Isolation Levels

Serializable

Tokyo Cabinet implements transactions with ACID properties. It supports serializable isolation for transactions using a global latch (only one transaction is active at a time).

Joins

Not Supported

Joins are not supported by Tokyo Cabinet.

Logging

Shadow Paging

Tokyo Cabinet implements write-ahead logging for transactions using shadow paging. However, the data for all the operations performed in a single transaction — inserts, updates, etc. — should fit in memory.

Query Compilation

Not Supported

Tokyo Cabinet is not a relational database management system; It is a dedicated key-value store with a custom non-SQL API used by applications to invoke insert, delete, update operations on data and other management functions. The API functions for performing insert, delete, update operations on data are independent, and there is no optimization of the sequence of API calls, even in transactions. Each function is executed synchronously as soon as it is invoked, similar to a regular C or C++ function.

Query Execution

Tuple-at-a-Time Model

Tokyo Cabinet does not support intra-query parallelism since there are no operators. The API functions for performing insert, delete, update operations on data are independent and non-divisible, and there is no optimization of the sequence of API calls, even in transactions. For instance, the get or lookup operation in the API is executed synchronously as soon as it is invoked, similar to a normal C or C++ function, by using the available indices or by iterating over records in the database one by one.

Query Interface

Custom API

Tokyo Cabinet does not support SQL. Applications need to use a custom non-SQL API to invoke insert, delete, update operations on data and other management functions. In addition, Tokyo Cabinet supports repeatedly appending to a value, characterized as a "concatenate" operation.

Tokyo Cabinet has native support for C and C++ and wrapper APIs for other languages.

Storage Architecture

Disk-oriented

Tokyo Cabinet is a disk-oriented key-value store. The database is stored as a single, ordinary (non-sparse) file prefixed with a header section describing the layout and information in the file.

For hash table-backed and array-backed stores, Tokyo Cabinet uses mmap to map all hash table or array buckets into main memory. For B+ tree indices (implemented over the hash table-based store by keeping B+ tree pages in hash table buckets), the internal pages are small, and all are typically able to be cached in main memory. Tokyo Cabinet uses the LRU (least recently used) policy to evict items from its B+ tree page cache.

Storage Model

N-ary Storage Model (Row/Record)

Tokyo Cabinet implements a thin "table" abstraction which simulates columns over a key-value store. In this table abstraction, a key and a column index (a non-negative integer) together serve as a pointer to a value, unlike a standard key-value record, where only the key serves as such a pointer. All parts of a record (key and value, or key and column values) are stored together in a row-oriented manner.

Storage Organization

Heaps

Tokyo Cabinet is a disk-oriented key-value store and stores a database as a single, ordinary (non-sparse) file prefixed with a header section describing the layout and information in the file.

If the database is backed by a fixed-size array, the header section is followed by key-value records. For a hash table-based database, the header section is followed by hash table buckets which are, in turn, followed by a list of free "blocks". Tokyo Cabinet organizes memory into "blocks", contiguous regions of memory. It supports allocating (best-fit allocation) and deallocating blocks and coalescing free regions. For a B+ tree-based database, the storage organization is similar to when a hash table is used since B+ tree pages are stored inside hash table buckets.

Two primary modes of compaction are supported for the database: (i) dynamic (coalesce and lazily reuse free blocks), and, (ii) static (transfer all records from the original database file to a new database file, removing all unused blocks).

Stored Procedures

Not Supported

Stored procedures are not supported by Tokyo Cabinet.

System Architecture

Embedded

Tokyo Cabinet is an embedded key-value store. Applications directly invoke functions from a custom non-SQL API for performing insert, delete, update operations on data and other management tasks.

Views

Not Supported

Views are not supported by Tokyo Cabinet.