1 /* 2 * 3 * Copyright 2022 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 package clusterresolver 19 20 import ( 21 "fmt" 22 23 "google.golang.org/grpc/xds/internal" 24 "google.golang.org/grpc/xds/internal/xdsclient/xdsresource" 25 ) 26 27 // nameGenerator generates a child name for a list of priorities (each priority 28 // is a list of localities). 29 // 30 // The purpose of this generator is to reuse names between updates. So the 31 // struct keeps state between generate() calls, and a later generate() might 32 // return names returned by the previous call. 33 type nameGenerator struct { 34 existingNames map[internal.LocalityID]string 35 prefix uint64 36 nextID uint64 37 } 38 39 func newNameGenerator(prefix uint64) *nameGenerator { 40 return &nameGenerator{prefix: prefix} 41 } 42 43 // generate returns a list of names for the given list of priorities. 44 // 45 // Each priority is a list of localities. The name for the priority is picked as 46 // - for each locality in this priority, if it exists in the existing names, 47 // this priority will reuse the name 48 // - if no reusable name is found for this priority, a new name is generated 49 // 50 // For example: 51 // - update 1: [[L1], [L2], [L3]] --> ["0", "1", "2"] 52 // - update 2: [[L1], [L2], [L3]] --> ["0", "1", "2"] 53 // - update 3: [[L1, L2], [L3]] --> ["0", "2"] (Two priorities were merged) 54 // - update 4: [[L1], [L4]] --> ["0", "3",] (A priority was split, and a new priority was added) 55 func (ng *nameGenerator) generate(priorities [][]xdsresource.Locality) []string { 56 var ret []string 57 usedNames := make(map[string]bool) 58 newNames := make(map[internal.LocalityID]string) 59 for _, priority := range priorities { 60 var nameFound string 61 for _, locality := range priority { 62 if name, ok := ng.existingNames[locality.ID]; ok { 63 if !usedNames[name] { 64 nameFound = name 65 // Found a name to use. No need to process the remaining 66 // localities. 67 break 68 } 69 } 70 } 71 72 if nameFound == "" { 73 // No appropriate used name is found. Make a new name. 74 nameFound = fmt.Sprintf("priority-%d-%d", ng.prefix, ng.nextID) 75 ng.nextID++ 76 } 77 78 ret = append(ret, nameFound) 79 // All localities in this priority share the same name. Add them all to 80 // the new map. 81 for _, l := range priority { 82 newNames[l.ID] = nameFound 83 } 84 usedNames[nameFound] = true 85 } 86 ng.existingNames = newNames 87 return ret 88 } 89