Summary

LineairDB is a C++ fast transactional key-value storage library. It provides transaction processing for multiple keys with guarantees of both strict serializability (linearizability) and recoverability (see Correctness to further details of these properties). LineairDB provides some novel concurrency-control protocol that promise scalability for many-core CPUs machines, especially in (or even if) write-intensive and contended workloads (see NWR to the detail of the protocols or Benchmark Results).

Notes

• LineairDB is not an SQL (Relational) database.
• There is no client-server support in the library (i.e., LineairDB is an embedded database).

Design

LineairDB fully adopts and benefits from the Epoch Framework [Tu13, Chandramouli18]. Briefly, the epoch framework divides the wall-clock time into epochs and assign each epoch into each transaction. (i.e., epoch framework groups running transactions). LineairDB uses the Epoch Framework in the followings:

1. Epoch-based group commit of transactions
2. RCU-QSBR-like garbage collection of storage
3. Epoch-based checkpoint recovery
4. Epoch-based range/point index

The Epoch Framework provides advantages in both correctness and performance.

Correctness

LineairDB assumes that the correctness properties of DBMS consist of strict serializability and recoverability.

The Epoch framework is favorable for both property:

• For strict serializability, the number of "concurrent" transactions can increase because transactions in the same epoch commit together at the same time. This nature gives us some possibility of performance optimization. The details are described later in NWR.
• For recoverability, we no longer have to worry about violating recoverability. Notably, epoch-based group commit has the constraint that all the logs of transactions in an epoch have to be persisted before the commit is returned. Hence, if a transaction reads a dirty value written by another running transaction, it does not commit before the writer commits because these two transactions are in the same epoch. This nature also enables early lock release of the exclusive lock.

Why "strict" serializability?

Why do we need "strict" serializability? LineairDB is an embedded single-node database and thus is (not strict) serializability good enough? Note that serializability theory permits to change orders among non-concurrent transactions. For instance, a serializable database allows all transactions to read from and write into any arbitrary version. More precisely, a transaction may always read the initial values, even if there exist some newer versions, and also can always write older versions than the initial values. Most users can not accept this behavior because even if several years may have passed after the initialization of DBMS, not strictly serializable databases allow such unacceptable results. Concurrency control protocols satisfying strict serializability never change the order of transactions when they are not concurrent.

Non-visible Write Rule (NWR)

LineairDB provides some novel extended concurrency control protocols, named _"NWR"_ (e.g., LineairDB provides Silo [Tu13] and its extended protocol, named SiloNWR). NWR-protocols have great performance in write-intensive and contended workloads, that includes _"blind-writes"_. The scalability of NWR extension is obtained by omitting unnecessary write operations. Briefly, LineairDB reorders concurrent transactions and omits some write operations. Remind that transactions in an epoch are grouped; the nature of epoch-based group commit is favorable for NWR; Since transactions in the same epoch are committed at the same time, we can say that transactions in the same epoch are concurrent, and can be reordered.

NWR can omit blind write operations, which are insert or no-read update-only operations. If you have blind write operations in your use case, choosing NWR-protocols is recommended strongly. Because unnecessary write operations are omitted, LineairDB improves the processing speed of transactions dramatically.

The correctness of transaction processing in LineairDB is proved based on the multi-version serializability theory. See the research paper at this link.

Example

The following is a simple example code of how to use LineairDB. Here we are not dealing with a multi-threaded environment; however, LineairDB is basically designed to be thread-safe. That is, it is allowed to invoke LineairDB::Database::ExecuteTransaction by multiple threads in parallel.

/*
 *   Copyright (C) 2020 Nippon Telegraph and Telephone Corporation.
 
 *   Licensed under the Apache License, Version 2.0 (the "License");
 *   you may not use this file except in compliance with the License.
 *   You may obtain a copy of the License at
 
 *   http://www.apache.org/licenses/LICENSE-2.0
 
 *   Unless required by applicable law or agreed to in writing, software
 *   distributed under the License is distributed on an "AS IS" BASIS,
 *   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 *   See the License for the specific language governing permissions and
 *   limitations under the License.
 */
 
#include <lineairdb/lineairdb.h>
 
#include <cassert>
#include <iostream>
 
int main() {
  {
    LineairDB::Database db;
    LineairDB::TxStatus status;
 
    // Execute: enqueue a transaction with an expected callback
    db.ExecuteTransaction(
        [](LineairDB::Transaction& tx) {
          auto alice = tx.Read<int>("alice");
          if (alice.has_value()) {
            std::cout << "alice is recovered: " << alice.value() << std::endl;
          }
          tx.Write<int>("alice", 1);
        },
        [&](LineairDB::TxStatus s) { status = s; });
 
    // Fence: Block-wait until all running transactions are terminated
    db.Fence();
    assert(status == LineairDB::TxStatus::Committed);
  }
 
  {
    LineairDB::Database db;
    LineairDB::TxStatus status;
 
    // Handler interface: execute a transaction on this thread
    auto& tx = db.BeginTransaction();
    tx.Read<int>("alice");
    tx.Write<int>("alice", 1);
    db.EndTransaction(tx, [&](auto s) { status = s; });
    // Fence: Block-wait until all running transactions are terminated
    db.Fence();
    assert(status == LineairDB::TxStatus::Committed);
  }
 
  {
    LineairDB::Database db;
    // Example of failures: database instance is not copy-constructable.
    //    NG: auto db2 = db;
    // Example of failures: we cannot allocate two Database instance at the same
    // time.
    //    NG: LineairDB::Database db2;
    //    NG: auto* db2 = new LineairDB::Database;
  }
 
  {
    // Here we have instantiated and destructed LineariDB twice, and
    // we can recover stored data from durable logs.
    LineairDB::Database db;
    db.ExecuteTransaction(
        [](LineairDB::Transaction& tx) {
          auto alice = tx.Read<int>("alice");
          assert(alice.has_value());
          assert(alice.value() == 1);
        },
        [&](LineairDB::TxStatus s) {});
  }
 
  {
    // Instantiate with customized configuration.
    LineairDB::Config config;
    config.concurrency_control_protocol =
        LineairDB::Config::ConcurrencyControl::Silo;
    config.enable_logging  = false;
    config.enable_recovery = false;
    config.max_thread      = 1;
 
    LineairDB::Database db(config);
    // Example of failures: we passed `config` as rvalue and it is nop to modify
    // this object after instantiation of LineairDB.
    //    NG: config.max_thread = 10;
 
    db.ExecuteTransaction(
        [](LineairDB::Transaction& tx) {
          auto alice = tx.Read<int>("alice");
          // Any data item is not recovered
          assert(!alice.has_value());
        },
        [&](LineairDB::TxStatus s) {});
  }
}

Roadmap

The LineairDB project roadmap is available at Roadmap

Benchmark Results

The followings are our benchmark results. This is a modified benchmark of YCSB-A; unlike official YCSB in which a transaction operates a single key, each transaction operates on four keys in our benchmark.

This benchmark is executed in the following environments:

CPU	four Intel Xeon E7-8870 (total 144 logical cores)
Memory	1TB (no swap-out)
YCSB Table size	100K
YCSB Record size	8-bytes
Epoch size	1000ms
Contention (θ)	0.9 (highly contended)
# of threads to process txns	70

YCSB-A

SiloNWR, our novel concurrency control protocol, achieves excellent performance by omitting transactions without exclusive lockings. Note that YCSB-A has an operation ratio of Read 50% and (Blind) Write 50%; that is, this is a fairly favorable setting for NWR-protocols. If your use case is such a blind write-intensive, then LineairDB can be a great solution.

Copyright

Copyright (c) 2020 Nippon Telegraph and Telephone Corporation. Licensed under the Apache License, Version 2.0 (the "License").