2 Log Structured Store

The underlying transactional storage engine has state of the art performance, it can readily achieve data ingestion rates at the sustained write rates of the secondary storage devices - even exceeding a gigabyte per second on a single machine. For example, in one comparison it took only 5 seconds to write a million (key,value) pairs totalling 4GB of data on a laptop with a pair of SSDs in RAID0. On the same machine BerkeleyDB took 2 minutes 20 seconds.

The CEDA database management system is built on the Log Structured Store (LSS). It provides low-level persistence for arbitrary-sized binary objects indexed by 64-bit identifiers. It fully supports transactions and guarantees their atomicity in the face of power failures.

Major LSS implementation components

The LSS can be regarded as a key-value store whose keys are 64-bit Serial Element Identifiers (seids) and whose values are arbitrary-length strings of octets called serial elements. Another useful analogy is a persistent heap: seids act like pointers to memory buffers that persist on disk. A serial element may range from zero octets to many terabytes and can be read or written as a stream without fitting into physical memory.

Seids are logical rather than physical addresses. A serial element can be rewritten at a new physical location while retaining the same identifier, allowing the old storage to be recycled. There are only three basic operations: write a serial element, delete a serial element, and read a serial element. Updating an element means writing its new value from scratch.

All writes and deletions occur within explicitly declared LSS transactions. Transactions define atomic changes: after crash recovery either the entire transaction is present or none of it is. If a transaction is recovered, all transactions that preceded it are recovered as well.

The LSS provides:

  • Stores up to 500 TB
  • Atomic transactions and concurrent reads
  • Optional durability
  • A design that does not use write-ahead logging
  • Very high read and write performance
  • Hot standby and incremental backup
  • Bounded crash recovery of less than one second
  • Automatic cleaning to reclaim obsolete storage and avoid fragmentation

Output multiplexing supports hot standby and backup consistent with continuous operation. Above the LSS, CEDA's persistent object store maps persistent object graphs onto these transactional serial elements.

The LSS supports embedded databases, allowing for a database management system (DBMS) which is tightly integrated with application software and hidden from the users. The data is loaded directly into the same process as the application, from database file(s) exclusively opened by that process.

The Log Structured Store specification describes the architecture, operations, public API, performance results, crash recovery, cleaning, backup, and implementation.