fix: merge multi-shard reads in the key sorting of the namespace - #1388

Problem

Some reads without a partition key go to every shard of the namespace:

• a Get with ComparisonFloor, ComparisonLower, ComparisonCeiling or ComparisonHigher, or with UseIndex;
• a RangeScan.

The client then has to combine the shards' answers. For a get it picks one answer: the largest for floor/lower, the smallest for ceiling/higher. For a range scan it merges the shards' streams into one ordered stream.

Each shard orders its keys by the key sorting of the namespace:

• natural: by their bytes;
• hierarchical (the default): keys with fewer / first, then by their bytes, with / after any other byte.

The client compares keys with compare.CompareWithSlash instead. That is the order of the old storage format, used before v0.15, and it matches neither sorting.

So a floor or ceiling get can return the wrong record, and a range scan can return records out of order, with both sortings. The client can't fix this on its own, because only the namespace config holds the key sorting. The shard assignments the client receives don't carry it.

Example

A natural namespace with 4 shards:

1. Put "a0" (it lands on shard 2) and "a/y/z" (it lands on shard 0).
2. Call Get("b", ComparisonFloor()), which asks for the greatest key ≤ "b". In byte order "a/y/z" < "a0" < "b" (/ is 0x2F, 0 is 0x30), so the answer should be "a0".
3. The get has no partition key, so the client sends it to all 4 shards. Shard 2 answers "a0", shard 0 answers "a/y/z", and the other two answer "not found".
4. Before: the client keeps the larger answer according to CompareWithSlash. That order puts a key with a / after one without, so it ranks "a0" < "a/y/z". The get returns "a/y/z", a key lower than "a0".
5. After: the client received KEY_SORTING_NATURAL with the shard assignments. It compares the bytes and returns "a0".

The default sorting is affected too. Take a hierarchical namespace with "a/x" (shard 3) and "ab/y" (shard 0), and call Get("a/z", ComparisonFloor()). In hierarchical order "ab/y" < "a/x" < "a/z", since / sorts after b, so the answer should be "a/x".

• Before: it returns "ab/y". CompareWithSlash compares the first segments, "a" < "ab".
• After: it returns "a/x".

A RangeScan("", "") over b, a/y/z, ab/y, a0, a/x on 4 shards returns:

Modification

• Protocol: a new enum KeySorting (KEY_SORTING_UNKNOWN, KEY_SORTING_NATURAL, KEY_SORTING_HIERARCHICAL) and a new field NamespaceShardsAssignment.key_sorting (field 3). It is a new enum rather than replication.KeySortingType because client.proto can't import replication.proto.

• Coordinator: fills the field for each namespace from the namespace config. A namespace with no key sorting is sent as hierarchical, which is what its shards use. The standalone server fills it from its own config.

• Data servers: unchanged. They pass the assignments on to the clients. Older data servers (v0.15.0, v0.16.1 and v0.17.1 checked) keep the field as an unknown field, so it still reaches the clients.

• Go client:

  • The shard manager keeps the key sorting from the latest assignments.
  • Multi-shard gets compare keys in that sorting, using the same key encoder as the shards. Index gets compare the secondary keys first.
  • The range-scan merge uses the same order, and computes each record's comparison key once.

• Older coordinators: when the coordinator doesn't send the field, the client keeps comparing with CompareWithSlash, exactly as before. This way a client-only upgrade doesn't change any result. It also stays correct for servers older than v0.15, which store keys in that order.

• Compatibility: old clients ignore the field. The fix takes effect once the coordinator (or the standalone server) and the client are upgraded.

• Tests: the example is reproduced by these e2e tests, which fail on main:

  • TestSyncClientImpl_FloorCeilingGetKeySorting (10 get cases);
  • TestSyncClientImpl_RangeScanKeySorting;
  • TestCoordinator_MultiShardKeySorting, which goes through a real coordinator and data server.

  With a single shard, where the server alone decides, all their cases pass, so the expected values are right. Unit tests cover:

  • the key order;
  • index gets;
  • the range-scan merge, including the fallback;
  • the shard manager;
  • the coordinator's assignments.

Notes

• Not fixed here: a range scan with UseIndex is still merged by the primary key, because the range-scan records don't carry their secondary key. That needs a server change, left as a follow-up.
• Index gets: they are correct end to end only together with fix: order secondary-index gets by the shard's key sorting #1387, which fixes the server-side comparison.
• Other SDKs: the Java and Rust SDKs have the same bug. Their changes are described separately and are not part of this PR.
• API change: oxia.ResultHeap, exported by accident, changes from a slice to a struct.