-
Notifications
You must be signed in to change notification settings - Fork 168
/
selection_algorithm.go
137 lines (114 loc) · 3.98 KB
/
selection_algorithm.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
package server
import (
"math"
"math/big"
"math/rand"
"time"
ethcommon "github.com/ethereum/go-ethereum/common"
"github.com/golang/glog"
)
var random = rand.New(rand.NewSource(time.Now().UnixNano()))
type ProbabilitySelectionAlgorithm struct {
MinPerfScore float64
StakeWeight float64
PriceWeight float64
RandWeight float64
PriceExpFactor float64
}
func (sa ProbabilitySelectionAlgorithm) Select(addrs []ethcommon.Address, stakes map[ethcommon.Address]int64, maxPrice *big.Rat, prices map[ethcommon.Address]*big.Rat, perfScores map[ethcommon.Address]float64) ethcommon.Address {
filtered := sa.filter(addrs, maxPrice, prices, perfScores)
probabilities := sa.calculateProbabilities(filtered, stakes, prices)
return selectBy(probabilities)
}
func (sa ProbabilitySelectionAlgorithm) filter(addrs []ethcommon.Address, maxPrice *big.Rat, prices map[ethcommon.Address]*big.Rat, perfScores map[ethcommon.Address]float64) []ethcommon.Address {
filteredByPerfScore := sa.filterByPerfScore(addrs, perfScores)
return sa.filterByMaxPrice(filteredByPerfScore, maxPrice, prices)
}
func (sa ProbabilitySelectionAlgorithm) filterByPerfScore(addrs []ethcommon.Address, scores map[ethcommon.Address]float64) []ethcommon.Address {
if sa.MinPerfScore <= 0 || len(scores) == 0 {
// Performance Score filter not defined, return all Orchestrators
return addrs
}
var res []ethcommon.Address
for _, addr := range addrs {
if scores[addr] >= sa.MinPerfScore {
res = append(res, addr)
}
}
if len(res) == 0 {
// If no orchestrators pass the perf filter, return all Orchestrators.
// That may mean some issues with the PerfScore service.
glog.Warning("No Orchestrators passed min performance score filter, not using the filter")
return addrs
}
return res
}
func (sa ProbabilitySelectionAlgorithm) filterByMaxPrice(addrs []ethcommon.Address, maxPrice *big.Rat, prices map[ethcommon.Address]*big.Rat) []ethcommon.Address {
if maxPrice == nil || len(prices) == 0 {
// Max price filter not defined, return all Orchestrators
return addrs
}
var res []ethcommon.Address
for _, addr := range addrs {
price := prices[addr]
if price != nil && price.Cmp(maxPrice) <= 0 {
res = append(res, addr)
}
}
if len(res) == 0 {
// If no orchestrators pass the filter, return all Orchestrators
// It means that no orchestrators are below the max price
glog.Warning("No Orchestrators passed max price filter, not using the filter")
return addrs
}
return res
}
func (sa ProbabilitySelectionAlgorithm) calculateProbabilities(addrs []ethcommon.Address, stakes map[ethcommon.Address]int64, prices map[ethcommon.Address]*big.Rat) map[ethcommon.Address]float64 {
pricesNorm := map[ethcommon.Address]float64{}
for _, addr := range addrs {
p, _ := prices[addr].Float64()
pricesNorm[addr] = math.Exp(-1 * p / sa.PriceExpFactor)
}
var priceSum, stakeSum float64
for _, addr := range addrs {
priceSum += pricesNorm[addr]
stakeSum += float64(stakes[addr])
}
probs := map[ethcommon.Address]float64{}
for _, addr := range addrs {
priceProb := 1.0
if priceSum != 0 {
priceProb = pricesNorm[addr] / priceSum
}
stakeProb := 1.0
if stakeSum != 0 {
stakeProb = float64(stakes[addr]) / stakeSum
}
randProb := 1.0 / float64(len(addrs))
probs[addr] = sa.PriceWeight*priceProb + sa.StakeWeight*stakeProb + sa.RandWeight*randProb
}
return probs
}
func selectBy(probabilities map[ethcommon.Address]float64) ethcommon.Address {
if len(probabilities) == 0 {
return ethcommon.Address{}
}
var addrs []ethcommon.Address
var cumProbs []float64
var cumProb float64
for addr, prob := range probabilities {
addrs = append(addrs, addr)
cumProb += prob
cumProbs = append(cumProbs, cumProb)
}
r := random.Float64()
for i, cumProb := range cumProbs {
if r <= cumProb {
return addrs[i]
}
}
// return any Orchestrator is none was found with the probabilities
// should not happen, but just to be on the safe side if we encounter some super corner case with the float
// number precision
return addrs[0]
}