Log-structured file system

<h2 id="rationale">Rationale</h2>
<p>Conventional file systems lay out files with great care for spatial locality and make in-place changes to their data structures in order to perform well on optical and magnetic disks, which tend to seek relatively slowly.
</p><p>The design of log-structured file systems is based on the hypothesis that this will no longer be effective because ever-increasing memory sizes on modern computers would lead to I/O becoming write-heavy since reads would be almost always satisfied from memory cache. A log-structured file system thus treats its storage as a <a href="/facts/Circular_buffer/Xu7vpzmP">circular log</a> and writes sequentially to the head of the log.
</p><p>This has several important side effects:
</p>
<ul><li>Write throughput on optical and magnetic disks is improved because they can be batched into large sequential runs and costly seeks are kept to a minimum.
<ul><li>The structure is naturally suited to media with <a href="/facts/Append-only/FPYe5zkw">append-only</a> zones or pages such as <a href="/facts/Flash_storage/Cn8JsStx">flash storages</a> and <a href="/facts/Shingled_magnetic_recording/wTIUm0Xk">shingled magnetic recording</a> HDDs<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a><a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a></li></ul></li>
<li>Writes create multiple, chronologically-advancing versions of both file data and meta-data. Some implementations make these old file versions nameable and accessible, a feature sometimes called time-travel or <a href="/facts/Snapshot_(computer_storage)/LKm3NX2A">snapshotting</a>. This is very similar to a <a href="/facts/Versioning_file_system/g1gDkdcN">versioning file system</a>.</li>
<li>Recovery from crashes is simpler. Upon its next mount, the file system does not need to walk all its data structures to fix any inconsistencies, but can reconstruct its state from the last consistent point in the log.</li></ul>
<p>Log-structured file systems, however, must reclaim free space from the tail of the log to prevent the file system from becoming full when the head of the log wraps around to meet it. The tail can release space and move forward by skipping over data for which newer versions exist further ahead in the log. If there are no newer versions, then the data is moved and appended to the head.
</p><p>To reduce the overhead incurred by this <a href="/facts/Garbage_collection_(computer_science)/j2vlIu7g">garbage collection</a>, most implementations avoid purely circular logs and divide up their storage into segments. The head of the log simply advances into non-adjacent segments which are already free. If space is needed, the least-full segments are reclaimed first. This decreases the I/O load (and decreases the <a href="/facts/Write_amplification/copgTWeh">write amplification</a>) of the garbage collector, but becomes increasingly ineffective as the file system fills up and nears capacity.
</p>
<h2 id="disadvantages">Disadvantages</h2>
<p>The <a href="/facts/Design_rationale/bwUAQBSU">design rationale</a> for log-structured file systems assumes that most reads will be optimized away by ever-enlarging memory caches. This assumption does not always hold:
</p>
<ul><li>On magnetic media—where seeks are relatively expensive—the log structure may actually make reads much slower, since it <a href="/facts/Fragmentation_(computer)/SflHry2p">fragments</a> files that conventional file systems normally keep contiguous with in-place writes.</li>
<li>On flash memory—where seek times are usually negligible—the log structure may not confer a worthwhile performance gain because write fragmentation has much less of an impact on write throughput. Another issue is stacking one log on top of another log, which is not a very good idea as it forces multiple erases with unaligned access.<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a> However, many flash based devices cannot rewrite part of a block, and they must first perform a (slow) erase cycle of each block before being able to re-write. By putting all the writes in one block, this can help performance as opposed to writes scattered into various blocks, and each one must be copied into a buffer, erased, and written back, which is a clear advantage for so-called "raw" flash memory where flash translation layer is bypassed.</li></ul>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Comparison_of_file_systems/M7ynsI2z">Comparison of file systems</a></li>
<li><a href="/facts/List_of_log-structured_file_systems/XX55LbQS">List of log-structured file systems</a></li></ul>

<h2 id="further-reading">Further reading</h2>
<ul><li><a href="http://pages.cs.wisc.edu/~remzi/OSTEP/file-lfs.pdf">Log-structured File Systems (2014), Arpaci-Dusseau, Remzi H.; Arpaci-Dusseau, Andrea C.; Arpaci-Dusseau Books</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>John K. Ousterhout, Mendel Rosenblum. (1991), The Design and Implementation of a Log-Structured File System (PDF), University of California, Berkeley <a href="https://people.eecs.berkeley.edu/~brewer/cs262/LFS.pdf" target="_blank">https://people.eecs.berkeley.edu/~brewer/cs262/LFS.pdf</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Magic Pocket Hardware Engineering Teams. "Extending Magic Pocket Innovation with the first petabyte scale SMR drive deployment". dropbox.tech. <a href="https://dropbox.tech/infrastructure/extending-magic-pocket-innovation-with-the-first-petabyte-scale-smr-drive-deployment" target="_blank">https://dropbox.tech/infrastructure/extending-magic-pocket-innovation-with-the-first-petabyte-scale-smr-drive-deployment</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>Reid, Colin; Bernstein, Phil (1 January 2010). "Implementing an Append-Only Interface for Semiconductor Storage" (PDF). IEEE Data Eng. Bull. 33: 14-20. <a href="http://sites.computer.org/debull/A10dec/hyder.pdf" target="_blank">http://sites.computer.org/debull/A10dec/hyder.pdf</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
<li id="fn:4"><p>Swaminathan Sundararaman, Jingpei Yang (2014), Don't stack your Log on my Log (PDF), SanDisk Corporation <a href="https://www.usenix.org/system/files/conference/inflow14/inflow14-yang.pdf" target="_blank">https://www.usenix.org/system/files/conference/inflow14/inflow14-yang.pdf</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li>
</ol>

Log-structured file system open-in-new

Log-structured file system