-
Notifications
You must be signed in to change notification settings - Fork 199
/
requestbasket.go
285 lines (263 loc) · 9.35 KB
/
requestbasket.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
// Copyright 2020 The go-ethereum Authors
// This file is part of the go-ethereum library.
//
// The go-ethereum library is free software: you can redistribute it and/or modify
// it under the terms of the GNU Lesser General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// The go-ethereum library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU Lesser General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public License
// along with the go-ethereum library. If not, see <http://www.gnu.org/licenses/>.
package client
import (
"io"
"github.com/celo-org/celo-blockchain/les/utils"
"github.com/celo-org/celo-blockchain/rlp"
)
const basketFactor = 1000000 // reference basket amount and value scale factor
// referenceBasket keeps track of global request usage statistics and the usual prices
// of each used request type relative to each other. The amounts in the basket are scaled
// up by basketFactor because of the exponential expiration of long-term statistical data.
// Values are scaled so that the sum of all amounts and the sum of all values are equal.
//
// reqValues represent the internal relative value estimates for each request type and are
// calculated as value / amount. The average reqValue of all used requests is 1.
// In other words: SUM(refBasket[type].amount * reqValue[type]) = SUM(refBasket[type].amount)
type referenceBasket struct {
basket requestBasket
reqValues []float64 // contents are read only, new slice is created for each update
}
// serverBasket collects served request amount and value statistics for a single server.
//
// Values are gradually transferred to the global reference basket with a long time
// constant so that each server basket represents long term usage and price statistics.
// When the transferred part is added to the reference basket the values are scaled so
// that their sum equals the total value calculated according to the previous reqValues.
// The ratio of request values coming from the server basket represent the pricing of
// the specific server and modify the global estimates with a weight proportional to
// the amount of service provided by the server.
type serverBasket struct {
basket requestBasket
rvFactor float64
}
type (
// requestBasket holds amounts and values for each request type.
// These values are exponentially expired (see utils.ExpiredValue). The power of 2
// exponent is applicable to all values within.
requestBasket struct {
items []basketItem
exp uint64
}
// basketItem holds amount and value for a single request type. Value is the total
// relative request value accumulated for served requests while amount is the counter
// for each request type.
// Note that these values are both scaled up by basketFactor because of the exponential
// expiration.
basketItem struct {
amount, value uint64
}
)
// setExp sets the power of 2 exponent of the structure, scaling base values (the amounts
// and request values) up or down if necessary.
func (b *requestBasket) setExp(exp uint64) {
if exp > b.exp {
shift := exp - b.exp
for i, item := range b.items {
item.amount >>= shift
item.value >>= shift
b.items[i] = item
}
b.exp = exp
}
if exp < b.exp {
shift := b.exp - exp
for i, item := range b.items {
item.amount <<= shift
item.value <<= shift
b.items[i] = item
}
b.exp = exp
}
}
// init initializes a new server basket with the given service vector size (number of
// different request types)
func (s *serverBasket) init(size int) {
if s.basket.items == nil {
s.basket.items = make([]basketItem, size)
}
}
// add adds the give type and amount of requests to the basket. Cost is calculated
// according to the server's own cost table.
func (s *serverBasket) add(reqType, reqAmount uint32, reqCost uint64, expFactor utils.ExpirationFactor) {
s.basket.setExp(expFactor.Exp)
i := &s.basket.items[reqType]
i.amount += uint64(float64(uint64(reqAmount)*basketFactor) * expFactor.Factor)
i.value += uint64(float64(reqCost) * s.rvFactor * expFactor.Factor)
}
// updateRvFactor updates the request value factor that scales server costs into the
// local value dimensions.
func (s *serverBasket) updateRvFactor(rvFactor float64) {
s.rvFactor = rvFactor
}
// transfer decreases amounts and values in the basket with the given ratio and
// moves the removed amounts into a new basket which is returned and can be added
// to the global reference basket.
func (s *serverBasket) transfer(ratio float64) requestBasket {
res := requestBasket{
items: make([]basketItem, len(s.basket.items)),
exp: s.basket.exp,
}
for i, v := range s.basket.items {
ta := uint64(float64(v.amount) * ratio)
tv := uint64(float64(v.value) * ratio)
if ta > v.amount {
ta = v.amount
}
if tv > v.value {
tv = v.value
}
s.basket.items[i] = basketItem{v.amount - ta, v.value - tv}
res.items[i] = basketItem{ta, tv}
}
return res
}
// init initializes the reference basket with the given service vector size (number of
// different request types)
func (r *referenceBasket) init(size int) {
r.reqValues = make([]float64, size)
r.normalize()
r.updateReqValues()
}
// add adds the transferred part of a server basket to the reference basket while scaling
// value amounts so that their sum equals the total value calculated according to the
// previous reqValues.
func (r *referenceBasket) add(newBasket requestBasket) {
r.basket.setExp(newBasket.exp)
// scale newBasket to match service unit value
var (
totalCost uint64
totalValue float64
)
for i, v := range newBasket.items {
totalCost += v.value
totalValue += float64(v.amount) * r.reqValues[i]
}
if totalCost > 0 {
// add to reference with scaled values
scaleValues := totalValue / float64(totalCost)
for i, v := range newBasket.items {
r.basket.items[i].amount += v.amount
r.basket.items[i].value += uint64(float64(v.value) * scaleValues)
}
}
r.updateReqValues()
}
// updateReqValues recalculates reqValues after adding transferred baskets. Note that
// values should be normalized first.
func (r *referenceBasket) updateReqValues() {
r.reqValues = make([]float64, len(r.reqValues))
for i, b := range r.basket.items {
if b.amount > 0 {
r.reqValues[i] = float64(b.value) / float64(b.amount)
} else {
r.reqValues[i] = 0
}
}
}
// normalize ensures that the sum of values equal the sum of amounts in the basket.
func (r *referenceBasket) normalize() {
var sumAmount, sumValue uint64
for _, b := range r.basket.items {
sumAmount += b.amount
sumValue += b.value
}
add := float64(int64(sumAmount-sumValue)) / float64(sumValue)
for i, b := range r.basket.items {
b.value += uint64(int64(float64(b.value) * add))
r.basket.items[i] = b
}
}
// reqValueFactor calculates the request value factor applicable to the server with
// the given announced request cost list
func (r *referenceBasket) reqValueFactor(costList []uint64) float64 {
var (
totalCost float64
totalValue uint64
)
for i, b := range r.basket.items {
totalCost += float64(costList[i]) * float64(b.amount) // use floats to avoid overflow
totalValue += b.value
}
if totalCost < 1 {
return 0
}
return float64(totalValue) * basketFactor / totalCost
}
// EncodeRLP implements rlp.Encoder
func (b *basketItem) EncodeRLP(w io.Writer) error {
return rlp.Encode(w, []interface{}{b.amount, b.value})
}
// DecodeRLP implements rlp.Decoder
func (b *basketItem) DecodeRLP(s *rlp.Stream) error {
var item struct {
Amount, Value uint64
}
if err := s.Decode(&item); err != nil {
return err
}
b.amount, b.value = item.Amount, item.Value
return nil
}
// EncodeRLP implements rlp.Encoder
func (r *requestBasket) EncodeRLP(w io.Writer) error {
return rlp.Encode(w, []interface{}{r.items, r.exp})
}
// DecodeRLP implements rlp.Decoder
func (r *requestBasket) DecodeRLP(s *rlp.Stream) error {
var enc struct {
Items []basketItem
Exp uint64
}
if err := s.Decode(&enc); err != nil {
return err
}
r.items, r.exp = enc.Items, enc.Exp
return nil
}
// convertMapping converts a basket loaded from the database into the current format.
// If the available request types and their mapping into the service vector differ from
// the one used when saving the basket then this function reorders old fields and fills
// in previously unknown fields by scaling up amounts and values taken from the
// initialization basket.
func (r requestBasket) convertMapping(oldMapping, newMapping []string, initBasket requestBasket) requestBasket {
nameMap := make(map[string]int)
for i, name := range oldMapping {
nameMap[name] = i
}
rc := requestBasket{items: make([]basketItem, len(newMapping))}
var scale, oldScale, newScale float64
for i, name := range newMapping {
if ii, ok := nameMap[name]; ok {
rc.items[i] = r.items[ii]
oldScale += float64(initBasket.items[i].amount) * float64(initBasket.items[i].amount)
newScale += float64(rc.items[i].amount) * float64(initBasket.items[i].amount)
}
}
if oldScale > 1e-10 {
scale = newScale / oldScale
} else {
scale = 1
}
for i, name := range newMapping {
if _, ok := nameMap[name]; !ok {
rc.items[i].amount = uint64(float64(initBasket.items[i].amount) * scale)
rc.items[i].value = uint64(float64(initBasket.items[i].value) * scale)
}
}
return rc
}