[FEATURE REQUEST] Support node locality routing hints

[mccheah]

What happened?

In distributed environments, sometimes it is desirable for multiple calls in a sequence to predictably route to a given node. This seems to have similarities to the request in #1000 and other places, so feel free to reroute this ask to that ticket or others that might be similar.

The use case is as follows: Suppose we have a client web browser, and two clustered servers, D with nodes D1, D2 ... Dk, and H with nodes H1, H2 ... Hn. An operation on the browser executes two requests against D, each of which routes to a request against H. The nodes of H each hold a local cache.

In this environment, currently, it is very hard to achieve optimal cache locality on H. For example, consider two requests R1 and R2. R1 against D might hit node D1, which routes to node H2. But the second request R2 reaching D, if it were to also route to node H2, would achieve cache locality - but suppose this request instead routes to D2, and then routes to H1 - this would cause a cache miss and degrade performance.

The current workaround would be to use per-node-clients, and have the web browser pass in a stable sort of session token to D, and D can pick a stable instance of H to route to. Using per-node-clients is not ideal, because in the process we end up losing the built-in failover / retry behavior that Dialogue offers.

What did you want to happen?

Introduce the construct of a "node locality hint", which is inspired by Elasticsearch's similar notion of node locality preference hinting: https://www.elastic.co/guide/en/elasticsearch/reference/7.17/search-search.html#search-preference.

Support a new type of client - name is debatable, but let's call it LocalityHintClientFactory / LocalityHintClient<T>. Have an API that supports conversion from LocalityHintClient<T> to T that accepts a hint key, which is used to seed the round-robin rotation in the underlying client (probably just hash the key, then modulo number of nodes, then sort the nodes and index into the sorted list). Thus multiple calls to the client that specify the same hint key should first attempt to route to the same node, even across a cluster.

[jkozlowski]

Have you seen this?

dialogue/dialogue-clients/src/main/java/com/palantir/dialogue/clients/ReloadingClientFactory.java

Line 226 in c16a03f

public StickyChannelFactory2 getStickyChannels2(String serviceName) {

[henryptung]

Hey @jkozlowski, for some more context:

• The goal isn't to make a single request flow stick with a given mirror, but rather to make all requests which map to a particular cache key (e.g. a particular Horizon subset ID, so that the same set of objects can be aggregated repeatedly in different ways) stick with/prefer a specific mirror.
• Even if we e.g. cached the sticky channel by user in Dispatch, this would still not guarantee that:
  • Requests with the same key on a different Dispatch don't get routed differently
  • Horizon internally routes traffic for that key to the same shard mirror (Horizon is also sharded, so different shards will talk to each other for some operations)

It feels like the existing sticky mechanisms aren't sufficient for those reasons, but suggestions are welcome.