[논문 리뷰] The Google File System(GFS) (1)

“The Google File System” 논문을 개인 공부 및 리뷰를 위해 쓴 글입니다.
분산 파일 시스템에 입문하시거나 관련 논문을 처음 보는 분을 위해 용어 설명도 덧붙였습니다.
또한, GFS의 모든 것을 알기 위해 최대한 요약없이 논문 내용을 담았습니다.
논문 출처 : https://dl.acm.org/doi/10.1145/1165389.945450

1. Introduction

• Google File System(GFS)는 구글의 데이터 처리 요구 사항의 급증하는 요구를 충족하기 위해 설계되고 구현되었다.
• GFS는 성능(performance), 확장성(scalability), 신뢰성(reliability), 가용성(availability)같은 이전의 분산 파일 시스템의 같은 목표들을 공유한다.
• 하지만, 구글은 이런 기존 특징들을 재검토하고 다른 관점에서 보고 있다.

1. 컴포넌트 고장은 예외라기보다는 표준이다.
   • 컴포넌트(component) : 여러 개의 프로그램 함수들을 모아 하나의 특정한 기능을 수행할 수 있도록 구성한 작은 기능적 단위 ¹
   • 지속적인 모니터링, 에러 감지, 장애 허용(fault tolerance), 자동 복구는 시스템에 통합되어야 한다.
2. 파일은 멀티 GB 파일이 흔한 것처럼 크다.
   • 설계 가정과 I/O 동작(operation), 블록 크기같은 파라미터들은 다시 재검토되어야 한다.
3. 대부분 파일들은 기존 데이터를 덮어쓰기보다는 데이터 스트림, 아카이브 데이터 등 새로운 데이터를 추가함으로써 변형된다(mutated).
   • 대용량 파일에 대한 이러한 액세스 패턴을 고려할 때 추가(append)는 성능 최적화와 원자성 보장의 초점이 되는 반면 클라이언트의 데이터 블록 캐싱은 매력을 잃는다.
4. 애플리케이션과 파일 시스템 API를 같이 설계하면 유연성(flexibility)을 높여 전체 시스템에 도움이 된다.
   • GFS의 일관성 모델을 완화하여 애플리케이션에 부담을 주지 않으면서 파일 시스템을 간소화했다.
   • 클라이언트가 별도의 동기화 없이 파일에 동시에 추가할 수 있도록 atomic append 동작을 도입했다.
   • API(Application Programming Interface) : 애플리케이션에서 사용할 수 있도록 운영 체제나 프로그래밍 언어가 제공하는 기능을 제어할 수 있게 만든 인터페이스 ²

2. Design Overview

2.1 Assumptions

• 다음은 저자들이 몇가지 가정들을 세운 것들이다.

1. 시스템은 종종 고장나는 많은 저렴한 상품 컴포넌트들로 구축된다. 지속적으로 모니터링하여 컴포넌트 고장을 감지(detect), 허용(tolerate) 및 신속하게 복구해야 한다.
2. 멀티 GB 파일이 일반적인 경우이므로 이를 효율적으로 관리해야 한다.
3. 워크로드(workload)는 주로 큰 스트리밍 읽기와 작은 랜덤 읽기, 두 가지 종류의 읽기로 구성된다.
   • 워크로드(workload) : 주어진 기간에 시스템에 의해 실행되어야 할 작업의 할당량
4. 시스템은 동일한 파일에 동시에 추가되는 여러 클라이언트에 대해 잘 정의된 semantics을 효율적으로 구현해야 한다.
5. 낮은 지연 시간(latency)보다 높은 지속적인 대역폭(bandwidth)이 더 중요하다.

2.2 Interface

• GFS에서 파일은 디렉토리에서 계층적으로 구성되고 경로 이름(pathname)으로 식별된다.
  • create, delete, open, close, read, write 동작을 지원한다.
• GFS는 snapshot과 record append 동작을 가지고 있다.
  • 스냅샷(snapshot)은 파일 또는 디렉토리 트리의 복사본을 저렴한 비용으로 생성한다.
  • 레코드 추가(record append)를 사용하면 여러 클라이언트가 동일한 파일에 데이터를 동시에 추가할 수 있으며, 각 개별 클라이언트의 추가 데이터의 원자성을 보장할 수 있다.

2.3 Architecture

• GFS 클러스터는 단일 master와 다수의 chunkserver으로 구성되어 있고, 다수의 client들이 액세스한다.
  • 클러스터(cluster) : 여러 대의 컴퓨터들이 연결되어 하나의 시스템처럼 동작하는 컴퓨터들의 집합 ³
• 파일은 고정 크기 청크(fixed-size chunks)로 나뉜다.
  • 각 청크는 불변(immutable)하고 전역적(globally)으로 고유한 64 bit chunk handle에 의해 식별된다.
    • 청크 핸들은 청크를 생성할 때 마스터가 할당해준다.
• chunkserver는 로컬 디스크에 청크를 리눅스 파일로 저장하고 청크 핸들 및 바이트 범위에서 지정된 청크 데이터를 읽거나 쓴다.
  • 신뢰성을 위해 각 청크는 여러 청크 서버에 복제된다.
    • default : 3 복제본

• master는 모든 파일 시스템 메타데이터(metadata)를 유지 관리한다.
  • 여기에는 name space, access control information, 파일에서 청크로의 mapping 및 청크의 현재 위치가 포함된다.
  • 또한 chunk lease management, 청크 서버 간 청크 마이그레이션과 같은 시스템 전반의 작업도 제어한다.
• master는 HeartBeat 메시지의 각 청크 서버와 주기적으로 통신하여 명령(instruction)을 제공하고 상태(state)를 수집한다.

• client는 메타데이터 작업을 위해 마스터와 상호 작용하지만 데이터를 포함한 모든 통신은 청크 서버로 직접 전달된다.
• 청크가 로컬 파일로 저장되기 때문에 청크 서버는 파일 데이터를 캐시할 필요가 없으며 리눅스의 버퍼 캐시는 이미 자주 액세스하는 데이터를 메모리에 보관한다.
  • 캐시(cache) : 데이터나 값을 미리 복사해 놓는 임시 장소 ⁴

2.4 Single Master

• 단일 마스터를 사용하면 설계가 크게 간소화되고 마스터가 글로벌 지식을 사용하여 정교한 청크 배치(chunk placement) 및 복제 결정(replication decision)을 내릴 수 있다.
• 클라이언트(client)는 어떤 청크 서버에 연결해야 하는지 마스터에게 묻는다.
• 이제 대략적인 과정을 살펴보자.
  • 클라이언트는 고정된 청크 크기를 사용하여 애플리케이션에서 지정한 파일 이름과 바이트 오프셋(offset)을 파일 내의 청크 인덱스로 변환한다.
    • 오프셋(offset) : 기준이 되는 주소에 더해진 값, 즉, 상대적인 값 ⁵
  • 그런 다음 파일 이름과 청크 인덱스가 포함된 요청을 마스터에 보낸다.
  • 마스터는 해당하는 청크 핸들과 복제본의 위치로 응답해준다.
  • 클라이언트는 (파일 이름, 청크 인덱스)를 키로 사용하여 이 정보를 캐시한다.
  • 클라이언트는 복제본 중 가장 가까운 복제본으로 요청을 보낸다.
    • 요청(request)은 청크 핸들 및 해당 청크 내의 바이트 범위를 지정한다.

2.5 Chunk Size

• 청크 크기는 주요 설계 파라미터 중 하나로, 64 MB로 선택했다.
• 각 청크 복제본은 청크 서버에 일반 리눅스 파일로 저장되며 필요한 경우에만 확장된다.

• 큰 청크 크기는 몇 가지 중요한 이점을 제공한다.

  1. 클라이언트가 마스터와 상호작용해야 할 필요성이 줄어드는데, 동일한 청크에 읽기 및 쓰기 작업이 청크 위치 정보를 위해 마스터에게 초기 요청이 한번만 필요하기 때문이다.
     • 애플리케이션이 대부분 대용량 파일을 순차적으로 읽고 쓰기 때문에 워크로드의 감소는 특히 중요하다.
  2. 큰 청크이기 때문에, 클라이언트는 주어진 청크에서 많은 작업을 수행할 수 있어, 오랜 시간 동안 청크 서버에 대한 지속적인 TCP 연결을 유지함으로써 네트워크 오버헤드를 줄일 수 있다.
     • 전송 제어 프로토콜(TCP) : 두 개의 호스트를 연결하고 데이터 스트림을 교환하게 해주는 네트워크 프로토콜 ⁶
     • 오버헤드(overhead) : 어떤 처리를 하기 위해 들어가는 간접적인 처리 시간, 메모리 등을 말함 ⁷
  3. 마스터에 저장된 메타데이터의 크기를 줄인다. 이를 통해 메타데이터를 메모리에 보관할 수 있다.

2.6 Metadata

• 마스터는 메타데이터의 3가지 주요 유형을 저장한다.
  1. file 및 chunk namespace
  2. 파일에서 청크로의 매핑(mapping)
  3. 각 청크 복제본의 location
• 모든 메타데이터는 마스터의 메모리에 저장된다.
• (1번 유형) file 및 chunk namespace, (2번 유형) 파일에서 청크로의 매핑은 마스터의 로컬 디스크에 저장되고 원격 시스템에 복제되는 작업 로그에 변형(mutation)을 기록함으로써 지속적으로(persistent) 유지된다.
  • 로그를 사용하면 마스터가 충돌 시 불일치의 위험 없이 단순하고 안정적으로 마스터 상태를 업데이트할 수 있다.
• 마스터는 청크 위치 정보를 지속적으로 저장하지 않는다. 대신, 마스터 시작할 때와 청크서버가 클러스터에 들어올 때마다 각 청크 서버에 청크를 묻는다.

2.6.1 In-Memory Data Structures

• 메타데이터가 메모리에 저장되기 때문에 마스터 작업이 빠르다.
• 또한 마스터는 백그라운드에서 전체 상태(state)를 주기적으로 스캔하는 것이 쉽고 효율적이다.
  • 주기적 검색은 청크 가비지(garbage) 수집, 청크 서버 장애 발생 시 재복제(re-replication), 청크 서버 간에 로드 및 디스크 공간 사용의 균형을 맞추기 위한 청크 마이그레이션을 구현하는 데 사용된다.
    • 마이그레이션(migration) : 대량의 데이터를 옮기는 프로세스를 말함 ⁸

2.6.2 Chunk Locations

• 마스터는 지정된 청크의 복제본이 있는 청크 서버에 대한 지속적인 기록을 보관하지 않는다.
• 시작 시 해당 정보를 위해 청크 서버를 폴링할 뿐이다.
  • 폴링(pooling) : 프로그램에 의한 입출력 방식. 데이터의 입출력이 CPU가 수행하는 프로그램의 입출력 명령에 의해 실행되고 입출력을 수행할 준비가 되었는지 알기 위해 CPU가 주변장치의 상태를 계속 감시한다. ⁹
• 마스터는 모든 청크 배치(chunk placement)를 제어하고 일반 HeartBeat 메시지로 청크 서버 상태를 모니터링하기 때문에 최신 상태를 계속 유지할 수 있다.

2.6.3 Operation Log

• 작업 로그는 중요한 메타데이터 변경 내역 기록이 포함되어 있는데 이것은 GFS의 중심 역할이다.
• 메타데이터의 유일한 지속적인 기록일 뿐만 아니라 동시 동작 순서를 정의하는 논리적 타임라인 역할을 한다.
  • 파일 및 청크와 해당 버전은 모두 고유하며 생성된 논리적 시간에 의해 지속적으로 식별된다.
• 작업 로그는 무척이나 중요하기 때문에 안정적으로 저장해야 한다. 따라서 이를 여러 원격 시스템에 복제하고 로컬 및 원격에서 해당 로그 레코드를 디스크에 플러시(flush)한 후에만 클라이언트 작업에 응답한다.
  • 플러시(flush) : 영속성 컨텍스트의 변경 내용을 DB에 반영하는 것을 말한다. ¹⁰
• 마스터는 플러시하기 전에 여러 로그 레코드를 일괄 처리하여 플러시 및 복제가 전체 시스템 처리량에 미치는 영향을 줄인다.
• 마스터는 로그가 특정 크기를 초과할 때마다 상태를 체크포인트(checkpoint)하므로 로컬 디스크에서 최신 체크포인트를 로드(load)한 후 제한된 수의 로그 레코드만 재생하여 복구할 수 있다.
  • 체크포인트(checkpoint)는 메모리에 직접 매핑되어 추가 파싱(parsing) 분석 없이 네임스페이스 검색에 사용할 수 있는 컴팩트한 B-트리(B-tree) 형식이다.
    • B-트리(B-tree) : 이진 트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조 ¹¹
  • 따라서 복구 속도가 더욱 빨라지고 가용성(availability)가 향상된다.

2.7 Consistency Model

• GFS는 고도로 분산된 애플리케이션을 잘 지원하지만 상대적으로 단순하고 효율적으로 구현하는 완화된 일관성 모델(relaxed consistency model)을 가지고 있다.
• GFS의 보증(guarantee)과 애플리케이션에 대한 의미가 무엇인지 논의해본다.

2.7.1 Guarantees by GFS

• 파일 네임스페이스 변형(ex. 파일 생성)은 원자성(atomic)을 지닌다.
• 네임스페이스 locking은 원자성과 정확성을 보장하며, 마스터의 작업 로그는 이러한 작업의 전체 순서를 정의한다.
• 데이터 변형 후 파일 영역의 상태는 변형의 유형, 성공 또는 실패 여부, 동시 변형이 있는지 여부에 따라 달라진다.
  • 위 Table 1은 그 결과를 요약한 것이다.
• 영역(region)은 파일 데이터 변형이 일관되면(consistent) 정의(defined)된다.
• 동시에 성공적인 변형은 영역이 정의되지 않았지만 일관되게 남는다. (consistent but undefined)
• 실패한 변형은 영역을 일관되지 않게 만든다.(inconsistent) 따라서 서로 다른 클라이언트는 서로 다른 시간에 서로 다른 데이터를 볼 수 있다.

• 데이터 변형은 writes이거나 record appends일 것이다.
• write는 데이터를 애플리케이션에서 지정한 파일 오프셋에 쓴다.
• record append는 데이터(“record”)가 동시 변형이 있는 경우에도 최소한 한 번 이상 원자적으로 추가되도록 하지만 GFS의 선택을 오프셋한다.

2.7.2 Implications for Applications

• GFS 애플리케이션은 이미 다른 목적에 필요한 몇 가지 간단한 기술을 사용하여 완화된 일관성 모델을 수용할 수 있다.
  • 덮어쓰기(overwrites), 체크포인트(checkpoint), 자기 확인(self-validation) 및 자기 식별(self-identifying) 기록 작성 대신 append에 의존한다.
• 실제로 모든 애플리케이션은 덮어쓰기가 아닌 append 작업을 통해 파일을 변형한다.
• 체크포인트에는 애플리케이션 수준 체크섬(checksum)도 포함될 수 있다.
• writer는 정의된 상태로 알려진 마지막 체크포인트까지의 파일 영역만 확인하고 처리한다.
• append는 랜덤 쓰기보다 훨씬 효율적이고 애플리케이션 장애에 더 탄력적이다.

3. System Interactions

The structure of the Google File System (GFS) 이미지출처 ¹²

• 저자들은 모든 작업에 대한 마스터의 참여를 최소화하도록 시스템을 설계했다.
• 이 배경을 바탕으로 클라이언트, 마스터 및 청크 서버가 데이터 변형, 원자 기록 추가 및 스냅샷을 구현하기 위해 상호 작용하는 방식을 설명한다.

3.1 Leases and Mutation Order

• 변형(mutation)은 쓰기 또는 추가 작업과 같은 청크의 내용이나 메타데이터를 변경하는 작업이다.
• 각 변형은 모든 청크의 복제본에서 수행된다.
• GFS는 복제를 통해 일관된 변형 순서를 유지하기 위해 리스(lease)를 사용한다.
  • 리스(lease) : 소유자에게 제한된 기간 동안 특정 자원에 대한 특정 권한을 부여하는 계약 ¹³

• 마스터는 복제본 중 하나에 청크 리스를 부여하며, 이를 primary라 한다.

  
  이미지출처 ¹⁴
  

  • primary : 쓰기 전용
  • secondary(replica) : 읽기 전용
• 전역 변형의 순서는 마스터가 선택한 리스 허가 순서에 의해 먼저 정의되며, 리스 내에서는 primary에 의해 할당된 일련 번호에 의해 정의된다.
• 리스 메커니즘은 마스터에서 관리 오버헤드를 최소화하도록 설계되었다.
• 리스의 초기 timeout은 60초이다. 그러나 청크가 변형되는 한 primary는 마스터로부터 무한하게 확장을 요청하고 일반적으로 수신할 수 있다.

• 다음 그림은 번호가 매겨진 단계들을 통해 쓰기(write)의 제어 흐름을 살펴볼 수 있다.

1. 클라이언트는 마스터에게 청크에 대한 현재 리스를 보유하고 있는 청크 서버와 다른 복제본의 위치를 묻는다. 리스가 없는 경우, 마스터는 선택한 표시되지 않은 복제본에 리스를 부여한다.
2. 마스터는 primary 복제본의 ID와 다른 secondary 복제본의 위치로 응답한다. 클라이언트는 향후 변형을 위해 이 데이터를 캐시한다. primary에 연결할 수 없거나 primary에 더 이상 리스가 없다고 응답할 경우에만 마스터에 다시 연락해야 한다.
3. 클라이언트가 데이터를 모든 복제본에 푸시한다. 각 청크 서버는 데이터가 사용되거나 만료될 때까지 내부 LRU(Least Recently Used) 버퍼 캐시에 데이터를 저장한다. data flow를 control flow에서 분리함으로써, 어떤 청크 서버가 primary인지 상관없이 네트워크 토폴로지를 기반으로 값비싼 data flow를 스케줄링함으로써 성능을 향상시킬 수 있다.
   • LRU(Least Recently Used) : 가장 오래전에 사용된 것은 디스크에 저장하고 메모리에는 가장 최근에 사용된 데이터를 저장함으로써, 디스크 I/O를 줄이고, 데이터베이스 시스템의 성능은 증가하도록 하는 관리 기법이다. ¹⁵
   • 스케줄링(scheduling) : 여러 프로세스가 번갈아가며 사용하는 자원을 어떤 시점에 어떤 프로세스에게 자원을 할당할지 결정하는 것이다. ¹⁶
4. 모든 복제본이 데이터 수신을 승인하면 클라이언트는 primary 복제본에 쓰기(write) 요청(request)을 보낸다. 요청은 모든 복제본에 이전에 푸시된 데이터를 식별한다. primary는 여러 클라이언트에서 수신하는 모든 변형에 연속 일련 번호를 할당하며, 필요한 일련 번호를 제공한다. 일련 번호 순서로 자신의 로컬 상태에 변형을 적용한다.
5. primary는 쓰기 요청을 모든 secondary 복제본으로 전달한다. 각 secondary 복제본은 primary 복제본에 의해 할당된 동일한 일련 번호 순서로 변형을 적용한다.
6. secondary들은 모두 작업을 완료했음을 primary에 응답한다.
7. primary가 클라이언트에 응답한다. 복제본에서 발생한 오류는 클라이언트에 보고된다. 클라이언트 요청이 실패한 것으로 간주되면 수정된 영역이 일관되지 않은(inconsistent) 상태로 유지된다. 클라이언트 코드는 실패한 변형을 재시도함으로써 오류를 처리한다.

• 애플리케이션에 의한 쓰기가 크거나 청크 경계에 걸쳐 있으면 GFS 클라이언트 코드는 여러 쓰기 작업으로 세분화한다. 이 과정은 모두 control flow을 따르지만, 다른 클라이언트의 동시 작업에 의해 인터리빙(interleaved)되고 덮어쓸 수 있다.
  • 인터러브(interleave) : 컴퓨터 하드디스크의 성능을 높이기 위해 데이터를 서로 인접하지 않게 배열하는 방식. (interleave : 교차로 배치하다) ¹⁷

3.2 Data Flow

• 네트워크를 효율적으로 사용하기 위해 data flow를 control flow에서 분리한다.
• 제어(control)이 클라이언트에서 primary 그리고 모든 secondary로 흐르는 동안 데이터는 파이프라인 방식으로 신중하게 선택된 청크 서버의 체인을 따라 선형적으로 푸시된다.
  • 데이터 파이프라인(data pipeline) : 다양한 데이터 소스에서 원시 데이터를 수집한 다음 분석을 위해 데이터 레이크 또는 데이터 웨어하우스와 같은 데이터 저장소로 이전하는 방법. (생성, 변환, 저장 등) ¹⁸
• GFS의 목표는 각 시스템의 네트워크 대역폭을 최대한 활용하고, 네트워크 병목 현상 및 지연 시간(latency)이 긴 링크를 방지하고, 지연 시간을 최소화하여 모든 데이터를 처리하는 것이다.
  • 각 시스템은 데이터를 수신하지 않은 네트워크 토폴로지의 가장 가까운 시스템으로 데이터를 전달한다.
  • TCP 연결을 통해 데이터 전송을 파이프라인화하여 지연 시간을 최소화한다.

3.3 Atomic Record Appends

• GFS는 레코드 추가(record append)라고 불리는 원자성 추가 작업(atomic append operation)을 제공한다.
• 기존 쓰기에서 클라이언트는 데이터가 기록될 오프셋을 지정한다.
  • 동일한 영역에 대한 동시 쓰기는 직렬화할 수 없다.
• 하지만, 레코드 추가(record append)에서 클라이언트는 데이터만 지정한다.
• GFS는 GFS가 선택한 오프셋에서 적어도 한 번 파일에 첨부하고 해당 오프셋을 클라이언트에 반환한다.
• 레코드 추가 기능은 분산 애플리케이션에서 많이 사용되며, 서로 다른 시스템의 많은 클라이언트가 동시에 동일한 파일에 추가된다.
• 레코드 추가는 변형(mutation)의 일종으로 섹션 3.1의 control flow를 따른다.
  • 동일한 청크의 복제본은 전체 또는 부분적으로 동일한 레코드의 복제를 포함하여 서로 다른 데이터를 포함할 수 있다.
• GFS는 모든 복제본이 바이트 단위로 동일하다고 보장하지 않고 데이터가 원자 단위로 한 번 이상 작성된다는 것만 보장한다.
  • 이 속성은 작업이 성공을 보고하려면 데이터가 일부 청크의 모든 복제본에서 동일한 오프셋에 기록되어야 한다는 관찰로부터 따라온다.
• 일관성 보장(consistency guarantee) 측면에서 성공적인 레코드 추가 작업이 데이터를 작성한 영역은 정의되는 반면(일관성 있음), 인터리빙 영역은 일관성이 없다.(따라서 정의되지 않음)

3.4 Snapshot

• 스냅샷(snapshot) 작업은 진행 중인 변형의 중단을 최소화하면서 파일 또는 디렉토리 트리(source)의 복사본을 거의 즉시 만든다.
• 사용자는 이 스냅샷을 사용하여 대용량 데이터 세트의 분기(branch) 복사본을 신속하게 생성하거나 나중에 커밋하거나 쉽게 롤백할 수 있는 변경사항을 실험하기 전에 현재 상태를 확인한다.
• AFS와 마찬가지로 표준 Copy-On-Write 기술을 사용하여 스냅샷을 구현한다.

• 챕터 4 Master Operation은 다음 글에서 이어서 진행된다.
  • 바로가기 : [논문 리뷰] The Google File System(GFS) 리뷰 (2)

References

1. 해시넷 - 컴포넌트 ↩

2. 위키백과 - API ↩

3. 위키백과 - 컴퓨터 클러스터 ↩

4. 위키백과 - 캐시 ↩

5. 프로그래머의 블로그 - 오프셋 (Offset) ↩

6. developer.mozilla.org - TCP ↩

7. 오버헤드 - 위키백과 ↩

8. 데이터 마이그레이션이란? - Dropbox ↩

9. 폴링(Polling) 방식 - 미친 남자 ↩

10. JPA 플러시(flush())란? - 꾸준히 성장하는 개발자스토리 ↩

11. 위키백과 - B 트리 ↩

12. 9.6. Reliable Data Storage and Location ↩

13. Lease(computer science) - 위키백과 ↩

14. Deep Dive into Primary/Secondary Replication for Fault Tolerance - Melodies Sim ↩

15. LRU 알고리즘 - 빵순이^^ ↩

16. 스케줄링(Scheduling) 개념 및 이해 - Crocus ↩

17. 사이언스올 - 인터리브(Interleave) ↩

18. 데이터 파이프라인이란? - IBM.com ↩