논문 요약 — Scaling Memcache at Facebook

Rajesh Nishtala, Hans Fugal, Steven Grimm, Marc Kwiatkowski, Herman Lee, Harry C. Li, Ryan McElroy, Mike Paleczny, Daniel Peek, Paul Saab, David Stafford, Tony Tung, and Venkateshwaran Venkataramani. 2013. Scaling Memcache at Facebook. In Proceedings of the 10th USENIX conference on Networked Systems Design and Implementation (nsdi’13). USENIX Association, USA, 385–398.

Scaling Memcache at Facebook - Meta Research

2013년 출간된 이 논문은 facebook의 대규모 캐시 스토리지 시스템인 memcache의 시스템 디자인을 소개하고 있다. facebook에서는 캐시 스토리지로서 매우 큰 (논문에 따르면 “the largest memcached installation in the world”) 규모의 memcached 클러스터를 구축하여 사용하고 있다고 한다. 이 논문에서는 혼동을 피하기 위해 ‘memcached’는 해당 오픈소스 솔루션 자체만을 가리키고 facebook의 캐시 스토리지 시스템은 ‘memcache’로 지칭하고 있다.

필자에 따르면 Facebook의 스토리지 접근 패턴은 아래와 같은 특징을 갖고 있다.

• 읽기 요청이 쓰기 요청 대비 압도적으로 많음
• facebook에서는 사용자의 요청 하나가 여러 memcache 읽기 요청으로 이어지는 경우가 많다고 한다. 예를 들어 일부 빈번히 방문되는 페이지 중 하나는 평균적으로 사용자 요청 하나 당 memcache 읽기 요청이 521번 발생한다고 한다. 이러한 상황에서 cache는 DB의 로드를 줄이기 위해 아주 효과적일 수 있다.
• 많은 fan-out

위 그림은 facebook에서 요청 하나가 조회하는 데이터를 DAG로 표현한 것이라 한다. mysql, HDFS, 여러 백엔드 서비스 등 상이한 데이터 소스를 필수적으로 지원해야 한다. 이러한 유연함과 확장성은 분산 시스템이 아니라면 달성하기 어려울 것이다.

필자에 따르면 이러한 요구사항은 memcache의 디자인에 많은 영향을 미쳤다. Memcached는 자체적인 클러스터링 기능을 지원하지 않는다(현재도 동일한 것 같다). memcache 시스템은 memcached 머신들을 엮어서 분산 시스템을 구축하기 위한 자체적인 configuration, aggregation, routing을 갖추고 있다. 이 시스템의 최종적인 아키텍쳐는 Figure 2와 같다.

시스템의 발전에 맞춰 이 논문에서는 규모의 단계로 섹션을 나누고 각각의 테마를 달리하고 있다:

• 단일 클러스터
• 높은 read-heavy workload
• 많은 fan-out
• 단일 데이터센터의 여러 클러스터
• data replication
• 여러 개의 IDC
• consistency

필자는 시스템을 점차 진화시키면서 두 가지 핵심적인 설계 목표를 아래와 같이 밝히고 있다.

• 모든 변화는 문제가 있을 수 있다. 그러므로 일부 유즈케이스만을 위한 최적화는 지양한다
• 일시적인 캐시 불일치는 DB의 로드를 줄이기 위해서 허용 가능한 trade off 사항이다

그럼 이제 memcache 시스템을 구성하는 메카니즘에 대해 알아보자.

단일 스토리지

단일 스토리지로서 memcache는 크게 아래와 같은 유즈케이스를 지원한다.

• DB의 캐시 레이어로서 query cache
• 그냥 key-value store로서의 Generic cache

이렇게 두가지 케이스를 지원한다고 한다.

이 중 query cache로서는 Facebook 내부의 수많은 mysql 데이터베이스의 캐시 레이어로서 사용된다.

Query cache로 사용될 때는 figure 1과 같이 demand-filled look-aside cache라는 패턴을 따른다. 구체적으로는 아래와 같다.

읽기 요청

1. Cache 조회
2. Cache miss일 경우 db 조회
3. 조회한 값을 cache에 생성

쓰기 요청

1. Db에 먼저 데이터를 업데이트
2. Cache 데이터 삭제

쓰기 요청시 cache 값은 업데이트하지 않고 삭제한다. 삭제 요청은 멱등성이 있기 때문에 문제가 발생했을 때 재시도를 해도 동시성 이슈를 피할 수 있다.

단일 클러스터

이 섹션에서는 수천 정도의 머신으로 이루어진 하나의 클러스터를 다룬다. 이 규모에서는 응답 속도와 cache miss로 인한 load 증가가 주요한 고려 사항이 된다.

응답 속도(latency)

캐시 데이터는 수백 대의 머신에 consistent hashing을 통해 분산 저장되므로 각각의 웹 서버는 여러 memcache 머신을 골고루 조회하게 된다. 결국 모든 웹 서버가 모든 memcached 서버를 조회하게 되는 all-to-all 패턴이 발생하게 되는데, 이는 TCP incast congestion의 원인이 된다.

Memcache client는 직렬화, 압축, 라우팅, 에러 핸들링, request batching 등 여러 기능을 전담하는데, latency 면에서의 개선은 이 client에 초점을 맞춰서 진행했다. 클라이언트는 외부 설정 시스템을 통해 memcache의 인스턴스 정보를 유지하고 있다.

요청 병렬화, batching

네트워크 트립을 최소화하기 위해 필요한 데이터의 DAG를 그리고, 요청을 병렬화 또는 batching할 수 있도록 하여 레이턴시를 개선한다. 평균 한 요청당 24개의 키를 가져오도록 하여 요청 수를 최적화할 수 있었다.

client — server 간 통신

client는 애플리케이션에 임베딩할 수 있는 라이브러리와 웹서버 머신에 떠있는 mcrouter라는 이름의 프록시, 이렇게 두 가지 형태로 제공이 된다. Get 요청은 mcrouter를 거치지 않고 웹서버에서 memcache 서버로 바로 UDP 요청으로 보낸다. TCP가 아니기 때문에 커넥션을 맺을 필요도 없고 따라서 메모리 오버헤드도 없다. 요청이 버려지거나 순서가 틀려도 재시도도 없다. 그냥 cache miss로 취급하고 바로 DB를 조회한다(단, cache를 set하지는 않는다)

set과 delete 요청은 reliability를 위해 mcrouter를 거쳐 tcp로 보내진다.

Incast congestion

클라이언트에 tcp 동시 요청 수를 제한하는 sliding window를 걸어서 incast congestion을 막을 수 있다. window의 크기는 tcp congestion control처럼 증감할 수 있다.

로드

memcache가 DB의 로드를 효과적으로 줄이려면 cache miss를 줄여야 한다.

lease

memcache에서는 lease 메카니즘을 통해 stale set 발생을 막는다.

Stale set은 아래와 같은 경우 때문에 생긴다

1. Web server a가 db에서 결과 a를 조회
2. db의 값이 b로 업데이트
3. Web server b가 db에서 결과 b를 조회
4. Web server b가 결과 b를 캐시에 저장
5. Web server a가 결과 a를 캐시에 저장

Web server a는 이미 stale된 데이터를 들고 있지만 a가 b보다 cache를 더 늦게 갱신하지 못하도록 보장하지 못하기 때문에 이미 stale된 데이터가 캐시에 저장되는 현상을 stale set이라고 한다.

Memcache 서버가 unique한 Lease id를 보유하고 있다 cache miss가 날 때 해당 id를 클라이언트에 보내주고, db가 업데이트될 때마다 lease id를 갱신한다면 1에서 web server a가 갖고 있는 lease id는 2에서 갱신된 lease id와 일치하지 않아 stale된 값을 갖고 있는 web server가 캐시를 갱신하는 것을 막을 수 있다.

만약 (바이럴 컨텐츠처럼) 빈번한 읽기 요청을 받는 데이터가 캐시에서 삭제된다면 캐시 미스로 인해 모든 웹서버가 db를 조회하게 되어 db에 핫스팟이 생길 것이다. 이를 Thundering herds라고 부른다. Lease id를 10초에 한번으로 제한하고, 그 사이에 캐시 읽기 요청을 보낸 클라이언트에게 db를 조회하는 대신 10초 후 다시 요청을 보내라는 응답을 한다면 thundering herds 문제를 해결할 수 있다.

memcache pool

다양한 접근 패턴, 메모리 풋프린트, QoS 요구사항에 맞추기 위해 memcache는 pool을 구성하는 기능이 있다. 예를 들어 적은 수의 키 들이 빈번하게 접근하는 패턴을 위한 작은 pool을 구성하고, 키의 수는 많고 거의 접근되지 않지만 cache miss가 매우 치명적인 경우를 위해 memory size가 큰 pool을 구성하는 식의 튜닝이 가능하다.

pool 레플리케이션

만약 풀이 1. 여러 키에 동시에 접근하고 2. 한 두 대의 서버에 들어가는 정도의 규모이고 3. 단일 서버로 트래픽 감당이 힘들다면 레플리케이션을 고려한다.

client가 request batching을 지원하기 때문에 memcache는 sharding보다는 replication을 사용한다.

이 경우 cache invalidation도 모든 레플리카에 진행해야 한다.

handling failure

memcache에 장애가 날 경우 이를 사용하는 백엔드 서비스로 장애가 번질 위험이 있다. 규모에 따라서 1. 네트워크 / 서버 장애로 인한 소규모 장애, 2. 클러스터의 상당 부분의 호스트가 장애에 빠진 상황으로 구분할 수 있다. 전체 클러스터가 오프라인인 상황이라면 다른 클러스터로 유저의 요청을 분산시킨다.

소규모 장애의 경우는 자동 복구 시스템에 의존하는데, 이 시스템은 수 분정도가 소요될 수 있고, 그때문에 장애가 번질 위험이 있다. 이 경우 전체의 약 1%를 차지하는 Gutter라는 예비 서버가 장애가 난 서버를 대체한다. 클라이언트가 응답을 받지 못하면 서버가 장애 상황에 빠졌다고 가정하고 Gutter pool로 요청을 다시 보낸다. 캐시 미스가 날 경우 Gutter에 캐시를 채워 넣는데 빠르게 만료된다.

풀의 멀쩡한 서버를 사용할 경우, hotspot이 있다면 로드가 크게 올라갈 수 있다. gutter는 이런 현상을 막아준다.

단일 리전: Replication

단순히 memacache 서버를 늘리기만 하면 all-to-all 패턴으로 인한 incast congestion 문제때문에 금방 성능 한계가 올 것이다. facebook에서는 all-to-all 패턴의 규모를 제한하기 위해 memcached server들을 frontend cluster로 나누고 하나의 웹 서버에서는 하나의 클러스터만 사용하도록 관리한다. 이렇게 하나의 스토리지 클러스터에 여러 frontend cluster를 합쳐 하나의 리전으로 정의한다. 이 섹션에서는 리전 내부에서 데이터 레플리카를 어떻게 관리하는지가 주요 테마가 된다.

regional invalidation

웹 서버가 쓰기 요청을 하면 로컬 클러스터의 값 만을 삭제하고, 다른 클러스터는 건드리지 않는다. facebook에서는 자체적인 mysql cdc인 mcsqueal이 db의 업데이트에 맞춰 cache 삭제 요청을 리전 내 모든 frontend cluster로 보내는데 이 요청 중 실제로 캐시를 삭제하는 것은 4% 정도 뿐이라고 한다. 이를 최적화하기 위해 마찬가지로 삭제 요청의 batching을 수행한다.

웹 서버에서도 자체적으로 cache invalidation을 수행하지만 이 경우 크게 두가지 문제가 있다. 1. 단일 웹서버에서 보내는 cache invalidation은 mcsqueal보다 오버헤드가 크다. 2. 설정 실수 등의 이유로 캐시 삭제가 잘못되면 복구하기 힘들다. (대부분의 경우 클러스터 재시작을 해야 한다) mcsqueal은 DB의 커밋 로그를 사용하기 때문에 그냥 리플레이하면 그만이다.

regional pool

각 frontend cluster는 유저의 요청과 독립적으로 캐싱한다. 즉, 자주 사용하는 데이터라면 아마 리전 내의 대부분의 cluster가 동일한 데이터를 보유하고 있을 것이다. 이렇게 되면 클러스터 하나 정도는 오프라인으로 돌려도 cache hit rate가 크게 떨어지진 않는 대신 여러 레플리카에서 같은 데이터를 유지한다는 메모리 비효율성이 발생할 것이다. 따라서 중요성이 떨어지는 데이터의 레플리카 수를 줄일 수 있다면 좋을 것이다.

레플리카의 수를 줄이기 위해 한 리전 안에서 모든 클러스터가 같은 memcached 서버를 공유하도록 하는데 이를 regional pool이라고 부른다. 클러스터 안팎을 지나는 대역폭은 클러스터 내부 대비 40%나 적기 때문에 이러한 비용 절감은 대역폭, 반응 속도, 장애 가용성과 trade off 관계에 있다. 현재 어떤 데이터를 regional pool에 쓰고 어떤 데이터를 각 cluster마다 쓸지는 사람이 휴리스틱하게 판단하고 있다고 한다.

cold cluster warmup

새 memcache 클러스터를 생성하고 바로 웹 서버가 쓸 수 있게 한다면 초반에는 cache miss가 엄청 많을 것이다. 이를 피하기 위해 기존 클러스터에서 데이터를 복제해 오는 warm up을 하여 시간을 단축할 수 있다.

이떄 inconsistency에 신경써야 한다. Cold cluster에서 데이터를 업데이트하고 캐시 값을 삭제한 직후 누군가 warm cluster에서 stale value에 접근하고, 그 값이 그대로 cold cluster에 쓰인다면 inconsistency가 발생할 것이다. 이를 막기 위해 cold cluster는 삭제한 데이터를 2초간 쓰지 못하도록 hold-off를 갖는다. 클라이언트는 cold cluster에서 캐시 미스가 발생하면 warm cluster에서 값을 가져와 cold cluster에 쓰기 하는데 이때 만약 hold-off에 걸린다면 warm cluster의 값이 stale되었을 가능성이 있으므로 DB에서 값을 가져오도록 한다.

Across region: consistency

멀티 IDC 환경에서 facebook은 mysql replication을 활용한다. 쓰기 클러스터는 하나의 데이터센터에만 위치하고, 나머지 클러스터는 모두 레플리카이다.

메인 리전에서의 업데이트

메인 리전에서 DB에 업데이트가 있다고 했을 때, 만약 아직 이 업데이트가 레플리카로 전파가 안된 상황에서 모든 리전의 cache를 invalidation해 버리면 레플리카의 stale된 값으로 cache가 채워질 위험이 있다. 따라서 mcsqueal은 메인 리전에 위치한 memcache만 invalidation시킨다.

만약 마스터 리전이 아닌 리전에서 키 k를 업데이트 요청했다고 해보자. Primary DB에 업데이트하고 Memcache 서버에서 키 k를 삭제했는데 이 업데이트가 해당 리전의 레플리카에 아직 전달되지 않았다고 해보자. 그럼 유저는 업데이트를 했는데도 이전의 데이터를 받아보는 일시적인 inconsistency가 발생할 것이다.

이 문제를 피하기 위해 remote marker라는 메커니즘을 사용한다. Remote marker가 있는 데이터는 레플리카 DB에 변경사항이 반영이 아직 안되었을 가능성이 있으므로 해당 데이터는 메인 DB를 조회한다. 이 경우 키 k를 업데이트한다면 순서는 이러하다.

1. 리전의 리모트 마커 r_k를 표시
2. 메인 DB에 k 업데이트와 r_k invalidation을 커밋
3. 로컬 리전의 캐시에서 k를 삭제

메인 DB의 변경사항이 로컬 리전으로 전파되었다면 리모트 마커 r_k는 invalidate될 것이므로 리모트 마커가 레플리카 DB의 업데이트 여부를 알려주는 역할을 한다. 리모트 마커는 regional pool에 위치한다.

이 방식은 동시에 여러 개의 변경이 들어와 최신 변경사항을 반영하기 전에 리모트 마커가 지워져버릴 위험을 허용한다. 리모트 마커는 캐시의 일반적인 사용례에서 동떨어져있음을 언급할 필요가 있다.

운영 상의 측면에서 리전 간 통신은 지리적으로 먼 거리를 이동하므로 높은 비용을 갖는다. 앞서 언급한 mcsqueal의 cache invalidation은 레플리카 DB에도 똑같이 작동한다.

단일 서버 성능 최적화

All-to-all 패턴에서는 하나의 서버가 병목이 될 위험성이 항상 존재한다. 이 섹션에서는 단일 서버를 위한 최적화 방법을 소개하고 있다.

성능 최적화

1. 해시 충돌을 피하기 위한 해시 테이블 크기 자동 확장
2. 글로벌 락을 사용하여 서버 멀티스레드 화
3. 각 스레드마다 UDP 포트를 하나씩 부여하여 네트워크 인터럽트 오버헤드 최소화

앞 두 가지는 오픈소스 업스트림에 기여하였고, 나머지는 아직이다.

adaptive slab allocator

memcached는 slab allocator를 사용하고 있다. facebook에서는 slab의 크기를 주기적으로 최적화하는 allocator를 구현해서 사용하고 있다.

transient item cache

memcached의 ttl은 lazy하게 작동한다. 대부분의 경우 별 문제 없지만 간혹 CPU 버스트를 유발하는 경우가 있다. facebook에서는 수명이 긴 키들은 기존 구현 방식을 따르되 수명이 짧은 키들을 circular buffer나 linked list 형식으로 갖고 있으면서 1초에 한번씩 만료된 키를 evict하도록 하는 구현을 추가해 사용하고 있다.

결론

필자는 memcache 시스템을 구축, 운영하면서 아래와 같은 교훈을 얻었다고 특별히 언급하고 있다.

• 캐시 레이어와 persistent storage를 분리하면 각각 독립적인 확장이 가능하다
• 모니터링, 디버깅, 운영 효율성 또한 성능만큼 중요하다
• stateful 한 컴포넌트는 stateless한 컴포넌트보다 관리가 훨씬 복잡한 만큼 client를 stateless하게 유지하는 것은 생산성 면에서 아주 큰 도움이 된다
• 일시적인 기능의 차이가 발생하더라도 시스템은 점진적 rollout, rollback을 허용해야 한다.
• 간결함은 필수