요약·해설과 원문, 전문 번역을 서로 분리했습니다. API 이름, symbol, source path는 원문 표기를 사용합니다.
1. 요약·해설
원문의 핵심 논리와 kernel programming 관점의 보충 설명입니다. 아래의 전문 번역과는 별도로 작성했습니다.
2. 영어 원문 전체
번역 기준이 된 Linux v6.18.37 원문입니다. 줄 번호는 이 버전의 파일 좌표입니다.
원문 전체 펼치기
.. SPDX-License-Identifier: GPL-2.0
Block and Inode Allocation Policy
---------------------------------
ext4 recognizes (better than ext3, anyway) that data locality is
generally a desirably quality of a filesystem. On a spinning disk,
keeping related blocks near each other reduces the amount of movement
that the head actuator and disk must perform to access a data block,
thus speeding up disk IO. On an SSD there of course are no moving parts,
but locality can increase the size of each transfer request while
reducing the total number of requests. This locality may also have the
effect of concentrating writes on a single erase block, which can speed
up file rewrites significantly. Therefore, it is useful to reduce
fragmentation whenever possible.
The first tool that ext4 uses to combat fragmentation is the multi-block
allocator. When a file is first created, the block allocator
speculatively allocates 8KiB of disk space to the file on the assumption
that the space will get written soon. When the file is closed, the
unused speculative allocations are of course freed, but if the
speculation is correct (typically the case for full writes of small
files) then the file data gets written out in a single multi-block
extent. A second related trick that ext4 uses is delayed allocation.
Under this scheme, when a file needs more blocks to absorb file writes,
the filesystem defers deciding the exact placement on the disk until all
the dirty buffers are being written out to disk. By not committing to a
particular placement until it's absolutely necessary (the commit timeout
is hit, or sync() is called, or the kernel runs out of memory), the hope
is that the filesystem can make better location decisions.
The third trick that ext4 (and ext3) uses is that it tries to keep a
file's data blocks in the same block group as its inode. This cuts down
on the seek penalty when the filesystem first has to read a file's inode
to learn where the file's data blocks live and then seek over to the
file's data blocks to begin I/O operations.
The fourth trick is that all the inodes in a directory are placed in the
same block group as the directory, when feasible. The working assumption
here is that all the files in a directory might be related, therefore it
is useful to try to keep them all together.
The fifth trick is that the disk volume is cut up into 128MB block
groups; these mini-containers are used as outlined above to try to
maintain data locality. However, there is a deliberate quirk -- when a
directory is created in the root directory, the inode allocator scans
the block groups and puts that directory into the least heavily loaded
block group that it can find. This encourages directories to spread out
over a disk; as the top-level directory/file blobs fill up one block
group, the allocators simply move on to the next block group. Allegedly
this scheme evens out the loading on the block groups, though the author
suspects that the directories which are so unlucky as to land towards
the end of a spinning drive get a raw deal performance-wise.
Of course if all of these mechanisms fail, one can always use e4defrag
to defragment files.
3. 한국어 전문 번역
영어 원문의 문단 순서와 의미를 유지한 전체 번역입니다. 코드, 함수명, symbol과 URL은 원문 표기를 유지합니다.
locality, multi-block와 delayed allocation
1-30ext4는 ext3보다 data locality가 파일시스템에 바람직하다는 점을 더 적극적으로 반영합니다. spinning disk에서는 관련 block을 가까이 두면 data block 접근을 위한 head actuator와 disk 이동이 줄어 I/O가 빨라집니다.
SSD에는 움직이는 부품이 없지만 locality가 좋으면 각 transfer request를 크게 만들고 전체 request 수를 줄일 수 있습니다. write가 한 erase block에 모여 file rewrite가 크게 빨라질 수도 있으므로 가능한 한 fragmentation을 줄이는 것이 유용합니다.
첫 번째 수단은 multi-block allocator입니다. 파일을 처음 만들 때 곧 write될 것으로 추정해 8KiB disk space를 미리 할당합니다. 파일을 닫을 때 쓰지 않은 speculative allocation은 해제합니다. 작은 파일을 한 번에 완전히 쓰는 흔한 경우처럼 예측이 맞으면 file data를 하나의 multi-block extent로 기록합니다.
두 번째 수단은 delayed allocation입니다. write를 흡수할 block이 더 필요해도 dirty buffer를 disk에 write out할 때까지 정확한 배치를 결정하지 않습니다. commit timeout 도달, `sync()` 호출, kernel memory 부족처럼 꼭 필요한 시점까지 결정을 늦춰 더 나은 위치를 선택하려는 방식입니다.
미리 확보하고 실제 위치 결정을 늦춰 연속 extent를 만드는 과정입니다.
.. SPDX-License-Identifier: GPL-2.0
Block and Inode Allocation Policy
---------------------------------
ext4 recognizes (better than ext3, anyway) that data locality is
generally a desirably quality of a filesystem. On a spinning disk,
keeping related blocks near each other reduces the amount of movement
that the head actuator and disk must perform to access a data block,
thus speeding up disk IO. On an SSD there of course are no moving parts,
but locality can increase the size of each transfer request while
reducing the total number of requests. This locality may also have the
effect of concentrating writes on a single erase block, which can speed
up file rewrites significantly. Therefore, it is useful to reduce
fragmentation whenever possible.
The first tool that ext4 uses to combat fragmentation is the multi-block
allocator. When a file is first created, the block allocator
speculatively allocates 8KiB of disk space to the file on the assumption
that the space will get written soon. When the file is closed, the
unused speculative allocations are of course freed, but if the
speculation is correct (typically the case for full writes of small
files) then the file data gets written out in a single multi-block
extent. A second related trick that ext4 uses is delayed allocation.
Under this scheme, when a file needs more blocks to absorb file writes,
the filesystem defers deciding the exact placement on the disk until all
the dirty buffers are being written out to disk. By not committing to a
particular placement until it's absolutely necessary (the commit timeout
is hit, or sync() is called, or the kernel runs out of memory), the hope
is that the filesystem can make better location decisions.inode locality와 block group 분산
31-56세 번째 수단은 ext4와 ext3 모두 file data block을 가능하면 inode와 같은 block group에 두는 것입니다. 파일을 열 때 inode를 읽은 뒤 data block으로 이동하는 seek penalty를 줄입니다.
네 번째 수단은 가능하면 directory 안의 모든 inode를 그 directory와 같은 block group에 두는 것입니다. 같은 directory의 파일들이 서로 관련됐을 가능성이 높다는 가정에 따라 함께 배치합니다.
다섯 번째 수단은 disk volume을 128MB block group으로 나누고 이 작은 container 안에서 locality를 유지하는 것입니다. 다만 root directory 바로 아래에 directory를 만들 때는 의도적으로 다르게 동작합니다.
root의 새 directory는 inode allocator가 block group들을 scan해 가장 덜 사용된 group, 즉 least-loaded group에 배치합니다. top-level directory와 file 덩어리가 group 하나를 채우면 allocator가 다음 group으로 이동하므로 directory가 disk 전체에 퍼지고 group load가 고르게 됩니다. 저자는 spinning drive 끝부분에 놓인 directory가 raw performance에서 불리할 수 있다고 덧붙입니다.
이 모든 mechanism으로도 fragmentation을 해소하지 못하면 `e4defrag`로 파일을 defragment할 수 있습니다.
allocator가 관련 metadata와 data를 묶으면서 top-level load를 분산하는 정책입니다.
The third trick that ext4 (and ext3) uses is that it tries to keep a
file's data blocks in the same block group as its inode. This cuts down
on the seek penalty when the filesystem first has to read a file's inode
to learn where the file's data blocks live and then seek over to the
file's data blocks to begin I/O operations.
The fourth trick is that all the inodes in a directory are placed in the
same block group as the directory, when feasible. The working assumption
here is that all the files in a directory might be related, therefore it
is useful to try to keep them all together.
The fifth trick is that the disk volume is cut up into 128MB block
groups; these mini-containers are used as outlined above to try to
maintain data locality. However, there is a deliberate quirk -- when a
directory is created in the root directory, the inode allocator scans
the block groups and puts that directory into the least heavily loaded
block group that it can find. This encourages directories to spread out
over a disk; as the top-level directory/file blobs fill up one block
group, the allocators simply move on to the next block group. Allegedly
this scheme evens out the loading on the block groups, though the author
suspects that the directories which are so unlucky as to land towards
the end of a spinning drive get a raw deal performance-wise.
Of course if all of these mechanisms fail, one can always use e4defrag
to defragment files.
요약·해설
allocators.rst:1-56ext4 allocator는 speculative multi-block allocation과 delayed allocation으로 연속 extent를 만들고, inode·data·directory를 같은 128MB block group에 모아 locality를 높입니다. root 하위 directory만 덜 사용된 group으로 분산해 load를 고르게 하며, 사후에는 `e4defrag`를 사용할 수 있습니다.
시간과 공간 두 축에서 allocation 결정을 최적화합니다.