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

   1 package coordinate
   2
   3 import (
   4         "fmt"
   5         "math"
   6         "math/rand"
   7         "time"
   8 )
   9
  10 // GenerateClients returns a slice with nodes number of clients, all with the
  11 // given config.
  12 func GenerateClients(nodes int, config *Config) ([]*Client, error) {
  13         clients := make([]*Client, nodes)
  14         for i, _ := range clients {
  15                 client, err := NewClient(config)
  16                 if err != nil {
  17                         return nil, err
  18                 }
  19
  20                 clients[i] = client
  21         }
  22         return clients, nil
  23 }
  24
  25 // GenerateLine returns a truth matrix as if all the nodes are in a straight linke
  26 // with the given spacing between them.
  27 func GenerateLine(nodes int, spacing time.Duration) [][]time.Duration {
  28         truth := make([][]time.Duration, nodes)
  29         for i := range truth {
  30                 truth[i] = make([]time.Duration, nodes)
  31         }
  32
  33         for i := 0; i < nodes; i++ {
  34                 for j := i + 1; j < nodes; j++ {
  35                         rtt := time.Duration(j-i) * spacing
  36                         truth[i][j], truth[j][i] = rtt, rtt
  37                 }
  38         }
  39         return truth
  40 }
  41
  42 // GenerateGrid returns a truth matrix as if all the nodes are in a two dimensional
  43 // grid with the given spacing between them.
  44 func GenerateGrid(nodes int, spacing time.Duration) [][]time.Duration {
  45         truth := make([][]time.Duration, nodes)
  46         for i := range truth {
  47                 truth[i] = make([]time.Duration, nodes)
  48         }
  49
  50         n := int(math.Sqrt(float64(nodes)))
  51         for i := 0; i < nodes; i++ {
  52                 for j := i + 1; j < nodes; j++ {
  53                         x1, y1 := float64(i%n), float64(i/n)
  54                         x2, y2 := float64(j%n), float64(j/n)
  55                         dx, dy := x2-x1, y2-y1
  56                         dist := math.Sqrt(dx*dx + dy*dy)
  57                         rtt := time.Duration(dist * float64(spacing))
  58                         truth[i][j], truth[j][i] = rtt, rtt
  59                 }
  60         }
  61         return truth
  62 }
  63
  64 // GenerateSplit returns a truth matrix as if half the nodes are close together in
  65 // one location and half the nodes are close together in another. The lan factor
  66 // is used to separate the nodes locally and the wan factor represents the split
  67 // between the two sides.
  68 func GenerateSplit(nodes int, lan time.Duration, wan time.Duration) [][]time.Duration {
  69         truth := make([][]time.Duration, nodes)
  70         for i := range truth {
  71                 truth[i] = make([]time.Duration, nodes)
  72         }
  73
  74         split := nodes / 2
  75         for i := 0; i < nodes; i++ {
  76                 for j := i + 1; j < nodes; j++ {
  77                         rtt := lan
  78                         if (i <= split && j > split) || (i > split && j <= split) {
  79                                 rtt += wan
  80                         }
  81                         truth[i][j], truth[j][i] = rtt, rtt
  82                 }
  83         }
  84         return truth
  85 }
  86
  87 // GenerateCircle returns a truth matrix for a set of nodes, evenly distributed
  88 // around a circle with the given radius. The first node is at the "center" of the
  89 // circle because it's equidistant from all the other nodes, but we place it at
  90 // double the radius, so it should show up above all the other nodes in height.
  91 func GenerateCircle(nodes int, radius time.Duration) [][]time.Duration {
  92         truth := make([][]time.Duration, nodes)
  93         for i := range truth {
  94                 truth[i] = make([]time.Duration, nodes)
  95         }
  96
  97         for i := 0; i < nodes; i++ {
  98                 for j := i + 1; j < nodes; j++ {
  99                         var rtt time.Duration
 100                         if i == 0 {
 101                                 rtt = 2 * radius
 102                         } else {
 103                                 t1 := 2.0 * math.Pi * float64(i) / float64(nodes)
 104                                 x1, y1 := math.Cos(t1), math.Sin(t1)
 105                                 t2 := 2.0 * math.Pi * float64(j) / float64(nodes)
 106                                 x2, y2 := math.Cos(t2), math.Sin(t2)
 107                                 dx, dy := x2-x1, y2-y1
 108                                 dist := math.Sqrt(dx*dx + dy*dy)
 109                                 rtt = time.Duration(dist * float64(radius))
 110                         }
 111                         truth[i][j], truth[j][i] = rtt, rtt
 112                 }
 113         }
 114         return truth
 115 }
 116
 117 // GenerateRandom returns a truth matrix for a set of nodes with normally
 118 // distributed delays, with the given mean and deviation. The RNG is re-seeded
 119 // so you always get the same matrix for a given size.
 120 func GenerateRandom(nodes int, mean time.Duration, deviation time.Duration) [][]time.Duration {
 121         rand.Seed(1)
 122
 123         truth := make([][]time.Duration, nodes)
 124         for i := range truth {
 125                 truth[i] = make([]time.Duration, nodes)
 126         }
 127
 128         for i := 0; i < nodes; i++ {
 129                 for j := i + 1; j < nodes; j++ {
 130                         rttSeconds := rand.NormFloat64()*deviation.Seconds() + mean.Seconds()
 131                         rtt := time.Duration(rttSeconds * secondsToNanoseconds)
 132                         truth[i][j], truth[j][i] = rtt, rtt
 133                 }
 134         }
 135         return truth
 136 }
 137
 138 // Simulate runs the given number of cycles using the given list of clients and
 139 // truth matrix. On each cycle, each client will pick a random node and observe
 140 // the truth RTT, updating its coordinate estimate. The RNG is re-seeded for
 141 // each simulation run to get deterministic results (for this algorithm and the
 142 // underlying algorithm which will use random numbers for position vectors when
 143 // starting out with everything at the origin).
 144 func Simulate(clients []*Client, truth [][]time.Duration, cycles int) {
 145         rand.Seed(1)
 146
 147         nodes := len(clients)
 148         for cycle := 0; cycle < cycles; cycle++ {
 149                 for i, _ := range clients {
 150                         if j := rand.Intn(nodes); j != i {
 151                                 c := clients[j].GetCoordinate()
 152                                 rtt := truth[i][j]
 153                                 node := fmt.Sprintf("node_%d", j)
 154                                 clients[i].Update(node, c, rtt)
 155                         }
 156                 }
 157         }
 158 }
 159
 160 // Stats is returned from the Evaluate function with a summary of the algorithm
 161 // performance.
 162 type Stats struct {
 163         ErrorMax float64
 164         ErrorAvg float64
 165 }
 166
 167 // Evaluate uses the coordinates of the given clients to calculate estimated
 168 // distances and compares them with the given truth matrix, returning summary
 169 // stats.
 170 func Evaluate(clients []*Client, truth [][]time.Duration) (stats Stats) {
 171         nodes := len(clients)
 172         count := 0
 173         for i := 0; i < nodes; i++ {
 174                 for j := i + 1; j < nodes; j++ {
 175                         est := clients[i].DistanceTo(clients[j].GetCoordinate()).Seconds()
 176                         actual := truth[i][j].Seconds()
 177                         error := math.Abs(est-actual) / actual
 178                         stats.ErrorMax = math.Max(stats.ErrorMax, error)
 179                         stats.ErrorAvg += error
 180                         count += 1
 181                 }
 182         }
 183
 184         stats.ErrorAvg /= float64(count)
 185         fmt.Printf("Error avg=%9.6f max=%9.6f\n", stats.ErrorAvg, stats.ErrorMax)
 186         return
 187 }