hashicorp / hashicorp/nomad

NamespaceIDTokenizer whole-string token compare breaks pagination across namespaces (e.g. team / team-a)

Open
#28,211 3 comments 0 reactions 0 assignees View on GitHub
hcc/jira theme/api type/bug
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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.