https://medium.com/@shagun/scaling-memcache-at-facebook-1ba77d71c082
이번 주에 Scaling Memcache at Facebook 논문을 읽었다. 논문은 페이스북이 멤캐시(당시에는 간단한 메모리 캐시)위에서 고성능, 분산 키-값 저장 장치를 만들고 세계에서 가장 큰 소셜 네트워크를 지원하게 확장한 이야기를 담는다.
페이스북의 관점에서 사용자는 만드는 거보다 많은 컨텐트를 소비한다. 그러므로 작업 부하는 읽기에 편중되고 캐싱은 작업 부하를 줄이는 데 도움이 된다. 거기에 더해 다른 장점이 있다. 페이스북은 멤캐시 클러스터를 사용하는데 각 멤캐시 인스턴스는 필요한 경우 값을 채우는, look-aside 캐시이다. 이 말은 클라이언트가 데이터를 멤캐시에 요청하고 데이터가 사용가능하지 않으면, 클라이언트는 데이터를 데이터베이스에서 가져오고 추후 요청을 위해 캐시에 채운다는 의미이다. 멤캐시는 loading 캐시가 아니므로, 데이터베이스에서 데이터를 가져오는 로직을 걱정할 필요가 없고 여러가지 데이터베이스와 연결하기 쉽다. 쓰기 요청의 경우, 클라이언트는 갱신 명령을 데이터베이스에 보내고 삭제 명령을 멤캐시에 보낸다. 삭제는 멱등idempotent이므로 갱신보다 선호한다. 전체 개요는 매우 간단하지만, 실제 구현에서는 더 많은 세부사항이 필요하다. 페이스북은 3가지 배포 규모 — 여러 서버들의 단일 클러스터, 서로 다른 클러스터간의 데이터 복제, 전 세계에 걸친 클러스터 배포, 를 고려하고 최적화했다.
A single cluster of servers
이 경우는 요청이 널리 산개되어 매우 높은 읽기에 집중된 작업 부하로 특징지을 수 있다. 약 44%의 요청이 20대가 넘는 멤캐시 서버에 이어진다. 인기있는 페이지는 이 값이 서로 다른 100개의 서버에 걸치기도 한다. 이렇게 되는 한 가지 이유는 각 요청이 매우 작은 양의 데이터를 돌려받기 때문이다. get 요청의 경우, UDP가 TCP보다 성능이 좋고 get 오류는 입력을 실행하지 않더라도 캐시 미스로 다룬다. 이런 설계를 선택한 건 단순히 실용적으로 보인다. 요청의 25%가 패킷이 늦거나, 유실되거나, 순서가 잘못되어 발생한다. 비록 응답 크기가 매우 작지만, 다양한 경우를 고려하면 평균은 954 바이트, 중간값은 135 바이트로 꽤 크다. (신뢰성의 이유로) 설정과 삭제 동작은 여전히 TCP에서 동작하지만 효율을 향상시키기 위해 연결과 같이 이뤄진다.
클러스터 내에서, 데이터는 consistent hashing을 통해 수백개의 서버에 분산한다. 대규모 전개와 연결된 매우 높은 요청 비율은 모든 멤캐시 서버간의 연결로 이어지고 하나의 서버가 많은 요청의 병목지점이 될 수도 있다. 클라이언트는 데이터간의 의존 관계를 나타내는 DAG를 만들어 보다 독립적인 요청은 동시에 진행되게 한다. 페이스북은 또한 mcrouter라 불리는 독립 프록시를 제공하는데 멤캐시 서버의 인터페이스로 동작하고 요청/응답을 서버들간에 이어준다. 이들과 함께 슬라이딩 윈도우 형태의 흐름 제어 체계가 제공되어 유입이 몰리는 걸 제한한다.
Lease
Lease는 stale 집합 (웹 서버가 캐시에 stale 값을 쓸 때)과 thundering herds (키가 매우 집중적인 읽기와 쓰기 동작하에 있을 때)를 address하는데 사용한다. 클라이언트가 캐시 미스를 겪을 때, 멤캐시는 lease (요청 키에 연관된 64비트 토큰)를 준다. 멤캐시가 키에서 삭제 요청을 받으면, lease는 무효화되고 값은 설정하지 않는다. thundering herds를 완화하기 위해, 멤캐시는 키마다 매 10초에 한 번 토큰을 돌려준다. 읽기 요청이 토큰을 발행하고 10초 이내에 오면, 클라이언트는, 캐시에 갱신값이 설정 되길 기다리는 약간의 시간 후에 다시 시도하도록 알림을 받는다. stale 데이터를 반환하는 게 큰 문제가 안되는 상황에서는, 클라이언트는 기다릴 필요가 없이 stale 데이터(최대 10초만큼 오래된)를 돌려받는다.
Memcache Pools
다른 작업 부하는 다른 접근 패턴과 요청을 가질 수 있기 때문에, 멤캐시 클러스터는 풀로 나뉜다. 기본 풀은 와일드카드라 불리고 키마다 다른 풀이 있는데 와일드카드 풀에 존재할 수 없다. 작은 풀은 캐시 미스 비용이 비싸지 않은 키에 대해 provision될 수 있다. 요청 비율이 매우 높고 몇 개의 머신에 데이터가 쉽게 맞는다면 데이터는 풀 내에서 복제된다. 페이스북의 관점에서, 일관성을 유지하는데 추가 부담이 있긴 하지만, 복제는 샤딩보다 더 잘 동작한다.
일부 멤캐시 서버에 문제가 있는 경우, gutter라 부르는 머신의 작은 집합이 대신 한다. 문제가 좀 더 넓은 범위에서 발생하는 경우, 요청은 대체 클러스터로 보내진다.
Regions
다수의 프론트 엔드 클러스터(웹과 멤캐시 클러스터)는 저장 클러스터(데이터베이스)와 함께 지역을 정의한다. 저장 클러스터는 프론트엔드 클러스터에 걸쳐 복제되는 데이터의 authoritative 사본을 갖는다. 데이터 변경을 다루기 위해, mcsqueal이라 불리는 무효화 데몬이 각 데이터베이스에 배포되어 쿼리를 분석해, 삭제 명령을 나누고 그룹화하고 지역의 모든 프론트엔드 클러스터에 브로드캐스트로 보낸다. 배치 작업화 된 삭제 명령은 각 프론트엔드 클러스터의 mcrouter 인스턴스로 보내지고, 각각의 삭제로 나누고, 관계있는 멤캐시 서버로 전달된다. 최적화로서, 데이터를 변경하는 웹 서버는 또한 각자의 클러스터에 무효화를 보내 하나의 사용자 요청에 대한 쓰기-후-읽기 semantic을 확실히 한다.
Cold cluster Warmup
새 클러스터가 온라인 상태가 될 때, 값이 적재되는 데 시간이 걸리고 초기에 캐시 적중 비율은 매우 낮다. 그래서 Cold Cluster Warmup이라 부르는 기술을 채용해 새로운 cold 클러스터에 데이터베이스가 대신에 warm 클러스터에서 데이터를 가져와 적재한다. 이 방법으로 cold 클러스터는 몇 시간내에 완전한 가용상태가 된다. 하지만 race 조건같은 경우를 처리하는데는 추가 작업이 필요하다. 한 가지 예를 들면 이럴 수 있다: cold 클러스터의 클라이언트가 갱신 작업을 하고, 이 갱신이 warm 클러스터에 이르기 전에, 같은 키에 대한 다른 요청이 cold 클러스터에서 이뤄져서, cold 캐시에 있는 항목이 무한정 일치하지 않을 수 있다. 이런 경우를 피하기 위해, 멤캐시는 삭제 작업이 발생하면 (handoff 시간이라 부르는) 2초간 더하는 작업을 거부할 수 있다. 그러므로 만약 cold 클러스터에서 값이 갱신되고, 2초 이내에 후속 요청이 이뤄지면, 데이터가 생신되었음을 알리고 값을 더하는 작업은 거부될 수 있다. 2초는 대부분의 갱신이 이 시간 내에 전파되기 때문에 선택했다.
Across Region consistency
저장 장치 클러스터를 구성하는 클러스터와 여러 개의 프론트엔드 클러스터는 서로 다른 지역에 배치된다. 단 하나의 지역만 마스터 데이터베이스를 포함하고 나머지는 복제본으로 동작한다. 이렇게 하면 동기화에 문제가 있을 수 있다. 마스터 지역에서 쓰는 작업은 마스터 지역 내에서만 무효화를 보낸다. 지역 밖으로 무효화를 보내는 건 데이터가 복제되기 전에 삭제가 도달해 레이스 조건으로 이어질 수 있다. 페이스북은 mcsequal 데몬을 사용해 어느 정도의 시간동안 stale 데이터를 사용하는 비용을 피하는 데 도움을 줄 수 있다.
마스터가 아닌 지역에서 오는 쓰기 작업은 다르게 처리한다. 사용자가 마스터가 아닌 지역에서 대규모 복제가 지연되는 상황에서 데이터를 갱신했다고 가정하자. 복제 데이터베이스에서 캐시를 다시 채우는 건 복제 스트림을 따라잡은 후에만 허용한다. stale 데이터를 읽는 경우 원격 marker 체계를 사용해 확률을 최소화한다. marker가 존재한다는 건 복제본의 데이터가 stale을 나타내므로 쿼리는 마스터 지역으로 재전송된다. 웹서버가 키 k를 갱신할 때, 지역에서는 원격 marker rk를 설정하고, 마스터 데이터베이스에는 키 k로 쓰기 작업을 실행하고 로컬 클러스터에서는 k를 삭제한다. 다음 번에 k를 읽으려고 시도할 때, 캐시 미스가 발생할 것이고, rk가 존재하는지 점검해, 쿼리를 마스터 클러스터에게 재전송하게 될 것이다. rk가 설정되지 않았다면, 쿼리는 로컬 클러스터에게 갔을 것이다. 가장 최근에 갱신된 데이터를 읽기 위해서는 레이턴시가 발생한다.
Single Server Improvements
페이스북은 하나의 인스턴스로도 동작하는 멤캐시 서버를 위해 많은 개선을 했다. 이런 작업은 멤캐시를 확장해 검색 시간이 O(n)에서 멀어지지 않고 해시 테이블을 자동으로 확장하는 걸 지원하는 걸 포함하는데, 서버가 전역 잠금을 사용해 멀티 스레드로 동작하게 하고 각 스레드에는 contention을 감소시키기 위해 각각의 UDP 포트를 주도록 만들었다.
멤캐시는 메모리를 slab 클래스 — 미리 할당된, 동일한 크기로 나눈 메모리,로 조직한 Adaptive Slab Allocator를 사용한다. slab 크기는 64바이트에서 시작하고 1메가바이트까지 커진다. 각 slab 클래스는 사용 가능한 메모리 조각의 free-list를 유지하고 free-list가 빈 경우 1메가바이트 내에서 더 많은 메모리를 요청한다. 더 이상 메모리를 할당할 수 없다면, LRU 방식으로 기존 메모리를 제거한다. allocator는 작업 부하를 유지하기 위해 주기적으로 slab 할당을 재조정해 균형을 맞춘다. 덜 사용되는 slab에서 메모리를 해제하고 더 많이 사용되는 slab에 할당한다.
일부는 시간이 만료되는 즉시 삭제되기도 하지만, 항목의 대부분은 메모리에서 lazy하게 제거된다. 짧은 시간동안 있던 항목은 Transient Item Cache라 불리는 (만료될 때까지 초 단위로 색인되는) 링크드 리스트로 된 원형 버퍼에 올라간다. 매초마다, 버퍼의 헤드에 있는 버킷에 있는 모든 항목은 삭제하고, 헤드는 리스트의 다음 칸을 가리키게 된다. 자주 사용하는 short useful 수명을 갖는 항목의 키들의 집합에 짧은 만료 시간을 더해, 이 키들이 사용하는 멤캐시 풀의 비율을 적중 비율에 영향을 주지 않고 6%에서 0.3%로 감소시켰다.
Lessons Learnt
멤캐시의 디자인 결정은 직관이 아니라 데이터로 이뤄졌다. 페이스북은 읽기 동작에 UDP를 사용하고 holdoff 시간과 같은 파라미터의 값을 선택하는 결정을 하기 전에 여러가지 설정을 가지고 실험한 것 같다. 이게 마땅히 그래야 하는 방법 — 데이터 주도 결정이다. 멤캐시를 개발하는 전체 과정에서, 페이스북은 각 가능한 경우를 최적화하는 대신 많은 사용자와 많은 경우에 영향을 줄 수 있는 최적화에 촛점을 맞췄다.
페이스북은 캐싱 계층을 영구 저장 계층과 분리해 두 계층을 각각 형성하기 쉽게 만들었다. 캐시 입력 로직을 어플리케이션 자체에서 다루도록 해, 멤캐시를 다른 데이터 저장장치와 연결하기 쉽게 만들었다.상태 데이터를 읽는 확률을 파라미터로 모델링해, 영구 저장 장치에 대한 지연과 캐시 히트 비율을 어느 정도까지 설정가능하도록 해 멤캐시의 영역을 확장했다. 페이스북은 하나의 페이지 로드 요청을 여러 개 요청으로 나눠, 각 컴포넌트에 대해 서로 다른 종류의 stale 데이터 tolerance를 허용했다. 예를 들어, 프로필 사진을 제공하는 서버는 메시지를 제공하는 서버보다 더 오랫동안 컨텐트를 캐시할 수 있다. 이렇게 하면 응답 지연을 낮추고 데이터 계층에서 로드를 감소할 수 있다.
페이스북의 멤캐시는 보다 일반적인 문제 — 확장 가능한 분산 키-값 저장소, 를 해결하는 많은 방법 중 하나이다. 아마존의 Dynamo는 작은 데이터 크기에 대해 쓰기에 집중하는 부하를 집중해 문제를 해결하고 페이스북은 읽기에 집중해 문제를 푼다. 목록의 다른 후보들은 카산드라, 볼드모트, 레디스, 트위터의 멤캐시 등이다. 순전히 많은 수의 가능한, 잘 알려진 해결책들은 문제에 대해 많은 차원을 제공하는데, 그들 중 일부는 아직 알려지지 않았고, 우리는 여전히 모든 경우에 사용할 수 있는 하나의 해결책은 갖고 있지 않다.
