東華大學圖書館 |

Language: English

Help

回圖書館首頁

手機版館藏查詢

Back

Switch To: Labeled | MARC Mode | ISBD

Write-Optimized Data Structures for ...

Yuan, Jun.

Linked to FindBook

Google Book

Amazon

博客來

Write-Optimized Data Structures for File Systems.

Record Type:	Electronic resources : Monograph/item
Title/Author:	Write-Optimized Data Structures for File Systems./
Author:	Yuan, Jun.
Published:	Ann Arbor : ProQuest Dissertations & Theses, : 2016,
Description:	85 p.
Notes:	Source: Dissertations Abstracts International, Volume: 78-06, Section: B.
Contained By:	Dissertations Abstracts International78-06B.
Subject:	Computer science. -
Online resource:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=10193129
ISBN:	9781369352689

Write-Optimized Data Structures for File Systems.
Yuan, Jun.

Write-Optimized Data Structures for File Systems. - Ann Arbor : ProQuest Dissertations & Theses, 2016 - 85 p.

Source: Dissertations Abstracts International, Volume: 78-06, Section: B.

Thesis (Ph.D.)--State University of New York at Stony Brook, 2016.

This item is not available from ProQuest Dissertations & Theses.

Write-Optimized Data Structures (WODS) are promising building blocks for modern file-system design. Recent file systems based on write-optimized key-value stores can perform small random writes, such as file and directory creation, metadata updates, and small random writes to files, orders of magnitude faster than conventional file systems. Key-value-store-based file systems that use full-paths as keys can also perform very fast recursive directory traversals, because sorting by full-paths retains good data locality. Early WODS-based file-system prototypes either did not achieve all these performance benefits or had performance problems on other operations, such as large sequential writes, deletes, and renames. For example, BetrFS, a file system based on the Bϵ-tree, out-performs traditional file systems by orders of magnitude on microdata operations. However, its sequential IO, delete, and rename have performance issues. Because BetrFS stores file blocks in a Bϵ-tree, file rename and delete are mapped to a sequence of per-block operations instead of one single B ϵ-tree operation. In addition, BetrFS sequential writes run at half disk bandwidth because it writes all data twice: once in a redo log and once in the Bϵ-tree. This dissertation explores techniques, at both the data structure and the schema level, that improve the performance of sequential writes, deletes and renames without sacrificing the performance of other operations. These dramatic improvements can be retained while matching conventional file systems on all other operations. In BetrFS 0.2, we implemented a range-delete primitive, which BetrFS can use to perform file deletes with a single Bϵ -tree operation, improving the latency from linear to constant. Additionally, range-delete improves overall system throughput by enabling the Bϵ -tree to avoid reading dead data during garbage collection. We implemented a late-binding journal which offers full-data journaling at the cost of meta-data-only journaling. The late-binding journal enables BetrFS to perform large sequential writes at nearly disk bandwidth by storing large writes directly in the Bϵ-tree and placing only a reference in the redo log. Last but not least, we implemented two techniques to address the performance issue of renaming: the zone-tree schema, based on an analytical framework for reasoning about trade-offs between locality for directory traversals and indirection for fast file and directory renames, and range-rename, a purely internal Bϵ-tree operation to support complex sub-tree updates that makes no trade-off between locality and indirection.

ISBN: 9781369352689Subjects--Topical Terms:

523869
Computer science.

Write-Optimized Data Structures for File Systems.
LDR:03835nmm a2200337 4500 001 2206222
005 20190829083205.5
008 201008s2016 ||||||||||||||||| ||eng d
020 $a 9781369352689
035 $a (MiAaPQ)AAI10193129
035 $a (MiAaPQ)grad.sunysb:13037
035 $a AAI10193129
040 $a MiAaPQ $c MiAaPQ
100 1 $a Yuan, Jun. $3 1044729
245 1 0 $a Write-Optimized Data Structures for File Systems.
260 1 $a Ann Arbor : $b ProQuest Dissertations & Theses, $c 2016
300 $a 85 p.
500 $a Source: Dissertations Abstracts International, Volume: 78-06, Section: B.
500 $a Publisher info.: Dissertation/Thesis.
500 $a Johnson, Robert.
502 $a Thesis (Ph.D.)--State University of New York at Stony Brook, 2016.
506 $a This item is not available from ProQuest Dissertations & Theses.
506 $a This item must not be added to any third party search indexes.
506 $a This item must not be sold to any third party vendors.
520 $a Write-Optimized Data Structures (WODS) are promising building blocks for modern file-system design. Recent file systems based on write-optimized key-value stores can perform small random writes, such as file and directory creation, metadata updates, and small random writes to files, orders of magnitude faster than conventional file systems. Key-value-store-based file systems that use full-paths as keys can also perform very fast recursive directory traversals, because sorting by full-paths retains good data locality. Early WODS-based file-system prototypes either did not achieve all these performance benefits or had performance problems on other operations, such as large sequential writes, deletes, and renames. For example, BetrFS, a file system based on the Bϵ-tree, out-performs traditional file systems by orders of magnitude on microdata operations. However, its sequential IO, delete, and rename have performance issues. Because BetrFS stores file blocks in a Bϵ-tree, file rename and delete are mapped to a sequence of per-block operations instead of one single B ϵ-tree operation. In addition, BetrFS sequential writes run at half disk bandwidth because it writes all data twice: once in a redo log and once in the Bϵ-tree. This dissertation explores techniques, at both the data structure and the schema level, that improve the performance of sequential writes, deletes and renames without sacrificing the performance of other operations. These dramatic improvements can be retained while matching conventional file systems on all other operations. In BetrFS 0.2, we implemented a range-delete primitive, which BetrFS can use to perform file deletes with a single Bϵ -tree operation, improving the latency from linear to constant. Additionally, range-delete improves overall system throughput by enabling the Bϵ -tree to avoid reading dead data during garbage collection. We implemented a late-binding journal which offers full-data journaling at the cost of meta-data-only journaling. The late-binding journal enables BetrFS to perform large sequential writes at nearly disk bandwidth by storing large writes directly in the Bϵ-tree and placing only a reference in the redo log. Last but not least, we implemented two techniques to address the performance issue of renaming: the zone-tree schema, based on an analytical framework for reasoning about trade-offs between locality for directory traversals and indirection for fast file and directory renames, and range-rename, a purely internal Bϵ-tree operation to support complex sub-tree updates that makes no trade-off between locality and indirection.
590 $a School code: 0771.
650 4 $a Computer science. $3 523869
690 $a 0984
710 2 $a State University of New York at Stony Brook. $b Computer Science. $3 1674709
773 0 $t Dissertations Abstracts International $g 78-06B.
790 $a 0771
791 $a Ph.D.
792 $a 2016
793 $a English
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=10193129