NamespaceIDTokenizer whole-string token compare breaks pagination across namespaces (e.g. team / team-a)
- Dominant language
- Go
- Stars
- 17k
- Forks
- 2.1k
- Avg merge
- 1d 9h
- Merged PRs (30d)
- 105
Description
## Overview
`NamespaceIDTokenizer` (`nomad/state/paginator/tokenizer.go`) builds a pagination
token of the form `"."` and compares it against the caller's
`next_token` as a whole string. That whole-string comparison does not match
the order the state store iterates the `(Namespace, ID)` index in, so paginating
across certain namespaces can duplicate some objects and make others
unreachable, with the cursor returning the same `next_token` forever.
This was found while working #28167 / #28178 (the `Job.Statuses` ModifyIndex
cursor regression). It is a separate, pre-existing bug with a wider blast radius,
split out per the maintainers' request so the #28178 backport stays clean.
## Affected code
`NamespaceIDTokenizer` is used by every endpoint that paginates on the
Namespace+ID cursor, including `Job.List`, Variables, CSI volumes, host volumes,
and service registrations. All of them share this behavior.
## Why it happens
The token is compared as one joined string, so the `.` separator (0x2E)
participates in the comparison. When one namespace name is a prefix of another
that continues with a byte lower than `.`, the joined strings order the opposite
way from the individual namespace names.
a good example is a dash: `-` is 0x2D, which is less than `.` (0x2E). So for
namespaces `team` and `team-a`:
"team.j1" vs "team-a.j1"
'.' 0x2E '-' 0x2D
`-` < `.`, so the whole-string compare orders `team-a...` before `team...`,
while the state store orders `team` before `team-a`. The cursor and the iterator
now disagree on where the boundary is.
I was incorrect originally when I framed it as memdb sorting differently from the endpoint - a
whole-string compare of `namespace.id` just isn't the correct comparison to make...as @tgross
pointed out on #28167, you can see the ordering flip in isolation:
https://go.dev/play/p/I-EYUEFW32R
## Reproduction
Harness: two namespaces `team` and `team-a`, 4 jobs each, `per_page=4`, walking
`/v1/jobs` and following `next_token`.
Script: https://github.com/afreidah/nomad/blob/repro-jobs-statuses-28132/repro-28132/ns-order-demo.sh
```
==> 2. Create namespaces 'team' and 'team-a' and submit 4 jobs in each
namespace team: submitted 4/4
namespace team-a: submitted 4/4
/v1/jobs total = 8
==> 3. The order /v1/jobs returns them in (one big page)
team/j1
team/j2
team/j3
team/j4
team-a/j1
team-a/j2
team-a/j3
team-a/j4
==> 4. Now page through /v1/jobs with per_page=4, following next_token
page 1: 4 job(s) next_token=team-a.j1
page 2: 4 job(s) next_token=team-a.j1
==> 5. Result
walk could not finish: page 2 returned the same next_token (team-a.j1) it
was given - repeats forever.
duplicated (returned on >1 page): team/j1 team/j2 team/j3 team/j4
never returned (exist in /v1/jobs but no page showed them):
team-a/j1 team-a/j2 team-a/j3 team-a/j4
```
So with `per_page=4` and 8 jobs, page 1 returns all four `team` jobs and hands
back `next_token=team-a.j1`. On page 2 the tokenizer compares each candidate's
`"team-a.jN"` token against the target `team-a.j1` as a whole string; because the
boundary is misplaced it re-selects the `team` jobs, emits the same
`next_token=team-a.j1`, and never advances into the `team-a` namespace. The walk
loops forever, `team` jobs are duplicated, and `team-a` jobs are never returned.
## Expected
Every object returned exactly once, in the state store's `(Namespace, ID)` order,
and the walk terminating.
## Fix direction
Compare the token field-by-field (namespace, then id) instead of as one joined
string, so the comparison matches the underlying index order regardless of which
separator byte the namespace names contain. The token *format* (`namespace.id`)
stays the same, so existing and in-flight `next_token`s remain valid across an
upgrade.
A rough cut of an implementation exists on my fork - it consolidates the four
pagination tokenizers onto a shared field-by-field helper and includes unit tests
for the `team`/`team-a` case plus a `Job.List` integration test that walks the two
namespaces (fails on `main`, passes with the change):
https://github.com/hashicorp/nomad/compare/main...afreidah:nomad:pagination-tokenizers-shared-helper
but I want to give this some more thought and play around with it a bit more before creating
any PRs on this just yet since this one covers a lot more turf than the previous ones.
Contributor guide
No contributing guide indexed for this repository
Research direction
Start in nomad/state/paginator/tokenizer.go and inspect NamespaceIDTokenizer and the endpoints that use the Namespace+ID cursor, especially Job.List. Run the linked ns-order-demo.sh reproduction with namespaces team and team-a, then verify pagination returns every object once, follows state-store order, and terminates without repeating next_token.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- go
- Domain
- api, backend-api-design
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Quiet
- Clarity
- Clearly specified
- Newbie friendliness
- 45/100