vendor/github.com/hashicorp/serf/coordinate/coordinate.go

   1 package coordinate
   2
   3 import (
   4         "math"
   5         "math/rand"
   6         "time"
   7 )
   8
   9 // Coordinate is a specialized structure for holding network coordinates for the
  10 // Vivaldi-based coordinate mapping algorithm. All of the fields should be public
  11 // to enable this to be serialized. All values in here are in units of seconds.
  12 type Coordinate struct {
  13         // Vec is the Euclidean portion of the coordinate. This is used along
  14         // with the other fields to provide an overall distance estimate. The
  15         // units here are seconds.
  16         Vec []float64
  17
  18         // Err reflects the confidence in the given coordinate and is updated
  19         // dynamically by the Vivaldi Client. This is dimensionless.
  20         Error float64
  21
  22         // Adjustment is a distance offset computed based on a calculation over
  23         // observations from all other nodes over a fixed window and is updated
  24         // dynamically by the Vivaldi Client. The units here are seconds.
  25         Adjustment float64
  26
  27         // Height is a distance offset that accounts for non-Euclidean effects
  28         // which model the access links from nodes to the core Internet. The access
  29         // links are usually set by bandwidth and congestion, and the core links
  30         // usually follow distance based on geography.
  31         Height float64
  32 }
  33
  34 const (
  35         // secondsToNanoseconds is used to convert float seconds to nanoseconds.
  36         secondsToNanoseconds = 1.0e9
  37
  38         // zeroThreshold is used to decide if two coordinates are on top of each
  39         // other.
  40         zeroThreshold = 1.0e-6
  41 )
  42
  43 // ErrDimensionalityConflict will be panic-d if you try to perform operations
  44 // with incompatible dimensions.
  45 type DimensionalityConflictError struct{}
  46
  47 // Adds the error interface.
  48 func (e DimensionalityConflictError) Error() string {
  49         return "coordinate dimensionality does not match"
  50 }
  51
  52 // NewCoordinate creates a new coordinate at the origin, using the given config
  53 // to supply key initial values.
  54 func NewCoordinate(config *Config) *Coordinate {
  55         return &Coordinate{
  56                 Vec:        make([]float64, config.Dimensionality),
  57                 Error:      config.VivaldiErrorMax,
  58                 Adjustment: 0.0,
  59                 Height:     config.HeightMin,
  60         }
  61 }
  62
  63 // Clone creates an independent copy of this coordinate.
  64 func (c *Coordinate) Clone() *Coordinate {
  65         vec := make([]float64, len(c.Vec))
  66         copy(vec, c.Vec)
  67         return &Coordinate{
  68                 Vec:        vec,
  69                 Error:      c.Error,
  70                 Adjustment: c.Adjustment,
  71                 Height:     c.Height,
  72         }
  73 }
  74
  75 // IsCompatibleWith checks to see if the two coordinates are compatible
  76 // dimensionally. If this returns true then you are guaranteed to not get
  77 // any runtime errors operating on them.
  78 func (c *Coordinate) IsCompatibleWith(other *Coordinate) bool {
  79         return len(c.Vec) == len(other.Vec)
  80 }
  81
  82 // ApplyForce returns the result of applying the force from the direction of the
  83 // other coordinate.
  84 func (c *Coordinate) ApplyForce(config *Config, force float64, other *Coordinate) *Coordinate {
  85         if !c.IsCompatibleWith(other) {
  86                 panic(DimensionalityConflictError{})
  87         }
  88
  89         ret := c.Clone()
  90         unit, mag := unitVectorAt(c.Vec, other.Vec)
  91         ret.Vec = add(ret.Vec, mul(unit, force))
  92         if mag > zeroThreshold {
  93                 ret.Height = (ret.Height+other.Height)*force/mag + ret.Height
  94                 ret.Height = math.Max(ret.Height, config.HeightMin)
  95         }
  96         return ret
  97 }
  98
  99 // DistanceTo returns the distance between this coordinate and the other
 100 // coordinate, including adjustments.
 101 func (c *Coordinate) DistanceTo(other *Coordinate) time.Duration {
 102         if !c.IsCompatibleWith(other) {
 103                 panic(DimensionalityConflictError{})
 104         }
 105
 106         dist := c.rawDistanceTo(other)
 107         adjustedDist := dist + c.Adjustment + other.Adjustment
 108         if adjustedDist > 0.0 {
 109                 dist = adjustedDist
 110         }
 111         return time.Duration(dist * secondsToNanoseconds)
 112 }
 113
 114 // rawDistanceTo returns the Vivaldi distance between this coordinate and the
 115 // other coordinate in seconds, not including adjustments. This assumes the
 116 // dimensions have already been checked to be compatible.
 117 func (c *Coordinate) rawDistanceTo(other *Coordinate) float64 {
 118         return magnitude(diff(c.Vec, other.Vec)) + c.Height + other.Height
 119 }
 120
 121 // add returns the sum of vec1 and vec2. This assumes the dimensions have
 122 // already been checked to be compatible.
 123 func add(vec1 []float64, vec2 []float64) []float64 {
 124         ret := make([]float64, len(vec1))
 125         for i, _ := range ret {
 126                 ret[i] = vec1[i] + vec2[i]
 127         }
 128         return ret
 129 }
 130
 131 // diff returns the difference between the vec1 and vec2. This assumes the
 132 // dimensions have already been checked to be compatible.
 133 func diff(vec1 []float64, vec2 []float64) []float64 {
 134         ret := make([]float64, len(vec1))
 135         for i, _ := range ret {
 136                 ret[i] = vec1[i] - vec2[i]
 137         }
 138         return ret
 139 }
 140
 141 // mul returns vec multiplied by a scalar factor.
 142 func mul(vec []float64, factor float64) []float64 {
 143         ret := make([]float64, len(vec))
 144         for i, _ := range vec {
 145                 ret[i] = vec[i] * factor
 146         }
 147         return ret
 148 }
 149
 150 // magnitude computes the magnitude of the vec.
 151 func magnitude(vec []float64) float64 {
 152         sum := 0.0
 153         for i, _ := range vec {
 154                 sum += vec[i] * vec[i]
 155         }
 156         return math.Sqrt(sum)
 157 }
 158
 159 // unitVectorAt returns a unit vector pointing at vec1 from vec2. If the two
 160 // positions are the same then a random unit vector is returned. We also return
 161 // the distance between the points for use in the later height calculation.
 162 func unitVectorAt(vec1 []float64, vec2 []float64) ([]float64, float64) {
 163         ret := diff(vec1, vec2)
 164
 165         // If the coordinates aren't on top of each other we can normalize.
 166         if mag := magnitude(ret); mag > zeroThreshold {
 167                 return mul(ret, 1.0/mag), mag
 168         }
 169
 170         // Otherwise, just return a random unit vector.
 171         for i, _ := range ret {
 172                 ret[i] = rand.Float64() - 0.5
 173         }
 174         if mag := magnitude(ret); mag > zeroThreshold {
 175                 return mul(ret, 1.0/mag), 0.0
 176         }
 177
 178         // And finally just give up and make a unit vector along the first
 179         // dimension. This should be exceedingly rare.
 180         ret = make([]float64, len(ret))
 181         ret[0] = 1.0
 182         return ret, 0.0
 183 }