Facebook 이 캐시 데이터 일관성을 관리하는 방법

Overview

Facebook 의 시스템은 초당 수십억 개의 요청이 들어온다고 합니다.

 

이렇게 대규모 트래픽이 상황에서는 일관성을 유지하는 것은 적은 트래픽일 때보다 훨씬 복잡할건데요.

 

본문에서는 Facebook이 캐시 데이터와 영속성 데이터의 일관성을 어떻게 유지하는지 소개하겠습니다.

 

본 글은 Facebook 에서 발표한 논문인 Scaling Memcache at Facebook 를 참고해서 많이 요약한 글인데요.

 

해당 논문에서는 캐시 레이어 확장 방법도 상세히 소개하니, 궁금하시면 원문을 확인해 보는 걸 추천드립니다.

 

 

High-Level Overview of Facebook's System Architecture

시스템 구조는 그림으로 봐도 좋을 것 같은데요. 아래의 설명과 첨부한 이미지를 비교해보면서 보면 더 이해하기 쉬울 것 같습니다.

 

 

 

먼저, Facebook은 전 세계에 걸쳐 클러스터를 여러 지역(Region)으로 분산하여 관리하고 있구요, 각 지역은 다음과 같은 구성 요소로 이루어져 있습니다:

• Front-End Clusters (웹 서버 + Memcached): 사용자의 요청을 처리하고 데이터를 캐싱하여 빠른 응답 시간을 보장하는 역할을 합니다.
• Storage Cluster (MySQL 등): 실제 사용자 데이터와 시스템 정보를 저장하는 역할을 합니다.

 

Storage Cluster와 Front-End Cluster의 상호 작용:

• Storage Cluster 에서 생성된 데이터는 Front-End Cluster 내의 Memcached 로 복제되어 사용자에게 빠른 데이터 접근을 제공하구요. 또한, Storage Cluster 는 캐시 무효화 요청을 통해 기본적으로 Memcached 에 최신 데이터를 유지하려고 합니다. 

 

다중 Region 과 데이터베이스 구성:

• Facebook은 다수의 Region 을 사용하며, 각 Region 마다 데이터베이스 Master 와 Slave 로 구분합니다.

 

Front-End Clusters 의 다중화:

• 하나의 지역 내에서도 Front-End Clusters 는 여러 개로 분리됩니다. 이렇게 분리된 이유는 다음과 같습니다:
  • Network Incast Congestion: 네트워크 내 많은 호스트가 동시에 소수의 수신자(예: Memcached)에 데이터를 전송할 때 발생하는 네트워크 혼잡 현상입니다. 이 현상은 네트워크 대역폭 병목 현상으로 이어져 패킷 손실과 지연 시간 증가의 문제를 일으킬 수 있습니다.
  • Fault Tolerance: 여러 개의 Cluster 로 분리함으로써, 하나의 Cluster 가 실패하더라도 다른 Cluster 들은 안전하게 운영될 수 있습니다.

 

캐시 스토어로 Memcached 선택:

• 저지연 및 고성능 (Low Latency, High Performance) 과 제한된 엔지니어링 자원 및 시간 (Limited Engineering Resources and Time) 을 고려했을 때 Memcached 를 선택헀습니다. (개발팀에 익숙한 기술을 이유로 선택한 것 같습니다.)

 

How Facebook Manages Cached Data

Facebook에서는 Memcached에 두 가지 주요 유형의 데이터를 저장합니다:

• Query Cache: 이는 주로 데이터베이스에서 직접 조회할 수 있는 데이터로 구성됩니다. 이 데이터 캐싱 목적은 데이터베이스의 부하를 분산시키는 것으로, 데이터베이스에 대한 직접적인 쿼리 수를 줄이기 위해 캐시에 저장합니다. 
• Generic Cache: 이 데이터는 머신러닝과 같은 애플리케이션에서 사전 계산된(pre-computed) 결과들로 구성됩니다. 이러한 종류의 데이터는 사용자의 시청 이력과 선호도와 같이 다양한 애플리케이션에서 활용될 수 있는 데이터들을 말합니다.

 

Facebook은 데이터를 처리하는 두 가지 주요 경로, 즉 읽기 경로와 쓰기 경로에서 Memcached를 활용합니다:

• Read Path: 'Look Aside' 패턴을 사용합니다. 즉 먼저 캐시에 데이터를 조회해보고, 캐시에 해당 데이터가 없을 경우엔 데이터베이스에서 조회한 후, 이를 캐시에 저장(Set)하는 방법입니다.
• Write Path: 데이터베이스에 데이터를 쓴 후, 캐시에 해당 데이터를 무효화합니다. 데이터를 직접 업데이트하는 것도 가능하지만, 캐시 무효화 작업은 데이터의 일관성을 보장하는 멱등성 있는 연산이기 때문에 이걸 사용합니다. 

 

총 2가지의 캐시 무효화 과정:

• 1) 웹 서버는 데이터를 Storage Cluster 에 있는 영속성 저장소에 업데이트된 후, 자신의 로컬 캐시인 Memcached 에 캐시 무효화 요청을 합니다. 이 과정은 완벽한 일관성을 보장하지는 않지만, 빠른 갱신과 기본적인 일관성은 보장할 수 있습니다.
• 2) 'Invalidation Batch Processing' 을 통해 클러스터 전체에 캐시 무효화 요청을 전달합니다. 이는 데이터베이스에서 커밋된 로그를 바탕으로 모든 변경 사항을 감지하고, 해당 지역의 모든 Front-End Cluster 에 있는 Memcached 서버에 무효화 요청을 보내는 과정입니다. 중요한 건 이 요청들은 직접적으로 Memcached 로 요청이 전달되진 않습니다. 중간 라우터 계층인 mcrouter 를 통해 캐시 무효화 과정은 Memcached 로 전달됩니다.

 

mcrouter의 역할:

• mcrouter는 이러한 캐시 무효화 요청을 관리하는 컴포넌트입니다. 배치 프로세스에서 Memcached 로 직접 캐시 무효화 요청을 전송하면 해당 시스템에 과부하가 발생할 수 있어, mcrouter를 사용하여 이를 방지하는 목적으로 사용합니다.
• mcrouter 인스턴스는 배치 요청을 받아 적절한 Memcached 서버로 라우팅하는 역할을 합니다. 또한, Memcached 가 응답하지 않을 경우를 대비해 캐시 무효화 요청을 내부적으로 버퍼링하는 기능을 갖추고 있습니다.

 

How Facebook Ensures Cache Data Consistency

Facebook Design Goals:

• Facebook의 설계 목표는 대규모 트래픽을 효과적으로 처리하는 것입니다. 이를 위해 일관성(Consistency)만을 고려할 수는 없으며, 일관성과 성능(Performance) 사이의 균형을 찾는 것이 중요합니다. 그래서 Facebook 은  Strong Consistency 를 보장하는 대신 Eventually Consistency를 채택합니다. 

 

근본적인 일관성 문제의 원인:

• 캐시 데이터와 영속성 저장소 사이의 일관성 문제는 주로 데이터 복제 지연 때문에 발생합니다. 만약 복제 지연이 없다면 캐시 무효화를 통해 일관성을 유지할 수 있습니다. 하지만 복제 지연이 발생하는 상황에서 슬레이브 데이터베이스에서 오래된 데이터를 검색할 경우, 캐시 무효화 이후에도 캐시에 오래된 데이터가 설정될 위험이 있습니다.
• Stale Set 문제: Race Condition 으로 인한 오래된 데이터가 캐시에 덮는 현상.  

 

Facebook 에서의 일관성 보장 전략:

• 결론부터 말하자면 복제 지연이 생겼다고 판단되는 경우에 데이터 조회를 Slave 에서 하지 않고 Master 에서 할 수 있도록 라우팅 전략을 수립하는 것입니다.
• Stale Set 문제를 해결하는 방법은 캐시 데이터에 동시적으로 업데이트 할 때 순서를 보장하는 매커니즘을 주는 것.  

 

Stale Set 문제를 해결하는 Lease 매커니즘:

• 임대 토큰 발행:
  • 클라이언트가 캐시 미스를 경험할 때, Memcached 인스턴스는 64비트 임대 토큰을 클라이언트에게 부여함. 이 토큰은 클라이언트가 처음 요청한 특정 키에 바인딩된다. 
• 임대 토큰 제출 및 검증: 
  • 클라이언트가 키를 업데이트할 때 임대 토큰을 함께 제출해야한다. 캐시 시스템은 이 토큰을 검증하여, 현재 해당 키에 대한 쓰기 작업을 수행할 수 있는 권한이 있는지 확인하는 것. 검증이 통과한 클라이언트만 캐시에 데이터를 쓸 수 있다. 
• 대기 알림:  
  • 토큰이 발급된 후 10초 이내에 특정 키의 값을 요청하는 경우, 클라이언트는 잠시 기다리라는 특별한 알림을 받는다. 이를 통해 다른 클라이언트가 동시에 같은 키에 대해 데이터를 설정하는 것을 방지할 수 있다. 
  • 이런 매커니즘을 통해서 캐시를 사용할 떄 발생하는 문제인 Thundering Herd 를 해결할 수 도 있다. 

 

일관성을 보장하는 매커니즘:

• 1) 원격 마커 설정: 데이터 업데이트를 원하는 웹 서버는 먼저 해당 리전에 대한 원격 마커 rk 를 설정합니다. 이 마커는 Slave 데이터베이스의 데이터가 오래된 것 일 수 있음을 나타냅니다.
• 2) Master 데이터베이스에 쓰기: 서버는 마스터 데이터베이스에 쓰기를 수행하면서, 해당 쓰기 작업이 무효화되어야 할 키 k 와 원격 마커 rk 를 SQL 문에 포함시킵니다. 이는 마스터에서의 변경 사항이 복제될 때까지 rk 를 유지하게 만들어, 복제가 완료된 후에만 rk를 무효화하도록 만드는 과정입니다. 
• 3) 로컬 클러스터에서의 키 삭제: 서버는 로컬 클러스터에서 키 k를 삭제합니다. 이렇게 하면 후속 요청이 발생했을 때, 로컬 캐시에서 k 를 찾을 수 없게 되고, 웹 서버는 rk 의 존재 여부를 확인합니다. 
• 4) 쿼리 리디렉션:  웹 서버는 rk의 존재 여부를 확인하고, rk가 존재한다면 쿼리를 마스터 리전으로, 그렇지 않다면 로컬 리전으로 리디렉션합니다.

 

rk 를 삭제하는 타이밍은?

• 복제 작업이 완료될 때, 이전에 본 배치 프로세스에서 데이터베이스 로그를 보고 삭제해야 할 rk 를 판단해서, 캐시 무효화 요청을 전달하는 작업을 통해 삭제됩니다.

 

이 방법의 한계점:

• rk 는 동시성 상황에서 Race Condition 으로 인해 여전히 존재할 수 있습니다. 그러나 Facebook은 이러한 상황이 매우 드물기 때문에 문제로 보지는 않습니다.
• 복제 지연 상황에서는 마스터 데이터베이스로의 질의가 증가하는 것을 피할 수 없습니다.

 

운영 고려사항:

• 복제를 위해 리전 간 통신은 비용이 많이 들고 네트워크 지연(latency)을 증가시키므로, 데이터베이스 복제와 삭제 스트림을 위한 전용 통신 채널을 구축하여 네트워크 효율성을 향상시킵니다.
• Memcached가 응답하지 않을 때를 대비해야합니다. Facebook 은 캐시 무효화 요청을 버퍼링할 수 있도록 만들고, Memcached 가 다시 작동하게 되면 캐시 무효화 요청을 재생할 수 있도록 구축했습니다.

 

 

https://www.usenix.org/system/files/conference/nsdi13/nsdi13-final170_update.pdf