How do I delete bytes from the beginning of a file? (2010)(devblogs.microsoft.com)
devblogs.microsoft.com
How do I delete bytes from the beginning of a file? (2010)
https://devblogs.microsoft.com/oldnewthing/20101201-00/?p=12153
89 comments
Reading this, I couldn't help but try to find the rhythm of a poem to match the formatting.
I was reminded of "The Story of Mel" (https://www.cs.utah.edu/~elb/folklore/mel.html), which was originally written as prose but got mutated through Usenet linebreaks into something that wound up looking like free verse, and is now remembered as such.
I realized I haven't been to Raymond's blog since this new layout was applied. It was a little jarring - it seems very stark and sterile, and there are a lot of 404'd links. I suspect it got hit in the MSDN blog purge that happened a little while back, unfortunately.
It reminded me of "Hyperion" and "The Fall of Hyperion" by Dan Simmons. The way an AI called Ummon communicates with humans is rendered in a similar fashion.
They've changed the CMS of Raymond's blog at least two times since this post was written. The style of many posts was "lost in translation", so to say.
Sometimes I wonder if keeping the blog up and the permalinks alive is part of the contract Raymond has with Microsoft.
Sometimes I wonder if keeping the blog up and the permalinks alive is part of the contract Raymond has with Microsoft.
br { display: none; }
I guess Raymond uses a line oriented editor like vim,
and the original line breaks have been preserved.
If you use one line per clause,
it's much easier to change sentence and paragraph structures
without having to seek around by the word.
Vim's not line oriented... at least as far I know. ed/ex, now those are line oriented.
But I wouldn't call vim line oriented. Unless you also want to call Notepad line oriented, since you can use Shift + End to do operations on an entire line :D
But I wouldn't call vim line oriented. Unless you also want to call Notepad line oriented, since you can use Shift + End to do operations on an entire line :D
I've often thought it would be useful (especially for software that manages container or archive file-formats, or for databases) to have exposed to the user a file-system object that operates like a file, but which—instead of being exposed by OS as a seekable byte stream that can be appended/truncated on one end—is exposed by syscalls as a vector of arbitrary, non-uniformly-sized extents, where the user is expected to ask the OS to pre-allocate extent buffers (think mmap(2) with anonymous private disk pages), and then, separately, stuff those into this vector object (which would be an operation almost exactly like hard-linking an existing file into a directory, in terms of its time and space complexity.)
Of course, for most filesystems (and especially ones with sparse-file support, and especially ones with copy-on-write support), such an on-disk data structure is exactly what's already underlying the byte-stream abstraction. So this would just be a passthrough to allow people to directly manipulate that data structure. (In the process probably breaking certain preconditions the filesystem relies on, though, so it would need to track these "low-level extent vectors" as a separate filesystem object type. Programs would still be able to use regular file-abstraction syscalls on them, though.)
Interestingly, despite filesystems themselves not exposing the lower-level extent-vector abstractions, in some other systems that have file-stream-like abstractions, you can operate on "files" this way.
Postgres's BLOBs, for example, are seekable byte-streams, which also (at least theoretically) allow you to insert into the middle of them. (I say theoretically because it's not an implemented API, but it's not exactly hidden from the user, either. BLOBs just get broken out into records in a table representing their extents; you can rewrite the keys of said records in that table to do whatever low-level operations you like.)
Or, for another example, S3 and its competitors let you arbitrarily compose objects as “components” of other virtual objects, which then read back as the concatenation of the objects they contain. (Sadly you don’t get any other vector-manipulation ops than this, but if you keep references to the leaf extents around, that’s often enough to rebuild your extent-vectors any time they change.)
Also, of course, back on the real filesystem, you can just manage your "vector of parts of a file" as multiple files in a directory, and then abstract over that directory that by using a FUSE server which exposes a view where the files are one contiguous file.
Of course, for most filesystems (and especially ones with sparse-file support, and especially ones with copy-on-write support), such an on-disk data structure is exactly what's already underlying the byte-stream abstraction. So this would just be a passthrough to allow people to directly manipulate that data structure. (In the process probably breaking certain preconditions the filesystem relies on, though, so it would need to track these "low-level extent vectors" as a separate filesystem object type. Programs would still be able to use regular file-abstraction syscalls on them, though.)
Interestingly, despite filesystems themselves not exposing the lower-level extent-vector abstractions, in some other systems that have file-stream-like abstractions, you can operate on "files" this way.
Postgres's BLOBs, for example, are seekable byte-streams, which also (at least theoretically) allow you to insert into the middle of them. (I say theoretically because it's not an implemented API, but it's not exactly hidden from the user, either. BLOBs just get broken out into records in a table representing their extents; you can rewrite the keys of said records in that table to do whatever low-level operations you like.)
Or, for another example, S3 and its competitors let you arbitrarily compose objects as “components” of other virtual objects, which then read back as the concatenation of the objects they contain. (Sadly you don’t get any other vector-manipulation ops than this, but if you keep references to the leaf extents around, that’s often enough to rebuild your extent-vectors any time they change.)
Also, of course, back on the real filesystem, you can just manage your "vector of parts of a file" as multiple files in a directory, and then abstract over that directory that by using a FUSE server which exposes a view where the files are one contiguous file.
This, and more, has been tried on mainframes. When you could not afford to install a free RDBMS with a click of a mouse (the mouse being not available yet, too), you could really appreciate record-oriented files you could use as a database, and even have indexed access to the records.
The Commodore 64 supported (or maybe it was the 1541 drive that implemented it) what was called "relative files", which were composed of fixed-size records that were accessed by index. I always thought they sounded cool, but never had a real need for them in my toy projects on that platform.
Has anyone written a high-level introduction to mainframe tech that's accessible to people outside the mainframe culture? I've always been curious about it, but the IBM manuals I've come across have been somewhat impenetrable.
How about:
'Introduction to the New Mainframe: z/OS Basics' http://www.redbooks.ibm.com/abstracts/sg246366.html?Open
This, and the 'ABCs of Systems Programming' series were pretty good I thought.
'Introduction to the New Mainframe: z/OS Basics' http://www.redbooks.ibm.com/abstracts/sg246366.html?Open
This, and the 'ABCs of Systems Programming' series were pretty good I thought.
Classic, compiling hello world: https://medium.com/@bellmar/hello-world-on-z-os-a0ef31c1e87f
> ...but the IBM manuals I've come across have been somewhat impenetrable.
I always thought that was intentional to maximize the consulting opportunities.
I always thought that was intentional to maximize the consulting opportunities.
I believe record-oriented data sets only give you fixed but not arbitrarily/variably-sized extents. I.e., a given file (data set) is of one record type (sort of like an RDBMS table is of one record type), and the record type then determines the extent size for the whole file.
Whereas, what I'm talking about, is more like what you get by having a sorted-set data structure in Redis, and putting arbitrary strings in it. Or storing data in LMDB with BASIC-like numeric labels as keys. Rather than a tabular representation, your data store is a heap, with a tabular index set aside to point into it.
(Of course, you can emulate arbitrary-length records over fixed-length records, as Postgres does with its TOAST tables, or—in the small—as UTF-8 does with runes. But in the record-orientation implementation, that’s something that would be exposed to the developer, requiring them to solve the problem themselves or through a library; rather than the file system just showing you arbitrary-length records from the start. And, if you can’t rely on other users doing that work, you can’t really use it as an interchange format.)
Whereas, what I'm talking about, is more like what you get by having a sorted-set data structure in Redis, and putting arbitrary strings in it. Or storing data in LMDB with BASIC-like numeric labels as keys. Rather than a tabular representation, your data store is a heap, with a tabular index set aside to point into it.
(Of course, you can emulate arbitrary-length records over fixed-length records, as Postgres does with its TOAST tables, or—in the small—as UTF-8 does with runes. But in the record-orientation implementation, that’s something that would be exposed to the developer, requiring them to solve the problem themselves or through a library; rather than the file system just showing you arbitrary-length records from the start. And, if you can’t rely on other users doing that work, you can’t really use it as an interchange format.)
Today, though, that filesystem abstraction is block-aligned. So you could delete blocks from the beginning or middle of a file easily, but you couldn't delete bytes from the beginning or middle.
Right—the difference is that, with a file object, the extents are all assumed to be full to capacity except for the very last one, with the information on the virtual size within the last extent being held in the file's inode.
Whereas, with these vector-of-buffers objects, either each extent would need to reserve two bytes at the beginning to represent the virtual size of that extent, or the vector would be a vector of disk slices at byte granularity, rather than a vector of plain disk offsets at sector granularity.
I can see the arguments for both.
The former is extremely efficient, and would probably be the go-to for databases that want to be performant without needing to dedicate a raw block device to them.
The latter approach, though, you can implement entirely "on top of" the filesystem (in the same way that the ext3 journal, or APFS containers, are implemented "on top of" their filesystems.) You could have a regular file representing the storage reservation (in full extents) for the vector-object; and then the vector object could be a tree (or something else efficient to rewrite) of byte-granular slices of offsets into that backing storage-file, with logic to ensure that such a reserved slice never straddles two extents, and a cache in the entry for a pointer to the actual extent. These would be perfect for, say, generating archive files.
In fact, since these are such different use-cases, there's no reason to not just give users both.
Whereas, with these vector-of-buffers objects, either each extent would need to reserve two bytes at the beginning to represent the virtual size of that extent, or the vector would be a vector of disk slices at byte granularity, rather than a vector of plain disk offsets at sector granularity.
I can see the arguments for both.
The former is extremely efficient, and would probably be the go-to for databases that want to be performant without needing to dedicate a raw block device to them.
The latter approach, though, you can implement entirely "on top of" the filesystem (in the same way that the ext3 journal, or APFS containers, are implemented "on top of" their filesystems.) You could have a regular file representing the storage reservation (in full extents) for the vector-object; and then the vector object could be a tree (or something else efficient to rewrite) of byte-granular slices of offsets into that backing storage-file, with logic to ensure that such a reserved slice never straddles two extents, and a cache in the entry for a pointer to the actual extent. These would be perfect for, say, generating archive files.
In fact, since these are such different use-cases, there's no reason to not just give users both.
For that matter, byte-oriented persistent memory would allow something byte-oriented and not block-oriented.
By itself, no. If the persistent memory is considered physical memory and there's virtual memory on top of it—but the part of the virtual-memory map that represents the persistent memory is itself persisted in the persistent memory—then you'd have something quite similar.
It'd be similar to—but faster than—what you'd get if you could both talk to, and past, the flash controller for a regular SSD, allowing you to both see an LBA block device, and see the physical extents + allocation map managed by the flash controller underlying the block device. (But you'd need to be able to write to the allocation map yourself, without making the flash controller fall over, which, well, good luck.)
It'd be similar to—but faster than—what you'd get if you could both talk to, and past, the flash controller for a regular SSD, allowing you to both see an LBA block device, and see the physical extents + allocation map managed by the flash controller underlying the block device. (But you'd need to be able to write to the allocation map yourself, without making the flash controller fall over, which, well, good luck.)
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.
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.
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.
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.
Linux's fallocate allows you to insert data into the middle of files by manipulating the extents.
That sounds a lot like RMS files in the VMS operating system.
> instead of being exposed by OS as a seekable byte stream that can be appended/truncated on one end—is exposed by syscalls as a vector of fixed-sized extents
That sounds similar to mainframe stuff like VSAM, where files are a stream of records instead of a stream of bytes.
That sounds similar to mainframe stuff like VSAM, where files are a stream of records instead of a stream of bytes.
Why not make a file an arbitrary data structure, instead of a vector to which you can push only at the end?
Maybe I didn’t make that clear, but that’s what I was talking about. That’s why I used the term “vector” instead of “stack.” A vector ADT usually allows insertion/deletion/replacement from the middle.
Ok, but what I meant was: instead of vectors, or deques, why not also consider sets, maps, etc.?
Another approach I can think of is using rolling hash (https://en.wikipedia.org/wiki/Rolling_hash) to split file to different size of chunks, those chunks can be saved on different sectors which don’t need to be continuous. The file keeps a list of indexes for all those chunks, just like inode did for blocks. When insert some bytes in the beginning of file, thanks for the rolling hash, most likely only the first several chunks need to be re-chunk and re-hash, thus the change is localised and can be cheaply done, all the rest chunks still untouched. When this combined with append-only storage, things are even easier because it only needs to deal with bytes around that beginning, and the update chunk index list in file.
This approach is already implemented in ZboxFS (https://github.com/zboxfs/zbox) to do content-based deduplication.
This approach is already implemented in ZboxFS (https://github.com/zboxfs/zbox) to do content-based deduplication.
I didn't get the "minus 100 points" reference, but it was not hard to find it on the web: https://blogs.msdn.microsoft.com/ericgu/2004/01/12/minus-100...
Why would you want to delete bytes from the beginning of a file? A file should be seen as a low-level data structure with a limited set of operations. If you want to implement a more complex data structure with a wider range of operations, there are usually multiple ways of implementing this on a low-level data structure with a limited set of operations. This is basically what a lot of software engineering is about. If you want to implement an array of bytes with delete and insert operations, there are many ways you could implement this on a low-level file. Which way is the best depends on so many other factors. Do you want undo-redo functionality, transaction properties, distributed access, and so on?
Because sometimes I want to remove old and irrelevant lines in a logfile but want to retain the recent lines.
> A file should be seen as a low-level data structure with a limited set of operations.
Why should? For many people, a file is a basic way to permanently store data. Changing the data at any point of the file should be easy.
> A file should be seen as a low-level data structure with a limited set of operations.
Why should? For many people, a file is a basic way to permanently store data. Changing the data at any point of the file should be easy.
Actually, most file systems let you randomly read and write to files. Usually, they implement this by reading and writing blocks (of 256 bytes or a multiple). One could create file systems with more advanced operations, but most likely, these will be based on the more primitive operations. For example, to add the function to remove 10 bytes from the start of the file, one could read the whole file, block-by-block, and move the data 10 bytes. For a large log file, this will take a long time. Another solution is to have a begin of file offset for all files, this means that some additional information need to be stored with every the file and that this information needs to be accessed with all file operations, resulting in some performance loss for all file operations. Existing programs that access files as blocks of a certain size, might see significant performance penalties when the offset is not a multiple of the block size, because reading the data from one block, needs to read two actual blocks from the underlying medium.
If you often want to strip a logfile from old data, a solution might be to create new logfiles at a regular intervals and delete old logfiles. Or maybe even better, use a database to store the log messages. Gives you query functionality and allows you to perform more advanced operations, as removing certain types of log messages.
If you often want to strip a logfile from old data, a solution might be to create new logfiles at a regular intervals and delete old logfiles. Or maybe even better, use a database to store the log messages. Gives you query functionality and allows you to perform more advanced operations, as removing certain types of log messages.
See fallocate() for Linux/ext4. http://man7.org/linux/man-pages/man2/fallocate.2.html
I've written a quick tutorial on linux sparse files/fallocate and effect on different writers/readers:
https://gist.github.com/minaguib/1cbe29922b06d50755a2f580b8c...
https://gist.github.com/minaguib/1cbe29922b06d50755a2f580b8c...
It looks like this will zero out data but not remove.
It will remove if you use FALLOC_FL_COLLAPSE_RANGE
But: " A filesystem may place limitations on the granularity of the
operation, in order to ensure efficient implementation. Typically,
offset and len must be a multiple of the filesystem logical block
size, which varies according to the filesystem type and
configuration. If a filesystem has such a requirement, fallocate()
fails with the error EINVAL if this requirement is violated."
Seems it's limited.
Seems it's limited.
Correct, my bad. Did some tests and AFAICT neither EXT4, XFS nor BTRFS allows arbitrary byte ranges here.
[deleted]
Theoretically, if the number of bytes to be removed were a multiple of FS data block size (usually an inode size), it should be possible to unlink that inode as well, and rewrite the metadata. It probably involves fewer shifts and fewer bytes/time wasted.
In general, if you intend to create structures that allow one to reduce file size, reclaim the data, defragment - that sort of thing, a rewrite/coalesce happens to be the viable solution. In general, if allowed to increase, fragmentation will worsen with time.
In general, if you intend to create structures that allow one to reduce file size, reclaim the data, defragment - that sort of thing, a rewrite/coalesce happens to be the viable solution. In general, if allowed to increase, fragmentation will worsen with time.
I'm not sure I really understood this. If you wanted to delete 10 bytes, couldn't you just read a sector, then copy the sector back sector[10:]?
Edit: then delete the last ten bytes.
Edit: then delete the last ten bytes.
The unix filesystem api doesn't provide a way to interact with sectors. The primitives are files and the methods available are writing more data, or truncating.
There is no function provided for shifting the byte offset of data in a file.
You can write an entirely new file, of course, but the question has an implicit goal of doing this efficiently.
There is no function provided for shifting the byte offset of data in a file.
You can write an entirely new file, of course, but the question has an implicit goal of doing this efficiently.
Does the whole sector thing still make sense for SSDs? Do they still work by sector or can every byte be addressed directly?
The "native" sector size of an SSD is the erasure block size, typically 64KiB.
I'm fairly sure SSD erase block sizes are more like 2 MB or more. Even 8 MB wouldn't surprise me anymore.
current SSDs are page/block oriented, but that's likely to change. (See intel's relatively recent Optane).
Only the last sector is allowed to be partially filled. Every other sector must be fully filled.
Each sector is a fixed size.
At first blush, I don't think this would work quite right because the last ten bytes of the sector would have some content (e.g., zero bytes or some other data from the original sector).
What happens to the last 10 bytes of that sector?
You'd have to do this for every sector in the file or increase potential fragmentation. Alternatively they could support an offset in the beginning, but it might wear out the decide much faster due to lack of alignment. In either case though I feel the capability would be nice to have regardless...
To delete from the beginning of a file, overwrite offset 0 from offset n, 1 from n+1 and so on, and then truncate it when the read offset hits EOF.
dunno about windows, but in llinux its fairly simple. I've had to do do this a lot of this sort of thing on big disk images my friend made with some weird program that pads the start of everything with 512 bytes of some random crap.
dd skip=10 iflag=skip_bytes if=original.file of=first10ktrimmed.file
despite being old, and the amount of insanely horrible things you can do when you mess up the syntax or mistype something using it, dd is fucking amazing.
to be fair, its not directly editing the file, but making a copy with the first 10k skipped.
you could have a jump/pointer that points to the shortened first block of the file and then at the end of that, a pointer/jump to pick up where the rest of the file continues, but you'd wind up with misalignment and fs fragmentation.
dd skip=10 iflag=skip_bytes if=original.file of=first10ktrimmed.file
despite being old, and the amount of insanely horrible things you can do when you mess up the syntax or mistype something using it, dd is fucking amazing.
to be fair, its not directly editing the file, but making a copy with the first 10k skipped.
you could have a jump/pointer that points to the shortened first block of the file and then at the end of that, a pointer/jump to pick up where the rest of the file continues, but you'd wind up with misalignment and fs fragmentation.
This really isn't solving the problem posed by the author, though. Copying the file is a completely different thing; for one, it will require double the space and take a lot longer.
What if you need to chop the first 10 bytes from a file that is more than half your disk?
What if you need to chop the first 10 bytes from a file that is more than half your disk?
_Copying_ what you want from a file is trivial on any OS.
The question is to how to trim the file head _in place_.
The question is to how to trim the file head _in place_.
> to be fair, its not directly editing the file, but making a copy with the first 10k skipped
...so missing the point of the question entirely.
...so missing the point of the question entirely.
Linux doesn't implement sparse files.
Yes it does? The details are file system specific and if they support mmap then it's also likely there's a page alignment requirement but that's not atypical.
Not only does it do so, but dd directly supports sparse files, using the "sparse" conv symbol.
[deleted]
burfog(4)
Is this a problem that really needs a solution?
I can't recall any times where this would have been useful to me or think of a situation where it'd be a deal breaker. I could contrive a bunch of other operations that are inefficient on file systems like this (remove every other byte from the file, why not?), but doesn't mean that literally any idea we can think up should be supported by the file system apis.
I can't recall any times where this would have been useful to me or think of a situation where it'd be a deal breaker. I could contrive a bunch of other operations that are inefficient on file systems like this (remove every other byte from the file, why not?), but doesn't mean that literally any idea we can think up should be supported by the file system apis.
Filesystem design and operating system design is full of these kinds of questions.
From Unix and Windows we are used that we can insert and delete the end of a file and that we can read, write and seek anywhere in the file, but a filesystem could potentially do much more: Inserting/deleting at the beginning or inserting/deleting in the middle.
Deleting at the beginning of a file would be handy for queues or logs and inserting and deleting in the middle is a common operation for text editors.
There are even more questions you could ask:
- Why not have tabular files that allow indexed access?
- Do we need hierarchical directories or do we need directories at all?
- What about adding tags to files?
- Why having a filesystem at all?
From Unix and Windows we are used that we can insert and delete the end of a file and that we can read, write and seek anywhere in the file, but a filesystem could potentially do much more: Inserting/deleting at the beginning or inserting/deleting in the middle.
Deleting at the beginning of a file would be handy for queues or logs and inserting and deleting in the middle is a common operation for text editors.
There are even more questions you could ask:
- Why not have tabular files that allow indexed access?
- Do we need hierarchical directories or do we need directories at all?
- What about adding tags to files?
- Why having a filesystem at all?
I think this was more for fun and intrigue than for real
> And I suspect the fact that you can simulate the operation yourself is a major reason why the feature doesn’t exist: Time and effort is better-spent adding features that applications couldn’t simulate on their own.
> And I suspect the fact that you can simulate the operation yourself is a major reason why the feature doesn’t exist: Time and effort is better-spent adding features that applications couldn’t simulate on their own.
At a previous job, long ago, I was working on software to add tags to audio and video files. Some of the formats required modifying or adding data to the start of the file. Having to rewrite a multi-gigabyte file just to add a few hundred bytes to the beginning of the file is slow, and dangerous if there isn't room on the disk for a second copy of the file. (Not as much of a consideration now, but disks weren't as large or cheap in the mid-00s.)
I just recently had to do this at work. We load data into aws redshift from csv in s3. Well, one particular set of files had a BOM[1], which redshift chokes on. Cue having to rewrite the entire 4.5GB file because to remove the first three bytes.
[1] https://en.wikipedia.org/wiki/Byte_order_mark
[1] https://en.wikipedia.org/wiki/Byte_order_mark
One place this would be useful is a DVR. You want to record the last n hours of video and discard anything older. And it's not inefficient. It just requires a lot of careful engineering that's probably not worth the bother.
It's unnecessary to create a filesystem-level support I think, since you could make a circular buffer holding a video stream in a file with some constant size that is approximately n hours of video. With some clever tricks you could even keep the format compatible with existing video container formats.
Or just use a set of files, each holding N minutes with, perhaps, some overlap + an index file. No real need to over-engineer things here.
From the ones I’ve read, Raymond Chen’s articles are more about problems that are fun to think about than problems that need solutions (though there are plenty of articles about problems that fit both descriptions).
The filesystem just needs a concept of a file start offset.
The initial value is 0, if you wanted to support truncating at the head, you just add to this offset the amount truncated.
In a sector-based filesystem, whenever this offset goes far enough into the file that crosses sector boundaries, you reclaim those sectors as free space. When it lands within a sector somewhere, that sector is pinned and you waste some space.
The problem is more that the userspace APIs don't expose well-supported mechanisms for doing this. Implementing it at the filesystem level is trivial.
The initial value is 0, if you wanted to support truncating at the head, you just add to this offset the amount truncated.
In a sector-based filesystem, whenever this offset goes far enough into the file that crosses sector boundaries, you reclaim those sectors as free space. When it lands within a sector somewhere, that sector is pinned and you waste some space.
The problem is more that the userspace APIs don't expose well-supported mechanisms for doing this. Implementing it at the filesystem level is trivial.
I thought his point in the blog was that it was indeed trivial to implement but when you think about all the consequences it becomes trickier to do it well.
He makes that point at the end.
He makes that point at the end.
I can think of a cool case for this.
What if you have an append-only system which is making remote backups. One service is writing the activity log append only, a second service is reading that, check-pointing, and then truncating the head of the file when the check-point has been committed. No need to do the tricky file-swap trickery.
What if you have an append-only system which is making remote backups. One service is writing the activity log append only, a second service is reading that, check-pointing, and then truncating the head of the file when the check-point has been committed. No need to do the tricky file-swap trickery.
Linux and fallocate() allows precisely this - we use this to "log locally" for applications, and a "tail this asap and publish to kafka then delete locally" helper.
See ( https://gist.github.com/minaguib/1cbe29922b06d50755a2f580b8c... ) for some test notes I took a couple of years ago.
See ( https://gist.github.com/minaguib/1cbe29922b06d50755a2f580b8c... ) for some test notes I took a couple of years ago.
fallocate() is not supported on network file systems, is it?
Curiously enough. PalmOS's file streams supported this very feature: delete as i read. As you read bytes from the start of the file, they'd be deleted. You were allowed to have a concurrent writer appending to the end.
As you read bytes from the start of the file, they'd be deleted. You were allowed to have a concurrent writer appending to the end.
Also known as a named pipe.
Also known as a named pipe.
Journaling filesystems do that internally.
This is discussed in TFA and a number of problems with this "just do" solution are pointed out.
I hovered over the link, and there it was.
Raymond Chen is a machine, the T-1000 of Windows development. I've never developed Windows applications using C++ and I still read his blog articles.