Tokyo Cabinet

Tokyo Cabinet is an [embedded](https://en.wikipedia.org/wiki/Embedded_database) [key-value store](https://en.wikipedia.org/wiki/Key-value_database) written in `C`, with native support for `C` and `C++` and wrapper APIs for other languages. Keys and values are `NULL`-terminated strings or arbitrary sequences of bytes and generally have variable size. Tokyo Cabinet is not a relational database management system; It is a dedicated key-value store similar to [LevelDB](https://en.wikipedia.org/wiki/LevelDB), [RocksDB](https://en.wikipedia.org/wiki/RocksDB), etc. An application uses a custom non-`SQL` API to invoke insert, delete, update operations on data and other management functions. Tokyo Cabinet supports concurrent access. It also implements a thin "table" abstraction which simulates columns over a key-value store and transactions with `ACID` properties and write-ahead logging. The key-value storage layer is built on top of three fundamental 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.

History

Tokyo Cabinet was developed in the late 2000s and improves upon older and simpler data storage libraries such as the Unix [`dbm`](https://en.wikipedia.org/wiki/Dbm) ("database manager") and the [GNU `GDBM`](https://www.gnu.org.ua/software/gdbm/) by providing a greater variety of backing data structures and additional API functions. Tokyo Cabinet is succeeded by a similar key-value store called [Kyoto Cabinet](https://dbdb.io/db/kyoto-cabinet).

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](https://en.wikipedia.org/wiki/Burrows–Wheeler_transform) or the [Lempel–Ziv](https://en.wikipedia.org/wiki/Lempel–Ziv–Welch) 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.

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](https://en.wikipedia.org/wiki/Embedded_database) [key-value store](https://en.wikipedia.org/wiki/Key-value_database). Applications directly invoke functions from a custom non-`SQL` API for performing insert, delete, update operations on data and other management tasks.

Tokyo Cabinet Logo
Website

http://fallabs.com/tokyocabinet/

Source Code

https://fallabs.com/tokyocabinet/

Tech Docs

https://fallabs.com/tokyocabinet/spex-en.html

Former Name

Sugamo Cabinet

Developer

FAL Labs

Country of Origin

JP

Start Year

2006

Project Type

Open Source

Written in

C

Supported languages

C, C++, Java, Lua, Perl, Ruby

Operating Systems

BSD, Linux, OS X, UnixWare

Licenses

LGPL v2

Wikipedia

https://en.wikipedia.org/wiki/Tokyo_Cabinet_and_Kyoto_Cabinet