[VOL-2538] Logging - Implement dynamic log levels in ofagent
Change-Id: I9582230d9d3c34ea84339fddf2b2f3b3d2804808
diff --git a/vendor/github.com/hashicorp/serf/LICENSE b/vendor/github.com/hashicorp/serf/LICENSE
new file mode 100644
index 0000000..c33dcc7
--- /dev/null
+++ b/vendor/github.com/hashicorp/serf/LICENSE
@@ -0,0 +1,354 @@
+Mozilla Public License, version 2.0
+
+1. Definitions
+
+1.1. “Contributor”
+
+ means each individual or legal entity that creates, contributes to the
+ creation of, or owns Covered Software.
+
+1.2. “Contributor Version”
+
+ means the combination of the Contributions of others (if any) used by a
+ Contributor and that particular Contributor’s Contribution.
+
+1.3. “Contribution”
+
+ means Covered Software of a particular Contributor.
+
+1.4. “Covered Software”
+
+ means Source Code Form to which the initial Contributor has attached the
+ notice in Exhibit A, the Executable Form of such Source Code Form, and
+ Modifications of such Source Code Form, in each case including portions
+ thereof.
+
+1.5. “Incompatible With Secondary Licenses”
+ means
+
+ a. that the initial Contributor has attached the notice described in
+ Exhibit B to the Covered Software; or
+
+ b. that the Covered Software was made available under the terms of version
+ 1.1 or earlier of the License, but not also under the terms of a
+ Secondary License.
+
+1.6. “Executable Form”
+
+ means any form of the work other than Source Code Form.
+
+1.7. “Larger Work”
+
+ means a work that combines Covered Software with other material, in a separate
+ file or files, that is not Covered Software.
+
+1.8. “License”
+
+ means this document.
+
+1.9. “Licensable”
+
+ means having the right to grant, to the maximum extent possible, whether at the
+ time of the initial grant or subsequently, any and all of the rights conveyed by
+ this License.
+
+1.10. “Modifications”
+
+ means any of the following:
+
+ a. any file in Source Code Form that results from an addition to, deletion
+ from, or modification of the contents of Covered Software; or
+
+ b. any new file in Source Code Form that contains any Covered Software.
+
+1.11. “Patent Claims” of a Contributor
+
+ means any patent claim(s), including without limitation, method, process,
+ and apparatus claims, in any patent Licensable by such Contributor that
+ would be infringed, but for the grant of the License, by the making,
+ using, selling, offering for sale, having made, import, or transfer of
+ either its Contributions or its Contributor Version.
+
+1.12. “Secondary License”
+
+ means either the GNU General Public License, Version 2.0, the GNU Lesser
+ General Public License, Version 2.1, the GNU Affero General Public
+ License, Version 3.0, or any later versions of those licenses.
+
+1.13. “Source Code Form”
+
+ means the form of the work preferred for making modifications.
+
+1.14. “You” (or “Your”)
+
+ means an individual or a legal entity exercising rights under this
+ License. For legal entities, “You” includes any entity that controls, is
+ controlled by, or is under common control with You. For purposes of this
+ definition, “control” means (a) the power, direct or indirect, to cause
+ the direction or management of such entity, whether by contract or
+ otherwise, or (b) ownership of more than fifty percent (50%) of the
+ outstanding shares or beneficial ownership of such entity.
+
+
+2. License Grants and Conditions
+
+2.1. Grants
+
+ Each Contributor hereby grants You a world-wide, royalty-free,
+ non-exclusive license:
+
+ a. under intellectual property rights (other than patent or trademark)
+ Licensable by such Contributor to use, reproduce, make available,
+ modify, display, perform, distribute, and otherwise exploit its
+ Contributions, either on an unmodified basis, with Modifications, or as
+ part of a Larger Work; and
+
+ b. under Patent Claims of such Contributor to make, use, sell, offer for
+ sale, have made, import, and otherwise transfer either its Contributions
+ or its Contributor Version.
+
+2.2. Effective Date
+
+ The licenses granted in Section 2.1 with respect to any Contribution become
+ effective for each Contribution on the date the Contributor first distributes
+ such Contribution.
+
+2.3. Limitations on Grant Scope
+
+ The licenses granted in this Section 2 are the only rights granted under this
+ License. No additional rights or licenses will be implied from the distribution
+ or licensing of Covered Software under this License. Notwithstanding Section
+ 2.1(b) above, no patent license is granted by a Contributor:
+
+ a. for any code that a Contributor has removed from Covered Software; or
+
+ b. for infringements caused by: (i) Your and any other third party’s
+ modifications of Covered Software, or (ii) the combination of its
+ Contributions with other software (except as part of its Contributor
+ Version); or
+
+ c. under Patent Claims infringed by Covered Software in the absence of its
+ Contributions.
+
+ This License does not grant any rights in the trademarks, service marks, or
+ logos of any Contributor (except as may be necessary to comply with the
+ notice requirements in Section 3.4).
+
+2.4. Subsequent Licenses
+
+ No Contributor makes additional grants as a result of Your choice to
+ distribute the Covered Software under a subsequent version of this License
+ (see Section 10.2) or under the terms of a Secondary License (if permitted
+ under the terms of Section 3.3).
+
+2.5. Representation
+
+ Each Contributor represents that the Contributor believes its Contributions
+ are its original creation(s) or it has sufficient rights to grant the
+ rights to its Contributions conveyed by this License.
+
+2.6. Fair Use
+
+ This License is not intended to limit any rights You have under applicable
+ copyright doctrines of fair use, fair dealing, or other equivalents.
+
+2.7. Conditions
+
+ Sections 3.1, 3.2, 3.3, and 3.4 are conditions of the licenses granted in
+ Section 2.1.
+
+
+3. Responsibilities
+
+3.1. Distribution of Source Form
+
+ All distribution of Covered Software in Source Code Form, including any
+ Modifications that You create or to which You contribute, must be under the
+ terms of this License. You must inform recipients that the Source Code Form
+ of the Covered Software is governed by the terms of this License, and how
+ they can obtain a copy of this License. You may not attempt to alter or
+ restrict the recipients’ rights in the Source Code Form.
+
+3.2. Distribution of Executable Form
+
+ If You distribute Covered Software in Executable Form then:
+
+ a. such Covered Software must also be made available in Source Code Form,
+ as described in Section 3.1, and You must inform recipients of the
+ Executable Form how they can obtain a copy of such Source Code Form by
+ reasonable means in a timely manner, at a charge no more than the cost
+ of distribution to the recipient; and
+
+ b. You may distribute such Executable Form under the terms of this License,
+ or sublicense it under different terms, provided that the license for
+ the Executable Form does not attempt to limit or alter the recipients’
+ rights in the Source Code Form under this License.
+
+3.3. Distribution of a Larger Work
+
+ You may create and distribute a Larger Work under terms of Your choice,
+ provided that You also comply with the requirements of this License for the
+ Covered Software. If the Larger Work is a combination of Covered Software
+ with a work governed by one or more Secondary Licenses, and the Covered
+ Software is not Incompatible With Secondary Licenses, this License permits
+ You to additionally distribute such Covered Software under the terms of
+ such Secondary License(s), so that the recipient of the Larger Work may, at
+ their option, further distribute the Covered Software under the terms of
+ either this License or such Secondary License(s).
+
+3.4. Notices
+
+ You may not remove or alter the substance of any license notices (including
+ copyright notices, patent notices, disclaimers of warranty, or limitations
+ of liability) contained within the Source Code Form of the Covered
+ Software, except that You may alter any license notices to the extent
+ required to remedy known factual inaccuracies.
+
+3.5. Application of Additional Terms
+
+ You may choose to offer, and to charge a fee for, warranty, support,
+ indemnity or liability obligations to one or more recipients of Covered
+ Software. However, You may do so only on Your own behalf, and not on behalf
+ of any Contributor. You must make it absolutely clear that any such
+ warranty, support, indemnity, or liability obligation is offered by You
+ alone, and You hereby agree to indemnify every Contributor for any
+ liability incurred by such Contributor as a result of warranty, support,
+ indemnity or liability terms You offer. You may include additional
+ disclaimers of warranty and limitations of liability specific to any
+ jurisdiction.
+
+4. Inability to Comply Due to Statute or Regulation
+
+ If it is impossible for You to comply with any of the terms of this License
+ with respect to some or all of the Covered Software due to statute, judicial
+ order, or regulation then You must: (a) comply with the terms of this License
+ to the maximum extent possible; and (b) describe the limitations and the code
+ they affect. Such description must be placed in a text file included with all
+ distributions of the Covered Software under this License. Except to the
+ extent prohibited by statute or regulation, such description must be
+ sufficiently detailed for a recipient of ordinary skill to be able to
+ understand it.
+
+5. Termination
+
+5.1. The rights granted under this License will terminate automatically if You
+ fail to comply with any of its terms. However, if You become compliant,
+ then the rights granted under this License from a particular Contributor
+ are reinstated (a) provisionally, unless and until such Contributor
+ explicitly and finally terminates Your grants, and (b) on an ongoing basis,
+ if such Contributor fails to notify You of the non-compliance by some
+ reasonable means prior to 60 days after You have come back into compliance.
+ Moreover, Your grants from a particular Contributor are reinstated on an
+ ongoing basis if such Contributor notifies You of the non-compliance by
+ some reasonable means, this is the first time You have received notice of
+ non-compliance with this License from such Contributor, and You become
+ compliant prior to 30 days after Your receipt of the notice.
+
+5.2. If You initiate litigation against any entity by asserting a patent
+ infringement claim (excluding declaratory judgment actions, counter-claims,
+ and cross-claims) alleging that a Contributor Version directly or
+ indirectly infringes any patent, then the rights granted to You by any and
+ all Contributors for the Covered Software under Section 2.1 of this License
+ shall terminate.
+
+5.3. In the event of termination under Sections 5.1 or 5.2 above, all end user
+ license agreements (excluding distributors and resellers) which have been
+ validly granted by You or Your distributors under this License prior to
+ termination shall survive termination.
+
+6. Disclaimer of Warranty
+
+ Covered Software is provided under this License on an “as is” basis, without
+ warranty of any kind, either expressed, implied, or statutory, including,
+ without limitation, warranties that the Covered Software is free of defects,
+ merchantable, fit for a particular purpose or non-infringing. The entire
+ risk as to the quality and performance of the Covered Software is with You.
+ Should any Covered Software prove defective in any respect, You (not any
+ Contributor) assume the cost of any necessary servicing, repair, or
+ correction. This disclaimer of warranty constitutes an essential part of this
+ License. No use of any Covered Software is authorized under this License
+ except under this disclaimer.
+
+7. Limitation of Liability
+
+ Under no circumstances and under no legal theory, whether tort (including
+ negligence), contract, or otherwise, shall any Contributor, or anyone who
+ distributes Covered Software as permitted above, be liable to You for any
+ direct, indirect, special, incidental, or consequential damages of any
+ character including, without limitation, damages for lost profits, loss of
+ goodwill, work stoppage, computer failure or malfunction, or any and all
+ other commercial damages or losses, even if such party shall have been
+ informed of the possibility of such damages. This limitation of liability
+ shall not apply to liability for death or personal injury resulting from such
+ party’s negligence to the extent applicable law prohibits such limitation.
+ Some jurisdictions do not allow the exclusion or limitation of incidental or
+ consequential damages, so this exclusion and limitation may not apply to You.
+
+8. Litigation
+
+ Any litigation relating to this License may be brought only in the courts of
+ a jurisdiction where the defendant maintains its principal place of business
+ and such litigation shall be governed by laws of that jurisdiction, without
+ reference to its conflict-of-law provisions. Nothing in this Section shall
+ prevent a party’s ability to bring cross-claims or counter-claims.
+
+9. Miscellaneous
+
+ This License represents the complete agreement concerning the subject matter
+ hereof. If any provision of this License is held to be unenforceable, such
+ provision shall be reformed only to the extent necessary to make it
+ enforceable. Any law or regulation which provides that the language of a
+ contract shall be construed against the drafter shall not be used to construe
+ this License against a Contributor.
+
+
+10. Versions of the License
+
+10.1. New Versions
+
+ Mozilla Foundation is the license steward. Except as provided in Section
+ 10.3, no one other than the license steward has the right to modify or
+ publish new versions of this License. Each version will be given a
+ distinguishing version number.
+
+10.2. Effect of New Versions
+
+ You may distribute the Covered Software under the terms of the version of
+ the License under which You originally received the Covered Software, or
+ under the terms of any subsequent version published by the license
+ steward.
+
+10.3. Modified Versions
+
+ If you create software not governed by this License, and you want to
+ create a new license for such software, you may create and use a modified
+ version of this License if you rename the license and remove any
+ references to the name of the license steward (except to note that such
+ modified license differs from this License).
+
+10.4. Distributing Source Code Form that is Incompatible With Secondary Licenses
+ If You choose to distribute Source Code Form that is Incompatible With
+ Secondary Licenses under the terms of this version of the License, the
+ notice described in Exhibit B of this License must be attached.
+
+Exhibit A - Source Code Form License Notice
+
+ This Source Code Form is subject to the
+ terms of the Mozilla Public License, v.
+ 2.0. If a copy of the MPL was not
+ distributed with this file, You can
+ obtain one at
+ http://mozilla.org/MPL/2.0/.
+
+If it is not possible or desirable to put the notice in a particular file, then
+You may include the notice in a location (such as a LICENSE file in a relevant
+directory) where a recipient would be likely to look for such a notice.
+
+You may add additional accurate notices of copyright ownership.
+
+Exhibit B - “Incompatible With Secondary Licenses” Notice
+
+ This Source Code Form is “Incompatible
+ With Secondary Licenses”, as defined by
+ the Mozilla Public License, v. 2.0.
+
diff --git a/vendor/github.com/hashicorp/serf/coordinate/client.go b/vendor/github.com/hashicorp/serf/coordinate/client.go
new file mode 100644
index 0000000..3582ee4
--- /dev/null
+++ b/vendor/github.com/hashicorp/serf/coordinate/client.go
@@ -0,0 +1,243 @@
+package coordinate
+
+import (
+ "fmt"
+ "math"
+ "sort"
+ "sync"
+ "time"
+
+ "github.com/armon/go-metrics"
+)
+
+// Client manages the estimated network coordinate for a given node, and adjusts
+// it as the node observes round trip times and estimated coordinates from other
+// nodes. The core algorithm is based on Vivaldi, see the documentation for Config
+// for more details.
+type Client struct {
+ // coord is the current estimate of the client's network coordinate.
+ coord *Coordinate
+
+ // origin is a coordinate sitting at the origin.
+ origin *Coordinate
+
+ // config contains the tuning parameters that govern the performance of
+ // the algorithm.
+ config *Config
+
+ // adjustmentIndex is the current index into the adjustmentSamples slice.
+ adjustmentIndex uint
+
+ // adjustment is used to store samples for the adjustment calculation.
+ adjustmentSamples []float64
+
+ // latencyFilterSamples is used to store the last several RTT samples,
+ // keyed by node name. We will use the config's LatencyFilterSamples
+ // value to determine how many samples we keep, per node.
+ latencyFilterSamples map[string][]float64
+
+ // stats is used to record events that occur when updating coordinates.
+ stats ClientStats
+
+ // mutex enables safe concurrent access to the client.
+ mutex sync.RWMutex
+}
+
+// ClientStats is used to record events that occur when updating coordinates.
+type ClientStats struct {
+ // Resets is incremented any time we reset our local coordinate because
+ // our calculations have resulted in an invalid state.
+ Resets int
+}
+
+// NewClient creates a new Client and verifies the configuration is valid.
+func NewClient(config *Config) (*Client, error) {
+ if !(config.Dimensionality > 0) {
+ return nil, fmt.Errorf("dimensionality must be >0")
+ }
+
+ return &Client{
+ coord: NewCoordinate(config),
+ origin: NewCoordinate(config),
+ config: config,
+ adjustmentIndex: 0,
+ adjustmentSamples: make([]float64, config.AdjustmentWindowSize),
+ latencyFilterSamples: make(map[string][]float64),
+ }, nil
+}
+
+// GetCoordinate returns a copy of the coordinate for this client.
+func (c *Client) GetCoordinate() *Coordinate {
+ c.mutex.RLock()
+ defer c.mutex.RUnlock()
+
+ return c.coord.Clone()
+}
+
+// SetCoordinate forces the client's coordinate to a known state.
+func (c *Client) SetCoordinate(coord *Coordinate) error {
+ c.mutex.Lock()
+ defer c.mutex.Unlock()
+
+ if err := c.checkCoordinate(coord); err != nil {
+ return err
+ }
+
+ c.coord = coord.Clone()
+ return nil
+}
+
+// ForgetNode removes any client state for the given node.
+func (c *Client) ForgetNode(node string) {
+ c.mutex.Lock()
+ defer c.mutex.Unlock()
+
+ delete(c.latencyFilterSamples, node)
+}
+
+// Stats returns a copy of stats for the client.
+func (c *Client) Stats() ClientStats {
+ c.mutex.Lock()
+ defer c.mutex.Unlock()
+
+ return c.stats
+}
+
+// checkCoordinate returns an error if the coordinate isn't compatible with
+// this client, or if the coordinate itself isn't valid. This assumes the mutex
+// has been locked already.
+func (c *Client) checkCoordinate(coord *Coordinate) error {
+ if !c.coord.IsCompatibleWith(coord) {
+ return fmt.Errorf("dimensions aren't compatible")
+ }
+
+ if !coord.IsValid() {
+ return fmt.Errorf("coordinate is invalid")
+ }
+
+ return nil
+}
+
+// latencyFilter applies a simple moving median filter with a new sample for
+// a node. This assumes that the mutex has been locked already.
+func (c *Client) latencyFilter(node string, rttSeconds float64) float64 {
+ samples, ok := c.latencyFilterSamples[node]
+ if !ok {
+ samples = make([]float64, 0, c.config.LatencyFilterSize)
+ }
+
+ // Add the new sample and trim the list, if needed.
+ samples = append(samples, rttSeconds)
+ if len(samples) > int(c.config.LatencyFilterSize) {
+ samples = samples[1:]
+ }
+ c.latencyFilterSamples[node] = samples
+
+ // Sort a copy of the samples and return the median.
+ sorted := make([]float64, len(samples))
+ copy(sorted, samples)
+ sort.Float64s(sorted)
+ return sorted[len(sorted)/2]
+}
+
+// updateVivialdi updates the Vivaldi portion of the client's coordinate. This
+// assumes that the mutex has been locked already.
+func (c *Client) updateVivaldi(other *Coordinate, rttSeconds float64) {
+ const zeroThreshold = 1.0e-6
+
+ dist := c.coord.DistanceTo(other).Seconds()
+ if rttSeconds < zeroThreshold {
+ rttSeconds = zeroThreshold
+ }
+ wrongness := math.Abs(dist-rttSeconds) / rttSeconds
+
+ totalError := c.coord.Error + other.Error
+ if totalError < zeroThreshold {
+ totalError = zeroThreshold
+ }
+ weight := c.coord.Error / totalError
+
+ c.coord.Error = c.config.VivaldiCE*weight*wrongness + c.coord.Error*(1.0-c.config.VivaldiCE*weight)
+ if c.coord.Error > c.config.VivaldiErrorMax {
+ c.coord.Error = c.config.VivaldiErrorMax
+ }
+
+ delta := c.config.VivaldiCC * weight
+ force := delta * (rttSeconds - dist)
+ c.coord = c.coord.ApplyForce(c.config, force, other)
+}
+
+// updateAdjustment updates the adjustment portion of the client's coordinate, if
+// the feature is enabled. This assumes that the mutex has been locked already.
+func (c *Client) updateAdjustment(other *Coordinate, rttSeconds float64) {
+ if c.config.AdjustmentWindowSize == 0 {
+ return
+ }
+
+ // Note that the existing adjustment factors don't figure in to this
+ // calculation so we use the raw distance here.
+ dist := c.coord.rawDistanceTo(other)
+ c.adjustmentSamples[c.adjustmentIndex] = rttSeconds - dist
+ c.adjustmentIndex = (c.adjustmentIndex + 1) % c.config.AdjustmentWindowSize
+
+ sum := 0.0
+ for _, sample := range c.adjustmentSamples {
+ sum += sample
+ }
+ c.coord.Adjustment = sum / (2.0 * float64(c.config.AdjustmentWindowSize))
+}
+
+// updateGravity applies a small amount of gravity to pull coordinates towards
+// the center of the coordinate system to combat drift. This assumes that the
+// mutex is locked already.
+func (c *Client) updateGravity() {
+ dist := c.origin.DistanceTo(c.coord).Seconds()
+ force := -1.0 * math.Pow(dist/c.config.GravityRho, 2.0)
+ c.coord = c.coord.ApplyForce(c.config, force, c.origin)
+}
+
+// Update takes other, a coordinate for another node, and rtt, a round trip
+// time observation for a ping to that node, and updates the estimated position of
+// the client's coordinate. Returns the updated coordinate.
+func (c *Client) Update(node string, other *Coordinate, rtt time.Duration) (*Coordinate, error) {
+ c.mutex.Lock()
+ defer c.mutex.Unlock()
+
+ if err := c.checkCoordinate(other); err != nil {
+ return nil, err
+ }
+
+ // The code down below can handle zero RTTs, which we have seen in
+ // https://github.com/hashicorp/consul/issues/3789, presumably in
+ // environments with coarse-grained monotonic clocks (we are still
+ // trying to pin this down). In any event, this is ok from a code PoV
+ // so we don't need to alert operators with spammy messages. We did
+ // add a counter so this is still observable, though.
+ const maxRTT = 10 * time.Second
+ if rtt < 0 || rtt > maxRTT {
+ return nil, fmt.Errorf("round trip time not in valid range, duration %v is not a positive value less than %v ", rtt, maxRTT)
+ }
+ if rtt == 0 {
+ metrics.IncrCounter([]string{"serf", "coordinate", "zero-rtt"}, 1)
+ }
+
+ rttSeconds := c.latencyFilter(node, rtt.Seconds())
+ c.updateVivaldi(other, rttSeconds)
+ c.updateAdjustment(other, rttSeconds)
+ c.updateGravity()
+ if !c.coord.IsValid() {
+ c.stats.Resets++
+ c.coord = NewCoordinate(c.config)
+ }
+
+ return c.coord.Clone(), nil
+}
+
+// DistanceTo returns the estimated RTT from the client's coordinate to other, the
+// coordinate for another node.
+func (c *Client) DistanceTo(other *Coordinate) time.Duration {
+ c.mutex.RLock()
+ defer c.mutex.RUnlock()
+
+ return c.coord.DistanceTo(other)
+}
diff --git a/vendor/github.com/hashicorp/serf/coordinate/config.go b/vendor/github.com/hashicorp/serf/coordinate/config.go
new file mode 100644
index 0000000..b85a8ab
--- /dev/null
+++ b/vendor/github.com/hashicorp/serf/coordinate/config.go
@@ -0,0 +1,70 @@
+package coordinate
+
+// Config is used to set the parameters of the Vivaldi-based coordinate mapping
+// algorithm.
+//
+// The following references are called out at various points in the documentation
+// here:
+//
+// [1] Dabek, Frank, et al. "Vivaldi: A decentralized network coordinate system."
+// ACM SIGCOMM Computer Communication Review. Vol. 34. No. 4. ACM, 2004.
+// [2] Ledlie, Jonathan, Paul Gardner, and Margo I. Seltzer. "Network Coordinates
+// in the Wild." NSDI. Vol. 7. 2007.
+// [3] Lee, Sanghwan, et al. "On suitability of Euclidean embedding for
+// host-based network coordinate systems." Networking, IEEE/ACM Transactions
+// on 18.1 (2010): 27-40.
+type Config struct {
+ // The dimensionality of the coordinate system. As discussed in [2], more
+ // dimensions improves the accuracy of the estimates up to a point. Per [2]
+ // we chose 8 dimensions plus a non-Euclidean height.
+ Dimensionality uint
+
+ // VivaldiErrorMax is the default error value when a node hasn't yet made
+ // any observations. It also serves as an upper limit on the error value in
+ // case observations cause the error value to increase without bound.
+ VivaldiErrorMax float64
+
+ // VivaldiCE is a tuning factor that controls the maximum impact an
+ // observation can have on a node's confidence. See [1] for more details.
+ VivaldiCE float64
+
+ // VivaldiCC is a tuning factor that controls the maximum impact an
+ // observation can have on a node's coordinate. See [1] for more details.
+ VivaldiCC float64
+
+ // AdjustmentWindowSize is a tuning factor that determines how many samples
+ // we retain to calculate the adjustment factor as discussed in [3]. Setting
+ // this to zero disables this feature.
+ AdjustmentWindowSize uint
+
+ // HeightMin is the minimum value of the height parameter. Since this
+ // always must be positive, it will introduce a small amount error, so
+ // the chosen value should be relatively small compared to "normal"
+ // coordinates.
+ HeightMin float64
+
+ // LatencyFilterSamples is the maximum number of samples that are retained
+ // per node, in order to compute a median. The intent is to ride out blips
+ // but still keep the delay low, since our time to probe any given node is
+ // pretty infrequent. See [2] for more details.
+ LatencyFilterSize uint
+
+ // GravityRho is a tuning factor that sets how much gravity has an effect
+ // to try to re-center coordinates. See [2] for more details.
+ GravityRho float64
+}
+
+// DefaultConfig returns a Config that has some default values suitable for
+// basic testing of the algorithm, but not tuned to any particular type of cluster.
+func DefaultConfig() *Config {
+ return &Config{
+ Dimensionality: 8,
+ VivaldiErrorMax: 1.5,
+ VivaldiCE: 0.25,
+ VivaldiCC: 0.25,
+ AdjustmentWindowSize: 20,
+ HeightMin: 10.0e-6,
+ LatencyFilterSize: 3,
+ GravityRho: 150.0,
+ }
+}
diff --git a/vendor/github.com/hashicorp/serf/coordinate/coordinate.go b/vendor/github.com/hashicorp/serf/coordinate/coordinate.go
new file mode 100644
index 0000000..fbe792c
--- /dev/null
+++ b/vendor/github.com/hashicorp/serf/coordinate/coordinate.go
@@ -0,0 +1,203 @@
+package coordinate
+
+import (
+ "math"
+ "math/rand"
+ "time"
+)
+
+// Coordinate is a specialized structure for holding network coordinates for the
+// Vivaldi-based coordinate mapping algorithm. All of the fields should be public
+// to enable this to be serialized. All values in here are in units of seconds.
+type Coordinate struct {
+ // Vec is the Euclidean portion of the coordinate. This is used along
+ // with the other fields to provide an overall distance estimate. The
+ // units here are seconds.
+ Vec []float64
+
+ // Err reflects the confidence in the given coordinate and is updated
+ // dynamically by the Vivaldi Client. This is dimensionless.
+ Error float64
+
+ // Adjustment is a distance offset computed based on a calculation over
+ // observations from all other nodes over a fixed window and is updated
+ // dynamically by the Vivaldi Client. The units here are seconds.
+ Adjustment float64
+
+ // Height is a distance offset that accounts for non-Euclidean effects
+ // which model the access links from nodes to the core Internet. The access
+ // links are usually set by bandwidth and congestion, and the core links
+ // usually follow distance based on geography.
+ Height float64
+}
+
+const (
+ // secondsToNanoseconds is used to convert float seconds to nanoseconds.
+ secondsToNanoseconds = 1.0e9
+
+ // zeroThreshold is used to decide if two coordinates are on top of each
+ // other.
+ zeroThreshold = 1.0e-6
+)
+
+// ErrDimensionalityConflict will be panic-d if you try to perform operations
+// with incompatible dimensions.
+type DimensionalityConflictError struct{}
+
+// Adds the error interface.
+func (e DimensionalityConflictError) Error() string {
+ return "coordinate dimensionality does not match"
+}
+
+// NewCoordinate creates a new coordinate at the origin, using the given config
+// to supply key initial values.
+func NewCoordinate(config *Config) *Coordinate {
+ return &Coordinate{
+ Vec: make([]float64, config.Dimensionality),
+ Error: config.VivaldiErrorMax,
+ Adjustment: 0.0,
+ Height: config.HeightMin,
+ }
+}
+
+// Clone creates an independent copy of this coordinate.
+func (c *Coordinate) Clone() *Coordinate {
+ vec := make([]float64, len(c.Vec))
+ copy(vec, c.Vec)
+ return &Coordinate{
+ Vec: vec,
+ Error: c.Error,
+ Adjustment: c.Adjustment,
+ Height: c.Height,
+ }
+}
+
+// componentIsValid returns false if a floating point value is a NaN or an
+// infinity.
+func componentIsValid(f float64) bool {
+ return !math.IsInf(f, 0) && !math.IsNaN(f)
+}
+
+// IsValid returns false if any component of a coordinate isn't valid, per the
+// componentIsValid() helper above.
+func (c *Coordinate) IsValid() bool {
+ for i := range c.Vec {
+ if !componentIsValid(c.Vec[i]) {
+ return false
+ }
+ }
+
+ return componentIsValid(c.Error) &&
+ componentIsValid(c.Adjustment) &&
+ componentIsValid(c.Height)
+}
+
+// IsCompatibleWith checks to see if the two coordinates are compatible
+// dimensionally. If this returns true then you are guaranteed to not get
+// any runtime errors operating on them.
+func (c *Coordinate) IsCompatibleWith(other *Coordinate) bool {
+ return len(c.Vec) == len(other.Vec)
+}
+
+// ApplyForce returns the result of applying the force from the direction of the
+// other coordinate.
+func (c *Coordinate) ApplyForce(config *Config, force float64, other *Coordinate) *Coordinate {
+ if !c.IsCompatibleWith(other) {
+ panic(DimensionalityConflictError{})
+ }
+
+ ret := c.Clone()
+ unit, mag := unitVectorAt(c.Vec, other.Vec)
+ ret.Vec = add(ret.Vec, mul(unit, force))
+ if mag > zeroThreshold {
+ ret.Height = (ret.Height+other.Height)*force/mag + ret.Height
+ ret.Height = math.Max(ret.Height, config.HeightMin)
+ }
+ return ret
+}
+
+// DistanceTo returns the distance between this coordinate and the other
+// coordinate, including adjustments.
+func (c *Coordinate) DistanceTo(other *Coordinate) time.Duration {
+ if !c.IsCompatibleWith(other) {
+ panic(DimensionalityConflictError{})
+ }
+
+ dist := c.rawDistanceTo(other)
+ adjustedDist := dist + c.Adjustment + other.Adjustment
+ if adjustedDist > 0.0 {
+ dist = adjustedDist
+ }
+ return time.Duration(dist * secondsToNanoseconds)
+}
+
+// rawDistanceTo returns the Vivaldi distance between this coordinate and the
+// other coordinate in seconds, not including adjustments. This assumes the
+// dimensions have already been checked to be compatible.
+func (c *Coordinate) rawDistanceTo(other *Coordinate) float64 {
+ return magnitude(diff(c.Vec, other.Vec)) + c.Height + other.Height
+}
+
+// add returns the sum of vec1 and vec2. This assumes the dimensions have
+// already been checked to be compatible.
+func add(vec1 []float64, vec2 []float64) []float64 {
+ ret := make([]float64, len(vec1))
+ for i := range ret {
+ ret[i] = vec1[i] + vec2[i]
+ }
+ return ret
+}
+
+// diff returns the difference between the vec1 and vec2. This assumes the
+// dimensions have already been checked to be compatible.
+func diff(vec1 []float64, vec2 []float64) []float64 {
+ ret := make([]float64, len(vec1))
+ for i := range ret {
+ ret[i] = vec1[i] - vec2[i]
+ }
+ return ret
+}
+
+// mul returns vec multiplied by a scalar factor.
+func mul(vec []float64, factor float64) []float64 {
+ ret := make([]float64, len(vec))
+ for i := range vec {
+ ret[i] = vec[i] * factor
+ }
+ return ret
+}
+
+// magnitude computes the magnitude of the vec.
+func magnitude(vec []float64) float64 {
+ sum := 0.0
+ for i := range vec {
+ sum += vec[i] * vec[i]
+ }
+ return math.Sqrt(sum)
+}
+
+// unitVectorAt returns a unit vector pointing at vec1 from vec2. If the two
+// positions are the same then a random unit vector is returned. We also return
+// the distance between the points for use in the later height calculation.
+func unitVectorAt(vec1 []float64, vec2 []float64) ([]float64, float64) {
+ ret := diff(vec1, vec2)
+
+ // If the coordinates aren't on top of each other we can normalize.
+ if mag := magnitude(ret); mag > zeroThreshold {
+ return mul(ret, 1.0/mag), mag
+ }
+
+ // Otherwise, just return a random unit vector.
+ for i := range ret {
+ ret[i] = rand.Float64() - 0.5
+ }
+ if mag := magnitude(ret); mag > zeroThreshold {
+ return mul(ret, 1.0/mag), 0.0
+ }
+
+ // And finally just give up and make a unit vector along the first
+ // dimension. This should be exceedingly rare.
+ ret = make([]float64, len(ret))
+ ret[0] = 1.0
+ return ret, 0.0
+}
diff --git a/vendor/github.com/hashicorp/serf/coordinate/phantom.go b/vendor/github.com/hashicorp/serf/coordinate/phantom.go
new file mode 100644
index 0000000..6fb033c
--- /dev/null
+++ b/vendor/github.com/hashicorp/serf/coordinate/phantom.go
@@ -0,0 +1,187 @@
+package coordinate
+
+import (
+ "fmt"
+ "math"
+ "math/rand"
+ "time"
+)
+
+// GenerateClients returns a slice with nodes number of clients, all with the
+// given config.
+func GenerateClients(nodes int, config *Config) ([]*Client, error) {
+ clients := make([]*Client, nodes)
+ for i, _ := range clients {
+ client, err := NewClient(config)
+ if err != nil {
+ return nil, err
+ }
+
+ clients[i] = client
+ }
+ return clients, nil
+}
+
+// GenerateLine returns a truth matrix as if all the nodes are in a straight linke
+// with the given spacing between them.
+func GenerateLine(nodes int, spacing time.Duration) [][]time.Duration {
+ truth := make([][]time.Duration, nodes)
+ for i := range truth {
+ truth[i] = make([]time.Duration, nodes)
+ }
+
+ for i := 0; i < nodes; i++ {
+ for j := i + 1; j < nodes; j++ {
+ rtt := time.Duration(j-i) * spacing
+ truth[i][j], truth[j][i] = rtt, rtt
+ }
+ }
+ return truth
+}
+
+// GenerateGrid returns a truth matrix as if all the nodes are in a two dimensional
+// grid with the given spacing between them.
+func GenerateGrid(nodes int, spacing time.Duration) [][]time.Duration {
+ truth := make([][]time.Duration, nodes)
+ for i := range truth {
+ truth[i] = make([]time.Duration, nodes)
+ }
+
+ n := int(math.Sqrt(float64(nodes)))
+ for i := 0; i < nodes; i++ {
+ for j := i + 1; j < nodes; j++ {
+ x1, y1 := float64(i%n), float64(i/n)
+ x2, y2 := float64(j%n), float64(j/n)
+ dx, dy := x2-x1, y2-y1
+ dist := math.Sqrt(dx*dx + dy*dy)
+ rtt := time.Duration(dist * float64(spacing))
+ truth[i][j], truth[j][i] = rtt, rtt
+ }
+ }
+ return truth
+}
+
+// GenerateSplit returns a truth matrix as if half the nodes are close together in
+// one location and half the nodes are close together in another. The lan factor
+// is used to separate the nodes locally and the wan factor represents the split
+// between the two sides.
+func GenerateSplit(nodes int, lan time.Duration, wan time.Duration) [][]time.Duration {
+ truth := make([][]time.Duration, nodes)
+ for i := range truth {
+ truth[i] = make([]time.Duration, nodes)
+ }
+
+ split := nodes / 2
+ for i := 0; i < nodes; i++ {
+ for j := i + 1; j < nodes; j++ {
+ rtt := lan
+ if (i <= split && j > split) || (i > split && j <= split) {
+ rtt += wan
+ }
+ truth[i][j], truth[j][i] = rtt, rtt
+ }
+ }
+ return truth
+}
+
+// GenerateCircle returns a truth matrix for a set of nodes, evenly distributed
+// around a circle with the given radius. The first node is at the "center" of the
+// circle because it's equidistant from all the other nodes, but we place it at
+// double the radius, so it should show up above all the other nodes in height.
+func GenerateCircle(nodes int, radius time.Duration) [][]time.Duration {
+ truth := make([][]time.Duration, nodes)
+ for i := range truth {
+ truth[i] = make([]time.Duration, nodes)
+ }
+
+ for i := 0; i < nodes; i++ {
+ for j := i + 1; j < nodes; j++ {
+ var rtt time.Duration
+ if i == 0 {
+ rtt = 2 * radius
+ } else {
+ t1 := 2.0 * math.Pi * float64(i) / float64(nodes)
+ x1, y1 := math.Cos(t1), math.Sin(t1)
+ t2 := 2.0 * math.Pi * float64(j) / float64(nodes)
+ x2, y2 := math.Cos(t2), math.Sin(t2)
+ dx, dy := x2-x1, y2-y1
+ dist := math.Sqrt(dx*dx + dy*dy)
+ rtt = time.Duration(dist * float64(radius))
+ }
+ truth[i][j], truth[j][i] = rtt, rtt
+ }
+ }
+ return truth
+}
+
+// GenerateRandom returns a truth matrix for a set of nodes with normally
+// distributed delays, with the given mean and deviation. The RNG is re-seeded
+// so you always get the same matrix for a given size.
+func GenerateRandom(nodes int, mean time.Duration, deviation time.Duration) [][]time.Duration {
+ rand.Seed(1)
+
+ truth := make([][]time.Duration, nodes)
+ for i := range truth {
+ truth[i] = make([]time.Duration, nodes)
+ }
+
+ for i := 0; i < nodes; i++ {
+ for j := i + 1; j < nodes; j++ {
+ rttSeconds := rand.NormFloat64()*deviation.Seconds() + mean.Seconds()
+ rtt := time.Duration(rttSeconds * secondsToNanoseconds)
+ truth[i][j], truth[j][i] = rtt, rtt
+ }
+ }
+ return truth
+}
+
+// Simulate runs the given number of cycles using the given list of clients and
+// truth matrix. On each cycle, each client will pick a random node and observe
+// the truth RTT, updating its coordinate estimate. The RNG is re-seeded for
+// each simulation run to get deterministic results (for this algorithm and the
+// underlying algorithm which will use random numbers for position vectors when
+// starting out with everything at the origin).
+func Simulate(clients []*Client, truth [][]time.Duration, cycles int) {
+ rand.Seed(1)
+
+ nodes := len(clients)
+ for cycle := 0; cycle < cycles; cycle++ {
+ for i, _ := range clients {
+ if j := rand.Intn(nodes); j != i {
+ c := clients[j].GetCoordinate()
+ rtt := truth[i][j]
+ node := fmt.Sprintf("node_%d", j)
+ clients[i].Update(node, c, rtt)
+ }
+ }
+ }
+}
+
+// Stats is returned from the Evaluate function with a summary of the algorithm
+// performance.
+type Stats struct {
+ ErrorMax float64
+ ErrorAvg float64
+}
+
+// Evaluate uses the coordinates of the given clients to calculate estimated
+// distances and compares them with the given truth matrix, returning summary
+// stats.
+func Evaluate(clients []*Client, truth [][]time.Duration) (stats Stats) {
+ nodes := len(clients)
+ count := 0
+ for i := 0; i < nodes; i++ {
+ for j := i + 1; j < nodes; j++ {
+ est := clients[i].DistanceTo(clients[j].GetCoordinate()).Seconds()
+ actual := truth[i][j].Seconds()
+ error := math.Abs(est-actual) / actual
+ stats.ErrorMax = math.Max(stats.ErrorMax, error)
+ stats.ErrorAvg += error
+ count += 1
+ }
+ }
+
+ stats.ErrorAvg /= float64(count)
+ fmt.Printf("Error avg=%9.6f max=%9.6f\n", stats.ErrorAvg, stats.ErrorMax)
+ return
+}