Build a Distributed LockStep 5 of 5

Redlock Quorum

12345

Step 5: Redlock Quorum

One lock server is a single point of failure. Redis's Redlock spreads the lock across N independent nodes: to hold the lock you must acquire it on a majority of them. If you can't get a majority, you release whatever you did grab and fail, so two clients can never both win.

Implement Redlock over the provided Nodes.

  • acquire(name, client_id): try every node; succeed only if you hold more than half. On failure, release your partial acquisitions and return False.
  • release(name, client_id): release the lock on every node.
Hints
Starter code
class Node:
    """One independent lock server."""
    def __init__(self):
        self._held = {}   # name -> client_id

    def acquire(self, name, client_id):
        if name in self._held:
            return False
        self._held[name] = client_id
        return True

    def release(self, name, client_id):
        if self._held.get(name) == client_id:
            del self._held[name]
            return True
        return False

    def holder(self, name):
        return self._held.get(name)


class Redlock:
    def __init__(self, nodes):
        self.nodes = nodes   # list of Node

    def acquire(self, name, client_id):
        """Hold the lock only with a majority of nodes; else roll back."""
        # TODO:
        #   got = [n for n in self.nodes if n.acquire(name, client_id)]
        #   if len(got) > len(self.nodes) // 2:
        #       return True
        #   for n in got:
        #       n.release(name, client_id)
        #   return False
        pass

    def release(self, name, client_id):
        # TODO: release on every node
        #   for n in self.nodes:
        #       n.release(name, client_id)
        pass
Write it on a laptop

The editor and the test runner need a wide screen. Open this page on a desktop browser and your progress will be waiting.

PreviousAll challenges