일관된 해시 알고리즘 이해 및 구현

일관된 해시 알고리즘 이해 및 구현

반응형

Go-zero의 분산 캐싱 구현에서는 일관된 해시 알고리즘을 많이 사용했습니다. 이 기사에서는 일관된 해시의 알고리즘과 구현 세부 사항에 대해 Go-zero에서 설명하겠습니다.

스토리지를 예로 들자면, 당사의 스토리지는 전체 마이크로 서비스 시스템의 단일 노드일 뿐이라고 말할 수 없습니다.

첫째는 안정성을 향상시키는 것이다. 단일 노드가 중단되면 전체 스토리지를 사용할 수 없게 됩니다.

둘째, 데이터 내결함성의 경우입니다. 단일 노드 데이터 손실로 인해 데이터 손실이 발생합니다. 다중 노드의 경우 상호 백업 노드가 동시에 파괴되지 않는 한 노드에 백업이 있습니다.

그렇다면 다중 노드 사례에서 데이터를 어떤 노드에 기록해야 하는가에 대한 의문이 제기됩니다.

으깨다

따라서 기본적으로 입력 값은 "압축"할 수 있고 일반적으로 고유하고 uint64**와 같이 매우 압축된 더 작은 값으로 변환될 수 있어야 합니다.

idempotent: 해시가 동일한 값으로 계산될 때마다 동일한 값을 얻도록 보장해야 합니다.

이것이 해시 알고리즘이 하는 일입니다.

그러나 라우팅에 대한 일반적인 해시 알고리즘(예: 키 % N)을 사용하십시오. 예외 또는 하트비트 예외로 인해 노드가 클러스터 밖으로 떨어지면 해시 라우트로 인해 많은 데이터가 다른 노드로 재배포됩니다. 노드가 새로운 요청을 수락할 때 데이터를 가져오기 위해 로직을 재처리해야 합니다. 데이터가 캐시에 있을 경우 캐시 눈사태를 쉽게 일으킬 수 있습니다.

이 경우 일관된 해시 알고리즘을 도입할 필요가 있습니다.

일관된 해시

일관된 해시가 이 문제들을 얼마나 해결하는지 봅시다.

재탕을 하다

대규모 재탕 문제를 해결하는 것부터 시작합시다.

위와 같이 새 노드를 추가할 때 영향을 받는 유일한 키는 key31입니다. 새 노드가 추가(제거)되면 해당 노드 근처의 데이터만 영향을 받습니다. 다른 노드의 데이터는 영향을 받지 않으므로 노드 변경 문제가 해결됩니다.

이것이 바로 단조함입니다. 이는 일반 해시 알고리즘이 분산 시나리오를 충족할 수 없는 이유이기도 합니다.

데이터 꼬임

실제로 위의 그림은 대부분의 키가 현재 노드 1에 집중되어 있음을 보여준다. 노드 수가 상대적으로 적을 경우 특정 노드에 집중된 대부분의 키를 트리거할 수 있습니다. 모니터링 시 문제는 노드 간의 부하가 일정하지 않다는 것입니다.

이 문제를 해결하기 위해 일관된 해시는 가상 노드 개념을 도입합니다.

부하가 고르지 않기 때문에 인위적으로 균형 잡힌 시나리오를 구성하지만 실제 노드 수는 그 정도밖에 없다. 따라서 가상 노드를 사용하여 영역을 분할하지만 실제 서비스된 노드는 이전 노드와 동일합니다.

구체적인 구현

Get()부터 시작하겠습니다.

얻다

먼저, 실행의 원리에 대해 이야기해 봅시다.

키의 해시를 계산하다.

일치하는 첫 번째 가상 노드의 색인을 찾아 해당 h.keys[index]: 가상 노드 해시 값을 가져옵니다.

이 링으로 이동하여 링과 일치하는 실제 노드를 찾습니다.

실제로 링에 []노드가 있음을 알 수 있습니다. 이는 가상 노드 해시를 계산할 때 다른 가상 노드 해시가 실제 노드에 해당하는 해시 충돌이 발생할 수 있기 때문입니다.

이는 또한 노드와 가상 노드가 일대다 관계에 있음을 의미합니다. 그리고 안에 있는 반지는 다음과 같은 디자인입니다.

이것은 실제로 일관성 해시의 할당 전략을 보여준다.

가상 노드가 값 도메인 분할로 사용됩니다. 키는 가상 노드에 의해 제한된 노드를 가져오는 데 사용됩니다.

가상 노드를 사용하면 서로 다른 노드에 할당된 키가 해시에 의해 거의 균등하게 분배됩니다. 즉 분할 바인딩입니다.

새 노드가 추가되면 여러 가상 노드가 할당됩니다. 새 노드는 여러 기존 노드의 압력을 로드할 수 있으므로 글로벌 관점에서 용량을 확장할 때 로드 밸런싱을 쉽게 달성할 수 있습니다.

노드 추가

Get을 읽고 나면 전체 일관된 해시가 어떻게 설계되었는지 대략 알 수 있습니다.

type ConsistentHash struct { hashFunc Func // hash function replicas int // virtual node amplification factor keys []uint64 // store virtual node hash ring map[uint64][]interface{} // virtual node to actual node correspondence nodes map[string]lang.PlaceholderType // actual node storage [easy to find quickly, so use map] lock sync.RWMutex }

기본적인 일관된 해시가 완전히 구현되도록 말이죠.

사용 시나리오

첫머리에 따르면 일관성 해시는 분산 시스템에서 다음과 같은 용도로 널리 사용될 수 있습니다.

분산 캐싱 redis 클러스터와 같은 스토리지 시스템에 캐시 프록시를 구축하고 라우팅을 자유롭게 제어할 수 있습니다. 이 라우팅 규칙에 대해, 우리는 일관된 해시 알고리즘을 사용할 수 있다.

서비스 검색

분산 작업 스케줄링

위의 모든 분산 시스템은 로드 밸런싱 모듈에서 사용할 수 있습니다.

프로젝트 주소

https://github.com/zeromicro/go-zero

Go-zero를 사용하는 것을 환영하며 우리를 응원할 별을 드립니다!

from http://devcloset.tistory.com/398 by ccl(A) rewrite - 2021-09-21 22:26:18