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.

• Blog Post: https://www.facebook.com/notes/facebook-engineering/needle-in-a-haystack-efficient-storage-of-billions-of-photos/76191543919
• Presentation: https://www.usenix.org/conference/osdi10/finding-needle-haystack-facebooks-photo-storage

최근 몇개월 동안  상대적으로 크기가 작고 많은 파일들을 비교적 단순한 솔루션을 이용해서 효율적으로 저장하는 것에 대해서 관심이 있어서 읽어본 페이퍼이다. 파일들의 개수로 인한 메모리 사용량과 복제 시간 등이 골칫거리라서 커다란 파일에 저장하는 방법을 여러가지로 검토하고 있었는데, 매우 실용적이고 깔끔한 접근으로 문제를 해결하고 있고, 실제로 개발 비용도 적게 (몇개월 정도 걸렸다고 한다) 들었으므로, 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%