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

5장 안정 해시 설계

김주혁

Mar 23, 2024

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

해시 키 재배치(rehash) 문제 안정 해시 마치며

수평 규모 확장성을 도달하기 위해선, 요청 또는 데이터를 서버에 균등하게 나누는 것이 중요하다. 안정해시는 이 목표를 달성하기 위해 사용하는 기술이다.

해시 키 재배치(rehash) 문제

해싱이란, 동적인 입력값에 대한 고정 길이 출력을 생성하는 과정으로 이 고정 길이를 출력하는 과정은 해시 함수(해시 알고리즘)을 통해 이루어진다. 해시 함수의 사용처 중

대표적인 알고리즘은

md5
sha-256

대표적인 사용처는

jwt
bcrypt
blockchain

등의 알고리즘과 사용처가 존재한다.

일부 데이터베이스의 경우, DHT(Dustrubuted hash Table)을 통해 데이터 검색 최적화를 수행하는데 여기서 핵심은 해시 테이블이다. 해시 함수는 일반적으로 Key-Value로 구성되있고, 해시 함수에 Key를 넣으면 테이블의 Index가 나오는 형식이다.

책에서 나온 예시를 예로들면, hash(key0) % 4 = 1이라면 클라이언트는 캐시에 보관된 데이터를 가져오기 위해 서버 인덱스인 1에 해당하는 요청을 보내 서버 1로부터 정보를 가져와야 한다.

간단하게 id값으로 얻은 해시 값을 통해 캐시 서버로 요청을 보내는 그림을 설명하면 이렇다.

간단하게 설명하면 공지사항 아이디를 해시 함수에 넣어 키를 얻고, 해당 키 값을 서버의 숫자로 나누면 인덱스 값을 얻을 수 있는데 해당 인덱스 값을 요청을 보낼 때 같이 보내 원하는 캐시 서버로부터 정보를 얻어오는 과정이다.

추가적으로 이해를 돕기 위해서 설명하면, 해시 테이블을 적극적으로 과거에 사용한 P2P 방식의 탐색은 완전 탐색에 가까운 방식으로 노드가 다음 노드로 이어지며 데이터를 찾아가는 과정이다.

그런데 이런 고정된 캐시 서버를 가정으로 하는 분산 방식은 특정 서버가 죽어버리거나 삭제 혹은 추가됐을 경우 문제를 발생시킬 수 있다.

위 처럼 장애가 발생한 1번 서버가 죽어버리면, 1번 서버에 보관된 키 뿐만 아니라 전부 재배치가 되버린다. 해시 함수로 얻어낸 키를 통해 서버 인덱스를 얻고 정보를 받아와야 하는데 정보가 저장된 서버가 아닌 다른 서버로 엉뚱하게 요청을 보내 결과를 얻게되는 이른바 대규모 캐시 미스가 발생할 것이다. 안정해시는 이런 문제를 해결한다.

안정 해시

위키 피디아에 따르면, 안정 해시는 해시 테이블이 재조정될 때 평균적으로 k(키의 개수)/n(슬롯)개의 키만 재배치하는 해시 기술이다. 이와 달리 전통적 해시 테이블은 슬롯의 수가 바뀌면 거의 대부분 키를 재배치한다.

해시 공간과 해시 링

만약 해시 함수로 sha-256을 사용한다고 치고, 함수의 출력 값이 x0,x1 … xn까지라고 할 때 sha256의 최대 해시 테이블의 공간 범위는 0부터 2^160-1까지라고 알려져 있다. 따라서 x0은 0, xn은 2^160-1이고 나머지는 x1 ~ xn-1은 그 사이의 값을 가지게 될 것이다.

그리고 그 사이를 구부리면, 해시 링이 만들어진다.

해시 서버

해시 함수를 사용하게 되면, 서버 IP나 해시 함수 내부적인 기준에 따라 링 위의 특정 위치에 배치 될 것이다.

위 처럼, 서버는 슬롯 0,1,2,3에 배치될 수 있다. 순서대로 배치될 수도 있고 해시 함수에 의해 정의해 둔 서버 번호와 다르게 배치될 수도 있다.

해시 키

또한 캐시할 키 또한 해시 함수에 의해 링 위의 특정 지점에 배치될 수 있다.

서버 조회

어떤 키(k)가 저장되는 서버는 해당 위치로부터 시계 방향으로 링을 탐색해 나가면서 만나는 가장 첫 번째 서버다. 해당 과정을 통해 키는 첫 번째 서버의 키로 저장된다.

서버 추가

안정 해시를 사용하면, 서버를 추가하더라도 키 가운데 일부만 재배치하면 된다.

위 그림 처럼 새로운 서버 s4가 해시 함수에 의해 배치되면 key0은 첫 번째 자신이 마주치는 서버인 s4로 재배치되고 나머지 key들은 그대로 있을 것이다.

서버 제거

하나의 서버가 제거되면, 키 가운데 일부만 재배치된다.

서버 1이 삭제됐을 때, key1만 서버2로 재배치 됐다.

기본 구현법의 두 가지 문제

위 방식은 다음과 같은 두 전제로 진행된다.

서버와 키를 균등 분포 해시 함수를 사용해 해시 링에 배치한다.
키의 위치에서 링을 시계 방향으로 탐색하다 만나는 최초의 서버가 키가 저장될 서버다.

이 접근법에는 두 가지문제가 있는데,

첫 번째는

서버가 추가되거나 삭제되는 상황을 감안하면 파티션 크기를 균등하게 유지하는 것이 불가능 하다는 것이다. 여기서 파티션은 인접한 서버 사이의 해시 공간이다. 어떤 서버는 굉장히 작은 해시 공간을 할당받고 또 어디는 굉장힐 큰 해시 공간을 할당 받는 상황이 가능하다는 것이다.