Validators Come From the Owner

The Question a Cache Cannot Answer Alone

A cache holds bytes. The one thing it cannot know by itself is whether those bytes are still right. There are two broad answers to that problem. One is a lifetime: keep the copy for ten minutes, an hour, a day, and trust it until then. The other is a validator: a short token the owner derives from the current state of the source, which changes when the source changes, so the receiver can ask "is it still this?" and get a yes or no.

Delta never guesses a lifetime. Every entry is revalidated against a validator the owner produced. A lifetime is a bet about how often someone else's data changes; a validator is a fact about whether it did. For a family's files, where a note edited a minute ago must read as edited, only the fact will do.

A File's Validator: Size, Modification Time, Inode

For a plain file, the owner builds the validator from one stat: the size, the modification time in nanoseconds, and the inode number, each in hex, joined with dashes and quoted, as an HTTP entity tag must be. Each part catches a different kind of change:

Part	Changes when
size	bytes were added or removed
`mtime_ns`	the file was written (or touched), to the nanosecond
inode	the file was replaced: an editor that saves to a temporary file and renames it over the old one creates a new inode, even if size and time come out identical

A stat costs microseconds and reads no content, which is the point: a revalidation must be much cheaper than a transfer, or it saves nothing. The same tag travels in listings (each file's etag), in ETag response headers, and back again in If-None-Match and expect. One definition, used at every step, so a listing and a read can never disagree about what version they mean. On the owner, the comparison (etag_matches) accepts a comma-separated list of tags or *, and ignores a W/ weak prefix, as HTTP clients expect.

The One Change It Cannot See

A stat-based validator has a known blind spot, and the runnable script below shows it plainly: a program that rewrites a file in place, keeps its length, and then sets its modification time back to the old value produces the same size, the same time and the same inode. The validator does not move. Very few tools do this on purpose, nanosecond timestamps make an accident unlikely, and Delta's transfers have a second line for it: the source's hash record of a file is keyed by device, inode, size, modification time and chunk size, and when the chunks that arrive disagree with that record, the receiver asks the source to hash the file again once (fresh=1) instead of trusting a record of bytes the file no longer holds. The cache itself keeps to the validator. Knowing where an instrument is blind is part of trusting it.

The opposite case is harmless: touch moves the time without changing a byte, the validator changes, and the next read is a miss. The bytes that come back hash to the blob already kept, so the commit finds the blob in place and stores nothing new. A false "changed" costs one transfer; a false "unchanged" would serve wrong data. The validator errs in the cheap direction.

When the Owner Is an App, the App Knows Better

A file's stat is a good validator for a file. It is a poor one for an app's read API, whose answer might be assembled from a dozen files and a database. So a share's root class has a validator(op, params) method a child can override to return a cheap tag for one operation. The Eagle library share does exactly that for its item-info call: an item's information changes only when Eagle rewrites that item's metadata.json, so the stat of that one file is the validator, and a revalidation is answered with a 304 before Eagle is asked anything.

A child that cannot tell cheaply returns None, and the gateway falls back to hashing the answer it just computed. That still saves the bytes on the wire when nothing changed, though not the owner's work. Derived outputs follow the same rule one level up: a thumbnail built from a source file carries the source's validator with the derivation's name appended, so when the source changes, its derived files are invalid too, with no separate bookkeeping.

Code

Delta's validators: a file's tag, a share's API tag, and a child's own (trimmed excerpts)·python

# Where Delta's validators come from (trimmed excerpts)

# delta/shares.py: a file's validator, from its stat on the owner
@property
def etag(self) -> str:
    return f'"{self.size:x}-{self.mtime_ns:x}-{self.ino:x}"'

# delta/server.py: an app share's read API, answered 304 before any work when it can
def serve_api(h, tail):
    share, op = _share_and_op(h, tail)
    params = dict(h.query)
    inm = h.headers.get("If-None-Match")
    tag = share.validator(op, params)  # a child that can tell cheaply answers before any work
    if tag and etag_matches(inm, tag):
        h.send_head(304, {"ETag": tag, "Content-Length": 0, "Cache-Control": "private, no-cache"})
        return
    result = share.api(op, params)
    body = json.dumps(result, separators=(",", ":"), default=str).encode()
    tag = tag or '"' + hashlib.sha256(body).hexdigest()[:32] + '"'  # otherwise the answer's own content
    if etag_matches(inm, tag):
        h.send_head(304, {"ETag": tag, "Content-Length": 0, "Cache-Control": "private, no-cache"})
        return
    ...

# A child's own validator (the Eagle library share): item-info changes only when
# Eagle rewrites the item's metadata.json, so its stat answers without asking Eagle.
def validator(self, op, params):
    if op != "item-info" or not ITEM_RE.match(params.get("id", "")):
        return None
    st = (self.library() / "images" / f"{params['id']}.info" / "metadata.json").stat()
    return f'"ii-{st.st_mtime_ns:x}-{st.st_size:x}"'

Watch a stat validator move, and the one edit it cannot see·python

# What a stat-derived validator sees, and the one change it cannot see.
import os
import tempfile


def etag(path):
    st = os.stat(path)
    return '"%x-%x-%x"' % (st.st_size, st.st_mtime_ns, st.st_ino)


folder = tempfile.mkdtemp(prefix="validator-")
path = os.path.join(folder, "draft.md")
with open(path, "w") as handle:
    handle.write("alpha\n")
start = etag(path)
print("written        ", start)

with open(path, "a") as handle:
    handle.write("beta\n")
print("appended       ", etag(path), "(size and mtime moved)")

os.utime(path, None)
print("touched        ", etag(path), "(mtime moved, bytes did not)")

before = os.stat(path)
with open(path, "r+") as handle:              # same length, edited in place
    handle.write("ALPHA")
os.utime(path, ns=(before.st_atime_ns, before.st_mtime_ns))
print("rewritten, time put back", etag(path), "<- the same tag: the edit is invisible")

tmp = path + ".tmp"
with open(tmp, "w") as handle:
    handle.write("alpha\nbeta\n")
os.utime(tmp, ns=(before.st_atime_ns, before.st_mtime_ns))
os.replace(tmp, path)                          # an editor's atomic save
print("replaced, time put back ", etag(path), "<- a new inode, so a new tag")

Exercise

Run the validator script, then try your own editors on a scratch file: save it from a text editor, from vim, and with sed -i '', printing stat -f '%z %m %i' before and after each. Which ones keep the inode and which replace the file? Then write down, for one API in a project of yours, the cheapest fact that would tell you its answer had not changed.

Hint

stat -f '%i' prints the inode on macOS. Editors that save atomically (write a temporary file, then rename) show a new inode on every save; sed -i on macOS also writes a new file. Appending with >> keeps the inode and moves size and time.