해시 키 재배치 rehash 문제
- 안정 해시 설계가 풀 수 있는 문제.
- 해시 알고리즘으로 배치된 키를 재배치해야 할 때, 기존의 균등했던 분포가 깨지는 문제
- 예) 해시 알고리즘으로 캐시 서버 4대에 데이터를 분산해놓은 상태 → 서버 1대가 죽음 → 이 때 일반적인 해싱을 사용하면 균등한 분포가 깨지는 경우 → 캐시 클라이언트가 갖고 있던 캐시 서버 정보는 바뀌지 않기 때문에 대규모 캐시 미스가 발생한다.
- 예) 해시 알고리즘으로 캐시 서버 4대에 데이터를 분산해놓은 상태 → 서버 1대가 죽음 → 이 때 일반적인 해싱을 사용하면 균등한 분포가 깨지는 경우 → 캐시 클라이언트가 갖고 있던 캐시 서버 정보는 바뀌지 않기 때문에 대규모 캐시 미스가 발생한다.
안정 해시 consistent hash 설계 알고리즘
- 해시 키 재배치가 필요할 때, 최소한의 키만 재배치할 수 있는 알고리즘.
일관된 해싱 (https://ko.wikipedia.org/wiki/일관된_해싱)
(Consistent hashing)은 웹서버의 개수가 변동하는 가운데 요청을 분산하는 방법을 말한다. 해시테이블의 크기가 변할 때, 평균적으로 K/n의 키만 재매핑되면 된다. 즉 노드나 슬롯의 개수가 바뀔 때, 노드의 추가나 삭제를 할 때, 오직 K/n의 아이템만 다시 섞이면 되는 것이다.
- 캐시 서버 예시에서
K는 캐시 서버에 저장되는 키의 총 개수,n은 캐시 서버(노드)의 개수를 의미한다.
키 배치 방법
- 해시 키가 들어갈 1차원 공간을 원형으로 연결한다. 즉, 끝과 끝이 만나는 원이라고 생각한다.
- 균등 분포 해시 함수를 사용해 서버를 배치한다. 위 그림에서는 S1, S2, S3, S4 총 4개의 서버를 배치했다.
- 균등 분포 해시 함수를 사용해 키를 배치한다. 위 그림에서는 K1 ~ K8까지 총 8개를 배치했다.
- 키 K가 저장될 곳은 K로부터 시계방향으로 돌았을 때 가장 처음 만나는 서버다.
- 예를 들어, 위 그림에서 K1이 저장될 곳은 서버 S2다.
서버가 추가되는 경우
- 만약 S4와 S1 사이에 들어가는 서버 S5가 추가되었다고 하면, 재배치가 필요한 키는 S4와 S5 사이에 위치하는 키밖에 없다. 그림에서는 K7.
- 👍: 나머지 키는 그대로 있으면 된다.
- 👎: 더이상 파티션의 크기가 균일하지 않다.
서버가 제거되는 경우
- 만약 서버 S4가 제거되었다고 하면, 재배치가 필요한 키는 기존에 S4에 저장되고 있었으나 더이상 그렇지 않은 키이다. 즉, S4와 S3에 있었던 키만 이동하면 된다.
- 👍: 나머지 키는 그대로 있으면 된다.
- 👎: 더이상 파티션의 크기가 균일하지 않다.
문제점과 해결책
문제점 2가지
- 서버가 추가, 제거 되는 경우 파티션의 크기가 일정하게 유지되지 않는다.
- 키의 균등 분포를 달성할 수 없는 경우가 생긴다.
- 링 위에서, 특정 서버 사이에 키가 몰리는 경우.
해결책: 가상 노드
- 실제 사용할 서버보다
Sn의 개수를 더 많이 만든다. 즉, 링 위에 실제로 사용할 서버와 그 서버를 의미하는 가상의 서버를 함께 올려둔다. - 가상 노드의 개수가 많아질수록 키의 분포는 점점 더 균등해진다. = 링을 쪼개는 단위가 점점 작아지기 때문에 파티션 분할이 더 균등해진다.
trade-off: 성능과 가상 노드 개수 사이
- 단, 가상 노드를 쓴다고 해서 무조건 좋은 점만 있는건 아니다. 어느 방법이나 그렇듯 trade-off가 존재한다.
vnode는 상당한 운영상의 이점을 제공하지만 주어진 노드에 할당된 vnode의 수가 클러스터 전체의 운영에 영향을 미칠 수 있다는 점을 명심하는 것이 중요합니다. 예를 들어 vnode의 수가 증가하면 복구 주기 동안 실행해야 하는 복구의 수도 증가하므로 전체 클러스터 복구 시간이 늘어납니다. 또한 vnode 토큰 범위의 수가 증가함에 따라 토큰 범위에 걸쳐 있는 DSE 검색과 같은 기능의 성능이 저하될 수 있습니다. https://docs.datastax.com/eol/en/dse/6.7/dse-arch/datastax_enterprise/dbArch/archDataDistributeVnodesUsing.html
그림에서 위쪽은 가상 노드를 사용하지 않은 경우, 아래쪽은 가상 노드를 사용한 경우다. 만약 노드 1이 죽었다면, 가상 노드가 없을 때는 A, F, E 3개만 복구하면 되지만 가상 노드로 잘게 쪼갠 상태라면 각 가상 노드별로 데이터를 복구하는 시간이 추가 되어 좀 더 오래 걸릴 것이다. 또한 검색 등의 연산을 할 때에도 영향을 미칠 수 있다고 한다.
즉, 너무 잘게 쪼개면 오히려 성능에 영향을 미칠 수 있다.
실제 사용 사례
- 수평적 규모 확장을 달성하기 쉽게 만든다.
- 핫스팟 키 문제가 발생할 가능성을 줄여준다.
- 예) 트위터에서 유명인의 데이터가 전부 같은 샤드에 몰리는 상황 → 안정 해시를 사용하면 데이터를 좀 더 균등하게 분배하기 때문에 그런 가능성이 줄어든다.
Discord 사례
- 디스코드 채널 안에 ‘길드’ 시스템이 있다. 사용자가 디스코드를 켜면 길드의 publisher를 subscribe하는 pub/sub 구조로 되어있었다.
- 한 채널의 동접자 수가 3만명에 이르게 되자, 길드 시스템의 pub/sub 구조가 제대로 동작하지 않게 되었다. 원인은 디스코드가 인프라로 사용 중이던 Erlang의 속도. pub/sub을 비롯한 여러 프로세스의 처리 비용이 생각보다 높았다.
- Erlang 프로세스들은 싱글 스레드를 사용하기 때문에 문제를 해결하기 위해서는 샤딩을 하는 것이 최선이었다. 이 때 다른 여러 알고리즘과 함께, 안정 해시 방식을 사용했다.
