[erlang-questions] ANN: locks (beta) - distributed lock manager and leader election

Ulf Wiger ulf@REDACTED
Tue Oct 8 11:58:17 CEST 2013


Many of you have heard me talk about a lock manager that I've been working on.

I think it's now in a state where I can invite people to take it for a spin. Some of you may be
interested primarily in the gen_leader-like leader election behavior. You may jump directly to that
description below.

Note that I consider this a *beta* release. There is a fairly interesting test suite, but the code has not
been used in anger yet.

The README is (for once) fairly extensive, including a fairly detailed discussion of the verification work done by Thomas Arts back in 1999-2000. I first designed the algorithm back in 1993, but it's taken quite a lot of "hammock time" (to quote Rich Hickey) to fit all details together.

A few notes on why I think this implementation is useful:

* It detects and resolves deadlocks in a distributed setting, in what we believe is an optimal way, given the assumption that the computers are faster than the network (i.e. trading CPU time for network efficiency).
No phantom deadlocks, and no central dependency graph. Note that in some interesting mnesia-based
applications, phantom deadlocks have been found to account for some 10-20% overhead in execution

* Since only true deadlocks are acted upon (either surrendered or leading to transaction abort if requested), transactions do not need to be preemptively restarted, as is the case in deadlock prevention. This means that transaction can be more 'erlang-ish' in their behavior and use side-effects at their leisure.

* It supports replicated locks, as well as quorum requirements. The 'lock space' is hierarchical, supporting
both read and write locks, as well as upgrade of read locks to write locks.

* Locks can be monitored by third parties. The leader election behavior uses this, but it can also be
used for debugging.

== The locks_leader behavior ==

Another gen_leader variant? Well, yes. This behavior is closely modeled after gen_leader,
but has a few important differences:

* The name of the election group is the name of the lock used to resolve elections. This means candidates
don't have to have registered names, and there can be multiple candidates on any given node.

* Candidates join the group simply by competing for the lock; other candidates discover them through
the #locks_info{} notifications, so the candidate list doesn't have to be statically defined. Nodes are
easily added at run-time.

The classic gen_leader example, gdict, has been implemented on locks_leader:

My own plan is to integrate this into the kvdb DBMS, but also to move gproc over to it, making distributed gproc more dynamic and well suited to Erlang's distribution behavior.

Feedback, questions and bug reports are highly appreciated!

Ulf W

Ulf Wiger, Co-founder & Developer Advocate, Feuerlabs Inc.

More information about the erlang-questions mailing list