[Paper Review] The Google File System - 2

 4. Master Operation 

master는 file system과 관련된 모든 system-wide한 동작들을 수행한다.

• all namespace operations of files and directories

• replica placement decision

• create, re-replicate, rebalance chunks

• reclaim unused storage

  
  

4.1 Namespace Management and Locking 

여러 master operation은 시간이 상당히 소요된다. 예를 들어 snaphost의 경우 lease를 revoke 시키는 경우 모든 chunkserver에 대해서 lease를 revoke 해야한다. 그러므로, 우리는 적절한 serialization (operation들을 순서대로 처리하는 것) 여러 operation들이 active하게 하고 각 namespace의 region별로 lock을 사용한다.

전통적인 file system과 다르게 GFS는 per-directory data structure를 사용하지 않으며 file이나 directory에 대한 alias (hard or symbolic links in Unix terms)도 지원하지 않는다. GFS는 full pathname을 metadata에 mapping 하는 lookup table을 통해서 logcial하게 namespace를 나타낸다. prefix compression을 통해서 효과적으로 memory에 저장할 수 있다. namespace tree에 있는 각 node는 관련된 read-write lock을 갖는다.

각 master operation은 실행되기 전 여러 lock을 획득한다. 보통 /d1/d2/.../dn/leaf에 대해서 operation을 수행하면 dirctory /d1, /d1/d2, ..., /d1/d2/.../dn에 대해서 read lock을 얻고 full pathname /d1/d2/.../dn/leaf에 대해서 write lock을 얻는다.

GFS locking scheme의 좋은 점은 같은 directory 내부에서 concurrent mutation이 가능하다는 점이다. 예를 들어 한 directory 내에서 여러 파일 생성이 일어날 때 각 mutation은 directory에 대해 read lock을 얻고 file name에 대해 write lock을 얻는다. read lock은 해당 directory가 변경, 삭제되는 것을 막고 write lock은 같은 file name에 대한 시도를 serialize하여 처리한다.

namespace가 여러 node를 가지고 있기 때문에 read-write lock은 lazy하게 할당되며 사용되지 않을 때 한번에 삭제된다. 또한 lock은 deadlock을 방지하기 위해 consistent total order로 획득된다.

4.2 Replica Placement 

GFS cluster는 replica factor가 1보다 크게 분산되어있다. 보통 다수의 machine rack에 걸쳐서 수백대의 chunkserver로 이루어져있다. 분산된 chunkserver는 서로 다른 rack으로부터 수백개의 클라이언트로부터 access된다. 서로 다른 rack에 존재하는 두 machine 간 통신은 하나 이상의 network switch를 통하게 되며, rack에 걸쳐이는 bandwidth는 동일한 rack 내부의 machine 간 aggregate bandwidth 보다 작다. scalability, reliability, availability를 위해서 이처럼 multi-level로 replica를 분산시키는 것은 고유의 도전을 의미한다.

chunk replica placemnet policy는 두가지 목적을 수행한다.

• maximize data relibility

• maximize network bandwidth utilization

이를 위해서 replica를 서로 다른 machine에 대해서만 복제하는 것은 충분하지 않다. 우리는 chunk replica를 rack에 걸쳐서 복제해두어야 한다. 이를 통해서 rack 전체가 실패했을 때도 대처가 가능하고 여러 rack에 걸쳐서 read traffic을 받을 수 있다. write traffic은 여러 rack에 걸쳐서 발생하지만 기꺼이 수용 가능한 tradeoff이다.

4.3 Creation, Re-replication, Rebalancing

chunk replica는 creation, re-replication, rebalancing에 의해 생성된다.

create.

master가 chunk를 create 할 때 빈 replica를 어디에 할당할지 결정한다. 이때 몇가지 factor를 고려한다.

1) 평균 아래의 disk space utilization인 chunkserver. 시간이 지날수록 다른 chunkserver와 utilization이 같아진다.

2) 각 chunkserver에서 최신의 creation이 다수 발생하는 것을 제한한다. 대부분의 application에서append-once-read-only 패턴에 비추어 보았을 때 초기 creation 이후 급격한 대량의 write traffic이 발생할 수 있기 때문이다.

3) replica는 여러 rack에 걸쳐서 분배되어야 한다.

re-replicate.

master는 가능한 replica의 수가 지정한 replication factor보다 떨어지면 신속하게 re-replicate를 수행한다. re-replicate가 필요한 각 chunk는 여러 factor에 의해 우선순위가 결정된다.

1) replication factor보다 얼마나 모자란지.

2) live file 먼저. delete 예정인 file 보다 자명하게 우선한다.

3) 실행 중인 application에 미치는 실패에 따른 영향도를 최소화하기 위해 client progress를 방해하는 chunk 먼저.

master는 highest prority chunk를 선택한 다음 chunkserver에 명령을 내려서 복제한다.

rebalance.

master는 주기적으로 replica를 rebalance 한다. master는 현재 replica distribution을 조사한 다음 replica들을 더 나은 disk space, load balancing을 위해 이동시킨다. 이 과정과 더불어서 master는 새로운 chunkserver를 점진적으로 채우며, 새로운 chunk를 급진적으로 받아들여 write traffic이 몰리는 것을 방지한다.

4.4 Garbage Collection 

file을 삭제한 후 GFS는 가능한 물리 저장소를 즉시 회수하지 않는다. file, chunk level 둘 다 regular garbage collection 시에 lazy하게 회수한다. 우리는 이러한 접근이 더 단순하고 신뢰성 있음을 발견하였다.

4.4.1 Mechanism 

file이 application으로부터 삭제될 때 master는 다른 변경처럼 deletion에 대한 log를 남긴다. 하지만 즉시 자원을 회수하는 것이 아니라 file은 단순히 숨김 파일로 변경되며 삭제 예정 timestamp를 가진다 (default 3일이며 설정 가능). master의 regular scan 때 삭제 예정 시간이 지났으면 이 숨김 파일은 master의 metadata에서 삭제된다. 이러한 방법은 효율적으로 chunk로의 링크를 끊는다.

chunk namespace의 regular scan에서 master는 orphaned chunk (file과의 링크가 삭제된 chunk)를 발견하면 master는 해당 chunk에 대한 metadata를 삭제한다. 이후 chunkserver와 주고받는 heartbeat 메시지에서 해당 chunk가 master의 metadata에 존재하지 않는 것을 확인하면 chunkserver는 해당 chunk의 replica를 자유롭게 삭제한다.

4.4.2 Discussion

programming language의 맥락에서 분산 garbage collection은 복잡한 해결책을 요구하는 어려운 문제이지만 GFS에서는 비교적 단순하다. master에 의해서 관리되는 file to chunk mapping을 통해서 모든 chunk에 대한 reference를 확인할 수 있다. 즉, master로부터 확인되지 않은 replica는 garbage다.

storage 자원 회수에 관한 lazy한 전략은 eager deletion에 비해서 다음과 같은 이점이 있다. 첫째, component의 실패가 빈번한 대규모의 분산 시스템에서는 이 방법이 단순하고 신뢰성있다. master로부터 알려지지 않은 replica를 지우는 이 방법은 동등하고 종속적인 방법을 제공한다. 둘째, storage 자원 회수를 regular background 작업에 merge 시킨다. 그러므로, batch로써 작업이 이루어지고 비용은 amotized 된다. 셋째, 의도적인 지연을 통해서 사고 혹은 비가역적인 삭제를 방지한다.

경험에 의하면, 이러한 방법의 주요 단점은 storage가 tight하게 사용될 때 사용자에 의한 fine tune을 방해한다는 점이다. 예를 들어 application에서 반복적으로 파일을 생성, 삭제한다면 문제가 될 수 있다. 이러한 문제는 의도적인 삭제에 대한 명시적인 명령을 내릴 수 있도록 하여 해결할 수 있다.

4.5 Stale Replica Detection 

chunk replica는 chunkserver가 실패했거나 down 되었을 때 발생한 mutation을 놓쳤을 때 발생한다. up-to-date replica와 stale replica를 구분하기 위해서 master는 각 chunk에 대해서 chunk version number를 관리한다.

master가 chunk에 새로운 lease를 부여할 때 master는 chunk version을 증가시키고 up-to-date replica에 알린다. master와 replica들은 이 새로운 version number를 persistent하게 관리한다. 만약 replica가 stale한 상태라면 verison number는 증가하지 않을 것이다. stale replica가 정상 상태로 돌아와서 master에게 version number를 master에다 알리면, master는 주어진 version number 현재의 것보다 뒤쳐져 있음을 확인하고 해당 replica를 garbage collection 처리될 수 있도록 한다.

5. Fault Tolerance and Diagnosis

자원들을 완전히 신뢰할 수 없다. 이러한 도전을 어떻게 맞닥뜨렸는지와 문제를 분석하기 위한 tool에 대해서 이야기하고자 한다.

5.1 High Availability

GFS cluster 내 수백대의 서버 중에서 일부는 반드시 unavailable한 상태에 이르른다. 우리는 fast recovery와 replication 이 두가지 전략으로 전체 시스템을 highly available 하게 유지하였다.

5.1.1 Fast Recovery 

master와 chunkserver 둘 다 어떻게 종료되었든 이전 상태를 복구하고 시작하는 데 수초 이내가 걸리도록 설계되었다. 사실 상 우리는 정상 종료와 비정상 종료를 구분하지 않는다. client에서는 서버가 재시작할 때 작은 hiccup (지표에 일시적으로 변동이 가해지는 현상)을 겪는다.

5.1.2 Chunk Replication 

이전에 논의한대로, 각 chunk는 서로 다른 rack에 걸쳐서 설정한 replication factor만큼 복제되어있다. master는 chunkserver가 잘 동작하지 않을 때 존재하는 다른 replica를 복제한다. 현 replication 전략이 잘 동작하고 있지만 우리는 parity, erasure code와 같은 cross-server redundancy의 형태를 더 탐색하는 중이다.

5.1.3 Master Replication 

master의 상태는 reliability를 위해서 복제되며, operation log와 checkpoint가 여러 machine에 저장된다. 상태에 관한 mutation은 local disk와 master replica에 flush 되었을 때 commit 된다. 만약 master가 실패했을 때 GFS 밖의 monitoring infrastructure에서 이를 탐지하여 새로운 master process를 기동한다. client 단에서는 서로 다른 master에 대해서 DNS로 접근하고 있기 때문에 전혀 변경 사항이 없다.

더욱이, shadow master는 primary master가 down 되었을 때 파일 시스템에 대한 read-only access를 제공한다. mirror가 아닌 shadow인 이유는 primary에 대해 약간의 지연이 있을 수 있기 때문이다. 하지만 file content가 아닌 metadata에 대한 지연은 application에 대한 영향이 크지 않다.

shadow master는 자신을 갱신하기 위해 primary master가 받는 operation log를 읽어 순서 그래도 변경사항을 가한다. 또한 primary처럼 chunkserver를 poll 하고 있으며 monitoring 한다. shadow master는 replica의 생성, 삭제로부터 발생하는 primary의 replica placement에 대한 update에 대해서만 primary에 종속적이다.

5.2 Data Integrity

각 chunkserver는 저장된 data의 corruption을 탐지하기 위해 checksum을 사용한다. GFS cluster에서 corruption은 흔한 일이고, 우리는 이 corruption을 탐지했을 때 복구할 수 있다. 하지만 다른 replica끼리 비교를 통해 corruption을 하는 것은 상당히 비 실용적이다. 따라서 각 chunkserver는 그들 고유의 checksum 유지함으로써 data integrity에 대한 verification을 해야한다.

chunk는 64KB block으로 이루어져 있다. 각각은 대응하는 32 bit의 checksum이 있고 다른 metadata처럼 memory 및 persistent에 로그와 함께 저장된다.

read 요청에 대해서 chunkserver는 응답하기 전 대상 range에 있는 data block에 대한 verification을 수행한다. 만약 checksum이 다르다면 chunkserver는 응답으로 error을 주고 client는 다른 replica로부터 data를 얻는다. 해당 chunkserver는 master에 의해 garbage collection 된다.

checksum은 성능에 영향을 거의 미치지 않는다. 대부분의 read 요청이 소수의 block에 한정되어있어 verification도 그만큼 이루어진. GFS client는 checksum block boundary에 맞추어 요청을 하기에 overhead를 줄인다. 게다가, checksum lookup 및 comparison은 I/O 없이 발생하고, checksum 계산은 I/O와 overlap 되어 이루어진다.

checksum 계산은 record append에 최적화되어있다. 마지막 partial checksum block에 대해서 단순히 increment를 시키고, 새로운 checksum block에 대해서는 새로이 계산을 한다.

반대로 write는 대상 range에 있는 기존 block에 대해서 read 및 verification을 하고, write 후 그 block에 대해서 checksum을 계산해서 저장해야 한다. 기존 block에 대한 verification은 반드시 필요한데, 만일 수행하지 않을 경우 corruption 된 data를 overwrite 하기 때문이다.

idle period 시에 chunk server는 scan을 하여 inactive chunk에 대한 verification을 수행한다. 이를 통해서 서버가 모두 valid한 replica만을 들고있다는 가정을 조금 더 완화시킬 수 있다.

5.3 Diagnostic Tools

광범위하고 세부적인 분석 로그는 비용을 거의 발생시키지 않으면서도 문제 격리 (한정적 문제 정의), 디버깅, 성능 분석에 헤아릴 수 없을만큼 중요하다. GFS는 여러 중요한 event와 모든 RPC 요청 및 응답에 로그를 남기고 있다. 이들을 조합해서 모든 상황에 대한 history generation이 가능하다.

로그를 남기는 것은 성능 상에 거의 영향을 주지 않는데, 로그가 sequential 하고 비동기적으로 쓰여지기 때문이다.

6. Measurements

이 section에서는 GFS architecture에 담긴 근본적인 bottleneck을 나타내기 위한 몇몇 micro-benchmark와 google에서 사용되는 실제 cluster에 대한 측정을 다룬다.

6.1 Micro-benchmarks

실험을 위한 GFS cluster는 1 master, 2 masters, 16 chunkservers, 16 clients로 구성되어 있다. 모든 machine은 다음과 같은 spec으로 이루어져있다.

• dual 1.4 GHz PIII processors, 2 GB of memory, two 80 GB 5400 rpm disks, and a 100 Mbps full-duplex Ethernet connection to an HP 2524 switch

• All 19 GFS server machines are connected to one switch, and all 16 client machines to the other.The two switches are connected with a 1 Gbps link.

6.1.1-3 Reads, Writes, Record Appends

figure 3은 위 cluster에 대한 aggregate read, write, record append rate를 나타낸다. 기본적으로 ideal peak는 1Gbps link에 의해 125 MB/s에서 saturate되며 client에서는 100 Mbps network interface에 의해 12.5 MB/s에서 saturate 된다.

read.

실제 실험에서는 한 client 연결 시 이론적인 성능의 80%를, client 수가 늘어나면서 추가적으로 80%에서 75%더 감소하였다. 이는 여러 client가 같은 chunkserver에서 동시에 read를 하기 때문이다.

write.

write는 67 MB/s에서 saturate 되는데, 기본적으로 chunk 하나 당 16개 chunkserver 중 3개씩 write해야하기 때문이다. 실제 성능은 조금 더 작게 증가한다. 이는 동시 write 뿐만아니라 replication factor에서 기인한다.

record append.

성능은 client 수에 상관없이 대상 마지막 chunk를 들고 있는 chunkserver의 network bandwidth에 의해 한정된다. client 수가 늘어날수록 congestion과 network trasfer rate 변수에 영향을 받아 성능이 조금씩 saturate 되었다.

실제 cluster에서는 N clients가 M shared file에 접근하는 형태가 될 것이다. 대량의 cluster에서는 위 congestion이 크게 문제가 되지 않는데, client는 chunkserver가 다른 file로 busy 할 때 다른 file에 먼저 쓸 수 있기 때문이다.

6.2 Real World Clusters

google에서 실제 사용되는 두 cluster 조사 결과이다. cluster A는 연구개발 용으로, cluster B는 실제 production 용으로 사용되었으며 둘은 각기 다른 spec을 가지며 다른 접근 패턴을 보인다.

6.2.1 Storage

두 cluster는 수백 chunkserver로 이루어진 storage로 사용되었으며 replication factor가 3임을 고려했을 때 실제 데이터 저장률은 used disk space의 1/3이 될 것이다.

6.2.2 Metadata

chunkserver의 metadata 용량은 64KB data block가지는 checksum이 대부분이며 chunk version number 또한 포함된다.

master의 metadata 용량은 훨씬 적은데 이는 우리가 초기 논의했던 master의 memory 이슈가 전체 system capacity에 영향을 미치지 않을 것이라는 주장과 일치하는 결과를 보여준다.

각 chunkserve와 master는 50~100MB 크기의 metadata를 가지고 있어 recovery가 신속하다. 다만, master의 경우 온전히 동작하려면 30~60초가 걸리는데, chunk location정보를 모두 취합해야 하기 때문이다.

6.2.3-5 Read and Write Rates, Master Load, Recovery Time 

6.3 Workload Breakdown

이 section에서는 두 cluster에 대한 workload 분석을 하려고 한다. cluster X는 연구개발용이며 cluster Y는 production의 data processsing 용이다.

6.3.1 Methodology and Caveats

결과는 client로 비롯된 request만을 포함하였다. I/O에 관한 통계는 GFS 서버에 로깅된 실제 RPC 요청을 바탕으로 heuristic하게 reconstruct 되었다.

논문을 통해서 workload에 대한 지나친 일반화를 조심하였으면 한다. google에서는 GFS와 application 모두 완전히 통제하고 있다. application은 GFS에 맞게 설계되었으며 역으로 GFS도 application을 위해 설계되었다.

6.3.2 Chunkserver Workload

table 4는 size 별 operation 분포를 보여준다.

read의 경우 64KB 이하는 큰 파일에서 작은 부분을 찾기 위한 seek-intensive 한 작업이며 512KB 이상은 긴 sequential read이다. cluster Y는 상당한 비율로 read의 결과 0을 retrun 하는데, 이는 producer-consumer queue에서 consumer가 producer 보다 overpace 된 상황으로부터 온다. X는 data analysis 목적으로 사용되어 short-lived data를 read 하기 때문이 그 비율이 적다.

write의 경우 256KB 이상은 writer의 buffering으로부터 온다. 작은 data를 buffer 한 경우는 checkpoint, syschronize 할 때나 혹은 정말로 작은 data를 write 할 때이다.

table 5는 operation의 size 별 data transfer 비율이다. 대부분의 data transfer는 큰 size에서 발생하며 read의 경우 소량의 random seek이 큰 비율을 차지하고 있다.

6.3.3 Appends and Writes 

record append는 production system에서 무겁게 사용되었다. cluster X의 경우 write 대비 record append는 108:1의 비율이며 byte transfer로는 8:1이다. cluster Y의 경우 각각 3.7:1, 2.5:1이다. 기대한대로 record append의 비율이 압도적으로 dominate 하였다. 또한 대부분의 overwrite는 client retry에서 발생하였다.

6.3.4 Master Workload 

master의 workload 중 대부분의 요청은 chunk locations에 대한 request (FindLocation)고 lease holder information에 대한 request (FindLeaseHolder)였다.

7. Experiences

GFS를 디자인하고 배포하는 과정에서 opeational, technical 한 다양한 이슈들을 겪었다.

먼저 GFS는 backend file system으로 인식되었으나 다양한 용처가 생기면서 permission, quota 등에 대한 근본적인 필요성이 제기되었다.

맞닥뜨린 가장 큰 문제들은 disk와 linux로부터 왔다. 자세한 내용은 논문을 참조하기를 바란다.

8. Related Work

GFS가 채택한 설계는 여러 연구와 관련이 있다. 자세한 내용은 논문을 참조하기를 바란다.

• location independent namespace

• a set of disks distributed in networks, rather than RAID

• do not provide any caching

• centralized server, rather than relying on distributed algorithms for consistency and management

• delivering aggregate performance to a large number of clients

• atomic record appends

  
  

9. Conclusions 

 GFS는 성공적으로 google의 storage 수요를 충족시켰으며 다양한 분야에서 storage platform에서 사용되고 있다. GFS는 전체 web scale의 문제들을 혁신하고 뛰어넘게 하기 위한 중요한 tool로 자리 잡았다.

References

- Sanjay Ghemawat, Howard Gobioff, & Shun-Tak Leung (2003). The Google File System. In Proceedings of the 19th ACM Symposium on Operating Systems Principles (pp. 20–43).

- https://www.cs.princeton.edu/courses/archive/fall18/cos418/docs/p8-consistency.pdf

1편

[Paper Review] The Google File System - 1

[Paper Review] The Google File System - 1

Background

Google 파일 시스템(GFS)은 대량의 데이터를 저장 및 처리하기 위한 Google의 분산 파일 시스템으로 2003년 SOSP에서 처음 소개가 되었다. 지속적으로 개선이 되어 현재는 Collossus라는 이름으로 Google에서 사용되고 있으며 Google Cloud Platform (GCP)에서도 Collossus를 기반으로한 파일 시스템 서비스를 제공하고 있다.

세상에 나온지 거의 20년이 다 되어가는 논문이지만 대량의 데이터를 효율적이고 신뢰성 있게 저장하기 위한 GFS의 디자인 및 구현, 그리고 설계 과정에서의 고민은 오늘 날에도 여전히 유효하다. 논문을 읽으면서 분산 시스템이 가진 고유의 문제들을 해결하면서 효율적인 파일 시스템을 제공하기 위한 GFS의 여러 지혜를 얻을 수 있을 것이다.

GFS 논문 리뷰는 두 차례에 걸쳐 작성되었다. 간결하게 정리하고 싶었지만 논문에서 빠뜨릴 내용이 없어 대부분의 내용을 글에 담게 되었다. 

Abstract

논문에서는 대량의 분산된 data를 처리하기 위한 scalable distributed file system인 Google File System(GFS)을 디자인 및 구현하였다. GFS는 commodity hardware을 기반으로 한 cluster에서 동작하며 fault tolerance하며, 다수의 client에게 높은 aggreagte performance를 보여준다.

이전의 distributed file system의 목적을 공유하면서, GFS의 디자인은 google의 application workload와 technoloical enviroment의 현재와 미래 측면 모두를 반영하여 고안되었다. 이는 전통적인 file system을 다시 탐색하고 급진적인 다른 design points들을 탐험하게 하였다.

GFS는 google의 storage needs를 성공적으로 충족시켰다. 대량의 data set을 다루는 development, research 모두에서 data generation, processing을 위한 storage platform으로 사용되었다. 이 대량의 cluster는 수천 개의 machine 상에서 수백 TB의 data를 저장하고 수백개의 client로부터 동시 접근된다.

논문은 다음 세가지를 담고있다.

• file system extension designed to support distributed applications

• discuss many aspects of GFS's design

• measurements from both micro-benchmarks and real world use

1. Introduction 

GFS는 google 내에서 빠른 속도로 증가하는 data processing에 대한 needs를 충족시키고자 탄생하였다. GFS의 디자인은 google의 application workload와 technoloical enviroment의 현재와 미래 측면 모두를 반영하여 고안되었다. 이는 전통적인 file system을 다시 탐색하고 급진적인 다른 design points들을 탐험하게 하였다.

첫째로, component failure는 예외 사항이 아니라 distributed system의 표준이다. 수천대의 machine으로 구성된 cluster는 저가의 상용 machine으로 구성되어 있으며 상응하는 수의 client로부터 access된다. machine의 quantity, quality가 의미하는 것은 언제라도 functional 하지 않을 수 있고 recove 되지 못할 수도 있다는 것이다. 우리는 application bug, operating system bugs, human erros, disk failure, memory, connector, network, power supplies 등 아주 다양한 곳에서 에러가 발생되는 것을 관찰하였다. 따라서 content monitoring, error detection, fault tolerance, automatic recovery는 system에 필수적이다.

둘째, 파일들은 전통적인 표준에 비해 그 크기가 매우 크다. 수 GB는 보통이다. 수 TB로 빠르게 증가하는 application 내 data를 처리할 때, 설령 file system이 지원 가능하다고 해도 수십억개의 KB-sized의 파일을 다루는 것은 매우 어렵다. 따라서 I/O operation과 block size 같은 design assumption 및 parameter는 다시 고려되어야 한다.

세번째, 대부분의 파일들은 기존의 data를 overwrite 하는 것 보다 새로운 data를 append 하는 것으로 mutate가 일어난다. random write 실질적으로 발생 빈도수가 적고 한번 write되면 대부분 read 혹은 sequential read만 발생한다. 대량의 파일에 대한 이러한 access pattern을 고려했을 때, append는 성능 최적화와 원자성 보장을 위한 focus가 되어야한다. 반면 client에 data block을 cache 하는 것은 설득력을 잃었다.

넷째, application과 file system API를 함께 설계하는 것은 flexibility를 높인다는 점에서 전체 system에 이득을 준다. 예를 들어 GFS는 file system을 매우 단순화하기 위해서 GFS의 consistency model을 단순화 하였다. 또한 다수의 client들이 추가적인 동기화 없이도 파일에 access 할 수 있도록 atomic append operation을 도입하였다.

여러 GFS cluster들은 현재 다른 목적으로 배포되었다. 가장 큰 것은 300TB 이상의 disk storage와 1000개의 node를 가지고 있는데, 별도의 machine에 있는 수백개의 client로부터 지속적으로 heavily acccess 되고 있다.

2. Design Overview 

2.1 Assumptions

file system을 설계하는 과정에서 우리는 도전과 기회를 모두 제공하는 가정을 따랐다. 우리는 이전에 몇 가지 key observations을 언급했으며 아래와 같다.

• inexpensive commodity hardware로 구성되어있으며 fail이 필연적으로 발생

• 시스템은 적당한 수의 large file을 저장한다. 100MB 이상 혹은 수 GB 파일을 저장하는 것이 common case

• workload는 두 종류의 read로 이루어져있다. large streaming read, small random read.

• workload는 또한 파일에 data를 append하는 large, sequential write로 이루어져있으며 한번 write되면 거의 수정되지 않는다.

• 시스템은 여러 client가 같은 파일에 대해 동시에 append 하는 것에 대한 잘 정의된 semantic이 필요하다.

• high sustained bandwidth가 low latency 보다 우선한다. google의 대부분의 application들이 대량의 data를 bulk로 high rate로 처리하는 것을 우선적으로 하며, 소수는 response time에 대한 조금 더 엄격한 요구사항이 있다.

2.2 Interface

GFS는 친근한 file system interface를 제공하며, POSIX와 같은 standard API를 구현하지는 않았다. 파일들은 directory 내에 hierarchical하게 구성되며 path name으로 구별된다. 지원하는 interface는 다음과 같다.

• create, delete, open, close, read, and write files

• snapshot, record append

이중 record append는 다수의 클라이언트가 한 파일에 동시 접근하는 것을 허용하면서 각 클라이언트의 append에 대한 원자성을 보장한다. 이는 multi-way merge와 producer-consumer queue에 유용하다. 이러한 성질을 가진 파일은 large distribtued application을 구현하는 데 매우 유용하다.

2.3 Architecture

Fig 1은 GFS cluster를 나타낸다. GFS cluster는 하나의 master와 여러 chunkserver로 이루어져 있으며 여러 client에 의해 access되며 각각은 상용 linux machine에서 user-level server process로 동작한다.

file들은 고정된 크기의 chunk로 나뉘어지며, 각각의 chunk는 immutable, global한 64bit의 chunkhandle(id)를 가지며 chunk 생성 시에 master가 할당한다. reliability를 위해서 각 chunk는 여러 chunkserver에 replication된다. replication factor의 default는 3이지만 file namespace의 서로 다른 region에 대해서 임의로 replication level을 지정할 수 있다.

master는 모든 file system의 metadata를 관리한다. 이는 namespace, access control 정보, file에서 chunk로의 mapping, chunk들의 현재 위치를 포함한다. master는 또한 chunk lease management, orphaned chunk에 대한 garbage collection, chunkserver 간 chunk migration 등 모든 system-wide activities를 control 한다.

GFS client는 file system API를 구현한 application과 연결되어 있으며 application을 대신하여 master, 각 chunkserver와 통신한다. master와 metadata operation을 수행하여 chunkserver와 data-bearing communication을 직접 수행한다.

client와 chunkserver는 둘 다 file data를 caching하지 않는다. client cache는 거의 이점이 없는데 대부분의 application은 거대한 file을 단순히 stream하거나 혹은 cache하기에 너무 크기 때문이다. cache하지 않음으로써 cache coherence issue가 없게 되고 그 결과 client와 전체 system이 단순해진다. chunkserver는 file data를 cache할 필요가 없는데 chunk는 local file에 저장되어 있어 linux buffer cache는 이미 자주 access되는 data에 대해 memory에 cache를 하고 있다.

2.4 Single Master

단일 master 구조는 디자인을 단순화시키고 master로 하여금 정교한 chunk placement와 global knowledge을 사용한 replication decision을 가능하게 하였다. 하지만 master가 read/write에 최소한으로 개입하여 master를 통한 bottleneck을 방지해야 한다. client는 master를 통해 read/write 하지 않으며, 대신에 client는 master로부터 data를 주고받기 위해 어떤 chunkserver와 접촉해야 하는지에 대한 정보를 얻는다. Fig 1는 read를 하기 위해서 client와 master, chunkserver가 어떤 방식으로 interact 하는지 나타냈다.

2.5 Chunk Size

chunk size는 핵심 design parameter 중 하나이다. GFS에서는 64MB로 정하였는데, 보통 file system의 block size보다 아주 크다. chunk replica는 각 chunkserver에 plain linux file로 저장되며 필요한 경우에만 확장된다. lazy space allocation은 internal fragmentation으로 인한 space 낭비를 방지한다.

큰 chunk size는 아래와 같은 이점을 지닌다.

1) read/write가 동일한 chunk에 주로 발생하게 함으로써 master와의 interaction을 줄인다. 이러한 효과는 read/wrtie가 sequential 하게 발생하는 application에서 극대화된다.

2) 동일한 chunkserver에 접근하면서 TCP connection을 persistent하게 유지하여 network overhead를 줄인다.

3) master가 가지고 있어야 할 metadata 크기를 줄일 수 있고 memory에 적재함으로써 여러 이점을 얻는다.

반면 lazy space allocation에도 불구하고 한계점도 가지고 있다. application에서 다수의 client가 어떤 특정 chunk에 대한 access rate가 높아지면 해당 chunkserver는 hot spot이 된다. GFS에 대한 테스트를 수행하면서 이 문제가 발견되었는데 해당 파일에 대한 replication factor를 높이고 application 수행 시점을 분산시킴으로써 병목을 완화함으로써 해결하였다.

2.6 Metadata

master는 세가지 주요 metadata를 저장한다.

1) file and chunk namespaces

2) mapping from files to chunks

3) locations of each chunk's replicas

이중에서 위 두개는 memory에 저장되면서 또한 mutation에 대한 operation log를 local disk, remote machine에 persistent하게 저장한다. operation log를 남김으로써 master update를 단순하고 신뢰성있고 일관성있게 할 수 있다. 반면 chunk replica에 대한 location은 persistent 하게 저장하지 않고 chunkserver가 시작하면서부터 그에 대한 정보를 주기적으로 반영한다.

2.6.1 In-Memory Data Structure

metadata를 memory에 저장함으로써 master operation은 신속하게 이루어질 수 있다. 게다가 background에서 master의 상태를 주기적으로 scan하기에도 유리하다. 이 주기적인 scan은 chunk garbage collection, chunkserver failure에 따른 re-replication, load과 disk usage의 balance를 위한 chunk migration을 위해 이루어진다.

memory-only approach에 대한 잠재적인 문제로 chunk의 개수가 많아지면서 memory capacity 부족이 있을 수 있다. 하지만 practical 하게 전혀 문제가 되지 않는데 64MB chunk를 위해서 master는 단순히 64 bytes가 되지않는 metadata를 저장하고 있기 때문이다.

정말로 memory 확장이 필요하다면 이 대량의 cluster에 대해서 memory를 scale up 하는 것은 그다지 문제가 되지 않는다.

2.6.2 Chunk Locations

master는 어떤 chunkserver가 chunk에 대한 replica를 가지고 있는지 persistent 하게 저장하지 않는다. master는 단순히 chunkserver의 startup부터 poll 하고 있으며 주기적인 heartbeat를 보내어 상태를 monitor 및 update한다.

GFS 설계 초기에는 persistent하게 저장하려고 하였으나, 위와 같은 poll 방식이 훨씬 단순하게 접근하다고 결정하였다. 이는 master와 chunkserver 간 sync 문제를 제거했다.

이 design을 더 단순하게 이해하는 다른 방식은 어떤 chunk에 대한 final word, 즉 최종 책임자는 chunkserver라는 것을 깨닫는 것이다. 이 같은 방식에서는 chunkserver 내에서도 얼마든지 실패할 수 있기에 master가 일관된 view를 가지고 있어야 할 지점이 없다.

2.6.3 Operation Log (*) 

operation log는 중요한 metadata 변경에 대한 historical record이며 GFS의 핵심이다. operation log는 metadata의 persistent record이자 cocurren operation에 대한 논리적인 시간 순서를 제공한다.

operation log는 중요하기 때문에 신뢰성 있게 저장되어야 하며 metadata가 persistent하게 저장되기 전까지 client에 보여지면 안된다. 여러 remote machine에도 저장되며 해당 log가 local disk 및 remote machine에 모두 flush 한 다음에 client에 응답한다.

master는 file system을 operation log를 replay함으로써 복원한다. 시작 시간을 줄이기 위해 log를 작게 유지해야 하는데, master는 operation log 크기가 커질 때마다 checkpoint를 갱신하여 가장 최신의 checkpoint를 load 하고 남아있는 log record를 실행하여 이를 가능하게 한다. checkpoint는 compact B-tree에 있어 신속한 접근이 가능하다.

checkpoint를 생성하는 데는 시간이 소요되므로 master의 내부 상태는 새로운 checkpoint가 incoming mutations에 대한 지연이 없이 생성될 수 있도록 구성되어 있다. master는 새로운 log file로 별도의 thread를 통해 switch 하며 이 log file은 checkpoint 이전 시점에 발생한 모든 mutation을 반영한다.

2.7 Consistency Model (*) 

GFS는 google의 distributed application을 지원하기 위해 완화된 consistency model을 가지고 있다. 우리는 GFS의 guarantee와 이것이 application에 무엇을 의미하는지 이야기 할 것이다.

2.7.1 Guarantee by GFS

file namespace mutation.

file namespace mutation은 atomic 하며 master에 의해 exclusive 하게 이루어진다. namespace locking은 atomicity와 correctness를 보장하며 master operation log는 이들 operation의 전체 순서를 정의한다.

data mutation 이후의 file region의 상태는 mutation의 type, 성공 여부, cocurrent 여부에 따라서 달라진다. table 1에서 이를 나타내고 있다.

consistent: all clients will see always the same data.

defined: consistent + reflect all cocurrent mutations.

전형적으로, concurrent mutations에 따른 data는 mutations이 적용된 일부분으로 이루어져있다. 실패한 mutation은 region을 inconsistent하게 만들며 서로 다른 client가 다른 data를 볼 수 있다. 아래에서 application이 defiend region과 undefined region을 어떻게 구분하는지 살펴보겠다.

data mutations.

write: write data at an application-specified file offset.

record append: append data atomically at least once even in the presence of concurrent mutations, but at an offset of GFS's choosing.

일련의 mutations가 발생한 다음에도 대상 mutate file region은 defined가 보장되며 마지막 mutation에 의한 data를 가지고 있다. GFS는 다음의 방법으로 이를 가능하게 한다.

a) chunk에 대한 mutations을 모든 replica에 동일한 순서로 적용한다.

b) chunk version number을 사용하여 chunkserver의 fail에 따른 stale한 상태의 chunk를 확인한다.

client는 chunk location을 cache하고 있기 때문에 stale replica로부터 read를 할 수 있다. 이는 cache entry의 timeout 만큼, 그리고 다음 file을 open 하기 전까지로 한정된다. 그리고 대부분의 파일이 append-only이기 때문에 outdated data를 보기보다는 prematured end를 return 한다. (따라서 application의 부작용에 대한 영향도도 제한된다는 의미로 해석)

여러 mutation 이후에 component failure는 data는 corrupt 혹은 destroy 시킬 수 있다. GFS는 master와 chunkserver 간 주기적인 handshake로 이를 확인하며 checksum을 통해 data corruption을 detect 한다.

2.7.2 Implications For Applications

GFS application은 몇가지 단순한 technique으로 완화된 cosistency model을 수용할 수 있다. 이 technique들은 다른 목적을 위해 이미 필요한 것들이며 아래와 같다.

relying on appends rather than overwrites, checkpointing, writing self-validating, self-identifying record.

전형적인 사용 예로서, 단일 writer가 file을 시작부터 끝까지 다 생성한다. data를 모두 write 한 다음 atomic하게 파일 이름을 변경하거나, 주기적으로 얼만큼 write 되었는지 주기적으로 checkpoint한다. checkpoint는 application-level checksum을 포함하여 reader는 마지막으로 defined state가 된 file까지만 읽는다.

다른 전형적인 사용 예로, 여러 writer가 merged result 혹은 producer-consumer를 위해 동시에 file에 append 하는 경우가 있다. record append의 at-least-once semantic은 writer의 ouput을 보존하며 reader는 그에 따른 padding이나 duplicate를 다룬다. 각 record에는 verification을 위한 checksum 등이 준비될 수 있으며 reader는 application에서 padding, duplicate를 filtering 할 수도 있다.

3. System Interactions

GFS는 master의 개입을 최소한으로 하는 system을 디자인되었으며 client, master, chunkserver가 어떻게 상호작용하는지 살펴보자.

3.1 Leases and Mutation Order

mutation은 chunk의 contents나 metadata를 변경시키는 동작이다. 각 mutation은 chunk의 replica 모두에 적용된다. GFS에서는 여러 replica에 일관성 있는 mutation order를 적용하기 위해서 lease 개념을 도입하였다. master는 chunk의 한 replica에 lease를 부여하며 이 replica는 primary라 불린다. primary에서는 mutation들에 serial number를 적용하며 나머지 replica인 secondary는 모두 이 순서를 따른다. lease 메커니즘은 master의 management overhead를 최소화하기 위해 디자인되었다. 초기 timeout은 60초이지만 chunk가 mutate 되고 있는 동안에는 무기한으로 늘어날 수 있다. 이를 위한 신호는 master, chunkserver 간 heartbeat에 piggyback 된다.

Figure 2는 write를 위한 control flow를 나타낸다.

1) client는 master에게 현재 lease를 가지고 있는 chunkserver와 (primary) 다른 replica의 location 정보(secondary)를 요청한다. lease가 아직 부여되지 않았으면 replica들 중 하나에 부여한다.

2) master는 client에 primary, secondary에 대한 정보를 반환한다.

3) client는 모든 replica에 data를 push 한다. 각 chunkserver는 data가 저장되거나 age out 될 때까지 내부 LRU buffer cache에 저장한다. data flow와 control flow를 decouple 함으로써 값비싼 data flow에 대한 scheduling을 함으로써 performance를 증대한다.

4) 모든 replica가 ack를 보내면 client는 write request를 보낸다. primay는 연속적인 mutations들에 serial number를 할당하고 그 순서에 맞게 적용한다.

5) priamry는 secondary에 write request를 forward하고 모든 secondary는 그 순서에 맞게 mutations을 적용한다.

6) 모든 secondary가 primary에 응답하면 operation을 완료한 것이다.

7) primary는 client에 응답한다. 어떤 에러가 발생하여 clien 실패가 발생할 수 있다. 실패한 region은 primary 및 secondary의 부분 집합일 수 있으며 수정된 region에서는 inconsistent한 상태가 된다. client는 retry를 통해 실패한 mutations 부터 다시 write를 시도한다.

write가 용량이 클 때는 여러 write operation으로 나누어서 처리한다. 모든 replica에서 각 operation을 잘 처리하여서 identical 하더라도 공유된 file region은 fragment를 가지고 있을 수 있다. 이는 file region이 consistent 하지만 undefined state에 있게한다.

3.2 Data Flow

우리는 network를 효율적으로 활용하기 위해서 data flow와 contorl flow를 분리하였다. control flow는 client에서 primary로, 그다음 secondary로 전되는 반면, data flow는 잘 채택된 chunkserver의 pipelined chain에 선형적으로 push된다. 목적은 각 machine의 bandwidth의 사용을 극대화하고, network bottleneck과 high-latency link를 피하고 모든 data를 push하는 데 필요한 latency를 최소화하는 것이다.

또 TCP connection 상에서 data trasfer를 pipeline 함으로써 latency를 최소화했다. chunkserver가 data를 일단 받으면 바로 chaining된 replica에 바로 forward를 시작한다. network 혼잡이 없다는 가정 하에 이상적인 elapse time은 아래와 같다.

B/T + RL (B: transferred bytes, T: network throughput, R: replicas, L: latency between two machines)

3.3 Atomic Record Appends

GFS는 record append라는 atomic append 동작을 지원한다. traditional write에는 client가 offset을 명시적으로 지정해야 하고, 따라서 같은 region에 대한 concurrent write가 불가능하다. 반면 record append는 client는 offset 없이 data만 지정을 한다. GFS는 data를 GFS가 정한 offset에 at-leas-once, atomic 하게 append 한다. client는 여러 client들 간 동기화 없이도 같은 file에 대해서 atomic하게 record append 하는 것이 가능하다.

record append가 어떤 replica에서 fail 한다면 client는 해당 동작을 retry 할 것이다. 그 결과 같은 chunk에 대한 replica들은 duplicate를 포함한 서로 다른 data를 가지고 있을 수 있다. GFS는 모든 replica가 bytewise로 같을 것을 보장하지 않는다. 단지 data가 atomic unit에 대해 at-lease-once로 write 되는 것을 보장한다. 우리의 consistency 보장에 따르면 성공적으로 record append한 region은 defined 상태이고 중간에 intervene 된 region은 inconsistent 상태이다. application에서는 2.7.2에서 언급한대로 inconsistency를 다룰 수 있다.

3.4 Snapshot

snapshot 동작은 file이나 directory tree의 copy를 만들며, 이는 진행 중인 mutations에 대한 방해를 최소화하면서 거의 즉시 이루어진다.

AFS처럼 GFS에서는 snapshot을 구현하기 위해 copy-on-write technique이 사용된다. snapshot은 다음 순서로 이루어진다.

1) master가 snapshot 요청을 받으면 먼저 snapshot의 target이 되는 chunk의 lease를 revoke 시킨다. 이는 그 다음 들어오는 write가 master와 interaction 하도록 강제하며, master가 새로운 copy를 만들 수 있을 기회를 준다.

2) lease가 revoke 혹은 expire되면 master는 disk에 이 동작을 log로 남긴다. 그 다음 source file이나 directory tree의 metadata를 복제함으로써 이 log를 in-memory 상태에 적용한다.

3) client에서 current lease holder에 대한 요청이 올 때 master는 chunk C에 대한 reference count가 1보다 큼을 알아차린다. master는 client의 요청을 defer 시키며 새로운 chunk C'를 선택한다.

4) 그다음 각 chunk C를 들고 있는 chunkserver에게 새로운 C'를 만들라 요청한다. C'을 local에서 복제함으로써 아주 빠르게 이루어진다.

5) 이 시점에서 request handling은 다른 요청과 다르지 않다. master는 C'에 대해 lease를 grant 함으로써 client가 C'에 대해서 아무런 인지 없이 정상적으로 사용할 수 있도록 한다.

References 

- Sanjay Ghemawat, Howard Gobioff, & Shun-Tak Leung (2003). The Google File System. In Proceedings of the 19th ACM Symposium on Operating Systems Principles (pp. 20–43).

- https://courses.cs.washington.edu/courses/cse490h/11wi/CSE490H_files/gfs.pdf

- https://cs.stanford.edu/~matei/courses/2015/6.S897/slides/gfs.pdf

2편에서 계속...

[Paper Review] The Google File System -2