1. 수평적 규모 확장에서 고려할 점
📌 수평적 규모 확장 (Horizontal Scaling, Scale-Out)
수평적 규모 확장성을 달성하기 위해서는 요청 또는 데이터를 서버에 균등하게 나눌 수 있어야 한다.
- 클라이언트의 요청이 쏟아질 때, 일부 서버에 요청이 몰리지 않게 균등하게 분배해야 한다.
- 데이터들이 균등하게 서버에 배치되어, 한 곳에 부하가 걸리지 않도록 유지해야 한다.
따라서 이번 논제는 "서버의 규모 확장성을 고려한 해시키 설계 방법"이 되겠다.
(수직/수평적 규모 확장의 개념은 1장에서 다뤘음)
📌 이상적인 환경에서 key 설계 방법
N개의 캐시 서버가 있을 때, 가장 쉽게 키를 설계하는 방법은 serverIndex를 다음과 같이 설정하는 것이다.
- serverIndex = hash(key) % N
| key | hash(key) | hash(key) % 4 |
| key0 | 18358617 | 1 |
| key1 | 26143584 | 0 |
| key2 | 18131146 | 2 |
| key3 | 35863496 | 0 |
| key4 | 34085809 | 1 |
| key5 | 27581703 | 3 |
| key6 | 38164978 | 2 |
| key7 | 22530351 | 3 |
- 서버 풀(server pool)의 크기가 고정 & 데이터 분포가 균등할 때는 가능
- 서버가 추가 or 삭제되거나, hash(key) % N의 값이 고르지 않을 경우 문제가 생긴다.
📌 해시 키 재배치(rehash) 문제
서버1이 장애를 일으켜 중단된 상황을 가정해보자.
그럼 N = 3이 되면서, 결과가 달라진다.
| key | hash(key) | hash(key) % 3 |
| key0 | 18358617 | 0 |
| key1 | 26143584 | 0 |
| key2 | 18131146 | 1 |
| key3 | 35863496 | 2 |
| key4 | 34085809 | 1 |
| key5 | 27581703 | 0 |
| key6 | 38164978 | 1 |
| key7 | 22530351 | 0 |
- hash(key) % N의 결과가 달라졌을 뿐, 실제 데이터가 동기화되지 않은 상태라면, 클라이언트는 원하는 데이터를 얻지 못할 수도 있다. → 대규모 캐시 미스
2. 일관성 있는 해시
📌 Consistent hashing
🙋♂️ 책에서는 Consistent를 "안정"이라고 번역했는데, 직관적으로 보려고 "일관성 있는"이라고 번역했습니다.
- 일관성 있는 해시: hash table 크기가 조정(resize)될 때, 평균적으로 오직 k/n개의 키만 재배치하는 해싱 기술. (위키에서 n, m이라고 설명하나, 책을 이해하기 쉽게 k, n으로 대응하여 작성)
- k: 키의 개수, n: 슬롯(slot)의 개수
- 쉽게 말해, 서버 한 대당 1,000명을 처리하고 있는 환경에서 장애가 나면, 이 1,000명만 서버를 재분배하고 나머지는 그대로 유지할 수 있다는 말이 된다.
- 전통적인 해시 테이블은 슬롯 수가 바뀌면, 대부분 키를 재배치한다.
- 일관성 있는 해시는 일부 샤드가 충돌하거나 사용할 수 없게 되어도, 캐시 키를 샤드 전체에 균등하게 분배할 수 있다.
📌 해시 공간과 해시 링
- 가정
- 해시 함수 f: SHA-1
- f의 출력 값 범위: x0 ~ xn (SHA-1의 경우, 해시 공간의 범위는 0 ~ 2^(160) - 1)
- 해시 공간 양쪽 끝을 접하게 만들면, 해시 링(hash ring)이 만들어진다.
📌 해시 서버
- 서버 IP, 이름 등의 정보를 이용해 각 서버의 hash 값을 구한 후, 해시 링에 배치시킨다.
🤔 서버 IP...를 사용한다구요?
일관성 있는 해시에서 서버 해시 값으로는 어떤 값을 쓸 수 있을까?
가장 쉽게 떠올릴 수 있는 건, IP 주소, port, 서버 이름 정도가 될 것이다.
그런데 AWS ElastiCache 공식 문서에도 나와있듯이, non-VPC 환경에선 캐시 노드가 복구될 때, DNS 이름은 유지하지만 IP 주소가 변경될 수 있다고 이야기한다.
이 말은 즉, 해시 링에서 노드의 위치가 변경될 수 있음을 의미하며, 이러한 동작이 어떤 장애를 발생시킬 지 불확실해지지 않을까?
그래도 non-VPC 환경을 사용하는 legacy infra가 아니라면 상관은 없겠지만, 그래도 도메인 이름을 사용하는 것이 안전할 것 같다.
📌 해시 키
- 여기서 사용하는 해시 함수는 "해시 키 재배치 문제"에 언급된 함수 F와 다르다.
- 일관성 있는 해시 알고리즘에선 서버와 해시 키를 균등 분포 해시 함수(uniform distribution hash function)를 사용해, 해시 링에 배치하게 한다.
✒️ Uniform Distribution Hash Function
뭔가..명확한 정의를 못 찾겠어서 추론을 했다.
wiki의 Uniformity에 대한 정의는 다음과 같다.
• 좋은 해시 함수는 예상된 입력을 출력 범위에 가능한 고르게 매핑해야 한다.
• 즉, 출력 범위의 모든 해시 값이 거의 동일한 확률로 생성되어야 한다.
• 값이 균일하게 분포되는 것이 기준이지, 무작위적이어야 한다는 말을 의미하진 않는다. (보통 무작위화 함수는 큰 수의 법칙에 의해 일반적으로 좋은 해시 함수로 선택되겠지만, 그 역이 참일 이유는 없다는 뜻이다.)
즉 균등 분포 해시 함수란, 위의 조건을 최대한 만족시킬 수 있는 해시 함수를 이야기 한다.
(당연히 완벽한 균등 분포는 불가능하지만, 산출량 분포가 왜곡되어서는 안 된다.)
일관성 있는 해시 알고리즘이 "hash table이 재조정될 때, 평균적으로 k/n개의 키만 재배치"될 수 있는 원리는 균등 분포 해시 함수가 서버와 키를 해시링에 고르게 분포시킬 수 있다는 가정으로 기반한다.
(이걸 이해해야, 아래 `(3) 일관성 있는 해시 메커니즘` 예시가 억지처럼 보이지 않는다.)
3. 일관성 있는 해시 메커니즘
📌 서버 조회
- 키가 저장되는 서버: 키의 위치로부터 시계 방향 탐색할 때, 첫 번째로 만나는 서버
📌 서버 추가
- 서버4가 추가되면, k0 위치에서 시계 방향 탐색 시 처음으로 만나는 서버는 서버4가 된다.
- key0만 재배치되고, key1,2,3은 같은 서버에 유지된다.
📌 서버 제거
- 하나의 서버가 갑자기 죽어도, 서버1에 배치되었던 key1만 재배치된다.
4. 일관성 있는 해시 구현
📌 기본 구현법의 두 가지 문제점
일관성 있는 해시 알고리즘의 절차는 매우 단순하다.
- 균등 분포 해시 함수를 사용해, 서버와 키를 해시 링에 고르게 배치한다.
- 키의 위치에서 링을 시계 방향으로 탐색하다 만나는 최초의 서버가 곧 키가 저장될 장소다.
그러나, 여기엔 두 가지 문제가 존재한다.
1️⃣ 키의 균등 분포를 달성하기 어렵다.
- 일관성 있는 해시 알고리즘의 기반은 해시 알고리즘이 균등 분포를 보장한다는 전제가 필요하다.
- 그러나 키의 균등 분포 달성에 실패하면, 대부분의 키가 특정 서버로 몰리게 될 수 있다.
2️⃣ 파티션(partition)의 크기를 균등하게 유지하는 게 불가능하다.
- 여기서 파티션(partition) 인접 서버 사이의 해시 공간을 의미한다.
- 인접 서버들 간의 간격이 고르지 않다면, 일부 서버의 파티션이 매우 커질 수 있다.
위 두 문제를 해결하기 위해서는 복제(replica)라고도 불리는 가상 노드(virtual node)를 사용해야 한다.
📌 가상 노드(virtual node)
- 기본 전략: 실제 노드를 가리키는 가상 노드를 여러 개 배치함으로써, 표준 분포(standard deviation)를 작게 만들어 데이터 균등화를 실현한다.
- 가상 노드 개수가 많을 수록, 키의 분포는 점점 더 균등해진다. (Tom White - Consistent Hasing의 그래프를 확인해보면, vnode 100~200개에서 표준 분포는 5~10% 사이다.)
- 하지만 그만큼 가상 노드 데이터 저장 공간이 더 필요하다. → trade-off가 요구된다.
📌 일관성 있는 해시의 이점
- 서버 추가/삭제 시, 재배치되는 키의 수가 최소화된다.
- 데이터가 보다 균등하게 분포되므로, 수평적 규모 확장성 달성에 용이하다.
- 핫스팟(hotspot) 키 문제를 줄일 수 있다.
🤔 근데 해시 링 정보는 누가 가지고 있는 건데?
수평적 확장의 대상은 물리 서버(노드) 그 자체일 수도 있고, 논리적으로 서로 다른 노드(또는 프로세스)일 수도 있다.
두 가지 경우 모두 일관성 있는 해시를 구현한다고 쳤을 때, 결국 누군가는 해시 링 정보를 가지고, 탐색을 위한 로직을 수행해야만 한다.
그럼 이걸 어디서, 누가 수행하는 건데?
우선 대부분의 수평적 샤딩이 적용된 캐시 시스템(Redis, Cassandra, Memcached 등)은 내부적으로 클러스터에서 파티셔닝을 처리하는 듯하다.
분산 스토리지 시스템의 경우엔 중앙 관리 노드(Coordinator) 역할을 수행할 시스템이 필요하지 않을까 싶다.
즉, 요청에 대해 해시 알고리즘을 적용하고, 적절한 노드로 라우팅하는 Proxy 서버가 이 역할을 수행해야 한다고 추측한다.