Key-Value Databases

I used a key-value database to store data on one project and would like to share a few things I learned. I chose Voldemort because it’s written entirely in Java. Voldemort began as an internal project used by LinkedIn, was later released as open source, and is still being developed.

Before going into more detail, I should show the client API you use to talk to Voldemort, the kind you can expect from any key-value database. It’s a map-like interface with three methods: put, get and delete.

String key = "dagblog.url";
client.put(key, "http://dagblog.cz");
String value = client.get(key);
client.delete(key);

When to use a key-value database

The simple answer is anywhere a relational or other kind of database is a poor fit. I chose one for two reasons: performance and the simplicity of the data I was storing. That second assumption didn’t survive further development. ;-) Since all operations are keyed, scaling is straightforward (seeVoldemort’s architecture), and response times are relatively steady no matter how much data you store.

That brings us to the API itself. You may have noticed there’s no method for searching the data and no query language such as SQL. That means several significant architectural constraints you need to take into account.

• You can’t project data by joining two or more entities. We’ll get to how to handle joins later. To get at the data, you need to know its key.
• You can’t retrieve only part of a value. In relational database and SQL terms, you can’t specify columns in the select clause.
• You can’t query for all data of a given type. In SQL terms, there’s no select * from table.
• The API provides no transactions or integrity enforcement. Keeping data consistent is entirely the application’s responsibility.

First, why is it like this? Second, who benefits? These constraints all make it easy to scale and get tremendous performance. They also tell you that a key-value database won’t suit applications that need to run complex queries over the data, or those where temporary inconsistency, as several related values under different keys change state, would be a problem. Think of transferring money from one account to another.

Key-value databases have benefits besides performance. The simple API makes them easy to mock. You can test and develop every part that depends on the database with a mock that keeps the data you need in an in-memory map. The data you store as values needn’t be normalized as it would be in a relational database.

Practical experience with Voldemort

I ended up storing fifteen entities in the key-value database. I call them entities because I needed to store a fairly complex graph of different entities or classes, along with a few supporting structures.

Because I was storing a graph and needed to retrieve parts of it, I had to break it up to some extent. Each part stored separately had its own dedicated space called a store, the equivalent of a table in a relational database.

Each store can use different strategies to serialize and deserialize the keys and values. Voldemort supports several formats, including JSON, Thrift, Protocol Buffers, Java serialization and others. In practice that means you can serialize whole objects. I used JSON so that each store had a defined structure.

public class User {
 private String firstName;
 private String lastName;
    
    ...
}

With JSON, the store format was {“firstName”:”string”,”lastName”:”string”}. Java represented it as a java.util.Map, which Voldemort requires for storing data in this format.

User user = new User("john", "doe");
Map value = new HashMap();
value.put("firstName", user.getFirstName());
value.put("lastName", user.getLastName());

//uložení dat
client.put(1, value);

//načtení dat
Map map = client.get(1);
String firstName = map.get("firstName");
String lastName = map.get("lastName");

Here’s what the code would look like with the store configured to use Java serialization. The User object has to implement java.io.Serializable.

User user = new User("john", "doe");

//uložení dat
client.put(1, user);

//načtení dat
User user = client.get(1)

Handling joins

As mentioned, key-value databases don’t do joins. If you need them, you either implement them in code or account for them when designing the store. Let’s start with doing it in code. Suppose a User entity is stored in one store and an Address entity in another. Given a user, I need to find all their addresses. The simplest solution is to record all the address keys when I save the user.

Address address = new Address("Na konci světa", "Zatavi", "12345");
User user = new User("john", "doe", address);

Map addressValue = new HashMap();
addressValue.put("street", address.getStreet());
addressValue.put("city", address.getCity());
addressValue.put("zipcode", address.getZipcode());

addressClient.put(1, addressValue);

Map userValue = new HashMap();
userValue.put("firstName", user.getFirstName());
userValue.put("lastName", user.getLastName());
//uložíme se klíče asociovaných adress
userValue.put("addressKeys", Arrays.asList(new Integer[]{1});

userClient.put(1, userValue);

The join in code when reading follows the same pattern.

Map userValue = userClient.get(1);
List addressKeys = userValue.get("addressKeys");
for(int key: addressKeys) {
 Map addressValue = addressClient.get(key);
}

This bit of code fetches all the associated addresses. Voldemort also offers a bulk get, so instead of looping through the keys I could pass the whole set at once. Splitting storage by entity isn’t always desirable, particularly with key-value databases. The only real reason to split it is if you have a large amount of data or need to get or put it independently of the rest of the system. If you find you need to split your data extensively, that’s a sign a key-value database may be a poor fit.

To avoid a join, you can store the data together in one store. In our example it might look like this.

Address address = new Address("Na konci světa", "Zatavi", "12345");
User user = new User("john", "doe", address);

Map addressValue = new HashMap();
addressValue.put("street", address.getStreet());
addressValue.put("city", address.getCity());
addressValue.put("zipcode", address.getZipcode());

Map userValue = new HashMap();
userValue.put("firstName", user.getFirstName());
userValue.put("lastName", user.getLastName());
userValue.put("addresses", Arrays.asList(new Map[]{addressValue});

client.put(1, userValue);

Or, if we use Java serialization:

Address address = new Address("Na konci světa", "Zatavi", "12345");
User user = new User("john", "doe", address);

client.put(1, user);

Observations

On the project where I used Voldemort, I wrote a thin layer to store individual entities transparently. Each entity had three methods: one to return its key, one to return a map representation of itself as the value, and one to reconstruct its state from a map. I also implemented lazy loading for entities in the object graph that hadn’t yet been fetched. That reduced the number of storage queries and the overall volume of data transferred.

With Voldemort, and I think this goes for key-value databases generally, the persistence layer grew considerably. It had to handle all the logic for joins, splitting and storing objects, checking consistency and so on. That took work, but in return I got code written entirely in Java that was easy to test.

Conclusion

A key-value database won’t suit every project. Its underlying concept is so different that you can’t treat it as a complete replacement for a relational database. Among other things, the patterns and techniques we learned from relational databases don’t carry over. If you start thinking of a key-value database in relational terms, consider whether it gives you what you need or whether something in the design has gone wrong.

A key-value database can work very well alongside a relational, document or object database. Use a key-value database where it suits a particular job in the application and keep the remaining data in a conventional relational database.