가상 면접 사례로 배우는 대규모 시스템 설계 기초 Study [5장] 안정 해시 설계
Contents
Note
팀 내에서 진행하는 Study 정리 입니다.
함께 논의하고 싶은 주제
- 챕터가 점점 어려워 집니다.
- 해시 키가 저장되는 서버를 탐색할 때 왜 시계방향으로 탐색을 했을지 문득 궁금해지네요?
- 성능과 메모리 두 개의 밸런스를 타협하는 결정은 어려워 보입니다.
- 이번 챕터의 내용을 떠나서 웹 서비스에 대한 튜닝 노하우 같은 게 있으신가요? (요청 제한 등등 인프라적으로 모든 것들)
- 서비스의 메모리 설정 등등 어떠한 근거를 통해 설정하고 어떤 데이터를 참고하는지요? (예를 들어 부하 테스트를 통해 예측 한다 등)
- 핫스팟 키 문제를 어떻게 해결하는지 자세한 설명이 있었으면 좋았었을 것 같습니다…
- 특정 유명인의 데이터를 예로 들었는데 만약 인덱스 키가 아닌 데이터 때문에 접근 빈도수가 높아지면 키를 재 배치 할 수 있을지?
1. 해시 키 재배치rehash 문제
N 개의 캐시 서버의 부하를 균등하게 나누는 보편적인 방법은 특정한 키가 보관된 서버를 알아내기 위해 나머지 연산을 통해 인덱스 값을 가져온다.
|
|
- 서버 풀
server pool의 크기가 고정되어 있을 때와 데이터 분포가 균등할 때 잘 동작 - 서버가 추가되거나 삭제시 문제가 발생
- 서버 풀의 크기가 변경되어 나머지 연산을 적용하여 계산한 서버 인덱스 값을 달라지게 됨 -> 캐시 미스 발생
2. 안정 해시consistent hash
- 해시 테이블 크기가 조정될 때 k(키의 개수)/n(슬롯의 개수)개의 키만 재배치 하는 기술
- 대부분의 전통적인 해시 테이블은 슬롯의 수가 바뀌면 대부분의 키를 재배치
2.1 해시 공간과 해시 링
- 해시 공간
hash space을 양쪽을 구부려 접으면 해시링hash ring이 만들어진다.
2.2 동작 원리
- 해시 서버
해시링 위에 서버 IP 이나 이름을 대응 시킬 수 있다. - 해시 키
해시 서버에 대한 캐시 키를 해시 링 위의 어느 지점에 배치 할 수 있다. - 서버 조회
어떤 키가 저장되는 서버는 해딩 키의 위치로부터 시계 방향으로 링을 탐색해 나가면서 첫 번째 만나는 서버에 저장하게 된다. - 서버 추가
서버를 추가하더라도 키 가운데 일부만 재배치 하면 된다. - 서버 삭제
하나의 서버가 제거되면 키 가운데 일부만 재 배치 된다.
2.3 기본 구현법의 두 가지 문제
- 서버와 키를 균등 분포
uniform distribution해시 함수를 사용해 해시 링에 배치 - 키의 위치를 링을 시계 방향으로 탐색하다 만나는 최초의 서버가 키가 저장될 서버
- 서버가 추가되거나 삭제되는 상황을 감안한 파티션
partition의 크기를 균등하게 유지가 불가능하다.
- 파티션 : 인접한 서버 사이의 해시 공간
- 어떤 서버는 작은 해시 공간을 할당받고 어떤 서버는 굉장히 큰 해시 공간을 할당
- 키의 균등 분포
uniform distribution달성하기 어렵다
2.4 해결 방안 - 가상노드
- 실제 노드 또는 서버를 가리키는 노드로 하나의 서버는 링 위에 여러개의 가상 노드를 갖을 수 있다.
- 각 서버는 하나가 아닌 여러 개의 파티 션을 관리해야한다.
- 가상 노드 수가 증가하면 키의 분포는 점점 더 균등해진다.
- 표준 편차
standard deviation가 작아저 데이터가 고르게 분포된다. - 가상 노드의 개수를 늘리면 가상 노드의 데이터를 저장할 공간이 더 많이 필요하다 - 타협적 결정이 필요
3. 마무리
3.1 안정 해시의 이점
- 서버가 추가되거나 삭제 될 때 재배치되는 키의 수가 최소화
- 데이터가 균등하게 분포되므로 수평적 구조 확작성을 달성하기 쉽다.
- 핫스팟
hotspot키 문제를 줄인다. 특정한 샤드shard접근이 지나치게 빈번하면 서버 과부하 문제가 생길 수 있다.
3.2 안정 해시를 사용하는 기술
- Amazon Dynamo DB의 파티셔닝 관련 컴포넌트
- Apach Cassandra 클러스터에서의 데이터 파티셔닝
- 디스코드의 채팅 어플리케이션
- 아카마이 CDN
- 매그레프 네트워크 부하 분산기