repair

Documentation

Index

• func SegmentDanger(numHealthy, minPieces int, failureRate float64) float64
• func SegmentHealth(numHealthy, minPieces int, failureRate float64) float64

Functions

func SegmentDanger

func SegmentDanger(numHealthy, minPieces int, failureRate float64) float64

SegmentDanger returns the chance of a segment with the given minPieces and the given number of healthy pieces of being lost in the next time period.

It assumes:

• Nodes fail at the given failureRate (i.e., each node has a failureRate chance of going offline within the next time period).
• Node failures are entirely independent. Obviously this is not the case, because many nodes may be operated by a single entity or share network infrastructure, in which case their failures would be correlated. But we can't easily model that, so our best hope is to try to avoid putting pieces for the same segment on related nodes to maximize failure independence.

(The "time period" we are talking about here could be anything. The returned danger value will be given in terms of whatever time period was used to determine failureRate. If it simplifies things, you can think of the time period as "one repair worker iteration".)

If those things are true, then the number of nodes holding this segment that will go offline follows the Binomial distribution:

X ~ Binom(numHealthy, failureRate)

A segment is lost if the number of nodes that go offline is higher than (numHealthy - minPieces). So we want to find

Pr[X > (numHealthy - minPieces)]

If we invert the logic here, we can use the standard CDF for the binomial distribution.

Pr[X > (numHealthy - minPieces)] = 1 - Pr[X <= (numHealthy - minPieces)]

And that gives us the danger value.

func SegmentHealth

func SegmentHealth(numHealthy, minPieces int, failureRate float64) float64

SegmentHealth returns a value corresponding to the health of a segment in the repair queue. Lower health segments should be repaired first.