<The Google File System> 논문 정리

2014-10-28 <The Google File System> 정리

 

 

슬라이드 몇 장으로 할 것인가: 15장 + 1장(소개) + 2장(첫 장, 끝 장)

영어로 구성할 것인가: 영어로.

핵심 내용은 한글로 정리:

 

밑줄은 어디에 그을 것인가. 조사해야 할 개념에 밑줄.

 

1~5

Abstract

 무정지 기능(failure tolerance)과 군집성능(high aggregate performance) 제공.

 앞으로 예측 되는 어플리케이션의 부하와 기술적 환경에 중점을 두고 새로운 파일 시스템을 설계했다.

 여기서는 분산 어플리케이션을 지원하기 위해 설계된 파일 시스템 인터페이스 확장을 소개하고, 이 설계의  다양한 측면과 실제 상황과 이론상의 벤치마크결과에 대해 이야기하려고 한다.

 

1. INTRODUCTION

우선, 구성요소(component)의 오류는 당연하다고 간주한다.

기존에 비해 훨씬 증가한 파일들의 크기이다. 

대부분의 파일이 새로운 데이터에 의해 덮어쓰여지는 것이 아니라 추가확장되어간다는 점이다.

한번 작성된 파일은 단순히 읽기만 가능하며 대부분 순차적으로만 읽혀진다. 

이러한 파일접근방식이 대용량의 파일에 적용된다고 가정하면, 기능 향상과 원자성 보장(atomicity guarantee)을 위해서 중점을 두어야 할 부분은 클라이언트의 데이터 블록 캐슁 알고리즘이 아니라 파일의 확장(appending) 알고리즘이라는 것을 알수 있다.

어플리케이션과 파일 시스템 API를 같이 설계한다는 것은 유연성 측면에서 전체 시스템의 효율을 높여준다. 

느슨한 GFS의 일관성 규약(consistency model)덕분에  어플리케이션 쪽에 귀찮은 여러 제약을 부가하지 않고 대단히 단순화된 파일 시스템을 구현할수 있었다.  또한 아토믹 어펜드 (atomic append) 기능은 별도의 동조화(synchronization)를 필요로 하지 않고도 복수의 클라이언트가 동시에 하나의 파일에 추가할수 있도록 한다.

 

2. Design Overview

2.1 Assumptions

시스템에 걸리는 부하는 대량 스트리밍 읽기와 소량 랜덤 읽기, 두 종류의 읽기 동작이 주가 된다. .

 대량의 스트리밍 읽기에서는 각각의 동작(operation)이 수백 킬로바이트 혹은 1메가바이트 이상을 읽어들이게 되고, 동일한 클라이언트에 의한 연속되는 동작은 주로 그 파일의 연장영역에서 읽어오게 된다.  소량의 랜덤 읽기는 임의의 좌표에서 수 킬로바이트단위를 읽게 된다.  속도가 중요한 어플리케이션의 경우엔 대부분, 매번 앞뒤로 읽기 작업을 행하는 것 보다 여러 랜덤 읽기 작업을 모아서 정렬후 일괄적으로 읽어들이는 방식을 취한다.

부하에는 또한 파일에 데이터를 추가하는 대량의 순차적 쓰기도 포함된다.  

• 시스템은 반드시 복수의 클라이언트가 동일한 파일에 동시에 자료를 추가하는 것을 지원하도록 명확히 정의된 언어체계를 갖추고 있어야 한다.  이러한 파일들은 종종 제작자와 소비자 사이의 연결고리(queue)나 다방향 병합(many-way merging)에 사용된다.
• 신속한 반응속도(low latency) 보다는 고부하를 견뎌낼수 있는 대역(bandwith) 유지가 더 중요하다. 실제 대상이 되는 어플리케이션은 일부 개개 요청에 대한 응답시간을 엄격히 지켜야 하는 경우를 제외하고 대부분 데이터를 대용량 고속처리하는것에 더 큰 비중을 두고 있다.

 

2.2 Interface

 GFS는  POSIX와 같은 표준 API를 보유하고 있지는 못하지만 어느정도 친숙한 파일 시스템 인터페이스를 제공한다.

GFS는 스냅샷 기능과 레코드 추가 기능을 지원한다. 

스냅샷: 복사본을 간단히 만들 수 있는 기능

레코드 추가 기능은 복수의 클라이언트가 추가하려는 각 데이터의 내용을 보장하면서 동시에 모든 클라이언트가 하나의 파일에 그 데이터들을 추가할 수 있도록 해준다.

 이런 구조는 여러 곳에서 생성된 결과보고서를 다방향 병합하는 경우나, 복수의 클라이언트가 파일을 잠그지 않고 (lock) 동시에 데이터를 추가해야 하는 생산자-소비자 연결에 사용될 수 있다. 

 

2.3 Architecture

파일들은 고정된 크기의 조각(chunk)들로 나뉘어 저장된다.  각각의 조각은 서버 전체를 걸쳐 고유의 64비트 조각 번호 (chunk handle)을 마스터로부터 생성시 부여받게 되고 이 번호는 절대로 변경될 수 없다. 

마스터는 모든 파일 시스템의 메타데이터를 관리한다.  여기에는 네임스페이스, 접근 조절 정보, 파일 조각 매핑과 각 조각의 현재 위치등이 포함되며, 마스터는 또한 조각 임대(lease) 관리, 연결이 유실된 조각(orphaned chunk)의 유휴메모리 정리 (garbage collection), 조각 서버들간의 조각 이동과 같은 시스템 수준 동작을 관리한다.  마스터는 주기적으로 각각의 조각서버와 맥박신호(heartbeat message)를 교환함으로써 명령을 전달하고 각 서버의 상태를 수집한다.

GFS 클라이언트 코드는 이 파일시스템 API를 적용하고 있는 각각의 어플리케이션과 링크되어 어플리케이션전반에 걸친 마스터와 조각서버간의 통신에 관여하게 된다.  클라이언트는 마스터와 통신하며 메타데이터 관련 작업을 수행하지만 실제 데이터 관련 통신은 모두 조각서버로 직접 전달된다.  이시스템은 POSIX레벨의 API를 제공하지 않기 때문에 리눅스 v노드계층을 후크할 필요가 없다.

클라이언트나 조각서버 어느쪽도 파일 데이터를 캐쉬하지 않는다.  대부분의 어플리케이션은 거대한 파일의 스트림을 읽어들이거나 캐쉬하기에 너무 큰 사이즈의 데이터를 다뤄야 하기 때문에 클라이언트의 캐쉬는 거의 유용성이 없으므로, 클라이언트에서 캐슁 기능을 제거해서 시스템 전반의 동조화에 관련된 문제점을 해결할 수 있다. (메타데이터는 클라이언트 캐쉬에 저장딘다)  각각의 조각 파일은 로컬 파일로 저장되므로 리눅스의 버퍼캐쉬가 지속적으로 메모리에 데이터를 저장하기때문에 조각서버 역시 파일 데이터를 캐쉬에 저장할 필요가 없다.

 

2.4 Single Master

 master는 메타데이터만 클라이언트에게 제공하고 파일 제공은 하지 않는다. 이로서 병목현상을 해소한다.

가장 단순한 형태의 읽기 작업을 그림1과 함께 설명해보면, 우선 클라이언트는 지정된 조각 사이즈에 따라 어플리케이션이 배정한 파일의 이름을 분석하고 파일내의 조각 인덱스 오프셋을 계산한다. 그러고나서 마스터에게 파일이름과 조각인덱스를 포함한 요청을 전송하면 마스터는 해당 조각핸들과 복제의 위치를 반환하게되는데, 클라이언트는 이정보를 파일이름과 조각인덱스를 키로 삼아 캐쉬에 저장한다.

  클라이언트는 이후 복제중 하나 - 대부분 가장 가까운 복제 - 에 요청을 보낸다.  이 요청은 조각 핸들과 그 조각 내의 구체적인 바이트 범위를 포함하는데, 동일한 조각에 대한 읽기 작업은 캐쉬에 저장된 이 정보가 만료가 되거나 파일이 다시 열리기 (reopened) 전에는 마스터와의 통신이 필요없게 된다.

 

2.5 Chunk Size

 

비적극적인 공간배치 알고리즘 (lazy space allocation)을 사용하여 대형 사이즈의 조각을 사용함으로써 야기될수 있는 가장 큰 문제중 하나인 내부 파일 조각화에 의한 공간 낭비를 줄였다.

장점; 클라이언트가 조각 정보에 관해서 마스터와 통신해야 하는 횟수를 줄여준다. 클라이언트가 해당 조각 내에서 더 많은 작업을 수행할 수 있다. 고정된 TCP연결을 유지해야할 필요가 없어 네트웍의 부하를 줄일 수 있다. 전체 메타데이터의 크기를 작게 만들어 준다.

단점: 이 파일을 동시에 여러 클라이언트가 접근할 경우 이러한 조각을 저장하는 조각서버는 분쟁지역(hot spot)화 할 수 있다. 분쟁 지역 발생 문제는 GFS가 초기 일괄 처리 시스템 (batch-queue system)에 적용되었을때 발견되었는데,

 더 높은 복제율로 저장하도록 하고 각각의 일괄 처리 시스템들은 어플리케이션의 실행 시점을 미묘하게 다르게 갖도록 했다.  좀 더 근본적인 해결책으로는 클라이언트가 이런 분쟁지역이 발생할 경우 다른 클라이언트로부터 데이터를 읽어들이도록 하게 하는 것일 것이다.

 

2.6 Metadata

마스터에는 파일과 조각의 네임스페이스, 파일과 조각간의 매핑 정보, 그리고 각 조각의 복제들의 위치정보, 크게 이 세가지의 메타데이터가 저장된다.  

 

2.6.1 In-Memory Data Structures

최악의 경우 거대한 파일 시스템을 구성하기위해 메모리가 부족한 경우라 할지라도, 마스터에 추가로 메모리를 확장하는 것은 모든 메타데이터를 메모리에 저장함으로써 얻을 수 있는 간편함과 안정성, 속도, 가변성을 생각하면 저렴한 비용이라고 간주할 수 있을 것이다.

이러한 설계가 수백개이상의서버로구성된클러스터에서는흔하게발생할수있는 문제들 - 조각서버들이클러스터에추가되거나삭제되고,이름을바꾸거나오류발생,재기동등의문제 - 속에서도 마스터와조각서버간의동기를맞추는작업을간편하게할수있다.

 

2.6.3 Operation Log 부터 시작.

 작업 로그는 메타데이터에 대해 치명적일 수 있는 변경의 순차적 기록을 저장한다.

파일과 조각들은 버전을 포함해서 (4.5항 참조) 모두 생성된 논리적 시간대에 의해서 단일하고 영구적으로 구분된다.

작업로그는 원격 기기에 다시 복제되어 해당하는 로그 기록을 로컬과 원격 모두의 디스크에 갱신을 마친후에 클라이언트 작업에 응답하도록 한다.

마스터는 이 작업 로그를 다시 수행함으로써 파일시스템의 상태를 복구한다.  재기동 시간을 줄이기 위해서는 로그의 크기가 작도록 유지해야하는데, 마스터는 로그가 특정 크기를 넘어설때마다 기록을 해두고 (checkpoint) 복구시에는 이것을 로컬 디스크에서 읽어들여서 다시 수행해야 하는 로그 기록의 갯수를 최소화 한다.  이 기록은 메모리에 직접 저장할 수 있는 압축된 B트리 형태로 저장되어 추가적인 분석과정 없이도 네임스페이스 검색에 이용될 수 있다.

기록을 작성하는 동안에 발생한 오류는 복구코드가 자동으로 검색하여 불완전하게 종료한 기록들을 무시하기 때문에 전체 데이터의 무결성에 영향을 미치지 않는다.

 

2.7 Consistency Model

 GFS는 우리의 고도로 분산된 어플리케이션들을 완벽하게 지원하면서도 비교적 적용이 단순하고 효율적일수 있도록 그다지 엄격하지 않은 일관성 모델을 (relaxed consistency model) 갖추고 있다. 

 

2.7.1 Guarantees by GFS

 

파일 네임스페이스의 변경은 - 예를들어 파일의 생성과 같은 - 각각의 원자성을 가진다.  이것들은 마스터에의해서만 처리될수 있다: 네임스페이스의 잠금 기능이 원자성과 정확성을 보장한다

 데이터 갱신 이후의 파일 영역 상태는 그 갱신 작업의 종류와 갱신 성공 여부, 또 병렬로 진행된 또 다른 갱신작업의 유무에 따라 달라진다.  여기서 가능한 모든 경우를 테이블 1에 요약해 보았다. 

파일 영역은  일정(consistent) 상태,

정의(defined)

일정하지 않은 상태(inconsistent) 또한 이는 동시에 미정의상태(undefined)이 기도 하다.)

Stale replicas are garbage collected at the earliest opportunity.

 

5p

 

2.7.2 Implications for Applications

the relaxed consistency model

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

it can filter them out using unique identifiers in the records, These functionalities for record I/O

 

3. SYSTEM INTERACTIONS

We designed the system to minimize the master’s involvement

in all operations.

 

3.1 Leases and Mutation Order

The master grants a chunklease to one of the replicas, which we call the primary.

the global mutation order is defined first by the lease grant order chosen by the

master, and within a lease by the serial numbers assigned

by the primary.

The lease mechanism is designed to minimize management

overhead at the master.

 

http://blog.naver.com/bacsumu/140038925093

 

http://www.slideshare.net/tutchiio/gfs-google-file-system?related=2

 

6p

 3.2 Data Flow

To avoid network bottlenecks and high-latency links (e.g.,

inter-switch links are often both) as much as possible, each

machine forwards the data to the “closest” machine in the

networkto pology that has not received it.

Finally, we minimize latency by pipelining the data transfer

over TCP connections.

Once a chunkserver receives some

data, it starts forwarding immediately. Pipelining is especially

helpful to us because we use a switched networkwit h

full-duplex links.

3.3 Atomic Record Appends

This is similar to writing

to a file opened in O APPEND mode in Unix without the

race conditions when multiple writers do so concurrently.

 

7p

distributed lock manager.

with traditional writes. In our workloads, such files often

serve as multiple-producer/single-consumer queues or contain

merged results from many different clients.

The client pushes the data to all replicas of the

last chunko f the file Then, it sends its request to the primary.

The primary checks to see if appending the record

to the current chunkw ould cause the chunkto exceed the

maximum size (64 MB)

If a record append fails at any replica, the client retries the

operation.

It only guarantees that the

data is written at least once as an atomic unit.

3.4 Snapshot

The snapshot operation makes a copy of a file or a directory

tree (the “source”) almost instantaneously, while minimizing

any interruptions of ongoing mutations.

4.1 Namespace Management and Locking

Therefore,

we allow multiple operations to be active and use locks over

regions of the namespace to ensure proper serialization.

GFS does not have a per-directory data structure

GFS

logically represents its namespace as a lookup table mapping

full pathnames to metadata.

8p

Since the namespace can have many nodes, read-write lock

objects are allocated lazily.

Also, locks are acquired in a consistent total order

to prevent deadlock: they are first ordered by level in the

namespace tree and lexicographically within the same level.

4.2 Replica Placement

The chunk replica placement policy serves two purposes:

maximize data reliability and availability, and maximize network b

andwidth utilization.

4.3 Creation, Re-replication, Rebalancing

Chunk replicas are created for three reasons: chunk creation,

re-replication, and rebalancing.

chunk creation - 1) below-average disksp ace utilization. 2) limit the number of “recent” creations(

creation itself is cheap, it reliably predicts imminent heavy write traffic), 3) spread replicas of a chunkacross racks.

re-replicates - a chunkserver becomes unavailable / Finally, to minimize the impact of failures on running applications,

rebalances - moves replicas for better disks pace and load balancing.

4.4 Garbage Collection

It does so only lazily during regular garbage collection at both the file and chunk levels.

4.4.1 Mechanism

the file is just

renamed to a hidden name that includes the deletion timestamp.

파일의 이름을 삭제 시간으로 바꾸고 히든파일로 만든다. 3일뒤에 삭제.

three days

orphaned chunks - HeartBeat message

4.4.2 Discussion

the main disadvantage:

Applications that repeatedly create and delete

temporary files may not be able to reuse the storage right

away.

9p

4.5 Stale Replica Detection

the master maintains a chunk version number

to distinguish between up-to-date and stale replicas.

The master removes stale replicas in its regular garbage

collection.

5. FAULT TOLERANCE AND DIAGNOSIS

5.1 High Availability

two simple yet effective

strategies: fast recovery and replication.

5.1.3 Master Replication

The master state is replicated for reliability.

Moreover, “shadow” masters provide read-only access to

the file system even when the primary master is down.

They are shadows, not mirrors.

 

10p

5.2 Data Integrity

each chunkserver must independently verify the integrity of its own copy by maintaining

checksums.

If a block does not match the recorded checksum, the chunkserver returns an error to the requestor

and reports the mismatch to the master

In response, the requestor will read from other replicas, while the master

will clone the chunk from another replica.

If we do not verify the first and last blocks before overwriting them

partially, the new checksums may hide corruption that exists

in the regions not being overwritten.

5.3 Diagnostic Tools

diagnostic logging

6. MEASUREMENTS

연구환경

one master, two master replicas, 16 chunkservers, and

16 clients.

 

11p

6.1.1 Reads

125 MB/s when the 1 Gbps link

The aggregate read rate reaches 94 MB/s (

because as the number of readers increases,

so does the probability that multiple readers simultaneously

read from the same chunkserver)

 

12.5 MB/s per client when its 100 Mbps

network

 

6.1.2 Writes

6.2 Real World Clusters

6.2.1 Storage

6.2.2 Metadata

prefix-compressed form

12p

6.2.3 Read and Write Rates

6.2.4 Master Load

therefore is not a bottleneckfor these workloads.

6.2.5 Recovery Time

40% of the number of chunkservers)

where each clone operation is allowed to consume at most

6.25 MB/s (50 Mbps). All chunks were restored in 23.2 minutes,

6.3 Workload Breakdown

6.3.1 Methodology and Caveats

13p

6.3.4 Master Workload

14p

7. EXPERIENCES

a variety of issues, some operational and some technical.

biggest problems were diskan d Linux related.

 ex. Linux 2.2 kernels - fsync()명령어. a single reader-writer lock 문제. mmap(), pread() 명령어

 

- conclusion

the qualities essential

GFS는 다수의 저가형 상용 하드디스크를 활용해서 분산 컴퓨팅 환경 구축을 위한 필수 품질을 구현했다.

design decisions

설계상의 결정은 구글의 특수한 설정에 맞도록 했지만, 많은 부분 대규모 분산 처리 시스템에 유효하다.

reexamining traditional file system -> different points in the design space

기존의 파일 시스템에 대한 재평가와 더불어 디자인 공간에서의 다른 점들을 찾았다.

다른점 - component failures > exception , huge files, append > read 

 -> file system interface to improve the overall system.

무정지 서비스 제공 fault tolerance - monitoring + replicating data + recovery +@ checksumming.

동시 접속 상에서의 퍼포먼스 보장 high aggregate throughput

기술적 기반 - separating file system control: master, chunkservers and clients.

no bottleneck

 

결론.

GFS는 저렴한 기기들로 구성된 파일 시스템의 필수 품질을 예증했다.

 

# Summary

 

ABSTRACT

• file system interface extensions designed to support distributed applications

분산 어플리케이션 지원을 위한 파일 시스템 인터페이스 확장

Keywords

• Fault tolerance, scalability, data storage, clustered storage

 

1. INTRODUCTION

• First, component failures are the norm rather than the exception.

Therefore, constant monitoring, error detection, fault tolerance, and automatic recovery must be integral to the system.

• Second, files are huge by traditional standards.
• Third, most files are mutated by appending new data rather than overwriting existing data.

대부분의 파일들은 새로운 데이터를 추가하는 작업이 덮어쓰는 작업보다 많다.

Design assumptions and parameters such as I/O operation and blocksizes have to be revisited.

• Fourth, co-designing the applications and the file system API benefits the overall system by increasing our flexibility.
• Main Purpose: over 1000 storage nodes, over 300 TB of diskst orage, and are heavily accessed by hundreds of clients on distinct machines on a continuous basis.

 

2. DESIGN OVERVIEW

 2.1 Assumptions

• inexpensive commodity components -> fail -> monitor & recover
• We expect a few million files, each typically 100 MB or larger in size. (optimized for Multi-GB files)