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

수평적 규모 확장성을 달성하기 위해서는 요청 or 데이터를 서버에 균등하게 나눠야한다.

 

안정해시는 이 목표를 달성하기 위해 보편적으로 사용하는 기술인데, 이 해시기술이 어떤 문제를 해결할 수 있는지 부터 알아본다.

해시 키 재배치(rehash) 문제

N개의 캐시서버가 있다고 할 때, 이 서버들에 부하를 균등하게 나누는 보편적 방법은 아래의 해시 함수를 사용하는 것이다.

serverIndex = hash(key) % N (N은 서버의 개수이다)

 

4대의 서버를 사용한다면 해시 값이 18358617은 1(서버인덱스)이다. 이런식으로 나머지연산(%)을 이용해서 각 서버에 저장한다.

 

그러나, 해당 방법은 서버가 추가되거나 삭제될 때 문제가 발생한다.

 

만약 0번 서버가 장애가 발생하여, 위 해시함수를 이용해서 해시를 재배치을 하는데, 장애가 발생한 서버 인덱스도 포함될 것이다. 해시 값이 18358617은 0(서버인덱스)로 재배치되고, 클라이언트가 18358617 값을 찾는데, 장애가 발생한 0번으로 접속하게 될 것이고, 캐시미스가 발생한다.

 

이러한 문제를 해결하기 위해 안정 해시라는 개념이 나온다.

 

안정해시

안정 해시는 해시 테이블 크기가 조정될 때, 평균적으로 k/n개의 키만 재배치 하는 해시 기술이다. 여기서 k는 키의 개수이고, n은 슬롯의 개수이다.

해시링

해당 기술은 그림을 참고하면 이해가 더 잘된다.

 

아래 예제에서는 해시 함수로는 SHA-1을 사용하고 있다.

 

SHA (Secure Hash Algorithm, 안전한 해시 알고리즘) 함수들은 암호학적 해시 함수들의 모음이다.

SHA 함수 INPUT에 The quick brown fox jumps over the lazy dog 을 넣으면 OUTPUT으로 2fd4e1c67a2d28fced849ee1bb76e7391b93eb12 값이 나온다.

해당 값을 이용하여 해시 링에 올려준다.

자세한 내용은 아래 블로그 참고
https://velog.io/@ejjjang0414/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D-SHA-1-%EC%9D%B4%EB%9E%80-%EB%AC%B4%EC%97%87%EC%9D%B8%EA%B0%80

 

해시 서버

해시 키

• 각 키들은 해시 링 위 어느 지점에 배치할 수 있다.

해시 키

 

서버 조회

• 해당 키의 위치로부터 시계 방향으로 링을 탐색해나가다 만나는 첫번 째 서버다.

서버조회

 

서버 추가

• 안정해시에서는 서버가 추가되더라도, 키 운데 일부만 재배치 하면 가능

서버추가

 

서버 제거

• 위와 마찬가지로 안정 해시에서는 서버를 제거하더라고, 키 일부만 재배치가 된다

서버제거

 

기본 구현법의 2가지 문제

1. 서버가 추가되거나, 삭제되는 상황을 감안하면 파티션의 크기를 균등하게 유지하는 것이 불가능하다.
2. 키의 균등 분포를 달성하기 어렵다. 즉 1개의 서버에 몰릴 가능성이 있다.

가상노드

위 2가지 문제점은 가상노드(머신)을 추가하면 된다. 머신과 머신사의에 가상노드를 만들어, 파티션을 분할하고, 균등분포를 달성한다.

 

예를 들어, 조회할 때, 시계방향으로 탐색하다 만나는 최초의 가상노드다.

결론

• 서버가 추가되거나 삭제 될 때 재배치되는 키의 수가 최소화 된다.
• 데이터가 균등하게 분포된다.
• 핫스팟 키 문제를 줄인다. 특정 샤드에 대한 접근으로 인한 서버 과부하 문제를 막는다.(유명인 문제)