[JF:20094] [Release] Linux-3.3: logfs.txt

2012年 6月 28日 (木) 23:55:28 JST

かねこです。一旦これはリリースします。

------>8------------>8------------>8------------>8------------>8
=========================================================
これは、
Linux-3.3/Documentation/filesystems/logfs.txt の和訳です。
翻訳団体： JF プロジェクト < http://www.linux.or.jp/JF/ >
更新日 ： 2012/5/31
翻訳者 ： Seiji Kaneko < skaneko at mbn dot or dot jp >
=========================================================

#The LogFS Flash Filesystem
#==========================
LogFS フラッシュファイルシステム
================================

#Specification
#=============
仕様
====

#Superblocks
#-----------
スーパーブロック
----------------

#Two superblocks exist at the beginning and end of the filesystem.
#Each superblock is 256 Bytes large, with another 3840 Bytes reserved
#for future purposes, making a total of 4096 Bytes.
ファイルシステムの最初と最後に、各一つのスーパーブロック (合計 2 個)があり
ます。いずれも 256 バイトの長さで、将来の拡張のため 3840 バイトがリザーブさ
れているため、合わせて 4096 バイトになります。

#Superblock locations may differ for MTD and block devices.  On MTD the
#first non-bad block contains a superblock in the first 4096 Bytes and
#the last non-bad block contains a superblock in the last 4096 Bytes.
#On block devices, the first 4096 Bytes of the device contain the first
#superblock and the last aligned 4096 Byte-block contains the second
#superblock.
スーパーブロックの位置は、MTD とブロックデバイスで異なる可能性があります。
MTD の場合、最初の不良の無いブロックに最初の 4096 バイトのスーパーブロック
が、そして最後の不良の無いスーパーブロックに最後の 4096 バイト分が格納され
ます。ブロックデバイスでは、デバイスの最初の 4096 バイトに最初のスーパーブ
ロックが、そして最後のアラインされた 4096 バイトのブロックに二番目のスーパ
ーブロックが格納されます。

#For the most part, the superblocks can be considered read-only.  They
#are written only to correct errors detected within the superblocks,
#move the journal and change the filesystem parameters through tunefs.
#As a result, the superblock does not contain any fields that require
#constant updates, like the amount of free space, etc.
殆どの場合、スーパーブロックは読み出し専用として扱われます。スーパーブロッ
クは、ブロック内でエラーが発見された場合の訂正時、ジャーナルの移動、そして
tunefs によるファイルシステムパラメータの変更時でのみ書き込まれます。この
結果、スーパーブロックには空き容量などの定常的に更新が行われるフィールドは
含まれません。

#Segments
#--------
セグメント
----------

#The space in the device is split up into equal-sized segments.
#Segments are the primary write unit of LogFS.  Within each segments,
#writes happen from front (low addresses) to back (high addresses.  If
#only a partial segment has been written, the segment number, the
#current position within and optionally a write buffer are stored in
#the journal.
デバイス空間は、同じ大きさのセグメントに分割されています。セグメントは
LogFS での基本的な書き込み単位です。各セグメントでは、書き込みは最初 (低
位アドレス) から最後 (高位アドレス) の方向に向かって行われます。セグメン
トの一部のみが書き込まれる場合、セグメント番号、セグメント内の最終書き込
み位置、オプションとして書き込みバッファの三つがジャーナルに保存されます。

#Segments are erased as a whole.  Therefore Garbage Collection may be
#required to completely free a segment before doing so.
セグメントは、セグメント単位で消去されます。このため、消去の前にはセグメン
トを完全に空きにするためのガベージコレクションが必要になります。

#Journal
#--------
ジャーナル
----------

#The journal contains all global information about the filesystem that
#is subject to frequent change.  At mount time, it has to be scanned
#for the most recent commit entry, which contains a list of pointers to
#all currently valid entries.
ジャーナルには、ファイルシステムの頻繁に変更されるグローバル情報すべてが
格納されます。マウント時に、ジャーナルをスキャンして最後にコミットされた
エントリを取得する必要が有ります。このエントリには、現在有効な全てのエン
トリへのポインタのリストが格納されています。

#Object Store
#------------
オブジェクトストア
------------------

#All space except for the superblocks and journal is part of the object
#store.  Each segment contains a segment header and a number of
#objects, each consisting of the object header and the payload.
#Objects are either inodes, directory entries (dentries), file data
#blocks or indirect blocks.
スーパーブロックとジャーナル以外の領域は、オブジェクトストア部になります。
各セグメントはセグメントヘッダと複数のオブジェクトを含みます。また、各オ
ブジェクトはオブジェクトヘッダとペイロードからなります。オブジェクトは、
inode か、ディレクトリエントリ (dentry) か、ファイルデータブロックか、間
接参照ブロックかの何れかです。

#Levels
#------
レベル
------

#Garbage collection (GC) may fail if all data is written
#indiscriminately.  One requirement of GC is that data is separated
#roughly according to the distance between the tree root and the data.
#Effectively that means all file data is on level 0, indirect blocks
#are on levels 1, 2, 3 4 or 5 for 1x, 2x, 3x, 4x or 5x indirect blocks,
#respectively.  Inode file data is on level 6 for the inodes and 7-11
#for indirect blocks.
全てのデータがいきあたりばったりに書かれていた場合、ガベージコレクション
(GC) が失敗する可能性が出てきます。GC 動作の必要条件の一つは、データがツ
リーのルートとデータまでの距離に従って大雑把に分散配置されていることです。
これは、実効的には、全てのファイルデータがレベル 0 にあった場合、1x, 2x,
3x, 4x, 5x の間接ブロックに対してレベル 1, 2, 3, 4, 5 の間接ブロックが順
に対応するということです。Inode ファイルデータは inode のレベル 6 に置か
れ、7-11 が間接ブロック向けになります。

#Each segment contains objects of a single level only.  As a result,
#each level requires its own separate segment to be open for writing.
各セグメントには単一のレベルのオブジェクトのみが格納されます。この結果、
書き込みに伴うオープンのためには、各レベルで専用のセグメントが必要になり
ます。

#Inode File
#----------
Inode ファイル
--------------

#All inodes are stored in a special file, the inode file.  Single
#exception is the inode file's inode (master inode) which for obvious
#reasons is stored in the journal instead.  Instead of data blocks, the
#leaf nodes of the inode files are inodes.
inode は全て inode ファイルという特別のファイルに格納されます。ただ一つの
例外は、inode ファイルの inode (マスタ inode) で、これは理由はあきらかと
思いますがジャーナルに格納されます。データブロックの場合とは異なり、inode
ファイルのリーフノードは inode になります。

#Aliases
#-------
エイリアス
----------

#Writes in LogFS are done by means of a wandering tree.  A naïve
#implementation would require that for each write or a block, all
#parent blocks are written as well, since the block pointers have
#changed.  Such an implementation would not be very efficient.
LogFS への書き込みは、ツリーの探索によって行われます。素朴な実装だと一つ
のブロックの書き込み毎にこの探索が必要になり、さらにブロックポインタが変
更されるため全ての親ブロックへの書き込みも行われます。このような実装はと
ても効率的とは言えません。

#In LogFS, the block pointer changes are cached in the journal by means
#of alias entries.  Each alias consists of its logical address - inode
#number, block index, level and child number (index into block) - and
#the changed data.  Any 8-byte word can be changes in this manner.
LogFS では、ブロックポインタの更新はエイリアスエントリとしてジャーナルに
キャッシュされます。各エイリアスには論理アドレス (inode 番号、ブロックイ
ンデックス、レベルと子番号 (ブロックへのインデックス)) と、更新データが格
納されています。各 8 バイト (1 ワード) は、このような内容の変更である可能
性があります。

#Currently aliases are used for block pointers, file size, file used
#bytes and the height of an inodes indirect tree.
現在、ブロックポインタ、ファイルサイズ、ファイルの使っているバイト数、
inode の間接ツリーの深さデータの格納にエイリアスが用いられています。

#Segment Aliases
#---------------
セグメントエイリアス
--------------------

#Related to regular aliases, these are used to handle bad blocks.
#Initially, bad blocks are handled by moving the affected segment
#content to a spare segment and noting this move in the journal with a
#segment alias, a simple (to, from) tupel.  GC will later empty this
#segment and the alias can be removed again.  This is used on MTD only.
通常のエイリアスとよく似ていますが、これらはバッドブロック処理で用います。
バッドブロックを見つけた場合、問題のあるセグメントがスペアセグメントに移
動され、移動したことがセグメントエイリアスとして、単純なタプル (移動元、
移動先) 形式でジャーナルに記録されます。そののち GC がこのセグメントを空
にし、エイリアスは再度削除可能になります。この機能は MTD でのみ使用します。

#Vim
#---
Vim
---

#By cleverly predicting the life time of data, it is possible to
#separate long-living data from short-living data and thereby reduce
#the GC overhead later.  Each type of distinc life expectency (vim) can
#have a separate segment open for writing.  Each (level, vim) tupel can
#be open just once.  If an open segment with unknown vim is encountered
#at mount time, it is closed and ignored henceforth.
データの寿命を賢く予測することにより、長期の寿命を持つデータと短期の寿命
しか持たないデータとを区別し、その結果後での GC オーバヘッドを削減するこ
とが可能になります。個々の予測寿命 (vim) タイプは独立のセグメントを持ち、
書き込み可能です。各 レベル/vim タプルは一回だけオープン可能です。マウン
ト時に vim の不明な開かれたセグメントを見つけた場合、それは閉じられて以降
無視されます。

#Indirect Tree
#-------------
間接ツリー
----------

#Inodes in LogFS are similar to FFS-style filesystems with direct and
#indirect block pointers.  One difference is that LogFS uses a single
#indirect pointer that can be either a 1x, 2x, etc. indirect pointer.
#A height field in the inode defines the height of the indirect tree
#and thereby the indirection of the pointer.
LogFS の inode は FFS に似たファイルシステムで、直接ブロックポインタと間
接ブロックポインタをもっています。一つの違いは、LogFS では一つの間接ポイ
ンタが 1x 2x などの間接ポインタとなりうる点が異なります。inode の height
フィールドは間接ツリーの深さ、つまりポインタの間接参照の深さを定めていま
す。

#Another difference is the addressing of indirect blocks.  In LogFS,
#the first 16 pointers in the first indirect block are left empty,
#corresponding to the 16 direct pointers in the inode.  In ext2 (maybe
#others as well) the first pointer in the first indirect block
#corresponds to logical block 12, skipping the 12 direct pointers.
#So where ext2 is using arithmetic to better utilize space, LogFS keeps
#arithmetic simple and uses compression to save space.
もう一つの違いは、間接ブロックのアドレス方法にあります。LogFS では、最初
の間接ブロックの初めから 16 個のポインタは空で残され、これは inode の 16
個の直接ブロックのポインタに対応します。ext2 (恐らく他にも) では、最初の
間接ブロックの初めから 12 個のポインタは空で残され、12 個の直接ブロックの
ポインタをスキップしています。つまり、ext2 では計算を行ってスペースの利用
効率をあげているのに対して、LogFS では計算を単純に留めてスペースの節約は
圧縮で行うという設計です。

#Compression
#-----------
圧縮
----

#Both file data and metadata can be compressed.  Compression for file
#data can be enabled with chattr +c and disabled with chattr -c.  Doing
#so has no effect on existing data, but new data will be stored
#accordingly.  New inodes will inherit the compression flag of the
#parent directory.
ファイルデータとメタデータの両方が圧縮可能です。ファイルデータの圧縮は、
chattr +c で有効化、chattr -c で無効化できます。この設定は、既存データに
は影響がなく、新規データは設定に従って書き込まれます。新しい inode は、親
ディレクトリの圧縮フラグ設定を引き継ぎます。

#Metadata is always compressed.  However, the space accounting ignores
#this and charges for the uncompressed size.  Failing to do so could
#result in GC failures when, after moving some data, indirect blocks
#compress worse than previously.  Even on a 100% full medium, GC may
#not consume any extra space, so the compression gains are lost space
#to the user.
メタデータは常に圧縮されます。但し、容量計算ではこの圧縮は無視され、非圧
縮のサイズで計算が行われます。そのようにしない場合は、データを移動した際
に間接ブロックが元のデータに比べて圧縮されなかった場合、GC が失敗するため
です。100% 一杯のメディアでも、GC で追加容量を消費することは許されないた
め、圧縮による効果はユーザからは利用できない領域という扱いになります。

#However, they are not lost space to the filesystem internals.  By
#cheating the user for those bytes, the filesystem gained some slack
#space and GC will run less often and faster.
但し、ファイルシステム内部的にはこれは無効領域という訳ではありません。ユ
ーザには嘘のサイズを報告することによって、ファイルシステムは余分の領域を
稼ぎ、GC 実行回数が減りますし、高速に動作するようにもなります。

#Garbage Collection and Wear Leveling
#------------------------------------
ガベージコレクションとウェアレベリング
--------------------------------------

#Garbage collection is invoked whenever the number of free segments
#falls below a threshold.  The best (known) candidate is picked based
#on the least amount of valid data contained in the segment.  All
#remaining valid data is copied elsewhere, thereby invalidating it.
ガベージコレクションは、空きセグメント数がしきい値を下回った場合にはいつ
も起動されます。最良の (既知の) 候補が、セグメントに格納されている有効デ
ータ量が少ない順に選択されます。残っている有効データは他の場所にコピーさ
れ、セグメントは無効化されます。

#The GC code also checks for aliases and writes then back if their
#number gets too large.
GC コードではエイリアス数もチェックし、(しきい値を越えるほど) 大きくなっ
ていた場合には書き込みを実施します。

#Wear leveling is done by occasionally picking a suboptimal segment for
#garbage collection.  If a stale segments erase count is significantly
#lower than the active segments' erase counts, it will be picked.  Wear
#leveling is rate limited, so it will never monopolize the device for
#more than one segment worth at a time.
ウェアレベリングは、ガベージコレクション中に最適ではないセグメントを「時
々」抽出することで実行されます。無効なセグメントの消去数 (訳注:ページの累
積消去回数) が有効なセグメントの消去回数より「明白に少ない」場合、そのセ
グメントが選択されます。ウェアレベリングの頻度は制限されており、一度に一
つのセグメント分以上にデバイスを占有することはありません。

#Values for "occasionally", "significantly lower" are compile time
#constants.
ここで「時々」と「明白に少ない」ことを判断する各しきい値は、コンパイル時
に設定されます。

#Hashed directories
#------------------
ディレクトリハッシュ
--------------------

#To satisfy efficient lookup(), directory entries are hashed and
#located based on the hash.  In order to both support large directories
#and not be overly inefficient for small directories, several hash
#tables of increasing size are used.  For each table, the hash value
#modulo the table size gives the table index.
効率的な lookup() を実現するために、ディレクトリエントリはハッシュ化され
てハッシュを元に位置が決定されるようになっています。巨大な (ファイル数の
多い) ディレクトリをサポートし、同時に小さなディレクトリで過度に非効率に
ならないようにするため、サイズが (順に) 大きくなる複数のハッシュテーブル
が使われています。各テーブルでは、ハッシュ値をテーブルサイズで割った剰余
がテーブルインデックスとして使われます。

#Tables sizes are chosen to limit the number of indirect blocks with a
#fully populated table to 0, 1, 2 or 3 respectively.  So the first
#table contains 16 entries, the second 512-16, etc.
テーブルサイズは、順に 0、1、2、3 階層のテーブルに間接ブロックを一杯に格
納した数の制限を元に選択されます。つまり最初のテーブルが 16 エントリを格
納し、二番目が 512-16 エントリを格納し、のようになります。

#The last table is special in several ways.  First its size depends on
#the effective 32bit limit on telldir/seekdir cookies.  Since logfs
#uses the upper half of the address space for indirect blocks, the size
#is limited to 2^31.  Secondly the table contains hash buckets with 16
#entries each.
最後のテーブルは様々の意味で特別です。まず、そのサイズは実質的に
telldir/seekdir クッキーの 32bit 制限に依存しています。これは、logfs がア
ドレス空間の上半分を間接ブロックに用いているため、サイズが 2^31 に制限さ
れるためです。次に、テーブルには各 16 エントリのハッシュバケットが格納さ
れています。

#Using single-entry buckets would result in birthday "attacks".  At
#just 2^16 used entries, hash collisions would be likely (P >= 0.5).
#My math skills are insufficient to do the combinatorics for the 17x
#collisions necessary to overflow a bucket, but testing showed that in
#10,000 runs the lowest directory fill before a bucket overflow was
#188,057,130 entries with an average of 315,149,915 entries.  So for
#directory sizes of up to a million, bucket overflows should be
#virtually impossible under normal circumstances.
エントリが一つしかないバケットでは、「誕生日攻撃」の餌食になってしまいま
す。たった 2^16 エントリしか使っていない場合には、ハッシュ衝突確率は
>=0.5 になるでしょう。数学は得意ではありませんので、バケットを溢れされる
のに必要な 17 回の衝突の組み合わせの計算はできませんが、最下位のディレク
トリを 10,000 回埋める実験の結果によるとバケットが溢れるまで最小で
188,057,130 エントリが作成でき、平均的には 315,149,915 エントリが作成可能
でした。従って、ディレクトリサイズが 1,000,000 以下なら、バケットオーバフ
ローは通常の条件下ではまず起こらないと思います。

#With carefully chosen filenames, it is obviously possible to cause an
#overflow with just 21 entries (4 higher tables + 16 entries + 1).  So
#there may be a security concern if a malicious user has write access
#to a directory.
ファイル名を注意深く選択するなら、単に 21 エントリ (4 つの上位テーブル +
16 エントリ + 1) でオーバフローを発生させることができるのもあきらかですか
ら、悪意を持ったユーザがディレクトリへの書き込み権限を持っている場合、セ
キュリティの懸念があるでしょう。

#Open For Discussion
#===================
今後議論すべき内容
==================

#Device Address Space
#--------------------
デバイスアドレス空間
--------------------

#A device address space is used for caching.  Both block devices and
#MTD provide functions to either read a single page or write a segment.
#Partial segments may be written for data integrity, but where possible
#complete segments are written for performance on simple block device
#flash media.
デバイスアドレス空間はキャッシュのために用います。ブロックデバイスと MTD
の両方が一ページ読み出しとセグメント書き込みの両方の関数を提供しています。
セグメントの一部のみをデータ整合性のために書き込むこともありますが、単純
なブロックデバイス型フラッシュメディアでの性能のため、可能な限りセグメン
トまるごとの書き込みが行われます。

#Meta Inodes
#-----------
メタ inode
----------

#Inodes are stored in the inode file, which is just a regular file for
#most purposes.  At umount time, however, the inode file needs to
#remain open until all dirty inodes are written.  So
#generic_shutdown_super() may not close this inode, but shouldn't
#complain about remaining inodes due to the inode file either.  Same
#goes for mapping inode of the device address space.
inode は inode ファイルに書き込まれます。殆どの目的では、inode ファイルは
単なる普通のファイルですが、umount 時だけは inode ファイルは全てのダーティ
inode の書き込みが完了するまでオープンしておく必要があります。従って、
generic_shutdown_super() ではこの inode をクローズできませんが、この
inode ファイルのために「残っている inode がある」という警告を出すことも許
されません。デバイスアドレス空間でのマップされた inode についても同じ問題
があります。

#Currently logfs uses a hack that essentially copies part of fs/inode.c
#code over.  A general solution would be preferred.
現在、logfs では fs/inode.c コードの一部をコピーしたハックで対応していま
す。汎用の解決方法が求められています。

#Indirect block mapping
#----------------------
間接ブロックマッピング
----------------------

#With compression, the block device (or mapping inode) cannot be used
#to cache indirect blocks.  Some other place is required.  Currently
#logfs uses the top half of each inode's address space.  The low 8TB
#(on 32bit) are filled with file data, the high 8TB are used for
#indirect blocks.
圧縮を用いる場合、ブロックデバイス (およびマッピング inode) は間接ブロッ
クをキャッシュするために利用することはできません。どこか他の場所が必要で
す。現在、logfs は各 inode アドレス空間の上半分を使うようになっています。
(32bit の場合) 下位の 8TB にはファイルデータが格納され、上位 8TB は間接ブ
ロックのために使われます。

#One problem is that 16TB files created on 64bit systems actually have
#data in the top 8TB.  But files >16TB would cause problems anyway, so
#only the limit has changed.
一つ問題があって、64bit システムで作成された 16TB のファイルには、実際に
上位の 8TB にデータが格納されることになります。ただし、いずれにせよ 16TB
より大きいファイルでは問題が発生しますから、制限が変わっただけということ
です。

------>8------------>8------------>8------------>8------------>8