안정 해시 설계

'가상 면접 사례로 배우는 대규모 시스템 설계 기초' 책을 보면서 '5장 안정 해시 설계' 단원을 읽어보았는데, 잘 이해가 가지 않아서 다시 한번 정리해보고자 한다.

일단, 해당 단원의 해시 기술은 API 서버가 아닌 데이터베이스나 캐시 서버와 같은 데이터 저장소 시스템에 사용되는 것이다. 왜냐하면 API 서버는 기본적으로 Stateless이기에 요청 처리를 위해 꼭 같은 서버에게 요청을 보내야 하는 것도 아니며, 서버를 추가 및 제거 한다고 해서 문제가 발생하지 않는다. 그리고 이런 API 서버에 대한 부하 분산은 로드 밸런서가 따로 하기 때문에 관계없다!

안정 해시의 목적은 기존 해시를 통한 데이터저장소 분산 방식의 단점을 해소하기 위함이다.
기존 해시 방법은 서버의 정보를 배열 같은 자료구조에 담아두고, 키 값을 해시하여 나온 값을 `% 서버의 수` 연산을 통해 인덱스로 접근한다. 하지만 여기서 서버가 추가되거나, 존재하던 서버 중 하나가 장애가 발생했을 때 문제가 생길 수 있다.

예를 들어, key1의 해시 값이 7 일 때, 서버가 3개 존재했다면 3으로 나눈 나머지는 1이다. 여기서 서버가 추가된다면 4로 나누게 되는데, 이러면 나머지가 1이 아닌 3이 된다. 만약 캐시 서버라면 캐시 미스가 나게 되는 상황이고, 데이터베이스 샤딩이었다면 필요한 데이터가 존재하지 않는 데이터베이스에 접근하게 되는 상황이 발생한다. 

이 뿐만 아니라 기존 3개의 서버 중 1개의 서버가 죽었다면, `% 2`가 되어 키들이 모두 재분배 되어서 요청이 균등하게 분포되지 않는 경우가 발생할 수도 있다. 이렇듯 기존 해시는 위의 두 단점이 있었기 때문에 이를 해소하기 위해 '안정 해시' 기술이 나오게 된 것이다.

안정 해시의 동작 방식은 해시 함수의 출력값 범위를 의미하는 해시 공간을 논리적인 원형 링 형태로 만드는 것으로 시작한다. 이제 서버는 인덱스 방식이 아닌 해시 공간에서 특정 좌표를 갖게 되고, 키 값도 동일하게 특정 좌표를 갖게 된다. 여기서 갖는다함은 실제로 이 값을 보유하는 것이 아니라 해시 공간의 특정 좌표에 존재함을 의미한다. 서버가 해시 공간의 좌표를 갖는 코드를 나타내면 아래와 같을 것이다.

TreeMap<Long, Server> hashRing = new TreeMap<>();
hashRing(hash(server1.ip), server1);
hashRing(hash(server2.ip), server2);
hashRing(hash(server3.ip), server3);

그러면 이제 요청 시 해시 함수의 결과로 나온 값을 기준으로 시계 방향으로 돌면서 가장 가까운 서버 노드를 찾는다. 찾았다면, 해당 서버로 해당 키에 대한 요청을 보내는 것이다.

그림으로 나타내면 위와 같은데, 실제로 저장된 것은 서버 뿐이고 키 값은 실제로 해시 공간에 저장되진 않는다. 그냥 논리적으로 나타낸 것일 뿐

이렇게 되면 서버가 해시 공간에 고르게 분포되어 있어 키 값은 더 이상 어느 한 서버로 몰리지 않을 것이다. 그리고, 하나의 서버가 사라지거나 추가되어도 영향을 받는 키 값의 수가 적어진다!

하지만 키 값과 서버의 해시 값이 같으면 어떻게 될까? 키를 저장하진 않고 비교하기만 하니 사실 문제가 없다. 단지, 같은 값의 서버를 통해 요청할지, 같은 값 다음의 가까운 서버를 통해 요청할지에 대한 전략 차이일 뿐이다. 코드로 본다면 아래와 같을 것이다.

TreeMap<Long, Server> ring = new TreeMap<>();
ring.put(hash(server1.ip), server1);
ring.put(hash(server2.ip), server2);
ring.put(hash(server3.ip), server3);

long keyPosition = hash(key);
Server server = ring.ceilingEntry(keyPosition).getValue();

그럼 이런 안정 해시는 단점이 없을까? 그건 또 아니다. 위의 예시에는 서버의 해시 값이 고르게 분포된다는 가정하에 한 것이라 그렇지만 서버끼리 서로 가깝게 해시 값이 이뤄지면 이런 안정 해시의 장점을 누릴 수 없게된다.

그래서 가상 노드를 활용하는데, 이 가상 노드들은 실제 노드 또는 서버들을 가르키는 노드이다. 가상 노드들을 여러 개 배치하여 단점을 해소할 수 있다. 그림으로 본다면 다음과 같다.

하지만 가상 노드를 많이 만들게 되면 그만큼 메모리 공간을 많이 사용하게 되니 적절한 트레이드 오프가 필요한 법이다.