Cross-language deterministic BatchWriteItem key-affinity candidate selection

[dkropachev]

Jira task: https://scylladb.atlassian.net/browse/DRIVER-658
Jira epic: https://scylladb.atlassian.net/browse/DRIVER-653

Cross-language requirement: scylladb/alternator-client-rust#60
Related review discussion: scylladb/alternator-client-rust#61 (review)

Client Scope

The JavaScript client must satisfy this cross-language requirement. Language-specific implementation choices are acceptable only if they preserve the same vote counts and coordinator preference order for equivalent requests.

Problem

BatchWriteItem key-affinity routing must not choose a coordinator based on request map iteration order, write order, or non-key payload attributes. A batch can contain multiple partition keys, so selecting one request by request-map order, write order, or canonicalized full item can route equivalent or near-equivalent batches to different coordinators and can ignore better retry candidates.

Goal

Define and implement a language-agnostic BatchWriteItem routing algorithm so Go, Rust, Java, JavaScript, Python, C#, C++, and future clients derive the same coordinator preference order from equivalent requests and a fixed sorted live-node list, while basing that order only on routing-relevant partition-key values.

Scope

This applies only to BatchWriteItem when key-route affinity mode is ANY_WRITE. BatchWriteItem must not use key-route affinity in NONE or RMW mode.

Required Algorithm

For each BatchWriteItem request:

1. Read RequestItems as a map of table_name to write_requests.
2. Build one routing candidate for every valid write request.
3. For PutRequest, candidate attributes are PutRequest.Item and operation is exactly PutRequest.
4. For DeleteRequest, candidate attributes are DeleteRequest.Key and operation is exactly DeleteRequest.
5. Ignore empty or invalid writes.
6. For each candidate, resolve the partition-key name for table_name.
7. If the partition-key name is unknown, trigger asynchronous partition-key discovery for that table and skip that candidate for the current request. Unknown metadata for one table must not prevent using another table in the same batch.
8. Keep only candidates whose attributes contain the table partition key and whose partition-key value type is supported: S, N, or B.
9. Hash only the candidate partition-key value using the shared cross-language AttributeValue hash: S = prefix 0x01 + UTF-8 bytes, N = prefix 0x02 + exact numeric string bytes, B = prefix 0x03 + raw bytes, MurmurHash3 x64 128 seed 0 first 64 bits.
10. Using the sorted live-node list and the standard seeded affinity query-plan algorithm, compute each usable candidate's preferred first node.
11. Count votes by preferred first node. Each usable write request contributes one vote.
12. If there are no usable candidates, fall back to normal non-affinity routing for this request.
13. If at least one usable candidate exists, build a deterministic affinity query plan from the vote counts:
    • coordinators with votes are tried first,
    • voted coordinators are ordered by vote count descending,
    • equal vote counts are broken by canonical node address ascending,
    • live coordinators with no votes are appended in canonical node-address order.

Non-key Attribute Rule

The routing decision must not depend on non-key attributes. Non-key values are part of the write payload, but they do not decide the partition that stores the item and must not affect the selected coordinator preference order.

Node Ordering Requirement

Affinity hash-to-node selection and retry-order tie breaking must use a canonical live-node order. Sort node addresses lexicographically before storing or using them for affinity. Initial seed nodes should follow the same rule if they can be used before discovery completes.

Cross-language Vectors

Existing vectors based on selecting the first sorted canonical item are obsolete and must be regenerated for the voting algorithm. New vectors should include the full selected coordinator preference order for strict-majority and tied-vote cases, and the fallback/no-affinity result for no-usable-vote cases.

Acceptance Criteria

1. Each language implementation has tests for single-table PutRequest and DeleteRequest votes.
2. Each language implementation has tests for multi-table batches with table insertion order reversed.
3. Each language implementation has tests for same-table write order reversed.
4. Each language implementation has tests for mixed put/delete candidates.
5. Unknown partition-key metadata for one table does not block another usable table in the same batch.
6. Unsupported partition-key values are skipped while other valid candidates can still vote.
7. Empty or invalid writes are ignored.
8. Non-key attribute changes do not change the selected coordinator preference order when the set of usable partition keys and live nodes is unchanged.
9. A strict majority of usable candidates puts the preferred node with the most votes first.
10. Equal top vote counts produce deterministic node-address tie breaking among voted coordinators.
11. Voted coordinators drive the full retry order before zero-vote live nodes.
12. No usable candidates fall back to normal non-affinity routing.
13. The same usable candidates produce the same vote counts and coordinator preference order across clients for a fixed sorted node list.
14. Existing key-affinity behavior outside positive BatchWriteItem ANY_WRITE cases is unchanged.