쉽게 이해할수 있는 Consistent Hashing

기존에 사내에서 발표했던 Consistent Hashing 발표정리한 문서

소개

David Kager 라는 사람에 의해서 처음 소개

현대물리학계의 거장으로 알려진 알란 히거(UC산타바바라)는 h 인덱스가 107,

노벨물리학상을 수상한 사람들의 평균 h 인덱스는 41 정도다.

논문 주소 : http://david.choffnes.com/classes/cs4700sp14/papers/akamai.pdf

무슨 내용일까..?

문제 발생

"핫스팟" 발생을 줄이는 데 사용할 수 있는 분산 네트워크에 대한 캐싱 프로토콜

노트북, 개인 휴대 정보 단말기 따위의 이동 단말기를 사용하여 액세스 포인트가 설치된 주변 지역에서 무선으로 네트워크에 접속하여 초고속 인터넷과 각종 콘텐츠를 이용할 수 있는 서비스 가능 지역

핫스팟은 다수의 클라이언트가 단일 서버에서 동시에 데이터에 액세스를 할때 발생합니다.

 

사이트가 이러한 모든 클라이언트를 동시에 처리하도록 프로비저닝되지 않으면 서비스가 저하되거나 손실될 수 있다.

고전적 해결방법

• 파티셔닝이나 로드 밸런싱을 할 때 Key를 기반으로 나눈다 • 파티셔닝: 하나의 데이터베이스 인스턴스에서 데이터(테이블)를 분할 만약 사는지역으로 파티셔닝이 된다고 하면

만약 사는지역으로 파티셔닝이 된다고 하자

사람 → 경기도, 서울, 강원도

서울 사는 사람이 많으니깐 데이터 저장도 서울 사람이 더 많이 된다.

파티셔닝 키를 적절하게 잡지 않으면 특정 패턴으로 hotspot 이 생긴다는 단점이 있다.

 

좋은 해시 함수는 서로 다른 입력 값에 대한 출력이 출력 범위에 가능한 고르게 분산되도록 입력 데이터를 어떻게든

"채핑하고 혼합"해야 한다.

해쉬 함수는 잘 작동하지만 캐시가 추가되거나 삭제되서 변경될 경우 거의 모든 객체의 위치도 함께 변경,

키가 새 위치에 없기 때문에 갑자기 키를 찾을 수 없게되고 hash가 무용지물이 된다.

key로 가져오는 쿼리는 누락될 수 있으며, 원본 데이터는 다시 캐시할 원본에서 다시 검색해야 하므로 원본 서버(일반적으로 데이터베이스)에 많은 부하를 걸 수 있습니다. 이로 인해 성능이 심각하게 저하하게 된다.

단점

• 서버 추가 시 다시 계산 후 할당
• 서버 제거 시 다시 계산 후 할당

결국 다시 캐시를 구축해야 하는데, 이미 요청이 있다면 문제가 생길 수 있다.

Consistent 해시를 이용해서 이러한 문제를 극복할 수 있다.

Consistent Hashing 은 이것을 해결하기 위해 나온 방법 중 하나

해결책

로드 밸런싱을 수행하기 위해서 시스템에서 사용하는 일반적인 방법 중 하나는 일관된 해싱을 사용하는 것입니다.

일관된 해싱

위와 같은 상황에서 로드 밸런싱을 수행하는 방법 중 하나는 일관된 해싱 개념을 사용하는 것.

• 메타 정보를 조회하지 않아도 클러스터에서 키가 저장된 노드를 바로 찾아갈 수 있는 방법

일관된 해싱을 사용하면 요청이 해시 버킷에 매핑되는 동시에 시스템이 각 시스템에서 양호한 로드 팩터를 유지할 수 있도록 노드를 유연하게 추가 및 제거할 수 있다.

최소 가능한 해시 값 0은 0의 각도에 해당하고, 최대 가능한 값(일부 INT_MAX라고 부를 큰 정수)은 2θ 라디안(또는 360도)의 각도에 해당하며, 다른 모든 해시 값은 그 사이의 어딘가에 선형적으로 들어맞는다

개체 키는 반시계 방향(또는 사용된 규칙에 따라 시계 방향)에서 키가 가장 가까운 서버에 속합니다. 즉, 주어진 키를 요구할 서버를 찾으려면 원에서 키를 찾아 서버를 찾을 때까지 오름각 방향으로 이동

각 서버에 하나의 레이블(각도)이 아니라 여러 개의 레이블(각도)을 할당합니다. 그래서 A, B, C라는 라벨을 붙이는 대신 A0을 붙일 수 있습니다. A9, B0.. B9와 C0.. C9, 모두 원을 따라 흩어져 있습니다. 가중치(weight)로 알려진 레이블(서버 키)의 수를 늘리는 계수는 키가 각 레이블에 나타날 확률을 조정하는 상황에 따라 달라집니다

서버 B가 제거되었다고 상상해 보십시오. 이렇게 하면 이전에 삭제된 레이블에 인접한 개체 키가 A0로 레이블링되어 서버 A에 재할당됩니다.

원래 A0와 A2에 속해 있던 다른 객체 키는 어떻게 될까?

전혀 문제없음

서버를 제거하는 대신 서버를 추가하는 경우에도 비슷한 일이 발생합니다. 예제에 서버 D를 추가하려는 경우(예: C를 대체하는 경우), D0 레이블을 추가해야 합니다. D9. 그 결과 기존 키(모두 A 또는 B에 속하는 키)의 약 1/3이 D에 재할당되고, 나머지는 그대로 유지된다.

 

만약 노드를 추가하면 특정 노드(많은 데이터를 가진 노드)가 맡고 있던 범위를 분할하여 새 노드에 할당한다. 

노드를 삭제할 때는 링에서 삭제된 노드가 맡고 있던 범위를 인접 노드가 맡는다. 따라서 서비스 중에 노드의 추가/삭제로 인해 영향을 받는 노드 수를 최소화할 수 있다.

다시 정리하자만 일관적 해싱은 

Key의 집합을 *K*, 슬롯의 크기를 *N*  라고 했을 때, N의 갯수가 바뀌더라도(서버의 개수가 변화) 대부분의 키들이  전체 데이터에 대한 재분배가 필요 없고, 그대로 사용할 수 있는 해싱 기법.

Consistent hash를 어디에 적용해야 할까?

웹 캐시 시스템 : 성능 최적화를 위해 분산 캐싱을 사용할 경우 캐싱 서버 수가 변경될 수 있습니다(서버가 손상되거나 전체 용량을 늘리거나 줄이기 위해 서버를 추가하거나 제거해야 함).

Consistent hash를 이용하면, 분산 웹 캐시 시스템을 만들 수 있다.

https://docs.google.com/drawings/d/18JT-sYkIFEFd1SgZABTGhRHOhuGAh0oYMnsVAAxuJJc/pub?w=579&h=340

1. 유저의 요청은 먼저 Proxy server로 향한다.
2. Proxy 서버는 유저가 요청한 자원(URL)이 해시테이블에 있는지 확인한다.
3. 해시테이블에 있다면, Cache Server에 요청한다.
4. 해시테이블에 없거나, 캐시에서 가져오는게 실패했다면 Web Server에 요청한다.

Consistent hash로 구성하면, (관리 없이)자유롭게 캐시를 늘리거나 줄일 수 있다.

카카오에서는 이렇게 사용한대요

여러 대의 노드로 구성된 클러스터를 구성하여 consistent hashing기법을 이용해 컨텐츠를 고르게 분포시키고, 클라이언트 요청이 들어왔을 때 알맞은 노드에 요청을 라우팅 해주도록 설계

redis

redis Cluster Introduction 레디스 클러트터 소개

redis 클러스터는 서버에서 데이터를 분산

레디스 클러스터는 퍼포먼스 등의 이유로 사용하지 않는다

consistent hashing 은 클라이언트에서 분산을 구현

구글에서 공개한 소스 5줄로 구현

int32 _t JumpConsistentHash(uint64_t key, 
                            int32_t num_buckets) { 
	int64_t b =­-1, j = 0; 
	while (j < num_buckets) { 
		b = j; 
		key = key * 2862933555777941757ULL + 1; 
		j = (b + 1) * (double(1LL << 31) 
                  / double((key >> 33) + 1)); 
	} 
	return b; 
}

 

1. redis 를 한대가 아닌 여러대 클러스터 환경에서 운영한다고 가정
2. 평소에 3대로 운영(운영할때 이미 consistent hashing으로 처리가 되고 있다고 가정)
3. 트래픽이 몰린다!
4. 인프라에서 redis 서버 추가
5. 서버가 추가시 consistent hashing 으로 특정 노드(많은 데이터를 가진 노드)가 맡고 있던 범위를 분할하여 새 노드에 할당
6. 트레픽이 줄어들면 삭제할 때는 링에서 삭제된 노드가 맡고 있던 범위를 인접 노드가 맡는다

Azure Cache for Redis

Azure Cache for Redis 를 사용하면 자동으로 마이크로소프트에서 제공하는

알고리즘으로 로드 밸런싱이 되지 않을까...?

마이크로소프트에서 권장하는 답변은 최상의 성능 및 처리량의 경우 키를 고르게 분산하는 것이 좋습니다. 해시 태그로 키를 사용하는 경우 키가 균등하게 분산되도록 하는 것은 애플리케이션이 담당합니다.

이상적인 목표

do you know kube?

• container orchestration
• easy scaling

쉬운 스케일링, 선언적으로 자동화

1. 트레픽들어온다아아아
2. 쿠버네티스가 사용률 감지
3. redis auto scaling 되면서 cache pod 증가
4. 증가된 pod에 Consistent hash로 분배
5. Exporter와 Prometheus, Grafana를 사용해 모니터링

 

일관된 해싱을 사용하는 다른 오픈소스

(Consistent hashing)은 웹서버의 개수가 변동하는 가운데 분산 요청을 처리하기 위해서 고안된 방법

분산이 중요한 키워드: 탑 레벨 아파치 프로젝트인 카산드라도 이 알고리즘을 사용

• Cassandra distributes data across the cluster using a Consistent Hashing  algorithm

Memcached 에서의 Consistent Hashing

참고 :

https://www.joinc.co.kr/w/man/12/hash/consistent

https://www.popit.kr/jump-consistent-hash/

https://www.toptal.com/big-data/consistent-hashing

https://tech.kakao.com/2017/10/23/wcache-1/

https://charsyam.wordpress.com/2011/11/25/memcached-에서의-consistent-hashing/

https://smallake.kr/?p=17730

https://www.mimul.com/blog/linux-server-operations/

https://www.youtube.com/watch?v=zaRkONvyGr8