오르로프 블록 할당자

Orlov block allocator

Orlov 블록 할당자는 특정 파일이 특정 파일 시스템(블록 단위)에서 어디에 위치하는지 정의하여 디스크 작업을 가속화하는 알고리즘입니다.

어원학

이 스킴의 이름은 2000년에 BSD Fast Filesystem 커널 변형에서 사용된 OpenBSD에[1] 대한 간단한 설명과 구현을 처음 게시한 그리고리 올로프의 이름을 따왔다.

배경

파일 시스템의 성능은 여러 가지 요소에 따라 달라집니다. 중요한 요소 중 하나는 파일 시스템이 디스크에 파일을 배치하는 방식입니다.일반적으로 관련 항목은 함께 보관하는 것이 가장 좋습니다.예를 들어 Linux ext2 및 ext3 파일 시스템은 디스크의 실린더에 디렉토리를 분산하려고 했습니다.사용자의 홈 디렉토리가 /home에 있는 시스템을 셋업하는 경우를 상상해 보십시오. /home 내의 모든 1레벨 디렉토리(즉, 다수의 사용자의 홈 디렉토리)가 서로 옆에 배치되어 있는 경우, 이러한 디렉토리의 컨텐츠를 위한 공간이 남아 있지 않을 수 있습니다.따라서 사용자 파일은 해당 파일을 포함하는 디렉토리에서 멀리 떨어져 배치되어 성능이 저하됩니다.

디스크에 디렉토리를 전개하면, 같은 디렉토리에 있는 파일의 수나 사이즈가 커짐에 따라, 어느 쪽인가 연속해 유지할 수 있습니다.다만, 디스크 표면의 데이터가 과도하게 퍼지는 경우가 있습니다.

구조

기본적으로 Orlov 알고리즘은 각각이 서로 관련이 없다는 가정 하에 "최상위" 디렉토리를 배포하려고 합니다.파일 시스템의 루트 디렉토리에 작성된 디렉토리는 최상위 디렉토리로 간주됩니다.Theodore Tso는 시스템 관리자가 다른 디렉토리를 최상위 디렉토리로 표시할 수 있는 특별한 inode 플래그를 추가했습니다.한다면/homeroot 파일 시스템에 존재하며,chattr명령어를 실행하면 시스템은 그것을 최상위 디렉토리로 취급합니다.

최상위 디렉토리에 없는 디렉토리를 작성할 때 Orlov 알고리즘은 상위 디렉토리와 동일한 실린더 그룹에 넣으려고 합니다.다만, 디렉토리의 컨텐츠가 그 실린더 그룹에도 들어갈 수 있도록 하기 위해서, 조금 더 주의를 기울여 주세요.그룹내에 사용 가능한 inode나 블록이 많지 않으면, 디렉토리는 보다 많은 자원을 가지는 다른 실린더 그룹에 배치됩니다.그 결과, 실제로 서로 관련되어 있고 함께 액세스 할 가능성이 높은 파일들이 훨씬 더 나은 위치에 위치할 수 있기를 바랍니다.

성능

Orlov 블록 할당기는 FreeBSD의 디렉토리[2] 트리를 통과하는 워크로드의 성능을 향상시키는 것으로 나타났습니다.2007년 10월 현재 allocator를 사용한ext3 벤치마크[3] 결과는 1개뿐인 것 같습니다.결과는 유망합니다. Linux 커널 트리를 통과하는 데 필요한 시간이 약 30% 단축되었습니다.

진화

Orlov 스킴은 보다 엄격한 벤치마킹이 필요합니다.또한 파일 시스템이 시간이 지남에 따라 변경되어도 퍼포먼스가 저하되지 않는다는 것을 증명하기 위해 몇 가지 심각한 스트레스 테스트도 필요합니다.

레퍼런스

  1. ^ Grigoriy Orlov. "Directory Allocation Algorithm For FFS". Archived from the original on 2008-01-31.
  2. ^ Recent Filesystem Optimisations in FreeBSD
  3. ^ Bert Hubert, Naive but spectacular ext3 HTREE+Orlov benchmark

외부 링크