paginator: fix tokenizer comparison of composite index and ID

[chrisroberts]

Description

The CreateIndexAndIDTokenizer creates a composite token by
combining the create index value and ID from the object with
a .. Tokens are then compared lexicographically. The comparison
is appropriate for the ID segment of the token, but it is not for
the create index segement. Since the create index values are stored
with numeric ordering, using a lexicographical comparison can cause
unexpected results.

For example, when comparing the token 12.object-id to 102.object-id
the result will show 12.object-id being greater. This is the
correct comparison but it is incorrect for the intention of the token.
With the knowledge of the composition of the token, the response
should be that 12.object-id is less.

The unexpected behavior can be seen when performing lists (like listing
allocations). The behavior is encountered inconsistently due to
two requirements which must be met:

1. Create index values with a large enough span (ex: 12 and 102)
2. Correct per page value to get a "bad" next token (ex: prefix with 102)

To prevent the unexpected behavior, the target token is split
and the components are used individually to compare against the
object.

Testing & Reproduction steps

1. Create a pageable number of allocations and space creation over a long enough timespan for the CreateIndex to reach three digits
2. List allocations and paginate the response such that the NextToken value is at the start of the three digit CreateIndex values
3. Request next page of results and view entries from start of list

Example

A simple script was used to cycle through page sizes, listing allocations and checking for duplicate objects. It displays where the comparison results in unexpected behavior:

Completed loop 138 (size: 3 next_token: "88.aef58062-8cd8-e5ba-33e2-f3ebe0054b0b")
  -> Item ID: 88.aef58062-8cd8-e5ba-33e2-f3ebe0054b0b
  -> Item ID: 101.96f23439-8921-572e-70fd-71a724a56b85
  -> Item ID: 117.5eb20d56-59eb-91e4-c92e-fc17bd714f3b
Completed loop 139 (size: 3 next_token: "117.d0ae8856-7863-80f1-abaa-52c05172449f")
  -> Item ID: 12.00438448-6b52-024d-1efd-ed1ace4147b4
ERROR - Item ID (12.00438448-6b52-024d-1efd-ed1ace4147b4) already seen on loop number 1, current index: 0

Links

#25435

Contributor Checklist

• Changelog Entry If this PR changes user-facing behavior, please generate and add a
  changelog entry using the make cl command.
• Testing Please add tests to cover any new functionality or to demonstrate bug fixes and
  ensure regressions will be caught.
• Documentation If the change impacts user-facing functionality such as the CLI, API, UI,
  and job configuration, please update the Nomad website documentation to reflect this. Refer to
  the website README for docs guidelines. Please also consider whether the
  change requires notes within the upgrade guide.

Reviewer Checklist

• Backport Labels Please add the correct backport labels as described by the internal
  backporting document.
• Commit Type Ensure the correct merge method is selected which should be "squash and merge"
  in the majority of situations. The main exceptions are long-lived feature branches or merges where
  history should be preserved.
• Enterprise PRs If this is an enterprise only PR, please add any required changelog entry
  within the public repository.

[tgross]

LGTM!

A bit embarrassing that I didn't catch this when I touched a bunch of this code in #25252 😊

[tgross]

This is a good commit message title, but for the changelog we try to describe this in user-visible terms. (If it weren't user-visible, we wouldn't have a changelog entry for it.) So something like:

api: Fixed a bug in pagination when there were more than 100 items in the set

[tgross]

@chrisroberts I've added the backport label for 1.10.x, but as noted in the sidebar discussion in Slack this isn't going to merge cleanly for 1.9.x+ent and 1.8.x+ent, so up to you as to whether you just want to do that by hand as a separate changset (I'd probably go for that just to avoid having to mess with backport assistant if it's not going to help).

[tgross]

LGTM!

[github-actions]

I'm going to lock this pull request because it has been closed for 120 days ⏳. This helps our maintainers find and focus on the active contributions.
If you have found a problem that seems related to this change, please open a new issue and complete the issue template so we can capture all the details necessary to investigate further.