Google File System 리뷰

요즘 GFS 논문을 읽어보고 있다. 흥미롭지만 어려워서 여러번 반복해서 읽으면서 정리를 해보고 있다. 아직 이해 제대로 못한 부분이 많지만 부족하게라도 일단 글을 발행해야겠다. 

 

현재 시점에서 가장 인상 깊은 점은 두가지이다.

 

1. 대부분의 'Operation이 Master의 오버헤드를 줄이는 방향으로 설계되었다'
2. Relaxed Consistency Model에서 Consistency/InConsistency와 Defined/Undefined의 개념을 구분했다.

이 외에도 Single Master에서 모든 Metadata를 메모리로 관리하는 점, GFS를 사용하는 Application Level에서 Write를 하고 Rename을 하도록 권장하고 있는데 알고보니 일반적인 파일 다운로드에서도 수행되고 있는 연산인 점, Distributed Lock Manager 없이 Lease의 개념을 도입해서 Consistency Model을 달성한 점이 재미있다.

아래는 아직 해결하지 못한, 애매하게 알고 있는 개념들이다. 그리고 더 아래에는 GFS를 읽으면서 정리한 내용이 아직 draft 상태로 정리되어 있다.

내일 출근길에 마저 읽고 정리해봐야겠다. 후

 

Question

동일 chunk에 대한 추가 read는 캐시 유효 기간이 지나거나 파일이 다시 열릴 때까지 master와의 상호작용 없이 수행됩니다.

• 파일이 다시 열릴 때는 왜 Client Side의 Chunk Index Cache가 만료될까?

master는 64 MB chunk당 64 bytes 미만의 metadata만 유지하며, 파일 이름은 prefix compression으로 저장되어 파일당 64 bytes 미만의 메모리를 차지합니다.

• prefix compression이 뭐지?

client가 캐시된 replica 위치로 stale replica에 접근할 수 있는 창이 있으나, cache 만료 또는 파일 재오픈 시 새 위치를 받아 consistency가 회복됩니다. append-only 파일은 stale replica가 premature end-of-chunk만 반환해 outdated data를 거의 노출하지 않습니다.

• 부족한 데이터를 반환하는게 왜 문제가 안되지? 그리고 lease에 의해서 ordered replica로 동작하면 stale replica는 어떻게 발생하고 대응되는거지? write 연산은 어떻게 되는거지?

record append의 at-least-once semantics는 각 writer의 출력을 보존합니다

master는 때때로 lease가 만료되기 전에 취소를 시도할 수 있다(예: 파일이 rename되는 동안 mutation을 중단하고 싶을 때).

가정

• 친숙한 파일 시스템 인터페이스를 제공함
  • create, delete, open, close, read, write
• POSIX 같은 표준 API는 구현하지 않음
• snapshot : 낮은 비용으로 디렉터리 트리를 복사함
• mutation = write or record append
• record append : 여러 클라이언트가 동시에 같은 파일에 데이터를 Append 할 때, 각 클라이언트의 Append를 Atomic하게 보장함
  • 추가적인 locking 없이 여러 클라이언트가 동시에 Append를 할 수 있음

Architecture

• GFS 클러스터는 Single Mater와 Multi Chunk Server로 구성됨
• 여러개의 Client가 GFS 클러스터에 접근할 수 있음
• Client
  • 각 애플리케이션에서 파일 시스템 API를 구현함
  • master와 chunkserver에 메타데이터 및 데이터 작업을 요청함
  • POSIX API를 제공하지 않아서 Linux vnode 레이어와 연동할 필요가 없음
  • Metadata 연산은 Mater와 수행함
  • Data 연산은 Chunk Server와 수행함
  • Metadat는 캐싱하지만, Chunk 데이터는 캐싱하지 않음
• Master
  • 하나의 File이 여러개의 Chunk로 나누어지고, 각 Chunk마다 64bit의 Chunk Handle로 식별할 수 있음
  • 모든 파일 시스템의 Metadata를 메모리에 관리함
• Metadata
  • File Namesapce
    • File Namespace 별로 다른 Replication Level을 지정할 수 있음
  • Access Control
  • File To Chunk Mapping
  • Chunk Location 관리
  • Chunk Lease 관리
  • Orphan Chunk GC
  • Chunk Migration
  • HeartBeat : 모든 ChunkServer와 통신하여 상태를 수집하고 명령을 전달함
• Chunk Server
  • Chunk를 Linux File로 저장함
  • Chunk Handle + Byte Range를 전달받아서 데이터를 Read, Write를 수행함
  • 데이터를 Linux File에 저장하므로 Linux Buffer Cache가 자주 접근되는 데이터를 메모리에 유지함
    • Assumption에서 동일한 파일에 대한 Heavy Operation이 가정됨
• Chunk
  • 각 File은 Fixed Size Chunk로 분할됨
  • 각 Chunk는 여러개의 Chunk Server에 Replication 되어 저장됨 (default replica size 3)

Single Master

• 단 하나의 Master만 존재함
• 모든 Metadata 정보를 메모리에 관리하여 빠른 연산을 수행함
• Read/Write의 과정에서 개입을 최소화하여 병목이 되지 않아야 함
• Client로부터 FileName, Chunk Index를 전달받아서 Chunk Handle, Chunk Replica의 위치를 응답함
  • Chunk Index : Fixed Chunk Size를 사용해서 Client가 직접 계산함
• Client로부터 여러개의 Chunk에 대한 정보를 요청받아서 Client와 Master 사이의 연산을 최소화할 수 있음

1. Client : FileSize, Fixed Chunk Size로 ChunkIndex를 계산
2. Client -> Master : FileSize, Chunk Index 전달
3. Master -> Client : Chunk Handle, Chunk Replica Location 반환
4. Client : 전달받은 정보를 Caching (캐시 유효 기간이 끝나거나, 파일이 다시 열릴 때까지)
5. Client -> Chunk Server : 가장 가까운* Chunk Server에게 Chunk Handle, Byte Ranage를 전달해서 Read/Write
   • 가장 가까운 : TODO

Chunk Size

• 64MB의 고정된 사이즈 : 전통적인 파일 시스템의 사이즈보다 배우 큰 사이즈
• 장점
  • 동일한 Chunk에 대한 Read/Write를 수행할 때 최초 한번만 Master와의 상호작용을 하게 됨. 대부분의 요청이 대용량 파일에 대한 순사 처리이기 때문에 특히 효율적임
  • 같은 Chunk에서 다수의 연산이 수행될 가능성이 높아서, ChunkServer와 TCP 연결을 장시간 유지함으로써 네트워크 오버헤드를 줄일 수 있음
  • Master에서 관리해야하는 Metadata의 갯수가 줄어들어서 Master에서 사용해야하는 메모리의 사이즈가 감소하는 영향이 있음
• 단점
  • 작은 파일은 하나의 Chunk로 구성될 수 있음. 이때 이 Chunk를 가지고 있는 Chunk Server가 HotSpot이 될 수 있음.
• 사례
  • GFS가 Batch Queue System으로 사용되는 경우, 동일한 Executable에 대해서 수백개의 Client가 Read 요청을 할 때 하나의 Chunk Server로 요청이 몰리는 현상이 발생함
• 대응
  • 해당 Executable에 대한 Replication의 갯수를 늘리고, Batch 시작 시간은 Stagger하도록 변경

Metadata

• 주요 Metadata 3가지
  1. File 및 Chunk Namespace
  2. File - Chunk Mapping
  3. 각 Chunk Replica Location
• 모든 Metadata를 Memory에서 관리함
• 처음 2가지는 Local Disk + Operation Log에 저장되고 원격 머신에 복제되어 영속성 및 일관성을 보장함
  • 원격 머신에 복제 : Single Master라고 했지만, Metadata 연산에 참여하는 것은 Single Master이고 가용성을 위해서 Master도 Replica로 존재하는 듯함
• Chunk Replica Location은 Chunk Server에게 질의해서 최신 정보를 조회함 (Master가 시작할 때, Chunk Server가 추가/삭제될 때)
• In-Memory Data Structure
  • 모든 Metadata를 메모리에 관리하므로 master의 작업이 빠름
  • 주기적으로 Chunk의 상태를 스캔해서 Chunk GC를 수행할 수 있음
  • Chunk Server의 장애시, Chunk Re-Replication을 수행할 수 있음
  • Load, Disk의 균형을 위해서 Chunk Migration을 수행할 수 있음
  • 단점
    • 메모리 사용량이 시스템 용량을 제한할 수 있음
    • 하지만 Chunk Size 64 MB 당 Metadata는 64 Bit미만이고, FileName은 Prefix Compression으로 저장되어 파일당 64 Bytes 미만의 메모리를 차지함
    • 필요하다면 Master 메모리를 추가하는 비용은 단순함, 신뢰성, 성능, 유연성을 고려할 때 합당한 대가로 판단됨
• Chunk Location
  • Master는 어떤 Chunk Server가 특정 Chunk Replica를 가지고 있는지 저장하지 않음 (Metadata의 3번째 항목)
  • Master의 시작, Chunk Server의 추가/삭제에서 HeartBeat 메시지로 Chunk Placement를 제어하여 최신 정보를 유지함
  • 실제로 Chunk Server가 갖고 있는 최종 정보는 해당 서버만 알기 때문에, Master가 이를 일관되게 유지하려는 시도는 불필요함

Operation Log

• Metadata의 영속적인 기록이고, 동시 작업의 순서를 정의하는 Logical Time의 역할을 수행함
  • Logical Time
    • 작업의 선후순서만을 보장하는 Time, 각 Operation과 그 사이의 시간을 측정하지 않음
    • File, Chunk, Version에 따라서 unique하게 부여됨
• Operation Log가 특히 중요하기 때문에 Local Disk, 원격 Disk에 모두 Flush한 뒤, Client의 요청을 처리함
• 여러개의 Record를 묶어서 Flush하여 성능 영향을 최소화 함
• Checkpoint
  • 복구의 과정은 checkpoint와 이후의 log 파일 상태만 재생해서 빠르게 복구할 수 있음
  • 별도의 쓰레드에서 여러개의 Record를 묶어서 Checkpoint를 생성하여 incoming mutation을 지연시키지 않음.
  • 수백만 파일 규모에서도 수 분 이내에 완료됨
  • 불완전한 checkpoint는 복구 과정에서 자동으로 무시됨

Consistency Model

• Relaxed Consistency Model

Gurantees by GFS

- File Namespace 변경 (파일 생성) : Atomic, Master가 Namespace Locking으로 일관성을 보장함. Operation Log가 global하게 순서를 정의함
- Data Mutation : mutation 유형, 성공 여부, 동시성 상황에 따라서 달라짐
    - A file region is consistent if all clients will always see the same data, regardless of which replicas they read from. 
    - A region is defined after a file data mutation if it is consistent and clients will see what the mutation writes in its entirety
    - Defined : 모든 클라이언트가 동일한 데이터를 읽음
    - 여러개의 Mutation이 동시에 성공하면 undefined  but consistent 상태가 됨
    - 실패한 Mutation은 inconsistent 상태로 만듦
- Write : 지정한 offset에 데이터를 저장함
- Append : Client가 아닌 GFS가 선택한 offset에 데이터를 Atomic하게 Append하고 Offset을 반환함
    - Record가 Chunk의 끝을 넘는 경우 Padding이 추가될 수 있음
    - 일부 Replica에 대해서 append가 실패하는 경우, 동일한 Record가 중복되어서 저장될 수 있음
- Defined = Consistency가 2가지 요소로 만족됨 
    - 모든 Replica에 대해서 동일한 순서대로 Mutation을 적용함
    - Chunk Version Number로 오래된Stale Replica를 배제함

Stale Replica // TODO

- Client의 요청에서 제외되고, Chunk GC에서 제거됨
- Client에 캐싱된 Chunk Handle에 Stale Replica가 포함된 경우, Cache 만료 또는 File 재오픈할 때 consistency가 회복됨
- Stale Replica가 가지고 있는 Chunk Version Number는 정상 Replica보다 작아서 Master에서 반환하는 Replica에서 제외됨
- Stale Replica의 경우 오래된 Offset을 가지고 있어서 premature end-of-chunk만을 반환하고, 오래된 데이터를 잘못 제공하지는 않음

Lease and Mutation Order

• mutation은 write, append operation과 같이 chunk의 내용 또는 metadata의 내용을 변경하는 연산
• 각 mutation은 해당 chunk의 모든 replica엑서 수행됨
• replica 사이의 일관된 mutation 순서를 보장하기 위해 lease의 개념을 사용함
• master는 replica 중 하나를 chunk lease로 지정하고 primary 라고 부름
• primary는 chunk에 대한 모든 mutation에 대한 순서를 지정하고, 모든 replica는 이 순서에 따라서 mutation이 수행됨
• 따라서 global mutation의 순서는 MAster가 부여한 Lease의 순서에 따라서 수행되고, 각 Mutation에 대한 순서는 primary가 할당한 순서에 따라서 결정됨

Lease 메커니즘

• master의 관리 오버헤드를 최소화하기 위해서 설계됨
• lease의 초기 timeout = 60초. 단, chunk가 계속해서 변형되는 한 primary는 master로부터 lease를 연장해서 계속 사용할 수 있음. 이 과정은 Master, Chunk Server 사이의 Heart Beat를 통해서 처리됨
• master와 primary가 통신이 끊어져도 lease가 안료된 이후에 안전하게 다른 replica에 새 lease를 부여할 수 있음

1. Client -> Master : Lease를 보유한 Chunk Server와 다른 Replica의 위치 정보를 조회
2. Master -> Client : Master는 Lease가 없을 때 생성해서 응답함. Primary ID, Secondary Replica의 위치를 응답
3. Client : 이 정보를 캐싱하여 primary가 unreachable하거나 더이상 lease를 보유하지 않는다고 응답할 때까지 master와 다시 통신하지 않음
4. Client -> Chunk Server : 모든 Replica에 데이터에 ID를 부여하고 Push. Primary가 정의한 순서와는 무관하게 데이터를 전송
5. Chunk Server -> Client : LRU Buffer Cache에 데이터를 보관. 데이터를 수신함을 ACK
6. Client -> Primary : 모든 Replica가 ACK을 보내면 Primary에게 데이터 ID와 함께 Write 요청을 전송
7. Primary -> Secondary : 모든 Write 요청을 정의한 순서에 따라서 Secondary에게 전달
8. Secondary -> Primary : ACK
9. Primary -> Client : 최종 응답을 전송

• 에러가 발생하는 경우 4~8의 과정을 retry하고 필요하면 전체 과정을 retry
• 만약 어플리케이션의 Write 연산이 대용량이거나 Chunk 사이즈를 넘는 경우, 여러개의 Write로 분할됨.
• 여러개의 Client들의 동시성 연산에 의해서 섞이거나 덮어써질 수 있음.
• 하지만 모든 Replica에는 동일한 연산이 적용되어서 undefined이지만 consistency가 보장될 수 있음

Data Flow

• data flow가 control flow와 분리되어 네트워크를 효율적으로 사용할 수 있음
• 목표 : 머신 전체의 네트워크 대역폭을 활용하고, 병목 및 높은 대기 구간을 피하고, 모든 데이터를 전달하는게 걸리는 지연 시간을 최소화하는 것
• 각 머신의 full outbount 대역폭을 활용하기 위해서 데이터는 tree가 아닌 chain 형태로 전달됨
• 네트워크 병목과 높은 대기 구간을 피하기 위해서 각 머신은 가직 데이터를 수신하지 않은 가장 가까운 머신에 데이터를 전달함
  • client가 serve 1~4에 데이터를 보낼 때 client -> s1 -> s2 -> s3 -> s4 순서대로 전달함
  • IP 주소로부터 토폴로지 상의 거리를 추정할 수 있음
• TCP 연결을 파이프라이닝하여 latency를 낮춤. chunk sever는 데이터를 받으면 곧바로 다음 머신으로 전달을 시작함
  • B 바이트를 R개의 Replica에 대해서 전송할 때 B 바이트 / T 네트워크 처리량 + R 리플리카 수 * L 머신 간 대기 전송 시간만큼이 걸림

Atomic Record Append

• GFS는 Record Append라는 Atomic Append를 제공함
• Write에서는 Offset을 Client가 지정하지만, concurrent write에서는 간섭이 발생해서 offset 사이에 영역이 섞일 수 있음
• Record Append에서는 Client가 데이터를 작성하면 GFS가 자차적으로 선택한 Offset에 Atomic하게 최소 한 번 이상 Append하고, 그 offset을 반환함
• 분산 환경에서 여러 Client가 동일한 파일에 Append를 하는 경우, 분산 락 Manager가 필요하지만, Record Appender에서는 primary에서 약간의 로직만 추가해서 이를 해결한다
• Client가 Chunk에 대한 Append를 Primary에게 요청할 때, Primary는 현재 Chunk가 최대 크기를 넘지 않는지 확인한다
• 넘는다면 현재 chunk를 padding하고 secondary에게도 padding을 지시한다. 그리고 그 다음 append를 실행한다.
• Record의 크기를 Chunk의 최대 1/4 사이즈로 제안하여 디스크 fragmentation을 최소화한다.
• Record가 MAX를 넘지 않으면 Secondary에게까지 Append하고 Offset을 전달한다

Primary가 모든 Replica에 대해서 동일한 Offset을 보장함으로서 Atomic한 연산을 보장하게 된다.
중복된 레코드가 남아서 inconsistency한 영역이 생기거나 offset이 record의 길이만큼 늘어나지 않을 수는 있다.
하지만 이 부분은 Application 레벨에서 Checksum, UniqueID를 사용해서 검증할 수 있으므로 Defined Region의 개념에는 어긋나지 않는다.

Implications for Applications

• Checkpoint : 지금까지 성공적으로 파일에 데이터를 Write한 Offset
• 애플리케이션이 중간에 실패해도 Checkpoint 이후부터 다시 쓰면 됨
• Checkpoint까지만 읽으면 됨
• CheckSum : CheckPoint 별로 현재까지 데이터로 만든 CheckSum을 저장해둔다
• Atomic Rename : 멀티파트 Write를 할 때 mv /tmp/data.part /data/finalname 처럼 atomic rename
• 대부분 애플리케이션은 overwrite 대신 append 방식으로 파일을 생성·수정합니다. writer는 처음부터 끝까지 파일을 작성한 뒤, atomic rename으로 영구 이름을 부여하거나 주기적으로 checkpoint를 기록합니다. checkpoint에는 애플리케이션 수준 checksum도 포함될 수 있습니다. reader는 정의된 상태가 보장된 마지막 checkpoint까지의 데이터만 처리합니다. 이 방식은 append가 random write보다 효율적이고, 실패에 더 강건하다는 장점이 있습니다. checkpoint는 writer 재시작을 용이하게 하고, reader가 incomplete 데이터를 읽지 않도록 합니다.
• 또 다른 전형적 사용은 다수의 writer가 병렬로 append해 merge 결과나 queue를 구성하는 경우입니다. record append의 at-least-once semantics는 각 writer의 출력을 보존합니다. reader는 checksums 기반으로 padding과 중복 record를 식별·제거하며, idempotency가 필요한 경우 record 내부의 unique identifier로 필터링할 수 있습니다. 이러한 record I/O 기능은 Google 내부 라이브러리 코드로 제공되어, 다른 파일 인터페이스 구현에서도 활용됩니다. 이로써 희소한 중복을 제외하면 동일한 record 시퀀스가 항상 전달됩니다