vbuckets로 멤캐시드 확장하기

수년 동안 사람들은 대규모 사이트를 확장하기 위해 멤캐시를 사용해 왔습니다. 원래는 간단한 모듈로 선택 해시 알고리즘이 사용되었습니다. 이 알고리즘은 실제로 여전히 많이 사용되고 있으며 이해하기 매우 쉽습니다(하지만 전체 시스템에 적용했을 때 제대로 이해하지 못하는 사람들이 종종 있습니다). 알고리즘은 기본적으로 다음과 같습니다:

즉, 해시 알고리즘이 주어지면 키를 해시하고 서버 목록의 위치에 매핑한 다음 해당 서버에 해당 키를 요청합니다. 이는 정말 이해하기 쉽지만 몇 가지 문제가 발생합니다..

1. 일부 서버는 다른 서버보다 용량이 더 큽니다.
2. 서버가 죽으면 캐시 누락이 급증합니다.
3. 깨지기 쉬운/혼란스러운 구성(깨진 것이 작동하는 것처럼 보일 수 있음)

가중치를 무시하고(기본적으로 동일한 서버를 목록에 여러 번 추가하여 "해결"할 수 있음), 가장 큰 문제는 서버가 죽었을 때 어떻게 해야 하는가 하는 것입니다. 새 항목을 추가하고 싶습니다.또는 대체 하나.

2007년에 리차드 존스 와 last.fm 는 이러한 문제를 해결하기 위한 새로운 방법을 만들었습니다. 케타마. 이것은 "일관된 해싱", 즉 서버 목록이 변경될 때 원하는 데이터가 없는 서버로 해싱할 확률을 크게 낮추는 방법을 위한 라이브러리이자 방법입니다.

멋진 시스템이지만 이 글에서는 자세한 내용은 다루지 않겠습니다. 여전히 다음과 같은 프로젝트에는 적합하지 않은 결함이 있습니다. 멤베이스를 사용하면 데이터가 있는 서버로 연결될 확률이 확률적으로 더 높을 뿐입니다. 다른 관점에서 보면, 위에서 설명한 모듈러스 방법보다 빈도가 적을 뿐 가끔 잘못된 서버로 연결될 가능성이 거의 보장됩니다.

새로운 희망

2006년 초, 아나톨리 보로비는 다음과 같이 소개했습니다. 일부 코드 를 사용하여 "관리되는 버킷"이라고 부르는 것을 만들었습니다. 이 코드는 2008년 말까지 그 자리에 있었습니다. 제거되었습니다. 완전하지도 않았고, 전혀 이해되지도 않았으며, 그런 것들을 더 쉽게 구축할 수 있는 새로운 프로토콜을 만들었기 때문입니다.

우리는 그것을 다시 가져왔고, 왜 그것이 존재하고 왜 여러분이 그것을 원하는지 말씀드리겠습니다.

먼저, 저희가 함께하고 싶었던 내용을 간단히 요약해 보겠습니다:

1. 잘못된 서버에서 요청을 처리하지 마세요.
2. 확장 허용 그리고 마음대로 내려놓을 수 있습니다.
3. 서버는 서비스해서는 안 되는 명령을 거부합니다, 하지만
4. 서버는 여전히 서로에 대해 알지 못합니다.
5. 한 서버에서 다른 서버로 데이터 집합을 원자 단위로 전달할 수 있습니다, 하지만
6. 시간적 제약이 없습니다.
7. 일관성이 보장됩니다.
8. 일반적인 경우에는 네트워크 오버헤드가 전혀 발생하지 않습니다.

앞서 살펴본 다른 솔루션과 비교하여 마지막 요점을 조금 더 설명하자면, 프록시, 위치 서비스, 서버 간 지식 또는 기타 오버헤드가 필요한 마법 같은 것들이 없습니다. vbucket 인식 요청은 데이터에 대한 작업을 수행하는 것보다 데이터를 찾는 데 더 많은 네트워크 작업이 필요하지 않습니다(심지어 1바이트도 더 크지 않습니다).

"최대 부하가 발생했을 때 서버를 추가할 수 있어야 한다"와 같은 다른 사소한 목표도 있지만, 이는 무료로 제공됩니다.

소개합니다: VBucket 소개

v버킷은 개념적으로 가능한 모든 키의 계산된 하위 집합입니다.

해시 테이블을 구현해본 적이 있다면, 모든 노드 조회를 위한 해싱의 첫 번째 수준인 가상 해시 테이블 버킷이라고 생각할 수 있습니다. 키를 서버에 직접 매핑하는 대신, vbucket을 서버에 정적으로 매핑하고 일관된 키 → vbucket 계산을 수행합니다.

클러스터의 v버킷 수는 서버 토폴로지에 관계없이 일정하게 유지됩니다. 즉, 키 x 는 항상 동일한 해시가 주어지면 동일한 vbucket에 매핑됩니다.

이 개념에 맞게 클라이언트 구성이 조금 더 커져야 합니다. 이제 구성에는 단순한 서버 시퀀스 대신 명시적인 vbucket-서버 매핑도 포함됩니다.

실제로는 서버 시퀀스, 해시 함수 및 v버킷 맵으로 구성을 모델링합니다. 서버 3개와 v버킷 6개(설명용으로 아주 적은 수)가 주어졌을 때 위의 모듈러스 코드와 관련하여 이것이 어떻게 작동하는지에 대한 예는 다음과 같습니다:

이 코드를 읽으면 vbuckets의 도입이 어떻게 엄청난 힘과 유연성을 제공하는지 분명하겠지만, 그렇지 않은 경우를 대비해 계속 설명하겠습니다.

용어

자세한 내용을 살펴보기 전에 여기서 사용할 용어를 먼저 살펴보겠습니다.

클러스터:

 공동 작업 서버의 모음입니다.

서버:

 클러스터 내의 개별 머신입니다.

vbucket:

 가능한 모든 키의 하위 집합입니다.

또한 특정 서버에서 특정 vbucket은 다음 상태 중 하나에 속하게 됩니다:

활성:

 이 서버는 이 vbucket에 대한 모든 요청을 서비스하고 있습니다.

죽었습니다:

 이 서버는 이 vbucket에 대해 어떠한 방식으로도 책임을 지지 않습니다.

복제본:

이 vbucket에 대한 클라이언트 요청은 처리되지 않지만 복제 명령을 받을 수 있습니다.

보류 중입니다:

 이 서버는 이 vbucket에 대한 모든 요청을 차단합니다.

클라이언트 운영

각 요청에는 해싱 알고리즘에 의해 계산된 vbucket ID가 포함되어야 합니다. 바이너리 프로토콜의 예약 필드를 사용하여 최대 65,536개의 vbucket을 만들 수 있었습니다(실제로는 상당히 많은 수입니다).

클라이언트가 해싱 알고리즘과 v버킷 수에 동의하기만 하면 올바른 v버킷을 일관되게 선택할 수 있으므로, 서버를 잘못 구성하여 특정 v버킷에 대해 잘못된 서버와 통신하는 것이 훨씬 더 어렵습니다.

또한, 설정 배포와 구성 배포, 매핑 알고리즘에 대한 합의, 잘못된 설정에 대한 대응을 반복적으로 해결할 필요가 없는 문제가 libvbucket을 통해 해결되었습니다. libvbucket의 포트를 Java 및 .net으로 가져오기 위한 작업이 진행 중이며, 그 동안 영구 클라이언트가 없거나 선호하는 클라이언트가 따라잡을 때까지 기다릴 수 없는 경우 moxi가 모든 번역을 대신 수행해 드립니다.

하나의 활성 서버

배포에는 일반적으로 1,024개 또는 4,096개의 v버킷이 있지만, 생각하기 쉽고 그림을 그리기 쉽기 때문에 이 모델은 6개로 계속 진행할 것입니다.

오른쪽 이미지에는 활성 버킷 6개로 실행 중인 서버가 하나 있습니다. 가능한 모든 버킷이 있는 모든 요청은 이 서버로 이동하며, 이 서버는 모든 요청에 대해 응답합니다.

하나의 활성 서버, 하나의 새 서버

이제 새 서버를 추가해 보겠습니다. 서버를 추가해도 트리가 불안정해지지 않습니다(오른쪽에서 볼 수 있듯이).

클러스터에 서버를 추가하고 구성에서 모든 클라이언트에 푸시한다고 해서 서버가 즉시 사용된다는 의미는 아닙니다. 매핑은 별도의 개념이며, 모든 v버킷은 여전히 이전 서버에 독점적으로 매핑됩니다.

이 서버를 유용하게 만들기 위해 한 서버에서 다른 서버로 v버킷을 전송합니다. 전송을 적용하려면 새 서버가 소유할 vbuckets 세트를 선택하고 수신 서버에서 모두 보류 중 상태로 설정합니다. 그런 다음 데이터를 가져와 새 서버에 배치하기 시작합니다.

이 정확한 순서대로 단계를 수행하면 특정 시점에 특정 vbucket에 대해 하나 이상의 서버가 활성화되어 있지 않도록 보장할 수 있습니다. 없이 실제 연대기와는 전혀 상관없습니다. 즉, 몇 시간 동안 시계가 왜곡되고 몇 분씩 걸리는 vbucket 전송이 일관성을 잃지 않도록 할 수 있습니다. 또한 고객에게 다음과 같은 일이 발생하지 않도록 보장합니다. 잘못된 답변합니다.

1. 새 서버의 vbucket은 보류 중 상태가 됩니다.
2. v버킷 추출 탭 스트림이 시작됩니다.
3. 대기열이 충분한 드레인 상태에 있을 때 vbucket 탭 스트림은 원자적으로 상태를 종료로 설정합니다.
4. 새 서버는 이전 서버가 더 이상 요청을 서비스하지 않는다는 확인을 받은 후에만 대기 중 상태에서 활성 상태로 전환되며, 하위 섹션이 독립적으로 전송되므로 한 번에 서버가 이동한다고 생각하지 않고 한 번에 서버의 일부만 이동한다고 생각할 필요가 있습니다. 따라서 사용량이 많은 서버에서 트래픽을 천천히 마이그레이션할 수 있습니다. 피크 시 를 최소한의 영향으로 덜 바쁜 서버로 이동합니다(10개의 서버에 각각 1,000만 개의 키가 있는 4,096개의 v버킷이 있는 경우, 11번째 서버를 가져올 때 v버킷 전송을 통해 한 번에 약 2만 개의 키를 이동하게 됩니다).

vbucket에 다음과 같은 기간이 있음을 알 수 있습니다. 아니요 활성 서버를 전혀 사용하지 않습니다. 이는 전송 메커니즘의 가장 마지막 단계에서 발생하며 차단을 유발합니다. 일반적으로 클라이언트가 실제로 차단되는 경우는 거의 없습니다. 이는 클라이언트가 이전 서버에서 전송 준비가 완료되었다는 오류를 받고 새 서버가 마지막 항목을 받기 전에 새 서버에 도착할 수 있을 때만 발생합니다. 그러면 새 서버는 해당 항목이 전달될 때까지만 클라이언트를 차단하고 vbucket은 다음과 같이 전환할 수 있습니다. 보류 중 에 활성 상태입니다.

이전 서버의 v버킷은 자동으로 이전 서버의 죽은 상태가 충분히 진행되면 하지 않습니다 데이터를 자동으로 삭제합니다. 이는 명시적으로 수행됩니다. 이후 새 노드가 사라졌음을 확인합니다. 활성. 대상 노드를 설정하기 전에 어느 시점에서든 실패하는 경우 활성로 설정하면 이전을 중단하고 이전 서버를 그대로 둘 수 있습니다. 활성 (또는 활성 충분히 진행되었다면).

복제 상태란 무엇인가요?

HA가 많이 나오기 때문에 반드시 다루었습니다. A 복제본 v버킷은 죽은 vbucket이 일반 클라이언트의 관점에서 볼 때. 즉, 모든 요청은 거부되지만 복제 명령은 허용됩니다. 이것은 또한 보류 중 상태는 레코드가 저장되지만 클라이언트가 차단하지 않는다는 점에서 대조적입니다.

오른쪽 이미지에서 서버 3개, v버킷 6개, v버킷당 하나의 복제본이 있는 경우를 생각해 보세요.

마스터와 마찬가지로 각 복제본도 정적으로 매핑되므로 언제든지 이동할 수 있습니다.

이 예에서는 목록의 "다음" 서버 즉, 다음 서버에 vbucket을 복제합니다. 활성 v버킷 켜기 S1 에 복제됩니다. 복제본 버킷 켜기 S2 - 다음에도 동일 S2 → S3 그리고 S3 → S1.

여러 복제본

또한 노드에서 데이터 복사본을 두 개 이상 사용할 수 있는 전략도 지원합니다.

아래 다이어그램은 3개의 서버가 각 버킷의 활성 복제본 1개와 복제본 2개를 보유하는 두 가지 전략을 보여줍니다.

1:n 복제

첫 번째 전략(1:n)는 여러 개의 슬레이브를 동시에 서비스하는 마스터를 의미합니다. 이 개념은 여러 복제본을 허용하는 데이터 스토리지 소프트웨어를 다뤄본 사람이라면 누구나 잘 알고 있습니다.

체인 복제

두 번째 전략(체인)는 하나의 마스터가 하나의 슬레이브만 서비스하지만, 그 슬레이브가 또 다른 다운스트림 슬레이브를 가지고 있는 것을 말합니다. 이렇게 하면 서버에서 단일 스트림의 변경 이벤트가 발생하면서도 모든 레코드의 사본을 두 개로 유지할 수 있다는 장점이 있습니다. 하지만 체인을 통과할 때 복제 지연 시간이 길어진다는 단점이 있습니다.

물론 두 개 이상의 추가 복사본이 있는 경우 마스터에서 단일 스트림을 수행한 다음 체인 V의 두 번째 링크가 출력되도록 혼합할 수 있습니다. 1:n 두 개의 추가 서버로 스트리밍합니다.

모든 것은 매핑하는 방식에 달려 있습니다.

감사

덕분에 Dormando 의 원래 "관리되는 버킷" 코드, 의도 및 워크플로우를 해독하는 데 도움이 됩니다. Jayesh Jose 그리고 독립적으로 이 기능을 발견하고 많은 사용 사례를 만들어낸 다른 Zynga 직원들에게 감사드립니다.