Table of Contents |
---|
1. Status
Current state: Under Discussion Accepted
Discussion thread: here
JIRA: here
...
Klein’s cycle canceling algorithm can solve the min-cost flow problem in O(E^2 * M * U) time where M is max cost and U is max capacity. In our particular case, U is 1 since a task can be assigned once to one client. M is related to the number of topic partitions a task can subscribe. So the algorithm runs in O(ME^2) time for our case. Note E is |T| * |C|
where T are the tasks and C are the clients. This is because each task can be assigned to any client; so there is an edge because every task to every client. In another word, the time complexity of the algorithm is O(M * |T|^2 * |NC|^2)
. Below is a rough sketch of the algorithm:
...
We can use a min-cost flow algorithm to assign stateless tasks. First, we can find a feasible solution based on task load. Then we can use the cycle canceling algorithm to compute minimum cost assignment as we do for active tasks. We can reuse the configuration for active tasks to control if we merely compute the min-cost assignment or we also balance tasks for the same sub-topology.
...
5. Public Interfaces
There will be a few new public configs added:
- rack.aware.assignment.strategy: this config controls if we should use 34.B.I or 34.B.II to compute min-cost with or without balanced sub-topology. If set to
NONE
, rack aware assignment will be disabled - rack.aware.assignment.traffic_cost: this config controls the cost we add to cross rack traffic
- rack.aware.assignment.non_overlap_cost: this config controls the cost we add to non overlap assignment with targeted assignment computed by HAAssignor
Note client.rack
consumer config needs to be configured by customer to enable rack aware assignment.
...
6. Compatibility, Deprecation, and Migration Plan
We will implement the new rack aware assignment logic in HighAvailabilityTaskAssignor
and StickTaskAssignor. Rack aware assignment will be
used only when
...
If users want to use rack aware assignment, they need to upgrade Kafka Streams to at least the earliest supported version. It's better to stop all the instances and start them all with the latest version with client.rack
config, but it's also OK to do a rolling bounce with the new version. Rolling bounce with new version may cause the assignment changing between rack aware assignment and no rack aware assignment but eventually the assignment will be computed using rack awareness after every instance uses the new version.
...
7. Test Plan
- Unit test will be added for min-cost flow graph algorithm and rack aware assignment
- Existing integration test will be updated to ensure it works with or without rack configuration as well as with both
client.rack
andrack.aware.assignment.tags
configurations - New integration test will be added to verify rack aware assignment
- Existing system test will be used to verify compatibility with old version
TaskAssignorConvergenceTest
will be updated to verify the new assignor will converge and it produces no worse assignment in terms of cross AZ cost- Performance test will be done manually to verify the efficiency of min-cost flow computation with large number of tasks and clients as well as different number of subscribed topic partitions
...
8. Rejected Alternatives
A. The follow algorithm for standby assignment is rejected
...