논문 정리 - The Google File System

The Google File System

1. Introduction

새로운 관점

component failure은 예외가 아니라 일반적인 상황이다. 그래서 constant monitoring, error detection, fault tolerance, automatic recovery가 필요하다.

파일의 크기가 커졌다. I/O 작업이나 block 크기 등이 고려되어야 한다.

원래 있는 데이터에 덮어쓰는 작업보다는 새로운 데이터를 추가한다. 따라서 appending이 성능 최적화에 중요해졌다.

2. Design Overview

2.1 assumptions

시스템은 잘 고장나는 저렴한 장비들로 구성되어 있다.

시스템은 큰 파일이 있다. 작은 파일들도 있지만 optimizing할 때는 고려하지 않는다.

로드는 주로 큰 스트리밍 읽기와 작은 랜덤 읽기로 구성되어 있다.

로드는 또한 파일에 데이터를 추가하는 많은 sequential write가 있다.

같은 파일에 여러 사용자가 동시에 데이터를 추가하는 경우도 잘 고려해야 한다.

빠른 반응 속도 보다는 high sustained bandwidth가 더 중요하다. 대부분의 타겟 애플리케이션은 데이터 뭉텅이를 빠른 시간 내에 처리하는 것을 중요하게 여긴다.

2.2 Interface

파일은 hierarchically ,디렉토리에 정렬돼있고 path name으로 구분된다. 또한 GFS는 snapshot과 record append 기능이 있다. snapshot은 파일이나 디렉토리 트리를 복사한다. record append는 다수 클라이언트가 데이터를 하나의 파일에 동시에 추가할 수 있도록 해준다. 각 append의 atomicity를 보장하면서.

2.3 Architecture

하나의 마스터와 여러개의 chunkserver로 구성되어 있다. 그리고 다수의클라이언트가 접속한다. figure 1. 파일은 정해진 크기의 청크로 나누어진다. 각 청크는 globally 고유한 64비트 chunk handle로 구분된다. 이건 청크가 만들어질 때 마스터에 의해 할당된다. 각 청크는 여러 청크서버에 복사된다. 기본값으로는 세 복사를 저장한다. 마스터는 모든 파일 시스템의 메타데이터를 갖고 있다. 또한 시스템 단위의 활동들을 관리한다. chunk lease management나 garbage collection of orphaned chunks나 chunk migration between chunkservers를 한다. 마스터는 각 청크서버와 주기적으로 heartbeat 메세지를 통해 통신하고 상태를 받는다. 클라이언트나 청크서버 둘 다 파일 데이터를 캐싱하지 않는다. 클라이언트 캐시는 별로 도움이 안 되는게, 대부분 애플리케이션들은 큰 파일을 스트리밍하거나 캐싱되기 너무 큰 작업을 갖기 때문이다. 메타디에터는 캐싱을 한다. 청크서버도 파일 데이터를 캐싱할 필요가 없는게 청크가 로컬 파일로 저장이 되고 리눅스 버퍼가 이미 자주 접근하는 데이터는 메모리에 갖고 있기 때문이다.

2.4 Single Master

단일 마스터를 쓰면 단순해지지만 읽기와 쓰기 작업에 관여하는 정도를 최소화해서 병목 현상이 생기지 않도록 해야한다. 클라이언트는 마스터에게 어떤 청크서버를 접속할지를 물어본다. 이 정보를 캐싱해서 많은 연속된 작업을 할 때 청크서버에 직접 접근한다.

클라이언트는 파일 네임과 청크 인덱스를 통해 마스터에게 해당하는 chunk handle과 복사본의 위치를 요청한다. 그러면 이 복사본들 중에 하나에 리퀘스트를 보낸다. 보통 가장 가까운 것에 보낸다. 그 청크를 읽을 때는 마스터와 통신할 일이 없다. 캐싱된 정보가 expire되거나 file이 reopen될 때 말고는.

2.5 Chunk Size

청크 사이즈는 디자인 할 때 중요한 요소 중 하나이다. 기본으로 64MB를 설정한다. 각 청크 복사본은 plain Linux file의 모습으로 저장이 된다. lazy space allocation은 internal fragmentation에 의해 생길 수 있는 공간 낭비를 줄여준다. 큰 청크 사이즈는 다음과 같은 장점이 있다. 1. 클라이언트가 마스터와 통신하는 일을 줄여준다. 왜냐하면 같은 청크 안에서의 읽기나 쓰기는 마스터에게 다시 요청할 필요가 없기 때문이다. 작은 랜덤 읽기의 경우에도 클라이언트가 청크 위치 정보를 캐싱할 수 있다. 2. 클라이언트가 주어진 청크에서 많은 작업을 할 수 있고 이건 네트워크 오버헤드를 줄여준다. TCP 연결을 계속 유지함으로써. 3. 마스터가 저장하는 메타데이터의 크기를 줄여준다. 반면 단점도 있다. 작은 파일은 작은 수의 청크로 구성되어 있다. 그렇게 되면 이 청크 하나에 많은 클라이언트가 접근하려 할 수 있으므로 hot spot이 될 수 있다. 이런 경우는 더 많은 복사본을 만듦으로써 보완할 수 있다.

2.6 Metadata

마스터는 크게 세 가지의 메타데이터를 저장한다. 파일과 청크의 네임스페이스, 파일이 청크로 매핑되는 것, 각 청크 복사본의 위치이다. 모든 메타데이터는 마스터의 메모리에 저장된다. 처음 두 데이터는 변한 내용이 operation log에 로깅된다. 이 로그는 마스터의 로컬 디스크에 있고 remote machine에 복제된다. 반면 청크 위치 정보는 persistently 저장하지 않는다. 대신 청크서버에게 청크 정보를 물어본다. 물어보는 때는 마스터가 시작할 때나 새로운 청크서버가 클러스터에 들어올 때이다.

2.6.1 In-Memory Data Structures

인메모리로 관리되기 때문에 마스터의 반응이 빠르고 백그라운드에서 전체를 점검하기 효율적이다. 이런 memory-only 접근을 쓸 때 유의할 점은 청크의 갯수, 즉 전체 시스템의 capacity가 마스터가 갖는 메모리에 의해 제한 될 수 있다는 것이다. 하지만 각 64MB 청크마다 마스터는 64bytes 이하를 쓰기 때문에 큰 문제가 되지 않는다.

2.6.2 Chunk Locations

마스터는 어떤 청크의 복제본이 어느 청크서버에 있는지에 대해 persistent record를 갖지 않는다. 처음 시작할 때 정보를 받고 그 뒤에 주기적은 heartbeat으로 청크서버를 모니터링한다. Persistently 정보를 갖게 하려고 했지만 그냥 맨 처음에 받고 그 다음에 주기적으로 정보를 받는 게 간단해서 그렇게 구현을 했다. 이렇게 함으로써 청크서버들과 마스터가 동기화돼있게 할 수 있다.

2.6.3 Operation Log

Operation log는 중요한 메타데이터의 변화를 기록한다. 파일과 청크는 만들어진 logical time에 의해 구분된다. Operation log는 중요하기 때문에 다른 원격 장치에 복사한다. 마스터는 operation log를 통해서 파일 시스템을 복구할 수 있다. 그 시간을 단축시키기 위해서는 로그의 크기를 작게 유지해야한다. 마스터는 로그가 특정 사이즈를 넘으면 체크포인트를 해서 복구할 때 가장 최근의 체크포인트를 로컬 디스크에서 로딩한다. 이 기록은 메모리에 직접 저장할 수 있는 B-tree 형태로 저장되어 추가적인 작업 없이도 네임스페이스 검색에 이용될 수 있다. 복구할 때 가장 최근의 complete한 체크포인트만 필요하고 그 전의 체크포인트는 지워도 되지만 만일에 대비해서 몇 개는 유지한다.

2.7 Consistency Model

2.7.1 Guarantees by GFS

파일 네임스페이스의 변경은 atomic하다. 마스터에 의해서만 관리된다. 마스터의 operation log가 이런 작업들의 순서를 정의한다. File region은 모든 클라이언트가 어떤 복제본을 읽든 항상 같은 데이터를 얻는다면 consistent하다. 파일 데이터 변화 이후에도 consistent하고 클라이언트가 어떤 쓰기 변화가 있는지 본다면 defined하다. 데이터 변화라는 건 write나 record append가 있을 수 있다. write는 애플리케이션 특정의 파일에 데이터가 쓰여지는 것이다. record append는 concurrent한 변화가 있어도 최소 한 번 atomically append하는 것이다. 연속으로 성공적인 변화를 하고 나면 변화된 파일 리전은 defined하다고 보장될 수 있고 가장 마지막 변화로 쓰인 데이터를 갖고 있다. GFS는 변화를 복제본에 같은 순서로 적용함으로써, 그리고 청크 버전 번호를 이용해서 어떤 복제본이 stale한 지를 찾아냄으로써 위와 같은 보장을 할 수 있다. stale 청크는 클라이언트가 요청해도 제공되지 않고 garbage collected된다. 마스터와 모든 청크서버가 통신하면서 checksumming으로 데이터 결함을 찾아낸다. 문제가 생기면 데이터는 믿을만한 복제본으로부터 복구된다.

2.7.2 Implications for Applications

3. System Interactions

3.1 Leases and Mutation Order

뮤테이션은 모든 복제본에서 실행된다. 복제본들에서 일정한 mutation 순서를 유지하기 위해 lease를 사용한다. 마스터가 primary라고 불리는 하나의 복제본에 청크 리스를 준다. 프라이머리가 뮤테이션 순서를 고르고 모든 복제본은 이 순서를 따른다. 리스 메커니즘은 마스터의 오버헤드를 줄여주기 위해 만들어졌다. figure2. 1. 어떤 청크서버가 지금 lease를 갖고 있는지 클라이언트가 마스터에게 묻는다. 아무도 없으면 마스터는 하나를 고른다. 2. 마스터는 프라이머리와 다른 복제본의 identity를 알려준다. 클라이언트는 이 데이터를 캐싱한다. 프라이머리가 접근이 안 되거나 더이상 리스를 갖고 있지 않을 때만 다시 마스터와 통신한다. 3. 클라이언트가 모든 복제본에 데이터를 푸쉬한다. 4. 모든 복제본이 데이터를 받게 되면 클라이언트는 쓰기 요청을 프라이머리에게 한다. 프라이머리는 순서대로 뮤테이션을 적용한다. (이게 여러 요청이 왔을 때 그 요청들을 어떤 순서대로 적용할지를 정한다는 건가)5. 프라이머리는 쓰기 요청을 모든 복제본에게 전달한다. 복제본은 프라이머리가 정한 순서대로 진행한다. 6. 작업이 끝나면 프라이머리에게 끝났다고 알려준다. 7. 프라이머리는 클라이언트에게 완료됐음을 알려준다.

3.2 Data Flow

각 머신의 네트워크 대역폭을 최대한 활용하기 위해 데이터는 linearly 푸쉬된다. 트리나 다른 형태가 아니라. 네트워크 병목현상이나 high latency link를 최대한 막기 위해서 각 머신은 데이터를 가장 가까운 머신에게 전달한다. 여러 머신에게 전달 할 때 가까운 머신부터 전달한다. TCP를 통한 데이터 전송을 파이프라이닝 함으로써 지연시간을 줄인다.

3.3 Atomic Record Appends

이전의 write는 클라이언트가 데이터가 쓰여질 오프셋을 정했다. 같은 region에 동시에 쓰여지는 것이 serializable하지 않았다. 그 리전은 여러 클라이언트에 의한 데이터 프래그먼트를 가질 것이다. 하지만 record append는 클라이언트는 데이터만 정한다. 그러면 GFS가 그 데이터를 파일에 추가한다. 그러고 그 오프셋을 클라이언트에게 알려준다.

3.4 Snapshot

스냅샷은 파일이나 디렉토리 트리의 복사본을 만든다. 마스터가 스냅샷 요청을 받게 되면 먼저 outstanding lease를 revoke한다. 이렇게 하면 어떠한 연속된 쓰기도 lease holder를 찾기 위해 마스터와 교류를 해야 한다. 이렇게 하면 마스터가 새로운 카피를 만들 수 있도록 한다. 리스가 revoke되거나 만료되면 마스터는 디스크에 작업을 로깅한다. 그러고는 이 로그를 인메모리 상태에 기록한다.

4. Master Operation

마스터는 모든 네임스페이스 작업을 실행한다. 그리고 청크 복제본을 관리한다.

4.1 Namespace Management and Locking

다양한 작업들이 실행될 수 있고 proper serialization을 위해 락을 이용한다. GFS는 per-directory 자료 구조를 갖지 않는다.

4.2 Replica Placement

Cunk replica placement policy는 두 가지 목적이 있다. data reliability와 availability를 높이는 것과, 네트워크 대역폭 활용을 최대화하는 것이다. 이렇게 하기 위해서는 단순히 머신들에 복제본을 나누는 것이 아니라 rack들에 뿌려야 한다.

4.3 Creation, Re-replication, Rebalancing

청크 복제본은 세 가지 이유로 만들어진다. 청크 생성, 재복사, rebalancing.

마스터가 청크를 만들 때 처음에 빈 복제본을 어디에 둘 지 정한다. 이 대 고려할 점은, 1. 디스크 사용량이 낮은 청크서버에 새 복제본을 둔다. 2. 각 청크서버마다 최근 생성 수를 제한한다. 3. rack들에 걸쳐서 복제본을 뿌린다.

사용 가능한 복제본의 수가 어떤 수 이하로 줄어들면 마스터는 re-replicate한다. 가장 우선 순위가 높은 청크를 골라서 청크서버에게 복사하도록 한다.
마스터는 주기적으로 복제본을 rebalancing 한다. 복제본이 어떻게 퍼져있는지를 확인한 뒤 복제본을 더 나은 디스크로 옮겨서 로드밸런싱을 한다.

4.4 Garbage Collection

4.4.1 Mechanism

애플리케이션이 파일을 지우면 마스터는 이 로그를 남긴다. 파일은 삭제된 시간이 포함된 hidden name으로 renamed 된다. 마스터가 정기적으로 하는 파일 시스템 네임스페이스 스캔에서 3일 이상 지난 hidden file이 있으면 지운다. 그 전에는 계속 읽힐 수 있고 정상적인 이름으로 바뀜으로써 안 지워질 수 있다. hidden file이 지워지게 되면 인메모리메타데이터가 지워진다. 이와 비슷하게 마스터는 orphaned chunks도 찾는다. 고아 청크는 어떤 파일에게서도 접근이 안 되는 청크이다. 그러고는 메타데이터를 지운다. heartbeat로 각 처ㅇ커서버는 갖고 있는 청크를 보고하고 마스터는 마스터의 메타데이터에 없는 청크를 알려준다. 그러면 청크서버가 지운다.

4.4.2 Discussion

4.5 Stale Replica Detection

청크서버가 다운되고 그 사이 수정이 일어나게 되면 청크 복제본이 stale될 수 있다. 각 청크마다 마스터는 청크 버전 번호를 갖고 있어서 최신인지 stale인지 알 수 있다. 마스터가 리스를 줄 때 마다 청크 버전 번호를 증가시켜서 최신 복제본임을 알려준다. 마스터는 regular garbage collection 때 stale replica를 제거한다.

5. Fault Tolerance and Diagnosis

5.1 High Availability

5.1.1 Fast Recovory

마스터와 청크서버는 상태를 복구하고 시작하는 데에 몇초만 걸린다.

5.1.2 Chunk Replication

청크는 다른 청크서버에 다른 rack에 복제된다.

5.1.3 Master Replication

마스터 상태가 복제된다. Operation log와 checkpoints가 다수의 머신에 복제된다. shadow master가 primary master가 다운됐을 때 read-only access를 제공할 수 있다. 별로 바뀌지 않는 파일이나 살짝 stale돼도 괜찮다는 애플리케이션에게 제공할 수 있다. shadow master도 operation log의 복제본을 읽어서 프라이머리가 하듯 자기의 데이터 구조에 변화를 준다. 프라이머리처럼 시작할 때 청크서버에게 poll하고 그 뒤로는 자주 하지 않지만 청크 복제본과 통신하면서 모니터링한다.

5.2 Data Integrity

각 청크서버는 저장된 데이터의 corruption을 탐지하기 위해 checksumming을 사용한다. 청크는 32비트 체크섬을 갖고 있다. 다른 메타데이터처럼 처크섬도 인메모리에 저장되고 유저 데이터와 별도로 저장된다. 읽기 작업이 오면 청크서버는 체크섬을 확인한다. 만약 체크섬에서 오류가 있다면 청크서버는 에러를 반환하고 마스터에게 알려준다. 그러면 요청자는 다른 복제본에서 읽을 것이고 마스터는 다른 복제본을 복사할 것이다. 그 뒤에는 mismatch가 일어난 복제본을 지우라고 청크서버에게 지시한다.

9. Conclusion

전통적인 파일 시스템 관점으로 보지 않고 새로운 시각으로 봤다. component failure을 일반적인 현상으로 봤다. 큰 파일에 대해 최적화를 했다.

fault tolerance를 제공한다. 모니터링과, 중요 데이터 복제와, 빠르고 자동화된 복구를 통해서.