#key-value store

Since a lot of KVS already exist, It’d be interesting to look at previously developed models, to get some inspiration.

Examples of KVS :

DBM

Berkeley DB

Kyoto Cabinet

Memcached and MemcacheDB

LevelDB

MongoDB

Redis

OpenLDAP

SQLite

Requirements for our KVS :

KVS designed for OOP

everything will be on-disk

network access to data store

no ACID 

no need for a query engine 

Berkeley DB : implemented in C, is an open source embedded (runs in the same address as the app, no inter-process comm for database operations) database library for scalable, high-performance, transaction-protected data management services to apps.

Kyoto Cabinet : implemented in C++, implements a hash table a B+ tree and other DS,but performance changes if the database’s size goes above a limit (ooooof course).

LevelDB: implemented in C++, implements a LSM (log-structured merge tree, which are optimized for SSD drives). For more than one million entries, performance drops. Clear source code though, and for a personal project, we don’t require a heavy load so that’s fine.

The different states and the transitions of a Couchbase node in a diagram:

This post describes the states and actions that can trigger the transitions. One interesting aspect is that state changes are not applied immediately and you can commit multiple such changes at once when satisfied with the new topology.

In an interview with Bob Widerhold1, Roberto V. Zicary asks: “why Couchbase Lite is so strategically important?”

Bob Wiederhold: First, because the world is going mobile. That is indisputable. Mobile initiatives top the list of every IT department. As I said above, if you don’t have a mobile data management offering, you are not looking at the complete needs of the developer or the enterprise.

Second, let’s level set on Couchbase Lite. Couchbase Lite is our offering for an embedded mobile JSON database.

Our complete mobile offering, Couchbase Mobile, includes Couchbase Server – for data management in the cloud, and Sync Gateway for synchronization of data stored on the device with other devices, or the database in the cloud. Today, because connectivity is unknown, data synchronization challenges force developers to either choose a total online (data stored in the cloud), or total offline (data stored on the device) data management strategy.

Maybe I’m seeing things from the wrong perspective:

the data synching between the disconnected device and the central databases needs to see very low contention; resolving conflicts on the device would be much more difficult than having a server component solving it;

as far as I can tell, the king of storage on mobile phones is SQLite; I somehow doubt that JSON + map/reduce can beat it;

while not an expert in iOS services, I think the CloudKit already covers the local-to-remote storage sync problem.

What am I missing?

Bob Widerhold is CEO of Couchbase. ↩

While we are in the era of specialized databases, tunable solutions are always preferable. As we all know by now, in the land of distributed system one of the most non-trivial decisions, and trade-offs, is between availability and consistency. It’s usually the first that is harder to achieve. But that doesn’t mean that strong consistency cannot be a mandatory requirement for some applications.

Many data needs are better served by data stores that are optimized for maximum availability and scalability — rather than optimized for consistency. For certain use cases, there are elements to the data that require strong consistency. With Riak 2.0, in addition to eventual consistency, there is now a way to enforce strong consistency when needed.

The rest of the post covers how strong consistency buckets work in Riak 2.0. It also lists the current trade-offs:

read-before-writes

secondary indexes are not yet supported

multi-datacenter replication is not yet supported

Salvatore Sanfilippo:

Can we have a fast and reliable system at the same time based on Redis? This blog post is an exploration in this area. I’ll try to describe a proposal for a simple algorithm to use N Redis instances for distributed and reliable locks, in the hope that the community may help me analyze and comment the algorithm to see if this is a valid candidate.

As much as I like Redis, use this post as an exercise on how to reason about distributed locks and stick with ZooKeeper for the implementation.

Tom Crayford (Yeller) describes how to test the merge and serialization functions used to resolve potential conflicts in Riak:

The way I prefer using riak, is with allow_mult=true. This means that whenever you have causally conflicting writes to a key, riak will store all of them, and upon your next read of that key you have to resolve them yourself. Designing your datatypes such that you can merge them is a huge topic, and an area of active research. However, even once you have a merge strategy worked out, how can you be sure that your reasoning is good? The merge functions you use have to obey a few properties: they have to be commutative, idempotent and associative, or you’ll mess things up when you have conflicts

Tony Darnell in Use MySQL to store NoSQL and SQL data in the same database using memcached and InnoDB | Scripting MySQL:

With MySQL version 5.6 (and above), you have the ability to store and retrieve NoSQL data, using NoSQL commands, while keeping the data inside a MySQL InnoDB database. So, you can use NoSQL and SQL at the same time, on the same data, stored in the same database. And the beauty is that it takes just a few minutes to setup. This post will provide you with a quick lesson on how to setup NoSQL on a MySQL InnoDb database.

I see this trivialization of the term NoSQL quite frequently in the communications signed by Oracle: “Oh, you want NoSQL? Take memcached. Now shut up!” This is quite disrespectful to their customers and the developer community in general.

John Daily covers Riak’s mechanisms for bringing data in sync across the nodes:

Riak’s overarching design goal is simple: be maximally available. […] In order to make sure your data can survive server failures, Riak retains multiple copies (replicas) and allows lock-free, uncoordinated updates. […] This then open ups the possibility that data will be out of sync across a cluster. Riak manages this issue in three distinct stages: entropy detection, correction, and conflict resolution.

You’ll read pitches from products promising both maximal availability and no out-of-date data. Those are just that promises.