Facebook 이 캐시 성능을 올리는 방법

 

크게 두 가지 개선이 있음:

• 캐시 데이터를 가져올 때 Latency 줄이기
• 캐시 미스로 인한 부하를 줄이기

 

Reducing Latency

Network Incast Congestion 문제:

• 하나의 서버가 많은 캐시 서버로부터 데이터를 가지고 오니까 Incast Congestion 문제가 발생함. 이걸로 인한 패킷 손실, 지연시간 증가 같은 문제가 발생할 수 있음.

 

Parallel requests and batching 적용:

• 병렬 요청 및 배치 처리:
  • 웹 애플리케이션 코드를 구조화하여 페이지 요청에 응답하기 위해 필요한 네트워크 라운드 트립의 수를 최소화. 이는 네트워크 대기 시간을 줄이고, 애플리케이션의 응답성을 향상시킴.
• 방향성 비순환 그래프(DAG)의 구성:
  • 데이터 간의 의존성을 나타내는 DAG를 구성함으로써, 데이터 요청과 처리의 순서를 최적화한다. 이 그래프는 어떤 데이터 요소가 다른 요소들에 의존하는지, 그리고 어떤 요소들이 독립적으로 처리될 수 있는지를 명확하게 해서 이걸 바탕으로 요청을 단계별로 보낸다.
• 동시성의 최대화:
  • 웹 서버는 이 DAG를 사용하여 가능한 많은 항목들을 동시에 가져옴. 이를 통해 서로 의존성이 없는 여러 데이터 요소는 병렬로 요청되어 더 빠른 데이터 처리와 페이지 로딩 시간을 달성할 수 있음.
• 배치 처리의 예시:
  • 평균적으로 이러한 배치 요청은 요청 당 24개의 키를 포함함. 이는 단일 요청에서 여러 데이터 항목을 함께 요청함으로써 네트워크 요청의 수를 줄이고, 전체적인 성능을 향상시키는 데 도움이 됨.

 

mcrouter 프록시 구축:

• TCP 연결의 메모리 요구사항:
  • TCP 연결은 상태를 유지하는 연결이므로 메모리 사용량이 높음. 웹 스레드와 Memcached 서버 간에 개별적인 TCP 연결을 유지하는 것은 메모리 비용이 매우 높기 때문에 중간 라우팅 계층인 mcrouter 을 구축함.
• 연결 통합(coalescing)을 통한 효율성 향상:
  • mcrouter와 같은 프록시를 사용하여 여러 TCP 연결을 통합함으로써, 네트워크, CPU, 그리고 메모리 자원 사용을 줄일 수 있음. 이러한 연결 통합은 TCP 연결을 통한 고처리량 통신의 효율성을 개선함.

 

UDP 통신 선택:

• 데이터를 가져오는 요청에는 UDP 프로토콜을 선택 (데이터를 삭제하거나, 갱신하는 작업은 신뢰성이 있는 TCP 를 선택함.)
• UDP 통신의 선택 이유:
  • UDP는 연결이 없는 프로토콜이기 때문에, 웹 서버의 각 스레드가 mcrouter를 거치지 않고도 Memcached 서버와 직접 통신할 수 있고, 이는 연결을 설정하고 유지하는 데 드는 오버헤드를 줄여줌.
• UDP 통신 활용:
  • UDP 통신 구현에서도 패킷이 드랍되거나 순서가 바뀌는 것은 감지할 수 있다. (신뢰성없는 통신이지만, 결과가 안왔거나 이상할 떄는 요청을 버림으로써도 처리할 수 있음.),
  • 이렇게 패킷이 잘못 왔을 때는 캐시 미스로 간주하고 추가로 데이터베이스에 조회를 하지는 않음. 그러면 부하가 많이 걸리니까.

 

Incast Congestion 을 해결하기 위한 슬라이딩 윈도우 (Sliding Window) 매커니즘 도입:

• UDP 레벨에서 구현 매커니즘임. 
• 슬라이딩 윈도우 메커니즘:
  • Memcache 클라이언트는 보류 중인(outstanding) 요청의 수를 제어하기 위해 슬라이딩 윈도우 메커니즘을 사용함. 이는 클라이언트가 응답을 받아야만 다음 요청을 보낼 수 있음. TCP의 혼잡 제어 메커니즘과 유사하게, 성공적인 요청 후에는 윈도우 크기가 천천히 증가하고, 요청에 응답이 없을 때는 줄어드는 방식임.
• 슬라이딩 윈도우의 적용 범위:
  • 이 윈도우는 모든 Memcache 요청에 대해 독립적으로 적용되며, 목적지와 관계없이 작동함. 이는 TCP 윈도우가 단일 스트림에만 적용되는 것과 대비됨.
• 최적의 슬라이딩 윈도우 사이즈 선택:
  • 낮은 윈도우 크기:
    • 윈도우 크기가 작을 때, 애플리케이션은 Memcache 요청을 순차적으로 더 많이 분배함. 이는 웹 요청의 처리 시간을 증가시킴. 낮은 윈도우 크기는 네트워크 혼잡을 줄이지만, 요청 처리 시간을 늘림.
  • 큰 윈도우 크기:
    • 윈도우 크기가 너무 커지면, 동시에 발생하는 Memcache 요청의 수로 인해 인캐스트 혼잡이 발생할 수 있음. 이는 Memcache 오류로 이어지며, 애플리케이션은 데이터를 위해 데이터베이스로 조회할 수 있음. 이는 결국 웹 요청의 처리를 느리게 만듬.

 

 

Reducing Load

웹 서버는 원하는 데이터가 캐시에 없을 때 이러한 비싼 경로로 되돌아가는데 Memcached 는 데이터베이스 쿼리와 같은 더 비싼 경로를 통해 데이터를 가져오는 빈도를 줄이기 위해 사용함.

 

여기서는 부하를 감소시키기 위한 세 가지 기술에 대해 설명함.

 

 

Leases 매커니즘 도입:

• Memcache 사용과 관련하여 발생할 수 있는 두 가지 문제인 "오래된 값 설정(stale sets)"과 "썬더링 허드(thundering herds)"를 해결하기 위해 "임대(leases)"라는 새로운 메커니즘을 도입함.
• 낡은 값 설정(Stale Sets):
  • 문제 설명:
    • 웹 서버가 Memcache에 값을 설정할 때, 그 값이 반드시 캐싱되어야 할 최신 값을 반영하지 않는 경우가 있음. 이는 Memcache에 대한 동시 업데이트 요청이 재정렬될 때 발생할 수 있음.
  • 문제 영향:
    • 이로 인해 캐시된 데이터의 정확성과 신뢰성이 떨어지며, 사용자에게 오래된 정보를 제공할 수 있다.
• 썬더링 허드(Thundering Herds):
  • 문제 설명:
    • 특정 키가 매우 높은 읽기 및 쓰기 활동을 겪을 때 발생한다. 쓰기 활동이 반복적으로 최근에 설정된 값을 무효화하면서, 많은 읽기 요청이 더 비싼 경로(예: 데이터베이스 조회)로 가면서 부하를 유발한다.
  • 문제 영향:
    • 이는 서버에 과부하를 일으키고, 데이터 접근 시간을 증가시키며, 전반적인 시스템 성능에 부정적인 영향을 미칠 수 있다.
• 임대 메커니즘의 주요 특징:
  • 임대 토큰:
    • 클라이언트가 캐시 미스를 경험할 때, Memcached 인스턴스는 64비트 임대 토큰을 클라이언트에게 부여한다. 이 토큰은 클라이언트가 처음 요청한 특정 키에 바인딩된다.
  • 토큰 사용:
    • 클라이언트는 캐시에 값을 설정할 때 이 임대 토큰을 제공한다. 임대 토큰을 사용함으로써, Memcached는 동시에 발생하는 쓰기 작업들을 조정할 수 있으며, 데이터가 저장되어야 하는지 여부를 검증하고 결정할 수 있다.
  • 검증 실패:
    • 만약 Memcached가 해당 항목에 대한 삭제 요청을 받고 임대 토큰을 무효화한 경우, 검증은 실패할 수 있다. 이는 동시에 여러 클라이언트가 같은 키에 대해 쓰기 작업을 시도할 때 데이터 일관성을 유지하기 위한 메커니즘이다.
  • 오래된 값 설정 방지:
    • 임대 메커니즘은 로드-링크/스토어-컨디셔널(load-link/store-conditional) 작동 방식과 유사하게 낡은 값 설정 문제를 방지한다. 이는 키에 대한 동시 업데이트가 발생했을 때 최신 값만이 캐시에 저장되도록 보장하여, 캐시된 데이터의 신뢰성을 높인다.

• 임대 토큰의 무효화 및 만료:
  • 무효화:
    • 쓰기 작업이 성공적으로 완료되면, 해당 임대 토큰은 무효화된다. 이는 다른 클라이언트가 같은 키에 대해 더 이상 쓰기 요청을 할 수 없게 만듬.
  • 만료:
    • 임대 토큰에는 일정 시간 후에 자동으로 만료되는 로직이 포함될 수 있다. 이는 오래된 임대 토큰이 시스템 내에 계속 남아있는 것을 방지한다.

 

Lease 매커니즘으로 Thundering herds 문제 해결:

• Thundering herds 는 특정 키에 대한 동시 요청이 폭증하는 상황을 말하며, 이는 캐시 미스 후 데이터를 다시 캐시에 저장하기 전까지 모든 요청이 데이터베이스와 같은 더 느리고 비용이 많이 드는 경로로 전환되면서 발생할 수 있다.
• 썬더링 허드 완화를 위한 임대 메커니즘의 수정:
  • 토큰 발급률 조절:
    • Memcached 서버는 발급하는 토큰의 비율을 조절한다. 기본 설정으로, 서버는 각 키에 대해 10초마다 한 번만 토큰을 반환하도록 구성된다.
  • 대기 알림:
    • 토큰이 발급된 후 10초 이내에 특정 키의 값을 요청하는 경우, 클라이언트는 잠시 기다리라는 특별한 알림을 받는다. 이는 다른 클라이언트가 동시에 같은 키에 대해 데이터를 설정하는 것을 방지하기 위해서이다.
  • 데이터 설정 및 캐시 접근:
    • 일반적으로, 임대 토큰을 가진 클라이언트는 몇 밀리초 내에 데이터를 성공적으로 설정할 것이다. 따라서, 대기 중인 클라이언트가 요청을 재시도할 때, 데이터는 종종 캐시에 이미 존재하게 된다.

• 네트워크 및 서버 부하를 감소:
  • 이 방법은 특정 키에 대한 동시 요청 수를 제한함으로써 네트워크와 서버에 가해지는 부하를 줄일 수 있다. 이는 특히 대규모 시스템에서 성능과 안정성을 유지하는 데 중요하다.
• 클라이언트에서 임의로 기다리라고 하는 건, 그 시간동안 다른 요청을 처리 못할수도 있는거 아님?
  • 해당 요청이 일시적으로 대기 상태에 들어가게 하며, 이는 클라이언트가 그 시간 동안 다른 요청을 처리하지 못할 가능성을 내포한다. 특히 비동기 처리 모델을 사용하지 않는 경우, 이 대기 시간은 클라이언트의 처리 능력에 영향을 줄 수 있다.

 

오래된(Stale) 데이터 활용:

• 이는 캐시 미스 상황에서, 특히 원하는 데이터가 최근에 삭제되었거나 업데이트로 인해 현재 캐시에 없을 때 적용되는 방법이다. 이 때, Memcached 서버는 요청한 키에 대해 임대 토큰과 함께 최근 삭제된 항목을 보관하는 곳에서 가져온 "Stale" 데이터를 클라이언트에 반환한다. 만약 어플리케이션이 이런 오래된 데이터로도 처리를 진행할 수 있는 경우에는 데이터베이스에서 최신 값을 가져올 필요가 없다.
• 대기 시간 최소화:
  • 이 접근 방식은 특정 키에 대한 최신 데이터를 기다리는 애플리케이션의 대기 시간을 크게 줄일 수 있다. 특히, 약간의 데이터 지연이 크리티컬하지 않은 읽기 중심의 작업에 유용한 방법이다.
• 성능 향상:
  • 데이터베이스 접근을 줄임으로써 전체 시스템의 부하를 감소시키고, 응답 시간을 개선할 수 있다.

 

 

Memcache Pool 분할 전략:

• Memcached 를 일반적인 목적의 캐싱 레이어로 사용할 때 요구사항은 다를 수 있다. 각 요구사항마다 캐시 풀을 분할해서 사용하면 성능적인 이점을 누릴 수 있다.
• 풀 분할 전략:
  • 기본 풀(wildcard 풀) 지정:
    • 클러스터 내의 Memcached 서버들 중 일부를 'wildcard'라 명명된 기본 풀로 지정한다. 이 풀은 특별한 요구사항이 없는 키들을 위한 기본적인 저장소 역할을 한다.
  • 문제가 되는 키를 위한 별도 풀 생성:
    • 'wildcard' 풀에서 관리하기에 문제가 있는 키들을 위해 별도의 풀을 설정한다. 이는 특정 애플리케이션의 요구사항에 맞춰 최적화된 캐싱 환경을 제공하기 위함이다.
  • 빈번한 접근 키를 위한 소규모 풀:
    • 자주 접근되지만 캐시 미스가 발생해도 비용이 크지 않은 키들을 위해 소규모의 풀을 할당한다. 이는 자주 사용되는 데이터의 적중률을 최대화하기 위해 필요한 최소한의 리소스를 제공한다.
  • 드문 접근 키를 위한 대규모 풀:
    • 드물게 접근되지만 캐시 미스가 발생할 경우 비용이 매우 큰 키들을 위해 대규모의 풀을 할당한다. 이러한 키들은 메모리 공간을 더 많이 필요로 할 수 있으며, 캐시 미스를 최소화하기 위해 충분한 저장 공간을 확보하는 것이 중요하다.
  • 이 방법은 가치 있는 낮은 접근 변동 키가 더 이상 접근되지 않는 높은 변동 키보다 먼저 제거되는 현상을 막기 위해서 사용한다. 즉 이러한 키들을 다른 풀에 배치함으로써 키가 삭제됨을 방지하는 것이다. (둘을 같은 풀에 넣으면 캐시 알고리즘에 따라서 한쪽 위주로 삭제될거라서)

 

Memcached 에 복제 적용:

• Memcached 서버의 지연 시간과 효율성을 향상시키기 위해 복제(replication) 를 사용한다.
• 복제를 적용할 때:
  • 애플리케이션이 동시에 많은 키를 자주 가져오는 경우:
    • 이는 동시 요청을 효율적으로 처리하기 위해 데이터의 복사본을 여러 서버에 분산시킬 수 있으니까.
  • 전체 데이터 세트가 하나 또는 두 개의 Memcached 서버에 맞는 경우:
    • 데이터 세트의 크기가 제한적이라면, 전체 데이터를 여러 서버에 복제함으로써 높은 가용성과 빠른 응답 속도를 보장할 수 있다.
  • 요청 비율이 단일 서버가 관리할 수 있는 것보다 훨씬 높은 경우:
    • 이는 고부하 상황에서 단일 서버의 처리 능력을 초과하지 않도록, 부하를 분산시키기 위해 복제가 필요할 수 있다.

 

Memcached 가 키를 나누는 방법보다 복제가 더 적절한 선택인 이유:

• 이는 한개의 키를 처리하는 것과 여러 키를 처리하는게 성능적으로 차이가 나지 않기 때문에 키를 분산해서 처리하는 방식으로 설계하는 것보다, 복제를 더 늘리는 식으로 처리한다.
• Memcached는 여러 키에 대한 데이터를 한 번의 네트워크 요청으로 검색할 수 있는 멀티-겟(multi-get) 기능을 지원하기 떄문.

 

클라이언트 요청이 복제 서버로 라우팅 하는 방법:

• 클라이언트의 복제 선택:
  • 각 클라이언트는 자신의 IP 주소를 기반으로 복제본을 선택한다.
• 구체적으로는 일관된 해싱(Consistent Hashing) 매커니즘이 있다:
  • 클라이언트와 서버를 해싱 링에 배치하고, 클라이언트의 해시값에 가장 가까운 서버를 선택하는 방식임. 이 방법은 서버의 추가나 제거가 있을 때도 해싱 링의 대부분을 유지하며, 부하 분산에 있어서 높은 일관성을 제공한다.