proposal: io/fs, net/http: define interface for automatic ETag serving

[rsc]

In the discussion of io/fs and embed, a few people asked for automatic serving of ETag headers for static content, using content hashes. We ran out of time for that in Go 1.16, in part because it's not entirely clear what we should do.

Here is a proposal that may be full of holes.

First, in io/fs, define

package fs

// A ContentHashFile is a file that can return its own content hash efficiently.
type ContentHashFile interface {
	File
	
	// ContentHash returns a content hash of the file that uniquely
	// identifies the file contents, suitable for use as a cache key.
	// The returned hash should be text, such as hexadecimal or base64.
	//
	// ContentHash must NOT compute the hash of the file during the call.
	// That is, it must run in time O(1) not O(length of file).
	// If a content hash is not already available, ContentHash should
	// return an error rather than take the time to compute one.
	ContentHash() (string, error)
}

Second, in net/http, when serving a File, if it implements ContentHashFile and the ContentHash method succeeds and is alphanumeric (no spaces, no Unicode, no symbols, to avoid any kind of header problems), use that result as the default ETag.

[johnjaylward]

Please correct the Big O notation:

// That is, it must run in time O(1) not O(length of file).

// That is, it must run in time O(1) not O(n).

[Merovius]

I feel "the returned hash should be text, such as hexadecimal or base64" is either not restrictive enough, or too restrictive. I think it would be reasonable to use the identifier in a URL, but not all base64 encodings are usable as such. So, IMO, we should either

1. Be more restrictive and specify what usages need to be fulfilled: "usable as an ETag header", "usable as a URL fragment" (I don't know if one of these implies the other), …
2. Be more restrictive and specify what encoding should be used: "hex", "base64.RawURLEncoding"…
3. Be less restrictive and specify that no encoding is used and the caller needs to re-encode based on intended usage: "the returned string may contain arbitrary bytes and must be encoded by the caller based on usage" (we might also use []byte as a signal, though string allows the interface to be allocation-free)

I think the last would be the least convenient in actual usage, but the most flexible.

#43076 is similar to this issue in the proposed solution and the addressed problem (so one or the other should be closed as duplicate, I think). It contains some discussion of other use-cases and how the API would need to be more complicated to serve them - notably, it was suggested that the hash should be able to be of arbitrary length and that it should be possible to specify the required hash-algorithm (useful if used e.g. in subresource integrity). I'm not fully on board with that being needed, but I wanted to bring it up.

@johnjaylward I think O(length of file) is clearer. Note, that if you want to be nitpicky, it is oxymoronic to "run in time O(1) not O(n)", because O(1)⊆O(n). So it'd need to be "run in time O(1) not ω(1)" (or something). Sometimes, clarity takes precedence over technical correctness.

[johnjaylward]

@johnjaylward I think O(length of file) is clearer. Note, that if you want to be nitpicky, it is oxymoronic to "run in time O(1) not O(n)", because O(1)⊆O(n). So it'd need to be "run in time O(1) not ω(1)" (or something). Sometimes, clarity takes precedence over technical correctness.

• O(1) is constant time regardless of input size.
• O(n) is linear time dependent on input size of n. In this case n would be the size of the file.

A concern that the function execution time is relative to the size of the file is not O(1) or ω(1). It would be some function of n. If n is non-linear, then you'd need to specify that as the class of function being compared (n log n for instance.)

Big O notation should be used correctly, or it should be avoided in favor of plain English. Using a mix of BigO and something else just feels wrong.

Since what I believe @rsc is trying convey is that Constant time should be guaranteed, I think plain English should be preferred.

Something like:

That is, it must run in constant time.

Optionally maybe specifying what isn't expected:

Execution time should not be relative to file size.

I'm also concerned about what this is expected to happen if the ContentHash returns an error before transport. Does the transport fail, or continue with no ETAG?

[rsc]

I'm not really sure arguing over big-O notation is the hill any of us needs to die on. But I taught intro to computational complexity three years in a row in college and am confident I understand the notation and how to use it. I'm going to sit out the big-O discussion here.

That said, I am explicitly avoiding saying "constant time" because the cryptographers have redefined that term to mean something much more subtle that I do not intend here. If I had written "constant time" in a paragraph that already contains "content hash", we'd be dying on a different pointless hill.

It's hard to win.

[rsc]

I'm also concerned about what this is expected to happen if the ContentHash returns an error before transport. Does the transport fail, or continue with no ETAG?

It continues with no ETag.

[johnjaylward]

I am explicitly avoiding saying "constant time" because the cryptographers have redefined that term to mean something much more subtle that I do not intend here. If I had written "constant time" in a paragraph that already contains "content hash", we'd be dying on a different pointless hill.

Understood, it is more of a nitpick than anything worth dying over. I'd prefer to drop improper use of O notation from official language docs. I've not read all of Go's docs by any means, but I've not seen this use anywhere in my reading. If it is used elsewhere, then this is just one more.

[ianlancetaylor]

Will it ever be necessary to know what kind of content hash function is being used by the underlying file system? For example, perhaps a security sensitive application would be willing to accept a SHA-256 hash but not an MD5 hash.

[rsc]

I don't know, and that's part of why we didn't propose anything for Go 1.16. ContentHash seems too vague at some level, but calling it ETag is too specific. We could call it something else - ContentID? - but it doesn't change the fact that the FS is in charge of which hash gets used, and the caller is expected not to be picky.

[tv42]

Either the acceptable character set of string has to be defined very clearly, resulting in either a one-size-fits-nobody solution or double encoding for most uses, or encoding should be left to the party that knows what encoding is needed (my preference).

ETag content (inside the quotes) character set is actually pretty different from most other uses:

etagc = "!" / %x23-7E / obs-text
obs-text = %x80-FF

[komuw]

maybe relevant; https://github.com/benbjohnson/hashfs