Tkrzw: a set of implementations of DBM

Tkrzw: a set of implementations of DBM

Overview

DBM (Database Manager) is a concept of libraries to store an associative array on a permanent storage. In other words, DBM allows an application program to store key-value pairs in a file and reuse them later. Each of keys and values is a string or a sequence of bytes. The key of each record must be unique within the database and a value is associated to it. You can retrieve a stored record with its key very quickly. Thanks to simple structure of DBM, its performance can be extremely high.

Tkrzw is a C++ library implementing DBM with various algorithms. It features high degrees of performance, concurrency, scalability and durability. The following classes are provided.

HashDBM : File database manager implementation based on hash table.

TreeDBM : File database manager implementation based on B+ tree.

SkipDBM : File database manager implementation based on skip list.

TinyDBM : On-memory database manager implementation based on hash table.

BabyDBM : On-memory database manager implementation based on B+ tree.

CacheDBM : On-memory database manager implementation with LRU deletion.

Std(Hash|Tree)DBM : On-memory DBM implementations using std::unordered_map and std::map.

(Poly|Shard)DBM : Polymorphic and sharding database manager adapters.

AsyncDBM : Asynchronous database manager adapter.

(File|Mem)Index : Secondary index implementations.

All database classes share the same interface so that applications can use any of them with the common API. All classes are thread-safe so that multiple threads can access the same database simultaneously. Basically, the database file is opened with the "Open" method and closed with the "Close" method. You can store records with the "Set" method, retrieve records with the "Get" method, and remove records with the "Remove" method. Iterator is also supported to retrieve each and every record of the database.

Transactional features are also supported. If you want to evaluate a record and update it atomically, you use the "Process" method, which takes a key and an arbitrary callback function to process the record. If you want to evaluate multiple records and update them atomically, you use the "ProcessMulti" method, which takes keys and arbitrary callback functions to process the records. If you want to do long transactions without locking records, the "CompareExchange" method and the "CompareExchangeMulti" method are useful.

Each data class has different approaches for durability. The file database classes support the auto restore feature to recover records after the process crashes. The file hash/tree databases support the appending update mode, which prevents data corruption of existing records. The file skip database and all on-memory databases atomically replace the entire database with a completed temporary file, which realizes the strongest durability on a single machine. All database classes support producing online update logs, which enables online data replication and staged backup.

If the data structure is more complex than key-value pairs, you can treat the value as a serialized text/binary of any data structure. You can use any serialization format. To look up records by some properties except for the primary key, you can use secondary indices. MemIndex and FileIndex classes are useful for the purpose.

HashDBM and TreeDBM supoort automatic data compression and encryption with various algorithms. If you enable one of them, the record data is stored after being encoded automatically. Conversely, the record data in the file is loaded after being decoded automatically. Compression allows you to store large records into smaller files. Encryption allows you to store secret records in local files safely.

Tkrzw adopts dependency injection for file implementations. Bundled implementations support memory mapping I/O, normal read/write I/O, and direct block I/O. You can inject your own implementations to support specific data storages and file systems. Whereas such file implementations use APIs (system calls) of the underlying operating systems, the upper layer for database algorithms doesn't depend on them so that the maximum portability is achieved. Tkrzw supports any Unix-like systems and Windows.

You can use some bridging interfaces to use Tkrzw in other programming languages than C++. Currently, C, Java, Python, Ruby, and Go interfaces are provided. The C interface is bundled in the main package. The other interfaces are packaged separately.

Command line utilities are provided as well. Thereby, you can create databases, set records, retrieve records, remove records, rebuild databases, and restore databases. A tool to do performance tests is also bundled.

If you want to share a database among multiple processes or programs on remote machines, use the database service of Tkrzw-RPC.

Download

You can download source packages in the following directories.

C++ source...