Contents
수평 규모 확장성을 도달하기 위해선, 요청 또는 데이터를 서버에 균등하게 나누는 것이 중요하다. 안정해시는 이 목표를 달성하기 위해 사용하는 기술이다.
해시 키 재배치(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로 재배치 됐다.
- 기본 구현법의 두 가지 문제
- 서버와 키를 균등 분포 해시 함수를 사용해 해시 링에 배치한다.
- 키의 위치에서 링을 시계 방향으로 탐색하다 만나는 최초의 서버가 키가 저장될 서버다.
- 첫 번째는
- 두 번째는
위 방식은 다음과 같은 두 전제로 진행된다.
이 접근법에는 두 가지문제가 있는데,
서버가 추가되거나 삭제되는 상황을 감안하면 파티션 크기를 균등하게 유지하는 것이 불가능 하다는 것이다. 여기서 파티션은 인접한 서버 사이의 해시 공간이다. 어떤 서버는 굉장히 작은 해시 공간을 할당받고 또 어디는 굉장힐 큰 해시 공간을 할당 받는 상황이 가능하다는 것이다.
s1이 삭제되는 바람에 s2의 파티션이 다른 곳 보다 2배 이상 커진 모습이다.
균등 분포자체가 어렵다는 것이다.
추가되고 삭제되는 과정에서 s2에 대부분의 키가 몰려있게 됐다.
- 가상 노드
위 문제를 해결하기 위한 기법으로 가상 노드가 제안됐다.
가상 노드는 실제 노드 또는 서비스를 가리키는 노드로서, 하나의 서버는 링 위의 여러 개의 가상 노드를 가질 수 있다.
위 그림처럼 링 위에 서버0과 서버1은 3개의 가상 공간을 가지고 있다.
따라서, 각 서버는 하나가 아닌 여러 개의 파티션을 관리해야 한다. 키의 위치로부터 시계방향으로 탐색하다 만나는 최초의 가상 노드가 해당 키가 저장될 서버가 된다.
가상 노드의 개수를 늘릴 수록 점점 더 키의 분포는 균일해진다. 표준 편차가 적어지는데 표준 편차는 데이터가 어떻게 퍼져 나갔는지 보이는 척도다.
가상 노드가 많아질 수록 표준 편차 값은 더 떨어져 효율적으로 보이겠지만 반대로, 가상 노드 데이터를 저장할 공간은 더 많이 필요해질 테니 타협점이 필요하다.
- 재배치할 키 결정
서버가 추가나 제거되면, 데이터의 일부가 재배치되야 한다.
위 그림 처럼, 서버4가 추가되면 서버3부터 서버4 사이의 키들을 전부 서버4로 재배치 해야 한다.
혹은 서버1이 삭제됐다면, 서버0부터 서버 2사이의 모든 값들(반시계 방향)이 서버2로 재배치되야 한다.
마치며
안정해시의 이점은 다음과 같다.
- 서버가 추가되거나 삭제될 때 재배치되는 키의 수가 최소화된다.
- 데이터가 보다 균등하게 분포하게 되므로 수평적 규묘 확장성을 달성하기 쉽다.
- 핫스팟 키 문제를 줄인다. 특정 샤드에 대한 접근이 지나치게 빈번하면 과부하 문제가 생길 수 있다.
안정해시 사용처는 다음과 같다.
- AWS DynamoDB
- Apache Cassandra 클러스터에서의 데이터 파티셔닝
- Discord 채팅
- 아카마이 CDN
- 매그레프 네트워크 부하 분산기
주로 파티셔닝 기술은 NoSQL의 데이터베이스에서 주로 사용되는 데이터 관리기술 이기 때문에 NoSQL 사용처가 많이 보이는 모습이다.
Share article
