https://reiser4.wiki.kernel.org/index.php?title=X0reiserfs&feed=atom&action=historyX0reiserfs - Revision history2024-03-28T23:49:37ZRevision history for this page on the wikiMediaWiki 1.19.24https://reiser4.wiki.kernel.org/index.php?title=X0reiserfs&diff=2182&oldid=prevChris goe: formatting fixes2010-12-21T11:47:24Z<p>formatting fixes</p>
<a href="https://reiser4.wiki.kernel.org/index.php?title=X0reiserfs&diff=2182&oldid=1748">Show changes</a>Chris goehttps://reiser4.wiki.kernel.org/index.php?title=X0reiserfs&diff=1748&oldid=prevChris goe: more cleanups to come...2010-04-25T04:54:47Z<p>more cleanups to come...</p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr valign='top'>
<td colspan='2' style="background-color: white; color:black;">← Older revision</td>
<td colspan='2' style="background-color: white; color:black;">Revision as of 04:54, 25 April 2010</td>
</tr><tr><td colspan="2" class="diff-lineno">Line 153:</td>
<td colspan="2" class="diff-lineno">Line 153:</td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>The disk Block  (Internal Node  of the tree is the place for keys and pointers to disk blocks)</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>The disk Block  (Internal Node  of the tree is the place for keys and pointers to disk blocks)</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>  Block_Head <del class="diffchange diffchange-inline"> </del>Key 0 <del class="diffchange diffchange-inline"> </del>Key 1 <del class="diffchange diffchange-inline"> </del>Key 2 --- <del class="diffchange diffchange-inline"> </del>Key N <del class="diffchange diffchange-inline"> </del>Pointer 0 <del class="diffchange diffchange-inline"> </del>Pointer 1 <del class="diffchange diffchange-inline"> </del>Pointer 2 <del class="diffchange diffchange-inline"> </del>--- <del class="diffchange diffchange-inline"> </del>Pointer N <del class="diffchange diffchange-inline">   </del>Pointer N+1 <del class="diffchange diffchange-inline"> </del>..Free Space..</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>  Block_Head <ins class="diffchange diffchange-inline"> </ins>Key 0 Key 1 Key 2 --- <ins class="diffchange diffchange-inline"> </ins>Key N <ins class="diffchange diffchange-inline"> </ins>Pointer 0 <ins class="diffchange diffchange-inline"> </ins>Pointer 1 Pointer 2 --- Pointer N Pointer N+1 <ins class="diffchange diffchange-inline"> </ins>..Free Space..</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>The disk Block  (Leaf Node  of the tree is the place for the Items and Items headers)</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>The disk Block  (Leaf Node  of the tree is the place for the Items and Items headers)</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>  Block_Head <del class="diffchange diffchange-inline"> </del>IHead 0 <del class="diffchange diffchange-inline"> </del>IHead 1 <del class="diffchange diffchange-inline"> </del>IHead 2 --- <del class="diffchange diffchange-inline"> </del>IHead N <del class="diffchange diffchange-inline"> .............</del>...Free Space...<del class="diffchange diffchange-inline">............. </del>Item N <del class="diffchange diffchange-inline"> </del>--- <del class="diffchange diffchange-inline"> </del>Item 2 <del class="diffchange diffchange-inline"> </del>Item 1 <del class="diffchange diffchange-inline"> </del>Item 0</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>  Block_Head <ins class="diffchange diffchange-inline"> </ins>IHead 0 <ins class="diffchange diffchange-inline"> </ins>IHead 1 <ins class="diffchange diffchange-inline"> </ins>IHead 2 --- IHead N <ins class="diffchange diffchange-inline"> </ins>...Free Space... Item N <ins class="diffchange diffchange-inline"> </ins>--- <ins class="diffchange diffchange-inline"> </ins>Item 2 <ins class="diffchange diffchange-inline"> </ins>Item 1 <ins class="diffchange diffchange-inline"> </ins>Item 0</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div><del class="diffchange diffchange-inline"> </del>The disk Block  (Unformatted Node  of the tree is the place for the data of the big file)</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>The disk Block  (Unformatted Node  of the tree is the place for the data of the big file)</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div><del class="diffchange diffchange-inline">..............................................................................................................................</del>...........................................................................</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>...........................................................................</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>ReiserFS objects: Files, Directories</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>ReiserFS objects: Files, Directories</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>Max number of objects = 2^32-4 = 4 294 967 292</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>Max number of objects = 2^32-4 = 4 294 967 292</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>Each object is a number of items :</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>Each object is a number of items:</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>Files items :</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>Files items:</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div><del class="diffchange diffchange-inline">1. StatData item + [Direct item]    (for small files : size from 0 bytes to MAX_DIRECT_ITEM_LEN=blocksize-112 bytes)</del></div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div><del class="diffchange diffchange-inline">2. StatData item + InDirect item + [Direct item]  (for big files    : size    > MAX_DIRECT_ITEM_LEN bytes)</del></div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>Directory items :</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins class="diffchange diffchange-inline">1. StatData item + [Direct item]  (for small files: size from 0 bytes to MAX_DIRECT_ITEM_LEN=blocksize-112 bytes)</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins class="diffchange diffchange-inline">2. StatData item + InDirect item + [Direct item]  (for big files: size > MAX_DIRECT_ITEM_LEN bytes)</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>Directory items:</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>1. StatData item + Directory item</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>1. StatData item + Directory item</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>Every reiserfs object has Object ID and Key .</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>Every reiserfs object has Object ID and Key .</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div><del style="color: red; font-weight: bold; text-decoration: none;"> </del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>Internal Node structures</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>Internal Node structures</div></td></tr>
<tr><td colspan="2" class="diff-lineno">Line 180:</td>
<td colspan="2" class="diff-lineno">Line 181:</td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>  Block_Head  Key 0 Key 1 Key 2 --- Key N Pointer 0 Pointer 1 Pointer 2 --- Pointer N   Pointer N+1 ..Free Space..</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>  Block_Head  Key 0 Key 1 Key 2 --- Key N Pointer 0 Pointer 1 Pointer 2 --- Pointer N   Pointer N+1 ..Free Space..</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins style="color: red; font-weight: bold; text-decoration: none;"><pre></ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>struct block_head</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>struct block_head</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>Field Name Type Size (in bytes) Description</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>Field Name Type Size (in bytes) Description</div></td></tr>
<tr><td colspan="2" class="diff-lineno">Line 283:</td>
<td colspan="2" class="diff-lineno">Line 285:</td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>fileName - the name of the file (array of bytes of variable length).</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>fileName - the name of the file (array of bytes of variable length).</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>Max length of file name = blocksize - 64 (for 4kb blocksize Max name length  = 4032 bytes).</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>Max length of file name = blocksize - 64 (for 4kb blocksize Max name length  = 4032 bytes).</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins style="color: red; font-weight: bold; text-decoration: none;"></pre></ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>= Using the Tree to Optimize Layout of Files =</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>= Using the Tree to Optimize Layout of Files =</div></td></tr>
</table>Chris goehttps://reiser4.wiki.kernel.org/index.php?title=X0reiserfs&diff=1747&oldid=prevChris goe: use *2010-04-25T04:50:02Z<p>use *</p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr valign='top'>
<td colspan='2' style="background-color: white; color:black;">← Older revision</td>
<td colspan='2' style="background-color: white; color:black;">Revision as of 04:50, 25 April 2010</td>
</tr><tr><td colspan="2" class="diff-lineno">Line 442:</td>
<td colspan="2" class="diff-lineno">Line 442:</td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>I personally favor performing a balance of commercial and public works in my life.  I have no axe to grind against software that is charged for, and no regrets at making reiserfs freely available to Linux users.  This project is GPL'd, but I sell exceptions to the GPL to commercial OS vendors and file server vendors.  It is not usable to them without such exceptions, and many of them are wise enough to understand that:</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>I personally favor performing a balance of commercial and public works in my life.  I have no axe to grind against software that is charged for, and no regrets at making reiserfs freely available to Linux users.  This project is GPL'd, but I sell exceptions to the GPL to commercial OS vendors and file server vendors.  It is not usable to them without such exceptions, and many of them are wise enough to understand that:</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div><del class="diffchange diffchange-inline">    </del>* the porting and integration service we are able to provide with the licensing is by itself worth what we charge,</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>* the porting and integration service we are able to provide with the licensing is by itself worth what we charge,</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div><del class="diffchange diffchange-inline">    </del>* that these services impact their time to market,</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>* that these services impact their time to market,</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div><del class="diffchange diffchange-inline">    </del>* and that the relationship spreads the development costs across more OS vendors than just them alone</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>* and that the relationship spreads the development costs across more OS vendors than just them alone</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>I expect that Linux will prove to be quite effective in market sampling my intended market, but if you suspect that I also like seeing more people use it even if it is free to them, oh well.</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>I expect that Linux will prove to be quite effective in market sampling my intended market, but if you suspect that I also like seeing more people use it even if it is free to them, oh well.</div></td></tr>
<tr><td colspan="2" class="diff-lineno">Line 450:</td>
<td colspan="2" class="diff-lineno">Line 450:</td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>I believe it is not so much the cost that has made Linux so successful as it is the openness.  Linux is a decentralized economy with honor and recognition as the currency of payment (and thus there is much honor in it).  Commercial OS vendors are, at the moment, all closed economies, and doomed to fall in their competition with open economies just as communism eventually fell.  At some point an OS vendor will realize that if it:</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>I believe it is not so much the cost that has made Linux so successful as it is the openness.  Linux is a decentralized economy with honor and recognition as the currency of payment (and thus there is much honor in it).  Commercial OS vendors are, at the moment, all closed economies, and doomed to fall in their competition with open economies just as communism eventually fell.  At some point an OS vendor will realize that if it:</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div><del class="diffchange diffchange-inline">    </del>* opens up its source code to decentralized modification,</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>* opens up its source code to decentralized modification,</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div><del class="diffchange diffchange-inline">    </del>* systematically rewards those who perform the modifications that are proven useful,</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>* systematically rewards those who perform the modifications that are proven useful,</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div><del class="diffchange diffchange-inline">    </del>* systematically merges/integrates those modifications into its branded primary release branch while adding value as the integrator,</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>* systematically merges/integrates those modifications into its branded primary release branch while adding value as the integrator,</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>that it will acquire both the critical mass of the internet development community, and the aggressive edge that no large communal group (such as a corporation) can have.  Rather than saying to any such vendor that they should do this now, let me simply point out that whoever is first will have an enormous advantage.....</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>that it will acquire both the critical mass of the internet development community, and the aggressive edge that no large communal group (such as a corporation) can have.  Rather than saying to any such vendor that they should do this now, let me simply point out that whoever is first will have an enormous advantage.....</div></td></tr>
</table>Chris goehttps://reiser4.wiki.kernel.org/index.php?title=X0reiserfs&diff=1746&oldid=prevChris goe: use *2010-04-25T04:47:58Z<p>use *</p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr valign='top'>
<td colspan='2' style="background-color: white; color:black;">← Older revision</td>
<td colspan='2' style="background-color: white; color:black;">Revision as of 04:47, 25 April 2010</td>
</tr><tr><td colspan="2" class="diff-lineno">Line 416:</td>
<td colspan="2" class="diff-lineno">Line 416:</td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>Many techniques from other file systems haven't been applied primarily so as to satisfy my goal of giving reiserfs 1.0 only the minimum feature set necessary to be useful, and will appear in later releases. Log Structured File Systems [Rosenblum and Ousterhout] embody several such techniques, which I will describe after I mention two concerns with that approach:</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>Many techniques from other file systems haven't been applied primarily so as to satisfy my goal of giving reiserfs 1.0 only the minimum feature set necessary to be useful, and will appear in later releases. Log Structured File Systems [Rosenblum and Ousterhout] embody several such techniques, which I will describe after I mention two concerns with that approach:</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div><del class="diffchange diffchange-inline">    </del>* With small object file systems it is not feasible to cache in RAM a map of objectid to location for every object since there are too many objects. This is an inherent problem in using temporal packing rather than semantic packing for small object file systems. With my approach my internal nodes are the equivalent of this objectid to location map, but internal node total size is proportional to the number of nodes rather than the number of objects. You can think of internal nodes as a compression of object location information made effective by the existence of an ordering function, and this compression is both essential for small files, and a major feature of my approach.</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>* With small object file systems it is not feasible to cache in RAM a map of objectid to location for every object since there are too many objects. This is an inherent problem in using temporal packing rather than semantic packing for small object file systems. With my approach my internal nodes are the equivalent of this objectid to location map, but internal node total size is proportional to the number of nodes rather than the number of objects. You can think of internal nodes as a compression of object location information made effective by the existence of an ordering function, and this compression is both essential for small files, and a major feature of my approach.</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div><del class="diffchange diffchange-inline">    </del>* I like obtaining good though not ideal semantic locality without paying a cleaning cost for active data. This is a less critical concern.</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>* I like obtaining good though not ideal semantic locality without paying a cleaning cost for active data. This is a less critical concern.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>I frequently find myself classifying packing and layout optimizations as either appropriate for implementing dynamically or appropriate only for a cleaner. Optimizations whose computational overhead is large compared to their benefit tend to be appropriate for implementation in a cleaner, and a cleaner's benefits mostly impact the static portion of the file system (which typically consumes ~80% of the space.) Such objectives as 100% packing efficiency, exactly ordering block layout by semantic order, using the full semantic tree rather than parent directory in determining semantic order, compression, these are all best implemented by cleaner approaches. In summary, there is much to be learned from the LFS approach, and as I move past my initial objective of supplying a minimal feature higher performance FS I will apply some of those lessons.</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>I frequently find myself classifying packing and layout optimizations as either appropriate for implementing dynamically or appropriate only for a cleaner. Optimizations whose computational overhead is large compared to their benefit tend to be appropriate for implementation in a cleaner, and a cleaner's benefits mostly impact the static portion of the file system (which typically consumes ~80% of the space.) Such objectives as 100% packing efficiency, exactly ordering block layout by semantic order, using the full semantic tree rather than parent directory in determining semantic order, compression, these are all best implemented by cleaner approaches. In summary, there is much to be learned from the LFS approach, and as I move past my initial objective of supplying a minimal feature higher performance FS I will apply some of those lessons.</div></td></tr>
</table>Chris goehttps://reiser4.wiki.kernel.org/index.php?title=X0reiserfs&diff=1745&oldid=prevChris goe: cleanup2010-04-25T04:47:16Z<p>cleanup</p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr valign='top'>
<td colspan='2' style="background-color: white; color:black;">← Older revision</td>
<td colspan='2' style="background-color: white; color:black;">Revision as of 04:47, 25 April 2010</td>
</tr><tr><td colspan="2" class="diff-lineno">Line 286:</td>
<td colspan="2" class="diff-lineno">Line 286:</td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>= Using the Tree to Optimize Layout of Files =</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>= Using the Tree to Optimize Layout of Files =</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>There are four levels at which layout optimization is performed: <del class="diffchange diffchange-inline">1) </del>the mapping of logical block numbers to physical locations on disk <del class="diffchange diffchange-inline">2) </del>the assigning of nodes to logical block numbers<del class="diffchange diffchange-inline">, 3) </del>the ordering of objects within the tree, and <del class="diffchange diffchange-inline">4) </del>the balancing of the objects across the nodes they are packed into.</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>There are four levels at which layout optimization is performed:</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins class="diffchange diffchange-inline"># </ins>the mapping of logical block numbers to physical locations on disk</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins class="diffchange diffchange-inline"># </ins>the assigning of nodes to logical block numbers</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins class="diffchange diffchange-inline"># </ins>the ordering of objects within the tree, and</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins class="diffchange diffchange-inline"># </ins>the balancing of the objects across the nodes they are packed into.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>== Physical Layout ==</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>== Physical Layout ==</div></td></tr>
<tr><td colspan="2" class="diff-lineno">Line 314:</td>
<td colspan="2" class="diff-lineno">Line 319:</td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>When balancing nodes I do so according to the following ordered priorities:</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>When balancing nodes I do so according to the following ordered priorities:</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div><del class="diffchange diffchange-inline">  1. </del>minimize number of nodes used</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins class="diffchange diffchange-inline"># </ins>minimize number of nodes used</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div><del class="diffchange diffchange-inline">  2. </del>minimize number of nodes affected by the balancing operation</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins class="diffchange diffchange-inline"># </ins>minimize number of nodes affected by the balancing operation</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div><del class="diffchange diffchange-inline">  3. </del>minimize the number of uncached nodes affected by the balancing operation</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins class="diffchange diffchange-inline"># </ins>minimize the number of uncached nodes affected by the balancing operation</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div><del class="diffchange diffchange-inline">  4. </del>if shifting to another formatted node is necessary, maximize the bytes shifted</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins class="diffchange diffchange-inline"># </ins>if shifting to another formatted node is necessary, maximize the bytes shifted</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>Priority 4) is based on the assumption that the location of an insertion of bytes into the tree is an indication of the likely future location of an insertion, and that policy 4 will on average reduce the number of formatted nodes affected by future balance operations. There are more subtle effects as well, in that if one randomly places nodes next to each other, and one has a choice between those nodes being mostly moderately efficiently packed or packed to an extreme of either well or poorly packed, one is more likely to be able to combine more of the nodes if one chooses the policy of extremism. Extremism is a virtue in space efficient node packing. The maximal shift policy is not applied to internal nodes, as extremism is not a virtue in time efficient internal node balancing.</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>Priority 4) is based on the assumption that the location of an insertion of bytes into the tree is an indication of the likely future location of an insertion, and that policy 4 will on average reduce the number of formatted nodes affected by future balance operations. There are more subtle effects as well, in that if one randomly places nodes next to each other, and one has a choice between those nodes being mostly moderately efficiently packed or packed to an extreme of either well or poorly packed, one is more likely to be able to combine more of the nodes if one chooses the policy of extremism. Extremism is a virtue in space efficient node packing. The maximal shift policy is not applied to internal nodes, as extremism is not a virtue in time efficient internal node balancing.</div></td></tr>
<tr><td colspan="2" class="diff-lineno">Line 343:</td>
<td colspan="2" class="diff-lineno">Line 348:</td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>The new scheme will continue to first determine the node it should be placed near, and then start the search for an empty block from that spot, but it will use a more complicated determination of what node to place it near.  This method will cause all nodes from the same packing locality to be near each other, will cause all directory entries and stat_data to be grouped together within that packing locality, and will interleaved formatted and unformatted nodes from the same packing locality.  Pseudo-code is best for describing this:</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>The new scheme will continue to first determine the node it should be placed near, and then start the search for an empty block from that spot, but it will use a more complicated determination of what node to place it near.  This method will cause all nodes from the same packing locality to be near each other, will cause all directory entries and stat_data to be grouped together within that packing locality, and will interleaved formatted and unformatted nodes from the same packing locality.  Pseudo-code is best for describing this:</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins style="color: red; font-weight: bold; text-decoration: none;"><pre></ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>/* for use by reiserfs_get_new_blocknrs when determining where in the bitmap to</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>/* for use by reiserfs_get_new_blocknrs when determining where in the bitmap to</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>start the search for a free block, and for use by read-ahead algorithm when</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>start the search for a free block, and for use by read-ahead algorithm when</div></td></tr>
<tr><td colspan="2" class="diff-lineno">Line 379:</td>
<td colspan="2" class="diff-lineno">Line 385:</td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>     right-handed version of get_logical_layout_left_neighbors_blocknr logic</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>     right-handed version of get_logical_layout_left_neighbors_blocknr logic</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>}</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>}</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins style="color: red; font-weight: bold; text-decoration: none;"></pre></ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>It is my hope that this will improve caching of pointers to unformatted nodes, plus improving caching of directory entries and stat_data, by separating them from file bodies to a greater extent.  I also hope that it will improve read performance for 1-10k files, and that it will allow us to do this without decreasing space efficiency.</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>It is my hope that this will improve caching of pointers to unformatted nodes, plus improving caching of directory entries and stat_data, by separating them from file bodies to a greater extent.  I also hope that it will improve read performance for 1-10k files, and that it will allow us to do this without decreasing space efficiency.</div></td></tr>
</table>Chris goehttps://reiser4.wiki.kernel.org/index.php?title=X0reiserfs&diff=1724&oldid=prevChris goe: moved ReiserFS to X0reiserfs: We'll use the ReiserFS article for something else2010-04-25T04:15:04Z<p>moved <a href="/index.php/ReiserFS" class="mw-redirect" title="ReiserFS">ReiserFS</a> to <a href="/index.php/X0reiserfs" title="X0reiserfs">X0reiserfs</a>: We'll use the ReiserFS article for something else</p>
<table class='diff diff-contentalign-left'>
<tr valign='top'>
<td colspan='1' style="background-color: white; color:black;">← Older revision</td>
<td colspan='1' style="background-color: white; color:black;">Revision as of 04:15, 25 April 2010</td>
</tr></table>Chris goehttps://reiser4.wiki.kernel.org/index.php?title=X0reiserfs&diff=1723&oldid=prevChris goe: cleanup2010-04-25T04:10:50Z<p>cleanup</p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr valign='top'>
<td colspan='2' style="background-color: white; color:black;">← Older revision</td>
<td colspan='2' style="background-color: white; color:black;">Revision as of 04:10, 25 April 2010</td>
</tr><tr><td colspan="2" class="diff-lineno">Line 466:</td>
<td colspan="2" class="diff-lineno">Line 466:</td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>* [C-FFS] Ganger, Gregory R., Kaashoek, M. Frans, [http://www.ece.cmu.edu/~ganger/papers/cffs.html Embedded Inodes and Explicit Grouping: Exploiting Disk Bandwidth for Small Files]. A very well written paper focused on 1-10k file size issues, they use some similar notions (most especially their concept of grouping compared to my packing localities). Note that they focus on the 1-10k file size range, and not the sub-1k range. The 1-10k range is the weakpoint in reiserfs performance.</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>* [C-FFS] Ganger, Gregory R., Kaashoek, M. Frans, [http://www.ece.cmu.edu/~ganger/papers/cffs.html Embedded Inodes and Explicit Grouping: Exploiting Disk Bandwidth for Small Files]. A very well written paper focused on 1-10k file size issues, they use some similar notions (most especially their concept of grouping compared to my packing localities). Note that they focus on the 1-10k file size range, and not the sub-1k range. The 1-10k range is the weakpoint in reiserfs performance.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>* [ext2fs] by Rémy Card, [http://e2fsprogs.sourceforge.net/ext2intro.html <del class="diffchange diffchange-inline">extensive information</del>], source code is available When you consider how small this file system is (~6000 lines), its effectiveness becomes all the more remarkable.</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>* [ext2fs] by Rémy Card, [http://e2fsprogs.sourceforge.net/ext2intro.html <ins class="diffchange diffchange-inline">Design and Implementation of the Second Extended Filesystem</ins>]<ins class="diffchange diffchange-inline">. Extensive information</ins>, source code is available When you consider how small this file system is (~6000 lines), its effectiveness becomes all the more remarkable.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>* [FFS] M.K. McKusick, W.N. Joy, S.J. Leffler, and R.S. Fabry. A fast file system for UNIX. ACM Transactions on Computer Systems, 2(3):181--197, August 1984 describes the implementation of a file system which employs parent directory location knowledge in determining file layout. It uses large blocks for all but the tail of files to improve I/O performance, and uses small blocks called fragments for the tails so as to reduce the cost due to internal fragmentation. Numerous other improvements are also made to what was once the state-of-the-art. FFS remains the architectural foundation for many current block allocation file systems, and was later bundled with the standard Unix releases. Note that unrequested serialization and the use of fragments places it at a performance disadvantage to ext2fs, though whether ext2fs is thereby made less reliable is a matter of dispute that I take no position on (reiserfs uses preserve lists, forgive my egotism in thinking that it is enough work for me to ensure that reiserfs solves the recovery problem, and to perhaps suggest that ext2fs would benefit from the use of preserve lists when shrinking directories)</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>* [FFS] M.K. McKusick, W.N. Joy, S.J. Leffler, and R.S. Fabry. <ins class="diffchange diffchange-inline">[http://www.eecs.berkeley.edu/~brewer/cs262/FFS.pdf </ins>A fast file system for UNIX<ins class="diffchange diffchange-inline">]</ins>. ACM Transactions on Computer Systems, 2(3):181--197, August 1984 describes the implementation of a file system which employs parent directory location knowledge in determining file layout. It uses large blocks for all but the tail of files to improve I/O performance, and uses small blocks called fragments for the tails so as to reduce the cost due to internal fragmentation. Numerous other improvements are also made to what was once the state-of-the-art. FFS remains the architectural foundation for many current block allocation file systems, and was later bundled with the standard Unix releases. Note that unrequested serialization and the use of fragments places it at a performance disadvantage to ext2fs, though whether ext2fs is thereby made less reliable is a matter of dispute that I take no position on (reiserfs uses preserve lists, forgive my egotism in thinking that it is enough work for me to ensure that reiserfs solves the recovery problem, and to perhaps suggest that ext2fs would benefit from the use of preserve lists when shrinking directories)</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>* [Ganger] Gregory R. Ganger, Yale N. Patt, <del class="diffchange diffchange-inline">``</del>Metadata Update Performance in File Systems<del class="diffchange diffchange-inline">'' abstract only</del></div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>* [Ganger] Gregory R. Ganger, Yale N. Patt, <ins class="diffchange diffchange-inline">[http://pages.cs.wisc.edu/~remzi/Classes/838/Fall2001/Papers/softupdates-osdi94.pdf </ins>Metadata Update Performance in File Systems<ins class="diffchange diffchange-inline">]</ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>* [Gifford], <del class="diffchange diffchange-inline">postscript only </del>Describes a file system enriched to have more than hierarchical semantics, he shares many goals with this author, forgive me for thinking his work worthwhile. If I had to suggest one improvement in a sentence, I would say his semantic algebra needs closure.</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>* [Gifford], <ins class="diffchange diffchange-inline">[http://portal.acm.org/citation.cfm?id=121133.121138 Semantic file systems]. </ins>Describes a file system enriched to have more than hierarchical semantics<ins class="diffchange diffchange-inline">]</ins>, he shares many goals with this author, forgive me for thinking his work worthwhile. If I had to suggest one improvement in a sentence, I would say his semantic algebra needs closure.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>* [Hitz, Dave]http://<del class="diffchange diffchange-inline">www</del>.netapp.com/<del class="diffchange diffchange-inline">technology</del>/<del class="diffchange diffchange-inline">level3/3002</del>.<del class="diffchange diffchange-inline">html  </del>A rather well designed file system optimized for NFS and RAID in combination.  Note that RAID increases the merits of write-optimization in block layout algorithms.</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>* [Hitz, Dave] <ins class="diffchange diffchange-inline">[</ins>http://<ins class="diffchange diffchange-inline">media</ins>.netapp.com/<ins class="diffchange diffchange-inline">documents</ins>/<ins class="diffchange diffchange-inline">wp_3002.pdf File System Design for an NFS File Server Appliance]</ins>. A rather well designed file system optimized for NFS and RAID in combination.  Note that RAID increases the merits of write-optimization in block layout algorithms.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>* [Holton and Das] , Holton, Mike., Das, Raj., <del class="diffchange diffchange-inline">``</del>The XFS space manager and namespace manager use sophisticated B-Tree indexing technology to represent file location information contained inside directory files and to represent the structure of the files themselves (location of information in a file).<del class="diffchange diffchange-inline">'' </del>Note that it is still a block (extent) allocation based file system, no attempt is made to store the actual file contents in the tree. It is targeted at the needs of the other end of the file size usage spectrum from reiserfs, and is an excellent design for that purpose (and I would concede that reiserfs 1.0 is not suitable for their real-time large I/O market.) SGI has also traditionally been a leader in resisting the use of unrequested serialization of I/O. Unfortunately, the paper is a bit vague on details, and source code is not freely available.</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>* [Holton and Das] , Holton, Mike., Das, Raj., <ins class="diffchange diffchange-inline">[http://www.uoks.uj.edu.pl/resources/flugor/IRIX/xfs-whitepaper.html XFS: A Next Generation Journalled 64-Bit Filesystem With Guaranteed Rate I/O]: "</ins>The XFS space manager and namespace manager use sophisticated B-Tree indexing technology to represent file location information contained inside directory files and to represent the structure of the files themselves (location of information in a file).<ins class="diffchange diffchange-inline">" </ins>Note that it is still a block (extent) allocation based file system, no attempt is made to store the actual file contents in the tree. It is targeted at the needs of the other end of the file size usage spectrum from reiserfs, and is an excellent design for that purpose (and I would concede that reiserfs 1.0 is not suitable for their real-time large I/O market.) SGI has also traditionally been a leader in resisting the use of unrequested serialization of I/O. Unfortunately, the paper is a bit vague on details, and source code is not freely available.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>* [Howard] <del class="diffchange diffchange-inline">``</del>Scale and Performance in a Distributed File System<del class="diffchange diffchange-inline">''</del>, Howard, J.H., Kazar, M.L., Menees, S.G., Nichols, D.A., Satayanarayanan, N., Sidebotham, R.N., West, M.J., ACM Transactions on Computer Systems, 6(1), February 1988 A classic benchmark, it was too CPU bound for both ext2fs and reiserfs.</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>* [Howard] <ins class="diffchange diffchange-inline">[http://www.cs.cmu.edu/~satya/docdir/s11.pdf </ins>Scale and Performance in a Distributed File System<ins class="diffchange diffchange-inline">]</ins>, Howard, J.H., Kazar, M.L., Menees, S.G., Nichols, D.A., Satayanarayanan, N., Sidebotham, R.N., West, M.J., ACM Transactions on Computer Systems, 6(1), February 1988 A classic benchmark, it was too CPU bound for both ext2fs and reiserfs.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>* [Knuth] Knuth, D.E., The Art of Computer Programming, Vol. 3 (Sorting and Searching), Addison-Wesley, Reading, MA, 1973, the earliest reference discussing trees storing records of varying length.</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>* [Knuth] Knuth, D.E., <ins class="diffchange diffchange-inline">[http://www-cs-faculty.stanford.edu/~knuth/taocp.html </ins>The Art of Computer Programming<ins class="diffchange diffchange-inline">]</ins>, Vol. 3 (Sorting and Searching), Addison-Wesley, Reading, MA, 1973, the earliest reference discussing trees storing records of varying length.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>* [LADDIS] Wittle, Mark., and Bruce, Keith., <del class="diffchange diffchange-inline">``</del>LADDIS: The Next Generation in NFS File Server Benchmarking<del class="diffchange diffchange-inline">''</del>, Proceedings of the Summer 1993 USENIX Conference.'', July 1993, pp. 111-128</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>* [LADDIS] Wittle, Mark., and Bruce, Keith., <ins class="diffchange diffchange-inline">[http://www.spec.org/sfs93/doc/WhitePaper.ps </ins>LADDIS: The Next Generation in NFS File Server Benchmarking<ins class="diffchange diffchange-inline">]</ins>, Proceedings of the Summer 1993 USENIX Conference.'', July 1993, pp. 111-128</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>* [Lewis and Denenberg] Lewis, Harry R., Denenberg, Larry <del class="diffchange diffchange-inline">``</del>Data Structures & Their Algorithms<del class="diffchange diffchange-inline">''</del>, HarperCollins Publishers, NY, NY, 1991, an algorithms textbook suitable for readers wishing to learn about balanced trees and their AVL predecessors.</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>* [Lewis and Denenberg] Lewis, Harry R., Denenberg, Larry <ins class="diffchange diffchange-inline">[http://portal.acm.org/citation.cfm?id=548586 </ins>Data Structures & Their Algorithms<ins class="diffchange diffchange-inline">]</ins>, HarperCollins Publishers, NY, NY, 1991, an algorithms textbook suitable for readers wishing to learn about balanced trees and their AVL predecessors.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>* [McCreight] McCreight, E.M., Pagination of B*-trees with variable length records, Commun. ACM 20 (9), 670-674, 1977, describes algorithms for trees with variable length records.</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>* [McCreight] McCreight, E.M., <ins class="diffchange diffchange-inline">[http://portal.acm.org/citation.cfm?id=359839 </ins>Pagination of B*-trees with variable length records<ins class="diffchange diffchange-inline">]</ins>, Commun. ACM 20 (9), 670-674, 1977, describes algorithms for trees with variable length records.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>* [McVoy and Kleiman], <del class="diffchange diffchange-inline">the </del>implementation of write-clustering for Sun's UFS.</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>* [McVoy and Kleiman], <ins class="diffchange diffchange-inline">[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.55.2970&rep=rep1&type=pdf Extent−like Performance from a UNIX File System]: The </ins>implementation of write-clustering for Sun's UFS.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>* [OLE] <del class="diffchange diffchange-inline">``</del>Inside OLE<del class="diffchange diffchange-inline">'' </del>by Kraig Brockshmidt, discusses Structured Storage<del class="diffchange diffchange-inline">, HREF="http://www.microsoft.com/mspress/books/abs/5-843-2b.htm" abstract only</del></div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>* [OLE] <ins class="diffchange diffchange-inline">[http://portal.acm.org/citation.cfm?id=207534 </ins>Inside OLE<ins class="diffchange diffchange-inline">] </ins>by Kraig Brockshmidt, discusses Structured Storage</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>* [Ousterhout] J.K. Ousterhout, H. Da Costa, D. Harrison, J.A. Kunze, M.D. Kupfer, and J.G. Thompson. A trace-driven analysis of the UNIX 4.2BSD file system. In Proceedings of the 10th Symposium on Operating Systems Principles, pages 15<del class="diffchange diffchange-inline">-</del>-24, Orcas Island, WA, December 1985.</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>* [Ousterhout] J.K. Ousterhout, H. Da Costa, D. Harrison, J.A. Kunze, M.D. Kupfer, and J.G. Thompson. <ins class="diffchange diffchange-inline">[http://portal.acm.org/citation.cfm?id=323627.323631 </ins>A trace-driven analysis of the UNIX 4.2BSD file system<ins class="diffchange diffchange-inline">]</ins>. In Proceedings of the 10th Symposium on Operating Systems Principles, pages 15-24, Orcas Island, WA, December 1985.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>* [NTFS] <del class="diffchange diffchange-inline">``</del>Inside the Windows NT File System<del class="diffchange diffchange-inline">'' the </del>book is written by Helen Custer, NTFS is architected by Tom Miller with contributions by Gary Kimura, Brian Andrew, and David Goebel, Microsoft Press, 1994, an easy to read little book, they fundamentally disagree with me on adding serialization of I/O not requested by the application programmer, and I note that the performance penalty they pay for their decision is high, especially compared with ext2fs. Their FS design is perhaps optimal for floppies and other hardware eject media beyond OS control. A less serialized higher performance log structured architecture is described in [Rosenblum and Ousterhout]. That said, Microsoft is to be commended for recognizing the importance of attempting to optimize for small files, and leading the OS designer effort to integrate small objects into the file name space. This book is notable for not referencing the work of persons not working for Microsoft, or providing any form of proper attribution to previous authors such as [Rosenblum and Ousterhout].</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>* [NTFS] <ins class="diffchange diffchange-inline">[http://portal.acm.org/citation.cfm?id=527752 </ins>Inside the Windows NT File System<ins class="diffchange diffchange-inline">]. The </ins>book is written by Helen Custer, NTFS is architected by Tom Miller with contributions by Gary Kimura, Brian Andrew, and David Goebel, Microsoft Press, 1994, an easy to read little book, they fundamentally disagree with me on adding serialization of I/O not requested by the application programmer, and I note that the performance penalty they pay for their decision is high, especially compared with ext2fs. Their FS design is perhaps optimal for floppies and other hardware eject media beyond OS control. A less serialized higher performance log structured architecture is described in [Rosenblum and Ousterhout]. That said, Microsoft is to be commended for recognizing the importance of attempting to optimize for small files, and leading the OS designer effort to integrate small objects into the file name space. This book is notable for not referencing the work of persons not working for Microsoft, or providing any form of proper attribution to previous authors such as [Rosenblum and Ousterhout].</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>* [Peacock] <del class="diffchange diffchange-inline">K</del>. Peacock, <del class="diffchange diffchange-inline">``</del>The CounterPoint Fast File System<del class="diffchange diffchange-inline">''</del>, Proceedings of the Usenix Conference Winter 1988</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>* [Peacock] <ins class="diffchange diffchange-inline">Dr</ins>. <ins class="diffchange diffchange-inline">J. Kent </ins>Peacock, <ins class="diffchange diffchange-inline">"</ins>The CounterPoint Fast File System<ins class="diffchange diffchange-inline">"</ins>, Proceedings of the Usenix Conference Winter 1988</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>* [Pike]  Rob Pike and Peter Weinberger, The Hideous Name, USENIX Summer 1985 Conference Proceedings, pp. 563, Portland Oregon, 1985.  Short, informal, and drives home why inconsistent naming schemes in an OS are detrimental. <del class="diffchange diffchange-inline">http://achille.cs.bell-labs.com/cm/cs/doc/85/1-05.ps.gz </del>His discussion of naming in plan 9: http://plan9.bell-labs.com/<del class="diffchange diffchange-inline">plan9</del>/doc/names.html</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>* [Pike]  Rob Pike and Peter Weinberger, <ins class="diffchange diffchange-inline">[http://pdos.csail.mit.edu/~rsc/pike85hideous.pdf </ins>The Hideous Name<ins class="diffchange diffchange-inline">]</ins>, USENIX Summer 1985 Conference Proceedings, pp. 563, Portland Oregon, 1985.  Short, informal, and drives home why inconsistent naming schemes in an OS are detrimental. His discussion of naming in plan 9: <ins class="diffchange diffchange-inline">[</ins>http://plan9.bell-labs.com/<ins class="diffchange diffchange-inline">sys</ins>/doc/names.html <ins class="diffchange diffchange-inline">The Use of Name Spaces in Plan 9]</ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>* [Rosenblum and Ousterhout] <del class="diffchange diffchange-inline">``</del>The Design and Implementation of a Log-Structured File System<del class="diffchange diffchange-inline">''</del>, Mendel Rosenblum and John K. Ousterhout, February 1992 ACM Transactions on Computer Systems, this paper was quite influential in a number of ways on many modern file systems, and the notion of using a cleaner may be applied to a future release of reiserfs. There is an interesting on-going debate over the relative merits of FFS vs. LFS architectures, and the interested reader may peruse http://www.<del class="diffchange diffchange-inline">scriptics</del>.<del class="diffchange diffchange-inline">com</del>/<del class="diffchange diffchange-inline">people</del>/<del class="diffchange diffchange-inline">john.ousterhout</del>/<del class="diffchange diffchange-inline">seltzer93.html </del>and the arguments by Margo Seltzer it links to.</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>* [Rosenblum and Ousterhout] <ins class="diffchange diffchange-inline">[http://www.eecs.berkeley.edu/~brewer/cs262/LFS.pdf </ins>The Design and Implementation of a Log-Structured File System<ins class="diffchange diffchange-inline">]</ins>, Mendel Rosenblum and John K. Ousterhout, February 1992 ACM Transactions on Computer Systems, this paper was quite influential in a number of ways on many modern file systems, and the notion of using a cleaner may be applied to a future release of reiserfs. There is an interesting on-going debate over the relative merits of FFS vs. LFS architectures, and the interested reader may peruse <ins class="diffchange diffchange-inline">[</ins>http://www.<ins class="diffchange diffchange-inline">eecs</ins>.<ins class="diffchange diffchange-inline">harvard.edu</ins>/<ins class="diffchange diffchange-inline">~margo</ins>/<ins class="diffchange diffchange-inline">papers</ins>/<ins class="diffchange diffchange-inline">icde93/ Transaction Support in a Log-Structured File System] </ins>and the arguments by Margo Seltzer it links to.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>* [Snyder] , <del class="diffchange diffchange-inline">``</del>tmpfs: A Virtual Memory File System<del class="diffchange diffchange-inline">'' </del>discusses a file system built to use swap space and intended for temporary files, due to a complete lack of disk synchronization it offers extremely high performance.</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>* [Snyder] , <ins class="diffchange diffchange-inline">[http://www.solarisinternals.com/si/reading/tmpfs.pdf </ins>tmpfs: A Virtual Memory File System<ins class="diffchange diffchange-inline">] </ins>discusses a file system built to use swap space and intended for temporary files, due to a complete lack of disk synchronization it offers extremely high performance.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>* [Vahalia] Uresh Vahalia, <del class="diffchange diffchange-inline">``Unix Kernal Internals''</del></div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>* [Vahalia] Uresh Vahalia, <ins class="diffchange diffchange-inline">[http://books.google.com/books?as_isbn=0131019082 UNIX internals: the new frontiers]</ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>[[category:ReiserFS]]</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>[[category:ReiserFS]]</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>[[category:Formatting-fixes-needed]]</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>[[category:Formatting-fixes-needed]]</div></td></tr>
</table>Chris goehttps://reiser4.wiki.kernel.org/index.php?title=X0reiserfs&diff=1722&oldid=prevChris goe: formatting fixes2010-04-25T03:34:58Z<p>formatting fixes</p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr valign='top'>
<td colspan='2' style="background-color: white; color:black;">← Older revision</td>
<td colspan='2' style="background-color: white; color:black;">Revision as of 03:34, 25 April 2010</td>
</tr><tr><td colspan="2" class="diff-lineno">Line 454:</td>
<td colspan="2" class="diff-lineno">Line 454:</td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>= References =</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>= References =</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>G.M. Adel'son-Vel'skii and E.M. Landis, An algorithm for the organization of information, Soviet Math. Doklady 3, 1259-1262, 1972, This paper on AVL trees can be thought of as the founding paper of the field of storing data in trees. Those not conversant in Russian will want to read the [Lewis and Denenberg] treatment of AVL trees in its place. [Wood] contains a modern treatment of trees.</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins class="diffchange diffchange-inline">* </ins>G.M. Adel'son-Vel'skii and E.M. Landis, <ins class="diffchange diffchange-inline">[http://en.scientificcommons.org/19884302 </ins>An algorithm for the organization of information<ins class="diffchange diffchange-inline">]</ins>, Soviet Math. Doklady 3, 1259-1262, 1972, This paper on AVL trees can be thought of as the founding paper of the field of storing data in trees. Those not conversant in Russian will want to read the [Lewis and Denenberg] treatment of AVL trees in its place. [Wood] contains a modern treatment of trees.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>[Apple] <del class="diffchange diffchange-inline">Inside Macintosh, Files, by </del>Apple Computer Inc., Addison-Wesley, 1992. Employs balanced trees for filenames, it was an interesting file system architecture for its time in a number of ways, now its problems with internal fragmentation have become more severe as disk drives have grown larger, and the code has not received sufficient further development.</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins class="diffchange diffchange-inline">* </ins>[Apple] Apple Computer Inc<ins class="diffchange diffchange-inline">, [http://books</ins>.<ins class="diffchange diffchange-inline">google.com/books?as_isbn=0201177323 Inside Macintosh, Files]</ins>, Addison-Wesley, 1992. Employs balanced trees for filenames, it was an interesting file system architecture for its time in a number of ways, now its problems with internal fragmentation have become more severe as disk drives have grown larger, and the code has not received sufficient further development.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>[Bach] Maurice J. Bach, <del class="diffchange diffchange-inline">``</del>The Design of the Unix Operating System<del class="diffchange diffchange-inline">''</del>, 1986, Prentice-Hall Software Series, Englewood Cliffs, NJ, superbly written but sadly dated, contains detailed descriptions of the file system routines and interfaces in a manner especially useful for those trying to implement a Unix compatible file system. See [Vahalia].</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins class="diffchange diffchange-inline">* </ins>[Bach] Maurice J. Bach, <ins class="diffchange diffchange-inline">[http://portal.acm.org/citation.cfm?id=8570 </ins>The Design of the Unix Operating System<ins class="diffchange diffchange-inline">]</ins>, 1986, Prentice-Hall Software Series, Englewood Cliffs, NJ, superbly written but sadly dated, contains detailed descriptions of the file system routines and interfaces in a manner especially useful for those trying to implement a Unix compatible file system. See [Vahalia].</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>[BLOB] R. Haskin, Raymond A. Lorie: On Extending the Functions of a Relational Database System. SIGMOD Conference (body of paper not on web) 1982: 207-212, See Drops section for a discussion of how this approach makes the tree less balanced, and the effect that has on performance.</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins class="diffchange diffchange-inline">* </ins>[BLOB] R. Haskin, Raymond A. Lorie: <ins class="diffchange diffchange-inline">[http://portal.acm.org/citation.cfm?id=582353.582390 </ins>On Extending the Functions of a Relational Database System<ins class="diffchange diffchange-inline">]</ins>. SIGMOD Conference (body of paper not on web) 1982: 207-212, See Drops section for a discussion of how this approach makes the tree less balanced, and the effect that has on performance.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>[Chen] Chen, P.M. Patterson, David A., A New Approach to I/O Performance Evaluation<del class="diffchange diffchange-inline">-</del>--Self-Scaling I/O Benchmarks, Predicted I/O Performance, 1993 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, also available on Chen's web page.</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins class="diffchange diffchange-inline">* </ins>[Chen] Chen, P.M. Patterson, David A., <ins class="diffchange diffchange-inline">[http://www.eecs.berkeley.edu/Pubs/TechRpts/1992/6129.html </ins>A New Approach to I/O Performance Evaluation<ins class="diffchange diffchange-inline">] </ins>-- Self-Scaling I/O Benchmarks, Predicted I/O Performance, 1993 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, also available on Chen's web page.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>[C-FFS] Ganger, Gregory R., Kaashoek, M. Frans, <del class="diffchange diffchange-inline">page with link to postscript paper </del>A very well written paper focused on 1-10k file size issues, they use some similar notions (most especially their concept of grouping compared to my packing localities). Note that they focus on the 1-10k file size range, and not the sub-1k range. The 1-10k range is the weakpoint in reiserfs performance.</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins class="diffchange diffchange-inline">* </ins>[C-FFS] Ganger, Gregory R., Kaashoek, M. Frans, <ins class="diffchange diffchange-inline">[http://www.ece.cmu.edu/~ganger/papers/cffs.html Embedded Inodes and Explicit Grouping: Exploiting Disk Bandwidth for Small Files]. </ins>A very well written paper focused on 1-10k file size issues, they use some similar notions (most especially their concept of grouping compared to my packing localities). Note that they focus on the 1-10k file size range, and not the sub-1k range. The 1-10k range is the weakpoint in reiserfs performance.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>[ext2fs] by <del class="diffchange diffchange-inline">Remi </del>Card extensive information, source code is available When you consider how small this file system is (~6000 lines), its effectiveness becomes all the more remarkable.</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins class="diffchange diffchange-inline">* </ins>[ext2fs] by <ins class="diffchange diffchange-inline">Rémy </ins>Card<ins class="diffchange diffchange-inline">, [http://e2fsprogs.sourceforge.net/ext2intro.html </ins>extensive information<ins class="diffchange diffchange-inline">]</ins>, source code is available When you consider how small this file system is (~6000 lines), its effectiveness becomes all the more remarkable.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>[FFS] M.K. McKusick, W.N. Joy, S.J. Leffler, and R.S. Fabry. A fast file system for UNIX. ACM Transactions on Computer Systems, 2(3):181--197, August 1984 describes the implementation of a file system which employs parent directory location knowledge in determining file layout. It uses large blocks for all but the tail of files to improve I/O performance, and uses small blocks called fragments for the tails so as to reduce the cost due to internal fragmentation. Numerous other improvements are also made to what was once the state-of-the-art. FFS remains the architectural foundation for many current block allocation file systems, and was later bundled with the standard Unix releases. Note that unrequested serialization and the use of fragments places it at a performance disadvantage to ext2fs, though whether ext2fs is thereby made less reliable is a matter of dispute that I take no position on (reiserfs uses preserve lists, forgive my egotism in thinking that it is enough work for me to ensure that reiserfs solves the recovery problem, and to perhaps suggest that ext2fs would benefit from the use of preserve lists when shrinking directories)</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins class="diffchange diffchange-inline">* </ins>[FFS] M.K. McKusick, W.N. Joy, S.J. Leffler, and R.S. Fabry. A fast file system for UNIX. ACM Transactions on Computer Systems, 2(3):181--197, August 1984 describes the implementation of a file system which employs parent directory location knowledge in determining file layout. It uses large blocks for all but the tail of files to improve I/O performance, and uses small blocks called fragments for the tails so as to reduce the cost due to internal fragmentation. Numerous other improvements are also made to what was once the state-of-the-art. FFS remains the architectural foundation for many current block allocation file systems, and was later bundled with the standard Unix releases. Note that unrequested serialization and the use of fragments places it at a performance disadvantage to ext2fs, though whether ext2fs is thereby made less reliable is a matter of dispute that I take no position on (reiserfs uses preserve lists, forgive my egotism in thinking that it is enough work for me to ensure that reiserfs solves the recovery problem, and to perhaps suggest that ext2fs would benefit from the use of preserve lists when shrinking directories)</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>[Ganger] Gregory R. Ganger, Yale N. Patt, ``Metadata Update Performance in File Systems'' abstract only</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins class="diffchange diffchange-inline">* </ins>[Ganger] Gregory R. Ganger, Yale N. Patt, ``Metadata Update Performance in File Systems'' abstract only</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>[Gifford], postscript only Describes a file system enriched to have more than hierarchical semantics, he shares many goals with this author, forgive me for thinking his work worthwhile. If I had to suggest one improvement in a sentence, I would say his semantic algebra needs closure.</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins class="diffchange diffchange-inline">* </ins>[Gifford], postscript only Describes a file system enriched to have more than hierarchical semantics, he shares many goals with this author, forgive me for thinking his work worthwhile. If I had to suggest one improvement in a sentence, I would say his semantic algebra needs closure.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>[Hitz, Dave]http://www.netapp.com/technology/level3/3002.html  A rather well designed file system optimized for NFS and RAID in combination.  Note that RAID increases the merits of write-optimization in block layout algorithms.</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins class="diffchange diffchange-inline">* </ins>[Hitz, Dave]http://www.netapp.com/technology/level3/3002.html  A rather well designed file system optimized for NFS and RAID in combination.  Note that RAID increases the merits of write-optimization in block layout algorithms.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>[Holton and Das] , Holton, Mike., Das, Raj., ``The XFS space manager and namespace manager use sophisticated B-Tree indexing technology to represent file location information contained inside directory files and to represent the structure of the files themselves (location of information in a file).'' Note that it is still a block (extent) allocation based file system, no attempt is made to store the actual file contents in the tree. It is targeted at the needs of the other end of the file size usage spectrum from reiserfs, and is an excellent design for that purpose (and I would concede that reiserfs 1.0 is not suitable for their real-time large I/O market.) SGI has also traditionally been a leader in resisting the use of unrequested serialization of I/O. Unfortunately, the paper is a bit vague on details, and source code is not freely available.</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins class="diffchange diffchange-inline">* </ins>[Holton and Das] , Holton, Mike., Das, Raj., ``The XFS space manager and namespace manager use sophisticated B-Tree indexing technology to represent file location information contained inside directory files and to represent the structure of the files themselves (location of information in a file).'' Note that it is still a block (extent) allocation based file system, no attempt is made to store the actual file contents in the tree. It is targeted at the needs of the other end of the file size usage spectrum from reiserfs, and is an excellent design for that purpose (and I would concede that reiserfs 1.0 is not suitable for their real-time large I/O market.) SGI has also traditionally been a leader in resisting the use of unrequested serialization of I/O. Unfortunately, the paper is a bit vague on details, and source code is not freely available.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>[Howard] ``Scale and Performance in a Distributed File System'', Howard, J.H., Kazar, M.L., Menees, S.G., Nichols, D.A., Satayanarayanan, N., Sidebotham, R.N., West, M.J., ACM Transactions on Computer Systems, 6(1), February 1988 A classic benchmark, it was too CPU bound for both ext2fs and reiserfs.</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins class="diffchange diffchange-inline">* </ins>[Howard] ``Scale and Performance in a Distributed File System'', Howard, J.H., Kazar, M.L., Menees, S.G., Nichols, D.A., Satayanarayanan, N., Sidebotham, R.N., West, M.J., ACM Transactions on Computer Systems, 6(1), February 1988 A classic benchmark, it was too CPU bound for both ext2fs and reiserfs.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>[Knuth] Knuth, D.E., The Art of Computer Programming, Vol. 3 (Sorting and Searching), Addison-Wesley, Reading, MA, 1973, the earliest reference discussing trees storing records of varying length.</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins class="diffchange diffchange-inline">* </ins>[Knuth] Knuth, D.E., The Art of Computer Programming, Vol. 3 (Sorting and Searching), Addison-Wesley, Reading, MA, 1973, the earliest reference discussing trees storing records of varying length.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>[LADDIS] Wittle, Mark., and Bruce, Keith., ``LADDIS: The Next Generation in NFS File Server Benchmarking'', Proceedings of the Summer 1993 USENIX Conference.'', July 1993, pp. 111-128</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins class="diffchange diffchange-inline">* </ins>[LADDIS] Wittle, Mark., and Bruce, Keith., ``LADDIS: The Next Generation in NFS File Server Benchmarking'', Proceedings of the Summer 1993 USENIX Conference.'', July 1993, pp. 111-128</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>[Lewis and Denenberg] Lewis, Harry R., Denenberg, Larry ``Data Structures & Their Algorithms'', HarperCollins Publishers, NY, NY, 1991, an algorithms textbook suitable for readers wishing to learn about balanced trees and their AVL predecessors.</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins class="diffchange diffchange-inline">* </ins>[Lewis and Denenberg] Lewis, Harry R., Denenberg, Larry ``Data Structures & Their Algorithms'', HarperCollins Publishers, NY, NY, 1991, an algorithms textbook suitable for readers wishing to learn about balanced trees and their AVL predecessors.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>[McCreight] McCreight, E.M., Pagination of B*-trees with variable length records, Commun. ACM 20 (9), 670-674, 1977, describes algorithms for trees with variable length records.</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins class="diffchange diffchange-inline">* </ins>[McCreight] McCreight, E.M., Pagination of B*-trees with variable length records, Commun. ACM 20 (9), 670-674, 1977, describes algorithms for trees with variable length records.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>[McVoy and Kleiman], the implementation of write-clustering for Sun's UFS.</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins class="diffchange diffchange-inline">* </ins>[McVoy and Kleiman], the implementation of write-clustering for Sun's UFS.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>[OLE] ``Inside OLE'' by Kraig Brockshmidt, discusses Structured Storage, HREF="http://www.microsoft.com/mspress/books/abs/5-843-2b.htm" abstract only</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins class="diffchange diffchange-inline">* </ins>[OLE] ``Inside OLE'' by Kraig Brockshmidt, discusses Structured Storage, HREF="http://www.microsoft.com/mspress/books/abs/5-843-2b.htm" abstract only</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>[Ousterhout] J.K. Ousterhout, H. Da Costa, D. Harrison, J.A. Kunze, M.D. Kupfer, and J.G. Thompson. A trace-driven analysis of the UNIX 4.2BSD file system. In Proceedings of the 10th Symposium on Operating Systems Principles, pages 15--24, Orcas Island, WA, December 1985.</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins class="diffchange diffchange-inline">* </ins>[Ousterhout] J.K. Ousterhout, H. Da Costa, D. Harrison, J.A. Kunze, M.D. Kupfer, and J.G. Thompson. A trace-driven analysis of the UNIX 4.2BSD file system. In Proceedings of the 10th Symposium on Operating Systems Principles, pages 15--24, Orcas Island, WA, December 1985.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>[NTFS] ``Inside the Windows NT File System'' the book is written by Helen Custer, NTFS is architected by Tom Miller with contributions by Gary Kimura, Brian Andrew, and David Goebel, Microsoft Press, 1994, an easy to read little book, they fundamentally disagree with me on adding serialization of I/O not requested by the application programmer, and I note that the performance penalty they pay for their decision is high, especially compared with ext2fs. Their FS design is perhaps optimal for floppies and other hardware eject media beyond OS control. A less serialized higher performance log structured architecture is described in [Rosenblum and Ousterhout]. That said, Microsoft is to be commended for recognizing the importance of attempting to optimize for small files, and leading the OS designer effort to integrate small objects into the file name space. This book is notable for not referencing the work of persons not working for Microsoft, or providing any form of proper attribution to previous authors such as [Rosenblum and Ousterhout].</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins class="diffchange diffchange-inline">* </ins>[NTFS] ``Inside the Windows NT File System'' the book is written by Helen Custer, NTFS is architected by Tom Miller with contributions by Gary Kimura, Brian Andrew, and David Goebel, Microsoft Press, 1994, an easy to read little book, they fundamentally disagree with me on adding serialization of I/O not requested by the application programmer, and I note that the performance penalty they pay for their decision is high, especially compared with ext2fs. Their FS design is perhaps optimal for floppies and other hardware eject media beyond OS control. A less serialized higher performance log structured architecture is described in [Rosenblum and Ousterhout]. That said, Microsoft is to be commended for recognizing the importance of attempting to optimize for small files, and leading the OS designer effort to integrate small objects into the file name space. This book is notable for not referencing the work of persons not working for Microsoft, or providing any form of proper attribution to previous authors such as [Rosenblum and Ousterhout].</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>[Peacock] K. Peacock, ``The CounterPoint Fast File System'', Proceedings of the Usenix Conference Winter 1988</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins class="diffchange diffchange-inline">* </ins>[Peacock] K. Peacock, ``The CounterPoint Fast File System'', Proceedings of the Usenix Conference Winter 1988</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>[Pike]  Rob Pike and Peter Weinberger, The Hideous Name, USENIX Summer 1985 Conference Proceedings, pp. 563, Portland Oregon, 1985.  Short, informal, and drives home why inconsistent naming schemes in an OS are detrimental. http://achille.cs.bell-labs.com/cm/cs/doc/85/1-05.ps.gz His discussion of naming in plan 9: http://plan9.bell-labs.com/plan9/doc/names.html</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins class="diffchange diffchange-inline">* </ins>[Pike]  Rob Pike and Peter Weinberger, The Hideous Name, USENIX Summer 1985 Conference Proceedings, pp. 563, Portland Oregon, 1985.  Short, informal, and drives home why inconsistent naming schemes in an OS are detrimental. http://achille.cs.bell-labs.com/cm/cs/doc/85/1-05.ps.gz His discussion of naming in plan 9: http://plan9.bell-labs.com/plan9/doc/names.html</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>[Rosenblum and Ousterhout] ``The Design and Implementation of a Log-Structured File System'', Mendel Rosenblum and John K. Ousterhout, February 1992 ACM Transactions on Computer Systems, this paper was quite influential in a number of ways on many modern file systems, and the notion of using a cleaner may be applied to a future release of reiserfs. There is an interesting on-going debate over the relative merits of FFS vs. LFS architectures, and the interested reader may peruse http://www.scriptics.com/people/john.ousterhout/seltzer93.html and the arguments by Margo Seltzer it links to.</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins class="diffchange diffchange-inline">* </ins>[Rosenblum and Ousterhout] ``The Design and Implementation of a Log-Structured File System'', Mendel Rosenblum and John K. Ousterhout, February 1992 ACM Transactions on Computer Systems, this paper was quite influential in a number of ways on many modern file systems, and the notion of using a cleaner may be applied to a future release of reiserfs. There is an interesting on-going debate over the relative merits of FFS vs. LFS architectures, and the interested reader may peruse http://www.scriptics.com/people/john.ousterhout/seltzer93.html and the arguments by Margo Seltzer it links to.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>[Snyder] , ``tmpfs: A Virtual Memory File System'' discusses a file system built to use swap space and intended for temporary files, due to a complete lack of disk synchronization it offers extremely high performance.</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins class="diffchange diffchange-inline">* </ins>[Snyder] , ``tmpfs: A Virtual Memory File System'' discusses a file system built to use swap space and intended for temporary files, due to a complete lack of disk synchronization it offers extremely high performance.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>[Vahalia] Uresh Vahalia, ``Unix Kernal Internals''</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins class="diffchange diffchange-inline">* </ins>[Vahalia] Uresh Vahalia, ``Unix Kernal Internals''</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>[[category:ReiserFS]]</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>[[category:ReiserFS]]</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>[[category:Formatting-fixes-needed]]</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>[[category:Formatting-fixes-needed]]</div></td></tr>
</table>Chris goehttps://reiser4.wiki.kernel.org/index.php?title=X0reiserfs&diff=1717&oldid=prevChris goe: more refs2010-04-25T03:12:16Z<p>more refs</p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr valign='top'>
<td colspan='2' style="background-color: white; color:black;">← Older revision</td>
<td colspan='2' style="background-color: white; color:black;">Revision as of 03:12, 25 April 2010</td>
</tr><tr><td colspan="2" class="diff-lineno">Line 31:</td>
<td colspan="2" class="diff-lineno">Line 31:</td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>An operating system is composed of components that access other components through interfaces. Operating systems are complex enough that, like national economies, the architect cannot centrally plan the interactions of the components that it is composed of. The architect can provide a structural framework that has a marked impact on the efficiency and utility of those interactions. Economists have developed principles that govern large economic systems. Are there system principles that we might use to start a discussion of the ways increasing component interactivity via naming system design impacts the total utility of an operating system? I propose these:</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>An operating system is composed of components that access other components through interfaces. Operating systems are complex enough that, like national economies, the architect cannot centrally plan the interactions of the components that it is composed of. The architect can provide a structural framework that has a marked impact on the efficiency and utility of those interactions. Economists have developed principles that govern large economic systems. Are there system principles that we might use to start a discussion of the ways increasing component interactivity via naming system design impacts the total utility of an operating system? I propose these:</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div><del class="diffchange diffchange-inline">    </del>* If one increases the number of other components that a particular component can interact with, one increases its expressive power and thereby its utility.</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>* If one increases the number of other components that a particular component can interact with, one increases its expressive power and thereby its utility.</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div><del class="diffchange diffchange-inline">    </del>* One can increase the number of other components that a particular component can interact with either by increasing the number of interfaces it has, or by increasing the number of components that are accessible by its current interfaces.</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>* One can increase the number of other components that a particular component can interact with either by increasing the number of interfaces it has, or by increasing the number of components that are accessible by its current interfaces.</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div><del class="diffchange diffchange-inline">    </del>* The cost of component interfaces dominates software design cost., like the cost of wires dominates circuit design cost.</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>* The cost of component interfaces dominates software design cost., like the cost of wires dominates circuit design cost.</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div><del class="diffchange diffchange-inline">    </del>* Total system utility tends to be proportional not to the number of components, but to the number of possible component interactions.</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>* Total system utility tends to be proportional not to the number of components, but to the number of possible component interactions.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>It is not simply the number of components that one has that determines an OS's expressive power, it is the number of opportunities to use them that determines it. The number of these opportunities are proportional to the number of possible combinations of them, and the number of possible combinations of them are determined by their connectedness. Component connectedness in OS design is determined by name space design, to much the same extent that buses determine it in circuit design.</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>It is not simply the number of components that one has that determines an OS's expressive power, it is the number of opportunities to use them that determines it. The number of these opportunities are proportional to the number of possible combinations of them, and the number of possible combinations of them are determined by their connectedness. Component connectedness in OS design is determined by name space design, to much the same extent that buses determine it in circuit design.</div></td></tr>
<tr><td colspan="2" class="diff-lineno">Line 40:</td>
<td colspan="2" class="diff-lineno">Line 40:</td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>Allow me to illustrate the impact of these principles with the use of an imaginary example.  Suppose two imaginary OS vendors with equally talented programmers hire two different OS architects.  Suppose one of the architects centers the OS design around a single name space design that allows all of the components to access all other components via a single interface (assume this is possible, it is a theoretical example).  Suppose the other allows the ten different design groups in the company that are developing components to create their own ten name spaces.  Suppose that the unified name space OS architect has half of the resources of the fragmented name space OS architect and creates half as many components.  While the number of components is half as large, the number of connections is 1/22/((1/102)*10) times larger.  If you accept my hypothesis that utility is more proportional to connections than components, then the unified operating system with half the development cost will still offer more expressive utility.  That is a powerful motivation.</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>Allow me to illustrate the impact of these principles with the use of an imaginary example.  Suppose two imaginary OS vendors with equally talented programmers hire two different OS architects.  Suppose one of the architects centers the OS design around a single name space design that allows all of the components to access all other components via a single interface (assume this is possible, it is a theoretical example).  Suppose the other allows the ten different design groups in the company that are developing components to create their own ten name spaces.  Suppose that the unified name space OS architect has half of the resources of the fragmented name space OS architect and creates half as many components.  While the number of components is half as large, the number of connections is 1/22/((1/102)*10) times larger.  If you accept my hypothesis that utility is more proportional to connections than components, then the unified operating system with half the development cost will still offer more expressive utility.  That is a powerful motivation.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>To return briefly to the long ago researched principles governing another member of the class of large systems, the economies of nations, it is perhaps interesting to note that Adam Smith in <del class="diffchange diffchange-inline">``</del>The Wealth of Nations<del class="diffchange diffchange-inline">'' </del>engaged in substantial study of the link between the extent of interconnectedness and the development of civilization, where the extent of interconnectedness was determined by waterways, etc.  The link he found  for economic systems was no less crucial than what is being suggested here for the effect of component interconnectedness on the total utility of software systems.  I suggest that I am merely generalizing a long established principle from another field of science, namely  that total utility in large systems with components that interact  to generate utility is determined by the extent of their interconnection.</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>To return briefly to the long ago researched principles governing another member of the class of large systems, the economies of nations, it is perhaps interesting to note that Adam Smith in <ins class="diffchange diffchange-inline">[http://en.wikisource.org/wiki/The_Wealth_of_Nations "</ins>The Wealth of Nations<ins class="diffchange diffchange-inline">"] </ins>engaged in substantial study of the link between the extent of interconnectedness and the development of civilization, where the extent of interconnectedness was determined by waterways, etc.  The link he found  for economic systems was no less crucial than what is being suggested here for the effect of component interconnectedness on the total utility of software systems.  I suggest that I am merely generalizing a long established principle from another field of science, namely  that total utility in large systems with components that interact  to generate utility is determined by the extent of their interconnection.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>There are many exceptions to these principles: not all chips on a motherboard sit on the bus, and analogous considerations apply to both OS design and the economies of nations.  I hope the reader will accept that space considerations make it appropriate to gloss over these, and will consider the central point that under some circumstances unifying name spaces in a design can dramatically improve the utility of an OS. That can be an enormous motivation, and it has moved a number of OS researchers in their work <del class="diffchange diffchange-inline">[</del>e.g. <del class="diffchange diffchange-inline">Pike ``</del>The Use of Name Spaces in Plan9<del class="diffchange diffchange-inline">'' </del>and <del class="diffchange diffchange-inline">``The Hideous Name'' </del>http://<del class="diffchange diffchange-inline">magnum</del>.<del class="diffchange diffchange-inline">cooper</del>.edu<del class="diffchange diffchange-inline">:9000</del>/ ~<del class="diffchange diffchange-inline">rp</del>/<del class="diffchange diffchange-inline">html/rob</del>.<del class="diffchange diffchange-inline">html</del>.</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>There are many exceptions to these principles: not all chips on a motherboard sit on the bus, and analogous considerations apply to both OS design and the economies of nations.  I hope the reader will accept that space considerations make it appropriate to gloss over these, and will consider the central point that under some circumstances unifying name spaces in a design can dramatically improve the utility of an OS. That can be an enormous motivation, and it has moved a number of OS researchers in their work <ins class="diffchange diffchange-inline">(</ins>e.g. <ins class="diffchange diffchange-inline">[http://plan9.bell-labs.com/sys/doc/names.html "</ins>The Use of Name Spaces in Plan9<ins class="diffchange diffchange-inline">", Rob Pike] </ins>and <ins class="diffchange diffchange-inline">[</ins>http://<ins class="diffchange diffchange-inline">pdos</ins>.<ins class="diffchange diffchange-inline">csail.mit</ins>.edu/~<ins class="diffchange diffchange-inline">rsc</ins>/<ins class="diffchange diffchange-inline">pike85hideous</ins>.<ins class="diffchange diffchange-inline">pdf "The Hideous Name", Rob Pike and P.J. Weinberger])</ins>.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>Unfortunately, it is not a small technical effort to combine name spaces.  To combine 10 name spaces requires, if not the effort to create 10 name spaces, perhaps an effort equivalent to creating 5 of the name spaces. Usually each of the name spaces has particular performance and semantic power requirements that require enhancing the unified name space, and it usually requires technical innovation to combine the advantages of each of the separated name spaces into a unified name space.  I would characterize none of the research groups currently approaching this unification problem as having funding equivalent to what went into creating 5 of the name spaces they would like to unify, and we are certainly no exception.  For this reason I have picked one particular aspect of this larger problem for our focus: allowing small objects to effectively share the same file system interface that large objects use currently.</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>Unfortunately, it is not a small technical effort to combine name spaces.  To combine 10 name spaces requires, if not the effort to create 10 name spaces, perhaps an effort equivalent to creating 5 of the name spaces. Usually each of the name spaces has particular performance and semantic power requirements that require enhancing the unified name space, and it usually requires technical innovation to combine the advantages of each of the separated name spaces into a unified name space.  I would characterize none of the research groups currently approaching this unification problem as having funding equivalent to what went into creating 5 of the name spaces they would like to unify, and we are certainly no exception.  For this reason I have picked one particular aspect of this larger problem for our focus: allowing small objects to effectively share the same file system interface that large objects use currently.</div></td></tr>
</table>Chris goehttps://reiser4.wiki.kernel.org/index.php?title=X0reiserfs&diff=1716&oldid=prevChris goe: reference added2010-04-25T03:04:28Z<p>reference added</p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr valign='top'>
<td colspan='2' style="background-color: white; color:black;">← Older revision</td>
<td colspan='2' style="background-color: white; color:black;">Revision as of 03:04, 25 April 2010</td>
</tr><tr><td colspan="2" class="diff-lineno">Line 21:</td>
<td colspan="2" class="diff-lineno">Line 21:</td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>= Introduction =</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>= Introduction =</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>The author is one of many OS researchers who are attempting to unify the name spaces in the operating system in varying ways <del class="diffchange diffchange-inline">[</del>e.g. Pike <del class="diffchange diffchange-inline">``</del>The Use of Name Spaces in Plan9<del class="diffchange diffchange-inline">'' </del>]. None of us are well funded compared with the size of the task, and I am far from an exception to this rule. The natural consequence is that we each have attacked one small aspect of the task. My contribution is in incorporating small objects into the file system name space effectively.</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>The author is one of many OS researchers who are attempting to unify the name spaces in the operating system in varying ways <ins class="diffchange diffchange-inline">(</ins>e.g. <ins class="diffchange diffchange-inline">[http://plan9.bell-labs.com/sys/doc/names.html </ins>Pike<ins class="diffchange diffchange-inline">, </ins>The Use of Name Spaces in Plan9]<ins class="diffchange diffchange-inline">)</ins>. None of us are well funded compared with the size of the task, and I am far from an exception to this rule. The natural consequence is that we each have attacked one small aspect of the task. My contribution is in incorporating small objects into the file system name space effectively.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>This implementation offers value to the average Linux user, in that it offers generally good performance compared to the current Linux file system known as ext2fs.It also saves space to an extent that is important for some applications, and convenient for most. It does extremely well for large directories, and has a variety of minor advantages.</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>This implementation offers value to the average Linux user, in that it offers generally good performance compared to the current Linux file system known as ext2fs.It also saves space to an extent that is important for some applications, and convenient for most. It does extremely well for large directories, and has a variety of minor advantages.</div></td></tr>
</table>Chris goe