3 ms·
Files grow and shrink. Think about even the simplest "log" file (ex: Apache logs) appending constantly to the end of the file. First you have an access.log (+1
by dragontamer 5y ago
Files grow and shrink. Think about even the simplest "log" file (ex: Apache logs) appending constantly to the end of the file. First you have an access.log (+1 line to the end). Then Apache opens the error.log and adds some info to the end. Then PHP has something logged somewhere, again opening and closing a new set of files.
Even if these files were all perfectly allocated in sequential order at the beginning, a few operations like this quickly fragments the files.
--------------
I don't recall all the files MS-DOS or Win95 opened / closed on a regular basis, but play a video game (save file changed), open a word document, edit a photo, and come back to the video game... and the save file will now start getting fragmented as the size of the save files change and new allocated blocks need to be figured out.
- rasz 5y ago- How would btrees help with that? - can you name couple of games saving state by appending/modifying files in place on disk?
- dragontamer 5y ago> - can you name couple of games saving state by appending/modifying files in place on disk? Hmm, maybe the video game wasn't the example I should have chosen. But swap the order around: open a word doc (which creates an "auto-save" file which is almost certainly modified in place), and then do the other stuff and I think it applies. ------ > - How would btrees help with that? At a minimum, your indices are all together and in order and are read together all at once. From there, you can build the file's representation in RAM with much fewer random-traversals than the FAT32 linked-list approach. Perhaps "fixing fragmentation" is the wrong description. B-Trees mitigate the random-reads associated with fragmentation. There are much fewer seeks from a b-tree based representation than a FAT/linked-list style representation. ----------------- Consider this scenario. You have a FAT/Linked list of the following: 0 -> 10 -> 5 -> 7 -> 2 -> 1 So you need to move-head to 0, read, move-head to 10, read, move-head to 5, read, (etc. etc.). That's 6 times you move the head randomly. Now lets say you have a b-tree of [0, 10, 5, 7, 2, 1]. Exactly the same order of nodes as the linked list, but you can optimize much better. You read initially the b-tree, and then you read 0, 1, 2, 5, 7, 10 in order. You probably only move the head twice: first you move the head to 0, to read [0, 1, 2] as a sequential scan. Then, you move the head to 5, and read [5, 6, 7, 8, 9, 10] in order. Except you throw away the results for 6, 8, and 9. So long as you have sufficient RAM to re-order the data after you've read them from disk, you're gold. ---------- There's no way to optimize the FAT32's reads, because the indicies are scattered across the linked list. You only know that 10 is the "next" FAT32 node after you've read the page at 0. You only know that 5 follows 10 after you've read 10.
- rasz 5y agoOffice autosave does not modify files in place, it creates new copy with some additional backup/history/unwritten mechanisms thrown in. Modifying files in place is very rare (pre allocation in case of many downloaders like bittorrent/aria2 etc, or straight up disk editing), appending is more common (logging). >From there, you can build the file's representation in RAM with much fewer random-traversals than the FAT32 linked-list approach. You can do same thing in FAT by reading whole cluster map at the start. Wiki: "Other high-level mechanisms may read in and process larger parts or the complete FAT on startup or on demand when needed and dynamically build up in-memory tree representations of the volume's file structures different from the on-disk structures." This passage references OS/2 documentation, but its unclear to me if OS/2 employed such optimizations. Later NT builds might have this, as Iv seen large files allocated into empty space in the middle of a disk instead of forcing writes into first available gap. >B-Trees mitigate the random-reads associated with fragmentation. There are much fewer seeks from a b-tree based representation than a FAT/linked-list style representation after reading whole cluster map you have same representation in RAM, there is no information disparity. Its less elegant, slower to initialize and wasteful - 2TB FAT32 partition with 32KB clusters means >250MB cluster map on disk. But at the end of the day disk will have to perform same random seeks to read already fragmented file. The magic bullet for fragmentation is a map of free sectors letting OS pre plan where to put files in a smart way, and even NTFS doesnt use fancy data structures for that. NTFS $BITMAP is a https://en.wikipedia.org/wiki/Free_space_bitmap https://en.wikipedia.org/wiki/Free_space_bitmap. exFAT has a nice feature of marking unfragmented files in the Directory entry removing the need for FAT traversal altogether. >Consider this scenario. You have a FAT/Linked list of the following: 0 -> 10 -> 5 -> 7 -> 2 -> 1 So you need to move-head to 0, read, move-head to 10, read, move-head to 5, read, (etc. etc.). That's 6 times you move the head randomly. or whole FAT table is cached in ram and there is no difference :)