Thursday, February 7, 2013

[ANN] ocaml-vclock - 0.0.0

I ported some Erlang vector clock code to Ocaml for fun and learning. It's not well tested and it hasn't any performance optimizations. I'm not ready yet but I have some projects in mind to use it so it will likely get fleshed out more.

Vector clocks are a system for determining the partial ordering of events in a distributed environment. You can determine if one value is the ancestor of another, equal, or was concurrently updated. It is one mechanism that distributed databases, such as Riak, use to automatically resolve some conflicts in data while maintaining availability.

The vector clock implementation allows for user defined site id type. It also allows metadata to be encoded in the site id, which is useful if you want your vector clock to be prunable by encoding timestamps in it.

The repo can be found here. If you'd like to learn more about vector clocks read the wikipedia page here. The Riak website also has some content on vector clocks here.

1 comment:

  1. This sounds like it could be turned into an useful benchmark ( http://gallium.inria.fr/~scherer/gagallium/we-need-a-representative-benchmark-suite/ ). Would you care to do that, trying to find some code whose running time can be parametrized and which is representative of real-world workloads on such structures?

    (Note that the fact that the library is not optimized to death right now is actually a *good* thing for benchmarking, as it allows to test candidate compiler optimizations on more idiomatic OCaml code; testing an optimized version would of course also be interesting, but that would provide a different kind of information (probably mostly non-regression)).

    ReplyDelete