dmutex

README

Dmutex

Dmutex is a distributed mutex package written in Go. It takes a quorum based approach to managing locks across n distributed nodes.

Overview

Dmutex implements the Agarwal-El Abbadi quorum-based algorithm. A good overview of the algorithm can be found here starting on page 50.

Example

Dmutex is initialized with the local node's address, the addresses of the entire cluster, and a timeout for the gRPC calls. Optional file locations of a TLS certificate and key can be passed in order to secure cluster traffic.

import (
  "github.com/bparli/dmutex"
)

func dLockTest() {
  nodes := []string{"192.168.1.12", "192.168.1.13", "192.168.1.14", "192.168.1.15", "192.168.1.16"}
  dm := dmutex.NewDMutex("192.168.1.12", nodes, 3*time.Second, "server.crt", "server.key")

  if err := dm.Lock(); err != nil {
    log.Errorln("Lock error", err)
  } else {
    log.Debugln("Acquired Lock")
    time.Sleep(time.Duration(100) * time.Millisecond)
    dm.UnLock()
    log.Debugln("Released Lock")
    }
  }
}

Note the timeout setting is used solely for acquiring the lock and not for holding the lock. A supplemental method for sanity/health checking the lock owner is still alive and means to still hold the lock. Its important to set the timeout for longer than the maximum time the lock is expected to be held for.

Approach

Lock process

The lock process largely follows the Agarwal-El Abbadi quorum-based algorithm

The steps in the lock process are as follows:

• broadcast lock Request message to all peers in the quorums
• collect all responses within certain time-out window
  • responses from all peers in the local node's quorums are expected
• if messages to some of the nodes in the quorum failed
  • calculate replacement paths based on the algorithm
  • generate unique substitute nodes and send the lock Request to them
  • if substitutes are not possible (according to the algorithm)
    • fallback to the naive approach and broadcast the lock Request to all remaining nodes in the cluster
    • if quorum met (at least n/2 + 1 responded) then grant lock
• each node sends a Reply to the request at the head of its queue, indicating consent to the lock
• if requests arrive out of order (according to timestamps)
  • an Inquire message is sent to the head of the queue
  • when a node receives an Inquire message it:
    • blocks on the Inquire if it has already been fully granted the lock
    • Yields the lock if it has not yet been fully granted the lock
• if the lock was not granted within the timeout window Relinquish any lock Replies

Unlock process

To unlock a Relinquish message is sent to all nodes that were originally sent lock Requests. This is ideally only peers in the local node's quorums, but in a degraded state could be more, or even all of the nodes in the cluster (as described above).

Dealing with Stale Locks

A 'stale' lock is a lock that has been granted to a node, but for some reason that node has not released it in a reasonable timeframe. This could happen for any number of reasons; the node crashed, the process paused, the network, etc.

Each time a new lock request arrives the node sends a Validate message to the node at the head of its request queue since thats the one it believes has the lock. If the grpc message fails or the reply indicates that node no longer owns the lock (for whatever reason), the lock request is purged from the head of the queue and the next in line is processed.

Again, note there is no timeout for holding the lock. The Validate message is meant to clear stale locks

Logging

Log level is set by the environment variable LOG_LEVEL

Documentation

Overview

Package dmutex is a distributed mutex package written in Go. It takes a quorum based approach to managing shared locks across n distributed nodes. Dmutex is initialized with the local node's address(it can be either the IP address or even the hostname), the addresses of the entire cluster, and a timeout for the gRPC calls. For simplicity it uses port 7070 for all nodes in the cluster. Optional file locations of a TLS certificate and key can be passed in order to secure cluster traffic.

Example

Example initializing and using dmutex

package main

import (
	"time"

	"github.com/bparli/dmutex"
	log "github.com/sirupsen/logrus"
)

func main() {
	nodes := []string{"192.168.1.12", "192.168.1.13", "192.168.1.14", "192.168.1.15", "192.168.1.16"}
	dm := dmutex.NewDMutex("192.168.1.12", nodes, 3*time.Second, "server.crt", "server.key")

	if err := dm.Lock(); err != nil {
		log.Errorln("Lock error", err)
	} else {
		log.Debugln("Acquired Lock")
		time.Sleep(time.Duration(100) * time.Millisecond)
		dm.UnLock()
		log.Debugln("Released Lock")
	}
}

Index

• type Dmutex
  • func NewDMutex(nodeAddr string, nodeAddrs []string, timeout time.Duration, tlsCrtFile string, ...) *Dmutex
  • func (d *Dmutex) Lock() error
  • func (d *Dmutex) UnLock()

Examples

• Package

Types

type Dmutex

type Dmutex struct {
	Quorums *quorums.Quorums
	// contains filtered or unexported fields
}

Dmutex is the main struct encompassing everything the local node needs to request and release the distributed shared lock

func NewDMutex

func NewDMutex(nodeAddr string, nodeAddrs []string, timeout time.Duration, tlsCrtFile string, tlsKeyFile string) *Dmutex

NewDMutex is the public function for initializing the distributed lock from the local node's perspective. It takes as arguments:

• the local node's address (in either hotname or IP address form)
• the entire cluster's individual addresses, again in either hostname or IP address form
• a timeout specifying grpc timeouts
• optional Certificate and Key files for encrypting connections between nodes

It calculates the tree, quorums, initializes grpc client and server and returns the initialized distributed mutex

func (*Dmutex) Lock

func (d *Dmutex) Lock() error

Lock is a public function to request the distributed mutex from the rest of the cluster Like a local lock, it blocks until it has locked the distributed mutex

func (*Dmutex) UnLock

func (d *Dmutex) UnLock()

UnLock is a public function to release the lock on the distributed mutex It notifies the rest of the quorum of the release and cleans up