Rethinking key value store

In this post i will share how key-value stores can be used for building different types of application, but before we start deep dive lets do quick recap of database systems.

Database technology is made of 2 important components ( Storage + Query). Such type of architecture allow to replace part of system or only build storage or query part of it and reuse other from open source.

Many modern database are taking advantage of plugin architecture and focusing on only one part of system, for example storage could be again broken down in various format based on access pattern for reads/write

 

Each storage format ( hash,b-tree,lsm or log) is optimized for specific read/write access pattern. Many database uses multiples format also.

Once we come to storage format then Row vs Column layout also comes in play, so in nutshell it is hard to build storage system, so it makes sense to use off the self solution rather than building something from ground up.

Query area is also huge as this include different types of API, Query engine, Optimizer , transactions etc

%3CmxGraphModel%3E%3Croot%3E%3CmxCell%20id%3D%220%22%2F%3E%3CmxCell%20id%3D%221%22%20parent%3D%220%22%2F%3E%3CmxCell%20id%3D%222%22%20style%3D%22edgeStyle%3Dnone%3Brounded%3D1%3BorthogonalLoop%3D1%3BjettySize%3Dauto%3Bhtml%3D1%3BentryX%3D0.5%3BentryY%3D0%3BentryDx%3D0%3BentryDy%3D0%3B%22%20edge%3D%221%22%20source%3D%224%22%20target%3D%228%22%20parent%3D%221%22%3E%3CmxGeometry%20relative%3D%221%22%20as%3D%22geometry%22%2F%3E%3C%2FmxCell%3E%3CmxCell%20id%3D%223%22%20style%3D%22edgeStyle%3Dnone%3Brounded%3D1%3BorthogonalLoop%3D1%3BjettySize%3Dauto%3Bhtml%3D1%3BentryX%3D0.5%3BentryY%3D0%3BentryDx%3D0%3BentryDy%3D0%3B%22%20edge%3D%221%22%20source%3D%224%22%20target%3D%229%22%20parent%3D%221%22%3E%3CmxGeometry%20relative%3D%221%22%20as%3D%22geometry%22%2F%3E%3C%2FmxCell%3E%3CmxCell%20id%3D%224%22%20value%3D%22Storage%22%20style%3D%22rounded%3D1%3BwhiteSpace%3Dwrap%3Bhtml%3D1%3BfillColor%3D%23fff2cc%3BstrokeColor%3D%23d6b656%3B%22%20vertex%3D%221%22%20parent%3D%221%22%3E%3CmxGeometry%20x%3D%22320%22%20y%3D%22270%22%20width%3D%22200%22%20height%3D%2240%22%20as%3D%22geometry%22%2F%3E%3C%2FmxCell%3E%3CmxCell%20id%3D%225%22%20style%3D%22rounded%3D1%3BorthogonalLoop%3D1%3BjettySize%3Dauto%3Bhtml%3D1%3B%22%20edge%3D%221%22%20source%3D%228%22%20target%3D%2210%22%20parent%3D%221%22%3E%3CmxGeometry%20relative%3D%221%22%20as%3D%22geometry%22%2F%3E%3C%2FmxCell%3E%3CmxCell%20id%3D%226%22%20value%3D%22%22%20style%3D%22rounded%3D0%3BorthogonalLoop%3D1%3BjettySize%3Dauto%3Bhtml%3D1%3B%22%20edge%3D%221%22%20source%3D%228%22%20target%3D%2211%22%20parent%3D%221%22%3E%3CmxGeometry%20relative%3D%221%22%20as%3D%22geometry%22%2F%3E%3C%2FmxCell%3E%3CmxCell%20id%3D%227%22%20style%3D%22rounded%3D0%3BorthogonalLoop%3D1%3BjettySize%3Dauto%3Bhtml%3D1%3BentryX%3D0.342%3BentryY%3D-0.033%3BentryDx%3D0%3BentryDy%3D0%3BentryPerimeter%3D0%3B%22%20edge%3D%221%22%20source%3D%228%22%20target%3D%2212%22%20parent%3D%221%22%3E%3CmxGeometry%20relative%3D%221%22%20as%3D%22geometry%22%2F%3E%3C%2FmxCell%3E%3CmxCell%20id%3D%228%22%20value%3D%22Disk%22%20style%3D%22rounded%3D1%3BwhiteSpace%3Dwrap%3Bhtml%3D1%3BfillColor%3D%23f8cecc%3BstrokeColor%3D%23b85450%3B%22%20vertex%3D%221%22%20parent%3D%221%22%3E%3CmxGeometry%20x%3D%22250%22%20y%3D%22360%22%20width%3D%22140%22%20height%3D%2230%22%20as%3D%22geometry%22%2F%3E%3C%2FmxCell%3E%3CmxCell%20id%3D%229%22%20value%3D%22Memory%22%20style%3D%22rounded%3D1%3BwhiteSpace%3Dwrap%3Bhtml%3D1%3BfillColor%3D%23e1d5e7%3BstrokeColor%3D%239673a6%3B%22%20vertex%3D%221%22%20parent%3D%221%22%3E%3CmxGeometry%20x%3D%22480%22%20y%3D%22360%22%20width%3D%22120%22%20height%3D%2235%22%20as%3D%22geometry%22%2F%3E%3C%2FmxCell%3E%3CmxCell%20id%3D%2210%22%20value%3D%22Flash%2FSSD%22%20style%3D%22rounded%3D1%3BwhiteSpace%3Dwrap%3Bhtml%3D1%3BfillColor%3D%23f8cecc%3BstrokeColor%3D%23b85450%3B%22%20vertex%3D%221%22%20parent%3D%221%22%3E%3CmxGeometry%20x%3D%2290%22%20y%3D%22440%22%20width%3D%22120%22%20height%3D%2230%22%20as%3D%22geometry%22%2F%3E%3C%2FmxCell%3E%3CmxCell%20id%3D%2211%22%20value%3D%22HDD%22%20style%3D%22rounded%3D1%3BwhiteSpace%3Dwrap%3Bhtml%3D1%3BfillColor%3D%23f8cecc%3BstrokeColor%3D%23b85450%3B%22%20vertex%3D%221%22%20parent%3D%221%22%3E%3CmxGeometry%20x%3D%22240%22%20y%3D%22450%22%20width%3D%22120%22%20height%3D%2230%22%20as%3D%22geometry%22%2F%3E%3C%2FmxCell%3E%3CmxCell%20id%3D%2212%22%20value%3D%22Cloud%22%20style%3D%22rounded%3D1%3BwhiteSpace%3Dwrap%3Bhtml%3D1%3BfillColor%3D%23f8cecc%3BstrokeColor%3D%23b85450%3B%22%20vertex%3D%221%22%20parent%3D%221%22%3E%3CmxGeometry%20x%3D%22370%22%20y%3D%22480%22%20width%3D%22120%22%20height%3D%2230%22%20as%3D%22geometry%22%2F%3E%3C%2FmxCell%3E%3CmxCell%20id%3D%2213%22%20style%3D%22edgeStyle%3Dnone%3Brounded%3D1%3BorthogonalLoop%3D1%3BjettySize%3Dauto%3Bhtml%3D1%3BentryX%3D0.5%3BentryY%3D0%3BentryDx%3D0%3BentryDy%3D0%3B%22%20edge%3D%221%22%20source%3D%2214%22%20target%3D%224%22%20parent%3D%221%22%3E%3CmxGeometry%20relative%3D%221%22%20as%3D%22geometry%22%2F%3E%3C%2FmxCell%3E%3CmxCell%20id%3D%2214%22%20value%3D%22API%22%20style%3D%22rounded%3D1%3BwhiteSpace%3Dwrap%3Bhtml%3D1%3BfillColor%3D%23dae8fc%3BstrokeColor%3D%236c8ebf%3B%22%20vertex%3D%221%22%20parent%3D%221%22%3E%3CmxGeometry%20x%3D%22320%22%20y%3D%22190%22%20width%3D%22200%22%20height%3D%2240%22%20as%3D%22geometry%22%2F%3E%3C%2FmxCell%3E%3CmxCell%20id%3D%2215%22%20style%3D%22edgeStyle%3Dnone%3Brounded%3D1%3BorthogonalLoop%3D1%3BjettySize%3Dauto%3Bhtml%3D1%3BentryX%3D0.5%3BentryY%3D0%3BentryDx%3D0%3BentryDy%3D0%3B%22%20edge%3D%221%22%20source%3D%2216%22%20target%3D%2214%22%20parent%3D%221%22%3E%3CmxGeometry%20relative%3D%221%22%20as%3D%22geometry%22%2F%3E%3C%2FmxCell%3E%3CmxCell%20id%3D%2216%22%20value%3D%22SQL%22%20style%3D%22rounded%3D1%3BwhiteSpace%3Dwrap%3Bhtml%3D1%3BfillColor%3D%2360a917%3BstrokeColor%3D%232D7600%3BfontColor%3D%23ffffff%3B%22%20vertex%3D%221%22%20parent%3D%221%22%3E%3CmxGeometry%20x%3D%22260%22%20y%3D%22110%22%20width%3D%22120%22%20height%3D%2230%22%20as%3D%22geometry%22%2F%3E%3C%2FmxCell%3E%3CmxCell%20id%3D%2217%22%20style%3D%22edgeStyle%3Dnone%3Brounded%3D1%3BorthogonalLoop%3D1%3BjettySize%3Dauto%3Bhtml%3D1%3BentryX%3D0.5%3BentryY%3D0%3BentryDx%3D0%3BentryDy%3D0%3B%22%20edge%3D%221%22%20source%3D%2218%22%20target%3D%2214%22%20parent%3D%221%22%3E%3CmxGeometry%20relative%3D%221%22%20as%3D%22geometry%22%2F%3E%3C%2FmxCell%3E%3CmxCell%20id%3D%2218%22%20value%3D%22Key%20Value%22%20style%3D%22rounded%3D1%3BwhiteSpace%3Dwrap%3Bhtml%3D1%3BfillColor%3D%231ba1e2%3BstrokeColor%3D%23006EAF%3BfontColor%3D%23ffffff%3B%22%20vertex%3D%221%22%20parent%3D%221%22%3E%3CmxGeometry%20x%3D%22450%22%20y%3D%22110%22%20width%3D%22120%22%20height%3D%2230%22%20as%3D%22geometry%22%2F%3E%3C%2FmxCell%3E%3CmxCell%20id%3D%2219%22%20value%3D%22Database%20Engine%22%20style%3D%22text%3Bhtml%3D1%3BstrokeColor%3Dnone%3BfillColor%3Dnone%3Balign%3Dcenter%3BverticalAlign%3Dmiddle%3BwhiteSpace%3Dwrap%3Brounded%3D0%3BfontFamily%3DVerdana%3BfontSize%3D18%3BfontStyle%3D1%22%20vertex%3D%221%22%20parent%3D%221%22%3E%3CmxGeometry%20x%3D%22320%22%20y%3D%2230%22%20width%3D%22200%22%20height%3D%2240%22%20as%3D%22geometry%22%2F%3E%3C%2FmxCell%3E%3C%2Froot%3E%3C%2FmxGraphModel%3E

With some high level understanding of databases now we can now focus on specific type of storage system and try to explore what types of application can be built on it.

Key-Value store is very popular storage system options. 

Key value store are like hash table that is designed to store/retrieve key & value tuple. Key-Value store can be memory or disk based. Some key value stores variations like B-Tree or LSM tree are ordered key value store.

Ordered KV stores provide efficient range scan and is very important if client interface is SQL like.

I will used ordered KV store as example to share type of application that can be build. I will use ecommerce Order data model as example for all the usecase

- Row Store

  This is the most straight forward use-case for any KV stores and also very good fit for building unique index for primary key. For order table KV store will contain below entry

Order/OrderId/1 -> {......}

Order/OrderId/2 -> {......}

Order/OrderId/3 -> {......}

Important thing to note in this format is that it contains fully qualified id of record that us made up of {table name}/{PK Column}/{PK Value}.

This type of key provides flexibility to use single KV store for multiple tables, another advantage that we get it since all the values are ordered by Key so query has to load less numbers of pages to get all the data for this table.

- Indexes

Ordered KV store can be extended to build non unique indexes also so that it can be used as efficient lookup table for underlying data.

Lets try to build couple of non unique index on order table.

Index on customer id 

Order/CustomerId/100/1 -> {......}

Order/CustomerId/101/1 -> {......}

Order/CustomerId/102/2 -> {......}

Index on Order Date

Order/OrderDate/20201001/1 -> {......}

Order/OrderDate/20201001/2 -> {......}

Order/OrderDate/20201010/3 -> {......}

Before i show other complex example lets try to understand format of key, it is contains "{table name}/{Index Col}/{Index Value}/{PK}" pattern, this pattern allow to handle duplicate values in index because primary key is suffix of every entry.

Lets keep going on this with little more complex example of index by Status & Order date

Order/StatusByOrderDate/CANCELLED_20201010/3 -> {......}

Order/StatusByOrderDate/CANCELLED_20201010/6 -> {......}

Order/StatusByOrderDate/PENDING_20201001/2 -> {......}

Order/StatusByOrderDate/PENDING_20201001/7 -> {......}

Order/StatusByOrderDate/PENDING_20201003/8 -> {......}

Order/StatusByOrderDate/SHIPPED_20201001/1 -> {......}

In above example Index key is made of 2 column.

- Range Scans

By this point it will be becoming clear how efficient range scan can be done with above index data.

Lets use some example query to verify this .

 - find all the orders that are cancelled between 20201001 to 20201015.

Above query can be resolved by looking for all the records between Order/StatusByOrderDate/CANCELLED_20201001 to Order/StatusByOrderDate/CANCELLED_20201031

- find all the orders that are cancelled in Oct 2020.

All records matching Order/StatusByOrderDate/CANCELLED_202010 pattern

-find all the pending orders

All records matching Order/StatusByOrderDate/PENDING pattern

One thing to note that all the related keys are together and can be retrieved using less number of IO operations. 

- Partition Index

Distributed databases creates partitions to split big data into chunk of manageable data so that it can be distributed and replicated.

Partition can be done using hash key or by key range. Key range based partition are must of interface is SQL or allows range scanning. 

Lets take above data for key column as example set to distributed. 

One way to create partition is to create partition of size 5 and store start & end key of that partition with data node reference, so that query looking for data in that range can be quickly resolved.

Partition index might look something like below.

- Column Store

One more place where ordered KV stores shines is creating column store.

We need slight change in format to achieve column store, it will use {table name}/{column}/{pk} -> {column value} format

This type of key format will put all the column for given table together.

Any query that needs selective column can take advantage of this layout as all the column are next to each other.

 

- SQL

Last one is building SQL interface on ordered map! SQL query need 2 basic operation to answer all the request

 - Point lookup

 - Range scan

With above examples of KV stores it is easy to build simple SQL using above mention access pattern.

Sample Application

As part of the research for this post, i build implementation that is based on all the ideas shared above. High level architecture of simple implementation looks something like below

In this application i have used 3 implementation of Ordered map to show underlying storage can be changed without given up on any functionality. 

- SkipList 

This is java "ConcurrentSkipListMap", which is in memory ordered map and is used in many real open source database to build memory store on top of LSM tree. Cassandra uses SkipList data structure for Memory table.

- B Tree

H2 database is based on B-Tree storage called "MVStore", it is possible to use MvStore as library. I used MVStore as B-Tree storage

- LSM Tree

Many implementation are available and popular ones are LevelDB, RocksDB etc. I used RocksDB as it is already used in many databases as storage engine. MyRocks, CassandraRocks, cockroachdb  etc

Implementation is based on 2 interface ( KeyValueStore & SSTable) to expose both key value and SQL interface on different storage backend.

public interface KeyValueStore {

    <Row_Type> SSTable<Row_Type> createTable(String tableName, Class<Row_Type> type,
                                             Map<String, Function<Row_Type, Object>> schema,
                                             Map<String, Function<Row_Type, String>> indexes);

    <Row_Type> SSTable<Row_Type> createTable(String tableName, Class<Row_Type> type,
                                             Map<String, Function<Row_Type, Object>> schema);

    <Row_Type> SSTable<Row_Type> createTable(TableInfo<Row_Type> tableInfo);

    List<String> desc(String table);

    void close();

    <Row_Type> SSTable<Row_Type> table(String tableName);

    default void execute(String sql, Consumer<RowValue> consumer) {
        new SqlAPI(this).execute(sql, consumer);
    }
}

 

public interface SSTable<T_TYPE> {
    List<String> cols();

    //Search functions
    void scan(Consumer<T_TYPE> consumer, int limit);

    void search(String indexName, String searchValue, Consumer<T_TYPE> consumer, int limit);

    void search(String indexName, String searchValue, Collection<T_TYPE> container, int limit);

    void rangeSearch(String index, String startKey, String endKey, Collection<T_TYPE> container, int limit);

    T_TYPE get(String pk);

    default Map<String, Function<T_TYPE, Object>> schema() {
        return null;
    }

    default Map<String, Function<T_TYPE, String>> indexes() {
        return null;
    }

    default Object columnValue(String col, Object row) {
        return null;
    }

    //Mutation functions
    void insert(T_TYPE row);

    void update(T_TYPE record); // Secondary index needs rebuilding
}

All the code is available on github @ query repo.

Each implementation is unit tested using contract based test, so feel free to experiment with it.

While implementation first i build KV related functionality and at the end added simple SQL interface. Adding simple SQL was done with help of Calcite SQL parser. Once basic query primitive was available ( point and range scan) then simple SQL interface was easy to add and that is the reason why i have "sql" as default function on interface. 

Conclusion

Ordered KV store are powerful data structure and can be used for solving many interesting problems. Many commercial and open source database are using some of techniques mention in post. 

In this post i have intentionally not covered about how to handle different data types and how to optimized Index key. These are things that can be solved by better encoding that still maintains sort property of key.

I plan to cover about encoding rules in future post.

Data modeling is everything

Everyone is aware of relation data modeling and it has served industry for long time but as data pressure increased relation data modeling that is based on Edgar_F._Codd rules are not scaling well. 

Data modeling

Those rules were based on hardware limit in 1970s and RDMS database took all that stuff and build database that was good fit based on hardware limit of 70s.

We are in 2020 and time has changed, hardware is so much cheap and better. Look at storage price over period of time.

Many data system has taken advantage of cheap storage to build highly available & reliable systems. Some of RDMS are still playing catch up game. I would say NoSQL has taken lead by leveraging this.

Data modeling is very different when storage is not an issue or bottleneck, today limit is CPU because they are not getting faster, you can have more but not faster. Lets look at some of the data modeling technique that can be used today even with your favorite RDBMS to get blazing fast performance. 

One thing before diving in modeling that real world is relational and data will always have relations, so any modeling technique that can't handle 1-2-1 , 1-2-Many or Many-2-Many etc is useless. Each data model has trade off and it is designed with purpose and it could be optimizing for write or read for specific access pattern.

Few things that makes RDBMS slow are unbounded table scans , Joins and Aggregation. If we build data model that does not need these slow operation then we can build blazing fast systems!
Most of RDBMS is key value store with B-Tree index on top of it, if all the query to DB can be turned into key lookup or small index scan then we can best out of databases.

With that lets dive into some of the ideas to avoid joining Dataset.

Use non scalar attribute type

Specially for complex relationship like customer to preference, customer to address , Fedex delivery to destinations, customer to payment options etc we tend to create table to have multiple rows and then join with foreign key at read time. 

If such type of request comes to your system millions time a day and then it not really good option to do join million time. What should we do then ? 

Welcome to non scalar type of your data storage system use maps, list, vector or blob.

I know this may sound like crazy but just by using above stated type you have avoided join and saved big CPU cost million time. You should also know the trade off this pattern, now it is no more possible to use plan SQL to see the value of non scalar column but that is just tooling gap and can be addressed.

Code snippet for such data model

Many join i have avoided using this pattern and user experience has improved so much with this. Database will load this column for free and you can assemble it in application layer if database does not support that.

One more thing to be aware with this is that column value should not be unbounded, put some limit and chunk it when limit is crossed to keep your favorite database happy.

Duplicate immutable attributes
This pattern need more courage to use. If you clearly know that some thing in system is immutable like product name ,  desc , brand , seller etc then anytime product is referred like order item refer to product that is bought then you can copy all the immutable attributes of product to order item. 
  

Showing order details is very frequent access pattern in e-commerce site and such type of solution will help with that access pattern.
Trade off involved is that if attributes are not immutable then this has overhead of updating it whenever referenced entity is changed but if that does not changes frequently then you will benefit with this in big way.

- Single table or multi entity table
This will definitely get most resistant because seems like insult to RDBMS but we have this done in past remember those parent child query where both parent and child is stored in single table and we join with parent and id. Employee and manager was modeled like this for many years. 

Lets take another example for parent & child relationship. 
Class and student is also classic example where class will have many student and vice-versa.

Anytime we want to show details of all the student for specific class then we make first query to get class id and then all the student for that class or we can join based on class id.

How can we avoid join or sequential load dependency? 
When we write the join query we are trying to create de-normalized view at runtime and discard it after request is served but what if this view is created at the write time then we managed to pre-join data and we just avoid the join at runtime.


This model is using generic name(pk1,pk2) for identifying entity in single table, this looks little different but is very powerful because with pre-join data we can get answer of questions like 

 - Single class details ( pk1="class:c1" , pk2="class:c1") 
 - Single student for given class( pk1="class:c1" , pk2="student:s1" ).

 - Both class and all the students (pk1="class:c1")
 - All the student of given class (pk1="class:c1" ,  pk2!="class:c1" )

Lets add one more scenario to get all the classes student is attending. This need just flipping pk1 and pk2 to make it something like 

Registration("student:s1", "class:C1", className = "science", classDesc = "Science for Primary kids")

Registration("student:s1", "class:C2", className = "Maths", classDesc = "Basic Algebra")

I would say that this is one of the most different one and needs out of the box thinking to give a try but with this you can solve many use case.

 - Projected column index
This is common one where projection and aggregation is done upfront and can be treated like de-normalization view at write time. If aggregation is linear like sum, avg, max , min then aggregation can be done incremental. This will avoid running Group By query for every request. Think how much CPU can be saved by using this simple pattern.

- Extreme projection index
This is extension of above pattern taking to next level by calculating projection at every level and very effective for hierarchy based query. This can help in totally avoiding group and aggregation at read time.

   
Conclusion
All the patterns shared are nothing new and are taking advantage of cheap storage to avoid de-normalization at read time. 
If all the joins and most aggregation can be done at write time then reads are so fast that it might feel that you are not hitting any database.

In this post we did not touch on data partition strategy but that also plays important role in building system that user love to use.

Time to get little closer to your data and spend time in understanding access pattern and hardware limit before design system!