구글 파일 시스템의 정체

그간 나름대로 구글 논문(http://labs.google.com/papers/gfs-sosp2003.pdf) 을 분석하여 정리하고 공개되지 않은 부분은 대충 눈치로 그럴거 같다고 때려맞춘 내용이니 정확하냐고 묻지는 마시기 바랍니다. 다 알면 이미 똑같이 만들었겠지요.

어차피 실제 구현을 어떻게 하는지에 대한 내용은 논문에 언급이 없으며 이론상으로만 대충 이렇게 한다는 식으로 설명하고 있기 때문에 구체적인 부분은 공개하지도 않으며 아마 실제 구현된 저 논문도 빨라야 2003년도에 나온것이니 지금의 구글파일시스템은 저 논문과 상당히 틀릴 것이고 사실 인간이 만든게 아니라 외계(?)의 기술이 아닐까도 생각합니다.

도저히 아무리 식음을 전폐하고 생각해도 저런 규모에서 항상 안정된 성능이 보장된다는게 신기할뿐입니다. 분명 뭔가 공개되지 않은 어떤 것으로 해결방법으로 있을텐데 말입니다. 대체 뭘까요?

전체적 특징

– 싼 PC(OS는 GNU/Linux)로 분산 파일 시스템을 구축하고 있는데 싸다고 말해도 공간절약을 위한 블레이드의 형태의 PC서버다. 그냥 일반 PC 타워형 케이스로 쓴다는건 진짜 몇대 안되는 초창기때에나 그렇게 썼다고 한다.

– PC는 망가진다고 하는 전제로 설계하고 있기에, 분산 시스템을 구성하는 노드가 망가졌을 때, 데이터가 없어지지 않는 것과 자동으로 복구할 수 있는 것에 주목적을 두고 있다.

– 파일 시스템을 이용하는 어플리케이션측에 어느 정도의 부담을 요구하고 있다. 임의의 경우에 대해서 항상 높은 퍼포먼스를 내는 것은 아니고, 특정의 이용의 경우에서만 평균적 성능을 발휘할 수 있도록 설계하고 있다.

– 성능을 발휘할 수 있는 경우는 다음과 같은 경우이다.

+ 주로 사이즈가 큰 파일을 취급한다.

+ 파일 쓰기는 덧붙여 쓰기(append)가 많다 (파일의 일부분을 몇번이나 고쳐 쓰는 것 같은 이용은 아니다).

+ 쓰기보다 읽기가 많다.

인터페이스(API)

– POSIX 호환은 아니지만 일반적인 파일 조작 API를 제공하고 있는 것 같다. 대충, gfs_open()나 gfs_read()같은 API로 할것이다.

– 파일의 지정은 그래도 트리 베이스의 전형적인 파일 패스이다. 즉, /usr/bin/emacs 같은 파일 패스로 식별하지만 파일의 실체는 분산한 PC의 디스크에 뿌려지고 있다.

– 특별한 쓰기 인터페이스로서 record-append가 있을 것이다. 다음과 같은 상황이기 때문이다. GFS의 파일을 쓰기 시도하는 클라이언트는 복수 존재 하기 때문에 즉, 하나의 클라이언트가 write를 연속해 가도 다른 클라이언트가 끼어들어져도 그대로의 쓰기는 되지 않는 것이다. record-append는 중복된 쓰기작업에 끼어들어지지 않은 것을 안전보장하는 API다. (GFS는 이 record-append의 효율에 최적화되고 있을 것이다)

– snapshot로 불리는 API를 제공하고 있다. 디렉토리 트리의 일부분을 고속으로 카피할 수 있는 기능인데 자세한 것은 실제의 파일 카피를 지연 하여 거대한 트리의 카피여도 고속으로 실행할 수 있게 한다.

– 하드 링크, 소프트 링크는 존재하지 않는다.

– google 의 어플리케이션 예를 들면 써치엔진이나 gmail가 직접 GFS의 API를 부르고 있다고 하면 Web의 HTML 문서나 메일의 문서는 GFS의 파일로서는 너무 작다. 어플리케이션계층에서 복수 문서를 파일에 정리하는 구조(compound document)가 있을 것이다.아니면 다른 API층이 존재할 가능성도 있다.

chunk (파일의 컨텐츠의 단편)

– GFS상에 보존된 파일은 고정 사이즈(64MByte가 통계낸 값인듯)에 분할되어 보존된다. 이 분할된 단편을 chunk라고 부른다.

– 각 chunk는 GFS상에서 독특하고 변화하지 않는 ID로 식별된다.

– chunk handle의 할당은 마스터가 일차적으로 실시한다.

– 1 chunk는 복제를 가지는 각 chunk서버의 파일 시스템상의 1 파일이 된다. chunk handle로부터 로컬 파일 패스에의 MAP는 각 chunk서버가 관리한다.

– 각 chunk는 복수의 chunk서버상에 복제되고 동기된다. chunk의 복제수의 디폴트는 3 이다.

– chunk는 version를 가지는데 이것은 히스토리 관리를 위해서는 아니고(GFS에 히스토리 관리는 없다), chunk의 복제가 올바르게 동기 하고 있는지를 검출하기 때문이다.

개요

– 구성 노드는 마스터 노드, chunk 서버, 클라이언트의 3 종류이다.

– 단일의 마스터 노드가 파일의 디렉토리 트리 상태 관리, 락 관리, chunk의 위치 관리를 담당한다.

– 복수의 chunk서버가 마스터 노드아래에 달린다. 각 파일은 chunk에 분할되어 chunk서버의 스토리지에 보존된다. 각 chunk는, 복수의 chunk서버에 복제된다(replication).

– 클라이언트는 GFS를 이용하는 어플리케이션과 거기에 링크 되는 프로그램 라이브러리다. 프로그램 라이브러리는 네트워크 RPC를 은폐한 API를 제공한다. 어플리케이션측의 시점에서 보면 API를 통해서 GFS상에 파일을 만들거나 읽고 쓰기하거나 하기에 GFS이던 아니던 관계없이 똑같다. GFS측의 시점에서 보면 어플리케이션에 링크된 프로그램 라이브러리가 마스터나 chunk서버와 GFS 통신 프로토콜로 통신한다.

– chunk 자체의 전송은 클라이언트와 chunk서버의 사이에 직접 행해진다(마스터는 전송에 관여하지 않는다. 마스터는 클라이언트에 chunk서버의 위치를 가르칠 뿐).

구성 노드의 개요

– 마스터

+ 마스터 노드는 시스템으로 단일이다.

– 마스터의 주된 역할(보관 유지하는 상태)은 다음의 6개이다.

+ 파일의 디렉토리 트리(파일 패스)의 관리

+ 파일로부터 chunk에의 MAP(파일 패스로부터 chunk handles에의 대응)

+ chunk의 위치 정보 관리(chunk가 어느 chunk서버상에 있을까)

+ 파일의 락 처리

+ 파일의 그 외의 메타데이타 관리(파일 오너, 파일 퍼미션)

+ chunk서버의 생존 확인(HeartBeat 메세지로 죽은 chunk서버를 검출), 상태 관리(빈디스크 용량이나 부하).

– 위 상태를 모두 메모리상에 가지는게 GFS의 핵심이다.

+ 디렉토리 트리 상태는 스토리지에 가지지 않는다. 디렉토리 트리에의 변경은 모두 조작 로그(operation log)의 형태로 스토리지에 적용되어진다.

+ 마스터가 크래쉬 해 온메모리 상태가 없어졌을 경우 조작 로그로부터 디렉토리 트리를 온메모리에 복원한다(replay the operation log). 일반의 파일 시스템이면, 디렉토리 트리 상태를 스토리지에 남기므로 이것은 GFS의 특징적인 점이다.

+ 상상할 수 있듯이 조작 로그는 매우 거대할 것이다. 거대한 조작 로그로부터 상태를 복원하려면 시간이 걸리기 때문에 어느 정도의 타이밍으로 조작 로그에 checkpoint를 설정해 그 시점 상태를 스토리지에 보존한다. 크래쉬로부터의 복귀는 마지막 checkpoint와 그 이후의 조작 로그로부터 실시한다.

+ 파일로부터 chunk에의 MAP도 똑같이 조작 로그로 보관 유지한다.

+ chunk의 위치 정보와 chunk서버 상태도 스토리지에 가지지 않는다. 마스터가 크래쉬로부터 복귀하면 각 chunk서버에 상태(어느 chunk를 가지고 있을까)를 문의하고 GC를 위해서 마스터와 각 chunk서버는 정기적으로 chunk서버가 어느 chunk를 가지고 있을까의 정보를 교환한다.

+ 모두 메모리에 밀어넣기 위해서 설계상의 트릭이 있을 것이다 .

마스터 노드의 장애 대책

– 마스터 노드가 장애가 생긴 것의 검출은 GFS의 외부 모니터로 하고 있다가 장애가 생기면 자동 기동하여 조작 로그로부터 온메모리 상태를 복원한다.

– 마스터 노드의 하드웨어 장애의 경우는 다른 머신의 마스터 노드가 기동하고 변환은 DNS 베이스이다.

– 백업 마스터가 복수 존재해서 조작 로그로 상태를 동기 하고 있다가 마스터가 장애가 있는 경우에서도 read-only 로 가동해 GFS를 존속한다.

마스터 노드의 디렉토리 트리

– 디렉토리 트리의 내부 데이터의 가지는 방법은 보통 Unix의 파일 시스템과 다르다. 보통 Unix의 파일 시스템의 경우 디렉토리 마다 파일을 가지는데, 즉 /usr/bin/emacs이면 /usr 디렉토리의 1 엔트리에 bin가 있고 /usr/bin 디렉토리의 1 엔트리에 emacs가 있다. GFS는 파일 패스로부터 메타데이타에의 일원적인 MAP를 가진다. 즉, /usr, /usr/bin, /usr/bin/emacs 각각의 파일 패스로부터 메타데이타에 MAP 하는 내부 데이터 구조이다.

– 이 메타데이타MAP(디렉토리 트리)을 온메모리로 가지기 때문에 파일 패스의 prefix compression 를 해 메모리를 절약하고 있다. 자세한 것은 쓰여있지 않지만, 아마 /usr를 /a, /bin은 /b, /emacs는 /c 와 같은 글자 하나로 줄이는거와 같은 변환 테이블을 갖게해 메모리를 절약하고 있다고 생각한다.

락

– 복수의 클라이언트가 동시에 같은 파일에 기입하거나 동명의 파일을 만들려고 했을 때 제어가 필요한데 마스터가 락 관리하는 것으로 실현되고 있다.

– 모든 파일 패스는 대응하는 락 오브젝트(read-write lock)를 가집니다. 즉, /d1/d2/…/dn/leaf의 파일 패스가 존재하면, /d1, /d1/d2,…, /d1/d2/… /dn, /d1/d2/…/dn/leaf의 각각, 대응하는 락이 존재한다.prefix compression에 의해 1 파일 대부분이 100바이트 이내에 들어가고 있는 것 같다.

– 예를 들면 /usr/bin/emacs에 기입하고 있는 동안 마스터는 /usr와/usr/bin의 read 락 /usr/bin/emacs의 write 락을 잠근다. Unix 의 통상의 파일 시스템의 디렉토리의 데이터의 가지는 방법이면, /usr/bin/emacs 파일을 작성중은/usr/bin를 write 락 해야 하지만, GFS에서는/usr/bin는 read 락만 하고 /usr/bin/emacs에는 write 락을 한다.  

쓰기작업의 동기화(replica간의 동기)

– lease가 주어진 chunk서버를 주(primary) replica라고 불르고 그 외 서버를 부(secondary) replica 라고 부른다.

– 어느 chunk에 쓸 때 마스터는 그 chunk의 replica를 가지는 chunk서버안의 하나를 선택해 lease를 준다. (lease에는 타임 아웃값이 있지만 언제나 lease의 교환을 하면 마스터에 부하가 걸리므로 한 번 주 replica를 선택하여 맡기고 있을 뿐이다)

– 복수의 클라이언트로부터 동시에 같은 chunk에 쓰기 요구가 왔을 경우 주replica가 그러한 쓰기 요구에 순서(serial number)를 붙여 부replica는 그 순서에 따라 chunk에 쓴다.

– 마스터는 각 chunk의 최신 version를 알고 있다. chunk서버가 다운중에 동기화를 벗어나도 마스터가 보관 유지하는 최신 version와 비교하는 것으로 동기화를 벗어난 것을 검출할 수 있다(이러한 동기 되어 있지 않은 chunk를 stale replica라고 부른다). 덧붙여, 이 경우 chunk서버는 그 chunk를 버린다. 최신 version를 가지는 chunk서버를 찾아 동기를 시도하는 것 같은 복잡한 일은 성능저하로 하지 않는다. 그 대신, chunk의 복제가 하나 없어진 것을 마스터에 통지한다. 마스터는 최신 version의 chunk(이것을 가지는 chunk서버를 마스터는 알고 있다)의 복제를 늘려 replica 수를 유지한다.

– 클라이언트는 마스터로부터 chunk서버의 위치와 동시에 현재의 version를 받아 클라이언트가 chunk서버에 액세스 했을 때 chunk서버가 가지는 chunk의 version를 확인해 stale replica를 에러로 검출한다.

– 각 chunk서버가 독자적으로 chunk의 checksum(32bit) 확인을 한다. 디스크 장애등으로 chunk가 망가졌을 경우 그 chunk는 stale replica이다.

– 클라이언트는 chunk서버의 위치를 캐쉬하므로 stale replica를 읽을 가능성은 제로가 아니라 append-only로 사용하고 있으면 너무 문제는 되지 않는다.

쓰기작업시의 흐름

– [클라이언트=>마스터] 주/부 replica의 chunk서버의 위치를 문의한다(클라이언트는 chunk서버의 위치를 캐쉬한다). 주 replica가 미정인 경우 마스터는 주 replica를 결정한다. (lease를 건네 준다).

– [클라이언트=>1 chunk서버] chunk 서버 가운데 네트워크적으로 가장 가까운 chunk서버에 데이터를 송신한다.

– [chunk서버=>chunk서버=>…] 쓰기 데이터는 replica를 가지는 chunk서버간을 전송 된다. 예를 들면 replica를 가지는 chunk서버가 3대 있어 A, B, C로 한다면 네트워크적으로 클라이언트로부터 가까운 순서에 B, A, C라고 하면, 데이터는 클라이언트=>B=>A=>C의 순서로 전송 된다. 이 시점에서는 아직 각각의 chunk서버는 로컬 디스크의 chunk에 기입은 하지 않는다.

– [클라이언트=>주 replica(의 chunk서버)] replica를 가지는 모든 chunk서버가 데이터를 수신한 후, 클라이언트는 주 replica에 요구를 송신한다.

– [주 replica(의 chunk서버)=>부 replica(의 chunk서버)] 주 replica는 쓰기 요구에 시리얼 번호를 할당하고 주 replica는 시리얼 번호순서에 로컬 디스크의 chunk에 쓰기 데이터를 반영시킨다. 디스크 에러-등으로 실패했을 경우, 클라이언트에 에러를 돌려주고 주replica는 부replica에 시리얼 번호를 송신한다. 각 부replica는 시리얼 번호순서에 로컬 디스크의 chunk(replica)에 데이터를 반영한다. 반영 후, 주replica에 응답을 돌려준다.

– [주replica(의 chunk서버=>클라이언트] 주 replica는 모든 부replica로부터 응답을 수신하면 클라이언트에 응답을 돌려준다. 부replica의 하나에서도 에러가 발생하면(replica에 어긋남이 생기면 주replica는 클라이언트에 에러를 돌려준다

read시의 통신 흐름

– [클라이언트=>마스터] chunk서버의 위치를 문의한다(클라이언트는 chunk서버의 위치를 캐쉬한다).

– [클라이언트=>1 chunk서버] chunk서버에 수신 요구를 던져 chunk데이타를 받는다.

삭제 파일의 취급

– 파일을 삭제해도 곧바로 실제 지우지는 않는다. 삭제시는 마스터의(온메모리의) 메타데이타에 반영할때 파일명을 rename 할 뿐이므로 고속으로 처리한다.

– 마스터상의 정기 태스크(thread)가 디렉토리 트리를 스캔 해 삭제가 끝난 파일을 검출한다. 삭제한후 3일정도 지나 있으면 실제 삭제 처리(GC:Garbage Collection)를 실시한다. 3일 이내이면 undelete가 가능하게 한다.

– GC로 마스터가 삭제 파일의 메타데이타를 온메모리로부터 삭제한다(조작 로그도 남길듯). 이 시점에서는 아직 chunk의 실체는 삭제하지 않는다.

snapshot

– 파일이나 디렉토리 트리의 고속 카피이다.

– snapshot를 취한 순간은 마스터의 온 메모리상에서 메타데이타의 복제를 실시할 뿐이다. 마스터는 snapshot 된 chunk의 reference counter를 올리고 클라이언트로부터 마스터에 그 chunk에의 요구가 왔을 때 마스터는 reference counter 를 보고 chunk 자체의 복제를 하고 나서 고쳐 쓴다(copy-on-write).