A practical approach to read write quorum systems [Part 2]

• by Samuele Resca

ℹī¸ The post is a continuation of A practical approach to read-write quorum systems.

💡 The code is available at https://github.com/samueleresca/quoracle-go.

I published the post "A practical approach to read-write quorum systems" a few months ago. The post refers to the paper Read-Write Quorum Systems Made Practical - Michael Whittaker, Aleksey Charapko, Joseph M. Hellerstein, Heidi Howard, Ion Stoica. It illustrates the implementation of "Quoracle". Quoracle provides the optimal quorums with respect to either the load, network or latency.

I have decided to rewrite the tool in Golang to explore the ecosystem and the tooling of the language. This article goes through the Golang implementation of the original Python library.

Quorum expressions definition

First of all, let's discuss the implementation of the expressions. The original paper uses expressions and nodes to describe quorums:

a, b, c = Node("a"), Node("b"), Node("c")
majority = QuorumSystem(reads=a*b + b*c + a*c)

The example above builds the majority quorums using the following pairs: [a,b], [b,c], [a,c]. Python can represent the expression above by overloading the * and the + operations. The original quoracle library uses the operator overloading approach.

Go advocates simplicity, and it does not embrace operator overloading. So, it is necessary to proceed with a different approach.

In Golang, these methods describe the operations:

// ExprOperator that wraps the Add and Multiply methods needed to build a quorum from a set of Node.
type ExprOperator interface {
	// Add method aggregate a Node to an Expr with a logical Or (a ∨ b)
	// returns the resulting Or operation.
	Add(expr Expr) Or
	// Multiply method aggregate a Node to an Expr with a logical And (a ∧ b)
	// returns the resulting And operation.
	Multiply(expr Expr) And
}

The ExprOperator interface defines the operations between two logical expressions. A logical expression between nodes represents many quorums.

Thus, it is possible to describe quorums as follows:

a, b, c :=
NewNode("a"), NewNode("b"), NewNode("c")

// (a * b) + (b * c) + (a * c)
majority := NewQuorumSystemWithReads(a.Multiply(b).Add(b.Multiply(c)).Add(a.Multiply(c)))

The ExprOperator interface provides the same functionalities as the original library. In the example above, the pairs: [a,b], [b,c], [a,c] are majority quorums. The next section goes through the Golang definition of a QuorumSystem and how to use it.

Quorum system definition

Now that we know how to define an Expr of nodes, we can declare a read-write quorum system. The below implementation describes the QuorumSystem struct used in the library.

// QuorumSystem describes a read-write quorum system.
type QuorumSystem struct {
	// reads describes the read-quorum.
	reads Expr
	// writes describes the write-quorum.
	writes Expr
	// nameToNode keeps track the name of a node to a GetNodeByName.
	nameToNode nameToNode
}

// Capacity calculate and gets the capacity from the optimized Strategy.
func (qs QuorumSystem) Capacity(strategyOptions StrategyOptions) (float64, error) {
	...
}

// Latency calculate and gets the latency from the optimized Strategy.
func (qs QuorumSystem) Latency(strategyOptions StrategyOptions) (float64, error) {
    	...
}

// Load calculate and gets the Load from the optimized Strategy.
func (qs QuorumSystem) Load(strategyOptions StrategyOptions) (float64, error) {
	...
}

// NetworkLoad calculate and gets the NetworkLoad from the optimized Strategy.
func (qs QuorumSystem) NetworkLoad(strategyOptions StrategyOptions) (float64, error) {
	...
}

The reads and writes fields represent the quorums. The nameToNode field keeps track of the different nodes in the quorum system. The QuorumSystem struct has the methods for calculating the quorum system's capacity, latency, load, and network load.

The StrategyOptions parameter struct represents the configurations for the strategy optimisation:

// OptimizeType describes an optimization type
type OptimizeType string

const (
	Load    OptimizeType = "Load"
	Network OptimizeType = "Network"
	Latency OptimizeType = "Latency"
)

// StrategyOptions describes the quorum system strategy options.
type StrategyOptions struct {
	// Optimize defines the target optimization.
	Optimize OptimizeType
	// LoadLimit defines the limit on the load limit.
	LoadLimit *float64
	// NetworkLimit defines the limit on the network limit.
	NetworkLimit *float64
	// LatencyLimit defines the limit on the latency.
	LatencyLimit *float64
	// ReadFraction defines the workflow distribution for the read operations.
	ReadFraction Distribution
	// WriteFraction defines the workflow distribution for the write operations.
	WriteFraction Distribution
	// F r ∈ R is F-resilient for some integer f if despite removing
	// any f nodes from r, r is still a read quorum
	F uint
}

The Optimize property points to the optimisation target. The LoadLimit, NetworkLimit, LatencyLimit define an optional limit on the load, the network, and latency. The ReadFraction and the WriteFraction determine the workload distribution of the read and write operations. The F field represents the resilience of the quorum. A quorum r is f-resilient if, for some integer f, despite removing any f nodes from r, r is still a read/write quorum1.

The library defines the initialisation functions for a new QuorumSystem:

// NewQuorumSystemWithReads defines a new quorum system given a read Expr, the write Expr is derived using DualOperator.Dual operation.
func NewQuorumSystemWithReads(reads Expr) QuorumSystem {
	qs, _ := NewQuorumSystem(reads, reads.Dual())

	qs.nameToNode = nameToNode{}

	for node := range qs.GetNodes() {
		qs.nameToNode[node.Name] = node
	}

	return qs
}

// NewQuorumSystemWithWrites defines a new quorum system given a write Expr, the read Expr is derived using DualOperator.Dual operation.
func NewQuorumSystemWithWrites(writes Expr) QuorumSystem {
  ...
}

// NewQuorumSystem defines a new quorum system given the reads Expr and the writes Expr.
func NewQuorumSystem(reads Expr, writes Expr) (QuorumSystem, error) {
  ...
}

The above code omits some methods implementations for brevity. If the caller provides either the read or write quorum, the constructor computes the logical dual operation of the other quorum and initialises a new QuorumSystem struct. If the caller provides both read and write quorums, the constructor checks the validity of the quorums and returns a new QuorumSystem struct with the corresponding quorums.

The following section shows how to translate the optimal strategy problem into a linear programming problem.

Optimal strategy problem definition

The original Python implementation of quoracle uses the PuLP library and coin-or. The previous blog post looked at how to use PuLP for optimisation problems in a Python runtime.

The Golang implementation uses a library called lanl/clp. lanl/clp also relies on coin-or for solving linear programming optimisation problems.

The codebase defines a helper struct to build a linear programming problem:

// lpDefinition defines a linear programming expression with its own Vars, Constraints, Objectives.
type lpDefinition struct {
	Vars        []float64
	Constraints [][2]float64
	Objectives  [][]float64
}

A lpDefinition struct contains the variables needed to describe a linear programming problem. Let's suppose that we have three six-faced dice. Two dice are not allowed to have the same value. The goal is to find a difference between the 1st and 2nd-largest dice smaller than the one between the 2nd and 3rd dice. The following lpDefinition represents the problem:

problemDefinition := lpDefinition {
	Vars: []float64 {1.0, 1.0, 1.0}, // dice A , dice B, dice C
	Constraints: [][2]float64{
		{1, 6}, // Index 0: dice A
		{1, 6}, // Index 1: dice B
		{1, 6}, // Index 2: dice C
	},
	Objectives: [][]float64{
		// LB   A    B    C    UB
		{1.0, 1.0, -1.0, 0.0, math.Inf(1)},  // 1 ≤ a - b ≤ ∞ | Dice A cannot be equal to dice B
		{1.0, 0.0, 1.0, -1.0, math.Inf(1)},  // 1 ≤ b - c ≤ ∞ | Dice B cannot be equal to dice C
		{math.Inf(-1), 1.0, -2.0, 1.0, -1.0}, // a − b < b − c -> -∞ ≤ a - 2b + c ≤ -1 | The main objective codified from the problem.
	},
}

The lpDefinition above stores a value in the Vars array for each die. The Constraints matrix represents the dice range constraint, from 1 to 6. The Objective matrix contains the two goals of the problem:

  1. Each die must be different from the others (lines 10 and 11);
  2. The difference between the 1st and 2nd largest dice must be smaller than the one between the 2nd and the 3rd dice.

The example above shows how to use the helper struct in the codebase to build a minimisation problem. Next, we will take a detailed look at the implementation for optimising the metrics. Depending on the optimisation target, the problem definition builds a different lpDefinition struct.

Load optimisation definition

Let's start by describing how the load optimisation problem is implemented. To recap, the formula for the load defined in the paper1 is:

$$ \frac{f_r}{cap_R(x)} \sum_{{r \in R | x \in r }} p_r + \frac{1 - f_r}{cap_W(x)} \sum_{{w \in W | x \in w }} p_w \leq L_{f_r} $$

The following snippet of code implements the above formula, and it builds the LP problem:

func (qs QuorumSystem) loadOptimalStrategy(
	optimize OptimizeType,
	readQuorums []ExprSet,
	writeQuorums []ExprSet,
	readFraction DistributionValues,
	loadLimit *float64,
	networkLimit *float64,
	latencyLimit *float64) (*Strategy, error) {
 ...
 
	buildLoadDef := func(loadLimit *float64, fr float64) (lpDefinition, error) {
		def := newDefinitionWithVarsAndConstraints(readQuorumVars, writeQuorumVars)
		// l def
		def.Vars = append(def.Vars, 1.0)
		def.Constraints = append(def.Constraints, [2]float64{ninf, pinf})

		// Load formula
		for n := range qs.GetNodes() {
			tmp := make([]float64, len(def.Vars))

			if _, ok := xToReadQuorumVars[n]; ok {
				vs := xToReadQuorumVars[n]
				for _, v := range vs {
					tmp[v.Index] += fr * v.Value / float64(*qs.GetNodeByName(n.Name).ReadCapacity)
				}
			}

			if _, ok := xToWriteQuorumVars[n]; ok {
				vs := xToWriteQuorumVars[n]
				for _, v := range vs {
					tmp[v.Index] += (1 - fr) * v.Value / float64(*qs.GetNodeByName(n.Name).WriteCapacity)
				}
			}

			def.Objectives = append(def.Objectives, tmp)
		}
		return def, nil
	}
  
 ...
  
	return &newStrategy, nil
}

The snippet omits some code for brevity. The buildLoadDef local function encapsulates the logic for building the load optimisation problem. The function initialises the Vars and the Constraints from the lpVariable. Next, it adds the l variable and constraint that indicates the load (\(L_{f_r}\)) for the specific read fraction. It builds the load formula for every lpVariable in the problem. For each Node in the quorum system, it applies the following expression in case of a read quorum:

tmp[v.Index] += fr * v.Value / float64(*qs.GetNodeByName(n.Name).ReadCapacity)

otherwise, in the case of a write quorum, it proceeds by using:

tmp[v.Index] += (1 - fr) * v.Value / float64(*qs.GetNodeByName(n.Name).WriteCapacity)

The ReadCapacity and the WriteCapacity are configurable for each Node. The code needs to maintain the same order in the Vars and the Objectives arrays. Thus, each lpVariable uses an Index to refer to the exact position of each element in the arrays.

Network load optimisation definition

This section describes the implementation of the network load. Let's start by refreshing the formula1:

$$ f_r ( \sum_{r \in R} p_r \cdot |r|) + (1 - f_r) ( \sum_{w \in W} p_w \cdot |w|) $$

\(|r|\) and \(|w|\) are the length of the read and write quorums sets. The library builds the network load minimisation problem as follows:

func (qs QuorumSystem) loadOptimalStrategy(
	optimize OptimizeType,
	readQuorums []ExprSet,
	writeQuorums []ExprSet,
	readFraction DistributionValues,
	loadLimit *float64,
	networkLimit *float64,
	latencyLimit *float64) (*Strategy, error) {
	
...

	buildNetworkDef := func(networkLimit *float64) lpDefinition {
		def := newDefinitionWithVarsAndConstraints(readQuorumVars, writeQuorumVars)

		objExpr := make([]float64, len(def.Vars))

		// network_def  - inf <= network_def <= +inf
		for _, v := range readQuorumVars {
			objExpr[v.Index] = fr * float64(len(v.Quorum))
		}

		for _, v := range writeQuorumVars {
			objExpr[v.Index] = (1 - fr) * float64(len(v.Quorum))
		}

		objExpr = append([]float64{ninf}, objExpr...)

		if networkLimit == nil {
			objExpr = append(objExpr, pinf)
		} else {
			objExpr = append(objExpr, *networkLimit)
		}

		def.Objectives = append(def.Objectives, objExpr)

		return def
	}
  
...
  
	return &newStrategy, nil
}

The above code initialises a new Vars and the Constraints fields for each quorum. Then, it applies the network load formula by multiplying the length of the quorum by fr. Also, the implementation adds a row in the Objectives matrix in case we specify a network limit.

Latency optimisation definition

The last optimisation target is the latency. The formula described in the paper defines the latency as:

$$ f_r ( \sum_{r \in R} p_r \cdot latency(r)) + (1 - f_r) ( \sum_{w \in W} p_w \cdot latency(w)) $$

Below is the optimisation definition of the latency:

func (qs QuorumSystem) loadOptimalStrategy(
	optimize OptimizeType,
	readQuorums []ExprSet,
	writeQuorums []ExprSet,
	readFraction DistributionValues,
	loadLimit *float64,
	networkLimit *float64,
	latencyLimit *float64) (*Strategy, error) {

  ...

	buildLatencyDef := func(latencyLimit *float64) (lpDefinition, error) {
		def := newDefinitionWithVarsAndConstraints(readQuorumVars, writeQuorumVars)

		// building latency objs | -inf <= latency_def <= inf
		objExpr := make([]float64, len(def.Vars))

		for _, v := range readQuorumVars {
			nodes := make([]Node, 0)

			for x := range v.Quorum {
				q := qs.GetNodeByName(x.String())
				nodes = append(nodes, q)
			}

			l, err := qs.readQuorumLatency(nodes)

			if err != nil {
				return lpDefinition{}, fmt.Errorf("error on readQuorumLatency %s", err)
			}

			objExpr[v.Index] = fr * v.Value * float64(l)
		}

		for _, v := range writeQuorumVars {
			nodes := make([]Node, 0)

			for x := range v.Quorum {
				q := qs.GetNodeByName(x.String())
				nodes = append(nodes, q)
			}

			l, err := qs.writeQuorumLatency(nodes)

			if err != nil {
				return lpDefinition{}, fmt.Errorf("error on writeQuorumLatency %s", err)
			}

			objExpr[v.Index] = (1 - fr) * v.Value * float64(l)
		}

		objExpr = append([]float64{ninf}, objExpr...)

		if latencyLimit == nil {
			objExpr = append(objExpr, pinf)
		} else {
			objExpr = append(objExpr, *latencyLimit)
		}
		def.Objectives = append(def.Objectives, objExpr)

		return def, nil
	}

	...
  
	return &newStrategy, nil
}

The implementation creates a new lpDefinition populating the Vars and the Constraints. Then, it retrieves the latency for each readQuorumVars and writeQuorumVars. The latency of a quorum is the shortest time required to form a quorum after contacting the nodes in that quorum. The code calculates l using the readQuorumLatency and the writeQuorumLatency methods.

Next, it continues by applying the formula of the latency for the read quorums:

obj[v.Index] = fr * v.Value * float64(l)

the code takes the same approach for the write quorums using the opposite workload:

obj[v.Index] = (1 - fr) * v.Value * float64(l)

The following section describes how to translate the optimisation result into a new Strategy. Also, it shows how to execute the LP optimisation using the definitions seen in this section.

Strategy initialisation

The previous section described how to build the problem definition. Now we can proceed by executing the optimisation. The snippet of code below describes the optimisation execution and the initialisation of the strategy:

func (qs QuorumSystem) loadOptimalStrategy(
	optimize OptimizeType,
	readQuorums []ExprSet,
	writeQuorums []ExprSet,
	readFraction DistributionValues,
	loadLimit *float64,
	networkLimit *float64,
	latencyLimit *float64) (*Strategy, error) {
  
  ...
  
	// Declare a new Simplex problem with a clp.Minimize optimization direction.
	simp := clp.NewSimplex()
	simp.SetOptimizationDirection(clp.Minimize)

	def := lpDefinition{}

	if optimize == Load {
		def = getLoadObjective(readFraction, loadLimit, buildLoadDef)
	} else if optimize == Network {
		def = buildNetworkDef(nil)
	} else if optimize == Latency {
		def, _ = buildLatencyDef(nil)
	}

	// The sum of the read and write quorums probabilities must be 1.
	sumOfReadProbabilities, sumOfWriteProbabilities := getTotalProbabilityObjectives(optimize, readQuorumVars, writeQuorumVars)
	def.Objectives = append(def.Objectives, sumOfReadProbabilities)
	def.Objectives = append(def.Objectives, sumOfWriteProbabilities)

	if loadLimit != nil {
		defTemp := getLoadObjective(readFraction, loadLimit, buildLoadDef)
		def.Vars = append(def.Vars, 0)

		for r := 0; r < len(def.Objectives); r++ {
			if len(def.Objectives[r]) != len(def.Vars) {
				def.Objectives[r] = insertAt(def.Objectives[r], len(def.Objectives[r])-1, 0.0)
			}
		}

		b := [2]float64{ninf, pinf}
		def.Constraints = append(def.Constraints, b)
		def.Objectives = append(def.Objectives, defTemp.Objectives...)
	}

	if networkLimit != nil {
		def.Objectives = merge(def.Objectives, buildNetworkDef(networkLimit).Objectives)
	}

	if latencyLimit != nil {
		defTemp, _ := buildLatencyDef(latencyLimit)
		def.Objectives = merge(def.Objectives, defTemp.Objectives)
	}

	simp.EasyLoadDenseProblem(def.Vars, def.Constraints, def.Objectives)
	// Solve the optimization problem.
	status := simp.Primal(clp.NoValuesPass, clp.NoStartFinishOptions)
	soln := simp.PrimalColumnSolution()

	if status != clp.Optimal {
		return nil, fmt.Errorf("no optimal strategy found")
	}

	readSigma := make([]SigmaRecord, 0)
	writeSigma := make([]SigmaRecord, 0)

	for _, v := range readQuorumVars {
		readSigma = append(readSigma, SigmaRecord{Quorum: v.Quorum, Probability: soln[v.Index]})
	}

	for _, v := range writeQuorumVars {
		writeSigma = append(writeSigma, SigmaRecord{Quorum: v.Quorum, Probability: soln[v.Index]})
	}

	newStrategy := NewStrategy(qs, Sigma{Values: readSigma}, Sigma{Values: writeSigma})

	return &newStrategy, nil
}

As a first step, the code initialises a NewSimplex. The simplex algorithm is a popular linear programming algorithm. We want to minimise the objective of our problem. Thus, the code sets the optimisation direction as clp.Minimize.

The code proceeds by creating a new lpDefinition based on the optimisation definitions seen in the previous section. For example, if the optimisation target is Network, the code calls the buildNetworkDef function.

On top of the optimisation target, the code needs to add another objective: the total sum of the read and write probabilities must be 1. The getTotalProbabilityObjectives method takes care of that. It returns a new objective array where the read and write probabilities sum to 1.

The code executes the optimisation and checks that the resulting status is optimal. If the operation succeeds, the code gets back the optimal solution. Then, for each quorum, the code initialises a new SigmaRecord with the quorum and its probability of being selected.

Finally, it creates a new Strategy with the SigmaR (array of SigmaRecord for the read quorums) and the SigmaW (array of SigmaRecord for the write quorums).

Let's refresh the definition of strategy as mentioned in the paper:

$$ \sigma = (\sigma_R, \sigma_W) $$

\(\sigma_R\) and \(\sigma_W\) are probability distributions: \(\sigma_R(r)\) and \(\sigma_W(w)\) are respectively the probabilities that the strategy chooses a read quorum \(r\) and a write quorum \(w\).

quoracle-go represents a Strategy in a similar way using the following structs:

// Strategy defines a strategy related to a QuorumSystem.
type Strategy struct {
	Qs                     QuorumSystem
	SigmaR                 Sigma
	SigmaW                 Sigma
	nodeToReadProbability  map[Node]Probability
	nodeToWriteProbability map[Node]Probability
}

// Sigma defines the probabilities of a specific Strategy. Each Expr (quorum) has a probability of being choose associated.
type Sigma struct {
	Values []SigmaRecord
}

// SigmaRecord defines as ExprSet that represents a quorum and the probability of being chosen.
type SigmaRecord struct {
	Quorum      ExprSet
	Probability Probability
}

The SigmaR and SigmaW correspond to the strategy's probability of choosing a specific quorum. Also, the Strategy struct maintains a hashmap storing the node and its likelihood of being selected.

The Strategy struct exposes some methods that retrieve some metrics and information. Below is the list of methods provided with the Strategy struct:

//Strategy defines a strategy related to a QuorumSystem.
type Strategy struct {
	Qs                     QuorumSystem
	SigmaR                 Sigma
	SigmaW                 Sigma
	nodeToReadProbability  map[Node]Probability
	nodeToWriteProbability map[Node]Probability
}

// Sigma defines the probabilities of a specific Strategy. Each Expr (quorum) has a probability of being choose associated.
type Sigma struct {
	Values []SigmaRecord
}

// SigmaRecord defines as ExprSet that represents a quorum and the probability of being chosen.
type SigmaRecord struct {
	Quorum      ExprSet
	Probability Probability
}

// GetReadQuorum returns a ExprSet representing a quorum of the strategy.
// The method return the quorum based on its probability.
func (s Strategy) GetReadQuorum() ExprSet {
 ...
}

// GetWriteQuorum returns a ExprSet representing a quorum of the strategy.
// The method return the quorum based on its probability.
func (s Strategy) GetWriteQuorum() ExprSet {
  ...
}

// Load calculates and returns the load of the strategy given a read and write distribution.
func (s Strategy) Load(rf *Distribution, wf *Distribution) (float64, error) {
  ...
}

// Capacity calculates and returns the capacity of the strategy given a read and write distribution.
func (s Strategy) Capacity(rf *Distribution, wf *Distribution) (float64, error) {
  ...
}

// NetworkLoad calculates and returns the network load of the strategy given a read and write Distribution.
func (s Strategy) NetworkLoad(rf *Distribution, wf *Distribution) (float64, error) {
  ...
}

// NodeLoad returns the load of a specific Node given a read and write Distribution.
func (s Strategy) NodeLoad(node Node, rf *Distribution, wf *Distribution) (float64, error) {
  ...
}

// NodeUtilization returns the utilization of a specific Node given a read and write Distribution.
func (s Strategy) NodeUtilization(node Node, rf *Distribution, wf *Distribution) (*float64, error) {  
  ...
}

// NodeThroughput returns the throughput of a specific Node given a read and write Distribution.
func (s Strategy) NodeThroughput(node Node, rf *Distribution, wf *Distribution) (*float64, error) {
  ...
}

The code above omits the implementation of the functions for brevity. The GetReadQuorum, GetWriteQuorum use a probability distribution to return the quorums. The Load, Capacity, NetworkLoad and Latency methods return the respective metrics for a given read or write workload. The NodeLoad, NodeUtilization and NodeThroughput methods target a specific Node in the quorum system. The implementations use the probability of a node getting selected to calculate the respective node metric.

Searching for the optimal quorum strategy

We have seen how the codebase leverages linear programming to find the optimal strategy.

Let's reiterate one of the primary purposes of quoracle. Given the nodes' details, an optimisation target and workload distribution, it returns the optimised strategy.

The Search method implements the rule mentioned above. It calculates the optimal strategy by trying all the combinations of quorums. Whenever the optimal strategy for a given valid quorum returns a better target metric, the Search function saves that.

Below is the code implementation of the Search function:

//Search given some nodes, and a SearchOptions instance, returns the optimal strategy and quorum system in respect of the optimization target and constraints.
func Search(nodes []Expr, option SearchOptions) (SearchResult, error) {
	return performQuorumSearch(nodes, initializeSearchOptions(option))
}

func performQuorumSearch(nodes []Expr, opts ...func(options *SearchOptions) error) (SearchResult, error) {
	sb := &SearchOptions{}

	// ... (write initializations with default values)...
	for _, op := range opts {
		err := op(sb)
		if err != nil {
			return SearchResult{}, err
		}
	}

	start := time.Now()

	var optQS *QuorumSystem = nil
	var optSigma *Strategy = nil
	var optMetric *float64 = nil

	getMetric := func(sigma Strategy) (float64, error) {
		if sb.Optimize == Load {
			return sigma.Load(&sb.ReadFraction, &sb.WriteFraction)
		}

		if sb.Optimize == Network {
			return sigma.NetworkLoad(&sb.ReadFraction, &sb.WriteFraction)
		}

		return sigma.Latency(&sb.ReadFraction, &sb.WriteFraction)
	}

	doSearch := func(exprs chan Expr) error {

		for r := range exprs {
			qs := NewQuorumSystemWithReads(r)

			if qs.Resilience() < sb.Resilience {
				continue
			}

			stratOpts := StrategyOptions{
				Optimize:      sb.Optimize,
				LoadLimit:     sb.LoadLimit,
				NetworkLimit:  sb.NetworkLimit,
				LatencyLimit:  sb.LatencyLimit,
				ReadFraction:  sb.ReadFraction,
				WriteFraction: sb.WriteFraction,
				F:             sb.F,
			}

			strategy, err := qs.Strategy(initializeStrategyOptions(stratOpts))

			if err != nil {
				fmt.Printf("Strategy not found %s \n", err)
				continue
			}

			sigmaMetric, err := getMetric(*strategy)

			if err != nil {
				fmt.Printf("Calc strategy err %s \n", err)
				continue
			}

			if optMetric == nil || sigmaMetric < *optMetric {
				optQS = &qs
				optSigma = strategy
				optMetric = &sigmaMetric
			}

			t := time.Now()
			elapsed := t.Sub(start)

			if sb.TimeoutSecs != 0 && elapsed.Seconds() > sb.TimeoutSecs {
				fmt.Printf("Timeout hit %f \n", sb.TimeoutSecs)
				return nil
			}
		}

		return nil
	}

	err := doSearch(dupFreeExprs(nodes, 2))

	if err != nil {
		return SearchResult{}, err
	}

	err = doSearch(dupFreeExprs(nodes, 0))

	if err != nil {
		return SearchResult{}, err
	}

	if optQS == nil {
		return SearchResult{}, fmt.Errorf("error in search")
	}

	return SearchResult{
		QuorumSystem: *optQS,
		Strategy:     *optSigma,
	}, nil
}

The dupFreeExprs and the doSearch functions encapsulate the core logic. The dupFreeExprs returns all the possible combinations of quorums composed using a list of nodes. The doSearch uses the dupFreeExprs outcome to initialise a new quorum system and find an optimal strategy. The implementation keeps track of the Strategy and QuorumSystem with the most optimised metric.

The search process is time-bound. When the operation reaches a specified timeout, the search stops. The timeout prevents the search from hanging indefinitely.

Wrap up

This post went through the Golang port of quoracle, describing the main components implemented in the codebase. The code is available at samueleresca/quoracle-go. The project had two primary purposes. First, to put into practice the core concepts described in the paper1. Secondly, to explore the Golang ecosystem and tooling. Some of the concepts might seem very theoretical, but it is essential to know the basics. Quorums are the foundation of distributed systems topics such as replication and consensus.

Further reading:23

  1. Read-Write Quorum Systems Made Practical - Michael Whittaker, Aleksey Charapko, Joseph M. Hellerstein, Heidi Howard, Ion Stoica ↩︎ ↩︎ ↩︎ ↩︎

  2. lanl/clp provides a Go interface to the COIN-OR Linear Programming (CLP) library ↩︎

  3. github.com/mwhittaker/quoracle ↩︎