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

2022-08-06 14 분 소요

“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)같은 이전의 분산 파일 시스템의 같은 목표들을 공유한다.
하지만, 구글은 이런 기존 특징들을 재검토하고 다른 관점에서 보고 있다.

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

2. Design Overview

2.1 Assumptions

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

시스템은 종종 고장나는 많은 저렴한 상품 컴포넌트들로 구축된다. 지속적으로 모니터링하여 컴포넌트 고장을 감지(detect), 허용(tolerate) 및 신속하게 복구해야 한다.
멀티 GB 파일이 일반적인 경우이므로 이를 효율적으로 관리해야 한다.
워크로드(workload)는 주로 큰 스트리밍 읽기와 작은 랜덤 읽기, 두 가지 종류의 읽기로 구성된다.
- 워크로드(workload) : 주어진 기간에 시스템에 의해 실행되어야 할 작업의 할당량
시스템은 동일한 파일에 동시에 추가되는 여러 클라이언트에 대해 잘 정의된 semantics을 효율적으로 구현해야 한다.
낮은 지연 시간(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)의 제어 흐름을 살펴볼 수 있다.

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

마스터는 모든 네임스페이스(namespace) 작업을 실행한다.
또한, 시스템 전체에서 청크 복제본을 관리한다. 배치(placement) 결정을 내리고, 새로운 청크를 생성하며, 복제본을 생성하고, 청크를 완전히 복제하고, 모든 청크 서버에서 로드의 균형을 맞추고, 사용되지 않는 스토리즈를 회수하기 위한 다양한 시스템 전반의 작업을 조정한다.

4.1 Namespace Management and Locking

많은 마스터 작업이 오래 걸릴 수 있기 때문에, 실행 중인 다른 마스터 작업을 지연시키지 않기 위해 여러 작업(operation)을 활성화하고 네임스페이스의 영역에 대한 잠금(lock)을 사용하여 올바른 직렬화(serialization)을 보장한다.
- 잠금(lock) : 트랜잭션 처리의 순차성을 보장하기 위한 방법 ¹
- 트랜잭션(transaction) : DB의 나누어지지 않는 최소한의 처리 단위
- 직렬화(serialization) : 데이터를 네트워크로 전송하기 위해 구조화된 객체를 바이트 스트림으로 전환하는 과정 ²
  - CSV, XML, JSON 등의 형식은 알아보기 쉽다는 장점이 있지만, 데이터 구조상 파싱하는 시간이 오래 걸린다. 이를 binary로 변경하면 파싱 시간이 짧아지기 때문에 성능상 이득을 볼 수 있다.
전통적인 파일 시스템과 달리, GFS는 해당 디렉토리의 모든 파일을 나열하는 디렉토리별 데이터 구조를 가지고 있지 않다. 또한 동일한 파일이나 디렉토리에 대한 별칭을 지원하지 않는다.
GFS는 네임스페이스를 전체 경로이름(pathname)을 메타데이터에 매핑하는 룩업(lookup) 테이블로 논리적으로 나타낸다.
- prefix compression을 사용하면, 이 테이블을 메모리에 효율적으로 나타낼 수 있다.
네임스페이스 트리의 각 노드에는 관련 read-write lock이 있다.
각 마스터 작업은 실행하기 전에 일련의 lock을 획득한다.

이미지출처 ⁶

스냅샷 작업은 /home 및 /save에 대한 read lock과 /home/user 및 /save/user에 대한 write lock을 획득한다.
파일 생성은 /home 및 /home/user에 대한 read lock와 /home/user/foo에 대한 write lock을 획득한다.
위 두 작업은 /home/user에서 충돌하는 lock을 얻으려고 하기 때문에 올바르게 직렬화이 된다.

네임스페이스는 많은 노드를 가질 수 있기 때문에 read-write lock 개체는 느리게 할당되고 사용되지 않으면 삭제된다.
lock은 deadlock을 방지하기 위해 일관된 전체 순서로 획득된다.
lock은 먼저 네임스페이스 트리의 레벨별로 정렬되고 사전순으로 동일한 레벨 내에 배치된다.

4.2 Replica Placement

GFS 클러스터는 일반적으로 수백 개의 청크 서버가 많은 기계 랙(rack)에 분산되어 있다.
- 랙(rack) : 서버 또는 네트워크 장비들을 넣어두는 철체 프레임. 데이터센터나 서버 룸과 같이 다수의 서버/네트워크 장비들을 두는 곳에서 사용한다. ³
이러한 청크 서버는 동일하거나 다른 랙의 수백 개의 클라이언트에서 차례로 액세스할 수 있다.
청크 복제본 배치 정책은 데이터 안정성과 가용성을 극대화하고 네트워크 대역폭 활용률을 극대화하는 목적들을 수행한다.
청크 복제본을 랙에 분산시켜 전체 랙이 손상되거나 오프라인 상태일 경우에도 청크의 일부 복제본이 유지되고 사용 가능한 상태로 유지된다.

4.3 Creation, Re-replication, Rebalancing

청크 복제본은 청크 생성(chunk creation), 재복제(re-replication), 재조정(rebalancing) 3 가지 이유로 생성된다.
마스터는 청크를 생성할 때 처음에 비어 있는 복제본을 배치할 위치를 선택한다.
이 때, 몇 가지를 고려한다.
1. 평균 이하의 디스크 공간 활용률을 가진 청크 서버에 새 복제본을 배치하려고 한다.
2. 각 청크 서버의 “최근” 생성 수를 제한하려고 한다.
3. 청크의 복제본을 랙에 분산시키려 한다.
마스터는 기존의 유효한 복제본에서 직접 청크 데이터를 복사하도록 청크 서버에 지시하여 가장 높은 우선 순위 청크를 선택하고 클론(clone)한다.
복제 트래픽이 클라이언트 트래픽(traffic)을 압도하지 않도록 마스터는 클러스터와 각 청크 서버 모두에 대해 활성 복제 작업 수를 제한한다.
또한 각 청크 서버는 소스 청크 서버에 대한 읽기 요청을 제한하여 각 복제 작업에 사용되는 대역폭의 양을 제한한다.
마지막으로 마스터는 주기적으로 복제본을 재조정(rebalancing)한다. 현재 복제본 분포를 검사하고 더 나은 디스크 공간과 로드 밸런싱을 위해 복제본을 이동한다.
또한 이 프로세스를 통해 마스터는 즉시 새로운 청크와 함께 제공되는 대량의 쓰기 트래픽으로 서버를 가득 채우는 대신 점차 새로운 청크 서버로 채운다.
또한 마스터는 삭제할 기존 복제본을 선택해야 한다. 평균 이하의 사용 가능한 공간을 가진 청크 서버에서 이러한 공간을 제거한다.

4.4 Garbage Collection

파일이 삭제된 후 GFS는 사용 가능한 물리적 스토리지를 즉시 회수하지 않는다.

4.4.1 Mechanism

애플리케이션에서 파일을 삭제하면 마스터는 다른 변경사항과 마찬가지로 삭제 내용을 즉시 기록(log)한다.
그러나 리소스를 즉시 회수(reclaim)하는 대신 deletion timestamp가 포함된 hidden name으로 파일이 변경된다.
파일 시스템 네임스페이스의 마스터가 정기적으로 검색하는 동안 이러한 hidden name이 3일 이상 존재한 경우 모두 제거된다.
hidden 파일이 네임스페이스에서 제거되면 메모리 내 메타데이터가 지워진다.
유사한 청크 네임스페이스의 정기적인 검색에서 마스터는 고아된 청크를 식별하고 해당 청크의 메타데이터를 지운다.

4.4.2 Discussion

GFS는 청크에 대한 모든 참조를 쉽게 식별할 수 있다. 그것들은 마스터에 의해 독점적으로 유지되는 파일-청크 매핑에 있다.
GFS는 모든 청크 복제본을 쉽게 식별할 수 있다. 그것들은 각 청크 서버에 지정된 디렉토리에 있는 리눅스 파일이다.
마스터가 알 수 없는 복제본은 가비지(garbage)이다.
스토리지 재확보에 대한 가비지 컬렉션(garbage collection) 접근 방식은 빠른 삭제보다 몇가지 이점을 제공한다.

컴포넌트 장애가 흔한 대규모 분산 시스템에서 단순하고 신뢰할 수 있다.
- 가비지 컬렉션은 유용하지 않은 복제본을 균일하게 정리할 수 있는 신뢰할 수 있는 방법을 제공한다.
스토리지 회수 작업을 네임스페이스의 정기적인 검색 및 청크 서버와의 핸드쉐이크(handshake)와 같은 마스터의 일반적인 백그라운드 작업에 merge한다. 일괄적으로 수행되며 비용은 삭감되며, 마스터는 적시에 주의를 요하는 클라이언트 요청에 보다 신속하게 응답할 수 있다.
- 핸드쉐이크(handshake) : 채널에 대한 정상적인 통신이 시작되기 전에 두 개의 실체 간에 확립된 통신 채널의 변수를 동적으로 설정하는 자동화된 협상 과정 ⁵
스토리지 회수 지연(delay)은 돌이킬 수 없는 우발적 삭제에 대한 안전망을 제공한다.

4.5 Stale Replica Detection

청크 서버가 다운된 동안 청크 서버에 장애가 발생하여 청크에 대한 변형이 누락되면 청크 복제본이 오래될 수 있다.
마스터는 각 청크에 대해 최신 복제본과 오래된 복제본을 구분하기 위해 청크 버전 번호를 유지한다.
마스터는 청크에 대해 새로운 리스를 부여할 때마다 청크 버전 번호를 늘리고 최신 복제본에 알린다.
- 리스(lease) : 큰 청크 크기와 데이터 변형의 기본 복제본에 권한을 위임을 말함.
마스터가 레코드의 버전 번호보다 큰 버전 번호를 볼 경우 마스터는 리스를 허용할 때 실패한 것으로 간주하여 상위 버전을 최신 버전으로 가져온다.
마스터는 일반 가비지 컬렉션에서 오래된 복제본을 제거한다.

5. Fault Tolerance And Diagnosis

시스템 설계 시 가장 challenge 중 하나는 잦은 컴포넌트 장애를 처리하는 것이다.
- 컴포넌트 오류로 인해 시스템을 사용할 수 없거나 데이터가 손상될 수 있다.

5.1 High Availability

GFS 클러스터에 있는 수백 개의 서버 중 일부는 항상 사용할 수 없게 되어 있다.
이에 단순하지만 효과적인 두 가지 전략인 빠른 복구(fast recovery)와 복제(replication)로 전체 시스템의 가용성(availability)을 유지한다.

5.1.1 Fast Recovery

마스터 서버와 청크 서버 모두 상태를 복원하고 종료 방법에 관계없이 몇 초만에 시작하도록 설계되었다.

5.1.2 Chunk Replication

각 청크는 서로 다른 랙의 여러 청크 서버에 복제된다.
사용자는 파일 네임스페이스의 다른 부분에 대해 다른 복제 수준을 지정할 수 있다.
- default : 3
마스터는 필요에 따라 기존 복제본을 복제하여 청크 서버가 오프라인으로 전환될 때 각 청크를 완전히 복제하거나 체크섬(checksum) 확인을 통해 손상된 복제본을 탐지한다.
- 체크섬(checksum) : 중복 검사의 한 형태로, 오류 정정을 통해, 공간(전자 통신)이나 시간(기억 장치) 속에서 송신된 자료의 무결성을 보호하는 단순한 방법 ⁴

5.1.3 Master Replication

신뢰성(reliability)을 위해 마스터 상태가 복제된다. 해당 작업 로그 및 체크포인트는 여러 시스템에 복제된다.
상태 변환은 로그 레코드(log record)가 로컬 및 모든 마스터 복제본에서 디스크로 플러시된 후에만 커밋된 것으로 간주된다.
단순성(simplicity)을 위해 하나의 마스터 프로세스가 모든 변형은 물론 내부적으로 시스템을 변경하는 가비지 컬렉션과 같은 백그라운드 활동을 담당한다.

5.2 Data Integrity

각 청크 서버는 체크섬(checksum)을 사용하여 저장된 데이터의 손상을 detect한다.
청크는 64KB 블록으로 분할된다. 각각에 해당하는 32 big 체크섬이 있다.
다른 메타데이터와 마찬가지로 체크섬은 메모리에 보관되며 사용자 데이터와 별도로 로깅(logging)와 함께 지속성있게 저장된다.
체크섬은 여러 가지 이유로 읽기 성능에 거의 영향을 주지 않는다.
- 대부분의 읽기는 최소 몇 블록에 걸쳐 있기 때문에 확인을 위해 상대적으로 적은 양의 추가 데이터만 읽고 체크섬하면 된다.
GFS 클라이언트 코드는 체크섬 블록 경계에서 읽기를 정렬함으로써 이러한 오버헤드를 더욱 줄여준다.

idle 기간 동안 청크 서버는 비활성 청크의 내용을 검색하고 확인할 수 있다. 이를 통해 거의 읽지 않는 청크의 손상을 detect할 수 있다.
손상이 발견되면 마스터는 손상되지 않은 새 복제본을 생성하고 손상된 복제본을 삭제한다.

5.3 Diagnostic Tools

GFS 서버는 많은 중요한 이벤트와 모든 RPC 요청 및 응답을 기록하는 진단 로그를 생성한다.
RPC 로그에는 읽거나 쓰는 파일 데이터를 제외하고 와이어(wire)로 전송되는 정확한 요청과 응답이 포함된다.
요청을 응답과 일치시키고 서로 다른 장치에서 RPC 레코드를 취합함으로써 전체 상호 작용 기록을 재구성(reconstruct)하여 문제를 진단할 수 있다.
로그는 부하 테스트 및 성능 분석을 위한 추적 역할도 있다.

6. Measurements

이 섹션에서는 GFS 아키텍처 및 구현에 내재된 병목 현상을 설명하기 위한 몇 가지 마이크로 벤치마크와 Google에서 사용 중인 실제 클러스터의 몇 가지 숫자를 제시한다.

6.1 Micro-benchmarks

1개의 마스터, 2개의 마스터 복제본, 16개의 청크 서버 및 16개의 클라이언트로 구성된 GFS 클러스터에서 성능을 측정했다.

6.1.1 Reads

N개의 클라이언트가 파일 시스템에서 동시에 읽는다.
각 클라이언트는 320GB 파일 셋에서 랜덤으로 선택된 4MB 영역을 읽는다. 이것은 각 클라이언트가 1GB의 데이터를 읽도록 256번 반복된다.
전체 청크 서버의 메모리가 32GB에 불과하므로 Linux 버퍼 캐시에서 최대 10%의 적중률(hit rate)이 예상된다.
Figure 3 (a)는 N개 클라이언트의 총 읽기 속도와 이론적 한계를 보여준다.
관찰된 read rate은 클라이언트당 제한의 80%인 10MB/s이다. (이는 클라이언트 한 개만 읽을 때)
총 read rate는 클라이언트당 6 MB/s인 16개의 reader에 대해 링크 제한 125MB/s의 약 75%인 94MB/s에 도달한다.

6.1.2 Writes

N개의 클라이언트는 N개의 개별 파일에 동시에 쓴다.
각 클라이언트는 새 파일에 1GB의 데이터를 1MB의 연속 쓰기로 기록한다.
한 클라이언트에 대한 write rate는 제한의 절반인 6.3MB/s이다.
- 한 복제본에서 다른 복제본으로 데이터를 전파하는 데 지연되면 전체 쓰기 속도가 줄어든다.
총 write rate는 16개 클라이언트에서 35MB/s에 달하며, 이는 이론적 제한의 절반에 해당한다.

6.1.3 Record Appends

Figure 3 (c)는 레코드 추가(record append) 성능을 보여준다.
N개의 클라이언트는 단일 파일에 동시에 추가된다.
성능은 클라이언트의 수에 관계없이 파일의 마지막 청크를 저장하는 청크 서버의 네트워크 대역폭에 의해 제한된다.
한 클라이언트의 경우 6.0MB/s에서 시작하여 16개 클라이언트의 경우 4.8MB/s로 떨어지는데, 이는 주로 다른 클라이언트에서 볼 수 있는 네트워크 transfer rate의 차이와 혼잡(congestion)으로 인해 발생한다.

6.2 Real World Clusters

이 섹션 내용들은 넘어가겠다.

7. Experiences

처음에 GFS는 프로덕션 시스템을 위한 백엔드 파일 시스템으로 구상되었다.
시간이 지남에 따라, 그 용도는 연구 및 개발 작업을 포함하도록 발전했다.

GFS는 load balance나 fault tolerance을 위해 데이터를 투명하게 이동할 수 있는 위치 독립적인 네임스페이스를 제공한다.
GFS는 총 성능 및 fault tolerance를 제공하기 위해 파일 데이터를 스토리지 서버에 분산한다.
GFS는 파일 시스템 인터페이스 아래에 캐싱을 제공하지 않는다. 타겟 워크로드는 대규모 데이터 셋을 통해 스트리밍하거나 데이터 셋 내에서 무작위로 검색하여 매번 소량의 데이터를 읽기 때문에 단일 애플리케이션 실행 시 재사용이 거의 없다.
GFS는 설계를 단순화(simplify)하고, 신뢰도(reliability)를 높이며, 유연성(flexibility)을 얻기 위해 중앙 접근 방식을 선택했다.
마스터 상태를 작게 유지하고 다른 시스템에서 완전히 복제하여 fault tolerance를 해결한다.
확장성(scalability)와 높은 가용성(availability)(읽기용)은 현재 섀도(shadow) 마스터 메커니즘에 의해 제공된다.

References

KakaoTalk Twitter Facebook LinkedIn

ingu627 🔅