대규모 시스템 설계 기초 - 5장

가상 면전 사례를 읽다보면 백엔드를 깊이있게 이해하고 있다는 느낌이 든다. 느낌만...? 

바로 5장을 보기 시작해보자. 5장은 안정 해시 설계에 대한 퀘스천이다. 안정 해시란 키워드에 대한 정의부터 시작해보자. 

주어진 입력에 대해 항상 동일한 해시 값을 생성하는 해시 함수를 의미한다. 파일이 변경되어 있지 않는 다면 항상 동일한 해시 값을 반환하여 파일이 변하지 않았음을 의미한다. 여기서 몇가지 고려해볼것이 있다. 바로 gogo ~ 

해시 키 재배치 문제

N개의 캐시 서버에 부하를 균등하게 나누는 방법은 해시 함수를 사용하는 것이다. 예를 들어서 hah(key0) % 4 = 1 이면 서버 1에 접속하는 것이다. 서버 풀 크기가 고정되어 있을때만 효과가 있는 방법이다. 해시 값은 변하지 않지만 키가 줄어들어 결과적으로 접근해야 하는 서버가 달라진다.  

안정해시

해시 테이블 (서버) 크기가 조정 될 때 평균적으로 k/n 개의 키만 재배치되는 해시 기술이다. 하지만, n이 줄어들거나 커질 때 k/n으로 나오는 인덱스 값이 항상 동일하게 보장되지 않는다. 당연히 n이 변하게 되면 해시 함수에서 키들이 새로운 n에 맞춰서 재배치되어야 한다. 재배치 과정은 해시 테이블의 로드 팩터에 의해 테이블에 저장된 키의 수 대비 테이블의 크기 비율을 조정하고 해시 충돌을 최소화 하여 성능을 유지하는데 <- 여기서는 안다룸, 

여기서는 크기 조정시 재배치되는 키의 수를 최소화 하도록 설계할 수 있는 컨시스턴스 해싱에 대해 알아본다. 

해시 공간과 해시 링

해시 함수로 SHA-1을 사용하고 있고 출력 값 범위가 x0, x1, x2,x3, ... xn이라고 할때 SHA-1 의 해시 공간 범위를 구성하고 그 안에 값을 구성한다. 해시 공간은 해시 함수가 가능한 모든 출력 값을 포함하는 범위이다. 즉, 해시 공간의 크기는 해시 함수에 의해 생성될 수 있는 유니크한 해시 값들의 총 수를 결정한다. 

해시 링은 데이터를 테이블에 저장하고 검색하는 과정을 의미한다. 해시 링은 노드들이 서로 물리적으로 묶여있는것만을 뜻하는것은 아니다. 해시 공간을 원형의 링으로 가정하여 이 위에 노드를 분산시키는것을 의미한다. 

특히, 묶는다라는 표현보다는 노드들이 연결되어 있다는것이 아닌 노드가 링 상에 할당된 데이터의 범위를 관리하는것을 의미한다. 

여기서 해싱은 컨시스턴트 해싱을 의미한다. 

• 데이터는 해시 함수를 통해 해시링 상의 지점에 매핑된다. 
• 해당 지점을 기준으로 가장 가까운 서버에 저장된다. 
• 서버 자체의 추가나 제거가 이루어져도 전체 해시 공간에 미치는 영향을 최소화 한다. 

https://binux.tistory.com/119

해시 서버 추가

마찬가지로 원형의 해시링이라고 가정하고 서버 4가 해시링에 추가 될 때 해시 함수에 의해 특정 위치 배치가 될것이다. 이때, 서버 4의 해시 값이 키 0의 해시 값 바로 뒤에 위치한다고 가정해보자. 

컨시스턴스 해싱은 해시링 상에서 시계 방향으로 데이터를 할당하게 된다. 키 값은 자신의 해시 값보다 크거나 같은 해시 값을 가진 가장 가까운 서버에 할당된다. 즉, 키 0은 서버 4에 할당된다. 최소 재배치 원칙에 따라서 서버 4의 추가는 키 0만 재배치 되어 서버 4로 이동하면 시스템의 균형을 맞출 수 있다. 

https://hello-backend.tistory.com/m/154

 

해시 서버 삭제 

위와 같은 동작 방식으로 서버 1이 삭제되었을 때 key1만 가장 가까운 서버 2로 재배치된다. 나머지 키에는 영향이 없다. 

https://hello-backend.tistory.com/m/154

 

기본 구현법의 두 가지 문제 

컨시스턴트 해싱은 분산 시스템에서 노드 추가나 제거 시 발생할 수 있는 데이터 재분배의 양을 최소화하여 시스템의 확장성을 향상시키는데 도움이 되는것은 사실이다. 하지만 다음과 같은 문제가 있다. 

1. 파티션 크기의 불균등

해시링(해시 공간을 원형으로 가정한 구조) 상에서 데이터나 리소스를 노드에 할당한다. 각 노드는 해시링 상의 특정 지점을 차지하게 되며 이 지점들 사이에 공간(파티션)에 해당하는 데이터를 관리한다. 해시 함수 출력에 따라서 노드들이 해시링  상에 균등하게 분포되지 않을 경우 일부 노드가 관리하는 파티션의 크기가 다른 노드에 비해 현저히 크거나 작아질 수 있다. 결과적으로 일부 노드에 과부하가 올수도 있는것이다. 

빨간색이 훨길다. 

 

https://hello-backend.tistory.com/m/154

2. 키의 균등 분포 달성 어려움 

컨시스턴스 해싱은 키를 해시 함수를 통해 해시링 상의 지점에 매핑하고 이 지점에 가까운 노드에 데이터를 할당한다. 해시 함수 특성상 모든 키가 해시링 상에 균등하게 분포되지 않을 수 있고, 이는 일부 노드에 더 많은 키가 할당되는 결과를 만들 수 있다. 

https://hello-backend.tistory.com/m/154

이를 해결하려면 가상 노드라는것을 사용해야 한다. 실제 노드마다 여러 개의 가상 노드를 해시링 상에 배치해서 노드와 키의 분포를 더욱 균등하게 만들어야 한다. 이러면 실제 노드에 대한 데이터 부하를 분산시킬 수 있다. 조금 어려운 말을 빌려쓰면 표준 편차가 작아져서 데이터를 고르게 분포할 수 있다. 

https://hello-backend.tistory.com/m/154

가상 노드를 도입했을 때 더 고민해봐야 하는 점 

• 관리에 좀 더 신경써야 한다. 
• 노드 별로 매핑된거 외에도 가상 노드 자체에 대한 오버헤드가 증가한다. 

컨시스턴스 해싱은 분산 시스템에서 데이터 분배 및 노드 (서버) 관리 문제를 해결하기 위한 기법이다. 예를 들어서 분산 캐시 시스템에서는 컨시스턴트 해싱을 사용해 데이터를 균등하게 분산하고 안정 해시를 통해 캐시된 데이터의 무결성을 검증한다. 

끝!