Scaling Memcache at Facebook

시대가 급변해가면서 많은 트래픽을 감당하기 위해서 안정적으로 운영하기 위한 다양한 기술들이 나타나고 있습니다.

더 복잡한 요구사항들을 구현하기 위해서 대기업들이 어떻게 발전하고 있는지 여러 논문들을 통해 알아볼 수 있습니다.

처음에는 이런 컴퓨팅 논문을 읽어보는 것이 부담으로 느껴질 수 있지만 한번 자세히 읽어보면 정말 깊은 인사이트를 얻을 수 있다고 듭니다. 앞으로 해외 컴퓨팅 논문을 이해하기 쉽게 글로 요약하고 설명하는 블로그 포스팅을 작성해볼까 합니다.

여러분들도 캐시를 적용하기 위해서 key-value형태를 많이 보셨을 텐데 실제로 운영하다보면 메모리 관리하는것이 상당한 난이도를 요구합니다. 우리는 안정적으로 캐시를 운영하기 위해 캐시에 대해 어떤 문제상황을 고려해야하는지 이해해보면 많은 도움이 될것이라 생각합니다.

오늘은 Facebook에서 사용하는 캐시 Memcache 의 내부 동작을 이해해보고자 합니다. 가시죠.

Key word

Memcached
Key-value
Auto Scaling
High I/O
1 trillion Request demand
near real-time
open-source
geograph-ically dsistributed cluster.
low latency
look-aside cache
shared storage pool at low cost
mcsquere
Adaptive Slab Allocator Tuning

What is Memcached?

Simple Memory Caching Solution / main consist element of Key-Value Memory Availability

  • Free!!
  • OpenSource

Consistent 보장

Consistent 보장하며 Cluster 관리하기

클러스터가 Incast Congestion이 발생하기 때문에 여러 클라스터로 나누어 관리합니다.

mcsqueal

  • 각 클러스터간 DB가 Deployment시켜 SQL에서 삭제된 키를 추출해 모든 Frontend Cluster에 Notify시켜 Consistent를 보장합니다.

MySQL을 일종의 Queue처럼 사용하기도 합니다.

실제로 대한민국 2금융권 일부는 Oracle DB Queue를 사용하기도 하니 말이 안되는 소리는 아니다.

Cold Cluster Warm up

Remote Marker Machanism

  • Master가 Non-Master에게 Replication하는 시간동안 데이터 UPDATE Operation을 Master로 Redirect합니다.

Lease ( 일관성, 동시성 관리 )

Stale Set(Memcache에 저장된 데이터가 최신 데이터와 불일치) / 여러 클라이언트의 동시 업데이트로 인한 업데이트 순서 혼잡

Thundering Herds(특정 키의 Read/Write Overload) / 특정 키의 캐시미스가 발생시 DB 동시 쿼리 전송, 동일한 데이터 동시 업데이트시 불필요한 중복 작업)

Lease의 기본 개념

Lease는 특정 키를 Memcached에 저장(set)할 권한을 클라이언트에 일시적으로 부여하는 방식입니다. Lease 메커니즘은 Stale Set과 Thundering Herds 문제를 해결하기 위해 다음과 같이 동작합니다

  1. 캐시 미스 발생 시 Lease 발급:
    • 클라이언트가 특정 키에 대해 캐시 미스를 경험하면, Memcached 서버는 해당 키에 대한 Lease 토큰(64비트 고유 ID)을 클라이언트에 발급합니다.
    • 이 토큰은 해당 클라이언트만이 데이터를 Memcached에 저장할 수 있도록 허용합니다.

Lease Token를 발행해서 다른 클라이언트가 데이터를 재설정할 수 있도록 해 미스로 인한 부하를 줄입니다.

성능 개선하기

2. UDP / TCP Optimization

UDP more better

UDP 는 패킷 손실과 순서 오류를 감지하는 일련의 과정을 클라이언트측으로 위임합니다. 때문에 TCP와는 다르게 비동기로 요청이 가능하지만, 복구 메커니즘은 제공하지 않으니 0.25% 정도의 요청 손실이 발생할 수도 있습니다.

그럼 못 믿는거 아니야?

그럼 꼭 믿어야 하는 부분만 TCP를 쓰면 된다. / SET, DELETE 작업을 TCP를 통해 해서 Reliability를 높이고, UDP Retry 메커니즘 문제를 해결합니다.

그럼 커넥션이 너무 많아져서 문제를 해결하지 못할텐데?

  • 고도의 병렬성과 오버 서브스크립션을 통해 높은 처리량을 확보
  • TCP Request때문에, mcrouter를 통한 연결 집합을 통해 효율성을 높입니다.

클라이언트 사이드는 슬라이딩 윈도우 메커니즘을 사용하여 요청을 제어해서 요청 스케쥴링하는 시간을 감소시킨다.4

Request Wait Time을 줄이기 위해서 더 작은 윈도우 크기로 설정합니다.

Incast Congestion을 줄이기 위한 적절한 균형을.

Handling Failure

Gutter

A. 장애 발생 시 작동 원리

  1. 요청 리다이렉션:
    • 클라이언트가 특정 Memcached 서버에서 데이터를 가져오지 못하면, 해당 요청을 Gutter 풀로 리다이렉션합니다.
    • Gutter 풀은 클러스터 내의 소규모 서버 집합(약 1%의 Memcached 서버)으로 구성되어 있습니다.
  2. 캐시 데이터 처리:
    • Gutter 풀에서도 데이터를 찾지 못하면 클라이언트는 데이터베이스에서 데이터를 가져와 Gutter 풀에 저장합니다.
    • 이후의 요청은 Gutter 풀에서 처리되어 데이터베이스의 부하를 줄입니다.
  3. 빠른 데이터 만료:
    • Gutter에 저장된 항목은 짧은 만료 시간을 가지며, 장애 서버가 복구되면 더 이상 사용되지 않습니다.

B. 부하 완화 메커니즘

Gutter는 Memcached 장애로 인해 발생할 수 있는 캐시 미스(Cache Miss)와 그로 인한 데이터베이스 부하를 완화합니다:

  • 장애 서버의 요청이 모두 데이터베이스로 전달되면 데이터베이스는 과부하로 인해 추가적인 장애를 초래할 수 있습니다.
  • Gutter는 이러한 요청을 대체 처리하여 캐시 히트율을 최대 50%까지 유지하며, 데이터베이스로의 요청을 최대 25%까지 줄입니다.

이 과정에서 단순히 키를 재해시(Hash)하지 않습니다. 특히 Hot Key가 다른 서버에 할당되어 새로운 병목을 초래할 위험을 줄입니다.

Client가 Memcached 서버로부터 응답을 받지 못하면 즉히 Gutter Pool로 Redirect 시켜서 저지연을 보장합니다.

Memory Cache Optimization

  • Slab Allocator Tuning:

    • 메모리를 동일한 크기의 청크로 나누어 할당하는 방식입니다. 초기 고정 메모리 할당 방식은 변화하는 요구사항을 대응하기 어려웠습니다. 이를 위해 Adaptive Slab Allocator를 적용했습니다.
    • Redistributing Algorithm : 주기적으로 평가하여 더 많은 메모리가 필요한 슬래브에 재할당합니다.
    • LRU Policy : 이 정책으로 우선순위를 선정해서 슬라브를 재조정해서 less active class를 high eviction rates할수 있도록 순위를 재조정해서 최적화했습니다.

  • Transient Item Cache:

    • 만료시간이 짧은 항목은 Circular Buffer 에 저장되고, 정해진 시간 이후 자동 삭제됩니다.
    • 이 개선으로 메모리 사용률을 대폭 감소시켰으며, 특히 특정 키 유형에서 캐시 점유율을 6%에서 0.3%로 줄였습니다.

  • Fine-grained Locking

    • coarse-grained locking에서는 모든 데이터베이스 구조에서 Global Lock을 사용해서 동시성을 제한했지만, Fine-grained Locking은 각 데이터 구조나 데이터 Chunk에 개별 잠금을 적용해 동시 요청 처리 효율을 극대화합니다.

      Coarse-grained Locking vs. Fine-grained Locking

      • Coarse-grained Locking: 단일 락으로 모든 데이터 접근을 제어 → 병렬 처리 제한.

      • Fine-grained Locking: 특정 데이터 구조나 청크에 개별 락을 적용 → 병렬 처리 개선.

        Rock Contention(락 경합)을 줄이고 멀티코어 환경에서 더 높은 병렬성을 제공하기 위해 Fine-Grained Locking이 도입되었습니다.

        이 Fine-grained Locking은 각 해시 버킷(bucket)마다 개별 락을 할당하여 동시 접근을 허용하며

        get연산은 shared lock / set, delete는 exclusive lock을 사용해 데이터 무결성을 보장

메모리를 최적화하면서 동시성 제한으로 인한 성능 저하를 개선하기 위해 위와 같은 방법들을 통해서 문제를 해결했습니다. 이렇게 구성하게 되면 히트율 상승 뿐 아니라 멀티 코어 활용을 극대화 할 수 있고 지연 시간을 감소시킬 수 있습니다.

Demand-Filled Look Aside Cache

Look-Through Cache(데이터가 캐시에 사전 로드)되는게 아니라 클라이언트가 요청 시점에 데이터를 캐시에 추가하는 동적 캐싱 전략입니다.

선정 이유

  • 읽기 중심 워크로드 : 읽기 부하가 쓰기보다 많기 때문
  • 데이터 접근 다양성 : 여러 소스(MySQL, HDFS 등)에서 데이터를 가져와야 합니다.

위 선정 이유가 있어서 초기 로드 작업시 과도한 리소스가 필요하지 않아지고, 불필요한 데이터 캐싱을 막을 수 있습니다.

Availability

Replication 전략

Replication Within Pools

3가지 조건을 충족시키는 경우 Replication을 실시합니다.

  1. Application에 많은 키를 요청할 경우
  2. 전체 데이터셋이 하나 또는 두개의 Memcached서버에 저장될 수 있을 때,
  3. 요청률이 특정 서버가 처리할 수 있는 수준을 초과할 때

Region Replication

  • Invalidation Mechanism
    • Master 데이터베이스의 변경이 일어나면, 해당 지역의 Memcached캐시를 먼저 무효화 해서 데이터 일관성을 유지합니다.
    • 변경 데이터가 Replica 지역에 동기화될 때까지 데이터 삭제를 지연시키는 Remote Marker 메커니즘을 활용해서 eventual consistency 를 보장합니다.

Mamcache Pools의 구성방식 ( 운영 노하우 )

Memcache는 각 용도에 따른 별도의 Pool들을 구성하여 지연시간을 최적화하였습니다.

  • Wildcard Pool : 모든 애플리케이션에 일반적으로 사용되는 자원 기본 풀 / 가장 사용량이 많고 가장 다양한 애플리케이션의 요청을 처리합니다.
  • Special Pool : 특정 패턴이나 키에만 별도로 설정된 풀입니다. / 장기적으로 자주 사용되며 캐시 미스 비용이 높은 키는 별도로 관리합니다.
    • High Churn Pool : 자주 접근하는 키를 포함하지만 캐시 미스 비용이 높은 경우 사용.
    • Low Churn Pool : 드물게 접근되지만 캐시 미스 비용이 많이 드는 경우에 적용됩니다. 대량의 데이터를 포함하고 있으며, 상대적으로 메모리 소모가 적습니다.

Memcache 내부 구현 메모리 구조 V Shared Memory

도입 계기

  • Memcached 서버가 재시작되면 데이터가 손실되어 데이터베이스로 트래픽 병목현상 발생
  • 업그레이드 시간 증가 : 캐시를 다시 채우려면 최대 12시간이 소요. 서비스 응답 시간이 증가.

위 문제들을 해결하기 위해 운영체제의 공유 메모리에 저장하는 방식을 도입.

동작원리

  • 데이터와 주요 메타데이터(키와 만료시간)을 공유 메모리에 보관하여 Memcached 가 재시작되더라도 유지.
  • 업그레이드시 공유 메모리에서 데이터를 불러오면 즉시 캐시 활성화 시킬 수 있음.
  • LRU(Least Recently Used) 정책과 동일하게 동작시키기.

6. 🍨 Sip of Paper 🍨

  • Cache를 구현하는데 캐시로만 구현할 필요는 없다. / DB와 Memory Cache의 혼합
    • DB Replication
  • TCP와 UDP의 혼합 접근
  • look-aside Cache
  • 요청의 크기에 따라 별도의 클러스터를 구성
  • 분산 서버간의 조정을 제공하지 않고 지연 시간과 로드를 줄이는 집요한 목적성 (대단히 캐시스럽다)
  • Consistent Validation

Reference

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, Venkateshwaran Venkataramani {rajeshn,hans}@fb.com, {sgrimm, marc}@facebook.com, {herman, hcli, rm, mpal, dpeek, ps, dstaff, ttung, veeve}@fb.com Facebook Inc.

BlackBean99
BlackBean99

티스토리툴바