It would help if you noted if the Key-Value store can fit in memory, needs to be in memory or even needs to be shared among multiple processes, i.e. your other question Is it safe to use a global hash table in an ocaml-5 parallel program?
Those factors are essential for choosing possible solutions.