CAP Theorem in Google File System

Introduction

GFS에서는 시스템 디자인을 할 때 기존의 방식을 재검토했던 4가지를 소개합니다.

• First, component failures are the norm rather than the exception.
  • File System은 비싸지 않은 수많은 머신에서 수많은 Client의 요청을 받기 때문에 시스템 결함은 일반적인 현상이다.
• Second, files are huge by traditional standards. Multi-GB files are common.
  • 여러개의 객체를 다루어야할 때, 작은 여러개의 파일로 나누어서 관리하기보다, 일반적으로 하나의 큰 파일을 생성해서 관리한다.
• Third, most files are mutated by appending new data rather than overwriting existing data
  • 새로운 데이터를 일반적으로 수정보다는 추가되는 형태로 저장된다. 따라서 Random Write는 일반적으로 발생하지 않는다.
  • 성능 최적화의 관점을 Append Operation을 위주로 진행된다.
  • Client 측에서 data block 자체를 Caching하는 것은 더이상 매력적이지 않다.
• Fourth, co-designing the applications and the file system API benefits the overall system by increasing our flexibility.

여담으로 다양한 Object를 여러개의 파일로 분할해서 저장하고 있는 상황이라면, 이들을 하나의 파일에 저장해서 Read/Write를 하도록 변경하는 것만으로도 시스템 성능에 더 도움이 될 수 있겠다는 생각이 들었습니다.

Assumptions

그리고 이러한 접근방법은 시스템 디자인의 기초적인 가정으로 이어집니다. GFS에서 소개하는 각 내용 별로 인상 깊었던 부분들을 정리해봤습니다.

1. The system is built from many inexpensive commodity components that often fail. It must constantly monitor itself and detect, tolerate, and recover promptly from component failures on a routine basis.
2. The system stores a modest(보통의) number of large files. We expect a few million files, each typically 100 MB or larger in size. Multi-GB files are the common case and should be managed efficiently. Small files must be supported, but we need not optimize for them.
   • 작은 사이즈의 파일은 최적화의 대상에서 제외된다
3. The workloads primarily consist of two kinds of reads: large streaming reads and small random reads. In large streaming reads, individual operations typically read hundreds of KBs, more commonly 1 MB or more. Successive operations from the same client often read through a contiguous region of a file. A small random read typically reads a few KBs at some arbitrary offset. Performance-conscious applications often batch and sort their small reads to advance steadily through the file rather than go backand forth.
   • Individual STREAMING READ operation size : 약 수백 KB ~ 1MB
   • Individual RANDOM READ operation size : 약 수 KB
   • Performance가 중요한 Application에서는 자체적으로 small size read를 batching 처리할 것이다
4. The workloads also have many large, sequential writes that append data to files. Typical operation sizes are similar to those for reads. Once written, files are seldom modified again. Small writes at arbitrary positions in a file are supported but do not have to be efficient.
   • WRITE 또한 READ와 동일한 Operation Size를 가정함
   • Small size RANDOM WRITE를 최적화의 대상에서 제외함
5. The system must efficiently implement well-defined semantics for multiple clients that concurrently append to the same file. Our files are often used as producer-consumer queues or for many-way merging. Hundreds of producers, running one per machine, will concurrently append to a file. Atomicity with minimal synchronization overhead is essential. The file may be read later, or a consumer may be reading through the file simultaneously.
   • 최소한의 동기화로 원자성을 보장해야한다.
   • 파일의 내용은 나중에 읽힐 수도 있고 동시에 읽어질 수도 있다.
6. High sustained bandwidth is more important than low latency. Most of our target applications place a premium on processing data in bulkat a high rate, while few have stringent response time requirements for an individual read or write.
   • bandwidth가 latency보다 중요하다
   • 큰 데이터를 처리할 수 있는 것이 개별 operation의 응답시간보다 중요하다

개인적으로 5번째의 내용이 가장 인상 깊었습니다. 5번의 요구사항을 어떻게 접근해야할지 상상이 잘 되지 않았기 때문입다. 그래서 GFS의 Architecture는 다음 글에서 다루도록 하고 Consistency Model에 대해서 먼저 정리해보겠습니다.

Consistency Model

GFS에서는 조금 더 유연한 consistency model을 사용합니다. 그래서 분산 시스템을 지원하면서도 좀 더 단순하게 구현할 수 있습니다.
개인적으로 유연한 consistency model을 아래의 표를 보기 전에는 상상하지 못했습니다. consistency하면 consistency 한 것이고, 아니라면 아닌 것으로만 상상이 됐거든요.

 

 

GFS에서는 consistent의 정의를 모든 client가 동일한 데이터를 보는 것으로 정의했습니다. 대신에 client들이 어떤 버전의 replication을 read하는지는 정의하지 않았습니다. 반면 defined는 파일에 데이터 변경이 일어난 뒤, 그 변경 내용이 완전히 반영되어 클라이언트가 온전하게 읽을 수 있는 상태를 의미합니다. 예를 들어서 동일한 파일을 두 사용자가 편집하고 있을 때, 두 사용자가 서로 다른 영역을 수정하고 저장했다면 그 자체로 consistent 하며 defined 된 상태입니다. 하지만 두 사용자가 동일한 영역을 동시에 저장했다면 consistent 하지만 undefined 상태입니다. 어떤 사용자의 수정본이 두 사용자에게 동일하게 보여질지는 알 수 없습니다. Data mutation은 write 또는 append로 정의됩니다. write는 application level에서 지정한 offset에 저장되어야 합니다. append는 atomically at least once 하게 현재의 mutation 버전에 이루어짐을 의미합니다. append가 이루어지는 과정에서의 offset는 GFS에 의해서 결정됩니다.

 

GFS는 이 과정을 다음의 2가지를 통해서 달성합니다.

1. (a) applying mutations to a chunkin the same order on all its replicas (Section 3.1)
2. (b) using chunkversion numbers to detect any replica that has become stale because it has missed mutations while its chunkserver was down (Section 4.5).

오래된 replica는 mutation 작업에 관여하지 않는다고 합니다. 자세한 과정은 다음 포스팅에서 GFS의 Architecture를 다루면서 다시 확인해보겠습니다.

CAP Theorem의 관점에서

Google File Storage에게는 Consistency가 Availability보다 더 중요하게 생각된 것으로 느껴집니다. 일반적인 User의 UseCase를 생각해도 적합해보입니다. 개인적으로 Consistency를 consistent와 defined의 개념을 분리해서 접근한 것이 인상 깊습니다. consistent를 보장하기 위해서 좀 더 디테일하게 고민된 사항들은 Architecture를 다루는 글에서 정리해보겠습니다.

Reference

• Googel File System > 2.7 Consistency Model