VOL-1967 move api-server to separate repository
Change-Id: I21b85be74205805be15f8a85e53a903d16785671
diff --git a/vendor/go.etcd.io/etcd/raft/quorum/joint.go b/vendor/go.etcd.io/etcd/raft/quorum/joint.go
new file mode 100644
index 0000000..e3741e0
--- /dev/null
+++ b/vendor/go.etcd.io/etcd/raft/quorum/joint.go
@@ -0,0 +1,75 @@
+// Copyright 2019 The etcd Authors
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package quorum
+
+// JointConfig is a configuration of two groups of (possibly overlapping)
+// majority configurations. Decisions require the support of both majorities.
+type JointConfig [2]MajorityConfig
+
+func (c JointConfig) String() string {
+ if len(c[1]) > 0 {
+ return c[0].String() + "&&" + c[1].String()
+ }
+ return c[0].String()
+}
+
+// IDs returns a newly initialized map representing the set of voters present
+// in the joint configuration.
+func (c JointConfig) IDs() map[uint64]struct{} {
+ m := map[uint64]struct{}{}
+ for _, cc := range c {
+ for id := range cc {
+ m[id] = struct{}{}
+ }
+ }
+ return m
+}
+
+// Describe returns a (multi-line) representation of the commit indexes for the
+// given lookuper.
+func (c JointConfig) Describe(l AckedIndexer) string {
+ return MajorityConfig(c.IDs()).Describe(l)
+}
+
+// CommittedIndex returns the largest committed index for the given joint
+// quorum. An index is jointly committed if it is committed in both constituent
+// majorities.
+func (c JointConfig) CommittedIndex(l AckedIndexer) Index {
+ idx0 := c[0].CommittedIndex(l)
+ idx1 := c[1].CommittedIndex(l)
+ if idx0 < idx1 {
+ return idx0
+ }
+ return idx1
+}
+
+// VoteResult takes a mapping of voters to yes/no (true/false) votes and returns
+// a result indicating whether the vote is pending, lost, or won. A joint quorum
+// requires both majority quorums to vote in favor.
+func (c JointConfig) VoteResult(votes map[uint64]bool) VoteResult {
+ r1 := c[0].VoteResult(votes)
+ r2 := c[1].VoteResult(votes)
+
+ if r1 == r2 {
+ // If they agree, return the agreed state.
+ return r1
+ }
+ if r1 == VoteLost || r2 == VoteLost {
+ // If either config has lost, loss is the only possible outcome.
+ return VoteLost
+ }
+ // One side won, the other one is pending, so the whole outcome is.
+ return VotePending
+}
diff --git a/vendor/go.etcd.io/etcd/raft/quorum/majority.go b/vendor/go.etcd.io/etcd/raft/quorum/majority.go
new file mode 100644
index 0000000..8858a36
--- /dev/null
+++ b/vendor/go.etcd.io/etcd/raft/quorum/majority.go
@@ -0,0 +1,210 @@
+// Copyright 2019 The etcd Authors
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package quorum
+
+import (
+ "fmt"
+ "math"
+ "sort"
+ "strings"
+)
+
+// MajorityConfig is a set of IDs that uses majority quorums to make decisions.
+type MajorityConfig map[uint64]struct{}
+
+func (c MajorityConfig) String() string {
+ sl := make([]uint64, 0, len(c))
+ for id := range c {
+ sl = append(sl, id)
+ }
+ sort.Slice(sl, func(i, j int) bool { return sl[i] < sl[j] })
+ var buf strings.Builder
+ buf.WriteByte('(')
+ for i := range sl {
+ if i > 0 {
+ buf.WriteByte(' ')
+ }
+ fmt.Fprint(&buf, sl[i])
+ }
+ buf.WriteByte(')')
+ return buf.String()
+}
+
+// Describe returns a (multi-line) representation of the commit indexes for the
+// given lookuper.
+func (c MajorityConfig) Describe(l AckedIndexer) string {
+ if len(c) == 0 {
+ return "<empty majority quorum>"
+ }
+ type tup struct {
+ id uint64
+ idx Index
+ ok bool // idx found?
+ bar int // length of bar displayed for this tup
+ }
+
+ // Below, populate .bar so that the i-th largest commit index has bar i (we
+ // plot this as sort of a progress bar). The actual code is a bit more
+ // complicated and also makes sure that equal index => equal bar.
+
+ n := len(c)
+ info := make([]tup, 0, n)
+ for id := range c {
+ idx, ok := l.AckedIndex(id)
+ info = append(info, tup{id: id, idx: idx, ok: ok})
+ }
+
+ // Sort by index
+ sort.Slice(info, func(i, j int) bool {
+ if info[i].idx == info[j].idx {
+ return info[i].id < info[j].id
+ }
+ return info[i].idx < info[j].idx
+ })
+
+ // Populate .bar.
+ for i := range info {
+ if i > 0 && info[i-1].idx < info[i].idx {
+ info[i].bar = i
+ }
+ }
+
+ // Sort by ID.
+ sort.Slice(info, func(i, j int) bool {
+ return info[i].id < info[j].id
+ })
+
+ var buf strings.Builder
+
+ // Print.
+ fmt.Fprint(&buf, strings.Repeat(" ", n)+" idx\n")
+ for i := range info {
+ bar := info[i].bar
+ if !info[i].ok {
+ fmt.Fprint(&buf, "?"+strings.Repeat(" ", n))
+ } else {
+ fmt.Fprint(&buf, strings.Repeat("x", bar)+">"+strings.Repeat(" ", n-bar))
+ }
+ fmt.Fprintf(&buf, " %5d (id=%d)\n", info[i].idx, info[i].id)
+ }
+ return buf.String()
+}
+
+// Slice returns the MajorityConfig as a sorted slice.
+func (c MajorityConfig) Slice() []uint64 {
+ var sl []uint64
+ for id := range c {
+ sl = append(sl, id)
+ }
+ sort.Slice(sl, func(i, j int) bool { return sl[i] < sl[j] })
+ return sl
+}
+
+func insertionSort(sl []uint64) {
+ a, b := 0, len(sl)
+ for i := a + 1; i < b; i++ {
+ for j := i; j > a && sl[j] < sl[j-1]; j-- {
+ sl[j], sl[j-1] = sl[j-1], sl[j]
+ }
+ }
+}
+
+// CommittedIndex computes the committed index from those supplied via the
+// provided AckedIndexer (for the active config).
+func (c MajorityConfig) CommittedIndex(l AckedIndexer) Index {
+ n := len(c)
+ if n == 0 {
+ // This plays well with joint quorums which, when one half is the zero
+ // MajorityConfig, should behave like the other half.
+ return math.MaxUint64
+ }
+
+ // Use an on-stack slice to collect the committed indexes when n <= 7
+ // (otherwise we alloc). The alternative is to stash a slice on
+ // MajorityConfig, but this impairs usability (as is, MajorityConfig is just
+ // a map, and that's nice). The assumption is that running with a
+ // replication factor of >7 is rare, and in cases in which it happens
+ // performance is a lesser concern (additionally the performance
+ // implications of an allocation here are far from drastic).
+ var stk [7]uint64
+ var srt []uint64
+ if len(stk) >= n {
+ srt = stk[:n]
+ } else {
+ srt = make([]uint64, n)
+ }
+
+ {
+ // Fill the slice with the indexes observed. Any unused slots will be
+ // left as zero; these correspond to voters that may report in, but
+ // haven't yet. We fill from the right (since the zeroes will end up on
+ // the left after sorting below anyway).
+ i := n - 1
+ for id := range c {
+ if idx, ok := l.AckedIndex(id); ok {
+ srt[i] = uint64(idx)
+ i--
+ }
+ }
+ }
+
+ // Sort by index. Use a bespoke algorithm (copied from the stdlib's sort
+ // package) to keep srt on the stack.
+ insertionSort(srt)
+
+ // The smallest index into the array for which the value is acked by a
+ // quorum. In other words, from the end of the slice, move n/2+1 to the
+ // left (accounting for zero-indexing).
+ pos := n - (n/2 + 1)
+ return Index(srt[pos])
+}
+
+// VoteResult takes a mapping of voters to yes/no (true/false) votes and returns
+// a result indicating whether the vote is pending (i.e. neither a quorum of
+// yes/no has been reached), won (a quorum of yes has been reached), or lost (a
+// quorum of no has been reached).
+func (c MajorityConfig) VoteResult(votes map[uint64]bool) VoteResult {
+ if len(c) == 0 {
+ // By convention, the elections on an empty config win. This comes in
+ // handy with joint quorums because it'll make a half-populated joint
+ // quorum behave like a majority quorum.
+ return VoteWon
+ }
+
+ ny := [2]int{} // vote counts for no and yes, respectively
+
+ var missing int
+ for id := range c {
+ v, ok := votes[id]
+ if !ok {
+ missing++
+ continue
+ }
+ if v {
+ ny[1]++
+ } else {
+ ny[0]++
+ }
+ }
+
+ q := len(c)/2 + 1
+ if ny[1] >= q {
+ return VoteWon
+ }
+ if ny[1]+missing >= q {
+ return VotePending
+ }
+ return VoteLost
+}
diff --git a/vendor/go.etcd.io/etcd/raft/quorum/quorum.go b/vendor/go.etcd.io/etcd/raft/quorum/quorum.go
new file mode 100644
index 0000000..2899e46
--- /dev/null
+++ b/vendor/go.etcd.io/etcd/raft/quorum/quorum.go
@@ -0,0 +1,58 @@
+// Copyright 2019 The etcd Authors
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package quorum
+
+import (
+ "math"
+ "strconv"
+)
+
+// Index is a Raft log position.
+type Index uint64
+
+func (i Index) String() string {
+ if i == math.MaxUint64 {
+ return "∞"
+ }
+ return strconv.FormatUint(uint64(i), 10)
+}
+
+// AckedIndexer allows looking up a commit index for a given ID of a voter
+// from a corresponding MajorityConfig.
+type AckedIndexer interface {
+ AckedIndex(voterID uint64) (idx Index, found bool)
+}
+
+type mapAckIndexer map[uint64]Index
+
+func (m mapAckIndexer) AckedIndex(id uint64) (Index, bool) {
+ idx, ok := m[id]
+ return idx, ok
+}
+
+// VoteResult indicates the outcome of a vote.
+//
+//go:generate stringer -type=VoteResult
+type VoteResult uint8
+
+const (
+ // VotePending indicates that the decision of the vote depends on future
+ // votes, i.e. neither "yes" or "no" has reached quorum yet.
+ VotePending VoteResult = 1 + iota
+ // VoteLost indicates that the quorum has voted "no".
+ VoteLost
+ // VoteWon indicates that the quorum has voted "yes".
+ VoteWon
+)
diff --git a/vendor/go.etcd.io/etcd/raft/quorum/voteresult_string.go b/vendor/go.etcd.io/etcd/raft/quorum/voteresult_string.go
new file mode 100644
index 0000000..9eca8fd
--- /dev/null
+++ b/vendor/go.etcd.io/etcd/raft/quorum/voteresult_string.go
@@ -0,0 +1,26 @@
+// Code generated by "stringer -type=VoteResult"; DO NOT EDIT.
+
+package quorum
+
+import "strconv"
+
+func _() {
+ // An "invalid array index" compiler error signifies that the constant values have changed.
+ // Re-run the stringer command to generate them again.
+ var x [1]struct{}
+ _ = x[VotePending-1]
+ _ = x[VoteLost-2]
+ _ = x[VoteWon-3]
+}
+
+const _VoteResult_name = "VotePendingVoteLostVoteWon"
+
+var _VoteResult_index = [...]uint8{0, 11, 19, 26}
+
+func (i VoteResult) String() string {
+ i -= 1
+ if i >= VoteResult(len(_VoteResult_index)-1) {
+ return "VoteResult(" + strconv.FormatInt(int64(i+1), 10) + ")"
+ }
+ return _VoteResult_name[_VoteResult_index[i]:_VoteResult_index[i+1]]
+}