Sticky Sessions Load-Balancer Algorithm

[locao]

Context

Some applications require that the client hits the same backend service on every requecost. To achieve that, Kong offers the consistent-hashing load-balancing algorithm. This algorithm assures that, based on an input string selected by the Kong Operator, the same client will hit the same upstream target on every request, as long as the upstream target list is fix. Furthermore, Kong's consistent-hashing algorithm is loosely based on the Ketama algorithm, meaning that adding or removing targets will affect a minimum set of clients.

But for some users, a minimum set of clients is still too much. Those users want/need their clients to never face session drops. More than that, in some environments growing and shrinking the list of targets is a constant process, meaning that even if the load-balancing algorithm changes the least amount of client-target relations, the changes are so frequent that the relations are almost non-existent.

For those cases we need a new load-balancing algorithm, which will guarantee that after an specific client initiates a request with an specific upstream target, that relation will continue to exist as long as the upstream target is available, even if this behavior overcomes the configured upstream targets weights.

Proposed solution: Sticky Sessions Algorithm

The sticky sessions algorithm will allow us to achieve that behavior by sticking a client to an upstream target.

Description

When the first request from a client is received, no previous upstream target was used by this client. So a target must be chosen from the target list, as it happens with other existent algorithms. After selecting the upstream target and before issuing the request to the proxied server, an HTTP cookie must be set in the request header, containing a reference to the upstream target.

1st request - no cookie set

When the load-balancer is in getPeer() it must check for ngx.var["cookie_" .. <cookie_name>]. During the client's first request, this value is nil. The upstream target must be selected using the same algorithm as the consistent-hashing algorithm least-connections algorithm (algorithm changed according to @Tieske input here).

Next, a Set-Cookie header must be added: ngx.req.set_header("Set-Cookie", <cookie_name> .. "=" .. <target_reference>).

Next client's requests

The next client's requests will include the sticky sessions cookie. When the getPeer() function runs, it will check for the cookie <cookie_name> and use its value. If the referenced upstream target is available, it must be used. If it's not, the process of the 1st request must be done again, but instead of setting the header Set-Cookie, the contents of ``ngx.var["cookie_" .. <cookie_name>]` must be overwritten.

Implementation details

Most of the code will be shared with the least-connections algorithm. The easiest way of doing that is inheriting the lc class and reusing the existent methods where it is possible.

Upstream target reference

The sticky sessions cookie must not contain a clear direct reference to the upstream target, as the hostname or the IP. To avoid that, a translate table may be created:

{
	["reference_1"] = "a-hostname",
	["reference_2"] = "another-hostname",
	["reference_3"] = "192.168.0.29",
}

And the cookie header will contain: <cookie_name>=reference_1.

This translate table must be populated when adding and removing upstream targets, in the afterHostUpdate() function, using a consistent method among all workers and nodes. This will make sure any Kong node will contain the same references.

When using this translate table, as the index is the cookie value, virtually no time will be added: return translate[cookie_value].

More configurations

Some configuration options that might be interesting but not required on the first version.

Keep existent sticky session or keep connectivity

For the cases where an upstream target is unavailable, we could give to the Kong Operator the option to choose between:

• discard the existent cookie value and balance again with the currently available targets (default behavior described earlier)
• fail the request but keep the cookie value

[Tieske]

Consistent hashing is an ideal choice if there is no fixed user provided input. By taking a techincal property we can ensure consistency. However in this case I think basing it on the least-connections handler makes more sense.

The essence here is: Consistent-hashing prefers load-distribution over connection stability. In this case the requirement is to prefer connection stability over load-distribution.

Since every connection is fixed over its lifetime to a specific backend (no matter the load), and the information is carried in the request (by means of a cookie). That is easily solved. The problem however is that over time the load gets skewed towards the longest running nodes.

If we use the consistent-hashing balancer as the base, then any new client would be randomly distributed over all nodes (including the long-running heavily loaded ones). By using the least-connections algorithm, we can ensure proper load distribution, since the newer empty nodes will get all the new connections until they are at the same capacity.

Depending on the complexity of the implementation, this might even be implemented as a feature of the least-connections algorithm.

Note: one thing not explicitly called out (only seen in the example) is that the cookie value should not leak any backend info, like hostnames, ports, etc. That value MUST be opaque.

[locao]

The problem however is that over time the load gets skewed towards the longest running nodes.

Good point. I was in doubt which one would be better, consistent-hashing or least-connections, and this argument settles it down in my opinion.

[scrudge]

I agree, this could be a good feature enhancement to least connections. It would do a much better job of distributing the load on scaling up.

[locao]

@scrudge I think you might be interested on this proposal.

[merusso]

This algorithm seems to require cookies and has no header-based equivalent to the "consistent-hashing" algorithm's hash_on: header, correct? In other words, you must use cookies, cannot use a custom header.

[Tieske]

This could be an enhancement, making the hash source configurable.

[merusso]

I'm not sure how this could work with custom headers, at least not the same way it's used for "consistent-hashing". I assume the server must generate a sticky session value that clients must pass back in future requests.

[locao]

The (or one) advantage of using cookies is that, for most cases, you don't have to change anything, cookies are usually allowed to pass around. If we use a custom header, it's possible that, for some cases, we would have to add exceptions to avoid filtering it in some hop on the way.

It's not required, but yes, the header could be configurable. And it's an option that can be added in a future version.

[Tieske]

I think @merusso is right. The hashing on just any property can change the destination, if the layout of the balancer changes. So we need to pass the selected target to the client and back. Hence that requires a cookie.

For browsers that will typically work, m-2-m is a different story, there it really depends on the client. It should probably be documented in the API docs that the cookies are required, if you want to make this work.

[scrudge]

@locao wrote:
The sticky sessions cookie must not contain a clear direct reference to the upstream target, as the hostname or the IP. To avoid that, a translate table may be created:

How will this mapping be consistant across proxies in dbless mode?

[Tieske]

Since the hash-input will be in the cookie, it should work across nodes. As long as you make a first request, and reuse the cookie on all other requests. (so if you make multiple initial requests without a cookie, you might get different ones assigned until one wins).

[scrudge]

I was referring to the translation table:

{
	["reference_1"] = "a-hostname",
	["reference_2"] = "another-hostname",
	["reference_3"] = "192.168.0.29",
}

But I'm guessing the keys could be a hash of the values, that way it maps the same across proxies.

[Tieske]

that would work. But keep in mind that the balancer will expand hostnames to a list of IP addressses through DNS lookups. So the target configured in Kong has format [hostname]:[port], but the final addresses will have [ip-address]:[possibly-different-port].

So I think you should hash the following key: [Kong target]:[ip-address]:[port]. Where [Kong target] is the target as provided in the admin api/configuration, itself being [hostname:port].

@locao wdyt?

[locao]

the keys could be a hash of the values, that way it maps the same across proxies

This is what I thought as well. I guess afterHostUpdate() has to clean the translate table and add all available addresses in it.

So I think you should hash the following key: [Kong target]:[ip-address]:[port]

It seems to me you are right. The main problem is that we don't store in the binaryHeap everything we must return (this is the same in all other algorithms). After selecting an entry in the binaryHeap, we need to call balancers.getAddressPeer() to actually get the values we will return to the caller.

[merusso]

This proposal is really well written, thanks!

[ajessup]

What is the behavior when a backend is removed but sessions are still mapped to it. Are those re-mapped to another backend?

[merusso]

Our preference is for the requests to be forwarded to another backend.

You may want to make this configurable (Example: either return HTTP 503 or forward to separate backend).

[Tieske]

if you use least-connections as the base, which is needed to ensure no skewed workloads. Then there will initially be race conditions, if multiple requests at the same time hit different Kong nodes in a cluster. This will settle after the cookies have been set. But the condition will temporarily exist.

The same thing will happen when a backend disappears. So that should be fine, returning a 503 doesn't really help. The client would probably just retry anyway. (and in the retry it would probably use the same cookie again, causing another 503...)

[ajessup]

What is the behavior when a backend receives a TERM signal but hasn't yet shut down? Some backends hold this open for a while (several seconds) and may still be able to accept requests during this time.

[Tieske]

this is an off topic question imho. This is generic for any backend, independent of the loadbalancing algorithm.