Kyoto Cabinet is a library of routines to manage a database. It is a multithreaded key-value embedded database manager, where key must be unique and both keys and values are simply composed of variable length bytes. Kyoto Cabinet is a representative successor of UNIX DBM with the claim of higher performance. The supported operations, including adding, deleting, querying and traversal, run fast with the speed of at most logarithmic to the scale of the database. The scalability is as well outstanding with the database size be up to 8EB. Kyoto Cabinet also has other highlights such as smaller database file size, various database manager implementations, great usability with object-oriented user API and high robustness.
Kyoto Cabinet is announced as the modern implementation of DBM library originally coined by AT&T in 1979. After the release of the original DBM library, similar DBM libraries were then written by different groups. In 2009, Kyoto Cabinet was developed by FAL Labs to be the successor of QDBM, one of the UNIX DBM-like products developed in 2003, for performance reason. The stable version (1.2.76) was released on December 2012, and the most recent release (1.2.77) was on October 2018.
The implementations based on hash table in Kyoto Cabinet uses MurMurHash 2.0, with collision managed by separate chaining implemented by binary search tree. The B+ tree implementation is based on the hash table, but it also maintains an additional B+ tree with pages linked in a doubly-linked list.
Custom API Command-line / Shell
Kyoto Cabinet supports direct shell commands. For example, if we intend to create an example database using trivial hash table implementations, we could type kchashmgr create test.kch
. To add, delete and retrieve some records from the database, we can type kchashmgr set test.kch key value
, kchashmgr get test.kch key
, kchashmgr remove test.kch key
. \
Kyoto Cabinet also supports API in multiple programming languages. For example, in object-oriented programming languages, there is a class called HashDB
. Each time we instantiate a HashDB
instance called hashDb
, and connect to it either in reader mode or in writer mode through hashDb.open(...)
. It supports adding, retrieval, remove and traversal by using hashDb.set(...)
, hashDb.get(...)
, hashDb.remove()
and allocating a cursor.
The connections to the database are in either reader mode or writer mode. Readers can only retrieve records, while writers can call all the methods. If a reader process has connected to the database, only other reader processes can connect to the database. However, writer processes have the exclusive access to the database, thus no later processes will be granted the access. There is no concurrency control since database has different permissions for different connection modes and the concurrency is done in the process level.
The default compression encoding is method is ZLIB Deflate because the records in the same page share similar patterns. There are configuration commands that could disable Deflate and enable other compression encodings such as LZO or LZMA. All the compression encodings here are of lossless dictionary type.
Some of the DBM routines in the Kyoto Cabinet aim at primarily relying on memory for storage, including ProtoDB, StashDB, CacheDB and GrassDB. Others mainly rely on disk for storage, such as HashDB, TreeDB, DirDB and ForestDB, and they either choose to store in single file, or store in multiple files in a directory.
The checkpointing procedure basically blocks all other threads no matter whether they are updating or reading. Any backup procedures can be done by using BasicDB::copy
method. Besides, cache hash database and cache tree database can use BasicDB::dump_snapshot
method to complete 'pseudo-snapshot' procedure. The checkpointing procedure backs up database records and status into a stream or output file. There is also a non-blocking backup mechanism called 'hot backup', using the snapshot command provided by the operating system and the File::synchronize
method to synchronize any later updates.
Each record in the database consists of a key and a value. Kyoto Cabinet supports adding key-value pair, deleting by key, retrieval by key and traversal every key. Every key must be unique in a database since there is no table concept. Keys and values are simply variable length bytes in Kyoto Cabinet.
http://fallabs.com/kyotocabinet/
https://fallabs.com/kyotocabinet/pkg/
http://fallabs.com/kyotocabinet/api/
FAL Labs
2009
Ayanokoji Cabinet
C, C++, Java, Lua, Perl, Python, Ruby
BSD, Linux, OS X, Solaris, Windows
https://en.wikipedia.org/wiki/Tokyo_Cabinet_and_Kyoto_Cabinet