Diagnostic GitHub API
rows move between pages and the walk skips records
The sync reads the Link header, follows rel="next" to the very end and asks for a hundred items a page. It is, by every check in this section, a correct pagination loop. It also misses about one issue a night and occasionally imports the same one twice, and nobody can reproduce it, because reproducing it requires somebody to touch an issue during the eleven seconds the walk is passing over it.
Offset pagination is only stable if the ordering is. page=2 means "items 101 to 200 in the current sort", evaluated fresh at the moment page two is requested — so if the collection is sorted on a field that changes, an item touched between your two requests moves, everything behind it shifts by one, and the record on the boundary is never returned to you at all.
Sort on something immutable and ascending: sort=created&direction=asc. For incremental work use since=<timestamp> and deduplicate on id as you go. Where the walk is long or the collection busy, use the GraphQL API's cursors, which describe a position in the result rather than an offset into it.
The problem in plain words
Every other pagination bug in this section leaves a mark you can find later: a short page, a missing header, a count that does not add up. This one leaves nothing. Each individual response is correct, complete and internally consistent. The damage is in the seam between two responses, and the seam is not in either of them.
So the investigation goes to all the wrong places first. The loop gets reviewed and is fine. The page size gets raised and it changes nothing except the size of the gap. Somebody adds a retry, which cannot help, and somebody else adds logging, which records that the record was never seen — not that it was seen and dropped. The API gets blamed for losing data it returned exactly as asked.
The frequency is what makes it unfixable by staring at it. The window in which an edit can hurt you is the time between two consecutive requests, so the loss rate is roughly the write rate times the walk time, divided by the collection size. On a quiet repository that is zero for months. On a busy one it is one record a night, which is exactly the rate at which a problem is annoying enough to complain about and rare enough that nobody can catch it in the act.
Why it happens
An offset is a position in an ordering, not a bookmark on a record. When you ask for page two, GitHub sorts the collection as it exists at that moment and hands you the second slice of it. Nothing carries over from your first request; there is no snapshot and no cursor. If the ordering changed in between, the slice boundaries fall in different places, and the difference between where they fell the first time and where they fall now is the data you lose.
Skips and duplicates are not the same failure. If an item moves forward past your read position, everything behind it shifts back by one and one record slides from the top of page two to the bottom of page one, which you have already read: it is never returned. If an item is inserted at the head, everything shifts the other way and one record appears on both pages: you process it twice. Duplicates are visible and idempotency handles them. Skips are silent and idempotency does nothing at all for them.
Which one you get depends on the sort key, and it is a real distinction. An immutable key in ascending order — created, oldest first — only ever grows at the end you have not reached yet, so a walk over it can neither skip nor repeat. The same key descending has new rows arriving at the head, which shifts your window and repeats records, but never hides one. A mutable key such as updated lets any row move anywhere at any time, and that is the only combination that can lose data for good.
Correct pagination does not save you. This is the note for the client that got everything else right. Following rel="next" to the end is necessary and it is not sufficient, because the header describes where the next slice starts, not which records were in the previous one. The first-page-only bug and the clamped page size are both loop bugs with loop repairs. This one is repaired by changing two query parameters and touching the loop not at all.
A bigger page size helps a little and for the wrong reason. Raising per_page to 100 reduces the number of seams, because there are fewer requests and therefore fewer moments at which the ordering can change under you. It does not remove a single one of them. Treating it as the fix produces a job that loses a fifth as much data and is exactly as wrong.
The script proves the exposure and sometimes catches it in the act. Sorting on a mutable key is a property of your request that a read-only observer can read straight back. Whether it has actually cost you a record needs evidence, so the check walks the same window twice and diffs the id sets, and it is careful about what it counts: a row appearing only in the second walk of an ascending, immutable listing is the collection growing, not the walk failing, and calling that a finding would be a false alarm shipped to a reader.
The fix, as a flow
Two walks of the same window, back to back, and a diff of the id sets they collected. What counts as evidence depends on the ordering, which is why the interpretation is a function of its own: an id that shows up only in the second walk of an ascending immutable listing is the collection growing rather than the walk failing, and reporting that as a skip would be a false alarm shipped to a reader. The exposure is readable without any of that, straight off the sort key in your own request.
How to fix it
Write down the sort your request actually sends
Not the one you assume. If your code does not set sort and direction, the endpoint picks, and the choice is documented per endpoint rather than being one rule across the API. The script takes the sort as an argument and refuses to guess it, because a check that assumed the wrong default would give a confident answer about a request you never made.
Classify the key before you measure anything
updated, pushed, comments and popularity all change while you read. created does not. Ascending on an immutable key is the only combination that cannot lose you a record, and knowing which of the three you are in tells you whether you are looking for duplicates, for skips, or for nothing at all.
Walk the same window twice and diff the ids
Two walks of the first few pages, back to back, on the collection as it really is. Any id present in one and absent from the other is the ordering moving under the loop. On a quiet repository the diff will be empty, which is not a clean bill of health — it is a quiet hour, and the script says so rather than reporting a pass.
Count repeats inside a single walk too
The same id twice in one walk is the other half of the failure and it is proof on its own, without needing a second walk to compare against. It is also the friendlier half: a duplicate you can see is a duplicate you can deduplicate. The script reports the two kinds of evidence separately because they mean different things about what you have lost.
Move to an immutable sort, or to cursors
sort=created&direction=asc with per_page=100 turns the walk into an append-only read. For incremental syncs, add since and keep deduplicating on id, because overlap at the boundary is by design. For long walks over busy collections, the GraphQL API's cursors are stable against insertion and are the right tool. The check costs one request per page, per walk, and prints that number before it starts.
How to check it worked
After the sort changes, the two walks agree and the risk classification changes with them, which is the part worth checking: the evidence was always intermittent, but the exposure is constant and readable.
GITHUB_TOKEN=$READ_ONLY_TOKEN python3 github_unstable_sort.py \
--repo acme/monorepo --sort updated --direction desc --pages 3
# read cost: 6 request(s) against the core hourly quota
# sort=updated direction=desc: mutable key, so a row can move anywhere between
# two requests. Both skips and duplicates are possible
# walk 1 collected 300 id(s), walk 2 collected 300 id(s)
# proven-skips: 2 id(s) appeared in one walk and not the other
# repair: sort on an immutable key ascending, sort=created&direction=asc
# the same window, sorted on something that does not move
GITHUB_TOKEN=$READ_ONLY_TOKEN python3 github_unstable_sort.py \
--repo acme/monorepo --sort created --direction asc --pages 3
# stable-walk: created ascending only grows at the end you have not reached,
# so this walk can neither skip a record nor return one twiceThe full code
One request per page per walk, two walks, and a classification that does not need the network at all. The interesting part is what counts as evidence: a two-walk diff means different things depending on the sort, so an id that shows up only in the second walk of an ascending immutable listing is growth rather than instability, and the script drops it rather than reporting a finding it cannot stand behind. All of that is pure, so the rule can be argued with in the tests instead of in production.
"""Show that a paginated walk is being reordered underneath itself.
Read only. One GET per page per walk, two walks by default. Nothing is written
and the repair is printed rather than performed.
Offset pagination is only stable if the ordering is. page=2 means "items 101 to
200 in the current sort", evaluated when page two is asked for, so an item that
moves between two requests shifts everything behind it and the record on the
boundary is never returned at all.
What this can and cannot see: the exposure is readable from your own request,
because the sort key is in it. The damage is intermittent by nature, so an empty
diff means a quiet window rather than a safe walk, and the script says which of
the two it is looking at.
Environment:
GITHUB_TOKEN a token with read access to the repository
"""
import argparse
import json
import logging
import os
import re
import sys
import requests
logging.basicConfig(level=logging.INFO, format="%(asctime)s %(levelname)s %(message)s")
log = logging.getLogger("github_unstable_sort")
API = "https://api.github.com"
UA = "github-unstable-sort/1.0"
MAX_PER_PAGE = 100
# Keys whose value changes while you are reading the collection. A row sorted on
# one of these can move in either direction at any moment.
MUTABLE_SORTS = {"updated", "pushed", "comments", "popularity", "long-running",
"reactions", "interactions", "best-match", "relevance", "stars",
"forks", "help-wanted-issues"}
# Keys that are set once and never move afterwards.
IMMUTABLE_SORTS = {"created", "full_name", "id"}
# What GitHub applies when a request names a sort but no direction. Descending
# is the common default and it is the one that shifts a window.
DEFAULT_DIRECTION = "desc"
LINK = re.compile(r'<([^>]+)>\s*;\s*rel="([^"]+)"')
def parse_link(header):
"""Parse a Link header into {rel: url}. Pure."""
if not header:
return {}
return {rel: url for url, rel in LINK.findall(header)}
def normalize(ids):
"""Ids as strings, so two walks can be compared and sorted the same way."""
return [str(i) for i in (ids or [])]
def sort_kind(sort):
"""Whether this sort key moves while you read. Pure."""
key = str(sort or "").strip().lower()
if key in MUTABLE_SORTS:
return "mutable"
if key in IMMUTABLE_SORTS:
return "immutable"
return "unknown"
def walk_risk(sort, direction=None):
"""What a walk over this ordering can lose. Pure. Returns (risk, detail).
Three outcomes, not two, and the middle one is the reason this function
exists. An immutable key descending shifts your window when a row is
inserted at the head, which repeats records and never hides one. A mutable
key lets a row move past your read position, which hides it for good.
"""
kind = sort_kind(sort)
way = str(direction or DEFAULT_DIRECTION).strip().lower()
if kind == "unknown":
return ("unknown",
"%r is not a sort key this check knows, so name the one your "
"request actually sends." % (sort,))
if way not in ("asc", "desc"):
return ("unknown", "%r is not a direction." % (direction,))
if kind == "mutable":
return ("skips-and-duplicates",
"sort=%s is a key that changes while you read, so a row can "
"move anywhere between two requests. Both skips and duplicates "
"are possible and only one of them is visible." % sort)
if way == "desc":
return ("duplicates-only",
"sort=%s descending is stable per row, but new rows arrive at "
"the head and shift your window, so a record can be returned "
"twice. Nothing can be hidden." % sort)
return ("append-only",
"sort=%s ascending only grows at the end you have not reached yet, "
"so this walk can neither skip a record nor return one twice." % sort)
def duplicates_within(ids):
"""Ids returned more than once inside a single walk. Pure, sorted."""
seen, twice = set(), set()
for i in normalize(ids):
if i in seen:
twice.add(i)
seen.add(i)
return sorted(twice)
def compare_walks(first, second):
"""Diff two walks of the same window. Pure.
Reports the raw difference in both directions plus the repeats inside each
walk. Interpretation is deliberately somebody else's job, because what the
difference means depends on how the collection is sorted.
"""
a, b = normalize(first), normalize(second)
sa, sb = set(a), set(b)
return {
"missing": sorted(sa - sb),
"appeared": sorted(sb - sa),
"repeated": sorted(set(duplicates_within(a)) | set(duplicates_within(b))),
"first_count": len(a),
"second_count": len(b),
}
def evidence(risk, diff):
"""Which parts of a two-walk diff actually prove instability. Pure.
On an append-only walk, ids that show up only in the second pass are the
collection growing, which is not a finding and must not be reported as one.
On a window that shifts by design, set differences at the edges prove
nothing either way, so only repeats count.
"""
diff = diff or {}
if risk == "skips-and-duplicates":
return sorted(set(diff.get("missing") or []) | set(diff.get("appeared") or []))
if risk == "append-only":
return sorted(diff.get("missing") or [])
return []
def verdict(sort, direction=None, first=None, second=None):
"""Classify the ordering, and the evidence if there is any. Pure."""
risk, detail = walk_risk(sort, direction)
if risk == "unknown":
return ("unknown", detail)
if first is not None and second is not None:
diff = compare_walks(first, second)
proof = evidence(risk, diff)
if proof:
return ("proven-skips",
"%d id(s) appeared in one walk of this window and not the "
"other, so the ordering moved between the two reads and a "
"record on a page boundary was never returned."
% len(proof))
if diff["repeated"]:
return ("proven-duplicates",
"%d id(s) came back twice inside a single walk, so the "
"window shifted mid read. Nothing was hidden, but the job "
"processed a record more than once." % len(diff["repeated"]))
if risk == "skips-and-duplicates":
return ("exposed",
detail + " The two walks agreed this time, which is a quiet "
"window rather than a safe walk.")
if risk == "duplicates-only":
return ("insertion-shift", detail)
return ("stable-walk", detail)
def stable_params(per_page=MAX_PER_PAGE, since=None):
"""The request that makes the walk safe. Pure."""
params = {"sort": "created", "direction": "asc", "per_page": int(per_page)}
if since:
params["since"] = since
return params
def repair(state):
"""The sentence a reader has to act on. Pure."""
if state in ("proven-skips", "exposed"):
return ("sort on an immutable key ascending, sort=created&direction=asc, "
"so the collection only grows at the end you have not reached. "
"For incremental work add since=<timestamp> and deduplicate on "
"id, and for long walks use GraphQL cursors instead of offsets.")
if state in ("proven-duplicates", "insertion-shift"):
return ("deduplicate on id as you go, and prefer direction=asc so new "
"rows land behind your read position instead of in front of "
"it. Nothing is being lost here, but the same record is being "
"processed more than once.")
if state == "stable-walk":
return ("nothing on the ordering. Keep per_page at 100 to reduce the "
"number of seams, and keep the sort where it is.")
return "name the sort and direction your request actually sends."
def read_cost(pages, walks=2):
"""Requests this run will spend against the core quota. Pure."""
try:
return max(0, int(pages)) * max(0, int(walks))
except (TypeError, ValueError):
return 0
def walk_once(session, path, params, pages):
"""Follow rel=next for at most `pages` pages, collecting ids."""
ids, url, query = [], API + path, dict(params)
for _ in range(max(1, pages)):
r = session.get(url, params=query, timeout=30)
if r.status_code == 401:
raise SystemExit("401 from GitHub: GITHUB_TOKEN is missing, "
"malformed or revoked")
if r.status_code == 403 and "rate limit" in r.text.lower():
raise SystemExit("403 rate limited. GET /rate_limit reports the "
"reset time and does not itself consume quota")
if r.status_code != 200:
log.info("%s returned %d; stopping this walk", url, r.status_code)
break
try:
items = r.json()
except ValueError:
break
if not isinstance(items, list):
break
ids.extend(item.get("id") for item in items if isinstance(item, dict))
nxt = parse_link(r.headers.get("Link")).get("next")
if not nxt:
break
# The next URL already carries the query, so it is followed exactly as
# given rather than rebuilt from the parameters.
url, query = nxt, {}
return normalize(ids)
def main():
ap = argparse.ArgumentParser(description=__doc__)
ap.add_argument("--repo", required=True, help="owner/name")
ap.add_argument("--path", help="API path to walk, default the repo's issues")
ap.add_argument("--sort", required=True,
help="the sort your request actually sends, e.g. updated")
ap.add_argument("--direction", default=DEFAULT_DIRECTION,
choices=("asc", "desc"))
ap.add_argument("--pages", type=int, default=3,
help="pages per walk. Two walks are made.")
ap.add_argument("--per-page", type=int, default=MAX_PER_PAGE)
args = ap.parse_args()
token = os.environ.get("GITHUB_TOKEN")
if not token:
log.error("set GITHUB_TOKEN (a read-only token is enough)")
return 2
path = args.path or "/repos/%s/issues" % args.repo
log.info("read cost: %d request(s) against the core hourly quota",
read_cost(args.pages, 2))
risk, detail = walk_risk(args.sort, args.direction)
log.info("sort=%s direction=%s: %s", args.sort, args.direction, detail)
session = requests.Session()
session.headers.update({
"Authorization": "Bearer " + token,
"Accept": "application/vnd.github+json",
"X-GitHub-Api-Version": "2022-11-28",
# GitHub rejects requests with no User-Agent outright.
"User-Agent": UA,
})
params = {"sort": args.sort, "direction": args.direction,
"per_page": args.per_page}
first = walk_once(session, path, params, args.pages)
second = walk_once(session, path, params, args.pages)
log.info("walk 1 collected %d id(s), walk 2 collected %d id(s)",
len(first), len(second))
diff = compare_walks(first, second)
state, verdict_detail = verdict(args.sort, args.direction, first, second)
log.info("%s: %s", state, verdict_detail)
log.info("repair: %s", repair(state))
print(json.dumps({
"requests_spent": read_cost(args.pages, 2),
"path": path,
"sort": args.sort,
"direction": args.direction,
"sort_kind": sort_kind(args.sort),
"risk": risk,
"diff": diff,
"evidence": evidence(risk, diff),
"state": state,
"detail": verdict_detail,
"stable_params": stable_params(args.per_page),
"repair": repair(state),
}, indent=2, default=str))
return 1 if state in ("proven-skips", "proven-duplicates", "exposed") else 0
if __name__ == "__main__":
sys.exit(main())
/**
* Show that a paginated walk is being reordered underneath itself.
*
* Read only. One GET per page per walk, two walks. Nothing is written and the
* repair is printed rather than performed.
*
* Environment:
* GITHUB_TOKEN a token with read access to the repository
* GITHUB_REPO owner/name
* GITHUB_PATH API path to walk, default the repo's issues
* GITHUB_SORT the sort your request actually sends, e.g. updated
* GITHUB_DIRECTION asc or desc, default desc
* GITHUB_PAGES pages per walk, default 3
*/
const API = 'https://api.github.com';
const UA = 'github-unstable-sort/1.0';
export const MAX_PER_PAGE = 100;
/** Keys whose value changes while you are reading the collection. */
export const MUTABLE_SORTS = new Set(['updated', 'pushed', 'comments', 'popularity',
'long-running', 'reactions', 'interactions', 'best-match', 'relevance', 'stars',
'forks', 'help-wanted-issues']);
/** Keys that are set once and never move afterwards. */
export const IMMUTABLE_SORTS = new Set(['created', 'full_name', 'id']);
/** What GitHub applies when a request names a sort but no direction. */
export const DEFAULT_DIRECTION = 'desc';
const LINK = /<([^>]+)>\s*;\s*rel="([^"]+)"/g;
/** Parse a Link header into {rel: url}. Pure. */
export function parseLink(header) {
const out = {};
if (!header) return out;
for (const m of String(header).matchAll(LINK)) out[m[2]] = m[1];
return out;
}
/** Ids as strings, so two walks compare and sort the same way. Pure. */
export function normalize(ids) {
return (ids || []).map((i) => String(i));
}
/** Whether this sort key moves while you read. Pure. */
export function sortKind(sort) {
const key = String(sort ?? '').trim().toLowerCase();
if (MUTABLE_SORTS.has(key)) return 'mutable';
if (IMMUTABLE_SORTS.has(key)) return 'immutable';
return 'unknown';
}
/** What a walk over this ordering can lose. Pure. Returns [risk, detail]. */
export function walkRisk(sort, direction = null) {
const kind = sortKind(sort);
const way = String(direction ?? DEFAULT_DIRECTION).trim().toLowerCase();
if (kind === 'unknown') {
return ['unknown',
`${sort} is not a sort key this check knows, so name the one your request `
+ 'actually sends.'];
}
if (way !== 'asc' && way !== 'desc') {
return ['unknown', `${direction} is not a direction.`];
}
if (kind === 'mutable') {
return ['skips-and-duplicates',
`sort=${sort} is a key that changes while you read, so a row can move `
+ 'anywhere between two requests. Both skips and duplicates are possible '
+ 'and only one of them is visible.'];
}
if (way === 'desc') {
return ['duplicates-only',
`sort=${sort} descending is stable per row, but new rows arrive at the `
+ 'head and shift your window, so a record can be returned twice. Nothing '
+ 'can be hidden.'];
}
return ['append-only',
`sort=${sort} ascending only grows at the end you have not reached yet, so `
+ 'this walk can neither skip a record nor return one twice.'];
}
/** Ids returned more than once inside a single walk. Pure, sorted. */
export function duplicatesWithin(ids) {
const seen = new Set();
const twice = new Set();
for (const i of normalize(ids)) {
if (seen.has(i)) twice.add(i);
seen.add(i);
}
return [...twice].sort();
}
/** Diff two walks of the same window. Pure. */
export function compareWalks(first, second) {
const a = normalize(first);
const b = normalize(second);
const sa = new Set(a);
const sb = new Set(b);
return {
missing: [...sa].filter((i) => !sb.has(i)).sort(),
appeared: [...sb].filter((i) => !sa.has(i)).sort(),
repeated: [...new Set([...duplicatesWithin(a), ...duplicatesWithin(b)])].sort(),
first_count: a.length,
second_count: b.length,
};
}
/** Which parts of a two-walk diff actually prove instability. Pure. */
export function evidence(risk, diff) {
const d = diff || {};
if (risk === 'skips-and-duplicates') {
return [...new Set([...(d.missing || []), ...(d.appeared || [])])].sort();
}
if (risk === 'append-only') return [...(d.missing || [])].sort();
return [];
}
/** Classify the ordering, and the evidence if there is any. Pure. */
export function verdict(sort, direction = null, first = null, second = null) {
const [risk, detail] = walkRisk(sort, direction);
if (risk === 'unknown') return ['unknown', detail];
if (first !== null && second !== null) {
const diff = compareWalks(first, second);
const proof = evidence(risk, diff);
if (proof.length) {
return ['proven-skips',
`${proof.length} id(s) appeared in one walk of this window and not the `
+ 'other, so the ordering moved between the two reads and a record on a '
+ 'page boundary was never returned.'];
}
if (diff.repeated.length) {
return ['proven-duplicates',
`${diff.repeated.length} id(s) came back twice inside a single walk, so `
+ 'the window shifted mid read. Nothing was hidden, but the job '
+ 'processed a record more than once.'];
}
}
if (risk === 'skips-and-duplicates') {
return ['exposed',
`${detail} The two walks agreed this time, which is a quiet window rather `
+ 'than a safe walk.'];
}
if (risk === 'duplicates-only') return ['insertion-shift', detail];
return ['stable-walk', detail];
}
/** The request that makes the walk safe. Pure. */
export function stableParams(perPage = MAX_PER_PAGE, since = null) {
const params = { sort: 'created', direction: 'asc', per_page: Number(perPage) };
if (since) params.since = since;
return params;
}
/** The sentence a reader has to act on. Pure. */
export function repair(state) {
if (state === 'proven-skips' || state === 'exposed') {
return 'sort on an immutable key ascending, sort=created&direction=asc, so '
+ 'the collection only grows at the end you have not reached. For '
+ 'incremental work add since=<timestamp> and deduplicate on id, and for '
+ 'long walks use GraphQL cursors instead of offsets.';
}
if (state === 'proven-duplicates' || state === 'insertion-shift') {
return 'deduplicate on id as you go, and prefer direction=asc so new rows '
+ 'land behind your read position instead of in front of it. Nothing is '
+ 'being lost here, but the same record is being processed more than once.';
}
if (state === 'stable-walk') {
return 'nothing on the ordering. Keep per_page at 100 to reduce the number '
+ 'of seams, and keep the sort where it is.';
}
return 'name the sort and direction your request actually sends.';
}
/** Requests this run will spend against the core quota. Pure. */
export function readCost(pages, walks = 2) {
const p = Number(pages);
const w = Number(walks);
if (!Number.isFinite(p) || !Number.isFinite(w)) return 0;
return Math.max(0, Math.trunc(p)) * Math.max(0, Math.trunc(w));
}
function headersFor(token) {
return {
Authorization: `Bearer ${token}`,
Accept: 'application/vnd.github+json',
'X-GitHub-Api-Version': '2022-11-28',
'User-Agent': UA,
};
}
async function walkOnce(token, path, params, pages) {
const ids = [];
const url = new URL(API + path);
for (const [k, v] of Object.entries(params)) url.searchParams.set(k, String(v));
let next = url.toString();
for (let i = 0; i < Math.max(1, pages) && next; i += 1) {
const res = await fetch(next, { headers: headersFor(token) });
if (!res.ok) {
console.log(`${next} returned ${res.status}; stopping this walk`);
break;
}
let items = null;
try { items = await res.json(); } catch { items = null; }
if (!Array.isArray(items)) break;
for (const item of items) if (item && item.id !== undefined) ids.push(item.id);
next = parseLink(res.headers.get('link')).next || null;
}
return normalize(ids);
}
async function main() {
const token = process.env.GITHUB_TOKEN;
const repo = process.env.GITHUB_REPO;
const sort = process.env.GITHUB_SORT;
if (!token || !repo || !sort) {
console.error('set GITHUB_TOKEN (read-only is enough), GITHUB_REPO=owner/name '
+ 'and GITHUB_SORT=updated');
process.exitCode = 2;
return;
}
const direction = process.env.GITHUB_DIRECTION || DEFAULT_DIRECTION;
const pages = Number(process.env.GITHUB_PAGES || 3);
const path = process.env.GITHUB_PATH || `/repos/${repo}/issues`;
console.log(`read cost: ${readCost(pages, 2)} request(s) against the core hourly quota`);
const [risk, detail] = walkRisk(sort, direction);
console.log(`sort=${sort} direction=${direction}: ${detail}`);
const params = { sort, direction, per_page: MAX_PER_PAGE };
const first = await walkOnce(token, path, params, pages);
const second = await walkOnce(token, path, params, pages);
console.log(`walk 1 collected ${first.length} id(s), walk 2 collected ${second.length} id(s)`);
const diff = compareWalks(first, second);
const [state, verdictDetail] = verdict(sort, direction, first, second);
console.log(`${state}: ${verdictDetail}`);
console.log(`repair: ${repair(state)}`);
console.log(JSON.stringify({
requests_spent: readCost(pages, 2),
path,
sort,
direction,
sort_kind: sortKind(sort),
risk,
diff,
evidence: evidence(risk, diff),
state,
detail: verdictDetail,
stable_params: stableParams(MAX_PER_PAGE),
repair: repair(state),
}, null, 2));
process.exitCode = ['proven-skips', 'proven-duplicates', 'exposed'].includes(state) ? 1 : 0;
}
// Guarded so importing this file from the test runner does not start a run.
if (import.meta.url === `file://${process.argv[1]}`) {
main().catch((err) => { console.error(err.message); process.exitCode = 2; });
}
Add a test
Three tests carry the note. The first is that the risk classification has three outcomes rather than two, because an immutable key descending can repeat a record and can never hide one, and collapsing that into "unstable" would send a reader chasing data that was never lost. The second is that evidence is interpreted against the ordering, so growth in an append-only walk is not reported as a skip. The third is that an empty diff on a mutable sort comes back as exposure rather than as a pass. The rest pins the diff, the repairs, and the cost of the two walks.
from github_unstable_sort import (
DEFAULT_DIRECTION, compare_walks, duplicates_within, evidence, normalize,
parse_link, read_cost, repair, sort_kind, stable_params, verdict, walk_risk,
)
def test_sort_keys_are_sorted_into_movers_and_non_movers():
assert sort_kind("updated") == "mutable"
assert sort_kind("PUSHED") == "mutable"
assert sort_kind("comments") == "mutable"
assert sort_kind("created") == "immutable"
assert sort_kind("full_name") == "immutable"
assert sort_kind("banana") == "unknown"
assert sort_kind(None) == "unknown"
def test_the_risk_has_three_outcomes_not_two():
assert walk_risk("updated", "desc")[0] == "skips-and-duplicates"
assert walk_risk("updated", "asc")[0] == "skips-and-duplicates"
assert walk_risk("created", "desc")[0] == "duplicates-only"
assert walk_risk("created", "asc")[0] == "append-only"
assert walk_risk("banana", "asc")[0] == "unknown"
assert walk_risk("created", "sideways")[0] == "unknown"
def test_a_missing_direction_is_treated_as_the_one_that_shifts():
assert DEFAULT_DIRECTION == "desc"
assert walk_risk("created")[0] == "duplicates-only"
def test_only_the_mutable_key_can_hide_a_record():
assert "hidden" in walk_risk("created", "desc")[1]
assert "neither skip" in walk_risk("created", "asc")[1]
assert "only one of them is visible" in walk_risk("updated", "desc")[1]
def test_repeats_inside_one_walk_are_found_and_deduplicated():
assert duplicates_within([1, 2, 2, 3, 3, 3]) == ["2", "3"]
assert duplicates_within([1, 2, 3]) == []
assert duplicates_within([]) == []
assert duplicates_within(None) == []
def test_ids_are_compared_as_strings_so_two_walks_line_up():
assert normalize([1, "1", 2]) == ["1", "1", "2"]
diff = compare_walks([1, 2, 3], ["1", "2", "4"])
assert diff["missing"] == ["3"]
assert diff["appeared"] == ["4"]
assert diff["first_count"] == 3
def test_growth_in_an_append_only_walk_is_not_a_finding():
diff = compare_walks([1, 2, 3], [1, 2, 3, 4])
assert evidence("append-only", diff) == []
assert evidence("skips-and-duplicates", diff) == ["4"]
def test_a_shifting_window_proves_nothing_from_set_differences():
diff = compare_walks([1, 2, 3], [0, 1, 2])
assert evidence("duplicates-only", diff) == []
assert evidence("append-only", diff) == ["3"]
def test_a_record_in_one_walk_and_not_the_other_is_the_finding():
state, detail = verdict("updated", "desc", [1, 2, 3], [1, 2, 4])
assert state == "proven-skips"
assert "never returned" in detail
def test_a_repeat_inside_a_walk_is_reported_as_the_gentler_failure():
state, detail = verdict("created", "desc", [1, 2, 2, 3], [1, 2, 3])
assert state == "proven-duplicates"
assert "Nothing was hidden" in detail
def test_agreeing_walks_on_a_mutable_sort_are_exposure_not_a_pass():
state, detail = verdict("updated", "desc", [1, 2, 3], [1, 2, 3])
assert state == "exposed"
assert "quiet window rather than a safe walk" in detail
def test_the_safe_ordering_comes_back_clean():
assert verdict("created", "asc", [1, 2, 3], [1, 2, 3])[0] == "stable-walk"
assert verdict("created", "desc", [1, 2, 3], [1, 2, 3])[0] == "insertion-shift"
assert verdict("banana", "asc", [1], [1])[0] == "unknown"
def test_a_walk_with_no_evidence_still_gets_classified():
assert verdict("updated", "desc")[0] == "exposed"
assert verdict("created", "asc")[0] == "stable-walk"
def test_the_repairs_are_different_for_skips_and_for_duplicates():
assert "sort=created&direction=asc" in repair("proven-skips")
assert "since=" in repair("exposed")
assert "deduplicate on id" in repair("proven-duplicates")
assert "Nothing is being lost" in repair("insertion-shift")
assert repair("stable-walk").startswith("nothing on the ordering")
def test_the_printed_repair_is_a_request_you_can_send():
assert stable_params() == {"sort": "created", "direction": "asc", "per_page": 100}
assert stable_params(50, "2026-01-01T00:00:00Z")["since"] == "2026-01-01T00:00:00Z"
def test_the_walk_follows_the_header_rather_than_counting_pages():
header = ('<https://api.github.com/repos/o/n/issues?labels=bug,ci&page=2>; rel="next", '
'<https://api.github.com/repos/o/n/issues?labels=bug,ci&page=9>; rel="last"')
assert set(parse_link(header)) == {"next", "last"}
assert parse_link(None) == {}
def test_two_walks_cost_twice_what_one_does():
assert read_cost(3) == 6
assert read_cost(3, 1) == 3
assert read_cost(0) == 0
assert read_cost(None) == 0
import { test } from 'node:test';
import assert from 'node:assert/strict';
import {
DEFAULT_DIRECTION, compareWalks, duplicatesWithin, evidence, normalize,
parseLink, readCost, repair, sortKind, stableParams, verdict, walkRisk,
} from './github-unstable-sort.mjs';
test('sort keys are sorted into movers and non-movers', () => {
assert.equal(sortKind('updated'), 'mutable');
assert.equal(sortKind('PUSHED'), 'mutable');
assert.equal(sortKind('comments'), 'mutable');
assert.equal(sortKind('created'), 'immutable');
assert.equal(sortKind('full_name'), 'immutable');
assert.equal(sortKind('banana'), 'unknown');
assert.equal(sortKind(null), 'unknown');
});
test('the risk has three outcomes, not two', () => {
assert.equal(walkRisk('updated', 'desc')[0], 'skips-and-duplicates');
assert.equal(walkRisk('updated', 'asc')[0], 'skips-and-duplicates');
assert.equal(walkRisk('created', 'desc')[0], 'duplicates-only');
assert.equal(walkRisk('created', 'asc')[0], 'append-only');
assert.equal(walkRisk('banana', 'asc')[0], 'unknown');
assert.equal(walkRisk('created', 'sideways')[0], 'unknown');
});
test('a missing direction is treated as the one that shifts', () => {
assert.equal(DEFAULT_DIRECTION, 'desc');
assert.equal(walkRisk('created')[0], 'duplicates-only');
});
test('only the mutable key can hide a record', () => {
assert.match(walkRisk('created', 'desc')[1], /hidden/);
assert.match(walkRisk('created', 'asc')[1], /neither skip/);
assert.match(walkRisk('updated', 'desc')[1], /only one of them is visible/);
});
test('repeats inside one walk are found and deduplicated', () => {
assert.deepEqual(duplicatesWithin([1, 2, 2, 3, 3, 3]), ['2', '3']);
assert.deepEqual(duplicatesWithin([1, 2, 3]), []);
assert.deepEqual(duplicatesWithin([]), []);
assert.deepEqual(duplicatesWithin(null), []);
});
test('ids are compared as strings so two walks line up', () => {
assert.deepEqual(normalize([1, '1', 2]), ['1', '1', '2']);
const diff = compareWalks([1, 2, 3], ['1', '2', '4']);
assert.deepEqual(diff.missing, ['3']);
assert.deepEqual(diff.appeared, ['4']);
assert.equal(diff.first_count, 3);
});
test('growth in an append-only walk is not a finding', () => {
const diff = compareWalks([1, 2, 3], [1, 2, 3, 4]);
assert.deepEqual(evidence('append-only', diff), []);
assert.deepEqual(evidence('skips-and-duplicates', diff), ['4']);
});
test('a shifting window proves nothing from set differences', () => {
const diff = compareWalks([1, 2, 3], [0, 1, 2]);
assert.deepEqual(evidence('duplicates-only', diff), []);
assert.deepEqual(evidence('append-only', diff), ['3']);
});
test('a record in one walk and not the other is the finding', () => {
const [state, detail] = verdict('updated', 'desc', [1, 2, 3], [1, 2, 4]);
assert.equal(state, 'proven-skips');
assert.match(detail, /never returned/);
});
test('a repeat inside a walk is reported as the gentler failure', () => {
const [state, detail] = verdict('created', 'desc', [1, 2, 2, 3], [1, 2, 3]);
assert.equal(state, 'proven-duplicates');
assert.match(detail, /Nothing was hidden/);
});
test('agreeing walks on a mutable sort are exposure, not a pass', () => {
const [state, detail] = verdict('updated', 'desc', [1, 2, 3], [1, 2, 3]);
assert.equal(state, 'exposed');
assert.match(detail, /quiet window rather than a safe walk/);
});
test('the safe ordering comes back clean', () => {
assert.equal(verdict('created', 'asc', [1, 2, 3], [1, 2, 3])[0], 'stable-walk');
assert.equal(verdict('created', 'desc', [1, 2, 3], [1, 2, 3])[0], 'insertion-shift');
assert.equal(verdict('banana', 'asc', [1], [1])[0], 'unknown');
});
test('a walk with no evidence still gets classified', () => {
assert.equal(verdict('updated', 'desc')[0], 'exposed');
assert.equal(verdict('created', 'asc')[0], 'stable-walk');
});
test('the repairs are different for skips and for duplicates', () => {
assert.match(repair('proven-skips'), /sort=created&direction=asc/);
assert.match(repair('exposed'), /since=/);
assert.match(repair('proven-duplicates'), /deduplicate on id/);
assert.match(repair('insertion-shift'), /Nothing is being lost/);
assert.ok(repair('stable-walk').startsWith('nothing on the ordering'));
});
test('the printed repair is a request you can send', () => {
assert.deepEqual(stableParams(), { sort: 'created', direction: 'asc', per_page: 100 });
assert.equal(stableParams(50, '2026-01-01T00:00:00Z').since, '2026-01-01T00:00:00Z');
});
test('the walk follows the header rather than counting pages', () => {
const header = '<https://api.github.com/repos/o/n/issues?labels=bug,ci&page=2>; rel="next", '
+ '<https://api.github.com/repos/o/n/issues?labels=bug,ci&page=9>; rel="last"';
assert.deepEqual(Object.keys(parseLink(header)).sort(), ['last', 'next']);
assert.deepEqual(parseLink(null), {});
});
test('two walks cost twice what one does', () => {
assert.equal(readCost(3), 6);
assert.equal(readCost(3, 1), 3);
assert.equal(readCost(0), 0);
assert.equal(readCost(null), 0);
});
FAQ
Is this just the pagination bug again?
No. Every other pagination note in this section is about a loop that stopped too early or read the wrong thing: the header was ignored, the page size was clamped, the page parameter did nothing. Here the loop is correct and the ordering is not. You can follow rel=next perfectly to the end of a collection and still never be handed a record, because the record moved to a page you had already read. The repair changes two query parameters and leaves the loop alone.
Does a bigger page size fix it?
It reduces the exposure and does not remove it. Each request is a moment at which the ordering can change, so ten requests at per_page=100 have a tenth as many seams as a hundred requests at 30. The seams that remain behave exactly as before. per_page=100 is worth setting for its own reasons; treating it as the fix for this gives you a job that loses less data and is no more correct.
Why is sorting by created ascending safe when descending is not?
Because of where new rows land. Ascending, oldest first, new records are appended after the position you have already passed, so they cannot shift anything you are about to read. Descending, new records arrive at the head, everything moves down by one, and a record you have already seen is served to you again on the next page. That is a duplicate rather than a skip, which is the friendlier of the two failures, but the walk is still not stable.
What is the default sort on the endpoint I am using?
Look it up for that endpoint rather than assuming, because it is documented per endpoint and it is not one rule across the API. The script takes the sort as a required argument for exactly this reason: a check that guessed the default would report confidently on a request you never sent. If your code does not set sort and direction explicitly, set them, if only so the next person can tell what you are relying on.
Does GraphQL have the same problem?
Not in the same way. GraphQL pagination is cursor-based: a cursor names a position in the result set rather than an offset into it, so a row inserted or updated elsewhere does not renumber everything behind your position. That makes it the right tool for long walks over busy collections. It has its own costs in points and node limits, but the instability this note is about is not one of them.
Related field notes
- Only the first page is ever read
- per_page above 100 is clamped silently
- The job polls what a webhook would push
Sources
Every figure in this note is traced to one of these. Prices are list rates and change — check them for your own region before acting.
- Using pagination in the REST API — GitHub Docs
- Issues — GitHub REST API
- Best practices for using the REST API — GitHub Docs
- Repositories — GitHub REST API
If your setup is misbehaving in a way this note does not cover, message me on LinkedIn with what you are seeing.