Reverse Indexing and Data modeling in Key-Value store

Question

I am new to key-value stores. My objective is to use an embedded key-value store to keep the persistent data model. The data model comprises of few related tables if designed with conventional RDBMS. I was checking a medium article on modeling a table for key value store. Although the article uses Level DB with Java I am planning to use RocksDB or FASTER with C++ for my work.

It uses a scheme where one key is used for every attribute of each row, like the following example.

$table_name:$primary_key_value:$attribute_name = $value

The above is fine for point lookups when usercode is aware about exactly which key to get. But there are scenarios like searching for users having same email address, or searching for users above a certain age or searching for users of one specific gender. In search scenarios the article performs a linear scan through all keys. In each iterations it checks the pattern of the key and applies the business logic (checking the value for match) once a key with a matching pattern is found.

It seems that, such type of searching is inefficient and in worst case it needs to traverse through the entire store. To solve that a reverse lookup table is required. My question is

How to model the reverse lookup table ? Is it some sort of reinvention of wheel ? Is there any alternative way ?

One solution that readily comes in mind is to have a separate ? store for each index-able property like the following.

$table_name:$attribute_name:$value_1 = $primary_key_value 

With this approach the immediate question is

How to handle collisions in this reverse lookup table ? because multiple $primary_keys may be associated with the same vale.

As an immediate solution, instead of storing a single value an array of multiple primary keys can be stored as shown below.

$table_name:$attribute_name:$value_1 = [$primary_key_value_1, ... , $primary_key_value_N]

But such type of modeling requires usercode to parse the array from string and again serialize that to string after manipulation several times (assuming the underlying key-value store is not aware about array values).

Is it efficient to store multiple keys as array value ? or there exists some vendor provided efficient way ?

Assuming that the stringifi'ed array like design works, there has to be such indexes for each indexable properties. So this gives a fine grained control on what to index and what not to index. Next design decision that comes in mind is where these indexes will be store ?

should the indexes be stored in a separate store/file ? or in the same store/file the actual data belongs to ? Should there be a different store for each property ?

For this question, I don't have a clue because both of these approaches require more or less same amount of I/O. However having large data file will have more things on disk and fewer things on memory (so more I/O), whereas for multiple files there will be more things on memory so less page faults. This assumption could be totally wrong depending on the architecture of the specific key-value store. At the same time having too many files turns into a problem of managing a complicated file structure. Also, maintaining indexes require transactions for insert, update and delete operations. Having multiple files results into single updation in multiple trees, whereas having single file results into multiple updation in single tree.

Is transaction more specifically transaction involving multiple store/files supported ?

Not only the indices there are some meta information of the table that are also required to be kept along with the table data. To generate a new primary key (auto incremented) it is required to have prior knowledge about the last row number or last primary key generated because something like a COUNT(*) won't work. Additionally as all keys are not indexed, the meta information may include what properties are indexed and what properties are not indexed.

How to store the meta information of each table ?

Again the same set of questions appear for the meta table also. e.g. should the meta be a separate store/file ? Additionally as we have noticed that not all properties are indexed we may even decide to store each row as a JSON encoded value in the data store and keep that along with the index stores. The underlying key-value store vendor will treat that JSON as a string value like the following.

$table_name:data:$primary_key_value = {$attr_1_name: $attr_1_value, ..., $attr_N_name: $attr_N_value}
...
$table_name:index:$attribute_name = [$primary1, ..., $primaryN]

However reverse lookups are still possible through the indexes pointing towards the primary key.

Is there any drawbacks of using JSON encoded values instead of storing all properties as separate keys ?

So far I could not find any draw backs using this method, other than forcing the user to use JSON encoding, and some heap allocation in for JSON encoding/decoding.

The problems mentioned above is not specific to any particular application. These problems are generic enough to be associated to all developments using key-value store. So it is essential to know whether there is any reinvention of wheel.

Is there any defacto standard solution of all the problems mentioned in the question ? Does the solutions differ from the one stated in the question ?

Answer 1

How to model the reverse lookup table ? Is it some sort of reinvention of wheel ? Is there any alternative way ?

• All the ways you describe are valid ways to create an index.
• It does not re-invent the wheel in RocksDB because RocksDB does not support indices.
• It really depends on the data, in general you will need to copy the index value and the primary key into another space to create the index.

How to handle collisions in this reverse lookup table ? because multiple $primary_keys may be associated with the same vale.

You can serialize pks using JSON (or something else). The problem with that approach is when the pks grow very large (which might or might not be a thing).

Is it efficient to store multiple keys as array value ? or there exists some vendor provided efficient way ?

With RocksDB, you have nothing that will make it "easier".

You did not mention the following approach:

$table_name:$attribute_name:$value_1:$primary_key_value_1 = ""
$table_name:$attribute_name:$value_1:$primary_key_value_2 = ""
...

$table_name:$attribute_name:$value_1:$primary_key_value_n = ""

Where the value is empty. And the indexed pk is part of the key.

should the indexes be stored in a separate store/file ? or in the same store/file the actual data belongs to ? Should there be a different store for each property ?

It depends on the key-value store. With rocksdb, if you need transactions, you must stick to one db file.

Is transaction more specifically transaction involving multiple store/files supported ?

Only Oracle Berkeley DB and WiredTiger support that feature.

How to store the meta information of each table ?

metadata can be in the database or the code.

Is there any drawbacks of using JSON encoded values instead of storing all properties as separate keys ?

Yeah, like I said above, if you encoded all pks into a single value, it might lead to problem downstream when the number of pk is large. For instance, you need to read the whole list to do pagination.

Is there any defacto standard solution of all the problems mentioned in the question ? Does the solutions differ from the one stated in the question ?

To summarize:

• With RocksDB, Use a single database file
• In the index, encode the primary key inside the key, and leave value empty, to be able to paginate.