I have some concurrent key-value store implementations that are implemented with hash tables and search trees that I would like to compare. I would like to benchmark them with a real world application where several threads stresses the key-value stores.

I already have some micro-benchmark that stresses the key-value stores by executing random operations on the key-value stores in parallel. What I'm interesting in now is applications that do some work that could be useful in the "real world" and where one or several key-value stores are important for scalability and speed. I would like to have a benchmark that is easy to set up and that could be run on many different system. I would prefer if it does not involve network communication etc.

An example of the kind of applications I'm looking for is the parallel PageRank algorithm. It is used as a benchmark of different key-value stores in the paper "Concurrent Tries with Efficient Non-Blocking Snapshots (PPoPP'12)".

The reasons why I'm not satisfied with "artificial" benchmarks that do X% inserts, Y% deletes and Z% lookups are:

  1. It can be more convincing with a benchmark that also solves a real world problem. The risk with an "artificial" benchmarks is that they might not correspond to any real world situation.
  2. Some usage scenarios that happen frequently in real world applications might not be covered by the artificial benchmark.
  • if you get some actual app will be great, else if you have a budget could post it in elance would get something for under $150. but you do not say in what language? do you want a java app that does this and you will test different java.util.Map implementations ?
    – tgkprog
    Commented May 14, 2013 at 15:55
  • This question is being discussed on our Meta site.
    – yannis
    Commented May 15, 2013 at 5:10
  • @tgkprog This question is not intended to be language specific.
    – Kjell
    Commented May 15, 2013 at 12:42
  • can you elaborate? where and how will you test your implementations then?
    – tgkprog
    Commented May 15, 2013 at 12:48
  • 1
    @tgkprog I don't know yet. I might implement the data-structures and the benchmarks in several languages.
    – Kjell
    Commented May 15, 2013 at 13:18

1 Answer 1


Why not take your existing random KVP (key value pair) operation testing to the next level?

Presumably, your current set of tests includes a list of potential KVPs and then performing CRUD operations against whichever KVP was selected. In effect, the list of KVPs drives the benchmarks against your system. An Actor randomly selects the KVP and then picks a CRUD op.

The next logical stage is to create sets of operations which will "replace" your list of potential KVPs as the driver. The sets of operations will reflect what you think a "real" workload will be. In some cases, it will still be CRUD ops on KVPs. In other cases, as you mentioned, it will have additional changes (aka "real work") and it's the aggregate of those operations that make the set.

Now your Actor will select from the list of sets instead of KVPs. Bonus points if you make your Actor intelligent enough to pick relative workloads, so some percentage would be CRUD on KVP and some other percentage would be "real work."

This approach doesn't fully address your concerns with "artificial" benchmarks, but I don't know that any solution in the abstract can really resolve that issue. In theory, you know the expected work load best so you can tailor those sets of operations accordingly.

The benefit of this approach is you can now state "The system can handle ### transactions of X% inserts, Y% deletes, Z% lookups and Q% 'real world' operations." And you'll add a parenthetical remark explaining what "real world" means to you.

  • I like this suggestion even if it is not exactly what I was looking for. I'm trying to make the key-value store suit as many "real world" applications as possible. The key-value store could for example be placed in some data structure library. What I'm looking for is some algorithms that stresses this key-value store in parallel and does some work that one can imagine could be used in some "real world" scenario. It does not matter if the "read world" scenario is made up if it is possible to imagine that it could be useful for something.
    – Kjell
    Commented Jul 25, 2013 at 18:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.