4 ms·

That seems like extra work for very little benefit. Like you say, this is already how filesystems are implemented with inodes and superblocks. But users don't

That seems like extra work for very little benefit. Like you say, this is already how filesystems are implemented with inodes and superblocks. But users don't care - all they need is a stream of bytes. If you really needed something like this, you could implement it yourself "inside" one preallocated file.

derefr 7y ago
Of course you can do it yourself; but the point would be to have a standard API (like files are a standard API) for interacting with such on-disk vector-of-extents objects, such that one program could write them and another program, written by a different author, could read them back. The simplest obvious use-case for pure vector objects: storing Unix text-based file formats as vectors of line-length extents, rather than a single byte-stream. wc(1), head(1), tail(1), etc. would now be O(log n) operations. Any parsing operation that can proceed separately for each line (like the context-free phases of syntax highlighting... or like grep) could be parallelized. The .mbox file format would be relevant again. This would essentially do for Unix what record-orientation does for z/OS—while keeping things "Unix-y." Another powerful use-case: concatenation. The direct ability to manipulate extents means the ability to compose sequences of extents together into new files, without having to copy the underlying extents. So you can download some large document in parts (either because it's explicitly chunked, ala partial RARs; or because you used range requests to retrieve the file one chunk at a time, perhaps in parallel, as in HTTP or BitTorrent) and then just concatenate the chunks back together in O(log n) time. No need to pre-allocate a file, target your chunk-writes, and keep an external index of which chunk-jobs have succeeded. Just keep a downloads directory and concatenate when you're done. It's funny; modern filesystems have the theoretical capacity for many operations like O(log n) concatenation, but they only bother to expose one or two (hard-link, and sometimes copy-on-write clone/snapshot). Filesystem authors are seemingly unimaginative and conservative where exposing new APIs is concerned; I wouldn't expect them to ever directly expose the ability to O(log n) concatenate files. But if they exposed a vector-object, it would give you these features for free! But maybe that doesn't seem useful enough. Let's add one more feature: give the ability to store a "table of contents" with this vector-object, i.e. a labelled interval tree where the extents in the vector are the leaves. Such a filesystem object would entirely obviate specialized tooling for container/record file formats; rather than mkvtoolnix(1), or avro-tools, or LevelDB, you'd just need a program that took the raw byte stream of one of these container files as input, and spat out a labelled-interval-tree-extent-vector file-system-object representation. You could cd into it, put things in, take things out... it'd seem a lot like a directory. But it'd still fundamentally be a file, in the sense that it'd still fundamentally be a bijection with a seekable byte stream. (Unlike actual directories, where dirents have no standardized collation order; where there's no obvious semantic answer for what part of the "content of a dirent", if any, goes into a treewise cryptographic checksum; etc.) Certainly, though, if you had this type of object in your filesystem, you could implement your filesystem's directories in terms of it.

derefr 7y ago

Of course you can do it yourself; but the point would be to have a standard API (like files are a standard API) for interacting with such on-disk vector-of-extents objects, such that one program could write them and another program, written by a different author, could read them back. The simplest obvious use-case for pure vector objects: storing Unix text-based file formats as vectors of line-length extents, rather than a single byte-stream. wc(1), head(1), tail(1), etc. would now be O(log n) operations. Any parsing operation that can proceed separately for each line (like the context-free phases of syntax highlighting... or like grep) could be parallelized. The .mbox file format would be relevant again. This would essentially do for Unix what record-orientation does for z/OS—while keeping things "Unix-y." Another powerful use-case: concatenation. The direct ability to manipulate extents means the ability to compose sequences of extents together into new files, without having to copy the underlying extents. So you can download some large document in parts (either because it's explicitly chunked, ala partial RARs; or because you used range requests to retrieve the file one chunk at a time, perhaps in parallel, as in HTTP or BitTorrent) and then just concatenate the chunks back together in O(log n) time. No need to pre-allocate a file, target your chunk-writes, and keep an external index of which chunk-jobs have succeeded. Just keep a downloads directory and concatenate when you're done. It's funny; modern filesystems have the theoretical capacity for many operations like O(log n) concatenation, but they only bother to expose one or two (hard-link, and sometimes copy-on-write clone/snapshot). Filesystem authors are seemingly unimaginative and conservative where exposing new APIs is concerned; I wouldn't expect them to ever directly expose the ability to O(log n) concatenate files. But if they exposed a vector-object, it would give you these features for free! But maybe that doesn't seem useful enough. Let's add one more feature: give the ability to store a "table of contents" with this vector-object, i.e. a labelled interval tree where the extents in the vector are the leaves. Such a filesystem object would entirely obviate specialized tooling for container/record file formats; rather than mkvtoolnix(1), or avro-tools, or LevelDB, you'd just need a program that took the raw byte stream of one of these container files as input, and spat out a labelled-interval-tree-extent-vector file-system-object representation. You could cd into it, put things in, take things out... it'd seem a lot like a directory. But it'd still fundamentally be a file, in the sense that it'd still fundamentally be a bijection with a seekable byte stream. (Unlike actual directories, where dirents have no standardized collation order; where there's no obvious semantic answer for what part of the "content of a dirent", if any, goes into a treewise cryptographic checksum; etc.) Certainly, though, if you had this type of object in your filesystem, you could implement your filesystem's directories in terms of it.