Debian Codegraph @

pkg/util/shufflesharding/shufflesharding.go

raw
1 /*
2 Copyright 2019 The Kubernetes Authors.
3
4 Licensed under the Apache License, Version 2.0 (the "License");
5 you may not use this file except in compliance with the License.
6 You may obtain a copy of the License at
7
8 http://www.apache.org/licenses/LICENSE-2.0
9
10 Unless required by applicable law or agreed to in writing, software
11 distributed under the License is distributed on an "AS IS" BASIS,
12 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 See the License for the specific language governing permissions and
14 limitations under the License.
15 */
16
17 package shufflesharding
18
19 import (
20 "fmt"
21 "math"
22 )
23
24 // MaxHashBits is the max bit length which can be used from hash value.
25 // If we use all bits of hash value, the critical(last) card shuffled by
26 // Dealer will be uneven to 2:3 (first half:second half) at most,
27 // in order to reduce this unevenness to 32:33, we set MaxHashBits to 60 here.
28 const MaxHashBits = 60
29
30 // RequiredEntropyBits makes a quick and slightly conservative estimate of the number
31 // of bits of hash value that are consumed in shuffle sharding a deck of the given size
32 // to a hand of the given size. The result is meaningful only if
33 // 1 <= handSize <= deckSize <= 1<<26.
34 func RequiredEntropyBits(deckSize, handSize int) int {
35 return int(math.Ceil(math.Log2(float64(deckSize)) * float64(handSize)))
36 }
37
38 // Dealer contains some necessary parameters and provides some methods for shuffle sharding.
39 // Dealer is thread-safe.
40 type Dealer struct {
41 deckSize int
42 handSize int
43 }
44
45 // NewDealer will create a Dealer with the given deckSize and handSize, will return error when
46 // deckSize or handSize is invalid as below.
47 // 1. deckSize or handSize is not positive
48 // 2. handSize is greater than deckSize
49 // 3. deckSize is impractically large (greater than 1<<26)
50 // 4. required entropy bits of deckSize and handSize is greater than MaxHashBits
51 func NewDealer(deckSize, handSize int) (*Dealer, error) {
52 if deckSize <= 0 || handSize <= 0 {
53 return nil, fmt.Errorf("deckSize %d or handSize %d is not positive", deckSize, handSize)
54 }
55 if handSize > deckSize {
56 return nil, fmt.Errorf("handSize %d is greater than deckSize %d", handSize, deckSize)
57 }
58 if deckSize > 1<<26 {
59 return nil, fmt.Errorf("deckSize %d is impractically large", deckSize)
60 }
61 if RequiredEntropyBits(deckSize, handSize) > MaxHashBits {
62 return nil, fmt.Errorf("required entropy bits of deckSize %d and handSize %d is greater than %d", deckSize, handSize, MaxHashBits)
63 }
64
65 return &Dealer{
66 deckSize: deckSize,
67 handSize: handSize,
68 }, nil
69 }
70
71 // Deal shuffles a card deck and deals a hand of cards, using the given hashValue as the source of entropy.
72 // The deck size and hand size are properties of the Dealer.
73 // This function synchronously makes sequential calls to pick, one for each dealt card.
74 // Each card is identified by an integer in the range [0, deckSize).
75 // For example, for deckSize=128 and handSize=4 this function might call pick(14); pick(73); pick(119); pick(26).
76 func (d *Dealer) Deal(hashValue uint64, pick func(int)) {
77 // 15 is the largest possible value of handSize
78 var remainders [15]int
79
80 for i := 0; i < d.handSize; i++ {
81 hashValueNext := hashValue / uint64(d.deckSize-i)
82 remainders[i] = int(hashValue - uint64(d.deckSize-i)*hashValueNext)
83 hashValue = hashValueNext
84 }
85
86 for i := 0; i < d.handSize; i++ {
87 card := remainders[i]
88 for j := i; j > 0; j-- {
89 if card >= remainders[j-1] {
90 card++
91 }
92 }
93 pick(card)
94 }
95 }
96
97 // DealIntoHand shuffles and deals according to the Dealer's parameters,
98 // using the given hashValue as the source of entropy and then
99 // returns the dealt cards as a slice of `int`.
100 // If `hand` has the correct length as Dealer's handSize, it will be used as-is and no allocations will be made.
101 // If `hand` is nil or too small, it will be extended (performing an allocation).
102 // If `hand` is too large, a sub-slice will be returned.
103 func (d *Dealer) DealIntoHand(hashValue uint64, hand []int) []int {
104 h := hand[:0]
105 d.Deal(hashValue, func(card int) { h = append(h, card) })
106 return h
107 }