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

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

• 이전 글에 이어서 챕터 4 Master Operation 부터 다시 정리해보겠다.
  • 이전 글 바로가기 : [논문 리뷰] The Google File System(GFS) 리뷰 (1)

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) 접근 방식은 빠른 삭제보다 몇가지 이점을 제공한다.

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

8. Related Work

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

References

1. [데이터베이스] Lock에 대해서 알아보자 - 기본편 by 사바라다 ↩

2. Hadoop 데이터 직렬화와 RPC(Remote Procedure Call) - 화이팅빌런 ↩

3. Google File system paper - (4) Master Operation - jinh2352 ↩

4. 02 서버 - 서버의 종류 - 정쿠의 즐라! ↩

5. 위키백과 - 핸드셰이킹 ↩

6. 위키백과 - 체크섬 ↩