An analysis of Facebook photo caching

💡 요약
- abstract: Facebook의 사진 서비스 워크로드를 캐싱 계층(브라우저 캐시, 엣지 캐시, 서버 캐시 등)마다 분석 및 캐시 알고리즘 성능 평가에 관한 연구
- introduction: 소셜 네트워크의 인기로 인터넷 포털에서 제작되는 미디어 콘텐츠의 양이 늘어남에 따라, 이를 저장하기 위한 대용량 볼륨을 저장하고 전송하는 스택의 효율성이 문제가 되고 있다.
- related works: 
  * 네트워크 트레이스 분석 측면
    * peer-to-peer 네트워크가 인터넷 트래픽의 주를 이루던 시기에 수행
    * "aggregated" 네트워크 트래픽을 모니터링하여 얻은 데이터를 분석하여 광범위한 통계를 산출하지만, 특정 애플리케이션 속성에 대한 인사이트는 제한적이었다.
    * Coral CDN의 5년치 시스템 로그를 운영 속성과 아키텍쳐의 측면에서 조사하여 그 동작을 연구
  * 백엔드 스토리지 측면
    * 웹 캐싱과 관련하여 Zipf의 법칙의 영향을 조사한 연구: 인기도 분포가 인구 규모에 따라 캐시 적중률을 대수적으로 증가
    * 미디어 콘텐츠에 대한 접근은 고전적인 Zipf 분포에 비해 머리와 꼬리 부분이 왜곡되어 있는 경우가 많다
- method: Facebook이 제어하는 스택의 모든 계층을 계측하고 그 결과 이벤트 스트림을 샘플링하여 트래픽 패턴, 캐시 액세스 패턴, 클라이언트 및 서버의 지리적 위치를 연구하고 콘텐츠의 속성과 액세스 간의 상관관계를 탐색
- experiment: 매우 활동적인 클라이언트의 경우 브라우저 캐시 크기를 늘리고 덜 활동적인 클라이언트의 경우 로컬 사진 크기 조정을 활성화하여 클라이언트 성능을 개선할 수 있다.
  * 브라우저 캐시, 엣지 캐시, 오리진 캐시가 총 트래픽의 90%를 처리
  * 가장 인기 있는 0.03%의 콘텐츠의 경우 캐시 적중률이 100%에 가까움
- conclusion & discussion: 본 연구는 계층별 캐시 효율성을 정량화함으로써 향후 콘텐츠 저장 및 전송 시스템의 설계 결정을 내리는데 인사이트를 확보할 수 있는 연구, 인터넷 이미지 서비스 인프라 전체를 대규모로 조사한 최초의 연구로서 의미가 있다.

 

 

Introduction

소셜 네트워크의 등장으로 인터넷 포털에 저장되는 사용자 생성 콘텐츠(특히 미디어 콘텐츠)가 크게 증가하면서 소셜 네트워크 제공업체를 위한 대용량 바이너리 객체를 저장하고 전송하는 효율적인 시스템이 중요해졌다. 본 논문에서는 클라이언트 브라우저에서 Facebook의 Haystack 스토리지 서버에 이르는 전체 Facebook 사진 서비스 스택을 살펴보고, 각 계층의 성능과 여러 시스템 계층 간의 상호 작용을 살펴본다.

Facebook photo serving stack

 

• 실험에 사용된 캐시 계층: 
  • 소셜 네트워크 웹 사이트에 접속하는 모든 데스크톱과 노트북에서 실행되는 클라이언트 브라우저: I/O가 제한된 백엔드 헤이스택 서버를 위한 트래픽 보호를 위해
    • 일반적으로 브라우저 캐시는 인메모리 해시 테이블을 사용하여 캐시 내 존재 여부 확인
    • LRU 알고리즘
    • miss: 브라우저는 HTTP 요청을 인터넷으로 보내고 fetch 경로에 따라 해당 요청이 Akamai CDN/Facebook Edge 전송 여부가 결정됨(2) => 사진 파일의 URL은 웹 서버의 고유한 사진 식별자/이미지의 표시 크기/각 캐시 계층에서 실패한 요청이 다음에 전달될 위치를 지정하는 fetch 경로가 초함되어있어 서버 스택 전반의 트래픽 분산을 제어할 수 있다.
  • 지리적으로 분산된 지점에 배포된 모든 엣지 캐시 호스트: 엣지 캐시의 주요 목표는 엣지와 오리진 데이터센터 간의 대역폭을 줄이기 위해
    • 최종 사용자와 가까운 접속 지점(PoP)에서 실행되도록
    • 미국 전역의 약 9개의 엣지 캐시가 분산되어 독립적으로 작동 => 동부 지역의 엣지 캐시가 서부 지역의 오리진 캐시 서버에 데이터를 요청해야 하는 경우도 있어 지연시간 증가할 수 있다
    • FIFO 알고리즘
    • 각 엣지 캐시에는 저장된 사진에 대한 메타데이터를 보관하는 인메모리 해시 테이블과 실제 사진을 저장하는 대용량의 플래시 메모리가 있다
    • hit: 플래시 메모리에서 사진을 검색하여 클라이언트 브라우저로 반환
    • miss: facebook origin cache에서 사진을 가져와 edge cache에 삽입(3)
  • 미국 데이터 센터의 origin cache: I/O가 제한된 백엔드 헤이스택 서버를 위한 트래픽 보호를 위해
    • 사진의 고유 ID를 기반으로 해시 매핑을 사용하여 에지 캐시에서 오리진 캐시에 있는 서버로 라우팅
    • 각 오리진 캐시 서버에는 저장된 사진에 대한 메타데이터를 보관하는 인메모리 해시 테이블과 실제 사진을 저장하는 대용량 플래시 메모리가 있다
    • FIFO 알고리즘
    • 스토리지 서버와 함께 위치하기 때문에 로컬 헤이스택 서버에서 이미지를 검색할 수 있는 경우가 많다(4)
  • 미국 데이터 센터의 백엔드 서버(Haystack)
    • compact blob representation 을 사용하여 log structured 볼륨에 보관되는 큰 세그먼트 이미지로 저장
    • 시스템은 사진 볼륨 ID와 오프셋을 메모리에 보관하고, 원하는 데이터를 검색하기 위해 한 번의 검색과 한 번의 디스크 읽기를 수행하도록 설계되어있다. (I/O를 최소화)
    • 사진이 Facebook에 처음 업로드되면 알려진 몇 가지 일반적인 크기로 크기가 조정되고, 각 크기에 맞는 사본이 백엔드 Haystack 머신에 저장됨(캐싱 인프라는 변형되고 잘린 사진을 모두 별도의 개체로 취급)

 

 

Related Work

• 콘텐츠 전송, 저장 및 웹 호스팅과 관련된 서비스에대한 웹 액세스 패턴을 조사한 연구
  • 워싱턴 대학 - 인터넷사이에 캡쳐한 네트워크 트레이스를 사용하여 네 가지 인터넷 콘텐츠 전송 매커니즘의 특성 비교 => peer-to-peer 네트워크가 인터넷 트래픽의 주를 이루던 시기에 수행된 한계점
  • 이후 워싱턴 대학 캠퍼스 트레이스에서 나타난 미디어 인기도 분포를 기존 웹 트래픽과 비교
• 콘텐츠 전송 네트워크(CDN)에서의 플래시 크라우드 현상에 관한 연구
  • 집계된 네트워크 트래픽을 모니터링하여 얻은 데이터에 중점 => aggregated 데이터를 분석한 것이므로, 관찰된 현상을 일으킨 애플리케이션 속성에 대한 인사이트는 제한적으로만 얻을 수 있다.
  • Coral CDN의 5년치 시스템 로그를 조사하여 그 동작을 연구
• 백엔드 스토리지 서버에 관한 연구
• 웹 워크로드 모델링에 관한 연구
  • 웹 자체의 진화에 따른 워크로드 변화를 평가할 정도로 장기간에 걸쳐 웹 트래픽을 모니터링
  • Zipf의 법칙의 영향을 조사하여 Zipf와 유사한 인기도 분포가 인구 규모에 따라 캐시 적중률을 대수적으로 증가시키고 다른 효과도 발생시킨다는 것을 보여줌
  • 미디어 콘텐츠에 대한 액세스는 고전적인 Zipf 분포에 비해 머리와 꼬리가 상당히 왜곡되어 있는 경우가 많다고 주장

 

기존 연구와의 차별점
- 본 논문은 페이스북의 워크로드에 대한 최초의 체계적인 연구로, CDN의 대규모 네트워크 트래픽 통계에만 집중했던 기존 연구와 차별화된다.
- 대규모 블롭 트래픽에 집중하여 다양한 이슈를 다루고 체계적인 분석과 인사이트를 제공
- 서버의 로깅 정보를 분석하고 캐싱 정책이 페이스북 인프라의 부하를 줄이는 방법을 탐구

 

 

Method

Facebook의 사진 서비스 인프라를 계측하여 한 달간 분산 로깅 서비스인 Scribe를 이용하여 트레이스 샘플링하여 수집

• 사진 ID에 대한 결정론적 테스트를 통해 선택된 일부 사진 하위 집합에 초점을 맞춘 샘플링 방식
• 트레이스의 편향 정도를 정량화하기 위해 두 개의 개별 데이터 셋으로 다운샘플링했으며, 각 데이터 셋은 원본 사진Id의 10%

 

Experiment

summary statistics of workload trace

7,720만 건의 브라우저 요청 중 브라우저 캐시(65.5%), 엣지 캐시(20.0%), 오리진 캐시(4.6%), 백엔드(9.9%)

• % of traffic served: 서비스 또는 시스템의 특정 요소가 처리하는 총 트래픽의 백분율을 나타내는 지표 = Hits/전체
• hit ratio: 캐시의 효율성을 측정하는 데 사용되는 메트릭 중 하나로, 데이터가 요청되어 이미 캐시에 저장되어 있을 때 얼마나 빨리 검색할 수 있는지를 나타내는 지표 = Hits/Photo requests

 

Popularity distribution (logscale)

각 사진에 대한 반복 요청 횟수를 추적함으로써 해당 객체의 인기도를 정량화할 수 있다. (Haystack-저장된 공통 크기의 사진을 하나의 개체로 간주/others-크기가 조정된 각 변형 사진을 기본 사진과는 별개의 개체로 취급)

• 일반적으로 웹 트래픽은 Zipfian 분포를 따르는데, 스택의 깊이가 깊어질수록(Haystack으로 갈수록) 양쪽 끝(가장 인기 있는 개체 & 가장 인기 없는 개체) 그래프가 평탄해진다 = Zipf계수 감소 = 일부 오브젝트가 이전 레이어에서보다 인기 있던 개체는 덜 인기있어지고, 인기없던 개체는 더 인기 있다 = Haystack으로 갈수록 인기도의 편향성이 적게 나타난다

 

레이어에 있는 항목의 인기도와 클라이언트 브라우저의 인기도를 비교

• X축: 브라우저에서 정렬된 특정 사진 블롭의 순위
• Y축: 동일한 사진 개체에 대한 Edge/Origin/Haystack 레이어에서의 순위
• 인기도 분포는 모든 레이어에서 대략 Zipfian과 비슷하나, 특히 Edge 레이어에서 상위 100개 사진의 경우 순위가 많이 바뀐다
• 트래픽은 브라우저캐시(요청 수 많음)->엣지캐시->헤이스택(요청 수 적음)에 도달하면서 캐싱 레이어에서 요청을 처리하므로 인기있는 이미지에 대한 요청수가 꾸준히 감소한다 = 스트림의 캐싱 가능량이 점차 줄어든다 = Haystack으로 갈수록 Zipf 계수가 작아지는 이유 

 

그 다음으로는 인기도와 캐시 Hit과의 관계를 살펴본다

• (a) 1주일간 각 계층에서 처리한 클라이언트 요청에 대한 트래픽 점유율
• (b) 각 계층이 처리하는 트래픽을 이미지 인기도 그룹으로 분류
  • 브라우저 캐시, 엣지 캐시가 가장 인기 있는 10만 개의 이미지(그룹 A-E)에 대한 요청의 89% 이상을 처리
  • 인기가 떨어질수록(그룹 F, G) 캐시에 상주할 가능성이 낮아져 더 높은 비율의 요청이 Haystack 백엔드에서 충족
  • 오리진 캐시는 특히 엣지 캐시에 유지될 만큼 인기가 높지 않은 중간 인기 그룹(D, E, F)의 블롭에 효과적이다
  • 브라우저 캐시 적중률이 B그룹<C그룹인 이유? 일부 사진 그룹에 특정 클라이언트의 요청 수가 많은 이유는 해당 사진이 바이럴 되면서 동시에 많은 사람이 액세스하기 때문 => 고객이 바이럴 콘텐츠를 재방문할 가능성은 낮다
  • 엣지 캐시와 브라우저 캐시가 이미지 카테고리를 서비스할 때 서로를 보완적으로 작동한다(그룹 A-C 요청의 90% 처리)
• (c) 인기 있는 사진과 인기 없는 사진의 캐시 레이어별 적중률
  • 인기 있는 사진은 많은 사용자가 자주 액세스하므로 공유 캐시(엣지, 오리진 캐시)에 해당 사진이 있을 가능성이 높다
    
  • 인기 없는 사진은 공유 캐시에 존재하지 않을 수 있지만 한 사용자의 트래픽만 표시되는 개별 브라우저 캐시에는 여전히 남아있을 수 있다

 

엣지 캐시->오리진 캐시 데이터 센터로 전송되는 요청 트래픽의 지리적 패턴을 알아보자

• Facebook의 라우팅 정책은 지연 시간, 엣지 캐시 용량, ISP 피어링 비용을 기반으로 하기 때문에 물리적 위치를 반드시 반영하진 않을 수 있다 = 지리적으로 가까운 도시에서 요청의 대부분을 수신하지만, 가장 많은 요청이 반드시 가장 가까운 이웃 도시로 전달되는 것은 아님
• San Jose, D.C. 엣지 캐시는 피어링 품질이 우수하여 멀리 떨어져 있는 클라이언트의 경우에도 다른 엣지 캐시에 비해 우수

엣지 캐시에 대해 각 데이터 센터가 제공하는 트래픽의 비율 = 거의 일정 = 일관된 해싱

• 오리진 캐시: 엣지 캐시에 누락이 발생할 때마다 해당 사진의 일관된 해시값을 기반으로 데이터 센터(오리진 캐시)에 연락
• 각 엣지 캐시를 대신하여 각 데이터 센터가 처리하는 트래픽의 비율은 거의 일정하다 = 에지 캐시가 요청된 사진을 찾지 못하면 해당 사진의 일관된 해시값을 기반으로 데이터 센터에 요청한다.
• 즉, 오리진 캐시 서버는 지역이 아닌 콘텐츠에 기반하여 동작한다. 

 

데이터 센터에 요청이 이루어지면 최적의 속도를 위해 요청이 해당 데이터 센터 내에 유지되는 것이 이상적이지만 

오리진 캐시 서버가 Miss인 경우 Facebook 백엔드 서버에서 사진을 가져올 수 있는데, 이 프로세스는 네트워크 지연 및 기타 요인으로 인해 시간이 오래 걸릴 수 있다. 이러한 경우에는 서버는 원격 대안을 선택한다.

• 원격 대안: 이미지의 로컬 복제본이 오프라인 상태이거나 과부하 상태인 경우, 오리진 캐시 서버는 다른 데이터 센터에 있는 해당 이미지의 다른 복사본을 선택한다. 즉, Facebook의 광범위하게 분산된 스토리지 계층에 저장된 동일한 사진의 다른 사본을 말한다.

 

브라우저, 엣지, 오리진 캐시의 성능 및 효과를 각각 살펴보자면,

브라우저 캐시

한 달동안 브라우저 캐시 트레이스 중 초반 25%를 사용하여 캐시를 채운 후, 나머지 75%로 Hit ratio를 평가한다.

다양한 클라이언트 그룹에 대한 집계된 Hit raio

• 활동성이 낮은 그룹(1-10건 요청)은 39.2%의 Hit ratio이지만, 활동성이 높은 그룹(1K-10K건 요청)은 92.9%의 Hit ratio를 보였다. = 활동성이 높은 클라이언트는 활동성이 낮은 클라이언트보다 반복 콘텐츠에 액세스할 가능성이 높다

엣지 캐시

본 연구에서는 엣지 캐시에서 다양한 캐시 크기와 캐시 알고리즘을 시뮬레이션하여 Hit ratio를 개선할 수 있는지 가능성을 조사했다. 마찬가지로, 한 달동안 엣지 캐시 트레이스 중 초반 25%를 사용하여 캐시를 채운 후, 나머지 75%로 Hit ratio를 평가한다.

• 브라우저 캐시에 비해 무한 캐시(상한선)가 높다 = 개선의 여지가 많다는 가능성 제시

 

다양한 캐시 알고리즘과 캐시 크기의 효과

• (a) LRU, Clairvoyant, S4LRU 등의 정교한 알고리즘이 현재의 FIFO 알고리즘에 비해 상당히 높은 Hit rate를 보여준다. 그리고 이러한 개선은 각각 다운스트림 요청 감소로 이어진다.
• (b) LFU의 경우는 엣지에서 일부 트래픽을 보호할 수는 있지만 대역폭 소비를 증가시키기 때문에 Facebook에 개선 효과가 없다 = LFU는 오브젝트 적중률과 다운스트림 요청 감소 측면에서는 성능이 우수할 수 있지만, 바이트 적중률 측면에서는 현재 캐싱 알고리즘(FIFO)보다 성능이 떨어지며, 이는 오리진과 엣지 캐시 간에 더 많은 데이터를 전송해야 한다
  • Facebook의 경우 엣지 캐시의 주요 목표는 트래픽 보호가 아니라 대역폭 감소임 
• (c) 협업형 엣지 캐시: 모든 에지 캐시를 하나의 논리적 캐시로 결합하는 가상의 캐시로, 사진을 한 번만 저장하도록 하여 더 많은 사진을 저장할 수 있는 여분의 공간이 남는다.
  • 현재의 모든 엣지 캐시를 하나의 논리적 캐시로 결합하는 것이 여러 개의 개별 캐시를 사용하는 것보다 더 효율적인지 확인해보기 위한 실험 => 더 효율적인 수 있지만, 피어링 비용과 지연 시간 증가로 인해 궁극적으로 경제적이지는 않을 수도 있다
• 변곡점: 캐시 크기를 이 지점 이상으로 늘려도 적중률이 크게 개선되지 않으며, 오히려 오버헤드 증가로 인해 수익이 감소하거나 성능이 저하될 수 있음
  • 캐시 크기를 늘리는 것도 적중률을 개선하는 효과적인 방법이나 적절한 캐시 크기를 선택해야 한다. 

오리진 캐시

• s4lru 알고리즘이 최상의 결과를 나타낸다.

 

 

 

 

Discussion

일단 이미지 개체이기때문에 수정이 별로 일어나지 않아서 캐시의 효과가 더 극대화 된 것이 아닐까 하는 생각이 든다.

트레이스를 추출한 후 어떤 그래프를 그려야 하는지, 그리고 어떻게 그래프를 해석했는지에 대한 내용이 많이 도움 되었다.

그리고 워크로드 패턴, 트래픽 분포, 지리적 시스템 등 여러가지 관점에서 워크로드를 분석하는 것을 어떻게 시스템 설계에 사용하면 좋을지 인사이트를 제공해주는 연구였다.