Finding a needle in Haystack: Facebook's photo storage

Finding a needle in Haystack: Facebook’s photo storage by Doug Beaver, Sanjeev Kumar, Harry C. Li , Jason Sobel , Peter Vajgel , Facebook Inc, 2010.

최근 몇개월 동안  상대적으로 크기가 작고 많은 파일들을 비교적 단순한 솔루션을 이용해서 효율적으로 저장하는 것에 대해서 관심이 있어서 읽어본 페이퍼이다. 파일들의 개수로 인한 메모리 사용량과 복제 시간 등이 골칫거리라서 커다란 파일에 저장하는 방법을 여러가지로 검토하고 있었는데, 매우 실용적이고 깔끔한 접근으로 문제를 해결하고 있고, 실제로 개발 비용도 적게 (몇개월 정도 걸렸다고 한다) 들었으므로, 2009년 경의 시스템이지만, 서비스를 다루는 엔지니어로서는 배울 점이 있다고 생각한다.  이미지 파일 자체가 불변 데이터이므로 상대적으로 쉬운 문제인 것은 맞지만, 실제로 서비스에 적용하는 것은 또 다른 문제이다. 오픈소스화 되어 있지 않은 것이 아쉬운 점이라고 할 수 있는데 – 실리콘 밸리의 큰 회사들 치고는 의외로 Facebook은 오픈소스에 그렇게 열려있지 않은 문화인 것 같다 –  구현이 비교적 단순하기 때문인지 수많은 Haystack Clone들이 있다. 혹시 좋은 구현을 찾게되면 소개할 기회가 있을지도 모르겠다.

Problem – NFS Approach

Facebook은 NAS와 NFS를 이용하는 사진 스토리지를 구축하고 있었으며 다음과 같은 문제를 인식하고 있었다.

  • 사진을 저장할 때 전통적인 POSIX 파일시스템에서 요구하는 파일 메타데이터는 필요하지 않음.
  • 사진 파일을 읽기 위해서 3번의 디스크 오퍼레이션이 필요하고 메타데이터의 액세스가 병목이 됨.
    • 디렉토리의 blockmap이 너무 커서 효과적으로 캐시되지 않음.
  • Hot한 액세스는 CDN으로 다룰 수 있지만, long tail 성격을 가진 액세스가 있으므로, 캐싱만으로 해결할 수 없음.
  • 대체 기술들도 적합하지 않음.
    • MySQL, Hadoop
    • RAM을 늘리는 것만으로는 비효율적.

Design & Implementation

Haystack은 다음과 같은 목표를 달성해서 NFS approach의 bottleneck을 줄인다.

  • 실제 데이터를 읽기 위한 디스크 오퍼레이션을 단 1번만 필요하도록 한다.
  • 메타데이터를 위한 메모리 사용량을 줄임.

기본적인 접근 방식은 여러 사진을 하나의 커다란 파일에 저장하는 방식을 사용하는 것이다.

전체적인 시스템 구성은 Haystack Store, Haystack Directory, Haystack Cache의 3개의 서브시스템으로 이루어져 있다.

  • Store
    • Persistent storage로 파일시스템 메타데이터를 관리하는 컴포넌트.
    • Logical volume은 서로 다른 장비의 Physical volume들로 구성됨.
  • Directory
    • Logical Volume으로부터 Physical volume으로의 맵핑.
    • 각 사진들이 있는 Logical volume이나 여유공간이 있는 Logical volume을 관리한다.
  • Cache
    • 내부적인 CDN과 같은 역할.

웹서버는 디렉토리를 이용해서 URL을 구성하는데, 특이한 것은 사진의 URL에 Logical volume이나 장비에 대한 힌트 등 사진을 가져오기 위한 정보가 들어가 있다는 점이다.

  • URL은 CDN host/Cache/Machine ID/Logical volume, Photo와 같은 형태인데, CDN 또는 Haystack Cache는 (Logical volume, Photo) 정보만을 이용해서 자신의 캐시로부터 사진을 찾는다.
  • CDN이나 Cache로부터 miss일 경우에는 Cache address를 URL로부터 제거하고 Store 장비에 사진을 요청한다.

Haystack Directory

Haystack Directory는 다음과 같은 4가지 기능을 가지고 있다.

  • Logical volume을 Physical volume으로 맵핑
    • 어떤 Store 장비가 소실된 상황에서는 mapping에 상응하는 엔트리를 삭제하고 온라인이 된 새로운 머신으로 대체.
  • 쓰기 액세스를 여러 로지컬 볼륨에 대해 로드 밸런싱, 읽기 액세스를 여러 피지컬 볼륨에 대해 로드밸런싱
  • 리퀘스트가 CDN으로 핸들링되어야할지 Cache로 핸들링되어야할지 결정
  • 로지컬 볼륨이 읽기전용인지 아닌지에 대한 판단. (운영적인 이유나 용량 한계)
    • 새로운 장비를 추가하면 이 장비는 쓰기가 허용되고, 쓰기가 허용된 장비만 사진의 업로드를 받는다.

Haystack Directory는 복제가 되는 데이터베이스에 정보들을 저장하고 PHP interface로 액세스되며, latency를 줄이기 위해 memcache를 사용한다고 한다.

Haystack Cache

Haystack Cache는 Photo ID를 키로 데이터를 찾을 수 있는 Distributed hash table로 구성되어 있다. 어떤 DHT를 사용하고 있는지에 대해서는 자세히 설명되어 있지 않다. 캐시되어있지 않다면, URL에 명시되어 있는 Store 장비에서 사진을 가져온다. 캐시하는 조건이 조금 특이한데 다음과 같다.

  • 사용자로부터 직접 온 리퀘스트이고 CDN이 아닐 때: CDN에서 miss된 것이 내부 캐시에서 hit될 가능성이 낮음.
  • 쓰기가 허용된 Store 장비로부터 사진을 가져왔을 때: 사진은 업로드된 뒤에 헤비하게 액세스되므로 쓰기가 허용된 장비를 과도한 읽기 액세스로부터 보호.

Haystack Store

  • 전반적인 구조
    • 각 Store 장비는 여러 개의 Physical volume을 관리하고, 각 volume은 수백만 개의 사진을 저장한다.
      • 이를테면, Physical volume은 100GB이고, /hay/haystack…<logical volume id>와 같이 저장됨.
    • Store 장비는 Logical volume의 ID와 file offset을 이용해서 사진을 액세스할 수 있다.
    • Store 장비는 각 Physical volume에 대해 file descriptor를 유지한다.
    • Physical volume은 수퍼블럭과 needle의 sequence로 이루어져 있음.
    • needle을 빠르게 가져오기 위해서 각 볼륨에 대해 In-memory data structure를 유지하고 있음.
      • (key, alternative key) -> (needle’s flags, size in bytes, volume offset)
      • alternative key는 4개의 서로 다른 크기의 사진을 나타냄.
  • 읽기 (Photo Read)
    • 읽기 요청에는 Logical volume ID, Key, Alternative key, Cookie가 있다.
    • 사진이 업로드될 때 cookie는 랜덤하게 생성되어 Directory에 저장된다. 사진의 URL을 추측해서 액세스하는 공격을 막아준다.
    • In-memory 맵핑에서 관련된 메타데이터를 찾고, 지워진 사진이 아니라면 적절한 offset을 seek해서 전체 needle을 읽어들임.
    • 읽어들인 needle로부터 cookie를 검증하고 데이터의 integrity를 체크 후 문제가 없다면 응답.
  • 쓰기 (Photo Write)
    • 쓰기 요청에는 Logical volume id, Key, Alternate key, Cookie, Data가 있다.
    • Physical volume file에 needle image를 동기적으로 append하고, In-memory 맵핑을 업데이트 함.
    • 이미 존재하는 사진의 업데이트는 동일한 key/alternate key로 업데이트된 needle을 append하는 것으로 이루어진다.
      • 새로운 needle이 다른 Logical volume에 쓰여진다면, Directory는 애플리케이션 메타데이터를 업데이트하므로 미래의 읽기 요청은 기존 버전을 읽지 않음.
      • 새로운 needle이 같은 Logical volume에 쓰여진다면, 새로운 needle을 append함.
      • 업데이트로 인해 중복된 needle이 발생할 수 있는데, 하나의 Physical volume에서 높은 offset의 needle이 최신 버전의 needle이다.
  • 지우기 (Photo Delete)
    • In-memory 맵핑과 Volume file에 삭제 플래그를 설정.
    • 삭제된 사진에 대한 읽기 요청은 먼저 In-memory 맵핑의 플래그를 체크하고, 삭제 플래그가 설정되어 있다면 에러.
  • 인덱스 파일
    • 이론적으로는 모든 Physical volume을 읽어서 In-memory 맵핑을 복구할 수 있지만, 꽤 시간이 걸리는 일이므로, 인덱스 파일은 In-memory 맵핑을 빨리 빌드하게 도와주어 Store의 재기동 시간을 줄여줌.
    • 각각의 Physical volume에 대해 인덱스 파일을 유지하는데, In-memory 데이터 구조의 체크포인트라고 생각할 수 있다.
    • 인덱스 파일의 구조는 Physical volume file과 유사하게 수퍼블럭과 인덱스 레코드들의 시퀸스인데, Physical volume file에 나타나는 needle과 동일한 순서임.
    • 사진을 추가할 때 needle은 Physical volume file에 동기적으로 쓰지만, 인덱스 레코드는 비동기적으로 쓴다.
    • 사진을 삭제할 때 Physical volume file의 needle에는 삭제 플래그를 설정하지만, 인덱스 파일은 업데이트하지 않는다.
      • 추가적인 동기적인 디스크 쓰기를 피하고, 쓰기나 삭제가 좀 더 빠르게 끝나도록 해준다.
    • 인덱스 레코드가 없는 needle (orphan)이 발생할 수 있음.
      • 재기동을 할 때 orphan에 해당하는 인덱스 레코드의 추가 작업을 수행.
      • 인덱스의 마지막 레코드는 볼륨 파일의 마지막 orphan이 아닌 needle임.
      • 재기동이 완료되면 인덱스 파일만을 사용해서 In-memory 맵핑을 초기화.
    • 삭제된 사진이지만 인덱스 레코드는 이를 반영하지 않는 경우가 발생할 수 있음.
      • 삭제된 사진을 Physical volume으로부터 가져오더라도 전체 needle을 읽으면 삭제 플래그를 검사할 수 있으므로, 그 때 In-memory 맵핑을 업데이트하고 캐시에 오브젝트가 없다고 응답.
  • 파일시스템
    • 현재는 Extent 기반의 파일시스템인 XFS를 사용.
      • 커다란 파일의 블록맵이 메인메모리에 저장되기 충분할 정도로 작다.
      • 효율적인 파일 preallocation을 제공하므로, fragmentation을 완화하고 블록맵이 커지는 것을 막아준다.
    • XFS를 사용해서 파일 시스템 메타데이터를 읽기 위한 디스크 오퍼레이션을 제거할 수 있다.
    • 예외적으로는 사진 데이터가 extent나 RAID stripe 가장자리에 걸쳐져있는 경우 1번 이상의 디스크 오퍼레이션을 필요로 한다.
      • Haystack은 1GB extent를 preallocation하고 256KB RAID stripe size를 사용하므로 실제로는 그런 경우는 드물다.

3.5. Recovery from failures

  • Detection
    • 적극적으로 문제가 있는 Store 장비를 찾기 위해서, 피치포크(pitchfork)라는 주기적으로 Store 장비의 상태를 체크하는 백그라운드 작업을 실행한다.
    • 각 Store 장비로의 접속을 원격에서 체크하고, Volume file의 가용성과 실제로 데이터를 읽는 것이 가능한지 체크한다.
    • 어떤 Store 장비가 일관되게 체크에 실패한다면  피치포크는 자동적으로 그 Store 장비에 있는 모든 Logical volume을 read-only로 표시한다.
  • Repair
    • 한달에 몇 번 정도 전체 동기화 (bulk sync)를 필요로 하는 상황이 있는데, Store 장비의 데이터를 복제본의 Volume file을 이용해 리셋해야하는 경우다.
    • 전체 동기화되는 데이터의 양은 각 Store 장비의 NIC 속도보다 order of magnitude로 크기 때문에 복구까지 몇시간이 걸릴 수 있다.
      • (나의 계산: 1Gbit하에서 10MB/s (10%)를 쓸 수 있는 상황이라면 10분 내에 복구하려면 10MB x 600sec = 6TB 정도. 1MB x 600 sec이라면 600GB.)

3.6. Optimizations

3.6.1 Compaction

  • 삭제되거나 업데이트에 의해 중복된 needle에 의해 사용되는 공간을 되찾기 위한 과정으로, 중복되거나 삭제된 엔트리를 skip하면서 needle을 새로운 파일로 복사함으로써 Volume file을 compaction한다.
  • Compaction 과정 중에 발생하는 삭제는 원래의 Volume file과 새로 빌드하는 Volume file 양쪽으로 적용된다.
  • 이 과정이 파일의 끝까지 진행되면 추가적인 수정을 블록하고 파일과 In-memory 맵핑을 atomic하게 swap한다.

3.6.2 Saving more memory

  • 플래그는 삭제 용도로만 사용하고 있기 때문에, In-memory record의 offset을 0으로 설정함으로써 삭제를 표현하고 플래그 필드는 제거.
  • 메인 메모리에는 쿠키를 저장하지 않고, 디스크로부터 니들을 읽은 후에만 쿠키를 체크한다.
  • 현재는 사진 당 10 bytes의 메모리를 사용함.
    • 하나의 이미지에 대해 4개의 사이즈를 유지하므로, 키 (8 bytes) + alternate key (4 byte) x 4 + data sizes (2 bytes) x 4 = 32 bytes
    • 해시 테이블에 의해 이미지당 2 bytes의 오버헤드.
    • 리눅스의 xfs_inode_t는 536 bytes임.

3.6.3 Batch upload

  • 디스크는 커다란 sequential write일 경우 성능이 좋으므로, 가급적이면 batch upload를 하려고 노력함.
  • 사용자의 앨범 업로드

4. Evaluations

4.1. Characterizing photo requests

  • 사용자는 매일 수백만개의 사진을 업로드함.
  • 옛날 것보다 최근에 업로드된 사진이 더 POPULAR함.

4.1.1. Features that drive photo requests

News Feed와 album이 98%의 Facebook request임.

  • 빠른 popularity 감소는 CDN/Cache가 popular content의 호스팅에 매우 효율적일 것임
  • Longtail 그래프는 무시할 수 없는 수의 리퀘스트가 캐시로 다룰 수 없음을 의미

4.1.2 Traffic Volume

  • Daily Uploaded: ~120 M
  • Haystack Photo WrittenL ~1.44 B (12배 = 4 sizes, 3 locations)
  • Photo Viewed: 80-100 B
  • Haystack Photo Read: 10 B

4.2. Haystack Directory

Hashing policy는 read-write를 잘 분산하고 있음.

4.3. Haystack Cache

80% 정도의 hit rates

4.4. Haystack Store

4.4.1 Experimental Setup

  • 2U storage blade
  • 2 hyper-threaded quad-core Intel Xeon CPUs
  • 48GB memory
  • hardware raid controller with 256-512MB NVRAM
  • 12 x 1 TB SATA drives
  • RAID-6 partition
    • 9TB of capacity
    • 적절한 redundancy와 뛰어난 읽기 성능, 낮은 스토리지 비용.
    • NVRAM write-back cache가 RAID-6의 write performance 저하를 완화
    • Store 장비에서의 캐싱은 비효율적이므로 NVRAM은 쓰기 용도로만 사용
  • Crash나 Power loss 시의 data consistency를 위해서 disk cache(?)는 disable.

4.4.2 Benchmark Performance

  • Randomio
    • random 64KB reads, direct I/O (sector aligned requests)
    • 읽기 throughput의 베이스라인 설정.
  • Haystress
    • buffer cache의 영향을 줄이기 위해 커다란 이미지 셋에 대한 랜덤 읽기를 사용.
    • Workload A randoms reads to 64KB on Store machine with 201 volumes
      • 770.6 qps, 85% of the raw throughput / 17% higher latency
  • 오버헤드의 원인
    • Haystack은 파일시스템 위에서 동작.
    • 디스크 읽기는 전체 needle을 읽기 위해 필요한 64KB보다 큼.
    • RAID-6 device stripe size에 align되지 않았을 가능성이 있으나, 적은 확률일 것임.
    • 인덱스 액세스, checksum 계산 등으로 인한 CPU 오버헤드.

4.4.3 Production workload

  • Multi-write latencies are very flat and stable
    • NVRAM allows us to write needles async and issue a single fsync to flush the volume file once the multi-write is complete
  • Read performance impacted by
    • number of photos stored on the machine
    • cached in the Cache (for read-only, buffer cache would be more effective)
    • recently written photos are usually read back immediately
  • CPU idle time varies 92-96%

Timestamps in Message-Passing Systems That Preserve the Partial Ordering

Fidge, C.J., Timestamps in Message-Passing Systems that Preserve the Partial Ordering, Proc. 11th Australian Comp. Sci. Conf., 1988, pp. 56-66.

Timestamping is a common method of totally ordering events in concurrent programs. However, for applications requiring access to the global state, a total ordering is inappropriate. This paper presents algorithms for timestamping events in both synchronous and asynchronous message-passing programs that allow for access to the partial ordering inherent in a parallel system. The algorithms do not change the communication graph or require a central timestamp issuing authority.

이 논문은 Vector Clock으로 알려진 개념을 소개하고 있다. Vector Clock은 [Fidge 1998]과 [Mattern 1998]에서 독립적으로 고안된 알고리즘인데, Fidge의 논문쪽이 좀 더 읽기 쉬운 편이라고 한다.

Limitation of Lamport’s logical clock

Clock Condition. For any events a, b:
if a → b then C(a) < C(b).

Lamport가 정의한 논리적 시계는 두 사건 사이의 happened-before 관계가 있다면 이를 반영하는 시계를 정의하고 있습니다. 그리고 이를 이용해 임의의 완전순서를 정의하고 있습니다. 이 완전순서는 임의의 프로세스 사이의 순서를 이용하고 있으므로 사건들을 정렬할 수 있는 방법 중의 임의적인 한 방법이고, 논리적 시계 이상의 어떤 정보가 추가되지는 않습니다.

Lamport가 정의한 논리적 시계의 문제는 이 논리적 시계를 통해서 사건들 사이의 인과성 (causality)를 알아낼 수 없다는 것입니다. 즉, C(a) < C(b)라고 해서 a  b라고 말할 수 없는 것입니다. 구체적으로 말해, C(a) < C(b)가 의미할 수 있는 것은 a와 b 사이에 happend-before 관계가 있는 것, 즉  a  b인 경우와, a와 b 사이에 happend-before 관계를 판단할 수 없고 b가 a에 대해 happened-before가 아닌 것, 즉 b ↛ a인 경우가 있습니다.

Vector Clock

Vector Clock이라는 단어를 논문에서 사용하고 있지는 않지만, 그 단어가 의미하듯이 논리적 시계의 타임스탬프를 integer가 아니라 다음과 같이 프로세스 수 만큼의 타임스탬프를 가진 배열로 대체하고 있습니다.

[c1, c2 … cn]

그리고 이 타임스탬프를 유지하기 위한 알고리즘은 아래와 같습니다. 타임스탬프가 배열이 되었다는 것 이외에 Lamport의 알고리즘과 큰 차이가 없다고도 얘기할 수 있겠지만, 주의를 기울여야 하는 부분은 메시지를 수신하는 프로세스에서는 메시지를 송신한 프로세스에 해당하는 타임스탬프 배열 항목의 값만을 증가시킨다는 것입니다.

Rule RA 1: Initially all values are zero.

Rule RA 2: The local clock value is incremented at least once before each atomic event

Rule RA 3: The current value of entire timestamp array is piggybacked on every outgoing signal

Rule RA 4: Upon receiving a signal, a process sets the value of each entry in the timestamp array to be the maximum of the two corresponding values in the local array, and in the piggybacked array received. The value corresponding to the sender, however, is a special case and is set to be one greater than the value received (to allow for transit time), but only if the local value is not already greater than that received (to allow for signal “overtaking” as described below), i.e.

q?other_array; /* receive timestamp array from process q */

if local_array[q] <= other_array[q] then
    local_array[q] := 1 + other_array[q];
for i := 1 to n do
    local_array[i] := max(local_array[i], other_array[i]);

Rule RA 5: Values in the timestamp arrays are never decremented.

이 논문에서는 설명하고 있지 않지만, 이러한 알고리즘으로 얻어지는 타임스탬프의 의미는 수신한 메시지에 근거해서 추측할 수 있는 가장 정확한 송신 측의 타임스탬프라는 것입니다. 또한, 수신한 프로세스에서 발생할 현재의 사건에 대해 happened-before 관계에 있는 송신 측의 프로세스의 가장 마지막 사건의 타임스탬프이기도 합니다.

이러한 타임스탬프 배열은 다음과 같이 비교될 수 있습니다.

각각 프로세스 p, q에서 실행된 사건 e, f를 ep, fq로 나타내고, 각 사건에 대한 타임스탬프 array를 Tep, Tfq, 그 타임스탬프 배열 중 프로세스 p에 해당하는 타임스탬프를 Tep[p], Tfq[p] 라고 할 때,

ep → fq iff Tep[p] < Tfq[p]

여기서 주목할 점은 iff 즉, 사건의 happened-before 관계와 타임스탬프의 대소 관계가 동치관계라는 것입니다. 임의의 두 사건이 주어졌을 때 인과성이 있는지 여부와 어떤 사건이 어떤 사건에 대해 인과성이 있는지를 판단할 수 있습니다.

ep ↔ fq if Tep[p] ≮ Tfq[p] and Tfq[p] ≮ Tep[p]

타임스탬프 사이의 대소 관계가 어느 방향으로도 성립하지 않는다면 두 사건은 동시적(concurrent)하다고 얘기할 수 있습니다.

Applications

그렇다면 논리적 시계를 통해서 인과성을 알아내는 것은 왜 필요한가에 대해서 이 논문이 예로 들고 있는 것 중 하나는 여러 프로세스들에 의해서 저장되는 상태의 스냅샷들에 타임스탬프를 이용해서, 전체 프로그램 상태에 대해 정상적인 상태인지 검사를 할 수 있고 이를 통해 역실행 (reverse execution), 에러의 복구, 롤백 등이 가능하다는 것입니다. 실제로 이후에 발표된 Dynamo나 Riak 등 Vector Clock을 이용하는 것으로 알려진 시스템에서는 동시적인 쓰기 등에 의해 어떤 데이터에 대해 2개 이상의 복제본이 발생했을 때 이를 해소하기 위해서 인과성을 활용하고 있는 사례를 볼 수 있습니다.

References

  • [Fidge 1998] Fidge, C.J., Timestamps in Message-Passing Systems that Preserve the Partial Ordering, Proc. 11th Australian Comp. Sci. Conf., 1988, pp. 56-66.
  • [Mattern 1998]  Mattern, F. Virtual time and global states of distributed systems. Proc. “Parallel and distributed algorithms” Conf., (Cosnard, Quinton, Raynal, Robert Eds), North-Holland, 1988, pp. 215-226.

Time, Clocks, and the Ordering of Events in a Distributed System

Leslie Lamport. 1978. Time, clocks, and the ordering of events in a distributed system.Commun. ACM 21, 7 (July 1978), 558-565.

The concept of one event happening before another in a distributed system is examined, and is shown to define a partial ordering of the events. A distributed algorithm is given for synchronizing a system of logical clocks which can be used to totally order the events. The use of the total ordering is illustrated with a method for solving synchronization problems. The algorithm is then specialized for synchronizing physical clocks, and a bound is derived on how far out of synchrony the clocks can become.

이 논문에 대해서는 Paxos Made Simple에서 이미 아래와 같은 소개를 한 적이 있습니다.

Leslie Lamport는 분산 컴퓨팅 분야에서는 너무나 유명한 분이기 때문에 따로 설명할 필요가 없을 정도입니다. 예를 들어, 1978년에 출판된 “Time, Clocks, and the Ordering of Events in a Distributed System”과 같은 페이퍼는 인용 회수로 볼 수 있는 그 영향력 뿐만 아니라 OS 수업의 읽기 과제로도 빠질 수 없는 그야말로 seminal work입니다.

1. “Happened before” 관계

가장 먼저, “Happened before” 관계라는 분산시스템 내에서 사건(event)들의 순서를 표현할 수 있는 부분순서(partial ordering)를 제안하고 있습니다.

“Happened before” relation은 분산시스템에서 구현이 어려운 물리적 시계 (physical clock)를 사용하지 않더라도 사건들의 순서를 표현할 수 있음을 보여주고 있습니다. 즉, 사건이 발생한 전역적으로 통용되는 시각을 알지 못해도 우리는 자연스럽게 사건의 순서를 정할 수 있습니다.

또한, 서로 다른 프로세스 사이에서 메시지를 주고 받을 경우에 사건 사이의 인과성(causality)이 발생하는 것을 다음과 같은 정의에 담고 있습니다.

Definition. The relation → on the set of events of a system is the smallest relation satisfying the following
three conditions:

  1. If a and b are events in the same process, and a comes before b, then a → b.
  2. If a is the sending of a message by one process and b is the receipt of the same message by another process, then a → b.
  3. If a → b and b → c then a → c.

Two distinct events a and b are concurrent if a ↛ b and b ↛ a. Assume a ↛ a for any event a. So → is an irreflexive partial ordering on the set of all events in the system.

2. Logical Clocks

논리적 시계는 하나의 프로세스 내의 각 사건들에 대해 단조 증가하는 숫자를 할당하는 것으로 볼 수 있으며, 물리적 시계가 아니라 사건이 발생한 순서에 기초해야 합니다.

Clock Condition. For any events a, b:
if a → b then C(a) < C(b).

“Happened before” 관계의 정의에 따라, 각 프로세스는 사건이 발생할 때마다 증가하는 타임스탬프를 부여하며, 프로세스 사이에 메시지를 송신할 때 타임스탬프를 함께 송신하며, 메시지를 수신하는 측에서는 수신한 타임스탬프보다 더 큰 타임스탬프를 새로운 사건에 할당합니다.

3. Ordering the Events Totally

위에서 정의된 논리적 시계만으로는 분산시스템 내의 사건들의 완전순서(total ordering)는 불가능하기 때문에, 프로세스 사이의 임의의 순서(!)를 도입해, 완전순서를 만들 수 있습니다.

In case two or more events occur at the same time, an arbitrary total ordering ≺ of processes is used. To do this, the relation ⇒ is defined as follows:

If a is an event in process Pi and b is an event in process Pj , then a ⇒ b if and only if either:
i. Ci<a> < Cj<b> or
ii. Ci<a> = Cj<b> and Pi ≺ Pj

이렇게 정의된 완전순서를 이용해 분산시스템에서의 상호배제(mutual exclusion) 문제를 해결하는 방법을 제시하고 있습니다.

간단히 얘기하면, 어떤 프로세스가 자원을 요청할 때는 자신의 타임스탬프를 함께 다른 모든(!) 프로세스들에게 전송하고, 이 자원의 요청은 요청한 프로세스 뿐만 아니라 모든 프로세스의 큐에 위에서 정의된 완전순서대로 정렬됩니다. 이 큐에서 가장 앞에 있는 자원 요청이 자원을 획득해야한다고 볼 수 있는데, 모든 프로세스들이 동일한 큐를 유지해야하기 때문에, 자원 획득을 위해서는 모든 다른 프로세스들로부터 receipt 메시지를 수신한 조건에서만 자원 획득이 가능합니다. 또한, 다른 프로세스의 자원 요청에 대한 응답과 자신의 자원 요청의 (타임스탬프의 순서는 올바르다고 하더라도) 전송 순서가 바뀌는 경우는 두 프로세스 사이의 통신은 순서대로 일어난다는 가정에 의해 발생하지 않습니다.

이 구현은 1개 이상의 프로세스의 실패나 메시지의 소실 등을 가정하고 있지 않기 때문에 현실적으로 사용할 수 있는 알고리즘은 아니지만, 분산시스템에서의 완전순서의 유용성을 보여주고 있다고 생각합니다. 그리고, Lamport가 이후에 제안한 Paxos가 바로 현실적인 환경 하에서의 완전순서를 보장하기 위한 방법을 제공하고 있는 것으로 보입니다.

4. Anomalous Behavior

위에서 제시한 상호배제 알고리즘에서 사건 사이의 인과성이 외부화됨으로써 발생할 수 있는 문제를 제시하고 있습니다. 예를 들어, 자원 요청 A를 한 후, 전화를 걸어 다른 컴퓨터에서 자원 요청 B를 한 경우, 자원 요청 A와 자원 요청 B 사이에는 실제로 인과성이 존재하지만, 논리적 시계의 체계는 이를 인지하지 못하므로, 자원 요청 B가 더 낮은 타임스탬프를 획득해 먼저 자원을 획득할 수 있다는 것입니다.

이를 해결하기 위한 방법으로 2가지 방법을 제시하고 있는데, 첫번째는 “happened-before” 관계에 필요하지만 외부화된 정보를 시스템 내로 도입하는 것입니다. 즉, 자원 요청 B를 하는 사용자에게 자원 요청 A 보다 더 이후의 타임스탬프를 발급하도록 자원요청 A의 타임스탬프를 전화를 통해 알려주는 방법 등으로 논리적 시계 체계를 유지하는 책임을 부여하는 것입니다.

다른 방법은 외부화된 사건들 사이의 관계를 포함해 모든 사건들을 정렬할 수 있는 물리적인 시계의 체계를 구성하는 것입니다. 이 시계들은 다음의 Strong Clock Condition을 만족해야 합니다.

Let S be the set of all system events and S be the set containing S along with relevant events external
to the system. Let ↪ denote the “happened before” relation for S.

For any events a, b in S: if a ↪ b then C<a> < C<b>.

5. Physical Clocks

Strong Clock Condition을 만족하기 위해서는 물리적 시계는 다음과 같은 조건을 만족해야합니다.

Let Ci(t) denote the reading of clock Ci at physical time t. Assume that Ci(t) is a continuous, differentiable
function of t except for isolated discontinuities introduced by clock resets.
PC1. There exists a constant k << 1 such that for all i: |dCi(t) / dt – 1| < k.
PC2. For all i, j : |Ci(t) – Cj(t)| < e.

PC1은 물리적 시계가 가는 속도가 물리적 시간이 흐르는 속도와 일정 오차 범위 내에 있다는 것을 의미합니다. 일반적인 수정 발진 방식의 시계의 경우, k는 약 10-6정도로 언급하고 있으며, PC1 자체는 만족되는 것으로 가정하고 있습니다.

한편, PC2는 물리적 시계들 사이의 오차가 일정 범위 내에 있다는 것을 의미합니다. PC2를 보장하기 위해서 물리적 시계의 보정을 위한 구현 방법을 제시하고 있습니다.

Let vm = t’ – t be the total delay of m which is unknown to the receiving process. Let µm be some minimum delay >= 0 known by the receiving process such that µm <= vm.

IR2′. a. If Pi sends a message m at physical time t, then m contains a timestamp Tm = Ci(t).
b. Upon receiving a message m at time t’, process Pj sets Cj(t’) equal to max(Cj(t’ – 0), Tm +
µm).

메시지에 타임스탬프를 넣어서 보내고, 이를 수신하는 측에서는 메시지를 통해 받은 타임스탬프와 최소 통신 지연 시간 이후의 시각으로 시계를 재설정하는 방식이라고 할 수 있고, 이러한 구현 요구사항을 만족한다면, PC2를 만족하는 것을 증명할 수 있다고 합니다. 이 증명에서는 일정 시간 내에 메시지가 전체 프로세스 사이로 전송되는 상황을 가정하고 있으므로, 메시지를 주고 받지 않는 조건을 염두에 두고 있는 것 같지는 않습니다.

한편, 최소 지연시간에 해당하는 µm은 일반적으로 거리와 빛의 속도로 계산할 수 있는 수준의 값으로 언급되고 있습니다. 그리고, 주어진 µm에 대해 k와 e가 얼마나 작아야 하는지에 대한 계산 방법도 설명하고 있습니다.

현실적으로는 이 논문에서 정의된 Physical Clock은 항상 가장 빠른 시계에 맞춰지게 되므로 실제 시간 (physical time)보다 더 빨라지게 되겠지만, 분산시스템의 동기화 문제를 해결하는 능력과는 무관하다고 할 수 있을 것 같습니다.

6. Closing

이 논문은 분산시스템의 문제에 대한 이해에 가장 중요한 사고 도구로 사용할 수 있는 중요한 개념들을 정의하고 있는 것 같습니다. 내용 자체를 정확하게 이해했는지의 여부를 차치하더라도, 이러한 개념이 마음에 와닿기 위해서는 몇 번은 더 읽어봐야 할 것 같습니다.

다음에는 Vector Clock에 관한 논문인 C. Fidge의 Timestamps in Message-Passing Systems That Preserve the Partial Ordering을 읽어볼 예정입니다.

What consistency does your key-value store actually provide?

What consistency does your key-value store actually provide? by Anderson, Eric, et al

Many key-value stores have recently been proposed as platforms for always-on, globally-distributed, Internet scale applications. To meet their needs, these stores often sacrifice consistency for availability. Yet, few tools exist that can verify the consistency actually provided by a key-value store, and quantify the violations if any. How can a user check if a storage system meets its promise of consistency? If a system only promises eventual consistency, how bad is it really? In this paper, we present efficient algorithms that help answer these questions. By analyzing the trace of interactions between the client machines and a key-value store, the algorithms can report whether the trace is safe, regular, or atomic, and if not, how many violations there are in the trace. We run these algorithms on traces of our eventually consistent key value store called Pahoehoe and find few or no violations, thus showing that it often behaves like a strongly consistent system during our tests.

예전에 HP-KVS에 관련해서 자료를 찾다가 발견한 페이퍼인데, 얼마전 한국에 다녀올 때 읽어보게 되었습니다.

1. Perceived consistency rather than worst-case consistency

이 페이퍼는 일반적으로 key-value store들이 보장하는 worst-case consistency가 아니라, 실제로 client에 의해서 관찰되는 consistency의 수준을 측정하는 알고리즘을 제안하고 있다. 우리가 스토리지 기술을 선택할 때는 물론 worst-case consistency가 고려되기는 하지만, 실제로는 ‘실용적인’ 접근을 취하는데, 그것이 의미하는 바는 애플리케이션의 액세스 패턴에 따라 사용자가 느끼는 consistency의 수준이 달라질 수 있음을 고려해서 스토리지 기술을 선택한다는 것이다. 이 페이퍼가 해결하려는 문제 자체가 엄밀하거나 학술적이기 보다는 실용적인 의미를 해석하려는 것이기 때문에 한계는 있겠지만, 어떤 worst-case consistency를 가진 스토리지 – 예를 들어 eventually consistent 스토리지들이 어떤 애플리케이션에 필요한 consistency를 달성하기에 충분한지 충분하지 않은지에 대해서 매우 피상적으로 논의하는 것보다는 체계적인 방법을 제공한다는 점 그리고, 그러한 방법이 존재할 수 있다는 점에서 의미가 있는 것 같다.

2. A eager, eventually consistent protocol often achieves strong consistency

이 알고리즘을 통한 검증을 역시 HP에서 만든 eventually consistent key-value store인 Pahoehoe를 가지고 실험한 결과를 보여주고 있는데, 가장 concurrent한 조건 (128 concurrent processes on 1 key)에서도 consistency violation의 수가 10% 이하로 발생하고 있고, 일반적인 조건 하에서는 1% 수준이다. 그 이유를 우리가 일반적인 웹 애플리케이션에서 예상하고 있는 것과 마찬가지로 concurrent write 하에서의 read가 많지 않기 때문으로 설명하고 있다.

3. Lamport’s consistency assumption on registers: safe, regular, and atomic

이 페이퍼가 검증하려고 하는 consistency 수준의 분류로 Leslie Lamport가 On Interprocess Communication. Part I: Basic Formalism에서 제안한 register의 3가지 consistency semantic을 사용하고 있다. 이는 다음과 같다.

3가지의 consistency 모두 write와 concurrent하지 않은 read는 가장 최근의 write에 의한 값을 return 해야한다. 차이는 write와 concurrent한 read에서 발생한다.

  • safe: write와 concurrent한 read는 임의의 값을 return
  • regular: write와 concurrent한 read는 가장 최근의 write에 의한 값과 concurrent한 write들에 의한 값들 중 하나를 return
  • atomic: write와 concurrent한 read도 가장 최근의 write에 의한 값을 return

worst-case consistency를 가지고 예를 든다면, 최근 유행하는 eventual consistent storage들은 concurrent하지 않은 read에 대해서 가장 최근의 write에 의한 값을 return하는 것을 보장하지 않으므로 가장 느슨한 수준인 safe 조차 만족하지 못한다. 반면에 일반적인 ACID 데이터베이스는 atomic 수준에 해당한다.

4. Methods

이 페이퍼가 제안하고 있는 알고리즘은 대략 다음과 같다.

  1. 어떤 key-value store에 대한 클라이언트의 모든 액세스에 대해 시작 시각과 종료 시각, 그리고 저장하거나 읽어온 값의 로그를 기록한다.
  2. 이 로그를 바탕으로 오퍼레이션이 vertex이고, should-happen-before 관계가 edge인 directed graph를 구성한다. 이 때 이 관계는 검증하려는 consistency 종류에 따라서 달라지는데, 대체로 시간의 관계, 값의 인과 관계를 의미한다고 보면 된다.
  3. 구성된 graph에서 cycle이 발견되지 않으면 consistent, 발견되면 inconsistent하다고 판단한다.

straight-forward하기 때문에 쉽게 이해할 수 있다. 시각의 정확성이나 값의 인과관계를 찾는 부분 등에서 보완이 필요한 것 같긴 하지만 중요한 문제는 아닌 것 같다.

5. Measuring Consistability

여러 eventually consistent 스토리지들은 failure가 발생했을 때 consistency를 희생하게 되어있는데 이 때의 consistency 희생이 어느 정도인지 측정하는 작업이 필요하다.

6. Further Reads

  • J. Misra, Axioms for memory access in asynchronous hardware systems, 1986.
  • L. Lamport, On interprocessing communication, Part I: Basic formalism and Part II: Algorithms, 1986
  • W. Vogels, Eventually consistent, 2009
  • A. Aiyer, et al., On the availability of non -strict quorum systems, 2005
  • E. Anderson, et al., Efficient eventual consistency in Pahoehoe, an erasure-coded key-blob archive, 2010

Paxos Made Simple

Paxos Made Simple by Leslie Lamport

Paxos Made Simple이라는 글의 저자인 Leslie Lamport는 분산 컴퓨팅 분야에서는 너무나 유명한 분이기 때문에 따로 설명할 필요가 없을 정도입니다. 예를 들어, 1978년에 출판된 “Time, Clocks, and the Ordering of Events in a Distributed System”과 같은 페이퍼는 인용 회수로 볼 수 있는 그 영향력 뿐만 아니라 OS 수업의 읽기 과제로도 빠질 수 없는 그야말로 seminal work입니다. 그의 주요한 업적 중 하나가 바로 Paxos 알고리즘인데, 최근에는 Chubby나 Zookeeper 등의 제품으로 구현되어 분산 시스템의 중요성이 점점 떠오르고 있는 요즈음 더욱 더 일상적으로 쓰이게 되어가고 있습니다.

The Paxos algorithm, when presented in plain English, is very simple.

Abstract에서 보다시피 이 글은 Paxos 알고리즘을 쉬운 말로 설명하고자 하는 시도인데, 합의 문제로부터 정의되는 조건을 충족하기 위한 자연스러운 해결책이 바로 Paxos 알고리즘임을 보이려 하고  있습니다.

하지만, 논리적인 단계들을 정확하기 이해하기 위해서는 쉬운 말로 쓰여진 용어들을 정확하게 해석해야 하기 때문에, 프로그래머 입장에서 볼 때는, 오히려 의사 코드 수준으로 설명하는 다른 글 (예를 들어, Paxos Made Moderately Complex)들이 훨씬 더 이해하기 쉽다는 생각이 들었습니다.

아래는 요약이라고 하기에는 너무 길고, 그렇다고 번역이라고 할 수도 없지만, 개인적으로 중요하다고 생각한 점들을 기록한 메모라고 보시면 좋을 것 같습니다.

Read More

Consistency Tradeoffs in Modern Distributed Database System Design

지난 번에 소개했던 IEEE Computer 2012년 2월호의 CAP Theorem 특집 중 세번째 글입니다. CAP Theorem 특집을 읽게된 계기도 바로 이 글의 저자인 Abadi의 블로그 글이었습니다.

Consistency Tradeoffs in Modern Distributed Database System Design by Daniel J. Abadi

Critique

현대의 DDBS에서 CAP의 consistency/availability tradeoff 보다 consistency/latency tradeoff가 중요한 설계상의 결정임을 주장하고 PACELC라는 모델을 제안하고 있습니다.

CAP 만으로 설명하기 어려웠던 설계 결정들에 대해 의문이 있었다면 PACELC가 완벽하지는 않지만 CAP에 비해서 더 좋은 모델임에 동의할 수 있을 것 같습니다. 주변 분들에게도 PACELC에 대해서 설명해주면 당연하게 받아들이는 눈치였습니다. 한편, 이 글은 매우 간결하면서도 문제로부터 결론을 도출하기 까지 논리의 흐름이 부드럽게 이어지기 때문에 이해가 잘 되고 그리 무겁지 않게 읽을 수 있습니다.

PACELC의 개념이 직관적으로는 이해하기 쉬운 반면, 현재 존재하는 시스템을 분류할 때 저자도 언급하고 있는 애매한 점들이 등장하는 것을 보면 엄밀한 도구라고 보기에는 약간 무리입니다. tradeoff 의 모든 측면을 모델로 표현하는 것은 매우 어렵기 때문에 베이스라인이라는 표현과 이로부터 상대적인 tradeoff의 유무를 기준으로 사용한 것 같습니다.

역시 완벽하지는 않겠지만 현대의 DDBS에서 활용하고 있는 설계 결정들을 모두 정리해서 스펙트럼 또는 이에 상응하는 모델로 정리할 수 있다면 앞으로의 DDBS 프레임워크의 발전에서 중요한 기초가 될 수 있지 않을까 생각합니다.

아래는 이 글의 요약입니다.

CAP is for Failure

CAP에서 consistency와 availability 사이의 tradeoff를 발생시키는 요소는 단지 partition tolerance 만이 아니라, partition tolerance와 network partition의 존재, 두 가지 요소의 조합이기 때문에, network partition이 존재하지 않을 때, CAP 자체는 consistency와 availability를 동시에 만족시키는 시스템을 허용하고 있다.

Consistency/Latency Tradeoff

network partition이 존재하지 않는다고 하더라도 consistency, availability, latency 사이의 tradeoff는 존재한다. 이러한 tradeoff가 존재하는 이유는 high availability 요구사항으로 인해 시스템은 데이터를 복제해야하기 때문이다.

Data Replication

시스템이 데이터를 복제하는 순간부터 consistency와 latency 사이의 tradeoff가 발생한다. 데이터 복제를 구현하는 데에는 아래와 같이 3개의 방법이 존재하지만, 각각은 모두 latency의 요소가 존재한다.

(1) 데이터의 업데이트를 동시에 모든 복제본으로 보내기

선처리 레이어(preprocessing protocol)를 통과하지 않거나 합의 프로토콜 (agreement protocol)이 없다면 오퍼레이션의 적용 순서의 차이로 인해 복제본들 사이의 차이가 발생한다. 선처리 레이어나 합의 프로토콜을 사용한다면 모든 복제본들이 합의된 순서대로 업데이트를 적용하는 것을 보장할 수 있지만, 선처리 레이어를 위한 추가적인 시스템 컴포넌트, 모든 복제본에 대한 업데이트, 합의 프로토콜 자체 등 latency가 발생하는 여러가지 원인들이 된다.

(2) 데이터의 업데이트를 합의된 마스터 노드에 먼저 보내기

마스터 노드는 모든 업데이트 요청을 처리하고 마스터 노드가 처리한 순서는 마스터 노드가 모든 리플리카에 복제하면서 다른 복제본들에도 그대로 적용된다.

마스터로부터 다른 복제본으로의 복제 방법은 아래와 같은 3가지가 존재한다.

a. 동기적인 복제: 복제본들로의 업데이트가 일어날 때까지 마스터 노드는 대기한다. 복제본들이 consistent하지만, 모든 복제본들의 업데이트로 인해 latency가 증가한다.

b. 비동기적인 복제: 복제본들이 업데이트 되었다는 보장이 없으므로, consistency/latency tradeoff는 시스템이 읽기를 어떻게 다루느냐에 달려있다.

i. 시스템이 모든 읽기를 마스터 노드에서 수행한다면 consistency의 감소가 없지만, 마스터 노드가 다른 복제본에 비해서 가까운 곳에 있지 않을 때, 또는 마스터 노드가 과부하 상태이거나 동작 불능 상태일 때는 latency가 발생한다.

ii. 어떤 노드에서도 읽기를 수행하도록 한다면 읽기의 latency는 좋아지지만, 동일한 데이터의 inconsistent한 읽기가 발생한다. update sequence number의 추적을 통해 sequential/timeline consistency 또는 read-your-writes consistency를 구현해 consistency의 감소를 줄일 수 있다.

c. 데이터의 업데이트를 복제본의 일부에 대해서는 동기적으로 복제하고, 나머지는 비동기적으로 복제한다. 이 경우에도 consistency/latency tradeoff는 시스템이 읽기를 다루는 방식에 달려있다.

i. 동기적으로 복제가 된 적어도 1개 이상의 노드로부터 읽기를 수행한다. (R + W > N)

ii. 동기적으로 업데이트 되지 않은 노드들에서 읽기를 수행하도록 허용한다. (R + W <= N)

(3) 데이터의 업데이트를 임의의 노드에 먼저 보내기

하나의 데이터 항목에 대한 두개의 업데이트가 서로 다른 노드로 보내질 수 있다. 동기적인 복제인가, 비동기적인 복제인가에 따라서 (1), (2)에서와 같은 latency 문제나 consistency 문제가 발생한다.

Tradeoff Examples

PNUTS의 경우, 마스터 노드로부터 비동기적으로 데이터를 복제하고, 아무 노드에서나 읽기를 수행하므로 (즉, 2-b-ii의 경우), latency를 위해 consistency를 tradeoff 하고 있다. 반면, CAP의 관점에서는 network partition이 발생했을 때, 소수 (minority) 파티션에 존재하는 마스터 노드는 사용 불가능하므로 consistency를 위해 availability를 trade-off하는 CP 시스템에 해당한다.

PNUTS는 일반적인 상황 (baseline case)에서 consistency를 희생하는 선택은 CAP에서의 consistency/availability tradeoff 라기보다는 consistency/latency tradeoff 때문이라고 할 수 있고, 일반적인 시스템에서 consistency를 희생하는 주된 이유가 CAP이 아니라는 증거를 보여주고 있다.

PACELC

DDBS에서의 consistency tradeoff는 CAP 대신 다음과 같은 PACELC로 좀 더 완전한 설명이 가능하다.

  • if there is a partition (P), how does the system trade off availability and consistency (A and C);
  • else (E), how does the system trade off latency and consistency (L and C)?

예를 들어, partition이 발생했을 때 availability를 위해 consistency를 포기하고, 보통의 상황에서는 낮은 latency를 위해 consistency를 포기하는 Dynamo, Cassandra, Riak과 같은 시스템들은 PA/EL 시스템이다. VoltDB/H-Store, Megastore와 같은 ACID 시스템들, BigTable과 이에 관련된 시스템들 (e.g. HBase) 은 PC/EC 시스템이다. MongoDB는 partition이 발생했을 때 master에서 복제되지 않은 데이터가 있더라도 새로운 master를 선출해서 서비스를 하기 때문에 PA/EC 시스템이다. PNUTS는 위에서 설명한대로 PC/EL 시스템이다. (이 때, PC는 CAP에서의 consistency가 아니라 일반적인 상황에 대비해서 consistency를 희생하지 않는다는 의미이다.)