feat(sqs): HT-FIFO partitioned-keyspace constructors (Phase 3.D PR 3)#703
feat(sqs): HT-FIFO partitioned-keyspace constructors (Phase 3.D PR 3)#703
Conversation
Adds the partitioned-keyspace constructors per §3.1 of the split-queue FIFO design without touching the legacy keyspace or any existing call site. The §11 PR 2 dormancy gate still rejects PartitionCount > 1 at CreateQueue, so these helpers are dead code in production until PR 5 atomically lifts the gate and wires the data-plane fanout.
The partitioned keyspace inserts a 'p|' discriminator after the family prefix and a fixed-width big-endian uint32 partition between the queue segment and the generation:
legacy: !sqs|msg|<family>|<queue>|<gen>|<rest>
partitioned: !sqs|msg|<family>|p|<queue>|<partition>|<gen>|<rest>
The discriminator is safe by construction: validateQueueName forbids '|' in queue names, and the queue segment is base32-raw-URL encoded (cannot start with the literal byte 'p' followed by '|').
New constants:
- sqsPartitionedDiscriminator = "p|"
- SqsPartitionedMsg{Data,Vis,Dedup,Group,ByAge}Prefix
New constructors (all unexported, mirroring the legacy family):
- sqsPartitionedMsgDataKey
- sqsPartitionedMsgVisKey
- sqsPartitionedMsgVisPrefixForQueue
- sqsPartitionedMsgDedupKey
- sqsPartitionedMsgGroupKey
- sqsPartitionedMsgByAgeKey
- sqsPartitionedMsgByAgePrefixForQueueAllPartitions
- parseSqsPartitionedMsgByAgeKey
- sqsMsgByAgePrefixesForQueue (returns {legacy, partitioned} pair for the reaper)
- appendU32 (helper for the 4-byte partition segment)
New record type sqsPartitionedMsgByAgeRecord mirrors sqsMsgByAgeRecord with Partition added.
Tests in adapter/sqs_keys_test.go cover:
- Byte-distinct legacy vs partitioned across all 5 families.
- Per-partition isolation: keys for partition k must not match the prefix of partition k+1's scan, otherwise ReceiveMessage fanout would double-count.
- Determinism: same inputs yield byte-identical keys across calls.
- Round-trip parse for partitioned byage keys at corner partition values (0, 31).
- Mutual rejection: parseSqsMsgByAgeKey rejects partitioned keys, parseSqsPartitionedMsgByAgeKey rejects legacy keys (the dual-parse contract).
- Reaper enumeration helper returns both prefixes in {legacy, partitioned} order.
- Discriminator constants all end with 'p|' (asserts none lost the trailing '|').
Design doc §3.1 example code updated to use the actual implementation names (sqsMsgDataKey + sqsPartitionedMsgDataKey) rather than the placeholder legacyMsgDataKey/partitionedMsgDataKey.
go test -race ./adapter/... pass; golangci-lint ./adapter/... clean. No call site changed; existing queues stay byte-identical on disk.
|
Warning Rate limit exceeded
To keep reviews running without waiting, you can enable usage-based add-on for your organization. This allows additional reviews beyond the hourly cap. Account admins can enable it under billing. ⌛ How to resolve this issue?After the wait time has elapsed, a review can be triggered using the We recommend that you space out your commits to avoid hitting the rate limit. 🚦 How do rate limits work?CodeRabbit enforces hourly rate limits for each developer per organization. Our paid plans have higher rate limits than the trial, open-source and free plans. In all cases, we re-allow further reviews after a brief timeout. Please see our FAQ for further information. ℹ️ Review info⚙️ Run configurationConfiguration used: defaults Review profile: CHILL Plan: Pro Run ID: 📒 Files selected for processing (3)
✨ Finishing Touches🧪 Generate unit tests (beta)
Thanks for using CodeRabbit! It's free for OSS, and your support helps us grow. If you like it, consider giving us a shout-out. Review rate limit: 0/1 reviews remaining, refill in 45 minutes and 55 seconds.Comment |
![gemini-code-assist[bot]](https://avatars.githubusercontent.com/in/956858?s=60&v=4){kind=small}
There was a problem hiding this comment.
Code Review
This pull request introduces a partitioned keyspace for HT-FIFO SQS queues, adding key constructors, prefix helpers, and unit tests. The review feedback identifies a critical issue where the lack of a delimiter after the variable-length queue name segment could cause prefix collisions between different queues. Additionally, the reviewer pointed out a discrepancy between the code comments and the actual encoding used, and suggested adding a test case to verify isolation between queues with overlapping names.
| func sqsPartitionedMsgDataKey(queueName string, partition uint32, gen uint64, messageID string) []byte { | ||
| buf := make([]byte, 0, len(SqsPartitionedMsgDataPrefix)+sqsKeyCapLarge) | ||
| buf = append(buf, SqsPartitionedMsgDataPrefix...) | ||
| buf = append(buf, encodeSQSSegment(queueName)...) |
There was a problem hiding this comment.
The partitioned key layout is missing a delimiter after the variable-length queue name segment. Without a delimiter (like '|'), a prefix scan for a queue name that is a prefix of another queue name (e.g., 'queue' and 'queue1') will incorrectly return records from both queues. This can lead to state inconsistencies. The design document (§3.1) explicitly mentions that segments should be terminated by a '|' to prevent such collisions.
This issue applies to all partitioned key constructors in this file (sqsPartitionedMsgDataKey, sqsPartitionedMsgVisKey, sqsPartitionedMsgDedupKey, sqsPartitionedMsgGroupKey, sqsPartitionedMsgByAgeKey) and their corresponding prefix helpers.
| buf = append(buf, encodeSQSSegment(queueName)...) | |
| buf = append(buf, encodeSQSSegment(queueName)...) | |
| buf = append(buf, '|') // Delimiter to prevent prefix collisions between queue names. |
References
- Avoid silently dropping entries or causing state inconsistencies during serialization or normalization.
| func sqsPartitionedMsgVisPrefixForQueue(queueName string, partition uint32, gen uint64) []byte { | ||
| buf := make([]byte, 0, len(SqsPartitionedMsgVisPrefix)+sqsKeyCapSmall) | ||
| buf = append(buf, SqsPartitionedMsgVisPrefix...) | ||
| buf = append(buf, encodeSQSSegment(queueName)...) |
There was a problem hiding this comment.
As noted in the data key constructor, a delimiter is required after the queue name to ensure prefix scans are isolated to a single queue.
| buf = append(buf, encodeSQSSegment(queueName)...) | |
| buf = append(buf, encodeSQSSegment(queueName)...) | |
| buf = append(buf, '|') |
| func sqsPartitionedMsgByAgePrefixForQueueAllPartitions(queueName string) []byte { | ||
| buf := make([]byte, 0, len(SqsPartitionedMsgByAgePrefix)+sqsKeyCapSmall) | ||
| buf = append(buf, SqsPartitionedMsgByAgePrefix...) | ||
| buf = append(buf, encodeSQSSegment(queueName)...) |
There was a problem hiding this comment.
The prefix helper used by the reaper must also include the delimiter to avoid scanning records from queues with overlapping encoded names.
| buf = append(buf, encodeSQSSegment(queueName)...) | |
| buf = append(buf, encodeSQSSegment(queueName)...) | |
| buf = append(buf, '|') |
| // — the queue-name segment is base32-encoded and cannot start with | ||
| // the literal ASCII byte 'p' followed by '|'. |
There was a problem hiding this comment.
The comment mentions that the queue-name segment is base32-encoded, but the implementation of encodeSQSSegment (line 216) uses base64.RawURLEncoding. This discrepancy also appears in the design document. Please update the comment to reflect the actual encoding used.
| // — the queue-name segment is base32-encoded and cannot start with | |
| // the literal ASCII byte 'p' followed by '|'. | |
| // — the queue-name segment is base64-encoded and cannot start with | |
| // the literal ASCII byte 'p' followed by '|'. |
| require.False(t, bytes.HasPrefix(legacy, partitionedPrefixOnly), | ||
| "a legacy key for any queue name must not start with the partitioned prefix; "+ | ||
| "the trailing | in the discriminator is what makes this true — "+ | ||
| "if the legacy key starts with `!sqs|msg|data|p|...`, the queue "+ | ||
| "name's encoded segment would have to start with `p|` which "+ | ||
| "base32-raw-URL never produces") |
There was a problem hiding this comment.
It would be beneficial to add a test case that specifically asserts that queue names with overlapping encoded prefixes do not collide in the partitioned keyspace. This would have caught the missing delimiter issue. Note: the encoding used is base64, not base32.
require.False(t, bytes.HasPrefix(legacy, partitionedPrefixOnly),
"a legacy key for any queue name must not start with the partitioned prefix; "+
"the trailing | in the discriminator is what makes this true — "+
"if the legacy key starts with '!sqs|msg|data|p|...', the queue "+
"name's encoded segment would have to start with 'p|' which "+
"base64-raw-URL never produces")
// Assert that queues with overlapping encoded names are distinct and prefix-safe.
// "queue" encodes to "cXVldWU", "queue1" encodes to "cXVldWUx".
q1 := sqsPartitionedMsgDataKey("queue", 0, 1, "id")
q2 := sqsPartitionedMsgDataKey("queue1", 0, 1, "id")
require.NotEqual(t, q1, q2)
require.False(t, bytes.HasPrefix(q2, q1), "partitioned key for 'queue' must not be a prefix of 'queue1'")
|
@claude review |
|
Claude encountered an error —— View job Code Review: feat(sqs): HT-FIFO partitioned-keyspace constructors (Phase 3.D PR 3)
SummaryThe overall structure — discriminator-based keyspace separation, named constructors, Critical: missing
|
| Location | Text |
|---|---|
sqs_keys.go:63 |
"the queue-name segment is base32-encoded" |
sqs_keys_test.go:18 |
"a base32-encoded queue segment" |
sqs_keys_test.go:243–248 |
"base32-raw-URL encoding", "base32-raw-URL never produces" |
The safety claim ("cannot start with the literal ASCII byte 'p' followed by '|'") is correct for base64, but the reasoning via "base32" is wrong. base32 and base64 have different alphabets — a base32-safe argument would need separate verification. Fix all three to say "base64-raw-URL".
Medium: design doc layout vs implementation
docs/design/2026_04_26_proposed_sqs_split_queue_fifo.md shows the key shape with | separators:
partitioned: !sqs|msg|<family>|p|<queue>|<partition>|<gen>|<rest>
and inline code comments in sqs_keys.go:57–58 repeat the same layout. If the | delimiter fix above is applied, the code will match the doc. If not, the doc should be updated to reflect the actual on-disk format so future implementors don't rely on separators that aren't there.
Low: missing prefix-isolation test between queue names
TestSqsPartitionedMsgKeys_PartitionsAreDistinct verifies that two queue names produce different complete keys (require.NotEqual). But the dangerous failure mode is a prefix scan for queue A returning queue B's entries, not equal keys. The test that would have caught the delimiter bug:
q1prefix := sqsPartitionedMsgByAgePrefixForQueueAllPartitions("queue")
q1key := sqsPartitionedMsgByAgeKey("queue1", 0, 1, 0, "id")
require.False(t, bytes.HasPrefix(q1key, q1prefix),
"prefix scan for 'queue' must not match 'queue1' keys")Minor: stringer helper
stringer (test line 267) is a hand-rolled uint32 → string converter. strconv.FormatUint(uint64(v), 10) is one import and handles the full uint32 range without branching. The current implementation is correct for partition values but slightly surprising to a reader who expects strconv.
Positives
- The
p|discriminator safety argument is sound: since|(0x7C) is not in the base64 alphabet, it can never appear in a base64-encoded queue name, so the partitioned prefix is always unambiguous relative to a legacy queue name. appendU32implementation is correct.- Named-constructor dispatch pattern (no variadic) is the right call.
parseSqsPartitionedMsgByAgeKeycorrectly bounds-checkstsRawthe same way the legacy parser does.- The dual-parse mutual-rejection tests are well-designed.
- Reaper enumeration helper returning both prefixes is future-proof.
The partitioned key shape from PR 3 omitted the segment terminator
between the variable-length encoded queue name and the fixed-width
partition uint32. Because base64.RawURLEncoding is variable-length,
base64("queue") = "cXVldWU" is a strict byte prefix of base64("queue1")
= "cXVldWUx", so a reaper-side prefix scan for queue "queue" would
also surface queue "queue1"'s entries (and the parser would misdecode
those bytes as the wrong (partition, gen, ts, msgID)).
Add a '|' byte after the encoded queue segment in every partitioned
constructor and prefix helper. '|' is outside the base64-raw-URL
alphabet (A-Z, a-z, 0-9, -, _) so the terminator can never collide
with the segment it terminates, and validateQueueName already rejects
'|' in raw queue names.
Other review fixes folded in:
- Comment fixes: encoder is base64.RawURLEncoding, not base32 — three
comment locations corrected (sqs_keys.go header, two test docs).
- Replace hand-rolled stringer with strconv.FormatUint(uint64(v), 10).
- Add TestSqsPartitionedMsgKeys_QueueNamePrefixIsolation that asserts
the bug above does not regress, using ("queue", "queue1") as the
motivating example pair.
- Update §3.1 design-doc paragraph to call out the per-segment '|'
terminator and to fix the same base32 → base64 wording.
|
@claude review Round 2 — addresses the gemini-code-assist review:
Also note: gemini's review flagged the legacy non-partitioned byage prefix (sqsMsgByAgePrefixAllGenerations) as having the same latent bug. That is genuinely a pre-existing issue but out of scope for this PR — I will open a separate follow-up for it after PR 4-A lands. |
|
Claude finished @bootjp's task in 2m 14s —— View job Code Review: Round 2 — HT-FIFO Partitioned Keyspace Constructors
All four issues from Round 1 have been correctly resolved. This is a clean pass. Critical: delimiter bug — fixed ✅Every partitioned constructor and both prefix helpers now append buf = append(buf, encodeSQSSegment(queueName)...)
buf = append(buf, sqsPartitionedQueueTerminator) // ← present in all 5 constructors
buf = appendU32(buf, partition)Verified: The new constant is well-documented: // sqsPartitionedQueueTerminator is appended after the encoded queue
// name in every partitioned key. … base64.RawURLEncoding never emits '|'
// (it uses A-Z, a-z, 0-9, '-', '_').
const sqsPartitionedQueueTerminator = '|'Medium: base32 → base64 — fixed ✅All three locations corrected:
The test file ( Minor: stringer → strconv — fixed ✅// Before: hand-rolled helper
// After:
t.Run(tc.queue+"/p"+strconv.FormatUint(uint64(tc.partition), 10), ...)Design doc §3.1 — fixed ✅Now explicitly documents the per-constructor
Also updates the pseudocode examples throughout to use the actual function names ( New test:
|
… PR 4-A) Adds the operator-config foundation for HT-FIFO routing per §5 of the split-queue FIFO design. Stacks on top of PR 3 (#703), which lands the partitioned-keyspace constructors. The grammar matches the design: 'queue.fifo:N=group_0,...,group_{N-1};...' with multiple queue entries separated by ';' (commas are reserved for the per-queue group list). PartitionCount must be a power of two ≤ 32 — the validator rejects anything else at config-parse time so a typo cannot land a half-shaped routing map at runtime. Two-stage validation: - parseSQSFifoPartitionMap: grammar + per-entry consistency (PartitionCount agrees with len(Groups), partition count is a power of two within the cap, no duplicate queues). - validateSQSFifoPartitionMap: runs after --raftGroups is parsed and asserts every group named in the partition map exists in --raftGroups; rejects with a queue/partition-pointer error message so the operator can fix typos without re-counting. Plumbed through parseRuntimeConfig into runtimeConfig.sqsFifoPartitionMap. Not yet consumed by routing — PR 4-B will wire it through ShardedCoordinator and add the htfifo capability advertisement once the routing layer lands. The §11 PR 2 dormancy gate still rejects PartitionCount > 1 on CreateQueue, so populating this flag has no effect on production traffic until PR 5 lifts the gate atomically with the data-plane fanout. parseSQSFifoPartitionMapEntry was extracted into parseSQSFifoPartitionCount + parseSQSFifoGroupList helpers to stay under the cyclop=10 ceiling once the four-rejection validation surface landed (zero / over-cap / non-power-of-2 / count-mismatch). parseRuntimeConfig grew over the cyclop ceiling too, so the partition-map block was extracted into buildSQSFifoPartitionMap. Tests in shard_config_test.go cover: - Empty input yields empty map. - Single-queue happy path. - Multiple queues separated by ';'. - Whitespace trimming. - PartitionCount > 0 enforcement. - PartitionCount must be a power of two. - PartitionCount within the per-queue cap. - count and group-list length must agree. - Malformed entry (missing '=', empty queue, empty group, trailing comma). - Duplicate queue rejection. - validateSQSFifoPartitionMap: all-groups-present passes; missing group fails with queue + partition-index pointer in the error message. go test -race ./... pass; golangci-lint ./... clean. No behaviour change in production paths.
… PR 4-A) (#704) ## Summary Phase 3.D PR 4-A of the split-queue FIFO rollout. Operator-config foundation: parses `--sqsFifoPartitionMap`, validates against `--raftGroups`, plumbs through `parseRuntimeConfig` into `runtimeConfig.sqsFifoPartitionMap`. Stacks on top of #703 (PR 3, partitioned-keyspace constructors). ## What's added - `--sqsFifoPartitionMap` flag with grammar `queue.fifo:N=group_0,...,group_{N-1};...` - `parseSQSFifoPartitionMap` + `parseSQSFifoPartitionMapEntry` (grammar + per-entry consistency) - `validateSQSFifoPartitionMap` (cross-check against `--raftGroups`) - `sqsFifoQueueRouting` struct (PartitionCount + Groups) - `runtimeConfig.sqsFifoPartitionMap` field ## What's NOT added (deferred to PR 4-B) - Routing layer wiring through `ShardedCoordinator` - `htfifo` capability advertisement on `/sqs_health` - `kv/lease_state.go` leadership-refusal hook for non-htfifo binaries - Catalog polling for partitioned-queue discovery at startup These are coupled by the design's "binary advertises htfifo only when both routing AND leadership-refusal are in place" rule, so they belong in one PR. ## Validation coverage - PartitionCount > 0 - PartitionCount ≤ 32 (per-queue cap) - PartitionCount must be a power of two - `len(Groups) == PartitionCount` - No duplicate queues across entries - Every named group exists in `--raftGroups` - Empty queue / empty group / trailing-comma / missing-`=` all rejected with the offending entry quoted in the error ## Test plan - [x] `TestParseSQSFifoPartitionMap` covers grammar, whitespace, multiple queues, all rejection paths. - [x] `TestValidateSQSFifoPartitionMap` covers the missing-group case with queue + partition-index pointer. - [x] `parseRuntimeConfig` integration: `main_bootstrap_e2e_test.go` updated for the new parameter. - [x] `go test -race ./adapter/... .` pass. - [x] `golangci-lint ./...` clean. ## Self-review (per CLAUDE.md) 1. **Data loss** — config-only change. No FSM, Pebble, or retention path is touched. No issue. 2. **Concurrency / distributed failures** — single-shot parse at startup, no goroutines or shared state. No issue. 3. **Performance** — startup-time validation only. No hot-path effect. No issue. 4. **Data consistency** — partition count and group list must agree at parse time, so the runtime cannot see a half-shaped routing map. The flag has no effect on production traffic until PR 4-B + PR 5 land. No issue. 5. **Test coverage** — 11 sub-tests in `TestParseSQSFifoPartitionMap` and 3 in `TestValidateSQSFifoPartitionMap`, covering every documented rejection branch.
1 participant
Summary
Phase 3.D PR 3 of the split-queue FIFO rollout (per §11 of
docs/design/2026_04_26_proposed_sqs_split_queue_fifo.md). Adds the partitioned-keyspace constructors without touching the legacy keyspace or any existing call site. The §11 PR 2 dormancy gate still rejectsPartitionCount > 1atCreateQueue, so these helpers are dead code in production until PR 5 atomically lifts the gate and wires the data-plane fanout.Keyspace shape
The
p|discriminator after the family prefix is safe by construction:validateQueueNameforbids|in queue names, and the queue segment is base32-raw-URL encoded (cannot start with the literal byte'p'followed by'|'). The partition is a 4-byte big-endianuint32so a prefix scan!sqs|msg|<family>|p|<queue>|<partition>|picks exactly one partition's keys.What's added
sqsPartitionedDiscriminator,SqsPartitionedMsg{Data,Vis,Dedup,Group,ByAge}Prefix.sqsPartitionedMsg{Data,Vis,Dedup,Group,ByAge}Key,sqsPartitionedMsgVisPrefixForQueue,sqsPartitionedMsgByAgePrefixForQueueAllPartitions.sqsMsgByAgePrefixesForQueuereturns the{legacy, partitioned}pair so the reaper enumerates both keyspaces during cleanup.parseSqsPartitionedMsgByAgeKeywith the matching record typesqsPartitionedMsgByAgeRecord(legacyparseSqsMsgByAgeKeyis unchanged).appendU32for the 4-byte partition segment.What's NOT added
sqsMsgDataKey/sqsMsgVisKey/ etc. invocation keeps using the legacy constructor, so existing queues stay byte-identical on disk.partitionForis wired into the send/receive paths (per the §3.1 design choice of "dispatch at the call site, no variadic, no silent argument loss").Test plan
adapter/sqs_keys_test.gocovers:{legacy, partitioned}order.p|.(partition, gen).go test -race ./adapter/...clean.golangci-lint ./adapter/...clean.Self-review (per CLAUDE.md "Self-review of code changes")
Data loss — No FSM, Pebble, or retention path is touched. Legacy constructors are unchanged on every byte and call site, so existing queues are byte-identical on disk. The new partitioned helpers are dead code until PR 5 lifts the dormancy gate, so no production data lands under the partitioned prefix in this PR. No issue.
Concurrency / distributed failures — No new goroutine, lock, or Raft path. The constructors are pure byte-builders. The reaper helper returns a fresh slice per call. No issue.
Performance — New constructors are one allocation each, sized like the legacy ones. The reaper enumeration adds at most one extra
Rangeiteration per queue (over the partitioned prefix, which is empty for legacy queues). Hot path (Send/Receive) is untouched. No issue.Data consistency — The
p|discriminator + base32 queue segment combination is verified non-overlapping. Legacy and partitioned keyspaces cannot collide. Mutual-rejection tests assert each parser refuses the other's keyspace. No issue.Test coverage — 7 new test functions covering byte layout, per-partition isolation, determinism, round-trip parse, mutual rejection, reaper enumeration, and discriminator-constant invariants. PR 7 lands the HT-FIFO Jepsen suite per §11.