mokuroku

Overview

This Rust crate is designed to provide a secondary index on top of the RocksDB key/value store, similar to what PouchDB does for LevelDB. The application provides implementations of the Document trait to suit the various types of data to be stored in the database, and this library will invoke a mapping function provided by the application to produce index key/value pairs.

The design of this library is similar to PouchDB, albeit with an API suitable for the language. Unlike PouchDB, however, this library does not put any constraints on the format of the database records. As a result, the library relies on the application to provide the functions for deserializing records and invoking the emit() function with index key/value pairs. To avoid unnecessary deserialization, the library will call Document.map() with each defined index whenever the application calls the put() function on the Database instance.

Classification

What this library does exactly: the indices managed by this library are "stand-alone", meaning they are not embedded in the database. Additionally, the index is updated in a lazy fashion, meaning that changes are appended rather than merged on update. At query time, the library will merge the results accordingly. This strategy avoids unnecessary reads during write operations, thus keeping the general performance of the database within expectations. The performance penalty of the index comes (mostly) at query time.

Work in Progress

The secondary indices work well if you never update or remove records. That is, the delete() call does not update the indices at all, and if an existing record is changed with put() and it emits new index values, the old ones will still be returned in queries. This will be addressed in a future release as this is clearly not adequate for all applications.

As a quick note, the plan is to use tombstones to mark deleted records, and employ a read repair strategy on query. Again, keeping the write performance in line with expectations, and taking the penalty at the time of query. How the index will be updated when existing records are changed is not yet decided.

Contributions Are Welcome

While the author has read a couple of relevant research papers, he is not by any means an expert in database technology. Likewise, his Rust skills may not be all that impressive either. If you wish to contribute, by all means, please do. Thank you in advance.

Building and Testing

Prerequisites

Rust stable (2018 edition)

Building and Testing

These commands will build the library and run the tests.

shell $ cargo clean $ cargo build $ cargo test

Examples

See the full example in the examples/tagged directory, which creates a RocksDB database, adds a few records, establishes a secondary index, and queries that index using specific key values.

Quick Example

This code snippet is lifted from the aforementioned example. It shows the most basic usage of opening the database, adding records, and querying an index. Examples of the functions for generating the index are in examples/tagged directory.

```rust let dbpath = "mydatabase"; let mut views: Vec = Vec::new(); views.push("tags".toowned()); let dbase = Database::new(Path::new(dbpath), views, Box::new(mapper)).unwrap(); let documents = [ Asset { key: String::from("asset/blackcat"), location: String::from("hawaii"), tags: vec![ String::from("cat"), String::from("black"), String::from("tail"), ], }, // ... ]; for document in documents.iter() { let key = document.key.as_bytes(); let _ = dbase.put(&key, document); }

// querying by a specific tag: cat let result = dbase.querybykey("tags", b"cat"); let iter = result.unwrap(); let results: Vec = iter.collect(); for result in results { let docid = str::fromutf8(&result.docid).unwrap().toowned(); println!("query result key: {:}", doc_id); } ```

Design

Terminology

Quick note on the terminology that this project uses. You may see the term view used here and there. This is what CouchDB and PouchDB call the indices in their documentation. Given this crate attempts to operate in a similar fashion, it seems natural to use the same term.

Usage

The application uses the mokuroku::Database struct in place of rocksb::DB, as this crate will create and manage that DB instance. Since the crate is managing the secondary indices, it is necessary for the application to call the put() function on Database, rather than calling directly to DB. For operations that should not affect any index, the application is free to get a direct reference to DB using the Database.db() function.

At startup, the application will create an instance of Database and provide three pieces of information.

Path to the database files, just as with DB::open()
Collection of index names that will be passed to Document.map()
A boxed function of type mokuroku::ByteMapper

The set of index names are those indices which the library will update every time Database.put() is called. That is, the implementation of Document that is passed to the put() call will have its map() invoked with each of the provided index names. Not every Document will emit index key/value pairs for every index. In fact, there is no requirement to emit anything, it is entirely application dependent. Similarly, a single invocation of a mapper may emit multiple values, which is demonstrated in the tagged example.

The ByteMapper is necessary when the library needs to rebuild an index. Since the library will be reading every record in the default column family, it does not know how to deserialize the records into the appropriate Document implementation. For this reason, the application must provide this function to recognize and deserialize records, and then emit index key/value pairs.

After setting up the database, the application may want to invoke query() on the database for each named index. This will cause the library to build the indices if they are missing, which will improve the response time of subsequent calls to query().

Data Model

The application defines the database record format; this library does not put any restrictions on the format of the keys or values. That is a big part of why the usage is slightly more complicated. This is not PouchDB and the documents are not all JSON formatted blobs.

The library maintains the secondary indices in separate column families, whose names start with mrview- to avoid collision with any column family that the application may have created. For instance, if the application creates an index named tags, then the library will create a column family named mrview-tags and populate it with the values given to the Emitter passed to the implementations of Document.map() and ByteMapper defined by the application.

The index keys output by the application need not be unique. The library will append a unique suffix (a ULID to be specific) to ensure that no index entry will overwrite any other. The application can emit an optional value for the index entry, while the library will inject the primary key automatically before saving the index row to the database. The format of that index value is entirely up to the application.