1 /* 2 * 3 * Copyright 2021 gRPC authors. 4 * 5 * Licensed under the Apache License, Version 2.0 (the "License"); 6 * you may not use this file except in compliance with the License. 7 * You may obtain a copy of the License at 8 * 9 * http://www.apache.org/licenses/LICENSE-2.0 10 * 11 * Unless required by applicable law or agreed to in writing, software 12 * distributed under the License is distributed on an "AS IS" BASIS, 13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 * See the License for the specific language governing permissions and 15 * limitations under the License. 16 * 17 */ 18 19 package ringhash 20 21 import ( 22 "math" 23 "sort" 24 "strconv" 25 26 xxhash "github.com/cespare/xxhash/v2" 27 "google.golang.org/grpc/internal/grpclog" 28 "google.golang.org/grpc/resolver" 29 ) 30 31 type ring struct { 32 items []*ringEntry 33 } 34 35 type subConnWithWeight struct { 36 sc *subConn 37 weight float64 38 } 39 40 type ringEntry struct { 41 idx int 42 hash uint64 43 sc *subConn 44 } 45 46 // newRing creates a ring from the subConns stored in the AddressMap. The ring 47 // size is limited by the passed in max/min. 48 // 49 // ring entries will be created for each subConn, and subConn with high weight 50 // (specified by the address) may have multiple entries. 51 // 52 // For example, for subConns with weights {a:3, b:3, c:4}, a generated ring of 53 // size 10 could be: 54 // - {idx:0 hash:3689675255460411075 b} 55 // - {idx:1 hash:4262906501694543955 c} 56 // - {idx:2 hash:5712155492001633497 c} 57 // - {idx:3 hash:8050519350657643659 b} 58 // - {idx:4 hash:8723022065838381142 b} 59 // - {idx:5 hash:11532782514799973195 a} 60 // - {idx:6 hash:13157034721563383607 c} 61 // - {idx:7 hash:14468677667651225770 c} 62 // - {idx:8 hash:17336016884672388720 a} 63 // - {idx:9 hash:18151002094784932496 a} 64 // 65 // To pick from a ring, a binary search will be done for the given target hash, 66 // and first item with hash >= given hash will be returned. 67 // 68 // Must be called with a non-empty subConns map. 69 func newRing(subConns *resolver.AddressMap, minRingSize, maxRingSize uint64, logger *grpclog.PrefixLogger) *ring { 70 logger.Debugf("newRing: number of subConns is %d, minRingSize is %d, maxRingSize is %d", subConns.Len(), minRingSize, maxRingSize) 71 72 // https://github.com/envoyproxy/envoy/blob/765c970f06a4c962961a0e03a467e165b276d50f/source/common/upstream/ring_hash_lb.cc#L114 73 normalizedWeights, minWeight := normalizeWeights(subConns) 74 logger.Debugf("newRing: normalized subConn weights is %v", normalizedWeights) 75 76 // Normalized weights for {3,3,4} is {0.3,0.3,0.4}. 77 78 // Scale up the size of the ring such that the least-weighted host gets a 79 // whole number of hashes on the ring. 80 // 81 // Note that size is limited by the input max/min. 82 scale := math.Min(math.Ceil(minWeight*float64(minRingSize))/minWeight, float64(maxRingSize)) 83 ringSize := math.Ceil(scale) 84 items := make([]*ringEntry, 0, int(ringSize)) 85 logger.Debugf("newRing: creating new ring of size %v", ringSize) 86 87 // For each entry, scale*weight nodes are generated in the ring. 88 // 89 // Not all of these are whole numbers. E.g. for weights {a:3,b:3,c:4}, if 90 // ring size is 7, scale is 6.66. The numbers of nodes will be 91 // {a,a,b,b,c,c,c}. 92 // 93 // A hash is generated for each item, and later the results will be sorted 94 // based on the hash. 95 var currentHashes, targetHashes float64 96 for _, scw := range normalizedWeights { 97 targetHashes += scale * scw.weight 98 // This index ensures that ring entries corresponding to the same 99 // address hash to different values. And since this index is 100 // per-address, these entries hash to the same value across address 101 // updates. 102 idx := 0 103 for currentHashes < targetHashes { 104 h := xxhash.Sum64String(scw.sc.addr + "_" + strconv.Itoa(idx)) 105 items = append(items, &ringEntry{hash: h, sc: scw.sc}) 106 idx++ 107 currentHashes++ 108 } 109 } 110 111 // Sort items based on hash, to prepare for binary search. 112 sort.Slice(items, func(i, j int) bool { return items[i].hash < items[j].hash }) 113 for i, ii := range items { 114 ii.idx = i 115 } 116 return &ring{items: items} 117 } 118 119 // normalizeWeights divides all the weights by the sum, so that the total weight 120 // is 1. 121 // 122 // Must be called with a non-empty subConns map. 123 func normalizeWeights(subConns *resolver.AddressMap) ([]subConnWithWeight, float64) { 124 var weightSum uint32 125 keys := subConns.Keys() 126 for _, a := range keys { 127 weightSum += getWeightAttribute(a) 128 } 129 ret := make([]subConnWithWeight, 0, len(keys)) 130 min := float64(1.0) 131 for _, a := range keys { 132 v, _ := subConns.Get(a) 133 scInfo := v.(*subConn) 134 // getWeightAttribute() returns 1 if the weight attribute is not found 135 // on the address. And since this function is guaranteed to be called 136 // with a non-empty subConns map, weightSum is guaranteed to be 137 // non-zero. So, we need not worry about divide a by zero error here. 138 nw := float64(getWeightAttribute(a)) / float64(weightSum) 139 ret = append(ret, subConnWithWeight{sc: scInfo, weight: nw}) 140 if nw < min { 141 min = nw 142 } 143 } 144 // Sort the addresses to return consistent results. 145 // 146 // Note: this might not be necessary, but this makes sure the ring is 147 // consistent as long as the addresses are the same, for example, in cases 148 // where an address is added and then removed, the RPCs will still pick the 149 // same old SubConn. 150 sort.Slice(ret, func(i, j int) bool { return ret[i].sc.addr < ret[j].sc.addr }) 151 return ret, min 152 } 153 154 // pick does a binary search. It returns the item with smallest index i that 155 // r.items[i].hash >= h. 156 func (r *ring) pick(h uint64) *ringEntry { 157 i := sort.Search(len(r.items), func(i int) bool { return r.items[i].hash >= h }) 158 if i == len(r.items) { 159 // If not found, and h is greater than the largest hash, return the 160 // first item. 161 i = 0 162 } 163 return r.items[i] 164 } 165 166 // next returns the next entry. 167 func (r *ring) next(e *ringEntry) *ringEntry { 168 return r.items[(e.idx+1)%len(r.items)] 169 } 170