14. File-System Implementation

파일 시스템의 내부 구현, 즉 파일 사용을 구조화하고, 저장소 공간을 할당하고, 여유 공간을 복구하고, 데이터의 위치를 추적하고, 운영체제의 다른 부분을 이차 저장소와 상호작용시키는 것에 대해 알아보자.

14.1. File-System Structure

대부분 이차 저장소로는 디스크가 쓰이는데, 제자리에서 수정될 수 있으며 담고 있는 정보 블록을 직접 접근할 수 있다는 특성 때문이다. 반면에 비휘발성 메모리는 파일 저장소와 파일 시스템에 더 많이 쓰이고 있는데, 이는 제자리에서 덮어쓸 수 없으며 이로 인한 성능차가 있다.

입출력 효율성을 높이기 위해, 메모리와 대용량 저장소간 입출력 전송은 블록 단위로 이루어진다. 파일 시스템은 데이터를 저장하고, 위치시키고, 검색하도록 해서 저장소 기기에 대한 효율적이고 편리한 접근을 제공한다. 설계상의 고려 요소는 파일 시스템이 사용자에게 어떻게 보여야 할지랑, 논리적 파일 시스템을 물리적 이차 저장소 기기와 연결지을 알고리즘과 자료구조를 생각하는 것이다.

파일 시스템은 여러 다른 층으로 이루어져 있다. 입출력 제어 층은 메인 메모리와 디스크 시스템간 정보를 전달하기 위한 장치 드리이버와 인터럽트 핸들러로 이루어진다. 기본 파일 시스템은 적절한 장치 드라이버가 저장소 기기의 블록들을 읽기/쓰기할 수 있게 만드는 일반적인 명령어만을 필요로 한다. 파일 구성 모듈은 파일과 논리적 블록에 대한 정보를 담는다. 마지막으로, 논리적 파일 시스템은 메타데이터 정보를 관리한다. 파일 제어 블록(FCB, UNIX에서는 inode)는 파일의 소유권, 허가, 위치 등의 정보를 담는다. 이런 층위 구조가 파일 시스템 구현에 쓰이면 중복 코드가 적어진다. 대부분의 운영 체제는 복수의 파일 시스템을 지원한다. 추가로 많은 운영 시스템은 하나 이상의 디스크 기반 운영체제를 지원한다. UNIX는 UNIX 파일 시스템(UFS)을 지원한다. Linux는 130개 이상의 다른 파일 시스템을 지원하는데, 표준 Linux 파일 시스템은 확장 파일 시스템으로 불리며 ext3, ext4 등이 있다. 파일 시스템 연구는 운영 체제 설계와 구현의 활발한 영역이다.

14.2. File-System Operations

파일 시스템 연산을 알아보자.

14.2.1. Overview

파일 시스템을 이루는 구조들 중 저장소 내 구조를 알아보자.

  • 부트 제어 블록은 시스템이 그 볼륨으로부터 운영 체제를 부팅하는 데 필요한 정보를 담는다. UFS에선 부트 블록으로 불리고 NTFS에서는 분할 부트 섹터로 불린다.
  • 볼륨 제어 블록은 볼륨의 세부 사항을 담는다. UFS에서는 슈퍼블록, NTFS에서는 마스터 파일 테이블이라 불린다.
  • 디렉토리 구조는 파일을 구성하는 데 쓰인다.
  • 파일별 파일 제어 블록은 파일의 세부 사항을 담는다.

메모리 내 구조를 알아보자.

  • 메모리 내 마운트 테이블은 마운트된 각 볼륨에 대한 정보를 담는다.
  • 메모리 내 디렉토리 구조 캐시는 최근에 접근한 디렉토리에 대한 디렉토리 정보를 담는다.
  • 시스템별 오픈 파일 테이블은 각 열린 파일에 대한 파일 제어 블록을 담는다.
  • 프로세스별 오픈 파일 테이블은 그 프로세스가 연 파일에 대해 시스템별 오픈 파일 테이블 내 제어 블록에 대한 포인터를 담는다.
  • 파일시스템 블록이 파일 시스템에 써지거나 읽힐 때 이는 버퍼에 담긴다.

새 파일을 생성할 때 프로세스는 논리적 파일 시스템을 호출하고 새로운 파일 제어 블록을 생성한다. UNIX을 포함한 어떤 운영 체제들은 디렉토리를 파일로 간주하기도 한다.

14.2.2. Usage

파일이 입출력에 쓰이려면 파일을 열어야 한다. 그 후 프로세스별 오픈 파일 테이블에 엔트리가 등록된다. 이 엔트리의 이름은 UNIX 시스템에서는 파일 디스크립터, Windows에서는 파일 핸들이라고도 불린다. 프로세스가 파일을 닫을 때 프로세스별 오픈 파일 테이블 내 해당 엔트리는 삭제된다. 파일 시스템 구조에서 캐싱으로 이를 돕는 것도 간과해서는 안 된다.

14.3. Directory Implementation

디렉토리의 구현을 알아보자.

14.3.1. Linear List

디렉토리를 구현하는 가장 간단한 방법은 데이터 블록에 대한 포인터로 구성된 파일명의 선형 리스트를 쓰는 것이다. 이것의 단점은 파일 검색이 선형 탐색이라는 것이다.

14.3.2. Hash Table

디렉토리 내 파일에 쓰는 다른 자료 구조는 해시 테이블이다. 이의 난점은 일반적으로 고정 크기이고 그 크기의 해시 함수에 의존한다는 것이다. 대안으로는 연쇄 오버플로우 해시 테이블을 쓰는 방법이 있다.

14.4. Allocation Methods

할당 방법을 알아보자.

14.4.1. Contiguous Allocation

연속된 할당은 각 파일이 기기 내에서 연속된 블록을 차지하도록 하는 것이다. 파일의 연속된 할당은 파일의 길이와 파일의 첫째 블록의 주소로 이루어진다. 연속 할당된 파일에 접근하는 것은 쉽다. 연속 할당의 난점은 새 파일을 위한 공간을 찾기 힘들다는 것인데, 이런 문제들은 동적 저장소 할당 문제의 일부로 볼 수 있다. 또한 외부 파편화의 문제도 있다. 외부 파편화로 저장소 공간이 날아가는 것을 방지하려면 전체 파일 시스템을 다른 장치에 복제한 뒤 원 장치를 비우고 다른 장치에서 원본 파일들을 연속으로 할당해 컴팩트화하면 된다. 단 이것은 오래 걸리므로 어떤 시스템들은 이것을 파일 시스템이 언마운트된 오프라인 상태에서 시작한다. 이러한 다운타임 동안에는 일반적인 대개 파일 시스템 연산이 불가능하다. 이는 온라인으로도 수행할 수 있으나 성능 저하가 클 수 있다.

연속 할당의 다른 문제는 파일에 얼마나 큰 공간이 필요한지를 판별하는 것이다. 파일에 필요한 공간의 크기를 미리 알게 되더라도 미리 할당하는 것은 비효율적일 수 있다. 이것을 막기 위해, 운영 체제는 수정된 연속 할당 방식을 쓸 수 있다. 서로 연결되지 않을 수 있는 연속된 메모리의 덩어리 (연장)을 추가하는 것이다.

14.4.2. Linked Allocation

연결된 할당은 연속된 할당의 문제를 수정한다. 이 구현에서 각 파일은 저장소 블록의 연결된 리스트로 구현된다. 파일을 생성할 때에는 디렉토리 내 새 엔트리를 추가하기만 하면 된다. 하지만 단점도 있는데, 이는 순차적 접근 파일에만 유용하고, 포인터들을 저장하는 데 추가적인 메모리가 든다는 것이다. 이에 대한 해결법은 블록 여러 개를 클러스터로 군집화해 블록 단위가 아닌 클러스터 단위로 할당하는 것이다. 연결 할당의 또 다른 문제는 가용성이다. 포인터 하나가 잘못되면 전체가 잘못되기 때문이다. 해결책은 이중 연결 리스트를 쓰는 것이다. 연결 할당의 중요한 변형은 파일 할당 테이블(FAT)이다. 이는 연결 리스트와 비슷한데, 캐시되지 않은 이상 많은 양의 디스크 헤드 검색을 야기할 수 있다.

14.4.3. Indexed Allocation

연결 할당은 연속 할당의 외부 파편화와 크기 선언 문제를 해결한다. 하지만 효율적인 직접 접근을 제공해 주지는 못하는데, 인덱스화된 할당은 포인터를 인덱스 블록에 몰아넣어 이를 해결한다. 이는 외부 파편화 없는 직접 접근을 제공한다. 저장소 기기 내 임의의 가용 블록은 더 많은 공간에 대한 요청을 수행할 수 있기 때문이다. 그러나 공간 낭비의 문제는 남는다. 인덱스 블록의 크기는 작은 게 좋은데 큰 파일에 대해서도 충분한 포인터를 담기 위해선 다음의 방법을 이용한다: 연결 방법, 다층 인덱스, 결합된 방법. 결합된 방법에서는 인덱스 블록을 직접 블록간접 블록으로 나누고, 간접 블록은 다시 단일 간접 블록, 2중 간접 블록, 3중 간접 블록으로 나뉜다. 인덱스화된 할당도 연결 할당과 같은 성능 문제를 일부 겪는다.

14.4.4 Performance

할당 방법을 고르기 전에는 시스템이 어떻게 사용될 것인지를 먼저 결정해야 할 필요가 있다. 모든 타입의 접근에 대해 연속된 할당은 단 하나의 블록 접근만을 필요로 한다. 직접 접근에 대해서는 연속 할당은 쓰기 어려우므로 연속 할당은 순차적 접근에 대해서만 쓰여야 한다. 인덱스화된 할당은 더 어렵다. 이 때의 성능은 인덱스 구조, 파일 크기, 원하는 블록의 위치에 따라 다르다. 어떤 시스템들은 연속된 할당과 인덱스화된 할당을 조합하는데, 작은 파일에는 연속된 할당을 쓰고 파일이 커지면 인덱스화된 할당으로 전환한다. 다른 최적화들도 쓰일 수 있다. 비휘발성 메모리 기기에 대해서는 디스크 헤드 탐색이 없기 때문에 다른 알고리즘과 최적화가 필요하다.

14.5. Free-Space Management

빈 디스크 공간을 추적하기 위해 시스템은 빈 공간 리스트를 유지한다.

14.5.1. Bit Vector

빈 공간 리스트는 비트맵 또는 비트벡터로 많이 구현한다. 이는 단순함과 효율성이라는 장점이 있으나, 전체 벡터가 메인 메모리에 저장되어 있지 않은 이상 비효율적이다.

14.5.2. Linked List

빈 공간 관리를 하는 또 다른 접근법은 빈 블록들을 연결 리스트로 연결하는 것이다.

14.5.3. Grouping

빈 리스트 접근법에서 n개의 빈 블록의 주소를 첫 블록에 모아 놓는 방법이 있다.

14.5.4. Counting

여러 연속된 블록은 한꺼번에 할당/해제될 수 있기 때문에 연속된 블록에 대해서는 한 블록만 주소를 갖고 그 뒤에 있는 블록 수를 기록하는 방법도 있다.

14.5.5. Space Maps

Oracle의 ZFS 파일시스템은 대량의 파일, 디렉토리, 심지어 파일시스템도 포함할 수 있도록 설계되었다. 이 파일시스템이 빈 공간 관리를 할 때 여러 방법을 조합한다. ZFS는 빈 공간들을 적당한 크기의 메타슬랩으로 쪼갠 뒤 이를 활용한다.

14.5.6. TRIMing Unused Blocks

비휘발성 플래시 메모리같이 덮어쓰기를 지원하지 않는 저장소 기기에 대해서는 장치에 페이지가 해제되었음을 알려주는 방식을 적용할 필요가 있다.

14.6. Efficiency and Performance

여러 할당 방법과 디렉토리 관리 방법의 효율성과 성능을 알아보자.

14.6.1. Efficiency

저장소 기기 공간의 효율적인 사용은 쓰는 할당과 디렉토리 알고리즘에 달려 있다. 많은 서로 다른 방법이 사용된다.

14.6.2. Performance

기본적인 파일시스템 알고리즘이 선택되어도, 성능을 여러 방법으로 개선할 수 있다. 어떤 시스템들은 메인 메모리의 일부 섹션을 버퍼 캐시로 분리하고 다른 시스템들은 파일 데이터를 페이지 캐시로 캐싱한다. 여러 시스템은 페이지 캐싱을 이용해 페이지와 파일 데이터를 모두 캐싱한다. 이를 통일 가상 메모리라 한다. UNIX와 Linux의 어떤 버전들은 통일 버퍼 캐시를 제공한다. 통일 버퍼 캐시를 사용하지 않는다면 가상 메모리 시스템은 버퍼 캐시와 상호작용을 하지 않기 때문에 파일을 열고 닫을 때 메모리 매핑 호출은 페이지 캐시와 버퍼 캐시를 모두 필요로 하는데 이를 이중 캐시라 한다. 이는 메모리와 동작시간 면에서 큰 문제가 된다. 대부분의 상황에서 블록과 페이지를 대체할 때는 최소 최근 사용 캐시가 괜찮은 선택이다.

입출력 성능에 영향을 미치는 또 다른 문제는 파일 시스템에 쓰는 연산이 동기적인지 비동기적인지이다. 동기 쓰기는 저장소 서브시스템이 쓰기 요청을 받는 순서대로 수행되고 쓰기는 버퍼링되지 않는다. 비동기 쓰기는 데이터가 캐싱되고 제어 흐름이 호출자에 되돌아간다. 대부분의 쓰기는 비동기적이나, 메타데이터 쓰기나 원자적 트랜잭션은 동기적일 수 있다. 어떤 시스템들은 서로 다른 대체 알고리즘으로 페이지 캐시를 최적화한다. 이후 해제는 다음 페이지가 요청되자마자 페이지를 버퍼에서 지운다. 미리 읽기는 호출된 페이지와 이후 페이지 몇 개가 읽어지고 캐싱된다. 쓰기는 읽기보다 훨씬 비동기적이기 때문에 작은 전송에 대해서는 파일 시스템을 통한 디스크로의 출력은 입력보다 빠르다.

14.7. Recovery

시스템 실패가 데이터 유실이나 데이터 비일관성을 낳으면 안 된다. 파일 시스템이 데이터 손상에 대처하는 법을 알아보자.

14.7.1. Consistency Checking

데이터의 일관성은 일관성 검사기로 이루어진다. 이는 디렉토리 구조나 다른 메타데이터 내 데이터를 저장소 내의 상태와 비교해 일관성을 고친다.

14.7.2. Log-Structured File Systems

데이터베이스의 로그 기반 복구 알고리즘은 일관성 검사에도 유용하다. 결과 구현을 로그 기반 트랜잭션 지향 (저널링) 파일시스템이라 한다. 이는 로그 기반 복구를 파일시스템 메타데이터 업데이트에 적용하는 것이다. 기본적으로 모든 메타데이터 변화는 순차적으로 로깅된다. 특정 작업을 수행하기 위한 연산 집합을 트랜잭션이라 한다. 로그 파일은 원환 버퍼로 구성된다. 시스템이 크래시되면 복구 시 커밋되었던 트랜잭션이 끝까지 진행되어야 한다. 트랜잭션이 중단된 경우라면 수행된 모든 변경들은 되돌려져야 한다. 디스크 메타데이터 업데이트에 로깅을 하는 것의 또다른 이점은 이러한 업데이트는 디스크에 있는 자료 구조에 직접 적용되었을 때 훨씬 더 빠르다는 것이다. 순차적 입출력이 무작위 입출력보다 성능 면에서 이점이 있기 때문이다.

14.7.3. Other Solutions

일관성 체킹에 대한 대안으로는 트랜잭션을 완전히 새 블록에 쓴 뒤 이를 교체하는 것이 있다. 이전 블록들은 일관성이 보장되기 이전까지 스냅샷에 보존된다.

14.7.4. Backup and Restore

데이터가 영영 유실되는 것을 막기 위해 시스템 프로그램은 데이터를 한 저장소 기기에서 다른 기기로 백업하고 유실된 파일은 백업으로부터 복구된다. 복제를 최소화하기 위해, 각 파일의 디렉토리 정보를 쓴다. 예를 들어 파일이 수정된 마지막 날짜가 백업 날짜 이전이면 그 파일은 재복사될 필요가 없다. 그래서 1일차에는 전체 백업을 하고 이후엔 증가적 백업을 수행한다. 이를 통해 전체 파일 시스템을 복원할 수가 있다. 이 사이클의 길이는 필요한 백업의 양과 복원을 수행하는 데 쓸 기간을 절충해야 한다. 전체 백업은 주기적으로 해줄 필요가 있다.

14.8. Example: The WAFL File System

NetApp의 원하는 위치에 쓰는 파일 레이아웃(WAFL)은 많은 최적화를 수행한다. 이는 네트워크 파일 서버에 주로 사용되는데 쓰기에는 NVRAM 캐시를 쓰며 Berkeley Fast File System과 비슷하나 많은 수정이 가해졌다. WAFL 파일 시스템은 루트 inode를 기반으로 한 블록의 트리라고 할 수 있다. 중요한 특성 중 하나는 빈 블록 맵이 블록당 한 비트 이상을 가질 수 이싿는 것이다. 다수의 스냅샷이 동시에 존재할 수 있으며, 클론이라고 불리는 읽기-쓰기 스냅샷도 존재한다. 또한, 네트워크의 데이터를 다른 시스템에 대해 복제와 동기화를 수행하는 사본도 구현에 존재한다.

14.9. Summary

  • 대다수의 파일 시스템은 대용량의 데이터를 영구적으로 보존할 수 있게 설계되어 있는 이차 저장소에 존재한다. 가장 주된 이차 저장소 도구는 디스크이나 비휘발성 메모리 장치의 사용도 증가하고 있다.
  • 저장소 기기는 매체의 사용을 제어하고 단일 기기에서 복수의 (서로 다를 수 있는) 파일 시스템을 지원하기 위해 파티션으로 분할되어 있다. 이 파일 시스템들은 논리적 파일시스템 아키텍쳐에 마운트되어 사용가능해진다.
  • 파일 시스템은 계층화되어 구현되거나 모듈화되어 구현된다. 저층은 저장소 기기의 물리적 특성을 다루고 이 기기들과 통신한다. 고층은 심볼릭 파일명이나 파일의 논리적 특성을 다룬다.
  • 파일 시스템 내의 여러 파일은 저장소 기기의 공간에 3가지 방법으로 할당될 수 있다. 연속 할당, 연결 할당, 인덱스화 할당. 연속 할당은 외부 파편화를 겪을 수 있다. 연결 할당에선 직접 접근이 매우 비효율적이다. 이 알고리즘은 여러 방법으로 최적화될 수 있다. 연속 공간은 연장을 통해 유연성을 보충하고 외부 파편화를 줄일 수 있다. 인덱스화된 할당은 여러 블록의 클러스터에 대해 수행되어 처리량을 늘리고 필요한 인덱스 수를 줄일 수 있다. 큰 클러스터에 대한 인덱싱은 연장을 도입한 연속 할당과 비슷하다.
  • 빈 공간 할당 방법은 디스크 공간 사용의 효율성과 파일 시스템의 성능, 이차 저장소의 가용성에 영향을 끼친다. 비트 벡터나 연결 리스트가 쓰인다. 최적화 방법에는 그룹화, 세기, 연결 리스트를 하나의 연속된 영역에 배치하는 FAT 등등이 있다.
  • 디렉토리 관리 루틴은 효율성, 성능, 가용성을 모두 고려해야 한다. 해시 테이블은 빠르고 효율적이므로 흔히 사용된다. 하지만 테이블이 손상되거나 시스템이 크래시되면 디렉토리 정보와 디스크 내용간 비일관성이 발생할 수 있다.
  • 일관성 검사기는 손상된 파 일시스템 구조를 복구할 수 있다. 운영 체제 백업 도구는 데이터를 마그네틱 테이프나 다른 저장소 기기에 복사해 사용자가 데이터 손실을 복구하거나 심지어는 하드웨어 실패나 운영 체제 버그나 사용자 오류로 인한 전체 기기 손실도 복구할 수 있게 한다.
  • 파일 시스템이 시스템 동작에서 차지하는 근본적 역할로 인해, 그 성능과 가용성은 매우 중요하다. 로그 구조나 캐싱 등은 성능을 늘일 수 있는데 로그 구조나 RAID는 가용상을 높인다. WAFL 파일 시스템은 특정한 입출력 부하를 견디기 위한 성능 최적화의 예시이다.

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중