Hello list. I''ve been working on my MSc thesis and I believe such a time came when it will cross paths with BTRFS. However, I have a couple of standing questions I haven''t been able do answer, even though having read Ohad Rodeh''s paper, most of the wiki''s documentation, after looking to BTRFS'' code and after testing it myself --- I''m not putting aside missing some information, somewhere, though. Basically, I need to be aware how the COW works in BTRFS, and what it may allow one to achieve. Questions follow. 1) Is COW only used when creating or updating a file? While testing BTRFS, using ''btrfs subvolume find-new'', I got the idea that neither creation of directories, nor any kind of deletion are covered by COW. Is this right? 2) Each time a COW happens, is there any kind implicit ''snapshotting'' that may keep track of changes around the filesystem for each COW? By Rodeh''s paper and some info on the wiki, I gather that a new root is created for each COW, due to shadowing, but will the previous tree be kept? The wiki, at "BTRFS Design", states that "after the commit finishes, the older subvolume root items may be removed". This would make impossible to track changes to files, but ''btrfs subvolume find-new'' still manages to output file generations, so there must be some info left behind. 3) Following (2), is there any way to access this informations and, let''s say, recover an older version of a given file? Or an entire previous tree? 4) From Rodeh''s paper I got the idea that BTRFS uses periodic checkpointing, in order to assign generations to operations. Using ''btrfs subvolume find-new'' I confirmed my suspicions. After copying two different directories into the same subvolume at the same time, all files got assigned the same generation and it took a while until they all showed up. This raises the question: what triggers a new checkpoint? Is it based on elapsed time since last checkpoint? Is it triggered by a COW and then, all COWs happening at the same time will be put together and create a big new generation? 5) If we have multiple jobs updating the same file at the same time, I assume the system will shadow their updates; when the time for committing comes, will there be any kind of ''conflict'' between concurrent updates, or will they be applied by order of commit, ignoring whether there were previous commits or not? Regarding checkpointing, will all the changes be shown as part of the generation, or will they be considered as only one? I would greatly appreciate any answer regarding any of this topics, including any pointers to additional documentation that I may have missed. Regards. --- João Eduardo Luís -- To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Monday, 08 November, 2010, João Eduardo Luís wrote:> Hello list.[...]> Basically, I need to be aware how the COW works in BTRFS, and what it mayallow one to achieve. Questions follow.> > 1) Is COW only used when creating or updating a file? While testing BTRFS,using ''btrfs subvolume find-new'', I got the idea that neither creation of directories, nor any kind of deletion are covered by COW. Is this right? The command "btrfs subvolume find-new" search through the keys with type == BTRFS_EXTENT_DATA_KEY. Because the COW is per disk-block basis, it is no so simple to track a change in a metadata (in a disk-block there are a lot of metadata). In fact there are a lot of false-positive. I thought a bit about a way to compare two tree(s). But it is not so simple. If I understood correctly even if only a leaf is different, you have to compare a full branch (from the root to the leaf) of different disk-blocks.> > 2) Each time a COW happens, is there any kind implicit ''snapshotting'' thatmay keep track of changes around the filesystem for each COW?> By Rodeh''s paper and some info on the wiki, I gather that a new root iscreated for each COW, due to shadowing, but will the previous tree be kept? The wiki, at "BTRFS Design", states that "after the commit finishes, the older subvolume root items may be removed". This would make impossible to track changes to files, but ''btrfs subvolume find-new'' still manages to output file generations, so there must be some info left behind.> > 3) Following (2), is there any way to access this informations and, let''ssay, recover an older version of a given file? Or an entire previous tree? Snapshotting a tree is the method to track "an older version of a given file"(s) or a tree. [...]> > I would greatly appreciate any answer regarding any of this topics,including any pointers to additional documentation that I may have missed.> > > Regards. > > > --- > João Eduardo LuísCiao Goffredo -- gpg key@ keyserver.linux.it: Goffredo Baroncelli (ghigo) <kreijack@inwind.it> Key fingerprint = 4769 7E51 5293 D36C 814E C054 BF04 F161 3DC5 0512 -- To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
(sorry for sending twice) On Mon, Nov 08, 2010 at 02:23:13PM +0000, João Eduardo Luís wrote:> Basically, I need to be aware how the COW works in BTRFS, and what it may allow one to achieve. Questions follow.From your questions, you don''t seem to understand CoW. CoW is basically an alternative to the logging/journalling used by most filesystems. When you change a data structure in a journalling filesystem, like ext4, you actually write two copies--one into the journal, and one that overwrites the old data structure. If a crash happens, at least one copy will still be valid, making recovery possible. When you change a data structure in a CoW filesystem, like btrfs, you only write one copy, but you DON''T write it over the old data structure. You write it to a new, unallocated space. This means the location of the data structure changed, so you have to change the parent data structure; you use CoW for that and so on up to the superblocks, which actually are overwritten. Once that''s finished, the old versions are no longer needed, so they will be unallocated and eventually overwritten. If a crash happens, the superblocks will still point to the old version of the data structures. This makes it relatively easy to add snapshot features--just add reference counting, and don''t free old versions of data structures if they''re still being used. However, this only happens if the user explicitly requests a snapshot. Otherwise, the old data structures are freed immediately once the new ones are completely written.> 1) Is COW only used when creating or updating a file? While testing BTRFS, using ''btrfs subvolume find-new'', I got the idea that neither creation of directories, nor any kind of deletion are covered by COW. Is this right?CoW is used anytime any structure is changed. find-new is not directly related to CoW.> 2) Each time a COW happens, is there any kind implicit ''snapshotting'' that may keep track of changes around the filesystem for each COW? > By Rodeh''s paper and some info on the wiki, I gather that a new root is created for each COW, due to shadowing, but will the previous tree be kept? The wiki, at "BTRFS Design", states that "after the commit finishes, the older subvolume root items may be removed". This would make impossible to track changes to files, but ''btrfs subvolume find-new'' still manages to output file generations, so there must be some info left behind.The old tree is discarded unless the user requested a snapshot of it. Every time btrfs updates the roots is a new generation. Some data structures have "generation" fields, indicating the generation in which they were most recently changed. This is mostly used to verify the filesystem is correct, but it''s also possible to scan the generation fields and find out which files have changed.> 3) Following (2), is there any way to access this informations and, let''s say, recover an older version of a given file? Or an entire previous tree?No, unless the user request a snapshot. I''m assuming you''re not talking about tools like PhotoRec, that try to reassemble files from whatever disk data looks valid.> 4) From Rodeh''s paper I got the idea that BTRFS uses periodic checkpointing, in order to assign generations to operations. Using ''btrfs subvolume find-new'' I confirmed my suspicions. After copying two different directories into the same subvolume at the same time, all files got assigned the same generation and it took a while until they all showed up. This raises the question: what triggers a new checkpoint? Is it based on elapsed time since last checkpoint? Is it triggered by a COW and then, all COWs happening at the same time will be put together and create a big new generation?Again, periodic checkpointing is probably the wrong way to think about it. It would be wasteful to overwrite the superblocks every time a change is made; instead, btrfs may combine multiple changes into one generation and only update the superblocks once. I''m not sure exactly how btrfs decides when to write a new generation.> 5) If we have multiple jobs updating the same file at the same time, I assume the system will shadow their updates; when the time for committing comes, will there be any kind of ''conflict'' between concurrent updates, or will they be applied by order of commit, ignoring whether there were previous commits or not? Regarding checkpointing, will all the changes be shown as part of the generation, or will they be considered as only one?This is handled just like in any other filesystem. There are no concurrent generations; if two threads both update a file, btrfs will handle the updates sequentially, one at a time. -- To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On 09/11/10 09:45, Sean Bartell wrote:> No, unless the user request a snapshot. I''m assuming you''re not talking > about tools like PhotoRec, that try to reassemble files from whatever > disk data looks valid.It may be that he has confused it with nilfs which does have automatic periodic checkpointing (and expiry thereof) based on a user configurable policy. These can be converted to persistent snapshots from the command line. cheers, Chris -- Chris Samuel : http://www.csamuel.org/ : Melbourne, VIC -- To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
First of all, thanks for all replies; they''ve been quite insightful. On Nov 8, 2010, at 10:45 PM, Sean Bartell wrote:> From your questions, you don''t seem to understand CoW. CoW is basically > an alternative to the logging/journalling used by most filesystems. >Actually, I do understand how CoW works. Although, maybe due to naiveté, I do lack some understanding on how it is applied on a full-fledged filesystem.>> 2) Each time a COW happens, is there any kind implicit ''snapshotting'' that may keep track of changes around the filesystem for each COW? >> By Rodeh''s paper and some info on the wiki, I gather that a new root is created for each COW, due to shadowing, but will the previous tree be kept? The wiki, at "BTRFS Design", states that "after the commit finishes, the older subvolume root items may be removed". This would make impossible to track changes to files, but ''btrfs subvolume find-new'' still manages to output file generations, so there must be some info left behind. > > The old tree is discarded unless the user requested a snapshot of it. > > Every time btrfs updates the roots is a new generation. Some data > structures have "generation" fields, indicating the generation in which > they were most recently changed. This is mostly used to verify the > filesystem is correct, but it''s also possible to scan the generation > fields and find out which files have changed.As Goffredo Baroncelli explained in a previous reply to my questions, the "find-new" command will search through keys with type BTRFS_EXTENT_DATA_TYPE. This command does print several changes to the same files throughout history since a given generation. My new question to this is rather simple: does BTRFS actually keep the data from this generations to which "find-new" has access, or is it only able to access information that records this changes?> >> 3) Following (2), is there any way to access this informations and, let''s say, recover an older version of a given file? Or an entire previous tree? > > No, unless the user request a snapshot. I''m assuming you''re not talking > about tools like PhotoRec, that try to reassemble files from whatever > disk data looks valid.You''re right. What I mean is for one to be able to actually recover an old, recently-modified version of a file -- somewhat like a versioning system. I believe to have read that both WAFL and ZFS have similar support. I do understand now that this is only possible if one explicitly creates a snapshot. However, I thought that, by using shadowing of the changed blocks, it could be quite inexpensive (aside from a storage point-of-view) to implicitly keep multiple "versions" of the tree --- unchanged blocks would be kept shared among "tree versions" until CoWed, if they were ever changed. With these versions one would be able to recover, or restore, a file or the entire filesystem, regardless of having created an explicit checkpoint. Then again, I understand this is not how it works with BTRFS, and neither do I have a clue if it is feasible such support.> >> 4) From Rodeh''s paper I got the idea that BTRFS uses periodic checkpointing, in order to assign generations to operations. Using ''btrfs subvolume find-new'' I confirmed my suspicions. After copying two different directories into the same subvolume at the same time, all files got assigned the same generation and it took a while until they all showed up. This raises the question: what triggers a new checkpoint? Is it based on elapsed time since last checkpoint? Is it triggered by a COW and then, all COWs happening at the same time will be put together and create a big new generation? > > Again, periodic checkpointing is probably the wrong way to think about > it. It would be wasteful to overwrite the superblocks every time a > change is made; instead, btrfs may combine multiple changes into one > generation and only update the superblocks once. I''m not sure exactly > how btrfs decides when to write a new generation.As Chris Samuel stated in another reply, at some point I did made the link between BTRFS'' checkpointing and NILFS''. Although I assumed BTRFS'' checkpointing was hardcoded somewhere in the code. If this is not the case, I''m still wondering how such decision is made, for I have not yet found where this checkpointing is happening in the code. Regards. --- João Eduardo Luís-- To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Tuesday, 09 November, 2010, João Eduardo Luís wrote:> > The old tree is discarded unless the user requested a snapshot of it. > > > > Every time btrfs updates the roots is a new generation. Some data > > structures have "generation" fields, indicating the generation in which > > they were most recently changed. This is mostly used to verify the > > filesystem is correct, but it''s also possible to scan the generation > > fields and find out which files have changed. > > As Goffredo Baroncelli explained in a previous reply to my questions, the"find-new" command will search through keys with type BTRFS_EXTENT_DATA_TYPE. This command does print several changes to the same files throughout history since a given generation. My new question to this is rather simple: does BTRFS actually keep the data from this generations to which "find-new" has access, or is it only able to access information that records this changes?>Btrfs stores the info in a btree. With the exception of the leaf, every block of the tree contains a list of a pair of key, pointer defined by the struct btrfs_key_ptr: struct btrfs_disk_key { __le64 objectid; u8 type; __le64 offset; } __attribute__ ((__packed__)); struct btrfs_key_ptr { struct btrfs_disk_key key; __le64 blockptr; __le64 generation; } __attribute__ ((__packed__)); The generation field, contains the info in which you are interested. So I think that the correct answer of your question is the second one. Regards G.Baroncelli -- gpg key@ keyserver.linux.it: Goffredo Baroncelli (ghigo) <kreijack@inwind.it> Key fingerprint = 4769 7E51 5293 D36C 814E C054 BF04 F161 3DC5 0512 -- To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html