| 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 |
} |