가상 면접 사례로 배우는 대규모 시스템 설계 기초 - 5장

🔖 5장 : 안정 해시 설계

읽은 날짜 : 2024.08.26

지은이 : 알렉스 쉬

출판사 : 인사이트

 

기억하고 싶은 내용

해시 키 재배치(rehash) 문제

• N개의 캐시 서버가 있을 때 서버들에 부하를 균등하게 나누는 일반적인 방법은
  • serverIndex = hash(key) % N
  • 특정 키가 보관된 서버의 인덱스를 계산하는 방법
• 이 방법은 서버 풀의 크기가 고정되어 있을 때와 데이터 분포가 균등할 때는 잘 동작한다.
• 그러나 서버가 추가되거나 기존 서버가 삭제되는 경우(즉, N 값이 바뀜), 서버 인덱스 값이 바뀌면서 대규모 캐시 미스(cache miss)가 발생한다.

 

안정 해시(consistent hash)

• 해시 테이블 크기가 조정될 때 거의 대부분의 키를 재배치하는 전통적인 방식과 달리, 안정 해시는 평균적으로 k/n개의 키만 재배치하는 해시 기술이다. (k는 키의 개수, n은 슬롯의 개수)

해시 공간과 해시 링

• x0 ~ xn 범위(해시 함수의 출력 범위)의 해시 공간의 양쪽을 구부려 접으면 해시 링(hash ring)이 된다.
• 서버와 키를 균등 분포 해시 함수를 사용해서 해시 링에 배치한다.
• 키가 저장될 서버는 키의 위치에서 링을 시계 방향으로 탐색하다 만나는 최초의 서버이다.

서버 조회/추가/삭제

• 해시 링에서 어떤 키가 저장된 서버를 찾는 방법은, 해당 키의 위치로부터 시계 방향으로 링을 탐색해서 만나는 첫번째 서버이다.
• 서버를 추가 또는 삭제하더라도 일부 키만 재배치 된다. 추가 또는 삭제된 서버의 반시계 방향에 있는 최초 서버까지의 키가 재배치 된다.

 안정 해시 알고리즘 문제점 두 가지

• 서버를 추가, 삭제하게 되면 파티션(인접 서버 사이의 해시 공간) 크기를 균등하게 유지하는 것이 불가능하다.
• 키의 균등 분포를 달성하기 어렵다.

가상 노드(virtual node)

• 실제 노드 또는 서버를 가리키는 노드. 하나의 서버는 링 위에 여러 개의 가상 노드를 가질 수 있다.
• 이로써 하나의 서버가 여러 개의 파티션을 관리하게 된다.
• 키의 위치로부터 시계 방향으로 링을 탐색하다 만나는 최초의 가상 노드가 해당 키가 저장될 서버가 된다.
• 가상 노드의 개수를 늘리면 키의 분포가 점점 더 균등해진다. 그러나 가상 노드 데이터를 저장할 공간에 대한 tradeoff가 발생한다.

 

안정 해시의 이점

• 서버 추가/삭제 시 재배치 되는 키의 수 최소화
• 데이터의 균등 분포로 수평적 규모 확장 달성하기 쉬움
• 핫스팟(hotspot) 키 문제를 줄임

 

오늘 읽은 소감

1장의 데이터베이스 규모 확장 부분에서 언급된 데이터 재 샤딩과 안정 해시 기법을 연관지어 정리해보자면, 다음과 같습니다.

• 샤드 소진(shard exhaustion) 현상이 발생하면 샤드 키를 계산하는 함수를 변경하고 데이터를 재배치 해야 합니다(재샤딩).
• 이때 안정 해시 기법을 활용하면 데이터 분포의 균형을 유지함과 동시에 재배치 되는 데이터를 최소하면서 재샤딩을 효율적으로 할 수 있습니다.

 

궁금한 내용 & 잘 이해되지 않는 내용

캐시 미스(cache miss)

• 요청한 데이터가 캐시에서 발견되면 캐시 히트(cache hit), 발견되지 않으면 캐시 미스(cache miss)라고 합니다.
• 캐시 미스의 유형
  • Cold Miss : 데이터에 처음 액세스할 때 발생하는 캐시 미스
  • Capacity Miss : 캐시의 크기가 충분하지 않아서 발생하는 캐시 미스
  • Conflict Miss : 캐시가 특정 알고리즘에 따라 데이터를 저장할 위치를 결정할 때, 서로 다른 데이터가 동일한 캐시 위치에 매핑될 때 발생하는 캐시 미스

참고

Cache Miss