← 1.0.0 scope SAPE-34

hashRange — a digest of a stretch of keys, without moving it

Status
Done
Shipped in
1.0.0 — b11b66e
Component
server
Priority
High — with SAPE-32 it is enough on its own for the use that prompted it
Blocked by
—
Blocks
SAPE-33

What it is, and why it comes before concatRange

Read the values of a key range in key order, join them with nothing between, and return a SHA-256 of the result. The range never leaves the server and the whole value never exists anywhere: a digest is computed incrementally, a chunk at a time.

Its output is thirty-two bytes whatever the input, which is the property that decides its position. SAPE-33 waits on a size ceiling (SAPE-31) because its output grows with its input. This one needs no ceiling on output at all, so it can ship first and independently.

For the application that prompted both — a ten-megabyte file split into two-kilobyte rows on a server with little memory — this plus SAPE-32 is the whole requirement. The rows stay where they are, the application writes one pointer row and reads them back with scan, and hashRange answers the only question that could not be answered without moving everything: did all of it arrive, and is it still what it was?

The decision this ticket has to make: what is hashed

This is not obvious and getting it wrong makes the feature useless rather than wrong-looking.

Binary is stored as base64 text today, because a string cannot carry arbitrary bytes — measured: the byte 0xFF is silently replaced with U+FFFD. So hashing the values as stored produces the SHA-256 of a base64 transcript, which will never equal the hash a client computed from the original file. Two correct systems would disagree forever, and the disagreement would look like corruption.

Two ways out, and they are not exclusive:

  1. A declared decode on the operation — "base64" or nothing. The engine decodes each value before feeding it to the digest, and still holds only a chunk, because a hash is incremental. This works today, against data that already exists.
  2. A real bytes type — SAPE-31. Then a bytes field needs no decode at all, because what is stored is what is hashed.

The recommendation is to take the first and let the second make it unnecessary. decode is a declared enumeration, in the same family as an index field's missing: skip | first | last — it is a choice written into the declaration, not an expression a caller composes. It ships without waiting for the type work, and it keeps working afterwards for data that is already base64.

The rules it shares with concatRange, and why

The three layers

Engine: yes. Cost is bounded by the row limit; output is fixed at thirty-two bytes; memory is one chunk at a time. It is the safest of the three primitives on this board.

Shell: a command beside scan taking the same bounds and printing the digest. An operator checking whether a stored file is intact is exactly the person who wants it at a prompt.

Driver: a declared operation with from, to and the declaration carrying field, decode and limit. No expression; the caller supplies bounds.

The ceiling is counted, not trusted

These three primitives are the first things in this store that walk a range at run time. Everything before them is bounded by construction: a declaration cannot express a loop, because a step pins operation@version, version numbers only ever rise, and a pinned reference resolves only to a version that already exists — so a cycle would need a version to exist before it was declared. The reference graph is a directed acyclic graph because nothing can build anything else, which is why ceiling() can compute a total at declare time and why nothing counts during a run.

That property does not survive a thing that walks. So the limit on this operation is a ceiling the host counts against while walking, not a number the host takes on trust, and it is counted per run of the operation rather than per underlying call. At the ceiling the operation stops and refuses; it does not return a shortened answer, because a truncated result is indistinguishable from a complete one.

The reason to write this down rather than assume it is measured, in pipelines/tasks/0071, measurement W7. An external operation declaring limit 50, correctly sandboxed and correctly signed, served 50,000,000 rows in one call — one million calls of a host function that served fifty each — because the host checked every individual call and never the total. A signature proves whose binary it is. A sandbox proves it does not escape. Neither proves what it costs. That gap is not open today because nothing can loop; it opens the moment something can.

What is counted here is rows read. The answer is thirty-two bytes however far it walked, which is exactly why the work needs a ceiling that the size of the answer will never reveal.

What shipped, and what it measured

Landed in b11b66e, CI green on both jobs. It is the tenth action, not the ninth — the brief that commissioned it miscounted its own list.

Criterion 1, the one that matters, was measured against the bytes and not against this package. Six megabytes in 3,072 rows of two kilobytes, decode: "base64". The store answered 414e4d5e45d7d69fbb96636e4c234a97078bbe4f332ac850c63fdd8e240fed6b, and so did shasum -a 256 and openssl dgst -sha256 on the original file. The permanent guard computes its expectation with sha256.Sum256(file) from the raw bytes, so it cannot agree with a wrong implementation by sharing one.

Criterion 5. The range grew 16×, from 32 MiB to 512 MiB, and the heap the walk added moved by 1.5% — 3,556 KiB against 3,608 KiB. The 512 MiB run was taken with GOMEMLIMIT at 32 MiB, a range sixteen times the memory the process was allowed, and finished with a maximum resident set of 17.0 MB.

Two guards worth more than the feature

One mutation is recorded as passing, on purpose. Counting the ceiling per underlying call instead of per run leaves the single-range ceiling test green; only a collection split across partitions turns it red. On a one-partition store the two counters are indistinguishable, so the guard against W7's shape had to be built to span a boundary. A green result anywhere else says nothing about it, and the mutation table says so rather than listing a pass and moving on.

And one thing this ticket did not foresee. Explore caps a typed limit at MostRows (1000) before validation. That is right for a scan: a capped scan still answers, a page plus a flag. A digest does not answer — it refuses. The ten-megabyte file in five thousand rows that this command exists to check would therefore have refused every single time, on a limit the operator never chose. A typed hash is asked for its limit instead. Explore's own doc comment, which claimed the cap meant the limit rules "can never fire through Explore, no matter what an operator types", was corrected rather than left standing where it reads as an instruction.

What it leaves behind

Acceptance criteria

  1. The digest of a range equals SHA-256 of the original file, computed independently outside the database — measured on a real file of several megabytes split across thousands of rows, with decode: "base64".
  2. Re-chunking does not change it. The same bytes split into 1 KB rows and into 4 KB rows hash the same. This is the assertion that proves the separator rule is doing its job, and it is the one that would catch a delimiter creeping in.
  3. A row with a missing or wrongly typed field refuses, naming the key.
  4. Exceeding the row limit refuses rather than hashing a prefix — a digest of part of a range is indistinguishable from a digest of all of it, which makes a partial answer the most dangerous possible output.
  5. Memory does not scale with the range: measured on a range far larger than the server's free memory.
  6. Every new guard watched failing.

Out of scope