-
Notifications
You must be signed in to change notification settings - Fork 41
/
fit.go
313 lines (284 loc) · 8.9 KB
/
fit.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
// Copyright 2020 PingCAP, Inc.
// Modifications copyright (C) 2021 MatrixOrigin.
//
// 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,
// See the License for the specific language governing permissions and
// limitations under the License.
package placement
import (
"math"
"sort"
"github.com/matrixorigin/matrixcube/components/prophet/core"
"github.com/matrixorigin/matrixcube/components/prophet/metadata"
"github.com/matrixorigin/matrixcube/components/prophet/pb/metapb"
)
// ResourceFit is the result of fitting a resource's peers to rule list.
// All peers are divided into corresponding rules according to the matching
// rules, and the remaining Peers are placed in the OrphanPeers list.
type ResourceFit struct {
RuleFits []*RuleFit
OrphanPeers []metapb.Replica
}
// IsSatisfied returns if the rules are properly satisfied.
// It means all Rules are fulfilled and there is no orphan peers.
func (f *ResourceFit) IsSatisfied() bool {
if len(f.RuleFits) == 0 {
return false
}
for _, r := range f.RuleFits {
if !r.IsSatisfied() {
return false
}
}
return len(f.OrphanPeers) == 0
}
// GetRuleFit returns the RuleFit that contains the peer.
func (f *ResourceFit) GetRuleFit(peerID uint64) *RuleFit {
for _, rf := range f.RuleFits {
for _, p := range rf.Peers {
if p.ID == peerID {
return rf
}
}
}
return nil
}
// CompareResourceFit determines the superiority of 2 fits.
// It returns 1 when the first fit result is better.
func CompareResourceFit(a, b *ResourceFit) int {
for i := range a.RuleFits {
if i >= len(b.RuleFits) {
break
}
if cmp := compareRuleFit(a.RuleFits[i], b.RuleFits[i]); cmp != 0 {
return cmp
}
}
switch {
case len(a.OrphanPeers) < len(b.OrphanPeers):
return 1
case len(a.OrphanPeers) > len(b.OrphanPeers):
return -1
default:
return 0
}
}
// RuleFit is the result of fitting status of a Rule.
type RuleFit struct {
Rule *Rule
// Peers of the Resource that are divided to this Rule.
Peers []metapb.Replica
// PeersWithDifferentRole is subset of `Peers`. It contains all Peers that have
// different Role from configuration (the Role can be migrated to target role
// by scheduling).
PeersWithDifferentRole []metapb.Replica
// IsolationScore indicates at which level of labeling these Peers are
// isolated. A larger value is better.
IsolationScore float64
}
// IsSatisfied returns if the rule is properly satisfied.
func (f *RuleFit) IsSatisfied() bool {
return len(f.Peers) == f.Rule.Count && len(f.PeersWithDifferentRole) == 0
}
func compareRuleFit(a, b *RuleFit) int {
switch {
case len(a.Peers) < len(b.Peers):
return -1
case len(a.Peers) > len(b.Peers):
return 1
case len(a.PeersWithDifferentRole) > len(b.PeersWithDifferentRole):
return -1
case len(a.PeersWithDifferentRole) < len(b.PeersWithDifferentRole):
return 1
case a.IsolationScore < b.IsolationScore:
return -1
case a.IsolationScore > b.IsolationScore:
return 1
default:
return 0
}
}
// ContainerSet represents the container.
type ContainerSet interface {
GetContainers() []*core.CachedContainer
GetContainer(id uint64) *core.CachedContainer
}
// FitResource tries to fit peers of a resource to the rules.
func FitResource(containers ContainerSet, res *core.CachedResource, rules []*Rule) *ResourceFit {
w := newFitWorker(containers, res, rules)
w.run()
return &w.bestFit
}
type fitWorker struct {
containers []*core.CachedContainer
bestFit ResourceFit // update during execution
peers []*fitPeer // p.selected is updated during execution.
rules []*Rule
}
func newFitWorker(containers ContainerSet, res *core.CachedResource, rules []*Rule) *fitWorker {
var peers []*fitPeer
for _, p := range res.Meta.Peers() {
peers = append(peers, &fitPeer{
Replica: p,
container: containers.GetContainer(p.ContainerID),
isLeader: res.GetLeader().GetID() == p.ID,
})
}
// Sort peers to keep the match result deterministic.
sort.Slice(peers, func(i, j int) bool { return peers[i].ID < peers[j].ID })
return &fitWorker{
containers: containers.GetContainers(),
bestFit: ResourceFit{RuleFits: make([]*RuleFit, len(rules))},
peers: peers,
rules: rules,
}
}
func (w *fitWorker) run() {
w.fitRule(0)
w.updateOrphanPeers(0) // All peers go to orphanList when RuleList is empty.
}
// Pick the most suitable peer combination for the rule.
// Index specifies the position of the rule.
// returns true if it replaces `bestFit` with a better alternative.
func (w *fitWorker) fitRule(index int) bool {
if index >= len(w.rules) {
return false
}
var candidates []*fitPeer
if checkRule(w.rules[index], w.containers) {
// Only consider containers:
// 1. Match label constraints
// 2. Role match, or can match after transformed.
// 3. Not selected by other rules.
for _, p := range w.peers {
if MatchLabelConstraints(p.container, w.rules[index].LabelConstraints) &&
p.matchRoleLoose(w.rules[index].Role) &&
!p.selected {
candidates = append(candidates, p)
}
}
}
count := w.rules[index].Count
if len(candidates) < count {
count = len(candidates)
}
return w.enumPeers(candidates, nil, index, count)
}
// Recursively traverses all feasible peer combinations.
// For each combination, call `compareBest` to determine whether it is better
// than the existing option.
// Returns true if it replaces `bestFit` with a better alternative.
func (w *fitWorker) enumPeers(candidates, selected []*fitPeer, index int, count int) bool {
if len(selected) == count {
// We collect enough peers. End recursive.
return w.compareBest(selected, index)
}
var better bool
for i, p := range candidates {
p.selected = true
better = w.enumPeers(candidates[i+1:], append(selected, p), index, count) || better
p.selected = false
}
return better
}
// compareBest checks if the selected peers is better then previous best.
// Returns true if it replaces `bestFit` with a better alternative.
func (w *fitWorker) compareBest(selected []*fitPeer, index int) bool {
rf := newRuleFit(w.rules[index], selected)
cmp := 1
if best := w.bestFit.RuleFits[index]; best != nil {
cmp = compareRuleFit(rf, best)
}
switch cmp {
case 1:
w.bestFit.RuleFits[index] = rf
// Reset previous result after position index.
for i := index + 1; i < len(w.rules); i++ {
w.bestFit.RuleFits[i] = nil
}
w.fitRule(index + 1)
w.updateOrphanPeers(index + 1)
return true
case 0:
if w.fitRule(index + 1) {
w.bestFit.RuleFits[index] = rf
return true
}
}
return false
}
// determine the orphanPeers list based on fitPeer.selected flag.
func (w *fitWorker) updateOrphanPeers(index int) {
if index != len(w.rules) {
return
}
w.bestFit.OrphanPeers = w.bestFit.OrphanPeers[:0]
for _, p := range w.peers {
if !p.selected {
w.bestFit.OrphanPeers = append(w.bestFit.OrphanPeers, p.Replica)
}
}
}
func newRuleFit(rule *Rule, peers []*fitPeer) *RuleFit {
rf := &RuleFit{Rule: rule, IsolationScore: isolationScore(peers, rule.LocationLabels)}
for _, p := range peers {
rf.Peers = append(rf.Peers, p.Replica)
if !p.matchRoleStrict(rule.Role) {
rf.PeersWithDifferentRole = append(rf.PeersWithDifferentRole, p.Replica)
}
}
return rf
}
type fitPeer struct {
metapb.Replica
container *core.CachedContainer
isLeader bool
selected bool
}
func (p *fitPeer) matchRoleStrict(role ReplicaRoleType) bool {
switch role {
case Voter: // Voter matches either Leader or Follower.
return !metadata.IsLearner(p.Replica)
case Leader:
return p.isLeader
case Follower:
return !metadata.IsLearner(p.Replica) && !p.isLeader
case Learner:
return metadata.IsLearner(p.Replica)
}
return false
}
func (p *fitPeer) matchRoleLoose(role ReplicaRoleType) bool {
// non-learner cannot become learner. All other roles can migrate to
// others by scheduling. For example, Leader->Follower, Learner->Leader
// are possible, but Voter->Learner is impossible.
return role != Learner || metadata.IsLearner(p.Replica)
}
func isolationScore(peers []*fitPeer, labels []string) float64 {
var score float64
if len(labels) == 0 || len(peers) <= 1 {
return 0
}
// NOTE: following loop is partially duplicated with `core.DistinctScore`.
// The reason not to call it directly is that core.DistinctScore only
// accepts `[]CachedContainer` not `[]*fitPeer` and I don't want alloc slice
// here because it is kind of hot path.
// After Go supports generics, we will be enable to do some refactor and
// reuse `core.DistinctScore`.
const replicaBaseScore = 100
for i, p1 := range peers {
for _, p2 := range peers[i+1:] {
if index := p1.container.CompareLocation(p2.container, labels); index != -1 {
score += math.Pow(replicaBaseScore, float64(len(labels)-index-1))
}
}
}
return score
}