Http header routing pattern

[gjreasoner]

Proposal

Would like to use a HTTP header in the HTTP request to determine which service to route to using http header based routing pattern.

Use-Case

Imagine hundreds of customers each with 100s of different domains pointed to their own HttpScaledObject.

Rather than maintaining the 100 domains on HTTPScaledObject, you send a custom header X-Customer-Id: customer-id-1 and register the hosts as customer-id-1, customer-id-2.

This means your upstream can add/update/delete host names without needing to update HTTPScaledObjects or extra k8s ingress/services.

Is this a feature you are interested in implementing yourself?

Yes

Anything else?

Can see this being implemented like

• An env variable on the interceptor, KEDA_HTTP_ADDTL_ROUTING_HEADER=X-Customer-Id when blank or missing from the request, it still uses the HTTP Host header

This gives you an easy way to opt into the feature and have fallback/main site domains.

apiVersion: http.keda.sh/v1alpha1
kind: HTTPScaledObject
spec:
  hosts:
  - my-main-site.example.com
  - customer-id-1
  replicas:
    max: 1
    min: 0

While your remaining domains might look like

- custom-domain-1.com
- ...
- custom-domain-99.com
- *.svc.domain.com

[wozniakjan]

I really like the idea of the feature, I think it's essential that http-add-on supports routing based on headers.

I would like to propose an alternative path on how it is implemented. Instead of ENV variable static for the entire traffic passing through the interceptor, it would be imho better to follow the design decisions from Gateway API. Mixing URLs and header values in spec.hosts might lead to confusing UX.

Currently the HTTPScaledObject allows routing based on hosts and pathPrefixes, e.g.

apiVersion: http.keda.sh/v1alpha1
kind: HTTPScaledObject
spec:
  hosts:
  - my.domain.com
  - my2.domain.com
  pathPrefixes:
  - /root
  - /new-feature

Adding headers to the spec would allow very fine-grained configurability resulting in overall increased satisfaction

apiVersion: http.keda.sh/v1alpha1
kind: HTTPScaledObject
spec:
  hosts:
  - my.domain.com
  - my2.domain.com
  pathPrefixes:
  - /root
  - /new-feature
  headers:
  - name: x-header-test
    value: abc
  - name: x-header-test2
    value: def

[erich23]

hey @gjreasoner I'm here because I'm seeing a similar issue (https://github.com/kedacore/http-add-on/issues/851 to be exact) and I think this fix can address it. If I can pass in custom headers, I can rewrite the L7 path on the ingress and route based on custom headers rather than the path.

when do you think you can have this PR merged by? im happy to help

[gjreasoner]

Hey @erich23 it's definitely top of mind, I have a work around (this patch on the interceptor image) in place that's keeping it from a being an absolute rush on my side. I'd still like to get back to the proposed solution hopefully in the week or so with the holiday slowdown. Feel free to take a stab at it if you'd like, I'll update here if I start work on it 👍🏻

[erich23]

hey @gjreasoner and @wozniakjan, here's my implementation of the proposed solution: https://github.com/kedacore/http-add-on/pull/1222. Can you guys give this a review? I'm going to try and get test cases to pass now but please let me know if anything is missing

[kahirokunn]

In KEDA's HTTPScaledObject, when two objects are configured as follows, which one will handle requests to my.domain.com?

apiVersion: http.keda.sh/v1alpha1
kind: HTTPScaledObject
metadata:
  name: canary
spec:
  hosts:
    - my.domain.com
    - my2.domain.com
  pathPrefixes:
    - /root
    - /new-feature
---
apiVersion: http.keda.sh/v1alpha1
kind: HTTPScaledObject
metadata:
  name: primary
spec:
  hosts:
    - my.domain.com
    - my2.domain.com
  pathPrefixes:
    - /root
    - /new-feature
  headers:
    - name: X-Flagger-Traffic-Target-To
      value: primary

In this setup, both HTTPScaledObject resources are configured to handle requests to my.domain.com with the paths /root and /new-feature. The primary object includes an additional header match condition: X-Flagger-Traffic-Target-To: primary.

The Kubernetes Gateway API's HTTPRoute defines matching precedence rules that could be beneficial to adopt here. According to the HTTPRoute documentation, the matching precedence is determined by the specificity of the match conditions:

1. Exact path matches: Routes with exact path matches take the highest precedence.
2. Longest prefix matches: Among prefix matches, the longest prefix has higher precedence.
3. Header matches: Routes with more header matches have higher precedence.
4. Query parameter matches: Routes with more query parameter matches have higher precedence.

Applying these principles to HTTPScaledObject would mean that the primary object, with its additional header match condition, should take precedence over the canary object for requests to my.domain.com with the specified paths.

Implementing such matching precedence in HTTPScaledObject would enable more granular traffic management, similar to systems like Knative. It would allow for the simultaneous management of canary, primary, and all past revisions within a single KEDA interceptor.

By clarifying and adopting these matching precedence rules, we can leverage header matches to achieve sophisticated routing and scaling scenarios, enhancing the flexibility and control over traffic management in KEDA deployments.

This approach would facilitate configurations like the one depicted below, enabling efficient management of multiple traffic versions and revisions:

[erich23]

@kahirokunn I'm not familiar with Gateway API's implementation of HTTPRoute, but based on what you're describing my PR is almost fulling these requirements.

Since it returns a longest prefix match that fulfills

• Exact path matches: Routes with exact path matches take the highest precedence.
• Longest prefix matches: Among prefix matches, the longest prefix has higher precedence.

But we can tweak the PR to rank HTTPScaledObjects by # of header matches and go with the most frequent one. This would also mean that, when none of headers match any HTTPScaledObjects which all have headers, it will just randomly choose one. I personally would prefer just failing unless you have HTTPScaledObject without any headers specified as its makes everything even more customizable / intentional. not familiar with what HTTPRoute does. i think all this sorting also comes with performance trade-offs so that's something we want to consider as well..

please feel free to review the current implementation 😊 I plan to chip away at this PR more tomorrow

[kahirokunn]

Thank you for your detailed response and the progress you've made with the current PR.

I understand that the implementation handles the longest prefix matches, which aligns with some aspects of my proposal. However, my suggestion primarily focuses on utilizing header matches to determine precedence among HTTPScaledObjects. Given that prefix matching pertains to the URL paths and isn't directly related to header conditions, I was wondering if you could share more about how the longest prefix match addresses the header-based precedence I mentioned?

Your clarification will help ensure that the proposed enhancements fully address the desired traffic management scenarios.

Thank you for your assistance.

Best regards, kahirokunn

[erich23]

@kahirokunn what I mentioned about prefix matches just addresses the ways in which this implementation aligns the conditions below:

• Exact path matches: Routes with exact path matches take the highest precedence.
• Longest prefix matches: Among prefix matches, the longest prefix has higher precedence.

After that, I mentioned that "we can tweak the PR to rank HTTPScaledObjects by # of header matches and go with the most frequent one."

The follow up question to that was what we should do if there's tie breakers or none of the HTTPScaledObjects match any headers

[kahirokunn]

I understand the content. Thank you for your message.

The Gateway API's HTTPRoute defines sort logic that guarantees deterministic and more intuitive results when multiple routes (or in this case, multiple HTTPScaledObjects) match the same request.

1. I think it's a very good situation to return the "longest prefix match" first.
2. For header-based routing, it's beneficial to add a step that ranks objects based on the number of matched headers. Objects that match more headers (i.e., more specific matching) are prioritized.
3. When nothing matches, instead of randomly selecting one, it might be clearer to fail (e.g., respond with HTTP 404). In production environment configurations, deterministic behavior is often desirable.

Regarding performance:

• Pre-sorting the HTTPScaledObject list according to these matching rules (or storing them in a data structure like a match tree) can significantly avoid impact on request-time performance.
• When a request arrives, iterate in sorted order and select the first match. Return 404 if there are no matching resources.
• This approach evaluates matching only until the first valid match is found, resulting in minimal overhead.

Here's a sequence diagram showing the flow of the matching process:

sequenceDiagram
    participant Client
    participant KEDA Interceptor
    participant Sorter/Match Logic

    KEDA Interceptor->>Sorter/Match Logic: Evaluate HTTPScaledObjects
    Sorter/Match Logic->>Sorter/Match Logic: Sort objects by precedence
    Client->>KEDA Interceptor: HTTP Request
    Sorter/Match Logic->>Sorter/Match Logic: Check Hostname match
    Sorter/Match Logic->>Sorter/Match Logic: Check Path (longest prefix, or exact)
    Sorter/Match Logic->>Sorter/Match Logic: Check Header matches
    alt Found a match
        Sorter/Match Logic->>KEDA Interceptor: Return matched object
        KEDA Interceptor->>Client: Forward request to matched object's destination
    else No match
        Sorter/Match Logic->>KEDA Interceptor: No match found
        KEDA Interceptor->>Client: Return 404 Not Found
    end

In contrast, choosing random logic when no header match exists could lead to non-deterministic behavior with multiple HTTPScaledObjects with headers, which can be problematic especially in production environments. Deterministic ordering is almost always clearer and more reproducible.

Here is the relevant part of the Kubernetes Gateway API's HTTPRoute specification, which explains how match prioritization works:

https://github.com/kubernetes-sigs/gateway-api/blob/4cebe3e4e36beef946081c5739154dd15f8d8c7e/apis/v1/httproute_types.go#L144-L203

	// Matches define conditions used for matching the rule against incoming
	// HTTP requests. Each match is independent, i.e. this rule will be matched
	// if **any** one of the matches is satisfied.
	//
	// For example, take the following matches configuration:
	//
	// ```
	// matches:
	// - path:
	//     value: "/foo"
	//   headers:
	//   - name: "version"
	//     value: "v2"
	// - path:
	//     value: "/v2/foo"
	// ```
	//
	// For a request to match against this rule, a request must satisfy
	// EITHER of the two conditions:
	//
	// - path prefixed with `/foo` AND contains the header `version: v2`
	// - path prefix of `/v2/foo`
	//
	// See the documentation for HTTPRouteMatch on how to specify multiple
	// match conditions that should be ANDed together.
	//
	// If no matches are specified, the default is a prefix
	// path match on "/", which has the effect of matching every
	// HTTP request.
	//
	// Proxy or Load Balancer routing configuration generated from HTTPRoutes
	// MUST prioritize matches based on the following criteria, continuing on
	// ties. Across all rules specified on applicable Routes, precedence must be
	// given to the match having:
	//
	// * "Exact" path match.
	// * "Prefix" path match with largest number of characters.
	// * Method match.
	// * Largest number of header matches.
	// * Largest number of query param matches.
	//
	// Note: The precedence of RegularExpression path matches are implementation-specific.
	//
	// If ties still exist across multiple Routes, matching precedence MUST be
	// determined in order of the following criteria, continuing on ties:
	//
	// * The oldest Route based on creation timestamp.
	// * The Route appearing first in alphabetical order by
	//   "{namespace}/{name}".
	//
	// If ties still exist within an HTTPRoute, matching precedence MUST be granted
	// to the FIRST matching rule (in list order) with a match meeting the above
	// criteria.
	//
	// When no rules matching a request have been successfully attached to the
	// parent a request is coming from, a HTTP 404 status code MUST be returned.
	//
	// +optional
	// +kubebuilder:validation:MaxItems=64
	// +kubebuilder:default={{path:{ type: "PathPrefix", value: "/"}}}
	Matches []HTTPRouteMatch `json:"matches,omitempty"`

Matches define the matching conditions of rules against incoming HTTP requests. Each match is independent, meaning this rule matches if any one of the matches is satisfied.

For example, consider the following situation:

kind: HTTPScaledObject
apiVersion: http.keda.sh/v1alpha1
metadata:
  name: first-match
spec:
  host: sample.com
  pathPrefixes:
  - /foo
  - /v2/foo
  targetPendingRequests: 100
  scaledownPeriod: 10
  scaleTargetRef:
    deployment: sample
    service: sample
    port: 8080
  replicas:
    min: 1
    max: 10
---
kind: HTTPScaledObject
apiVersion: http.keda.sh/v1alpha1
metadata:
  name: second-match
spec:
  host: sample.com
  headers:
  - name: version
    value: v2
  targetPendingRequests: 100
  scaledownPeriod: 10
  scaleTargetRef:
    deployment: sample
    service: sample
    port: 8080
  replicas:
    min: 1
    max: 10
---
kind: HTTPScaledObject
apiVersion: http.keda.sh/v1alpha1
metadata:
  name: last-match
spec:
  host: sample.com
  targetPendingRequests: 100
  scaledownPeriod: 10
  scaleTargetRef:
    deployment: sample
    service: sample
    port: 8080
  replicas:
    min: 1
    max: 10

In this case, the sort order would be:

1. first-match
2. second-match
3. last-match

Here's a flowchart showing how multiple matching rules are combined:

flowchart TB
    A[Incoming HTTP Request] --> B{Evaluate HTTPScaledObjects in order}
    B -->|Host match| C{Longest prefix<br>path match?}
    C --> D[Exact match gets higher priority]
    D --> E{Header match?}
    E -->|More matching headers = higher priority| F[Highest priority gets the match]
    F --> G[Accept & forward to<br>matched object]
    B -->|No match found<br>end of list| H[Return 404 Not Found]

The Envoy Gateway's HTTPRoute sort implementation is very sophisticated, so I think it would be helpful to share it as a reference:

https://github.com/envoyproxy/gateway/blob/3567496287c6657c9106827977e62999a60d817d/internal/gatewayapi/sort.go#L1-#L107

// Copyright Envoy Gateway Authors
// SPDX-License-Identifier: Apache-2.0
// The full text of the Apache license is available in the LICENSE file at
// the root of the repo.


package gatewayapi


import (
	"sort"


	"github.com/envoyproxy/gateway/internal/gatewayapi/resource"
	"github.com/envoyproxy/gateway/internal/ir"
)


type XdsIRRoutes []*ir.HTTPRoute


func (x XdsIRRoutes) Len() int      { return len(x) }
func (x XdsIRRoutes) Swap(i, j int) { x[i], x[j] = x[j], x[i] }
func (x XdsIRRoutes) Less(i, j int) bool {
	// 1. Sort based on path match type
	// Exact > RegularExpression > PathPrefix
	if x[i].PathMatch != nil && x[i].PathMatch.Exact != nil {
		if x[j].PathMatch != nil {
			if x[j].PathMatch.SafeRegex != nil {
				return false
			}
			if x[j].PathMatch.Prefix != nil {
				return false
			}
		}
	}
	if x[i].PathMatch != nil && x[i].PathMatch.SafeRegex != nil {
		if x[j].PathMatch != nil {
			if x[j].PathMatch.Exact != nil {
				return true
			}
			if x[j].PathMatch.Prefix != nil {
				return false
			}
		}
	}
	if x[i].PathMatch != nil && x[i].PathMatch.Prefix != nil {
		if x[j].PathMatch != nil {
			if x[j].PathMatch.Exact != nil {
				return true
			}
			if x[j].PathMatch.SafeRegex != nil {
				return true
			}
		}
	}
	// Equal case


	// 2. Sort based on characters in a matching path.
	pCountI := pathMatchCount(x[i].PathMatch)
	pCountJ := pathMatchCount(x[j].PathMatch)
	if pCountI < pCountJ {
		return true
	}
	if pCountI > pCountJ {
		return false
	}
	// Equal case


	// 3. Sort based on the number of Header matches.
	hCountI := len(x[i].HeaderMatches)
	hCountJ := len(x[j].HeaderMatches)
	if hCountI < hCountJ {
		return true
	}
	if hCountI > hCountJ {
		return false
	}
	// Equal case


	// 4. Sort based on the number of Query param matches.
	qCountI := len(x[i].QueryParamMatches)
	qCountJ := len(x[j].QueryParamMatches)
	return qCountI < qCountJ
}


// sortXdsIR sorts the xdsIR based on the match precedence
// defined in the Gateway API spec.
// https://gateway-api.sigs.k8s.io/references/spec/#gateway.networking.k8s.io/v1.HTTPRouteRule
func sortXdsIRMap(xdsIR resource.XdsIRMap) {
	for _, irItem := range xdsIR {
		for _, http := range irItem.HTTP {
			// descending order
			sort.Sort(sort.Reverse(XdsIRRoutes(http.Routes)))
		}
	}
}


func pathMatchCount(pathMatch *ir.StringMatch) int {
	if pathMatch != nil {
		if pathMatch.Exact != nil {
			return len(*pathMatch.Exact)
		}
		if pathMatch.SafeRegex != nil {
			return len(*pathMatch.SafeRegex)
		}
		if pathMatch.Prefix != nil {
			return len(*pathMatch.Prefix)
		}
	}
	return 0
}

https://github.com/envoyproxy/gateway/blob/226082b52c9dcbf85b22bd3c01f35509dc0cce2f/internal/gatewayapi/route.go#L297-L434

func (t *Translator) processHTTPRouteRule(httpRoute *HTTPRouteContext, ruleIdx int, httpFiltersContext *HTTPFiltersContext, rule gwapiv1.HTTPRouteRule) ([]*ir.HTTPRoute, error) {
	var ruleRoutes []*ir.HTTPRoute

	// If no matches are specified, the implementation MUST match every HTTP request.
	if len(rule.Matches) == 0 {
		irRoute := &ir.HTTPRoute{
			Name: irRouteName(httpRoute, ruleIdx, -1),
		}
		irRoute.Metadata = buildRouteMetadata(httpRoute, rule.Name)
		processRouteTimeout(irRoute, rule)
		applyHTTPFiltersContextToIRRoute(httpFiltersContext, irRoute)
		ruleRoutes = append(ruleRoutes, irRoute)
	}

	var sessionPersistence *ir.SessionPersistence
	if rule.SessionPersistence != nil {
		if rule.SessionPersistence.IdleTimeout != nil {
			return nil, fmt.Errorf("idle timeout is not supported in envoy gateway")
		}

		var sessionName string
		if rule.SessionPersistence.SessionName == nil {
			// SessionName is optional on the gateway-api, but envoy requires it
			// so we generate the one here.

			// We generate a unique session name per route.
			// `/` isn't allowed in the header key, so we just replace it with `-`.
			sessionName = strings.ReplaceAll(irRouteDestinationName(httpRoute, ruleIdx), "/", "-")
		} else {
			sessionName = *rule.SessionPersistence.SessionName
		}

		switch {
		case rule.SessionPersistence.Type == nil || // Cookie-based session persistence is default.
			*rule.SessionPersistence.Type == gwapiv1.CookieBasedSessionPersistence:
			sessionPersistence = &ir.SessionPersistence{
				Cookie: &ir.CookieBasedSessionPersistence{
					Name: sessionName,
				},
			}
			if rule.SessionPersistence.AbsoluteTimeout != nil &&
				rule.SessionPersistence.CookieConfig != nil && rule.SessionPersistence.CookieConfig.LifetimeType != nil &&
				*rule.SessionPersistence.CookieConfig.LifetimeType == gwapiv1.PermanentCookieLifetimeType {
				ttl, err := time.ParseDuration(string(*rule.SessionPersistence.AbsoluteTimeout))
				if err != nil {
					return nil, err
				}
				sessionPersistence.Cookie.TTL = &metav1.Duration{Duration: ttl}
			}
		case *rule.SessionPersistence.Type == gwapiv1.HeaderBasedSessionPersistence:
			sessionPersistence = &ir.SessionPersistence{
				Header: &ir.HeaderBasedSessionPersistence{
					Name: sessionName,
				},
			}
		default:
			// Unknown session persistence type is specified.
			return nil, fmt.Errorf("unknown session persistence type %s", *rule.SessionPersistence.Type)
		}
	}

	// A rule is matched if any one of its matches
	// is satisfied (i.e. a logical "OR"), so generate
	// a unique Xds IR HTTPRoute per match.
	for matchIdx, match := range rule.Matches {
		irRoute := &ir.HTTPRoute{
			Name:               irRouteName(httpRoute, ruleIdx, matchIdx),
			SessionPersistence: sessionPersistence,
		}
		irRoute.Metadata = buildRouteMetadata(httpRoute, rule.Name)
		processRouteTimeout(irRoute, rule)

		if match.Path != nil {
			switch PathMatchTypeDerefOr(match.Path.Type, gwapiv1.PathMatchPathPrefix) {
			case gwapiv1.PathMatchPathPrefix:
				irRoute.PathMatch = &ir.StringMatch{
					Prefix: match.Path.Value,
				}
			case gwapiv1.PathMatchExact:
				irRoute.PathMatch = &ir.StringMatch{
					Exact: match.Path.Value,
				}
			case gwapiv1.PathMatchRegularExpression:
				if err := regex.Validate(*match.Path.Value); err != nil {
					return nil, err
				}
				irRoute.PathMatch = &ir.StringMatch{
					SafeRegex: match.Path.Value,
				}
			}
		}
		for _, headerMatch := range match.Headers {
			switch HeaderMatchTypeDerefOr(headerMatch.Type, gwapiv1.HeaderMatchExact) {
			case gwapiv1.HeaderMatchExact:
				irRoute.HeaderMatches = append(irRoute.HeaderMatches, &ir.StringMatch{
					Name:  string(headerMatch.Name),
					Exact: ptr.To(headerMatch.Value),
				})
			case gwapiv1.HeaderMatchRegularExpression:
				if err := regex.Validate(headerMatch.Value); err != nil {
					return nil, err
				}
				irRoute.HeaderMatches = append(irRoute.HeaderMatches, &ir.StringMatch{
					Name:      string(headerMatch.Name),
					SafeRegex: ptr.To(headerMatch.Value),
				})
			}
		}
		for _, queryParamMatch := range match.QueryParams {
			switch QueryParamMatchTypeDerefOr(queryParamMatch.Type, gwapiv1.QueryParamMatchExact) {
			case gwapiv1.QueryParamMatchExact:
				irRoute.QueryParamMatches = append(irRoute.QueryParamMatches, &ir.StringMatch{
					Name:  string(queryParamMatch.Name),
					Exact: ptr.To(queryParamMatch.Value),
				})
			case gwapiv1.QueryParamMatchRegularExpression:
				if err := regex.Validate(queryParamMatch.Value); err != nil {
					return nil, err
				}
				irRoute.QueryParamMatches = append(irRoute.QueryParamMatches, &ir.StringMatch{
					Name:      string(queryParamMatch.Name),
					SafeRegex: ptr.To(queryParamMatch.Value),
				})
			}
		}

		if match.Method != nil {
			irRoute.HeaderMatches = append(irRoute.HeaderMatches, &ir.StringMatch{
				Name:  ":method",
				Exact: ptr.To(string(*match.Method)),
			})
		}
		applyHTTPFiltersContextToIRRoute(httpFiltersContext, irRoute)
		ruleRoutes = append(ruleRoutes, irRoute)
	}

	return ruleRoutes, nil
}

Currently, HTTPScaledObject already supports hostname and path matching, and header matching is being added as a new feature. Adopting clearly defined ordering as described above means:

• Users can rely on deterministic results
• It's intuitive for people who have used Gateway API or similar systems
• Overhead is minimal when using pre-sorted lists

Finally, you might not need to exactly replicate the HTTPRoute algorithm. However, taking inspiration from it (i.e., "exact match > longest prefix > number of header matches", etc.) and clearly documenting that "when multiple HTTPScaledObject resources match a request, the system selects the most specific one" is a big step toward a production-ready solution.

I hope this feedback helps with the implementation and serves as a starting point for further discussion in the PR. Please let me know if you have any questions or need clarification about the approach.

It's wonderful to see KEDA continuing to evolve in alignment with broader cloud-native patterns. Thank you again for this excellent work.

Best regards, kahirokunn

[wozniakjan]

thank you @gjreasoner for driving this feature implementation and @kahirokunn for great input. This is exactly the discussion that is necessary in order to implement the advanced routing capabilities well and as far as I can tell, people around Gateway API gave it a lot of thought and we can benefit from their careful considerations as well.

http-add-on can probably suffice for now with exact header matches and leave regexp matches for future enhancements. The header ordering and rules precedence from Gateway API is imho something we should try to implement as similar as possible.

[kahirokunn]

Thank you! What else is needed to move this forward? I'm excited that this wonderful feature will be implemented!

[stale[bot]]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed in 7 days if no further activity occurs. Thank you for your contributions.

[stale[bot]]

This issue has been automatically closed due to inactivity.

[kahirokunn]

/reopen

[stale[bot]]

This issue has been automatically closed due to inactivity.

[militarpancho]

Any update on this ? Are there plans to release this in the new version ? Thanks!

[stale[bot]]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed in 7 days if no further activity occurs. Thank you for your contributions.

[kahirokunn]

keep

[robinderat]

Any update on this? I need this in my project and it seems like most of the work has already been done in the PR by @wozniakjan