builder.go

Documentation: google.golang.org/grpc/balancer/rls/internal/keys

     1  /*
     2   *
     3   * Copyright 2020 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 keys provides functionality required to build RLS request keys.
    20  package keys
    21  
    22  import (
    23  	"errors"
    24  	"fmt"
    25  	"sort"
    26  	"strings"
    27  
    28  	rlspb "google.golang.org/grpc/internal/proto/grpc_lookup_v1"
    29  	"google.golang.org/grpc/metadata"
    30  )
    31  
    32  // BuilderMap maps from request path to the key builder for that path.
    33  type BuilderMap map[string]builder
    34  
    35  // MakeBuilderMap parses the provided RouteLookupConfig proto and returns a map
    36  // from paths to key builders.
    37  func MakeBuilderMap(cfg *rlspb.RouteLookupConfig) (BuilderMap, error) {
    38  	kbs := cfg.GetGrpcKeybuilders()
    39  	if len(kbs) == 0 {
    40  		return nil, errors.New("rls: RouteLookupConfig does not contain any GrpcKeyBuilder")
    41  	}
    42  
    43  	bm := make(map[string]builder)
    44  	for _, kb := range kbs {
    45  		// Extract keys from `headers`, `constant_keys` and `extra_keys` fields
    46  		// and populate appropriate values in the builder struct. Also ensure
    47  		// that keys are not repeated.
    48  		var matchers []matcher
    49  		seenKeys := make(map[string]bool)
    50  		constantKeys := kb.GetConstantKeys()
    51  		for k := range kb.GetConstantKeys() {
    52  			seenKeys[k] = true
    53  		}
    54  		for _, h := range kb.GetHeaders() {
    55  			if h.GetRequiredMatch() {
    56  				return nil, fmt.Errorf("rls: GrpcKeyBuilder in RouteLookupConfig has required_match field set {%+v}", kbs)
    57  			}
    58  			key := h.GetKey()
    59  			if seenKeys[key] {
    60  				return nil, fmt.Errorf("rls: GrpcKeyBuilder in RouteLookupConfig contains repeated key %q across headers, constant_keys and extra_keys {%+v}", key, kbs)
    61  			}
    62  			seenKeys[key] = true
    63  			matchers = append(matchers, matcher{key: h.GetKey(), names: h.GetNames()})
    64  		}
    65  		if seenKeys[kb.GetExtraKeys().GetHost()] {
    66  			return nil, fmt.Errorf("rls: GrpcKeyBuilder in RouteLookupConfig contains repeated key %q in extra_keys from constant_keys or headers {%+v}", kb.GetExtraKeys().GetHost(), kbs)
    67  		}
    68  		if seenKeys[kb.GetExtraKeys().GetService()] {
    69  			return nil, fmt.Errorf("rls: GrpcKeyBuilder in RouteLookupConfig contains repeated key %q in extra_keys from constant_keys or headers {%+v}", kb.GetExtraKeys().GetService(), kbs)
    70  		}
    71  		if seenKeys[kb.GetExtraKeys().GetMethod()] {
    72  			return nil, fmt.Errorf("rls: GrpcKeyBuilder in RouteLookupConfig contains repeated key %q in extra_keys from constant_keys or headers {%+v}", kb.GetExtraKeys().GetMethod(), kbs)
    73  		}
    74  		b := builder{
    75  			headerKeys:   matchers,
    76  			constantKeys: constantKeys,
    77  			hostKey:      kb.GetExtraKeys().GetHost(),
    78  			serviceKey:   kb.GetExtraKeys().GetService(),
    79  			methodKey:    kb.GetExtraKeys().GetMethod(),
    80  		}
    81  
    82  		// Store the builder created above in the BuilderMap based on the value
    83  		// of the `Names` field, which wraps incoming request's service and
    84  		// method. Also, ensure that there are no repeated `Names` field.
    85  		names := kb.GetNames()
    86  		if len(names) == 0 {
    87  			return nil, fmt.Errorf("rls: GrpcKeyBuilder in RouteLookupConfig does not contain any Name {%+v}", kbs)
    88  		}
    89  		for _, name := range names {
    90  			if name.GetService() == "" {
    91  				return nil, fmt.Errorf("rls: GrpcKeyBuilder in RouteLookupConfig contains a Name field with no Service {%+v}", kbs)
    92  			}
    93  			if strings.Contains(name.GetMethod(), `/`) {
    94  				return nil, fmt.Errorf("rls: GrpcKeyBuilder in RouteLookupConfig contains a method with a slash {%+v}", kbs)
    95  			}
    96  			path := "/" + name.GetService() + "/" + name.GetMethod()
    97  			if _, ok := bm[path]; ok {
    98  				return nil, fmt.Errorf("rls: GrpcKeyBuilder in RouteLookupConfig contains repeated Name field {%+v}", kbs)
    99  			}
   100  			bm[path] = b
   101  		}
   102  	}
   103  	return bm, nil
   104  }
   105  
   106  // KeyMap represents the RLS keys to be used for a request.
   107  type KeyMap struct {
   108  	// Map is the representation of an RLS key as a Go map. This is used when
   109  	// an actual RLS request is to be sent out on the wire, since the
   110  	// RouteLookupRequest proto expects a Go map.
   111  	Map map[string]string
   112  	// Str is the representation of an RLS key as a string, sorted by keys.
   113  	// Since the RLS keys are part of the cache key in the request cache
   114  	// maintained by the RLS balancer, and Go maps cannot be used as keys for
   115  	// Go maps (the cache is implemented as a map), we need a stringified
   116  	// version of it.
   117  	Str string
   118  }
   119  
   120  // RLSKey builds the RLS keys to be used for the given request, identified by
   121  // the request path and the request headers stored in metadata.
   122  func (bm BuilderMap) RLSKey(md metadata.MD, host, path string) KeyMap {
   123  	// The path passed in is of the form "/service/method". The keyBuilderMap is
   124  	// indexed with keys of the form "/service/" or "/service/method". The service
   125  	// that we set in the keyMap (to be sent out in the RLS request) should not
   126  	// include any slashes though.
   127  	i := strings.LastIndex(path, "/")
   128  	service, method := path[:i+1], path[i+1:]
   129  	b, ok := bm[path]
   130  	if !ok {
   131  		b, ok = bm[service]
   132  		if !ok {
   133  			return KeyMap{}
   134  		}
   135  	}
   136  
   137  	kvMap := b.buildHeaderKeys(md)
   138  	if b.hostKey != "" {
   139  		kvMap[b.hostKey] = host
   140  	}
   141  	if b.serviceKey != "" {
   142  		kvMap[b.serviceKey] = strings.Trim(service, "/")
   143  	}
   144  	if b.methodKey != "" {
   145  		kvMap[b.methodKey] = method
   146  	}
   147  	for k, v := range b.constantKeys {
   148  		kvMap[k] = v
   149  	}
   150  	return KeyMap{Map: kvMap, Str: mapToString(kvMap)}
   151  }
   152  
   153  // Equal reports whether bm and am represent equivalent BuilderMaps.
   154  func (bm BuilderMap) Equal(am BuilderMap) bool {
   155  	if (bm == nil) != (am == nil) {
   156  		return false
   157  	}
   158  	if len(bm) != len(am) {
   159  		return false
   160  	}
   161  
   162  	for key, bBuilder := range bm {
   163  		aBuilder, ok := am[key]
   164  		if !ok {
   165  			return false
   166  		}
   167  		if !bBuilder.Equal(aBuilder) {
   168  			return false
   169  		}
   170  	}
   171  	return true
   172  }
   173  
   174  // builder provides the actual functionality of building RLS keys.
   175  type builder struct {
   176  	headerKeys   []matcher
   177  	constantKeys map[string]string
   178  	// The following keys mirror corresponding fields in `extra_keys`.
   179  	hostKey    string
   180  	serviceKey string
   181  	methodKey  string
   182  }
   183  
   184  // Equal reports whether b and a represent equivalent key builders.
   185  func (b builder) Equal(a builder) bool {
   186  	if len(b.headerKeys) != len(a.headerKeys) {
   187  		return false
   188  	}
   189  	// Protobuf serialization maintains the order of repeated fields. Matchers
   190  	// are specified as a repeated field inside the KeyBuilder proto. If the
   191  	// order changes, it means that the order in the protobuf changed. We report
   192  	// this case as not being equal even though the builders could possible be
   193  	// functionally equal.
   194  	for i, bMatcher := range b.headerKeys {
   195  		aMatcher := a.headerKeys[i]
   196  		if !bMatcher.Equal(aMatcher) {
   197  			return false
   198  		}
   199  	}
   200  
   201  	if len(b.constantKeys) != len(a.constantKeys) {
   202  		return false
   203  	}
   204  	for k, v := range b.constantKeys {
   205  		if a.constantKeys[k] != v {
   206  			return false
   207  		}
   208  	}
   209  
   210  	return b.hostKey == a.hostKey && b.serviceKey == a.serviceKey && b.methodKey == a.methodKey
   211  }
   212  
   213  // matcher helps extract a key from request headers based on a given name.
   214  type matcher struct {
   215  	// The key used in the keyMap sent as part of the RLS request.
   216  	key string
   217  	// List of header names which can supply the value for this key.
   218  	names []string
   219  }
   220  
   221  // Equal reports if m and are are equivalent headerKeys.
   222  func (m matcher) Equal(a matcher) bool {
   223  	if m.key != a.key {
   224  		return false
   225  	}
   226  	if len(m.names) != len(a.names) {
   227  		return false
   228  	}
   229  	for i := 0; i < len(m.names); i++ {
   230  		if m.names[i] != a.names[i] {
   231  			return false
   232  		}
   233  	}
   234  	return true
   235  }
   236  
   237  func (b builder) buildHeaderKeys(md metadata.MD) map[string]string {
   238  	kvMap := make(map[string]string)
   239  	if len(md) == 0 {
   240  		return kvMap
   241  	}
   242  	for _, m := range b.headerKeys {
   243  		for _, name := range m.names {
   244  			if vals := md.Get(name); vals != nil {
   245  				kvMap[m.key] = strings.Join(vals, ",")
   246  				break
   247  			}
   248  		}
   249  	}
   250  	return kvMap
   251  }
   252  
   253  func mapToString(kv map[string]string) string {
   254  	keys := make([]string, 0, len(kv))
   255  	for k := range kv {
   256  		keys = append(keys, k)
   257  	}
   258  	sort.Strings(keys)
   259  	var sb strings.Builder
   260  	for i, k := range keys {
   261  		if i != 0 {
   262  			fmt.Fprint(&sb, ",")
   263  		}
   264  		fmt.Fprintf(&sb, "%s=%s", k, kv[k])
   265  	}
   266  	return sb.String()
   267  }
   268
View as plain text