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.

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 packages
• Java source packages
• Python source packages
• Ruby source packages
• Go source packages

Documents

The following are API documents for each language.

• C++ API documents
• Java API documents
• Python API documents
• Ruby API documents
• Go API documents

Installation

Tkrzw is implemented based on the C++17 standard and POSIX/Windows API. On a Unix-like system (Linux, FreeBSD, and Mac OS X), GCC (version 7.3 or later) is required. On a Windows system, Visual C++ (2019 or later) is required.

For UNIX

To build and install the library, usually, you will run the following commands.

“make check” is just for testing and it can take several minutes. You can omit it. If you build binary packages on resource-limited systems, use “make check-light” instead. If you want to install the files under “/usr”, specify “–prefix=/usr” with the configure script.

By default, the library and related files are installed under “/usr/local”.

Let’s check whether the command utilities work properly.

Read the C++ API documents for usage of the library. Then, let’s build a sample program. Make a file of the following C++ code and save it as “helloworld.cc”.

To build an application program, you’ll typically run a command like this. The compiler flag “-std=c++17” is necessary if the default C++ version of your compiler is older than C++17. The flags “-llzma”, “-llz4”, “-lzstd”, and “-lz” should be set only if corresponding features (LZMA, LZ4, ZStd, and ZLib) are enabled by the configure script. If you don’t use threading functions in the application code, you can omit the compiler flag “-pthread”. Even so, the linking flags “-latomic” and “-lpthread” are necessary because the library uses threading functions.

The bundled command “tkrzw_build_util” is useful to know necessary CPPFLAGS (flags for the preprocessor), and LDFLAGS (flags for the linker).

In some environments, you can also use the “pkg-config” command to list up those flags.

To run the test suite, GoogleTest is required. Although testing the library is not necessary for most users, you can do so just in case.

The “–enable-opt-native” flag of the configure script is to optimize the operation code specifically to the native platform. If it is omitted, normal optimization is done. The “–enable-most-features” flag is to enable as many features as possible on the platform. Data compression features using external libraries are integrated. You can enable each of them separately by setting “–enable-zlib”, “–enable-zstd”, “–enable-lz4”, and “–enable-lzma”. If you use another prefix than “/usr/local” for extra packages, specify the prefix with “–with-extra”, such as “–with-extra=/opt/homebrew”. If you don’t need dynamic linking library, set “–disable-shared”. If you want the utility commands with static linking, set “–enable-static”. If you develop Tkrzw itself, set “–enable-devel” or “–enable-debug”.

For Windows

To build and install the library, you use “nmake”. Edit VCMakefile to assure the base path of Visual C++ and the base path of the system SDK are correct. The directory names are different among minor versions so checking them is important.

Open “x64 Native Tools Command Prompt for VS 2019” in the control panel. It sets command paths and other necessary environment configurations. Set the current directory to Tkrzw’s source directory. Run the following command.

 nmake -f VCMakefile
> nmake -f VCMakefile check
]]>

To install the library, open another command prompt of VC++ as Administrator and run the following command.

 nmake -f VCMakefile install
]]>

By default, the library and related files are installed under “C:Program Filestkrzw”. You can change it by editing VCMakefile before installation.

Read the C++ API documents for usage of the library. Then, let’s build a sample program. Make a file of the following C++ code and save it as “helloworld.cc”.

To build an application program, you’ll typically run a command like this. The compiler flag “/std:c++17” is necessary if the default C++ version of your compiler is older than C++17.

 cl /std:c++17 /Zc:__cplusplus 
  /I "C:Program Files (x86)tkrzwinclude" 
  /O2 /EHsc /W3 /MT helloworld.cc tkrzw.lib /OUT:helloworld.exe 
  /link /libpath:"C:Program Files (x86)tkrzwlib"
]]>

The bundled command “tkrzw_build_util” is useful to know necessary CPPFLAGS (flags for the preprocessor), and LDFLAGS (flags for the linker).

 tkrzw_build_util config -i
/I "C:Program Filestkrzwinclude"
> tkrzw_build_util config -l
/libpath:"C:Program Filestkrzwlib" tkrzw.lib
]]>

By default, the compiler flag “/MT” is specified to link to the multithread, static version of the run-time library. You can change it to “/MD” link to the dynamic run-time library. You can also make a DLL for TKRZW by the linker option “/LD”.

The data compression libraries are not integrated on Windows by default. If you want to enable some of them, define macros by adding some of “/D_TKRZW_COMP_ZLIB”, “/D_TKRZW_COMP_ZSTD” , “/D_TKRZW_COMP_LZ4”, and “/D_TKRZW_COMP_LZMA” to CLFLAGS in VCMakefile. Then, add the library (lib/dll) files to EXTRALIBRARIES in VCMakefile. You’ll also add the library files to the command line to build your own programs.

Performance

Each database class has specific traits. It is important to select the best one or combine some of them for the use case.

Performance is also different among the database classes. Let’s say, one thread sets 1 million records. The key of each record is an 8-byte string from “00000000”, “00000001”, to “00999999” in ascending order. The value is an 8-byte string. Then, it retrieves all records and finally remove them. The following table shows throughput of all operations on a computer with a 3.5Ghz 6-core CPU.

Next, we use 10 threads, each of which sets 100 thousand records. Thus, 1 million records in total are set. Then, the threads retrieve all records and finally remove them. As seen below, the on-memory hash database is extremely good at concurrent updating. The file hash database is also very good at concurrent updating although it is based on the file storage.

The above test cases should show ideal performance of each database class because records are accessed sequentially and the entire data can be cached on memory by the file system. Then, let’s move on to tougher test cases. We build a large database of 100 million records with random keys between “00000000” and “99999999”. As some keys are duplicated and such records are overwritten, the actual number of unique records is about 63 million.

Finally, we do the same operations with 10 threads. These test cases aim to simulate typical use cases where a large amount of random records are inserted and retrieved simultaneously. As suggested by the time complexity O(1) in theory, actual throughputs of the file hash database and the on-memory hash database are not affected by access patterns or the number of records. Meanwhile, throughputs of the file tree database and the file skip database decline although they can still respond to hundreds of thousands of queries per second.

In general, if you want a key-value storage with the highest performance, choosing the file hash database is recommended. If you need ordered access of records, choosing the file tree database is recommended. If you need scalability of ordered databases, choosing the file skip database is recommended. If you need extreme performance, the on-memory hash database and the on-memory tree database are useful although they require another way to save/load records. If you want a cache system with deletion of LRU records, the cache database is useful.

HashDBM: The File Hash Database

The file hash database stores key-value structure in a single file. It uses a hash table and linked lists of records from buckets. Therefore, given the number of records N and the number of buckets M, the average time complexity of data retrieval is O(N/M). If M is large enough, the time complexity can be said O(1).

Thread concurrency is pursued in this implementation. Only reader-writer locking is applied to each hash bucket. Therefore, even writer threads which can set or remove records performs in parallel. Blocking is done only when multiple writers try to update the same record simultaneously. Reader threads which retrieve records don’t block each other even for the same record.

Durability is also pursued. Updating operations support two modes: in-place and appending. In the in-place mode, the region of an existing record in the file is re-written to modify the value of the record. In the appending mode, the region in the file for an existing record is never re-written. Instead, new data to overwrite the value is appended at the end of the file. The new data is put at the top of the linked list for the record so that it is detected prior to the old one. In both modes, even if the hash table is broken for some reason, the database is restored automatically to salvage record data. In the in-place mode, the record being updated when brokage happens can be lost but the other records can be recovered. In the appending mode, any record can never be lost unless the file system itself breaks.

The hash table is static and not reorganized implicitly. Thus, if the load factor of the hash table is high, the database should be rebuilt explicitly by the application. Rebuilding the database is effective to resolve fragmentation which can happen in both the in-place mode and the appending mode. Rebuilding the database doesn’t block other database operations. In other words, you can retrieve and update records while the database is being rebuilt.

See the tips of Tuning HashDBM too. Tuning has a significant influence on performance. For details of the API, see the API document.

Example Code

This is a code example where basic operations are done without checking errors.

 iter = dbm.MakeIterator();
  iter->First();
  std::string key, value;
  while (iter->Get(&key, &value) == Status::SUCCESS) {
    std::cout Next();
  }
  
  // Closes the database.
  dbm.Close();

  return 0;
}
]]>

This is a code example which represents a more serious use case with performance tuning and thorough error checks.

 iter = dbm.MakeIterator();
  if (iter->First() != Status::SUCCESS) {
    // Failure of the First operation is critical so we stop.
    Die("First failed: ", status);
  }
  while (true) {
    // Retrieves the current record data.
    std::string iter_key, iter_value;
    status = iter->Get(&iter_key, &iter_value);
    if (status == Status::SUCCESS) {
      std::cout Next();
    if (status != Status::SUCCESS) {
      // This could happen if another thread removed the current record.
      if (status != Status::NOT_FOUND_ERROR) {
        // Error types other than NOT_FOUND_ERROR are critical.
        Die("Iterator::Get failed: ", status);
      }
      std::cerr 

The file hash database, as well as other database classes, supports call-back functions to process the value of a record. The operation is done while the record is locked so that the update looks done atomically.

Format

The hash database file is composed of five sections: the metadata section, the bucket section, the free block pool section, the record header section, and the record section.

The metadata section dominates the first 128 bytes of the file. It contains the following fields.

Magic data

From the offset 0. A 9-byte string “TkrzwHDBn”.

The front cyclic magic data.

From the offset 9. A 1-byte integer.

The package major version

From the offset 10. A 1-byte integer.

The package minor version

From the offset 11. A 1-byte integer.

The static flags

From the offset 12. A 1-byte integer.

The offset width

From the offset 13. A 1-byte integer.

The alignment power

From the offset 14. A 1-byte integer.

The closure flags

From the offset 15. A 1-byte integer.

The number of buckets

From the offset 16. An 8-byte big-endian integer.

The number of records

From the offset 24. An 8-byte big-endian integer.

The effective data size.

From the offset 32. An 8-byte big-endian integer.

The file size

From the offset 40. An 8-byte big-endian integer.

The last modified timestamp.

From the offset 48. An 8-byte big-endian integer.

The database type

From the offset 56. A 4-byte big-endian integer.

The opaque data

From the offset 62. Arbitrary string data.

The back cyclic magic data.

From the offset 127. A 1-byte integer.

The magic data and the package version data are used for identifying the kind of the file. The two figures of the cyclic magic data are used to check consistency of the meta data. The version data indicates the version of the Tkrzw package when the file is created.

The static flags specifies flags which are not changed during lifetime of the database. The first bit and the second bit represent the update mode. 0x1 means the in-place update mode. 0x2 means the appending update mode. 0x0 and 0x3 are invalid. The third bit and the fourth bit represent the record CRC mode. 0x0 means no CRC. 0x1 means CRC-8. 0x2 means CRC-16. 0x3 means CRC-32. The fifth bit, the sixth, and the seventh bit represent compression mode. 0x0 means no compression. 0x1 means ZLib. 0x2 means ZStd. 0x3 means LZ4. 0x4 means LZMA.

The offset width specifies how many bytes are used to store an offset value. Given the offset width W, the maximum value is 2^(W*8). So, W=3 sets the maximum value 16,777,216 and W=4 sets it 4,294,967,296. The offset width affects the size of the buckets and the footprint of each record. The alignment power specifies the alignment of the offset value. Given the alignment power P, the alignment is 2^P. So, P=2 sets the alignment 4 and P=3 sets it 8. The alignment affects the size of space for each record. The maximum database size is determined as 2^(W*8+P). The default value of the offset width is 4 and the default value of the alignment power is 3. So, the maximum database size is 32GiB by default.

When a database is opened in the writable mode, the metadata section is updated immediately to set the closure flag zero and set the last modified timestamp to the current UNIX time in microseconds. If the process crushes without closing the database, the flag and the timestamp helps us detect the incident. If the writable database is closed normally, the closure flag is set one and the last modified timestamp is updated too.

The number of buckets determines how many buckets are used for the hash table. The number of records indicates the current number of living key-value pairs in the database. The effective data size indicates the total amount of bytes used for the key and the value data of the living records. In other words, it doesn’t include data for removed data, overwritten data, or other footprints. This figure is used to calculate storage efficiency.

The database type and the opaque data are used for any purposes by the application. Modifying them is done in place so it doesn’t increase the file size even in the appending mode. The file tree database uses the opaque data to store its metadata.

The bucket section dominates from the offset 128 to an offset determined by the number of buckets and the offset width. Given the number of buckets M and the offset width W, the end offset is 128 + M * W. The default value of the number of buckets is 1,048,583. Then, the bucket section dominates from the offset 128 to 4,194,460. Each bucket is an integer in big-endian. If there’s no record matching the bucket index, the value is zero. Otherwise, it indicates the offset of the data of the first record in a linked list of records matching the bucket index.

The hash function is the 64-bit version of MurmurHash 3. It is applied to the whole key data. If the number of buckets is less than 2^32, the hash value is folded by taking XOR of the greater 32 bits and the lower 32 bits in the format of (([32,47]<<16)|[48,63]) ^ (([0,15]<<16)|[16,31]). The bucket index of the key is the remainder of division of the hash value by the number of buckets.

The record section dominates from an aligned offset after the bucket section to the end of the file. The start point is equal to or after the figure calculated as 128 + num_buckets * W + 1024 and it is aligned to 4096 and 2^P. The record section contains multiple record data in sequence. Each record is serialized in the following format.

The magic data

1 byte integer.

The child offset

A big-endian integer with the offset width.

The key size

A byte delta encoded integer.

The value size

A byte delta encoded integer.

The padding size

A byte delta encoded integer.

The CRC value

Optional: A 1-byte, 2-byte, or 4-byte integer.

The key data

Optional: Arbitrary string data.

The value data

Optional: Arbitrary string data.

The padding data

Optional: A magic data and null data.

The magic data is composed of the operation type part and the checksum part. The upper 2 bits are the operation type part. 0xC0 (0x3 << 6) indicates that the operation is to do nothing. 0x80 (0x2 << 6) is to set the value of an existing record. 0x40 (0x1 << 6) is to remove an existing record. 0x00 (0x1 << 6) is to add a new record. The lower 6 bits are the checksum part. The checksum is a total value of the seed value 11 and each byte of a concatenated sequence of the record key and the record value in modulo 61. And, the final value is added to 3 so that the range is between 3 and 63 inclusive. The checksum helps us detect data corruption.

The child offset indicates the offset of the next record data in the linked list of the bucket. When a new record data of the same bucket is added, the bucket points to the new record data and the new record data points to the top one of the existing linked list, or zero if it doesn’t exist.

The key size, the value size, and the padding size are represented in byte delta encoding. A value between 0 and 127 takes 1 byte. A value between 128 and 16,383 takes 2 bytes. A value between 16,384 and 2,097,151 takes 3 bytes. A value between 268,435,456 and 34,359,738,367 takes 4 bytes.

The CRC value is optional. If it exists, the value is the result of CRC-8, CRC-16, or CRC-32 applied to the concatenated data of the key and the value. The CRC value is used to detect inconsistency when the database is restored.

The key data and the value data are optional, which means an empty key and an empty value respectively. The key data is stored as-is. The value data is also stored as-is by default. If the record compression is enabled, compressed data by the algorithm is stored.

The padding data is optional. If it exists, it begins with a byte of 0xDD. The remaining data is null codes. The actual padding size includes additional size of the metadata for the padding size. That is, if the padding size in the record metadata is more than 127, the actual padding size is less by one byte. Likewise, larger than 16383 means less by two bytes, larger than 2097151 means less by three bytes.

With the default 4-byte offset width and small-sized (less than 128 bytes) keys and medium-sized (less than 16384 bytes) values, the footprint for each record is 1 + 4 + 1 + 2 + 1 = 9 bytes. However, due to alignment, padding bytes can be added. With the default 8-byte alignment, average padding size is about 4 bytes.

The 16 bytes before the record section is the record header section. It is composed of “TkrzwRECn”, a 1-byte integer for the static flags, a 1-byte integer for the offset width, and a 1-byte integer for the alignment power. They would be used to recover records if the main header were broken.

The 1008 bytes before the record header section is the free block pool section. It contains pairs of an offset and a size of each free block. The offset is a big-endian integer of the offset width. The size is a big-endian integer of 4 bytes. The maximum number of pairs is determined as 1008 / (W + 4). Given the offset width 4, the maximum number is 126.

As long as the meta data for the file size indicates the actual content size, padding data of null codes can be appended at the end of the file. This is useful to align the file size to the requirement of direct I/O.

TreeDBM: The File Tree Database

The file tree database stores key-value structure in a single file. It uses a multiway balanced tree structure called B+ tree. Therefore, given the number of records N, the average time complexity of data retrieval is O(log N). Because records are ordered by the key, range searches including forward matching search are supported.

A B+ tree is composed of nodes which are composed of records and links. Each node is serialized as a “page”, which are stored in the file hash database. Therefore, the file tree database inherits many characteristics of the file hash database: performance, scalability, and durability. The file tree database uses a double-layered LRU cache system to reduce frequency of inputs and outputs of pages; Pages which have been repeatedly accessed are stored in the “hot” cache so that they are not wiped out even if many pages are accessed by a few traversal operations, which use the “warm” cache.

Thread concurrency is pursued in this implementation. Only reader-writer locking is applied to each page. Therefore, if threads randomly access records, they don’t block each other. If multiple threads access the same page, a writer blocks the others but readers don’t block other readers. The page cache system is managed with slotted mutexes so that multiple threads can access the cache system simultaneously.

If records are accessed sequentially in order of the key, performance of the file tree database can be better than the file hash database because file I/O is done by the page and its frequency is much less. However, if records are accessed randomly, performance of the file tree database is worse than the file hash database. Likewise, space efficiency of the file tree database can be better than the file hash database if records are inserted in order. However, if records are inserted randomly, one thirds of storage space is used for padding. As with the file hash database, rebuilding the database can reduce the file size and it is done without blocking other threads.

See the tips of Tuning TreeDBM too. Tuning has a significant influence on performance. For details of the API, see the API document.

Example Code

This is a code example where basic operations are done without checking errors.

 iter = dbm.MakeIterator();
  iter->Jump("ba");
  std::string key, value;
  while (iter->Get(&key, &value) == Status::SUCCESS) {
    if (!StrBeginsWith(key, "ba")) break;
    std::cout Next();
  }
  
  // Closes the database.
  dbm.Close();

  return 0;
}
]]>

This is a code example which represents a more serious use case with performance tuning and thorough error checks.

 iter = dbm.MakeIterator();
  if (iter->First() != Status::SUCCESS) {
    // Failure of the First operation is critical so we stop.
    Die("First failed: ", status);
  }
  while (true) {
    // Retrieves the current record data.
    std::string iter_key, iter_value;
    status = iter->Get(&iter_key, &iter_value);
    if (status == Status::SUCCESS) {
      std::cout Next();
    if (status != Status::SUCCESS) {
      // This could happen if another thread removed the current record.
      if (status != Status::NOT_FOUND_ERROR) {
        // Error types other than NOT_FOUND_ERROR are critical.
        Die("Iterator::Get failed: ", status);
      }
      std::cerr 

This is an example to make a dictionary from a TSV file. The keys are normalized into lower case and forward matching queries are supported.

 columns = StrSplit(line, "t");
    if (columns.size()  iter = dbm.MakeIterator();
  iter->Jump("app");
  std::string key, value;
  while (iter->Get(&key, &value) == Status::SUCCESS) {
    if (!StrBeginsWith(key, "app")) break;
    std::cout Next();
  }

  // Close the input file
  file.Close();

  // Closes the database.
  dbm.Close();

  return 0;
}
]]>

Format

The tree database file is based on the hash database. Metadata of B+ tree are stored in the opaque metadata section and nodes of B+ tree are stored as records of the hash database.

The opaque metadata section of the hash database is a space to store an arbitrary 64-byte string, which the tree database uses to store its metadata. It contains the following fields.

Magic data

From the offset 0. A string “TDB” and a training null ‘’ character.

The number of records

From the offset 4. A 6-byte big-endian integer.

The effective data size.

From the offset 10. A 6-byte big-endian integer.

The root page ID

From the offset 16. A 6-byte big-endian integer.

The first page ID.

From the offset 22. A 6-byte big-endian integer.

The last page ID.

From the offset 28. A 6-byte big-endian integer.

The number of leaf nodes

From the offset 34. A 6-byte big-endian integer.

The number of inner nodes

From the offset 40. A 6-byte big-endian integer.

The maximum page size

From the offset 46. A 3-byte big-endian integer.

The maximum number of branches

From the offset 49. A 3-byte big-endian integer.

The level of the tree

From the offset 52. A 1-byte integer.

The key comparator type

From the offset 53. A 1-byte integer.

The opaque data

From the offset 54. Arbitrary string data.

The magic data is used for identifying the kind of the database. The number of records indicates the current number of living key-value pairs in the database. The effective data size indicates the total amount of bytes used for the key and the value data of the living records. In other words, it doesn’t include data for removed data, overwritten data, or other footprints. This figure is used to calculate storage efficiency.

There are two kinds of nodes of B+ tree: leaf nodes and inner nodes. Leaf nodes contain records of key-value pairs. Inner nodes contain keys and links to other nodes. The root ID indicates the ID of the root node of B+ tree. The root node is used as the entry point of search. The first ID indicates the ID of the first leaf node of B+ tree. Leaf nodes are linked in a double linked list and the first leaf node is the entry point of sequential access. The level of the tree indicates how many layers exist in the tree. If there’s no inner tree, the level is 1.

The key comparator type indicates a function used to compare keys of records. The default LexicalKeyComparator is 1. LexicalCaseKeyComparator which ignores case is 2. DecimalKeyComparator which compares keys as numeric decimal integer expressions is 3. HexadecimalKeyComparator which compares keys as numeric hexadecimal integer expressions is 4. RealNumberKeyComparator which compares keys as decimal real number expressions is 5. Their counterparts for pair strings are 101, 102, 103, and 104. 255 means that another custom comparator is set. In that case, the comparator must be specified every time when the database is opened.

A leaf nodes has a key which is a 6-byte big-endian integer of its ID. The ID is a unique number not less than 1. Its value is serialized in the following format. Records are sorted in ascending order of the key.

The previous leaf node ID

A 6-byte big-endian integer.

The next leaf node ID

A 6-byte big-endian integer.

Repetition of records

Pairs of key-value records.

The key is composed of the key size in byte delta encoding and an arbitrary key data.

The value is composed of the value size in byte delta encoding and an arbitrary value data.

An inner nodes has a key which is a 6-byte big-endian integer of Its ID. The ID is a unique number not less than 2^46 * 3. Its value is serialized in the following format. links are sorted in ascending order of the key.

The heir node ID

A 6-byte big-endian integer.

Repetition of links

Pairs of key/ID links.

The key is composed of the key size in byte delta encoding and an arbitrary key data.

The ID is a 6-byte big-endian integer.

By default, the maximum payload size of each leaf node is 8130. When the page size exceeds it, the leaf node is divided into two and the half size 4065 fits the typical page size 4096 of the operating system. This maximizes space efficiency. If a node is divided and there is no parent node, a new inner node is created and the ID of the first divided node becomes the heir ID. The first key of the second divided node and the ID of the second divided node compose a link, which is inserted in the parent node. By default, the maximum number of links of each inner node is 256. When the number of links exceeds it, the inner node is divided into two and their links are inserted to the parent. This operation is done recursively to the root of the tree.

When the page size of the leaf node becomes less than half of the maximum payload size, the leaf is merged with a sibling node. Therefore, actually, the page size of the merged leaf node can be 1.5 times of the maximum payload size. When the number of links of an inner node becomes less than half of the maximum number of links, the inner node is merged to a sibling node. This operation is done recursively to the root of the tree. If the root is an inner node and it has only one child, the root is removed and the only child becomes the new root.

SkipDBM: The File Skip Database

The file skip database stores key-value structure in a single file. It uses a skip list of sorted records. Therefore, given the number of records N, the average time complexity of data retrieval is O(log N). Because records are ordered by the key, range searches including forward matching search are supported. Retrieving a record by the positional index is also supported.

Although skip list is a static structure, you can modify the database with usual methods of DBM, like the Set and Remove methods. Updates are reflected on the file in a batch manner. After a series of updates, you have to synchronize the database by calling the Synchronize method or close the database by the Close method. Then, you can retrieve records.

The file skip database supports two building modes: at-random and in-order. In the default at-random mode, records can be inserted in random order. When the database is synchronized, input records are sorted by merge sort with temporary files. Thus, you can build a large database whose size exceeds the RAM capacity of your machine. The average time complexity of building the entire database is O(N * log N) in the at-random mode. In the in-order mode, records must be inserted in ascending order of the key. The average time complexity of building the entire database is O(N) in the in-order mode. In both modes, duplicated keys are allowed but you can call an arbitrary reducer function to solve them later.

Records can be inserted concurrently in the at-random mode although synchronizing the database takes the most of the time for building the database. In the in-order mode, it is no use to insert records concurrently because the order cannot be assured by concurrent insertion. For retrieval, only reader locking is applied so that multiple threads can access the database in parallel.

See the tips of Tuning SkipDBM too. Tuning has a significant influence on performance. For details of the API, see the API document.

Example Code

This is a code example where basic operations are done without checking errors.

 iter = dbm.MakeIterator();
  iter->First();
  std::string key, value;
  while (iter->Get(&key, &value) == Status::SUCCESS) {
    std::cout Next();
  }
  
  // Closes the database.
  dbm.Close();

  return 0;
}
]]>

This is a code example which represents a more serious use case with performance tuning and thorough error checks.

 input_records;
  input_records["foo"] = "hop";
  input_records["bar"] = "step";
  input_records["baz"] = "jump";

  // Stores records.
  for (const auto& input_record : input_records) {
    status = dbm.Set(input_record.first, input_record.second);
    if (status != Status::SUCCESS) {
      // The Set operation shouldn't fail.  So we stop if it happens.
      Die("Set failed: ", status);
    }
  }

  // Closes the database.
  status = dbm.Close();
  if (status != Status::SUCCESS) {
    // The Close operation shouldn't fail.  So we stop if it happens.
    Die("Close failed: ", status);
  }

  // Opens the existing database as a reader mode.
  status = dbm.Open("casket.tks", false);
  if (status != Status::SUCCESS) {
    // Failure of the Open operation is critical so we stop.
    Die("Open failed: ", status);
  }

  // Retrieves records.
  // If there was no record, NOT_FOUND_ERROR would be returned.
  std::string value;
  status = dbm.Get("foo", &value);
  if (status == Status::SUCCESS) {
    std::cout  iter = dbm.MakeIterator();
  status = iter->Jump("ba");
  if (status == Status::NOT_FOUND_ERROR) {
    // This could happen if there are no records equal to or greater than it.
    std::cerr Get(&iter_key, &iter_value);
    if (status == Status::SUCCESS) {
      if (!StrBeginsWith(iter_key, "ba")) break;
      std::cout Next();
    if (status != Status::SUCCESS) {
      // This could happen if another thread cleared the database.
      if (status != Status::NOT_FOUND_ERROR) {
        // Error types other than NOT_FOUND_ERROR are critical.
        Die("Iterator::Get failed: ", status);
      }
      std::cerr 

Although the file skip database is not suitable for incessant updates, it supports updating content by adding some records and merging them with the entire database. You can apply an arbitrary reducing function to handle records with the same key.

Format

The skip database file is composed of two sections: the metadata section and the record section.

The metadata section dominates the first 128 bytes of the file. It contains the following fields.

Magic data

From the offset 0. A 9-byte string “TkrzwSDBn”.

The front cyclic magic data.

From the offset 9. A 1-byte integer.

The package major version

From the offset 10. A 1-byte integer.

The package minor version

From the offset 11. A 1-byte integer.

The offset width

From the offset 12. A 1-byte integer.

The step unit

From the offset 13. A 1-byte integer.

The maximum level

From the offset 14. A 1-byte integer.

The closure flags

From the offset 15. A 1-byte integer.

The number of records

From the offset 24. An 8-byte big-endian integer.

The effective data size.

From the offset 32. An 8-byte big-endian integer.

The file size

From the offset 40. An 8-byte big-endian integer.

The last modified timestamp.

From the offset 48. An 8-byte big-endian integer.

The database type

From the offset 56. A 4-byte big-endian integer.

The opaque data

From the offset 62. Arbitrary string data.

The back cyclic magic data.

From the offset 127. A 1-byte integer.

The magic data, the cyclic magic data and the package version data are used for identifying the kind of the file. The two figures of cyclic magic data are used to check consistency of the meta data. The version data indicates the version of the Tkrzw package when the file is created.

The offset width specifies how many bytes are used to store an offset value. Given the offset width W, the maximum value is 2^(W*8). So, W=3 sets the maximum value 16,777,216 and W=4 sets it 4,294,967,296. The offset width affects the size of the buckets and the footprint of each record. The default value of the offset width is 4, which means the maximum file size is 4GB. The step unit specifies how often records are given links to forward records. Given the step unit S, records whose indices can be divided by S have the level 1 links, which refers to the forward record in S-th steps. Records whose indices can be divided by S^2 have the level 2 links, which refers to the forward in S^2-th steps. Likewise, fewer records have higher level links. The highest level is limited by the maximum level property. To get the optimal performance, given the number of records N, the maximum level should be higher than Log_S N – 1. So given, R=1000000 and S=4, the maximum level should be higher than log_4 100000 – 1 = 8.96. The default value of the step unit is 4 and the default value of the maximum level is 14. So, they are optimal until the number of records is 4^15 = 1,073,741,824.

When a database is opened in the writable mode, the metadata section is updated immediately to set the closure flag zero and set the last modified timestamp to the current UNIX time in microseconds. If the process crushes without closing the database, the flag and the timestamp helps us detect the incident. If the writable database is closed normally, the closure flag is set one and the last modified timestamp is updated too.

The record section dominates from 128 to the end of the file. The record section contains multiple record data in sequence in ascending order of the key. Each record is serialized in the following format.

The magic data

1 byte integer.

The offsets of the forward records

A big-endian integers with the offset width.

The key size

A byte delta encoded integer.

The value size

A byte delta encoded integer.

Optional: The key data

Arbitrary string data.

Optional: The value data

Arbitrary string data.

The magic data is 0xFF and helps us detect data corruption.

The offsets of the forward records are composed of big-endian integers whose number is the same as the level of the record. The level is determined by how many times the index of the record can be divided by the step unit without a remainder. Given the step unit S and the index C, the destination of the first level link is the record whose index is C + S^1. The destination of the second level link is the record whose index is C + S^2.

The key size and the value size are represented in byte delta encoding. A value between 0 and 127 takes 1 byte. A value between 128 and 16,383 takes 2 bytes. A value between 16,384 and 2,097,151 takes 3 bytes. A value between 268,435,456 and 34,359,738,367 takes 4 bytes.

The key data and the value data are optional, which means an empty key and an empty value respectively. The key data and the value data are stored as-is.

As long as the meta data for the file size indicates the actual content size, padding data of null codes can be appended at the end of the file. This is useful to align the file size to the requirement of direct I/O.

TinyDBM: The On-memory Hash Database

The on-memory hash database stores key-value structure on-memory. It uses a hash table and linked lists of records from buckets. Therefore, given the number of records N and the number of buckets M, the average time complexity of data retrieval is O(N/M). If M is large enough, the time complexity can be said O(1).

Thread concurrency is pursued in this implementation. Only reader-writer locking is applied to each hash bucket. Therefore, even writer threads which can set or remove records perform in parallel. Blocking is done only when multiple writers try to update the same record simultaneously. Reader threads which retrieve records don’t block each other even for the same record.

Whereas thread safety and thread performance are the most important features of the on-memory hash database, memory efficiency is also remarkable. Because the key and the value, and all metadata are serialized in a single sequence of bytes, memory footprint is minimum. Typically, pure footprint except for the footprint from the memory allocator is 10 bytes. Assuming the key and the value are 8-byte strings, actual memory usage is about 55% of std::map.

You don’t have to open or close on-memory databases to use them. You can just set records and retrieve them as if they were std::unordered_map. However, you can associate the database to a file by opening it with a file path. Then, when you close the database, all records are saved in the file. And, you can reuse the records by opening the database with the same file path.

For details of the API, see the API document.

Example Code

This is a code example where basic operations are done without checking errors.

 iter = dbm.MakeIterator();
  iter->First();
  std::string key, value;
  while (iter->Get(&key, &value) == Status::SUCCESS) {
    std::cout Next();
  }
  
  return 0;
}
]]>

This is a code example which represents a more serious use case where records are saved in a file and they are reused later.

First();
  std::string key;
  while (iter->Get(&key) == Status::SUCCESS) {
    if (dbm.CompareExchange(key, "jump", "land") == Status::SUCCESS) {
      std::cout Next();
  }

  // Closes the database.
  // In the reader mode, the file is not updated and no error occurs.
  dbm.Close();

  return 0;
}
]]>

BabyDBM: The On-memory Tree Database

The on-memory tree database stores key-value structure on-memory. It uses a multiway balanced tree structure called B+ tree. Therefore, given the number of records N, the average time complexity of data retrieval is O(log N). Because records are ordered by the key, range searches including forward matching search are supported.

A B+ tree is composed of nodes which are composed of records and links. Each node is serialized as a “page”, which are kept on-memory. Thread concurrency is pursued in this implementation. Only reader-writer locking is applied to each page. Therefore, if threads randomly access records, they don’t block each other. If multiple threads access the same page, a writer blocks the others but readers don’t block other readers.

Whereas thread safety and thread performance are the most important features of the on-memory tree database, memory efficiency is also remarkable. Because the key and the value, and all metadata are serialized in a single sequence of bytes, memory footprint is minimum. Typically, pure footprint except for the footprint from the memory allocator is 10 bytes. Assuming the key and the value are 8-byte strings, actual memory usage is about 50% of std::map.

You don’t have to open or close on-memory databases to use them. You can just set records and retrieve them as if they were std::unordered_map. However, you can associate the database to a file by opening it with a file path. Then, when you close the database, all records are saved in the file. And, you can reuse the records by opening the database with the same file path.

For details of the API, see the API document.

Example Code

This is a code example where basic operations are done without checking errors.

 iter = dbm.MakeIterator();
  iter->Jump("ba");
  std::string key, value;
  while (iter->Get(&key, &value) == Status::SUCCESS) {
    if (!StrBeginsWith(key, "ba")) break;
    std::cout Next();
  }
  
  return 0;
}
]]>

This is a code example which represents a more serious use case where records are saved in a file and they are reused later.

Last();
  std::string key, value;
  while (iter->Get(&key, &value) == Status::SUCCESS) {
    std::cout Previous();
  }

  // Closes the database.
  // In the reader mode, the file is not updated and no error occurs.
  dbm.Close();

  return 0;
}
]]>

CacheDBM: The On-memory Cache Database with LRU Deletion

The on-memory cache database stores key-value structure on-memory. It uses a hash table and triple linked lists: from the buckets to each record, from the first record to the last record, and from the last record to the first record. When a record is accessed, it is placed at the end of the list. Therefore, the least recent used record is placed at the first position. The cache database has a capacity to keep the memory usage stable. When the number of records exceeds the capacity, least recent used records are removed implicitly. The average time complexity is O(1).

The cache database is sharded internally so that mutex is done for each shard, in order to improve concurrent performance. The actual concurrent performance of the cache database is almost the same as the normal on-memory hash database. Whereas space efficiency of the cache database is worse than those of the on-memory hash database and the on-memory tree database, it is suitable as a cache system, thanks to the LRU deletion feature.

You don’t have to open or close on-memory databases to use them. You can just set records and retrieve them as if they were std::unordered_map. However, you can associate the database to a file by opening it with a file path. Then, when you close the database, all records are saved in the file. And, you can reuse the records by opening the database with the same file path.

For details of the API, see the API document.

Example Code

This is a code example where basic operations are done without checking errors.

Std(Hash|Tree)DBM: The STL On-memory Databases

The standard on-memory hash database StdHashDBM stores key-value structure on memory with std::unordered_map. The standard on-memory tree database stores key-value structure on memory with std::map. As the hash database uses a hash table, the average time complexity of data retrieval is O(1). As the tree database uses a binary tree, the average time complexity of data retrieval is O(log N).

Thread safety is assured in these implementations. Reader-writer locking is applied to the whole database. Therefore, multiple reader threads can access the same database without blocking whereas a writer thread blocks other threads. Thread safety is the only benefit of these implementations over using bare std::unordered_map or std::map.

You don’t have to open or close on-memory databases to use them. You can just set records and retrieve them as if they were std::unordered_map and std::map. However, you can associate the database to a file by opening it with a file path. Then, when you close the database, all records are saved in the file. And, you can reuse the records by opening the database with the same file path.

In contrast with the hash database, the tree database StdTreeDBM assures that all keys are ordered in alphabetical order. The iterator supports the Jump method, which enables range searches including forward-matching search.

For details of the API, see the API document.

Example Code

This is a code example where basic operations are done without checking errors.

 iter = dbm.MakeIterator();
  iter->Jump("ba");
  std::string key, value;
  while (iter->Get(&key, &value) == Status::SUCCESS) {
    if (!StrBeginsWith(key, "ba")) break;
    std::cout Next();
  }

  return 0;
}
]]>

This is a code example which represents a more serious use case where records are saved in a file and they are reused later.

(Poly|Shard)DBM: Polymorphic and Sharding DBM Adapters

Although all database classes share the same interface defined by the DBM class, constructors and tuning parameters are different. The polymorphic database manager adapter PolyDBM is provided in order to absorb such differences so that you can always use the same class PolyDBM. The concrete class is determined by the extension of the path. You can open a hash database by the following code.

The following extensions are recognizable.

• HashDBM: .tkh, .hash
• TreeDBM: .tkt, .tree
• SkipDBM: .tks, .skip
• TinyDBM: .tkmt, .tiny, .flat
• BabyDBM: .tkmb, .baby
• CacheDBM: .tkmc, .cache
• StdHashDBM: .tksh, .stdhash
• StdTreeDBM: .tkst, .stdtree

You can specify the class name directly by passing the “dbm” parameter to the OpenAdvanced method. It also takes tuning parameters. You can use the hash database and tune it by the following code.

 params = {
  {"dbm", "HashDBM"}, {"align_pow", "0"}, {"num_buckets", "10000"}};
dbm.OpenAdvanced("casket", true, File::OPEN_DEFAULT, params);
]]>

On-memory databases also have to be opened by the Open or OpenAdvanced method. However, if the path is empty, records are not saved in or loaded from any file. If you specify a non-empty path, records are saved in and loaded from the file. The following code opens an on-memory tree database without associating it to any file.

 params = {
  {"dbm", "BabyDBM"}, {"key_comparator", "DecimalKeyComparator"}};
dbm.OpenAdvanced("", true, File::OPEN_DEFAULT, params);
]]>

The polymorphic database manager adapter is also useful when you develop interfaces for other programming languages, like Java, Python, Ruby, Go, Lua etc. Whereas writing code for each database class is tedious, just writing code for PolyDBM allows you to use all database classes.

The sharding database manager adapter ShardDBM is a wrapper of multiple PolyDBM instances for sharding a database. Whereas an instance of ShardDBM behaves like a usual DBM, records are stored in multiple database files, which are called shards. A hash function is used to determine which shard each record belongs to.

By separating one database file into several files, concurrent performance improves. Possibility that a thread is blocked by mutexes is divided by the number of shards. Moreover, efficiency of rebuilding database improves. Usually, rebuilding a database file requires making a temporary file whose size is proportional to the original database file. With sharding, rebuilding database is done for each shard one by one. Thus, the size of each temporary file is also divided.

ShardDBM can shard any database, whether it is ordered or unordered. With an ordered database, the iterator gathers records from each shard using a heap tree structure so that records are retrieved in ascending order of the key.

You specify the number of shards by passing the “num_shards” parameter to the OpenAdvanced method. It also takes the same tuning parameters as PolyDBM.

 params = {
  {"num_shards", "4"}, {"dbm", "TreeDBM"},
dbm.OpenAdvanced("casket", true, File::OPEN_DEFAULT, params);
]]>

If the file path is “casket” and the number of shards is 4, “casket-00000-of-00004”, “casket-00001-of-00004”, “casket-00002-of-00004”, and “casket-00003-of-00004” are created. To open an existing database, specify the path without the suffix. You can omit the “num_shards” parameter to open existing files.

For details of the API, see the API document of PolyDBM and ShardDBM.

Example Code

This is a code example of basic usase of PolyDBM.

 open_params = {
    {"update_mode", "UPDATE_APPENDING"},
    {"max_page_size", "1000"}, {"max_branches", "128"},
    {"key_comparator", "DecimalKeyComparator"},
  };
  dbm.OpenAdvanced("casket.tkt", true, File::OPEN_TRUNCATE, open_params).OrDie();
  
  // Stores records.
  dbm.Set("1", "one").OrDie();
  dbm.Set("2", "two").OrDie();
  dbm.Set("3", "three").OrDie();

  // Rebuild the database.
  const std::map<:string std::string=""> rebuild_params = {
    {"update_mode", "UPDATE_IN_PLACE"},
    {"max_page_size", "4080"}, {"max_branches", "256"},
  };
  dbm.RebuildAdvanced(rebuild_params).OrDie();

  // Retrieves records.
  std::cout 

This is a code example of basic usase of ShardDBM.

 open_params = {
    {"num_shards", "10"},
    {"dbm", "TreeDBM"}, {"key_comparator", "DecimalKeyComparator"},
  };
  dbm.OpenAdvanced("casket", true, File::OPEN_TRUNCATE, open_params).OrDie();
  
  // Stores records.
  for (int32_t i = 1; i Jump("50");
  std::string key, value;
  while (iter->Get(&key, &value).IsOK()) {
    std::cout Next();
  }
  
  // Closes the database.
  dbm.Close().OrDie();

  return 0;
}
]]>

AsyncDBM: Asynchronous Database Manager Adapter

Database operations can take time because of file I/O operations done inside. So, a thread calling DBM methods can block for a while. If you want to avoid blocking of the current thread, using the asynchronous API is useful. The class AsyncDBM is a wrapper of the normal synchronous API of the DBM interface. Thus, any concrete class of DBM can be used asynchronously. AsyncDBM has a task queue handled by a thread pool. When you call an asynchronous method, the operation is registered as a task in the task queue. The thread pool monitoring the task queue detects tasks and the operations are done in the background by some threads simultaneously. The main thread never blocks just for registering database operations.

Each asynchronous methods returns a std::future object. If you want to wait for a database operation to finish, you can call the “wait” or “wait_for” methods of the future object. You can get the result of the database operation by calling the “get” method of the future object. If you are not interested in the result of the database operation, you can ignore the future object without waiting or evaluating the result. The destructor of the AsyncDBM object assures that all pending tasks are done and all threads in the thread pool are joined.

Generally speaking, asynchronous API is not for improving the throughput because serializing tasks in the task queue and notifying its update to worker threads has a certain overhead. To improve throughput, you should create and use multi threads yourself to handle divided subtasks concurrently. Meanwhile, asynchronous API is useful for interactive features, where blocking of the current thread should be avoided. You use the TaskQueue class to execute arbitrary tasks in the background. The task queue instance used inside the AsyncDBM instance can be obtained by the GetTaskQueue method.

You can use std::async to execute an arbitrary function in the background. It also returns std::future to wait for the operation to finish and evaluate the result. So, the semantics are almost the same between AsyncDBM and std::async. However, std::async creates a new thread for each operation, which deteriorates performance and throughput. Therefore, AsyncDBM manages a thread pool where the same threads are reused again and again. Whereas the maximum throughput of std::async is less than 100,000 QPS, the maximum throughput of the TaskQueue class is more than 2,000,000 QPS. However, serializing parameters for various operations to put them in the task queue is a cumbersome to implement. AsyncDBM encapsulates such complex details, you can easily implement asynchronous database operations without deep knowledge of multi threading.

Example Code

This is a code example of basic usase of AsyncDBM.

(File|Mem)Index: Secondary Indices

HashDBM is the fastest file database in theory and in practice. Its performance is stable and it tolerates frequent and concurrent updates. However, it is an unordered database so it supports only exact matching of the key. In other words, it doesn’t support range search or forward matching search, which ordered databases support. Moreover, compared with relational databases, the interface of DBM is simple and it can find records only by the primary key. However, combining HashDBM and secondary indices is a practical solution to demands for high performance and complex structure.

You store the main entity data with HashDBM so that you get performance and durability. The key is a unique string which is considered as the primary key of a relational database. The value is a serialized complex data structure in a format like JSON and Protocol Buffers. You make on-memory indices for some fields of the main entity so that you can search the database for records whose specific fields match some conditions.

Typically, an index means an inverted structure made from the main database. The key of the index is composed of two factors: pattern for matching and the primary key of a record in the main database. Let’s say, you build a database for employees. The primary key is the employee ID so the main database uses the employee ID as the key. The value is a data structure composed of a personal name, a division ID, a job title, salary etc. You make an index for division IDs because you want to know who are working for each division quickly without scanning the whole database for each query. Then, each record of the index should be composed of a division ID and an employee ID.

FileIndex is a class to handle a secondary index on file. It is implemented with the file tree database. MemIndex is a class to handle a secondary index on memory. It is implemented with the on-memory tree database. And, StdIndex is a template class to realize secondary indices by wrapping std::set> composed of arbitrary data types.

For the division ID index, the first element can be int64_t for the division ID and the second element can be int64_t for the employee ID. Therefore, using StdIndex is a good idea. By having the primary key of the main database as the second element, each record becomes unique and you don’t have to worry about duplication. You can also set an arbitrary comparator to adjust the order of records.

Secondary indices are not important data to be perpetuated on the storage because they can be reproduced as long as the main entity data exist. Therefore, using some of memory indices is a practical solution to realize extreme throughput. To use on-memory indices, you have to load all index entries from the main database every time when the process starts.

For details of the API, see the API document of FileIndex and MemIndex.

Example Code

This code represents an advanced usage of HashDBM with FileIndex, which allows for finding employees by the division ID.

 fields = StrSplit(serialized, "t");
    if (fields.size()  0) {
        division_index_->Remove(ToString(old_record.division_id), key);
      }
      // If the new name is empty, removes the record.
      if (employee_.name.empty()) {
        return REMOVE;
      }
      // Adds an entry for the new record.
      if (employee_.division_id > 0) {
        division_index_->Add(ToString(employee_.division_id), key);
      }
      // Updates the record.
      new_value_ = employee_.Serialize();
      return new_value_;
    }
    // This is called if there is no existing record of the key.
    std::string_view ProcessEmpty(std::string_view key) override {
      // If the new name is empty, nothing is done.
      if (employee_.name.empty()) {
        return NOOP;
      }
      // Adds an entry for the new record.
      if (employee_.division_id > 0) {
        division_index_->Add(ToString(employee_.division_id), key);
      }
      // Updates the record.
      new_value_ = employee_.Serialize();
      return new_value_;
    }
   private:
    const Employee& employee_;
    FileIndex* division_index_;
    std::string new_value_;
  } updater(employee, division_index);
  dbm->Process(primary_key, &updater, true).OrDie();
}

// Main routine.
int main(int argc, char** argv) {

  // Creates the database manager.
  HashDBM dbm;

  // Prepare an index for divisions and their members.
  FileIndex division_index;

  // Opens a new database,
  dbm.Open("casket.tkh", true, File::OPEN_TRUNCATE).OrDie();

  // Opens a new index.
  // Setting PairDecimalKeyComparator is to sort the division ID in numeric order.
  // Otherwise, "10" would come earlier than "2" in lexical order.
  TreeDBM::TuningParameters division_index_params;
  division_index_params.key_comparator = PairDecimalKeyComparator;
  Status status = division_index.Open(
      "casket-division-index.tkt", true, File::OPEN_TRUNCATE, division_index_params);

  // Register employee records.
  const std::vector employees = {
    {10001, "Anne", 301}, {10002, "Marilla", 301}, {10003, "Matthew", 301},
    {10004, "Diana", 401},
    {10005, "Gilbert", 501},
  };
  for (const Employee& employee : employees) {
    UpdateEmployee(employee, &dbm, &division_index);
  }

  // Closes the index.
  division_index.Close().OrDie();
  
  // Closes the database.
  dbm.Close().OrDie();

  // Opens an existing database,
  dbm.Open("casket.tkh", true).OrDie();

  // Opens an existing index,
  division_index.Open("casket-division-index.tkt", true).OrDie();

  // Updates for employees.
  const std::vector updates = {
    {10001, "Anne", 501},  // Anne works with Gilbert.
    {10003, "", 0},        // Matthew left the company.
    {10006, "Minnie May", 401},
    {10007, "Davy", 301}, {10008, "Dora", 301},
  };
  for (const Employee& employee : updates) {
    UpdateEmployee(employee, &dbm, &division_index);
  }

  // Prints members for each division.
  for (const int64_t division_id : {301, 401, 501}) {
    std::cout 

Let’s do the same thing as the above with StdIndex instead of FileIndex. We scan the main database when the process starts in order to build the on-memory secondary index.

 DivisionIndex;

// Structure for an employee.
// Actually, you should use a serious implementation like Protocol Buffers.
struct Employee {
  int64_t employee_id = 0;
  std::string name;
  int64_t division_id = 0;
  std::string Serialize() const {
    return StrCat(employee_id, "t", name, "t", division_id);
  }
  void Deserialize(const std::string_view& serialized) {
    const std::vector<:string> fields = StrSplit(serialized, "t");
    if (fields.size() Add(employee.division_id, key_num);
      return NOOP;
    }
   private:
    DivisionIndex* division_index_;
  } index_builder(division_index);
  dbm->ProcessEach(&index_builder, false).OrDie();
}

// Updates information of an employee.
// If the name is empty, the entry is removed.
void UpdateEmployee(const Employee& employee, DBM* dbm, DivisionIndex* division_index) {
  const std::string& primary_key = ToString(employee.employee_id);
  class Updater : public DBM::RecordProcessor {
   public:
    Updater(const Employee& employee, DivisionIndex* division_index)
        : employee_(employee), division_index_(division_index) {
    }
    // This is called if there is an existing record of the key.
    std::string_view ProcessFull(std::string_view key, std::string_view value) override {
      const int64_t key_num = StrToInt(key);
      Employee old_record;
      old_record.Deserialize(value);
      // Removes an entry for the existing record.
      if (old_record.division_id > 0) {
        division_index_->Remove(old_record.division_id, key_num);
      }
      // If the new name is empty, removes the record.
      if (employee_.name.empty()) {
        return REMOVE;
      }
      // Adds an entry for the new record.
      if (employee_.division_id > 0) {
        division_index_->Add(employee_.division_id, key_num);
      }
      // Updates the record.
      new_value_ = employee_.Serialize();
      return new_value_;
    }
    // This is called if there is no existing record of the key.
    std::string_view ProcessEmpty(std::string_view key) override {
      const int64_t key_num = StrToInt(key);
      // If the new name is empty, nothing is done.
      if (employee_.name.empty()) {
        return NOOP;
      }
      // Adds an entry for the new record.
      if (employee_.division_id > 0) {
        division_index_->Add(employee_.division_id, key_num);
      }
      // Updates the record.
      new_value_ = employee_.Serialize();
      return new_value_;
    }
   private:
    const Employee& employee_;
    DivisionIndex* division_index_;
    std::string new_value_;
  } updater(employee, division_index);
  dbm->Process(primary_key, &updater, true).OrDie();
}

// Main routine.
int main(int argc, char** argv) {

  // Creates the database manager.
  HashDBM dbm;

  // Prepare an index for divisions and their members.
  DivisionIndex division_index;

  // Opens a new database,
  dbm.Open("casket.tkh", true, File::OPEN_TRUNCATE).OrDie();

  // After opening the database, indices should be loaded.
  // As the database is empty at this point, there's no effect here.
  LoadIndexRecords(&dbm, &division_index);

  // Register employee records.
  const std::vector employees = {
    {10001, "Anne", 301}, {10002, "Marilla", 301}, {10003, "Matthew", 301},
    {10004, "Diana", 401},
    {10005, "Gilbert", 501},
  };
  for (const Employee& employee : employees) {
    UpdateEmployee(employee, &dbm, &division_index);
  }

  // Closes the database.
  dbm.Close().OrDie();

  // Opens an existing database,
  dbm.Open("casket.tkh", true).OrDie();

  // After opening the database, indices should be loaded.
  // All existing records are reflected on the index.
  LoadIndexRecords(&dbm, &division_index);

  // Updates for employees.
  const std::vector updates = {
    {10001, "Anne", 501},  // Anne works with Gilbert.
    {10003, "", 0},        // Matthew left the company.
    {10006, "Minnie May", 401},
    {10007, "Davy", 301}, {10008, "Dora", 301},
  };
  for (const Employee& employee : updates) {
    UpdateEmployee(employee, &dbm, &division_index);
  }

  // Prints members for each division.
  for (const int64_t division_id : {301, 401, 501}) {
    std::cout 

C Language Interface

The C++ API cannot be use directly in C code. So, the C interface is provided as a wrapper of PolyDBM and ShardDBM. Those adapter classes absorb differences among concrete database classes so you can use HashDBM, TreeDBM, SkipDBM and other databases in C code. The C interface is useful to embed the functionality to other languages which provide bridging interface for C but not for C++. As the name mangling feature of C++ sometimes hinders simple integration.

You can create the database object and open a database by calling the tkrzw_dbm_open function. It returns the pointer to a TkrzwDBM object. Most methods of PolyDBM and ShardDBM in C++ have their counterparts in the C interface. For methods of the database object, there are counterpart functions whose names begin with “tkrzw_dbm_” and they receive the pointer to a TkrzwDBM object as the first parameter. An iterator object is created by calling the tkrzw_dbm_make_iterator function. For methods of the iterator object, there are counterpart functions whose name begins with “tkrzw_dbm_iter_” and they receive the pointer to a TkrzwDBMIter object as the first parameter.

The generic file functions are also useful to handle flat files. They are wrapper of PolyFile class in C++. You can use files in the memory mapping I/O mode, the normal I/O mode, and the direct I/O mode with the same interface. Their names begin with “tkrzw_file_” and they receive the pointer to a TkrzwFile object as the first parameter.

The status of last called database operation or file operation is stored as a thread-local variable. You can get it with “tkrzw_get_last_status” function.

The library header is based on the C99 and C11 standards. On UNIX-like systems, typically, your program is built like this:

On Windows, typically, your program is built like this:

 cl /std:c11 
  /I "C:Program Files (x86)tkrzwinclude" 
  /O2 /EHsc /W3 /MT helloworld.c tkrzw.lib /OUT:helloworld.exe 
  /link /libpath:"C:Program Files (x86)tkrzwlib"
]]>

For details of the API, see the API document for details.

Example Code

You can use a hash database by the following code.

#include "tkrzw_langc.h"

// Main routine.
int main(int argc, char** argv) {
  // Opens the database file.
  TkrzwDBM* dbm = tkrzw_dbm_open(
      "casket.tkh", true, "truncate=true,num_buckets=100");
  
  // Stores records.
  tkrzw_dbm_set(dbm, "foo", -1, "hop", -1, true);
  tkrzw_dbm_set(dbm, "bar", -1, "step", -1, true);
  tkrzw_dbm_set(dbm, "baz", -1, "jump", -1, true);

  // Retrieves a record.
  char* value_ptr = tkrzw_dbm_get(dbm, "foo", -1, NULL);
  if (value_ptr) {
    puts(value_ptr);
    free(value_ptr);
  }

  // Traverses records.
  TkrzwDBMIter* iter = tkrzw_dbm_make_iterator(dbm);
  tkrzw_dbm_iter_first(iter);
  while (true) {
    char* key_ptr = NULL;
    if (!tkrzw_dbm_iter_get(iter, &key_ptr, NULL, &value_ptr, NULL)) {
      break;
    }
    printf("%s:%sn", key_ptr, value_ptr);
    free(key_ptr);
    free(value_ptr);
    tkrzw_dbm_iter_next(iter);
  }
  tkrzw_dbm_iter_free(iter);
  
  // Closes the database file.
  tkrzw_dbm_close(dbm);

  return 0;
}
]]>

Note that every created TkrzwDBM object should be closed by the tkrzw_dbm_close function. Every regions allocated by tkrzw_dbm_get, tkrzw_dbm_iter_get and other functions should be released by the free function. Every created TkrzwDBMIter object should be released by the tkrzw_dbm_iter_free function.

Command Line Utilities

tkrzw_build_util: Build Utilities

tkrzw_build_util is a command for build utilities. Thereby, you can obtain flags to build your own program using the library of Tkrzw. The usage is the following. A subcommand name comes as the first argument. Some options and other arguments can follow.

tkrzw_build_util config [options]

Prints configurations.

tkrzw_build_util version

Prints the version information.

Options of the config subcommand:

-v : Prints the version number.

-i : Prints C++ preprocessor options for build.

-l : Prints linker options for build.

-p : Prints the prefix for installation.

The following is a way to build your own application without setting complicated flags.

tkrzw_dbm_util: DBM Utilities

tkrzw_dbm_util is a command for managing database files. Thereby, you can create databases, set records, retrieve records, remove records, rebuild databases, and restore databases. The usage is the following. A subcommand name comes as the first argument. Some options and other arguments can follow.

tkrzw_dbm_util create [common_options] [tuning_options] [options] file

Creates a database file.

tkrzw_dbm_util inspect [common_options] file [attr]

Prints inspection of a database file.

tkrzw_dbm_util get [common_options] file key

Gets a record and prints it.

tkrzw_dbm_util set [common_options] [options] file key

Sets a record.

tkrzw_dbm_util remove [common_options] file key

Removes a record.

tkrzw_dbm_util rekey [common_options] file old_key new_key

Changes the key of a record.

tkrzw_dbm_util list [common_options] file

Lists up records and prints them.

tkrzw_dbm_util rebuild [common_options] [tuning_options] file

Rebuilds a database file for optimization.

tkrzw_dbm_util restore [common_options] old_file [new_file]

Restores a broken database file.

tkrzw_dbm_util merge [common_options] dest_file src_files...

Merges database files.

tkrzw_dbm_util export [common_options] [options] dbm_file rec_file

Exports records to a flat record file.

tkrzw_dbm_util import [common_options] [options] dbm_file rec_file

Imports records from a flat record file.

Common options:

--dbm impl : The name of a DBM implementation: auto, hash, tree, skip, tiny, baby, cache, stdhash, stdtree, poly, shard. (default: auto)

--file impl : The name of a file implementation: std, mmap-para, mmap-atom, pos-para, pos-atom. (default: mmap-para)

--no_wait : Fails if the file is locked by another process.

--no_lock : Omits file locking.

--sync_hard : Synchronizes the file physically when closing.

--alloc_init num : The initial allocation size. (default: 1048576)

--alloc_inc num : The allocation increment factor. (default: 2.0)

--block_size num : The block size of the positional access file. (default: 1)

--direct_io : Enables the direct I/O option of the positional access file.

--sync_io : Enables the synchronous I/O option of the positional access file.

--padding : Enables padding at the end of the file.

--pagecache : Enables the mini page cache in the process.

--multi : Calls xxxMulti methods for get, set, and remove subcommands.

Options for the create subcommand:

--truncate : Truncates an existing database file.

Options for the inspect subcommand:

--validate : Validates records.

Options for the set subcommand:

--no_overwrite : Fails if there’s an existing record with the same key.

--append str : Appends the value at the end after the given delimiter.

--incr num : Increments the value with the given initial value.

--reducer func : Sets the reducer for the skip database: none, first, second, last, concat, concatnull, concattab, concatline, total. (default: none)

Options for the rekey subcommand:

--no_overwrite : Fails if there’s an existing record with the same key.

Options for the list subcommand:

--move type : Type of movement: first, jump, jumplower, jumplowerinc, jumpupper, jumpupperinc. (default: first)

--jump_key str : Specifies the jump key. (default: empty string)

--items num : The number of items to print (default: 10).

--escape : C-style escape is applied to the TSV data.

--keys : Prints keys only.

Options for the rebuild subcommand:

--restore : Skips broken records to restore a broken database.

Options for the merge subcommand:

--reducer func : Sets the reducer for the skip database: none, first, second, last, concat, concatnull, concattab, concatline, total. (default: none)

Options for the restore subcommand:

--auto str : The restore mode automatically done: none, default, default-ns, sync, sync-ns. (default: none)

--end_offset : The exclusive end offset of records to read. (default: -1)

--class : The class name given to PolyDBM or ShardDBM.

Options for the export and import subcommands:

--tsv : The record file is in TSV format instead of flat record.

--escape : C-style escape/unescape is applied to the TSV data.

--keys : Exports keys only.

--ulog num : Uses update logs based on the timestamp.

--ulog_ids num num : Sets the server ID and the DBM index of update logs.

Tuning options for HashDBM:

--in_place : Uses in-place rather than pre-defined ones.

--append : Uses the appending mode rather than the in-place mode.

--record_crc num : The record CRC mode: -1, 0, 8, 16, 32. (default: 0 or -1)

--record_comp str : The record compression mode: default, none, zlib, zstd, lz4, lzma. (default: none or default)

--offset_width num : The width to represent the offset of records. (default: 4 or -1)

--align_pow num : Sets the power to align records. (default: 3 or -1)

--buckets num : Sets the number of buckets for hashing. (default: 1048583 or -1)

Tuning options for TreeDBM:

--in_place : Uses in-place rather than pre-defined ones.

--append : Uses appending rather than pre-defined ones.

--record_crc num : The record CRC mode: -1, 0, 8, 16, 32. (default: 0 or -1)

--record_comp str : The record compression mode: default, none, zlib, zstd, lz4, lzma. (default: none or default)

--offset_width num : The width to represent the offset of records. (default: 4 or -1)

--align_pow num : Sets the power to align records. (default: 10 or -1)

--buckets num : Sets the number of buckets for hashing. (default: 131101 or -1)

--max_page_size num : Sets the maximum size of a page. (default: 8130 or -1)

--max_branches num : Sets the maximum number of branches of inner nodes. (default: 256 or -1)

--comparator func : Sets the key comparator: lex, lexcase, dec, hex, real. (default: lex)

Tuning options for SkipDBM:

--offset_width num : The width to represent the offset of records. (default: 4)

--step_unit num : Sets the step unit of the skip list. (default: 4)

--max_level num : Sets the maximum level of the skip list. (default: 14)

--sort_mem_size num : Sets the memory size used for sorting. (default: 268435456)

--insert_in_order : Inserts records in ascending order of the key.

Options for PolyDBM and ShardDBM:

--params str : Sets the parameters in “key=value,key=value” format.

The following is a sample usage to make a hash database file to associate country names to their capital cities’ names. If the extension of the file is “tkh”, the type of the database is regarded as HashDBM.

Let’s say, you have a dictionary in TSV format. The first field is an index word and the second field is its description. Then, make a skip database of the dictionary. If the extension of the file is “tks”, the type of the database is regarded as SkipDBM.

You can look up words which forward-match a pattern.

tkrzw_dbm_perf: DBM Performance Checker

tkrzw_dbm_perf is a command for checking performance of DBM implementations. Thereby, you can check performance of database operations in various scenarios including multithreading. The usage is the following. A subcommand name comes as the first argument. Some options and other arguments can follow.

tkrzw_dbm_perf sequence [options]

Checks setting/getting/removing performance in sequence.

tkrzw_dbm_perf parallel [options]

Checks setting/getting/removing performance in parallel.

tkrzw_dbm_perf wicked [options]

Checks consistency with various operations.

tkrzw_dbm_perf index [options]

Checks performance of on-memory indexing.

Common options:

--dbm impl : The name of a DBM implementation: auto, hash, tree, skip, tiny, baby, cache, stdhash, stdtree, poly, shard. (default: auto)

--iter num : The number of iterations. (default: 10000)

--size num : The size of each record value. (default: 8)

--threads num : The number of threads. (default: 1)

--random_seed num : The random seed or nagative for real RNG. (default: 0)

--verbose : Prints verbose reports.

--path path : The path of the file to write or read.

--file impl : The name of a file implementation: std, mmap-para, mmap-atom, pos-para, pos-atom. (default: mmap-para)

--no_wait : Fails if the file is locked by another process.

--no_lock : Omits file locking.

--sync_hard : Synchronizes the file physically when closing.

--alloc_init num : The initial allocation size. (default: 1048576)

--alloc_inc num : The allocation increment factor. (default: 2.0)

--block_size num : The block size of the positional access file. (default: 1)

--direct_io : Enables the direct I/O option of the positional access file.

--sync_io : Enables the synchronous I/O option of the positional access file.

--padding : Enables padding at the end of the file.

--pagecache : Enables the mini page cache in the process.

--ulog str : Sets the prefix of update log files.

Options for the sequence subcommand:

--random_key : Uses random keys rather than sequential ones.

--random_value : Uses random length values rather than fixed ones.

--set_only : Does only setting.

--get_only : Does only getting.

--iter_only : Does only iterating.

--remove_only : Does only removing.

--validate : Validates records.

Options for the parallel subcommand:

--random_key : Uses random keys rather than sequential ones.

--random_value : Uses random length values rather than fixed ones.

--keys : The number of unique keys.

--rebuild : Rebuilds the database occasionally.

--sleep num : The duration to sleep between iterations. (default: 0)

--validate : Validates records.

Options for the wicked subcommand:

--iterator : Uses iterators occasionally.

--clear : Clears the database occasionally.

--rebuild : Rebuilds the database occasionally.

--validate : Validates records.

Options for the index subcommand:

--type expr : The types of the key and value of the index: file, mem, n2n, n2s, s2n, s2s, str. (default: file)

--random_key : Uses random keys rather than sequential ones.

--random_value : Uses random length values rather than fixed ones.

Options for HashDBM:

--append : Uses appending rather than pre-defined ones.

--record_crc num : The record CRC mode: -1, 0, 8, 16, 32. (default: 0 or -1)

--record_comp str : The record compression mode: default, none, zlib, zstd, lz4, lzma. (default: none or default)

--offset_width num : The width to represent the offset of records. (default: 4)

--align_pow num : Sets the power to align records. (default: 3)

--buckets num : Sets the number of buckets for hashing. (default: 1048583)

--fbp_cap num : Sets the capacity of the free block pool. (default: 2048)

--min_read_size num : Sets the minimum reading size to read a record. (default: -1)

--cache_buckets : Caches the hash buckets on memory.

Options for TreeDBM:

--append : Uses the appending mode rather than the in-place mode.

--record_crc num : The record CRC mode: -1, 0, 8, 16, 32. (default: 0 or -1)

--offset_width num : The width to represent the offset of records. (default: 4)

--align_pow num : Sets the power to align records. (default: 10)

--buckets num : Sets the number of buckets for hashing. (default: 131101)

--fbp_cap num : Sets the capacity of the free block pool. (default: 2048)

--min_read_size num : Sets the minimum reading size to read a record. (default: -1)

--cache_buckets : Caches the hash buckets on memory.

--max_page_size num : Sets the maximum size of a page. (default: 8130)

--max_branches num : Sets the maximum number of branches of inner nodes. (default: 256)

--max_cached_pages num : Sets the maximum number of cached pages. (default: 10000)

Options for SkipDBM:

--offset_width num : The width to represent the offset of records. (default: 4)

--step_unit num : Sets the step unit of the skip list. (default: 4)

--max_level num : Sets the maximum level of the skip list. (default: 14)

--sort_mem_size num : Sets the memory size used for sorting. (default: 268435456)

--insert_in_order : Inserts records in ascending order of the key.

--max_cached_records num : Sets the number of cached records (default: 65536)

--reducer func : Sets the reducer: none, first, second, last, concat, total. (default: none)

Options for TinyDBM and StdHashDBM:

--buckets num : Sets the number of buckets for hashing. (default: 1048583)

Options for CacheDBM:

--cap_rec_num num : Sets the maximum number of records. (default: 1048576)

--cap_mem_size num : Sets the total memory size to use.

Options for PolyDBM and ShardDBM:

--params str : Sets the parameters in “key=value,key=value” format.

The following is a sample usage to make a hash database file and then store 1 million records of 8-byte keys and 8-byte values, retrieve all of them, and remove all of them in sequence. The number of threads is 10 and each thread handles 100 thousand records. The number of buckets is 2 million.

The following is a sample usage to make a skip database file and then store 1 million records of 8-byte keys and 8-byte values, retrieve all of them. The number of threads is 10 and each thread handles 100 thousand records. The step unit and the maximum level of the skip list are 3 and 13 respectively.

tkrzw_ulog_util: Update Logging Utilities

tkrzw_ulog_util is a command for managing update log files. Thereby, you can add update logs, inspect update logs, list up files, and remove old files. The usage is the following. A subcommand name comes as the first argument. Some options and other arguments can follow.

tkrzw_ulog_util writeset [options] prefix key value

Writes a SET operation.

tkrzw_ulog_util writeremove [options] prefix key

Writes a REMOVE operation.

tkrzw_ulog_util writeclear [options] prefix

Writes a CLEAR operation.

tkrzw_ulog_util read [options] prefix

Reads each log.

tkrzw_ulog_util listfiles [options] prefix

Lists log files.

tkrzw_ulog_util removeoldfiles [options] prefix

Removes old log files.

Options for the write subcommands:

--timestamp num : The timestamp to record. (default: current time)

--max_file_size num : The maximum file size. (default: 1Gi)

--server_id num : The server ID to record. (default: 0)

--dbm_index num : The DBM index to record. (default: 0)

Options for the read subcommand:

--timestamp num : The timestamp to start at (default: 0)

--server_id num : The server ID to focus on. (default: all)

--dbm_index num : The DBM index to focus on. (default: all)

--items num : The number of items to print. (default: 10)

--escape : C-style escape is applied to the TSV data.

Options for the listfiles subcommand:

--timestamp num : The timestamp to start at (default: 0)

Options for the removeoldfiles subcommand:

--timestamp num : The timestamp of threshold. (default: -7D = 7 days ago)

--exclude_latest : Avoid removing the latest file.

The following is a sample usage to make a file of update logs to write three records and apply it to a database.

To remove old update logs, you run the “removeoldfiles” subcommand. The “–timestamp” option can take a relative time from the current time with a value beginning with “+” or “-“. And the value can have a suffix for the unit: “D” for days, “H” for hours, “M” for minutes, and “S” for seconds. No unit means milliseconds. It is a good manner not to remove the latest file regardless of its age. If you remove files which are older than 2 days from now exclusing the latest one, you run the following. Don’t forget “-“.

Tips

Tuning HashDBM

The file hash database uses a static hash table, whose size doesn’t change implicitly. The number of hash buckets is set when the database is created. The load factor, which is defined as the ratio of the number of records to the number of buckets, should be less than 1, in order to maintain a good performance. So, the number of buckets should be larger than the estimated number of records. By default, the number of buckets is about 1 million.

To create a very small database, you’ll run a command like this.

The same thing can be done in C++.

To make a very large database, you’ll set offset_width=5, align_pow=4, and num_buckets=100000000 or something.

When the load factor exceeds 1 and performance decreases, you’ll rebuild the database. By default, the number of buckets is set as twice as the number of records so that the load factor becomes 0.5.

The same thing can be done in C++. The RebuildAdvanced method can take tuning parameters so that you can specify them explicitly.

One of the most important features of Tkrzw’s file hash database is that the operation to rebuild the database doesn’t block other threads trying to update the database. Rebuilding is done by making a temporary database file while accepting updates to the original file. When the rebuilding is done, updates during the rebuilding are applied to the new file incrementally and then the original file is replaced with the new file atomically. All these operations are done just by calling the Rebuild method by a dedicated thread.

Rebuilding the database is also effective to resolve data fragmentation. The file hash database has a metadata property of effective data size, which is the total size of keys and values of all records. When the effective data size is less than 30% of the file size, it’s time to rebuild the database. To know whether the database should be rebuilt, you’ll run a command like this.

The same thing can be done in C++.

Alignment is effective to mitigate fragmentation when the size of the value of records are changed frequently. By default, the alignment is set 2^3 = 8 bytes so that every records begins at an offset which is a multiple of 8. If the record size is not a multiple of 8, padding bytes are put at the end. If the size of a record increases but the padding can contain the increment, the record don’t have to be moved to another place. If the record is moved, the original position region becomes a free block. In the in-place update mode, the free block can be reused but it is not assured. Having 8-byte alignment means that the expected size of padding is 4 bytes. If the typical record size is 30 bytes or something, 4 bytes padding seems acceptable and effective.

The position of each record is represented by a 4-byte integer by default. It means that the maximum value is 4^32 = 4GiB. Actually, the position is calculated as the value multiplied by the alignment. So, the maximum size is 4GiB * 8 = 32GiB by default. If the database size is about to exceed the limit, you should rebuild the database with an increased offset width. Usually, 5-byte integer will do because it can represent up to 1TiB. Alignment is not useful for the appending mode. And, databases in the appending mode tend to be very large. Therefore, you’ll create a database in the appending mode like this.

By default, I/O of the file hash database file is done via memory mapping. Thus, if the size of the database file exceeds the capacity of the virtual memory, the process can crash with segmentation fault or be killed by the OOM killer. To avoid it, you can use the normal I/O system calls, by creating the database object with the specific file object. See the tips on File Classes for details. If the database file is much larger than the RAM on your machine, using direct I/O is the best practice. See Direct I/O for details. Compressing record data is useful to calibrate tradeoff of time efficiency and space efficiency. See Data Compression for details.

Update Modes of HashDBM and TreeDBM

You specify an update mode when creating or rebuilding a HashDBM or TreeDBM database by setting the update_mode tuning parameter to the OpenAdvanced or RebuildAdvanced method. The value can be UPDATE_IN_PLACE (the default) or UPDATE_APPENDING.

In-Place

In the in-place mode, an existing record is updated in-place if possible. Let’s say, there’s two records in the database, A (key=”A”, value=”aaa”) and B (key=”B”, value=”bbb”). The record section in the database file is like this. “xxx” means metadata and “…” means padding.

[xxx:A:aaa.....][xxx:B:bbb.....]

Now, the value of A is updated into “aaaaaa”. The padding can contain the additional size so the record is not moved.

[xxx:A:aaaaaa..][xxx:B:bbb.....]

The value of A is updated into “aaaaaaaaa”. The padding cannot contain the additional size so the record is moved. The original section becomes a free block.

[xxx:*:........][xxx:B:bbb.....][xxx:A:aaaaaaaaa.......]

The free block is registered in the free block pool so it is reused for a new record whose size can be contained in it. Let’s say, a new record C (key=”C”, value=”cccccc”) is added.

[xxx:C:cccccc..][xxx:B:bbb.....][xxx:A:aaaaaaaaa.......]

If a record is removed, the region for the record becomes a free block and it is reused later.

Therefore, in the in-place mode, the size of the database doesn’t increase rapidly even if records are set or deleted often. Even so, fragmentation can still gradually creep in, so you should rebuild the database occasionally.

Appending

Meanwhile, in the appending mode, we never write to the existing region, which is the region of the file where records have already been stored. There is no free block pool, and space for removed records is never reused.

Let’s say the value of record A is updated from “aaa” to “aa”. A new record region is appended at the end of the file even though “aa” could fit in the old space.

[xxx:A:aaa][xxx:B:bbb][xxx:A:aa]

If A is removed, a new record region to mark it as removed is appended. This removal record stores a key, but no value:

[xxx:A:aaa][xxx:B:bbb][xxx:A:aa][xxx:A:(removed)]

Similarly, if we add a new record C with value “c”, we append a record for it rather than using the space of the removed record A:

[xxx:A:aaa][xxx:B:bbb][xxx:A:aa][xxx:A:(removed)][xxx:C:c]

So in appending mode, each updating operation appends one record to the file. These records are linked together in a chain from the most recent operation to the oldest operation. Each bucket of the hash table points to the record for the most recent operation on any record whose key falls in that bucket. For example, here is what it looks like when a given hash bucket has a chain of two records and we add one more new record:

Notice how each new record gets prepended to the existing chain of records. So whenever HashDBM needs to search for a record with a given key (for example, to do a Get or Set operation), or iterate keys, HashDBM will encounter the most recent records first. That is how HashDBM can correctly fetch the most recent value for a key even if that key’s value has been set multiple times, and correctly determine that a previously-added key has been removed.

Because one record gets appended for each updating operation, the size of the database file increases rapidly if you update a lot, even if you repeatedly update the same key. Furthermore, after many update operations, the chain of records for a given hash bucket grows longer and longer, and so that potentially slows down most Tkrzw operations.

So, it is very important to rebuild the database periodically to save space and restore good performance. Tkrzw lets you rebuild a live database (from a background thread, if you desire) while it is still in use.

By now you may be thinking that the appending mode is totally crazy. But it has two major advantages over the in-place mode: durability and updating performance. Because appending mode never modifies the existing area, the existing information is never lost. This lets us provide stronger durability guarantees in case of an operating system crash or power failure. See ACID Transaction for details.

You might think that the in-place mode is faster and that the appending mode is slower. However, it is not the case necessarily. In the in-place mode, updated “dirty” pages of the I/O buffer scatter across the database file so that effectiveness of synchronizing the dirty pages with the device is low. Meanwhile, in the appending mode, dirty pages occur only at end of the file so that effectiveness of synchronizing the dirty pages with the device is high. In other words, a database in the appending mode causes inefficient reading with random access but it causes efficient writing with sequential access. Therefore, if rebuilding the database is done at a reasonable frequency, the appending mode can be faster than the in-place mode. SSD devices are good at random reading but not good at random writing. Especially if you build a huge database on an SSD storage, the appending mode is worth considering.

Performance Comparison

Let’s build a hash database and store 100 million records (10 million for each of 10 threads). And then retrieve and remove all of them. First, we check performance of the in-place mode.

On my environment, setting operations took 48 seconds, which meant 2.0 million QPS. Getting operations took 25 seconds, which meant 3.9 million QPS. And, removing operations took 83 seconds, which meant 1.2 million QPS. The file size was 2.9GiB. Removing operations took longer time than setting operations because removing existing records requires random access writing to reorganize bucket chains. Then, let’s do the same thing in the appending mode.

This time, setting operations took 44 seconds, which meant 2.2 million QPS. Getting operations took 26 seconds, which meant 3.8 million QPS. And, removing operations took 54 seconds, which meant 1.8 million QPS. The file size was 4.5GiB. Throughput of setting and getting operations in this setting should be the same between the in-place mode and the appending mode. However, removing operations in the appending mode should be faster than the in-place mode because appending causes only sequential writing.

Tuning TreeDBM

The file tree database uses B+ tree. Records are organized in ascending order of the key. Records at adjacent positions are chunked as a unit called “page”. The larger each page is, the better space efficiency is. And, performance of sequential access is also better. Meanwhile, performance of random access deteriorates if pages are too big. The default maximum page size 8130 is suitable in most cases.

If the machine has abundant memory, increasing the max_cached_pages parameter contributes better performance of random access. By default, 10,000 pages are cached. The average page size is about 8K bytes so 80MB memory is used for the cache system. Let’s say, the machine has 2GB free memory. Then, specifying 200,000 or something is feasible.

Usually, there’s no need to modify the default tuning parameters. By default, the maximum database size is 1TB because the offset width is 4 and the alignment power is 8. If the number of records exceeds 20 million, the num_buckets parameter should be increased for better performance.

To create a very small database, you’ll run a command like this.

The same thing can be done in C++.

To make a very large database which are accessed at random, you’ll set align_pow=12 and max_page_size=4080. Due to the alignment power, every hash record is aligned at a multiple of 4096 bytes, which maximize efficiency of the underlying I/O system. As the maximum page size doesn’t include footprint of the hash record of 16 bytes, 4096 – 16 = 4080 is the ideal size. Note that 4080 is the maximum size so the actual usage is less than it. However, having padding space is beneficial to mitigate movement of page positions. Increasing the max_cached_pages is also better as long as the memory capacity allows for it.

Let’s say, there is a leaf page containing only one small record. If the alignment is 4096 bytes, most space is filled with padding bytes.

[XXX:A:aaa............................]

Some records are inserted into the leaf page. If the total page size doesn’t exceed the allocated size, the page doesn’t have to reallocated.

[XXX:A:aaa:B:bbb:C:ccc:D:ddd..........]

If a new record is added to the leaf page and the total page size exceeds the allocated size, the page is reallocated and the original position becomes a free space.

[XXX:*********************************][XXX:A:aaa:B:bbb:C:ccc:D:ddd:E:eee:F:fff:G:ggg:H:hhh:I:iii...]

However, if the maximum page size setting is less than the alignment size, the page is divided and it avoids reallocation. Half of records are moved to a new page. Therefore, having a large alignment and setting the maximum page size a bit less than the alignment pay in the long run.

[XXX:A:aaa:B:bbb:C:ccc:D:ddd:E:eee:...][XXX:F:fff:G:ggg:H:hhh:I:iii..........]

In case that the cache cannot contain all records, however you tune the tree database, performance of random access cannot be comparable to the file hash database. Thus, if you don’t need ordered record access, using the file hash database is recommended. If you need ordered record access and updating is done at random, consider using the file skip database, which is more scalable.

By default, I/O of the file tree database file is done via memory mapping. Thus, if the size of the database file exceeds the capacity of the virtual memory, the process can crash with segmentation fault or be killed by OOM killer. To avoid it, you can use by the normal I/O system calls, by creating the database object with the specific file object. See the tips on File Classes for details. If the database file is much larger than the RAM on your machine, using direct I/O is the best practice. See Direct I/O for details. Compressing record data is useful to calibrate tradeoff of time efficiency and space efficiency. See Data Compression for details.

Comparators of TreeDBM

By default, the file tree database uses a lexical comparator which compares keys in lexicographical order. This is suitable for many use cases. If you want to use numeric values, representing a number as a big-endian binary is a good idea because the default comparator sorts it properly. However, if you want, the following built-in comparator can be specified via the tuning parameters.

• LexicalKeyComparator : Compares keys as strings in lexicographical order.
• LexicalCaseKeyComparator : Compares keys as strings but ignore cases in ASCII code.
• DecimalKeyComparator : Compares keys as decimal integers like “1” and “99”.
• HexadecimalKeyComparator : Compares keys as hexadecimal integers like “8A” and “FF3C”.
• RealNumberKeyComparator : Compares keys as decimal real numbers like “2.1” and “-5.82”.

You can implement your own comparator. In that case, you must specify it every time when you open the database.

By the way, databases other than the file skip database don’t support duplicated keys. That’s because duplicated keys deteriorate time and space efficiency. If you have to handle duplicated keys, build a skip database first and merge duplicated records. Then, you can convert it to another type of database.

Data Compression for HashDBM and TreeDBM

Data compression can be applied to the record value so that the size of the database file becomes smaller at the cost of processing time. In general, using data compression decreases performance and throughput. However, if the database file is large and I/O is the bottle neck, data compression sometimes increases performance and throughput because of lower amount of data transmission with the storage.

You can integrate the following compression libraries when you build Tkrzw.

• ZLib : Probably the most popular compression library, which is used in GZip. It combines good compression ratio and good processing speed.
• ZStd : Probably the most useful compression library. As compression ratio is almost the same as ZLib, the processing speed is much faster.
• LZ4 : A very fast compression library. Though compression ratio is worse than ZLib and ZStd, processing speed is much faster.
• LZMA : A library known for the best compression. Though compression ratio is better than ZLib and ZStd, the processing speed is much slower.

If you tune the database to enable one of those algorithms, record data stored in the database is compressed. When you retrieve the record, the data is decompressed automatically. In HashDBM, compression is done for each record and only the record value is compressed. Thus, compression is useful only if the record value is large. In TreeDBM, compression is done for each page which includes multiple records. Thus, compression is more useful in TreeDBM.

Which algorithm is the best suited should be determined according to the data size, the data content, and the access pattern. However, ZStd is the one you should try first. If ZStd is not available on your platform, you use ZLib instead. If you prefer faster speed, try LZ4. If the database is almost read-only for archival usage, try LZMA.

To check performance, let’s write and read 1 million records in HashDBM and TreeDBM. The key is a 8-byte numeric string like “00000001” and “00000002”. The value is a 100-byte semi-random alphabet strings like “cvexgzibb…”.

Tuning SkipDBM

The file skip database uses a skip list based on sorted records. Whereas its time efficiency is worse than that of the hash table, its space efficiency is better. Typically, the footprint for each record is less than 5 bytes. Usually, there’s no need to modify the default tuning parameters. If the size of the database can exceed 4GB, the offset width parameter should be set 5. If the number of records is more than 1 billion, the maximum level parameter should be set 15 or more. If the main usage of the database is for sequential access, the step unit can be 16 and the maximum level can be 8.

To create a very small database, you’ll run a command like this.

The same thing can be done in C++.

To make a very large database, you’ll set offset_width=5, step_unit=8, max_level=12, and sort_mem_size=2GB. Increasing the step_unit parameter reduces frequency of random access. Increasing the sort_mem_size parameter is a good idea because the default value is 256MB.

If you want to optimize the time/space efficiency by all means, rebuilding the database might help because optimal parameters are set implicitly.

The same thing can be done in C++. The RebuildAdvanced method can take tuning parameters so that you can specify them explicitly.

Rebuilding the database blocks other threads completely. In the first place, the file skip database is not suitable for random updates. Use the file hash database for that purpose. The skip list database is suitable for batch processing.

Although the file skip database uses much resources to build the database file, space efficiency of the database file is the best. Therefore, it is practical to build a large database on a high-performance machine and distribute it to low-performance machines where data retrieval is done.

You can improve performance of data retrieval on the file skip database by increasing the maximum number of cached records. By default, 65536 records are cached. Because nodes whose indices are multiples of the step unit or its powered numbers. You can set the parameter like this.

By default, I/O of the file skip database file is done via memory mapping. Thus, if the size of the database file exceeds the capacity of the virtual memory, the process can crash with segmentation fault or be killed by OOM killer. To avoid it, you can use normal positional by the normal I/O system calls, by creating the database object with the specific file object. See the tips on File Classes for details.

Building SkipDBM

The skip database is composed of records sorted by the key. Although you can insert records randomly, they are not visible until you call the Synchronize() method, which sorts records implicitly and merge them with existing records of the database. In other words, updating the skip database is done in an offline (batch) manner, not in an online manner. If you already have records which are sorted in ascending order of the key, you can use the insert_in_order mode, which is very quick and scalable. You can input multiple records of the same key and the order of insertion within records of the same key is preserved in the database. Note that the order of records of different keys must strictly be consistent to std::less if you use the insert_in_order mode. In contrast, if your records are not sorted, you use the default mode, which sorts the records implicitly with merge sort on temporary files. The reason for using temporary files is to build a huge database exceeding the memory capacity. You can input multiple records with the same key here too. The order within records of the same key is preserved during merge sort because it is a stable sort.

You can specify an arbitrary reducer to handle records of the same key. By default, no reducer is applied and all records are passed through. Whereas the following built-in reducers are bundled, you can implement your own reducers too.

• ReduceToFirst : Keeps the first record.
• ReduceToSecond : Keeps the second record if it exists. Otherwise, keeps the first record.
• ReduceToLast : Keeps the last record.
• ReduceConcat : Concatenates all values and makes a single record.
• ReduceConcatWithNull : Concatenates all values and makes a single record. Null code is used as separators.
• ReduceConcatWithTab : Concatenates all values and makes a single record. Tab is used as separators.
• ReduceConcatWithLine : Concatenates all values and makes a single record. Linefeed is used as separators.
• ReduceToTotal : Totals the numeric values and makes a single record.

If the input records have multiple records of the same key and you want to keep the first one, you’ll finish the database with ReduceToFirst. The following code keeps records of {“foo”:”first”} and {“bar”:”primero”} only.

In principle, the file skip database should be considered as a “static” database which is not updated after building it. However, you can modify it with usual methods of DBM. You can insert arbitrary records, which are put after existing records of the same keys. Then, you can reduce them when calling the Synchronize method. If you want to keep the latest value to overwrite the old value, you’ll synchronize the database with ReduceToLast. Assuming we use the above finished database, the following code keeps records of {“foo”:”fifth”} and {“bar”:”segundo”} only.

You can insert new data, but how do you remove the existing data? It is implemented as insertion of a special value. If you call the Remove method, a special value called REMOVING_VALUE is inserted. When synchronizing the database, if the special value is detected, records of the same key before the special value are removed. Then, the reducer is applied if any. The following code removes records of “foo” but doesn’t remove records of “bar”.

Note that synchronizing the database requires rebuilding the entire database even if only one record is modified. Therefore, updating records should be done in a batch processing style, where you do every operation and then synchronize the database. Note again that you cannot access new records until you call the Synchronize method.

You can merge multiple skip database files after building them separately. You can apply a reducer there. If you have to aggregate a large amount of data, building partial results as separate database files and merge them afterward is a practical way. You can do it in C++ by calling the MergeSkipDatabase method. You can do the same thing by a command like this.

The “merge” subcommand of tkrzw_dbm_util is useful to apply a reducer even if you specify no source databases to merge.

SkipDBM as a MapReduce

You can use SkipDBM as a framework of MapReduce. Map means an operation to generate and classify records from the given data source. Reduce means an operation to process records for each class and store the result. Between Map and Reduce, the framework does merge sort to organize records for each class. Reading data source and adding records to the database are considered a Map operation. And, the reducer applied when finishing the database represents a Reduce operation. The following code implements word counting.

First();
std::string doc_id, text;
while (iter->Get(&doc_id, &text) == Status::SUCCESS) {
  const std::vector<:string> words = GetWords(text);
  for (const auto& word : words) {
    count_dbm(word, "1");
  }
  iter->Next();
}
count_dbm.SynchronizeAdvanced(false, nullptr, SkipDBM::ReduceToTotal);

count_dbm.Close();
text_dbm.Close();
]]>

Tuning TinyDBM, BabyDBM, and CacheDBM

On-memory databases are convenient to manage large amount of objects while saving memory as much as possible. Objects to be stored must be serialized as strings. Thus, choosing an efficient serialization format is important. Of all on-memory databases, TinyDBM is the best in time efficiency. BabyDBM is the best in space efficiency. It also supports ordered access of records. CacheDBM is suitable for handling cache data where old records are discarded implicitly.

TinyDBM has a tuning parameter for the number of buckets. The number of buckets should be the same as or more than the number of stored records. It is set with the constructor.

BabyDBM has a tuning parameter for the comparison function of keys. The default comparison function is a lexical comparator, which is also usable for integers serialized as big-endian binary strings. It is set with the constructor.

CacheDBM has two tuning parameters for the capacity: the maximum number of records and the maximum memory usage. The maximum number of records is necessary because it is used to determine the number of buckets. Therefore, setting too large value is not good for space efficiency. The maximum memory usage is used as an insurance to ensure that memory usage doesn’t exceed the specified value.

If you use integers as keys and/or values, using functions IntToStrBigEndian and StrToIntBigEndian as a serializer and a deserializer is a good idea for space efficiency. This technique is usable for file databases too.

DBM::Process

One of the nicest features of Tkrzw is the Process method, shared by all database classes, which lets your application read and modify a single record of the database in a way that is atomic to all other threads. So it will never be possible for another thread to sneak in and change the record value between when your thread reads it and modifies it. This is one example of Atomicity and Isolation in the ACID traits.

More specifically, when you call Process, you provide a key and a “writeable” boolean indicating whether or not you want to modify/add records with that key. Multiple threads can all get read access (writeable==false) at the same time. Only one thread can have write access (writeable==true), and while a thread has write access, it blocks all reader threads. Most of the other DBM methods like Get, Set and Remove use Process under the covers, so they also acquire the appropriate read or write lock.

Locking is based on keys, not records. So when you acquire a read or write lock on a key, you prevent any other thread from modifying the record with that key or creating a new record with that key or removing a record with that key. When you acquire a write lock on a key, you also gain the right to modify the record with that key or create a new record with that key or remove a record with that key.

Different database classes implement key locking with different granularities. For example, HashDBM internally has a bank of 256 locks and keys get grouped together and guarded with these locks, whereas StdHashDBM internally has a single lock for all keys in the database. These internal differences will not affect the correctness of your application, but they may impact its performance. See the individual section for each database type to learn more.

Process takes a callback that Tkzrw calls with the record lock held so that you may perform the atomic operation. For that callback you can pass either an instance of a subclass of DBM::RecordProcessor or a lambda function. A subclass of DBM::RecordProcessor overwrites ProcessFull and ProcessEmpty methods.

• If the database has an existing record for the key passed to Process, Tkzrw calls your ProcessFull(key, value) with the key and the existing value, and you can either:
  • return DBM::RecordProcessor::NOOP to make no change to the database, or
  • return DBM::RecordProcessor::REMOVE to remove that record from the database, or
  • return a new record value to modify that record in the database.
• If the database has no existing record for the key passed to Process, Tkzrw calls your ProcessEmpty(key), and you can either:
  • return DBM::RecordProcessor::NOOP or DBM::RecordProcessor::REMOVE to make no change to the database, or
  • return a new record value to add that record to the database.

The Process method can also take a lambda function, whose signature is like the following.

• If the database has an existing record for the key passed to Process, Tkzrw calls your lambda with the key and the existing value, and you can either:
  • return DBM::RecordProcessor::NOOP to make no change to the database, or
  • return DBM::RecordProcessor::REMOVE to remove that record from the database, or
  • return a new record value to modify that record in the database.
• If the database has no existing record for the key passed to Process, Tkzrw calls your lambda with the key and a special value of string_view where value.data() == DBM::RecordProcessor::NOOP.data(), and you can either:
  • return DBM::RecordProcessor::NOOP or DBM::RecordProcessor::REMOVE to make no change to the database, or
  • return a new record value to add that record to the database.

When testing “value” passed to your callback against NOOP, make sure that you compare the pointers with the code “value.data() == DBM::RecordProcessor::NOOP.data()” rather than the incorrect code “value == DBM::RecordProcessor::NOOP”, which would only compare the string values, or the incorrect code “&value == &NOOP”, which would compare the object addresses. The uniqueness of the special NOOP value comes from the value of its NOOP.data() pointer. This applies to all callbacks for Process, ProcessMulti, ProcessFirst, and ProcessEach.

When returning a new value from your callbacks including lambda ones, remember that you are returning a std::string_view, and so the memory to which the string_view.data() points must remain valid throughout Process. This often means you must return a std::string_view that points to a member of your DBM::RecordProcessor subclass or a variable in a higher scope captured by reference in your lambda.

The following example has a lambda callback that works as an access counter. It takes an arbitrary ID string, increments the record value for it, saves the value as a decimal numeric string, and then returns the current access count. Note the check of NOOP by data() pointer, and note how the returned string is declared outside the lambda so it lasts util Process finishes, as explained above.

Process(id,
    [&](std::string_view key, std::string_view value) -> std::string_view {
      if (value.data() == DBM::RecordProcessor::NOOP.data()) {
        count = 1;
        return "1";
      }
      count = StrToInt(value) + 1;
      new_value = ToString(count);
      return new_value;
    }, true).OrDie();
  return count;
}
]]>

If your callback needs to spend a substantial amount of time between when it reads the existing database value and when it calculates the correct return value (NOOP, REMOVE, new value), this forces you to potentially degrade the performance of other threads, because your callback runs while Tkzrw is holding a lock on that record (and possibly other records) in the database. For many applications, there is a clever way around this dilemma called CompareExchange.

DBM::ProcessFirst

If you want to do an atomic operation to the first record without checking the key beforehand, the ProcessFirst method is useful. Using ProcessFirst is more effective than using an extternal iterator and call its First and Process methods in sequence.

As with the Iterator class, ProcessFirst can be slow if it is used with unordered databases (HashDBM, TinyDBM, CacheDBM, StdHashDBM) because finding the first record might scan the whole hash buckets. Meanwhile, Iterator and ProcessFirst are effective with ordered databases (TreeDBM, SkipDBM, BabyDBM, StdTreeDBM).

If you want to use the database as a queue (FIFO), you can use TreeDBM or BabyDBM, and their PushLast and PopFirst methods. PushLast takes an arbitrary record value and generates its key from the current timetamp. The, a record of the generated key and the given value is stored. Deduplication of the key is done implicitly. Thus, the enqueueing operation is written like the following.

PushLast(value);
}
]]>

PopFirst is implemented based on ProcessFirst. It retrieves the first record and removes it atomically. Thus, the dequeueing operation is written like the following.

PopFirst(nullptr, value);
}
]]>

DBM::ProcessEach

The ProcessEach method is a way to make bulk changes to the database atomically. It works as the following procedures.

• locks the entire database so no other thread can read or write any record.
• calls your callback once with a special sentinel value, giving you a chance to do preprocessing. For a DBM::RecordProcessor subclass, the sentinel is ProcessEmpty(key) with key.data() == DBM::RecordProcessor::NOOP.data(). For a lambda, the sentinel is func(key, value) with both key.data() == DBM::RecordProcessor::NOOP.data() and value.data() == DBM::RecordProcessor::NOOP.data().
• calls your callback once for every existing record in the database, just as with Process. So you will either get ProcessFull() or lambda func(key,value) with non-NOOP key and value.
• calls your callback one more time with the special sentinel value again, giving you a chance to do postprocessing.
• unlocks the entire database.

The following function multiplies the values of all records with a given factor. If the value of a record is less than 1, the record is removed.

ProcessEach(
    [&](std::string_view key, std::string_view value) -> std::string_view {
      if (value.data() == DBM::RecordProcessor::NOOP.data()) {
        return DBM::RecordProcessor::NOOP;
      }
      const int64_t count = StrToInt(value) * factor;
      if (count 

The Iterator class of each DBM type also has the Process method, and it can also take a DBM::RecordProcessor or lambda function as explained above. If you want to modify a specific record in an atomic manner, use DBM::Process. If you want to modify some or all records, each in an atomic manner (but not atomically as a whole), use DBM::Iterator::Process. If you want to access every records atomically and modify some of them, use DBM::ProcessEach. If you need to modify multiple records as a batch/transaction in an atomic manner, use DBM::ProcessMulti, which is described below.

DBM::ProcessMulti

Transactional operations on multiple records can be done with the ProcessMulti method. It takes multiple record keys and multiple callback functions to operate the records. As with the Process method, you use lambda functions as callback functions. All records specified by the keys are locked while all callback functions are executed. Thus, other threads don’t observe transitional states of the transaction. ProcessMulti works as the following procedures.

• It acquires read or write locks on all of your specified keys in the database in exactly the same way we described above for Process. So this prevents other threads from modifying, adding, or removing any records with those keys. If writeable==true, you have the right to modify, add, or remove records with those keys yourself.
• Then it calls your callbacks in sequence, one per key.
• Then releases the locks on all the records at once, so other threads will see all the records change state atomically rather than seeing any intermediate states of records.

Let’s assume that you manage bank accounts using a file hash database. You transfer 1000 from account A to account B. This transaction is composed of these operations.

1. Confirm that the account B exists.
2. Evaluate the balance of account A and confirm it is not less than 1000.
3. Decrease the balance of account A by 1000.
4. Increase the balance of account B by 1000.

To keep the consistency as a financial system, all operations must be done atomically. You can implement this money transfer function as the following.

 std::string_view {
        if (value.data() == DBM::RecordProcessor::NOOP.data()) {
          op_status.Set(Status::NOT_FOUND_ERROR, "no such destination account");
        }
        return DBM::RecordProcessor::NOOP;
      };

  // Callback to operate the source account.
  std::string new_src_value;
  auto proc_src =
      [&](std::string_view key, std::string_view value) -> std::string_view {
        if (!op_status.IsOK()) {
          return DBM::RecordProcessor::NOOP;
        }
        if (value.data() == DBM::RecordProcessor::NOOP.data()) {
          op_status.Set(Status::NOT_FOUND_ERROR, "no such source account");
          return DBM::RecordProcessor::NOOP;
        }
        const int64_t current_balance = StrToInt(value);
        if (current_balance  std::string_view {
        if (!op_status.IsOK()) {
          return DBM::RecordProcessor::NOOP;
        }
        if (value.data() == DBM::RecordProcessor::NOOP.data()) {
          op_status.Set(Status::APPLICATION_ERROR, "inconsistent transaction");
          return DBM::RecordProcessor::NOOP;
        }
        const int64_t current_balance = StrToInt(value);
        new_dest_value = ToString(current_balance + amount);
        return new_dest_value;
      };

  // Invokes the three callbacks in sequence atomically.
  const Status status = dbm->ProcessMulti({
      {dest_key, check_dest},
      {src_key, proc_src},
      {dest_key, proc_dest}}, true);
  if (!status.IsOK()) {
    return status;
  }
  return op_status;
}
]]>

If your callbacks need to spend a substantial amount of time between when they read the existing database values and when they calculate the correct return values, this forces you to potentially degrade the performance of other threads, because your callbacks run while Tkzrw is holding locks on one or more records in the database. For many applications, there is a clever way around this dilemma called CompareExchangeMulti.

DBM::CompareExchange and DBM::CompareExchangeMulti

Callbacks of the Process or ProcessMulti method shouldn’t spend much time because they hold locks of the target records and prevent any other threads from making progress. However, doing the same thing with separate method calls is not acceptable because another thread may simultaneously change the values that you are processing. To get out of this dilemma, you can often use the extremely clever CompareExchange and CompareExchangeMulti methods.

The key insight is that, for many applications, if you read the value of a record, do some lengthy processing of that record, and then at the moment you write the result, you find that someone else has modified the value of the original record, you can simply re-run the lengthy process again with the new value, or (for some applications) just forget about running the lengthy process because it is no longer needed. You only actually need atomic behavior at the very last step, where you are deciding to commit your processed data or not based on whether or not the value has changed since the beginning of the process.

CompareExchange and CompareExchangeMulti are wrappers around Process and ProcessMulti which help you accomplish this. You do the following procedures.

• first read the value of the records you want (using Get(); no special locking needed at this stage)
• then process the value (the lengthy part)
• then call CompareExchange or CompareExchangeMulti, passing in the old record value(s) that you worked on, and the new record value(s) that you computed. CompareExchange and CompareExchangeMulti atomically check that the record(s) still have the same old value(s), and if so they set your new value(s) and return success. If not (if the value(s) changed while you were processing), CompareExchange and CompareExchangeMulti fail so you can try again.

In this example, you read the current balances of the accounts, calculate the desired balances after the transaction, and then call CompareExchangeMulti so that it only succeeds if the balances have not changed. You repeat the transaction until it succeeds.

Get(src_key, &src_value);
    if (!status.IsOK()) {
      return status;
    }
    const int64_t src_balance = StrToInt(src_value);
    if (src_balance Get(dest_key, &dest_value);
    if (!status.IsOK()) {
      return status;
    }
    const int64_t dest_balance = StrToInt(dest_value);

    // Generate new values for the new balances.
    const std::string src_new_value = ToString(src_balance - amount);
    const std::string dest_new_value = ToString(dest_balance + amount);
    
    // Finish the transaction atomically if the balances are not modified.
    const std::vector<:pair std::string_view="">> expected =
        {{src_key, src_value}, {dest_key, dest_value}};
    const std::vector<:pair std::string_view="">> desired =
        {{src_key, src_new_value}, {dest_key, dest_new_value}};
    status = dbm->CompareExchangeMulti(expected, desired);
    if (status.IsOK()) {
      return Status(Status::SUCCESS);
    }
    if (status != Status::INFEASIBLE_ERROR) {
      return status;
    }
  }

  return Status(Status::INFEASIBLE_ERROR, "too busy");
}
]]>

Notification

In multi-thread programming, you sometimes want to use notification features. The SignalBroker class is useful to notify of generic updates to other threads. The “producer” threads and the “consumer” threads share an instance of SignalBroker. The producer threads calls its Send method after they update the database.

PushLast("hello");
  broker->Send();
}
]]>

The consumer threads check the database first. If the checked data doesn’t satify the precondition of the succeeding operation, they wait for the next database update and its signal. To prevent the signal from being sent between checking the current state and starting to wait, the Waiter object should be created before checking the current state.

PopFirst(nullptr, &value) == Status::SUCCESS) {
      std::cout 

If you want to use signals associated with arbitrary identifiers, you can use SlottedKeySignalBroker. The Send method takes a key and wakes up threads which are waiting for the same key.

* broker) {
  dbm->Set("greeitng", "hello");
  broker->Send("greeting");
}
]]>

As in the SignalBroker case, the consumer uses a Waiter object to make a critical section to check the database and wait for the next update.

* broker) {
  while (true) {
    SlottedKeySignalBroker::Waiter waiter(broker, "greeting");
    std::string value;
    if (dbm->Get("greeting", &value) == Status::SUCCESS) {
      std::cout 

Using SignalBroker and SlottedKeySignalBroker is better in terms of concurrency performance than using std::mutex and std::condition_variable. SignalBroker and SlottedKeySignalBroker don’t cause exclusive locking for the database operations but use shared locking. Moreover, the Wait method of the Waiter class takes an optional timeout parameter so that you can use the long polling idiom.

Restoring Broken Databases

An opened database should be closed properly. Otherwise, the database file might be broken. When a database is opened, a field in the metadata section is marked as “opened”. When the database is closed, the field is marked as “closed”. If the process opening a database crashes without closing the database, the field is still marked as “opened”. When the database file is opened the next time, the library detects the past incident and the database is considered “unhealthy”.

By default, an unhealthy database is restored automatically when you open the database. The whole database file is scanned and as many records as possible are salvaged. This behavior can be changed by setting the restore_mode tuning parameter. The default value is RESTORE_DEFAULT, which causes the best-effort restore. If it is RESTORE_SYNC, the database is restored to the state at the time when the Synchronized method was called last time. If it is RESTORE_READ_ONLY, no restore operations are done and the database becomes read-only to avoid further inconsistency. If it is RESTORE_NOOP, the database is treated healthy without any restore operation.

You can add optional settings to RESTORE_DEFAULT or RESTORE_SYNC by bit-or operation, like RESTORE_SYNC | RESTORE_NO_SHORTCUTS. By default, the following shortcuts are checked and applied before doing the full-fledged restoration. The RESTORE_NO_SHORTCUTS option suppresses them.

#1 : If the following condition is satisfied, the database is considered healthy and restoration is skipped.

The update mode is the appending mode.

The actual file size is the same as the metadata’s file size.

The validation check of the bucket section passes.

#2 : If the following condition is satisfied, the database is considered restored without doing actual restoration.

The update mode is the in-place mode.

The actual file size is equal to or larger than the metadata’s file size.

The validation check of the bucket section passes.

The validation check of the entire record section passes.

#3 : If the following condition is satisfied, the database is considered restored without doing actual restoration.

The update mode is the appending mode.

The actual file size is equal to or larger than the metadata’s file size.

The validation check of the bucket section passes.

The validation check of the record section after the metadata’s file size passes.

If the database is in the appending update mode and you call the Synchronize method periodically, it is likely that the third shortcut is applied. And, it finishes very quickly. That’s another reason why the appending mode is suitable for online services.

Another option is RESTORE_WITH_HARDSYNC, which synchronizes temporary data during the restoration operation. You set the option if you are concerned about another system crash during the restoration operation.

You can check whether a database is healthy or not by a command like this.

“num_records”, “file_size”, and “mod_time” represent information when the database was closed successfully (or the Synchronize method is called) the last time. So, even if you add many records before the last crash, the metadata doesn’t reflect them. The restore operation recompute the metadata from salvaged records.

In contrast to the default API setting, the command line tool opens the database file in the RESTORE_READ_ONLY mode, the file is not restored implicitly. If you want to do the restore operation explicitly, you’ll run a command like this.

If you want to set tuning parameters to the new restored database, you can prepare the new database with the tuning parameters and set it as the destination. This operation can be done even for a healthy database to rebuild it.

The same thing can be done in C++. HashDBM, TreeDBM, and SkipDBM have the RestoreDatabase method. PolyDBM and ShardDBM also privides wrapper functions.

To restore sharded database files like (casket.tkh-00000-of-00002 and casket.tkh-00001-of-00002), you’ll run a command like this.

HashDBM and TreeDBM support the appending update mode. Databases in the appending mode can utilize an interesting feature called snapshot reproduction. As all updating operations are recorded in the database, you can consider the database as a list of REDO logs. You can replay them until a certain moment. And, the moment is represented as the then size of the database file. Given that you know the file size at a moment by calling the GetFileSize method, you can restore the database to the state at the moment.

You’ll check the behavior by commands like this.

If the value of –end_offset is 0, the database is restored to the state at the time when the Synchronized method was called the last time. If the value of –end_offset is -1, as many records as possible are salvaged.

ACID Transaction

In the context of database, transaction is a concept of executing one or more database operations in a meaningful and reliable manner. We expect tansactions have ACID traits. Tkrzw’s transactional features are designed to achieve the ACID traits. We should consider transactions in two aspects: transactions across threads and transactions across crashes.

Process, ProcessFirst, ProcessEach, ProcessMulti, CompareExchange, and CompareExchangeMulti assure Atomicity and Isolation. Specifically, they assure that other threads reading the same database will either observe no changes to any of the records, or they will observe the complete set of changes to all of the records involved in the transaction, regardless of the relative timing of all threads in the process. The business logic that you write inside your callbacks for those methods assure the Consistency of the transaction, another important aspect of ACID.

File database implementations provide Durability across crashes as well as the other ACI traits. If the application or system crashes when it is in the middle of a transaction, the database will rollback cleanly to the state before the transaction on the next Open. Durability of a translaction is guaranteed only when the next Synchronize or Close method finishes successfully. In this meaning, on-memory databases associated with files also provide the same level of durability.

Unlike some other databases, Tkrzw doesn’t have an explicit rollback operation to cancel a set of previously requested updating operations. Once you call Set, Remove, or once your callback of the Process returns a new value or REMOVE, there is no way to take the operation back. Usually, checking the precondition in ProcessMulti or before CompareExchangeMulti makes rollback unnecessary. If you want rollback features, you have to record “undo” transaction logs in another database and apply them explicitly by yourself. If the database is HashDBM or TreeDBM and it is in the appending update mode, you can use the snapshot reproduction feature that lets you rollback your database to a specific point in its transaction history.

The Synchronize method is done within an exclusive lock against other threads. Thus, atomicity of transactional operations of multiple records are protected as long as you use ProcessMulti or CompareExchangeMulti.

There is a lot of misunderstanding about durability because “durability” is not a single yes-or-no, or even single-valued, concept. Different “durability” configurations of hardware and software can offer you different guarantees, or probabilities, that your data will not be damaged in specific specified threat situations. We consider the following situations as typical threads. The lower items are more severe and succeed all risks of the upper items.

#1 : The process finishes without closing the database.

The metadata is not written into the file.

Record data cached in the process is not written into the file.

#2 : The process crashes suddenly.

Multiple write operations for one record updating can stop in the middle.

One write operation can stop in the middle.

#3 : The operating system crashes suddenly.

A part of dirty pages is not written into the device.

Inconsistent data blocks can be written into the device.

#4 : The hardware breaks down.

Anything unpredicable can happen.

The entire file can be lost.

To deal with hardware brokage (#4), you should consider data replication service or distributed computing, which are not in the scope of Tkrzw’s features. Tkrzw provides features for ACID traits across crashes of the operating system (#3) and the upper.

There is often a tradeoff between performance (CPU, memory, disk space) and durability. For example, by adding synchronization points by the Synchronize method at strategic points, we can often gain certain durability benefits, but at some performance cost. Or by appending new changes to the end of the file by the appending update mode of HashDBM/TreeDBM, we can gain certain durability benefits, but at the cost of extra disk space usage and fragmentation. In its default configuration, Tkzrw always favors performance. But Tkrzw offers a host of options to trade off durability for performance depending on your needs.

Settings for Higher Durability

HashDBM and TreeDBM give you higher durability with the following settings. Each has benefits for durability at the cost of performance.

Open the database in the appending mode by setting the TuningParameters.update_mode to OpenAdvanced to UPDATE_APPENDING.

The file size of the database in the appending update mode grows by each update operations. Thus, you call the Rebuild method periodically to keep time and space efficiency.

Open the database with the TuningParameters.restore_mode to OpenAdvanced to RESTORE_SYNC.

This restores unhealthy databases to the state at the last time when Synchronize succeeds. Adding RESTORE_NO_SHORTCUTS reduces the risk of possible missing links in case that null codes are written unexpectedly. Adding RESTORE_WITH_HARDSYNC to the restore mode gives you more safety against another crash during the restoration operation.

Call the Synchronize method after the transaction which you must consider completed/consistent.

The “hard” flag should be true to tolarate system crashes. If it is false, it can toralate only process crashes. If hard=true is more costly since it writes all cached data to disk and waits for confirmation from the hardware.

Open the database with a file open option OPEN_SYNC_HARD.

This option causes the same physical synchronization as above just before closing the database file.

In addition, if you are concerned that the storage device could taint the existing region on the same disk block when you append data, you should set the TuningParameters.align_pow to OpenAdvanced to a value for the disk block size. Typically, it’s from 9 (meaning 2^9 = 512 bytes) to 14 (meaning 2^14 = 16384). However, it means that the minimum record size becomes 512 or 16384, whereby the space efficiency can be unpractically low.

SkipDBM gives you higher durability with the following settings. Each has benefits for durability at the cost of performance. The same thing can be said to the other on-memory databases associated with files.

Call the Synchronize method after the transaction which you must consider completed/consistent.

The “hard” flag should be true to tolarate system crashes. If it is false, it can toralate only process crashes. If hard=true is more costly since it writes all cached data to disk and waits for confirmation from the hardware.

Open the database with a file open option OPEN_SYNC_HARD.

This option causes the same physical synchronization as above just before closing the database file.

The Synchronize method of SkipDBM and on-memory databases makes a new database file as a temporary file. Then, the old database file is replaced with the temporary file atomically. Thus, the database never breaks and no record is ever lost. Even so, SkipDBM has restore features just in case that the file is currupted for unexpected reasons. RESTORE_DEFAULT and RESTORE_SYNC are equivalent for SkipDBM. Actually, calling Synchronize often is not practical in terms of performance. Just setting OPEN_SYNC_HARD and delaying synchronization as much as poossible is better for performance.

If you use ShardDBM for sharding databases, ACID traits across crashes are not guaranteed regardless of the inner database classes. That’s because the Synchronize method is called one by one for each inner databases without the global locking. It can end up with a partial success of Synchronize.

The above settings can realize the durability that most ACID-supporting databases provide, although some important details vary between databases. Even if you do not configure Tkrzw into the ACID settings, you can still call Process, ProcessMulti, etc. to get the benefits of Atomicity and Isolation between threads in your callback. But if you want ACID transactions, where you can modify two or more records atomically even in the presence of crashes, you must use the ACID settings. Even applications which don’t require ACID traits may still want to choose the ACID setting, because it offers stronger durability benefits against various forms of disk corruption.

Some applications might want ACID transactions or other benefits of the ACID settings, but cannot accept the performance penalty of calling Synchronize. Such applications can still get some partial protection by opening the database with the default restore mode. With RESTORE_DEFAULT, Tkrzw will make a best-effort attempt to recover as many records as possible after a crash. There is no guarantee about which records, or even how many records, can be recovered. However, you can often recover many records beyond the last Synchronize, which might be a better trade-off depending on the application. Unlike the ACID settings, this method works even with a ShardDBM database. Such applications should also consider using UPDATE_APPENDING, which offers some protection against disk corruption.

Detecting Corruption

Regardless of whether you choose the ACID settings or not, HashDBM and TreeDBM provide partial protection against corruption to record data in the file in the form of checksums on each record. The checksums allow Tkrzw and your application to detect database corruption with a probability that you can tune:

• By default, you get a 6-bit checksum on each record, which can detect errors at a rate of 98.3%
• You can pass RECORD_CRC_8 as the TuningParameters.record_crc_mode to OpenAdvanced to add 8 more bits of CRC-8 checksum stored with each record, raising the error detection rate to 1 – 1/ (61 * 256) = 99.993%
• You can pass RECORD_CRC_16 as the TuningParameters.record_crc_mode to OpenAdvanced to add 16 more bits of CRC-16 checksum stored with each record, raising the error detection rate to 1 – 1 / (61 * 65536) = 99.999975%
• You can pass RECORD_CRC_32 as the TuningParameters.record_crc_mode to OpenAdvanced() to add 32 more bits of CRC-32 checksum stored with each record, raising the error detection rate to 1 – 1 / (61 * 4294967296) = 99.9999999996%

CRCs are better than checksums in that they detect one contiguous error sequence within the width of CRC at the 100% rate. Typically RECORD_CRC_8 or RECORD_CRC_16 are enough for situations where power failures and hardware failures are not common.

The checksum and CRC are not checked in normal database operation like Get and Set. They are checked when the database is restored by the auto restore feature or an explicit call of the RestoreDatabase function. Consistency of metadata is checked for each record access. If you want to validate all records using the checksum and CRC, call the ValidateRecords method explicitly.

Tkrzw can also detect corruption in the file header containing the metadata of the database. If corruption of the file header is detected, the backup metadata is read from the record header section. If Tkzrw can restore some or all of your data, the Open method returns a success status and the IsAutoRestored method returns true. If your database is too corrupted to be read at all, the Open method returns an error status.

In all cases, any form of corruption to the database file shouldn’t make Tkrzw crash your process. Tkrzw will either detect the corruption and return an error as described above, or it will fail to detect the corruption and return success status. Some forms of corruption that Tkzrw cannot detect may cause you to lose data. For example, if a rogue process modifies a certain header field in a certain way, some of your records can disappear on the next Open, but your process will not crash.

Making Backup Data Online

Let’s say, your service runs 24 hours a day and any downtime is not allowed. Then, you have to make backup data of the database online without halting the service. There are two methods to do so: CopyFileData and Export.

The CopyFileData method synchronizes the updated content to the database file and copy the whole data to another file. As copying is done while the content of the database is synchronized and frozen, the copied file is considered as a snapshot of the database at a certain moment. And, the copying operation is done by the fastest way on the system. If the file system is BtrFS or XFS on Linux, reflink (copy-on-write) is used and the copying operation is done at a split second. Otherwise, on Linux, the sendfile system call is used.

The downside of the CopyFileData method is that other threads trying to update the database are blocked during the copying operation, which can take several seconds or minutes depending on the file size. If it is not acceptable, use the Export method, which accesses each and every records and adds them to another database. As other threads updating the database are not blocked during the iteration, atomicity as the database is not assured. Atomicity of each record is assured.

Some file systems provides a feature to make a snapshot of a file. The Synchronize method can call a callback function while the database is synchronized. Therefore, if the callback function uses the snapshot feature, you can make an atomic snapshot at a moment without making other threads wait.

Update Logging and Incremental Backup

If you have a backup database file, you can recover the state of the database at the time of taking the backup file. However, you loose updates after that time. Taking update logs mitigates this issue. Each database class supports injection of any update logger instance, whose class is derived from the UpdateLogger class. The WriteSet method is called just before a record is modified or added by the Set method and so on. The WriteRemove method is called just before a record is removed by the Remove method and so on. The WriteClear method is called just before all records are removed the Clear method. If you want to monitor all updates on the terminal, you’ll write the following code.

Note that all updates represent the current content of the database. Let’s say, if the value “foo” of a record is updated by Append method to be “foobar”, WriteSet(“foobar”) is called. It’s not WriteAppend(“bar”). If the Remove method is called but the record doesn’t exist, no callback is called.

By storing update logs into files, you can redo the operations later. It’s like row-level REDO logs of RDBMS. One easy way to achieve it is to use another DBM object. The class DBMUpdateLoggerDBM wraps any DBM object as UpdateLogger. The following code replicates every updates of the main database to the backup database.

However, using two databases is not ideal in most cases. As the backup database is also online, you cannot stop it while the main database is in operation. Moreover, the throughput of updating operatins is halved.

Instead, it is recommended to store update logs into flat files by the DBMUpdateLoggerMQ class. It serializes update logs in a binary format and appends them at the end of a flat file. Thanks to the simple structure, overhead for taking logs is relatively low. Moreover, file rotation is done implicitly; If the size of the current file exceeds a threshold, a new file is created and then newer update logs are stored there. The timestamp when the update happens is attached to each update log. Thus, you can retrieve update logs in a specific time range. Thanks to those features, you can maintain incremental backup data for online databases.

The DBMUpdateLoggerMQ class uses a message queue managed by the MessageQueue class. It realizes thread-safe operations of writing and reading logs simultaneously. You specify a prefix of log files and the maximum file size when you call the Open method of MessageQueue. The actual file name has a suffix of ten digits of a sequential ID, like “casket-ulog.0000000000” and “casket-ulog.0000000001”.

The same thing can be done with PolyDBM and ShardDBM by setting tuning parameters.

If the database is completely broken or lost somehow, you restore the current state by applying the update logs to the latest backup file. It is a good practice to copy the backup file for restoration to keep the original file intact, just in case.

The typical scenario of operations with incremental backup data is like the following. After restoration and before resuming the normal operations, the restored database should be copied as the new backup file.

• Makes a full backup data.
• Does normal update operations while taking update logs.
• The system crashes and the main database is lost somehow.
• Applies the update log to the full backup file.
• Archive/remove old update log files.

The restore operation can be done by the command line utility too. If you take update logs from the beginning, you can make a full backup file by applying all update logs to an empty database. The parameter of “–ulog” means the minimum timestamp in milliseconds of the updates to be applied. So, 0 means all updates.

Unless the system crashes and restoration is done, the update log files continue to increase. Thus, you should apply the update logs periodically and archive/remove unnecessary files. The above command works with update log files which are in operation by another process. As the race condition is avoided by checking metadata for each record, you can read update log files which can be written by another process simultaneously. After you apply all exisiting update logs, you can remove the update log files except for the latest one. The following