It was a sequence simple operations (simple as in no 2i or mapred) of read an existing key A, check if a nonexistent key exists B, write a previously nonexistent key C, delete an existing key D, overwrite an existing key A.

All performed in serial over protobuf (python riak lib).

LevelDB is known to have heavily degrading performance when you ask for a key that doesn't exist.