해싱
해시테이블에서도 사용하는 알고리즘이다.
주어진 키에, 해시 함수를 적용하고, 테이블의 총 크기/길이로 나눈 나머지 값을, 즉 modular(%)연산의 값으로 서버 인덱스를 가지는 개념이다.
로드밸런서로 라우팅 시에 아래와 같이 해싱을 통해 처리해줄 수 있다.
- Request ID 추출 : IP, User ID, 몇번째로 Request를 요청했는지에 대한 순서, …
- Hash(Request ID)를 통한 해시값 도출
- 주어진 해시값에 따라 라우팅
문제점
위와 같이 어떠한 갯수, 크기에 따라서 해시 처리를 하면, 갯수, 크기가 변하면 모든게 변하게 된다.
위 이미지에서는 총 크기를 5로 잡았는데, 만약 4로 변경하게 된다면 아래와 같이 많은 데이터가 다른 인덱스를 가져야한다.
이렇게 버킷이 추가되거나 삭제됨으로 인해 키 값이 많이 이동되는 것은, 키 값이 리밸런싱되는 것은, 성능 저하의 원인이 된다.
이러한 부작용으로 인해 생길 수 있는 부작용의 예시를 들어보면,
- 세션 - 로그인 세션을 처리하는 서버에 로드 밸런싱을 적용했을 경우
- 로그인 세션 서버 하나가 죽으면, 인덱스 값이 달라지고, 일부 요청은 기존과 다른 서버로 요청이 전달된다.
- 새롭게 전달된 서버에는 세션데이터가 없으므로 사용자는 다시 로그인해야한다.
- 캐시 - 데이터를 캐싱 처리하는 서버에 로드 밸런싱을 적용했을 경우
- 캐싱 서버 하나가 죽으면, 인덱스 값이 달라지고, 일부 요청은 기존과 다른 서버로 요청이 전달된다.
- 새롭게 전달된 서버에는 기존에 캐싱했던 데이터가 없으므로, 이미 열람했던 데이터 임에도 불구하고 데이터를 다시 로딩해야한다.
Consistent Hash 안정 해시
Consistent Hash를 사용하면 리밸런싱을 최소화 하기 때문에, 이러한 부작용을 최소화된다.
→ Consistent Hash은 버킷이 추가, 제거 될 때 평균적으로 전체 키의 수 / 전체 버킷의 수 개수의 키가 이동한다.
Consistent Hash는 주어진 키가 어느 서버(노드)에 고정적으로 속하는 개념이 아니다.
위 이미지 처럼 해시값에 따라 링 모양(Hash Ring)안에 노드(버킷/서버/…)와 데이터가 배치한다.
그리고, 각 데이터에서 시계 방향으로 가장 처음 도달하는 노드가 이 데이터와 연결될 노드이다.
아래와 같이 그림으로 표현할 수 있다.
버킷이 추가되거나 삭제되었을 때
이러한 Consistent Hash의 가장 큰 차이점이자 단점은 버킷의 추가, 삭제의 영향을 받는 범위가 훨씬 좁다는 것이다.
어떠한 버킷이 추가되거나 삭제되면, 새롭게 추가된 버킷을 제일 가까운 버킷으로 하는 키값만 혹은 삭제된 버킷의 다음에 위치하는 버킷을 제일 가까운 버킷으로 하는 키 값만 영향을 받는다는 것이다.
아래 그림은 3번 노드(버킷)이 삭제된 경우이다.
3번 노드가 삭제되기 전, Jem 이라는 데이터는 3번 노드가 가장 가까운 버킷이었기에 3번 노드가 이 데이터를 관리했다.
3번 노드가 삭제된 후, Jem 이라는 데이터는 1번 노드가 가장 가까운 버킷이 되었기에, 1번 노드가 이 데이터를 관리하게 되었다.
만약, modular 연산을 통해 데이터를 분산 처리하였다면 많은 리밸런싱이 적용되었을 것이다.
하지만, Consistent Hash를 통해서 훨씬 좁은 영역만이 영향을 받게 되었다.
즉, 버킷이 추가되거나 제거되면 그 버킷에서 시작해서 시계 반대 방향으로 다른 버킷이 등장할 때까지가 영향 범위이다.
문제점
만약 위의 3번 노드가 삭제되는 그림에서, 3번뿐 아니라 4번, 5번도 삭제되면 어떻게 될까? 1번 노드가 그 데이터를 모두 담당하게 된다.
즉, 리밸런싱의 범위가 좁아진다고 하더라도, 버킷의 분포가 균일해지지 않아서 데이터가 균일하지 않게 분산 처리 된다는 것이다.
다른 예시로 이 문제점을 살펴보자.
위 이미지와 같이 Consistent Hash를 구성하였다.
그리고, 1번 노드를 삭제한다면, 균일하게 분포되지 않았기 때문에 John 데이터를 제외한 모든 데이터가 3번 노드 담당이 된다.
Adaptive Consistent Hash
위 문제를 해결하기 위해서, 가상 버킷(가상 노드) vBucket(vNode)의 개념이 추가된다.
버킷이 추가되거나 삭제되어도, 균등하게 분산될 수 있도록 버킷의 분신들(vBucket)을 곳곳에 배치하는 것이다.
아래는 Consistent Hash의 문제점을 다룬 예제에 vNode를 추가한 예제이다. 곳곳에 가상 노드를 배치함으로서 보다 균일하게 배치되었다.
여기서 1번 노드를 삭제한다면, Consistent Hash에서 리밸런싱했을 때보다 균등하게 리밸런싱 되는 것을 볼 수 있다.
이러한 가상 노드/버킷의 특징을 이용해서, 각 Bucket마다 Bucket과 vBucket의 비율을 조절하여 각 Bucket이 서로 다른 비율 (Weight)로 Key를 갖도록 만들 수 있다.
Hash Ring의 대부분의 값 사이에 vBucket이 위치하도록 vBucket을 많이 생성해 둔다면, Hashing 시간 복잡도는 O(1)이 된다.
Jump Consistent Hash
vBucket/vNode를 활용한 Adaptive Consistent Hash는 좋은 방법이지만, 그 만큼 곳곳에 가상 노드를 배치하기에 메모리 공간을 차지한다.
Jump Consistent Hash는 가상 노드의 개념이 없는, 사용하는 메모리 량을 줄일 수 있는 방법이다.
주어진 데이터는 -1부터 시작해서, 알고리즘에 따라서 버킷 갯수와 동일할 때까지 혹은 최초로 초과할때까지 Jump한다.
그리고, 버킷 갯수를 넘지 않는 선에서 마지막으로 Jump를 수행한 위치가 키값을 배치될 버킷 값으로 정한다.
아래 예제에서는 총 7개의 버킷에, 총 4개의 데이터를 분산 배치하였다.
Freddie는 -1 → 3 → 8 으로 Jump 했기 때문에, 마지막으로 Jump한 3번 버킷에 배치된다.
John은 -1 → 1 → 4 → 7 으로 Jump 했기 때문에, 마지막으로 Jump한 7번 버킷에 배치된다.
Jem은 -1 → 4 → 5 → 7 으로 Jump 했기 때문에, 마지막으로 Jump한 7번 버킷에 배치된다.
Africa는 -1 → 2 → 6 → 8 으로 Jump 했기 때문에, 마지막으로 Jump한 6번 버킷에 배치된다.
Jump하는 방법을 통해, vBucket같은 추가적인 메모리 없이 빠르게 각 데이터가 버킷에 균등하게 배치되었다.
버킷이 삭제되었을 때도 균등하게 배치되는지 아래 예제에서 확인해보자.
Freddie는 -1 → 3 → 8 으로 Jump 했기 때문에, 마지막으로 Jump한 3번 버킷에 배치된다.
John은 -1 → 1 → 4 → 7 으로 Jump 했기 때문에, 마지막으로 Jump한 4번 버킷에 배치된다.
Jem은 -1 → 4 → 5 → 7 으로 Jump 했기 때문에, 마지막으로 Jump한 5번 버킷에 배치된다.
Africa는 -1 → 2 → 6 으로 Jump 했기 때문에, 마지막으로 Jump한 6번 버킷에 배치된다.
버킷이 삭제되었을 때도, vBucket 없어 더 적은 메모리를 쓰면서도, 균등하게, 빠르게 배치되었다.
Jump Consistent Hashing은
각 Key의 모든 Jump 과정을 저장할 필요 없이, Bucket 크기를 넘기 기전의 위치만 기억하면 되기 때문에,
Ring Consistent Hashing과 같이 vBucket의 개념이 필요 없으며,
Ring Consistent Hashing에 비해서 적은 Memory 공간을 이용한다.
단, Ring Consistent Hashing와 같이 각 Bucket이 서로 다른 비율로 Key를 갖도록 만들수는 없다.
Hashing 시간 복잡도는 O(ln(n))이다.
구현 코드
Jump Consistent Hashing를 발표한 논문에서는 아래와 같은 C 코드로 작성되었다.
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;
}(Python이 더 익숙해서) Python으로 구현된 코드는 아래와 같다.
def py_hash(key, num_buckets):
"""Generate a number in the range [0, num_buckets).
Args:
key (int): The key to hash.
num_buckets (int): Number of buckets to use.
Returns:
The bucket number `key` computes to.
Raises:
ValueError: If `num_buckets` is not a positive number.
"""
b, j = -1, 0.0
if num_buckets < 1:
raise ValueError(
f"'num_buckets' must be a positive number, got {num_buckets}"
)
while j < num_buckets:
b = int(j)
key = ((key * int(2862933555777941757)) + 1) & 0xFFFFFFFFFFFFFFFF
j = float(b + 1) * (float(1 << 31) / float((key >> 33) + 1))
return int(b)변수 b는 해시 계산된 버킷 번호가 된다. 변수 j는 버킷 갯수까지만 jump를 수행하기 위한 제어용 변수이다.
전반적인 플로우는 아래와 같다.
- 점프 한뒤에
b에 할당한다. key를 Jump Consistent Hash 알고리즘에 따라 해싱한다.2862933555777941757은 내부적인 상수이다.key를 비트 연산을 통해 적절한 크기로 조정한다.- 조정된 Key와 b값에 기반하여 Jump할 값을 계산하여
j에 할당한다.
굉장히 간단하게 해싱 알고리즘을 구현하였다.
Reference
python-jump-consistent-hash/src/jump/init.py at master · lithammer/python-jump-consistent-hash
Consistent hashing explained | Ably Blog: Data in Motion
킴코더 / 자주 언급되는 로드 밸런싱 알고리즘 6가지 | 커리어리
'Java & Spring' 카테고리의 다른 글
| 변수 동기화 하기 - atomic, volatile, synchronized (0) | 2023.07.04 |
|---|---|
| Concurrent Hash Map과 HashMap, HashTable, Synchronized Hash Map (1) | 2023.05.30 |
| Interceptor (0) | 2023.05.23 |
| Filter (0) | 2023.05.16 |
| 이펙티브 자바 - 아이템 21: 인터페이스는 구현하는 쪽을 생각해 설계하라 (0) | 2023.05.08 |