논문 - Scaling Memcached at Facebook: A look at the complexities of Caching

논문 읽기 스터디를 하고 있는데, 이번엔 나의 발표차례여서 해당 논문을 정리한 내용을 공유하려고 한다. 논문 이외에 조사한 내용도 포함되어 있으니 혹시 잘못된 정보가 존재한다면 피드백은 언제나 환영!!

등장 배경 - facebook의 상황

Facebook은 매일 수억 명의 사용자로부터 발생하는 막대한 읽기/쓰기 요청을 처리해야 한다. 이를 위해 대규모 데이터를 빠르게 처리하고 실시간으로 사용자 경험을 제공하는 것이 필수적이다. 기존의 데이터베이스 시스템만으로는 이러한 규모를 감당하기 어렵기 때문에, Memcached를 기반으로 한 분산 캐싱 시스템을 구축했다.

• 초당 수십억 요청을 처리해야 하는 대규모 소셜 네트워크 인프라.
• 데이터베이스 부하 증가로 인해 응답 시간 지연 발생.
• 전 세계 사용자에게 실시간 데이터 제공 필요.

memcache

메모리 내 데이터를 빠르게 저장하고 읽는데 사용되는 해시 테이블 기반 시스템

facebook에서 memcache란?

• 인메모리 캐싱 솔루션 → 읽기/쓰기 요청 경감 및 데어터 접근 속도 향상
• 분산 키-값 저장소

facebook에서의 memcache 아키텍처

Facebook은 Memcached를 단순히 한 대의 서버에서 사용하는 것이 아니라, 여러 서버로 확장하여 클러스터화했다. 데이터는 일관된 해싱 기법을 통해 여러 Memcached 서버에 분산 저장되며, 클라이언트는 Memcached를 먼저 조회한 후 캐시 미스일 경우 데이터베이스에서 데이터를 가져오도록 설계되었다.

• 기본 구조
  1) master- slave 구조
  
  2) 일관된 해싱을 통해 키 분산
  3) 모든 웹서버는 짧은 시간 내에 모든 memcache 서버와 통신
  (all to all 통신 패턴→ 병목 현상, incast congestion의 원인)

• 읽기 및 쓰기 경로
  • 읽기: Memcache 조회 → 캐시 미스 시 데이터베이스 접근.
  • 쓰기: 데이터베이스 업데이트 후 Memcache 캐시 삭제(무효화).

주요 기술 및 최적화

📌 병렬 요청 및 일괄 처리

Facebook의 Memcache 클라이언트가 네트워크 효율성을 극대화하고 요청 지연 시간을 최소화하기 위해 구현한 전략

1. 병렬 요청

   문제

   • Facebook의 한 사용자 요청(예: 피드 로드)은 Memcache에서 수백 개의 키를 요청하는 작업으로 이루어질 수 있다. (한 요청 = 여러 memcache 조회)
   • 이러한 요청을 하나씩 순차적으로 처리하면 네트워크 왕복(Round-Trip Time, RTT)이 증가하여 응답 시간이 길어진다.

   해결 방법

   • 요청 간의 의존 관계를 분석하여 병렬로 처리 가능한 요청을 동시에 실행.
   • 의존 관계를 DAG(Directed Acyclic Graph, 방향 비순환 그래프)로 나타내어 요청을 설계:
     • 예: 요청 A가 요청 B에 의존하지 않는다면 두 요청을 병렬로 실행 가능.
     • 요청 B가 요청 A의 결과를 필요로 한다면, A를 완료한 후에 B를 실행.
     • DAG 구조
       • DAG(Directed Acyclic Graph) : 방향성 비순환 그래프
       • 데이터 또는 작업의 의존 관계를 나타내는 데 사용
       • Facebook의 Memcache 클라이언트가 요청을 병렬 처리하는 데 중요한 역할

💡 예시

• Facebook 뉴스피드 로드 시:
  1) 게시물 데이터를 가져오기 위한 요청(A).
  2) 각 게시물의 댓글 데이터를 가져오는 요청(B, C, D).
  3) 댓글 좋아요 수 데이터를 가져오는 요청(E, F).
  이처럼 요청 간 의존 관계가 있을 경우, 순차적으로 처리하면 성능이 저하
  

• DAG 구조의 적용 : 의존 관계를 DAG로 표현하여 병렬로 실행 가능한 요청을 구분
  - A → (B, C, D) → (E, F).
  - 요청 A가 완료된 후, 요청 B, C, D를 병렬로 실행.
  - B, C, D가 완료되면, 요청 E와 F를 병렬로 실행.

• 결과
  - 요청의 네트워크 왕복 횟수를 최소화하여 응답 시간을 단축.
  - 많은 사용자 요청을 빠르게 처리할 수 있는 병렬 처리가 가능해짐.

2. 요청 일괄 처리

   문제:

   • Memcache는 단일 요청마다 네트워크 비용이 발생하므로, 많은 키를 개별 요청으로 보낼 경우 네트워크와 서버 부하가 증가한다

   해결 방법:

   • 여러 키를 한 번의 요청으로 묶어서 일괄 처리(Batch) 형태로 서버에 전송.
     • 예: 24개의 키를 요청해야 할 경우, 24번의 개별 요청 대신 한 번의 요청으로 묶어서 처리.
   • 클라이언트는 병렬로 묶인 요청 배치를 Memcache 서버에 보냄으로써 네트워크 부하를 줄임.

   결과:

   • 평균적으로 한 번의 요청에 24개의 키를 포함.
   • 서버와 클라이언트 간 네트워크 왕복(RTT)이 감소.
   • 네트워크 패킷 수를 줄여 네트워크 대역폭을 절약.

💡 사례 예시
사용자가 Facebook 뉴스피드 로드 요청 시
1. 병렬 처리:
- 뉴스피드의 각 게시물, 댓글, 좋아요 데이터를 독립적으로 병렬 요청.
2. 일괄 처리:
- 게시물 100개에 대한 데이터를 한 번의 요청으로 Memcache에서 가져옴.

📌 클라이언트-서버 통신의 최적화 방식

배경

• Facebook의 Memcache 시스템에서 웹 서버(클라이언트)는 Memcache 서버에 자주 요청을 보낸다.
• 이때 클라이언트와 서버 간의 통신은 효율적이어야 하고, 지연 시간을 최소화해야 한다.
• 초기 설계에서는 서버 간 통신이 필요하지 않았지만, 클라이언트와 서버 간의 통신에서 최적화가 필요했기 때문에 다양한 방법이 도입됨

방식

• Memcache는 서버 간의 직접적인 통신을 하지 않는다
  • Memcache 서버들은 서로 상호작용하지 않고, 각 클라이언트(웹 서버)가 여러 Memcache 서버에 직접 접근
  • 모든 복잡한 로직(예: 요청 라우팅, 오류 처리 등)은 클라이언트(웹 서버)에서 처리
• 상태 없는(stateless) 시스템
• 클라이언트(웹 서버)는 요청을 여러 Memcache 서버로 보낼 때, 여러 작업을 동시에 할 수 있도록 복잡한 로직을 처리
• UDP와 TCP를 사용하여 통신 → 네트워크 대역폭 최적화
  • UDP : 읽기 요청 - 연결을 설정하지 않고 빠르게 데이터를 전송할 수 있기 때문에
  • TCP : 쓰기 요청 - 데이터 일관성을 보장해야 하기 때문에 신뢰성 있는 전송이 필요
• incast congestion을 방지하기 위한 흐름 제어(flow control)가 적용
  • incast congestion : 여러 클라이언트가 동시에 많은 요청을 서버에 보내면서 네트워크가 과부하되는 현상
  • 슬라이딩 윈도우 방식을 사용하여 동시에 보낼 수 있는 요청 수를 제한

📌 부하 감소를 위한 방법

Memcache 시스템을 사용하여 서버의 부하를 어떻게 줄일까?

Memcache 시스템은 읽기 요청이 매우 많고, 캐시 미스(캐시에서 찾지 못한 데이터를 데이터베이스에서 다시 가져오는 작업)가 발생할 때마다 데이터베이스 부하가 증가

1. Leases (리스)

   stale sets와 Thundering herds를 해결하기 위한 메커니즘

   • stale sets: 캐시된 값이 최신 상태가 아니어서 데이터가 불일치할 때 발생하는 문제.
   • Thundering herds: 특정 키가 자주 읽고 쓰여서 여러 클라이언트가 동시에 캐시를 갱신하려고 시도하는 상황에서 발생하는 문제.
   • Leases 메커니즘:
     • Memcache 인스턴스는 클라이언트에게 Leases 토큰(64비트 값)을 부여.
       • 클라이언트가 캐시 누락을 경험할 때 데이터를 캐시에 다시 설정하기 위함
       • 토큰 : 클라이언트가 원래 요청한 특정 키에 바인딩된 값
     • 리스가 유효할 때만 클라이언트가 Memcache에 데이터를 다시 쓸 수 있다.
     • 리스를 통해 동시 데이터 업데이트로 인한 불일치를 방지하고, 여러 클라이언트가 같은 데이터를 동시에 수정하는 문제를 해결
   • 결과:
     • 캐시 세트가 발생하는 것을 방지하여 데이터 일관성 유지.
     • 스램 문제를 해결해 데이터베이스 부하를 감소시킴.

💡 예시
Facebook에서 사용자가 피드를 로드할 때, 각 게시물의 좋아요 수를 Memcache에서 캐시하고 있다. 여러 사용자가 동일한 게시물을 동시에 좋아요를 눌렀다면, 좋아요 수를 업데이트하려는 여러 요청이 동시에 들어오게 될 수 있다.

• 리스가 없는 경우 (문제 발생):

1. 사용자 A와 사용자 B가 동시에 같은 게시물에 대해 좋아요를 누른다.
2. 두 사용자가 Memcache에서 캐시된 좋아요 수를 조회하고, 캐시 미스가 발생하여 데이터베이스에서 값을 가져온다.
3. 데이터베이스에서 가져온 값은 기존 값이고, 두 사용자가 동시에 좋아요 수를 증가시킨다.
4. 두 사용자가 각각 Memcache에 업데이트를 하게 되면, 최신 상태의 데이터가 아니므로 일관성이 깨지게 된다.

• 리스 적용 후 (문제 해결)

1. 사용자 A가 첫 번째로 Memcache에서 캐시된 좋아요 수를 조회.
2. Memcache는 좋아요 수를 새로 갱신할 수 있는 리스 토큰을 사용자 A에게 할당.
3. 사용자 A는 해당 데이터를 갱신하고, 리스 토큰을 이용해 Memcache에 값을 설정.
4. 사용자 B가 동일한 게시물의 좋아요 수를 조회할 때, 이미 리스 토큰이 만료되지 않은 사용자 A에게만 데이터 갱신 권한이 있기 때문에, 사용자 B는 데이터를 다시 가져와 갱신을 시도할 수 없다.
5. 사용자 B는 새로운 리스 토큰을 요청하고, 사용자 A의 갱신 작업이 완료되면 데이터베이스에서 최신 값을 가져와 업데이트.

• 결과
  리스 메커니즘 덕분에 사용자 A만 해당 데이터를 갱신할 수 있으며, 사용자 B는 갱신 권한을 얻기 전까지 기다린다.
  이를 통해 데이터 일관성을 유지하고, 스램 문제를 해결하며, 데이터베이스 부하도 줄인다.

2. Memcache Pools

Memcache 서버는 여러 워크로드(작업 부하)를 처리할 수 있지만, 서로 다른 데이터 접근 패턴과 메모리 사용량을 가진 워크로드가 한 풀 안에서 상호작용하면 성능이 저하될 수 있다.

• 예를 들어, 자주 변경되는 데이터와 드물게 접근되는 데이터가 같은 Memcache 풀에 있으면, 자주 변경되는 데이터로 인해 드물게 접근되는 데이터가 메모리에서 지워질 수 있다.
• Memcache 풀:
  • Memcache 서버를 여러 개의 별도 풀로 나누어 사용
    • wildcard pool: 일반적인 캐시 데이터를 저장. 자주 업데이트되지 않는 데이터
    • app-specific pool: 자주 변하는 데이터를 저장.
    • replicated pool: 읽기 요청이 많은 데이터를 저장.
    • regional pool: 지역적 특성이 있는 데이터를 저장.
• 결과:
  • 서로 다른 데이터를 분리하여 풀에 저장함으로써, 각 데이터 유형에 맞는 최적화된 메모리 관리와 성능 향상을 이끌어낼 수 있다
  • 서로 다른 데이터 유형이 메모리 풀 간섭 없이 저장되므로, 성능이 향상되고 효율적인 메모리 사용이 가능

3. Replication
   특정 키가 자주 요청되는 경우, 여러 Memcache 서버에 복제본을 만들어 데이터 접근 시간을 단축시키는 기법

• 복제된 데이터를 여러 Memcache 서버에 분산 저장하여, 읽기 요청이 한 서버에 몰리는 것을 방지.
• 데이터베이스 요청이 많아지는 시점에 복제를 통해 다중 서버에서 동시에 데이터 제공이 가능

📌 글로벌 확장

Memcache 시스템이 글로벌 사용자에게 안정적이고 빠른 서비스를 제공하였나

1. 지역 기반 설계:

• facebook은 글로벌 사용자에게 빠르고 일관된 응답을 제공하기 위해, Memcache를 지역별로 분산하여 배치
• 지역 단위로 캐시 데이터를 관리하고, 서버 간의 데이터 전파 시간을 줄여 응답 시간을 최적화
• 각 지역별 클러스터:
  • Facebook은 지역별 클러스터를 구성하여, 서버들이 같은 지역 내에서만 통신하도록 설계.
  • 예를 들어, 북미, 유럽, 아시아 등 각 대륙별로 독립적인 Memcache 클러스터를 운영.
  • 각 지역에 서버를 배치하여, 사용자 요청이 발생할 때 가장 가까운 서버에서 데이터를 처리하도록 하여 응답 시간을 최소화.
• 글로벌 서버 분산:
  • 데이터는 여러 서버에 복제되어 저장. 각 지역에 복제된 데이터를 두어, 한 지역에서 장애가 발생하더라도 다른 지역에서 백업 데이터를 빠르게 사용할 수 있게 된다.

2. 클러스터 분할 (Sharding) : 효율적인 확장
   샤딩은 Memcache 서버를 여러 개의 작은 서브 클러스터로 나누는 방식으로, 각 클러스터가 데이터의 일부분만 담당하도록 한다.

3. 데이터 일관성 (Data Consistency) : 다양한 지역에 배포된 서버들이 동일한 데이터를 제공.

• 캐시 일관성 유지
  • Facebook은 일관성 있는 데이터를 보장하기 위해 원격 캐시 및 데이터 동기화 전략을 사용.
    • 각 서버가 다른 지역에 있는 서버들과 주기적으로 데이터를 동기화하여, 최신 데이터를 여러 지역에서 동일하게 제공.
    • 데이터베이스에서 변경된 사항은 캐시에서 무효화된 후, 새로 갱신된 데이터를 다시 캐시로 가져오는 방식으로 일관성을 유지.
• 데이터 전파 및 복제
  • 데이터베이스의 변경 사항은 복제된 Memcache 서버에 자동으로 전파.
  • 동기 복제 또는 비동기 복제 방식을 사용하여 각 지역 서버에 실시간 데이터 동기화를 구현.

📌 단일 서버 개선 사항

• 멀티스레드 구현
• Adaptive Slab Allocator 적용
  Memcache 서버에서 메모리를 고정 크기 블록으로 할당할 경우, 메모리 낭비가 발생할 수 있음. 특히 작은 크기의 데이터나 자주 변하는 데이터에 대해서는 비효율적인 메모리 사용이 문제이다.
  • 메모리 할당을 동적으로 최적화
  • 작은 데이터는 작은 크기의 슬랩을 사용하고, 큰 데이터는 더 큰 슬랩을 할당하여 메모리 사용 효율을 높임
• LRU(Least Recently Used) 캐시 정책 개선
  Memcache는 기본적으로 LRU(Least Recently Used) 정책을 사용하여 오래된 데이터를 삭제하고 새로운 데이터를 저장하는 방식으로 동작 → 데이터 삭제가 발생할 때 불필요한 연산이 발생
  LRU 알고리즘을 개선하여 캐시의 유효성을 최적화하고, 불필요한 삭제를 최소화
  
• 비동기 요청 처리 도입
• 네트워크 지연 시간 감소
• 메모리 효율성 향상

그래서 Redis랑 어떤차이가 있는 건데? 🤔

데이터 구조

• Redis: 다양한 데이터 구조를 지원.
  - 문자열 (String)
  - 리스트 (List)
  - 집합 (Set)
  - 정렬된 집합 (Sorted Set)
  - 해시 (Hash)
  - 비트맵, 하이퍼로그로그 등 고급 자료 구조
  -> 이를 통해 복잡한 데이터 연산을 인메모리에서 처리할 수 있다.

• Memcached:
  단순히 key-value 쌍의 데이터를 문자열 또는 바이너리 형태로 저장.
  -> 구조가 간단하여 캐싱 이외의 복잡한 작업에는 부적합.

영속성 (Persistence)

• Redis:데이터 영속성을 지원.
  - RDB (주기적으로 데이터 덤프)
  - AOF (명령 로그 기록)
  -> 캐시로뿐만 아니라 데이터베이스로도 활용 가능.

• Memcached:영속성을 지원하지 않는다.
  -> 메모리가 날아가면 데이터도 손실.

클러스터링 (Clustering)

• Redis:Redis 클러스터를 통해 샤딩과 복제를 지원.
  -> 확장성이 높으며, 고가용성을 위한 설정이 가능합니다.

• Memcached:
  클러스터링을 자체적으로 지원하지 않는다.
  -> 클라이언트 라이브러리를 사용해 샤딩 구현.

성능

• Redis:
  다양한 데이터 구조와 기능으로 인해 특정 상황에서 오버헤드가 발생할 수 있습니다.
  하지만 대부분의 경우 성능은 매우 뛰어나다.

• Memcached:
  단순한 구조 덕분에 읽기/쓰기 성능이 매우 빠르다.
  -> 단순 캐싱 용도라면 Redis보다 약간 더 나은 성능을 보일 수 있다.

사례

• Redis: 세션 관리, 실시간 분석 (e.g., 순위, 카운터), 메시지 큐, Pub/Sub 시스템, 복잡한 데이터 구조 캐싱
• Memcached:단순 데이터 캐싱, 웹 페이지 렌더링 속도 개선,자주 변경되지 않는 데이터 저장

메모리 관리

• Redis:
  - LRU(Least Recently Used) 정책으로 메모리 관리.
  - 사용자가 메모리 사용량을 세부적으로 제어 가능.

• Memcached:
  메모리 블록 단위로 데이터를 저장하며, 메모리 초과 시 오래된 데이터를 자동 삭제.

정리하자면,
Redis는 다양한 데이터 구조와 영속성을 지원하며, 데이터베이스나 메시지 브로커 등으로도 활용 가능. 복잡한 작업에 적합하다.
Memcached는 단순한 데이터 캐싱에 특화되어 있으며, 빠르고 가볍다

논문 링크 : https://www.usenix.org/system/files/conference/nsdi13/nsdi13-final170_update.pdf