Consistent Hashing

Consistent hashing: 웹서버의 갯수가 변동하는 가운데 요청을 분산하는 방법. 

출처: wikipedia

해시테이블의 크기가 변할때, 평균적으로 K/n의 키만 재매핑되면 된다. 

즉, 노드나 슬롯의 개수가 바뀔때, 노드의 추가나 삭제를 할 때, 오직 K/n의 아이템만 다시섞이면 됨. (n은 전체 노드의 갯수, K는 item의 개수) 

기존의 해싱에서는 슬록의 개수 변화가 거의 모든 키가 다시 재매핑되야만 했다. (키와 슬롯간의 매핑이 모듈러 연산에 의해 정의되었기 때문)

Consitent hashing이 사용되는 상황

1. Consistent hashing은 분산 캐싱을 위해 나오게 되었다. 이는 변화하는 웹서버들의 수들 사이에서 요청을 분산하는 방법의 하나로 소개되었다. 
2. 또한 consistent hashing은 거대한 웹 애플리케이션에서의 부분적인 장애의 충격을 감소시키는 역할을 하는데, 이는 시스템의 전반적인 장애의 결과를 초래하는 것 없이 강력한 캐시를 사용하기 위해서이다.
3. Consistent hashing은 또한 분산 해시 테이블(DHT) 디자인에 적용할 수 있다. DHT는 분산된 노드들의 집합사이에서 전체 키공간을 파티셔닝하기 위해서 사용한다. 게다가 노드들을 연결해서 노드가 어떤 키가 효과적으로 위치될 수 있도록 하는 오버레이 네트워크를 제공한다.

Consistent hashing의 필요성

• 보통, n개의 캐싱 머신을 로드밸런싱하는 방법은 데이터(O)에 대한 해시값을 모듈러 n 하는 방식인데[= hash(O) (mod n) ] , 이는 캐싱 머신이 늘어나거나 줄어들 때 n이 바뀌며 모든 데이터들이 새로운 곳에 해시되어야 한다. 이것은 매우 치명적일 수 있는데, 왜냐하면 기존의 데이터가 있는 서버가 캐싱 머신으로부터의 요청으로 과부하가 걸릴 수 있기 때문이다. 따라서 Consistent hashing은 서버의 과부하를 막기위해서 필요하다. 
• Consistent hashing은 데이터를 가능한 한 같은 캐싱 머신에 해싱시킨다. 이는 캐싱머신이 추가될 때, 추가되는 캐싱머신이 다른 모든 캐싱머신들로부터 데이터를 공유한다는 의미이다. 반대로 이 캐싱 머신이 클러스터에서 빠져나갈때,  이 머신의 데이터들은 클러스터에 남아잇는 캐싱머신들사이에서 공유된다
• Consistent hashing의 핵심 목적은 각각의 캐시를 다른 해시 값 구간들과 연관시키도록 하는 것인데, 이 구간의 경계는 각각의 캐시 identifier의 해시를 계산하면서 결정된다. 만약 그 캐시가 제거된다면, 그 캐시의 구간은 적정의 구간과 함께 다른 캐시에 의해 취해진다. 모든 남아있는 캐시는 변하지않는다.
• 만약 버킷이 이용불가능하다면, hash ring에서의 버킷의 포인트는 제거된다. 그리고 그 버킷에 매핑된 모든 데이터에 대한 요청은 그 다음 포인트에 매핑된다. 각각의 버킷이 무수한 램덤하게 분산된 포인트들과 연관되기때문에 (vnode 혹은 vbucket이라 불리는 각 버킷의 virtual버전의 버킷들을 hash ring의 군데군데 만든다. 이로 인해 노드 제거시 부하 불균형을 해결한다.), 각 버킷에 소유되는 리소스들은 무수히 다른 버킷들로 매핑된다. 사라진 버킷에 소유되었던 데이터들은 남아있는 것들사이의 버킷들로 재분산된다. 그러나 다른 버킷에 매핑된 값은 여전히 그 같은 값이고, 이동될 필요가 없다.

의문점: 왜 K/n만큼의 데이터만 재매핑되면 되는가?

간혹 K/n으로 딱 안떨어질때가 있는데, 어디까지나 평균적으로 그렇다는 의미이다.

---

Technique

Consistent Hashing은 모든 데이터를 hash ring의 각 지점에 매핑 시키는데에 기반을 둔다. 시스템은 각각의 이용가능한 머신을 hash ring의 무수한 랜덤하게 분산된 포인트에 매핑시킨다.

데이터가 어디 위치해야하는지를 찾기 위해서, 시스템은 hash ring상에서의 데이터의 키의 위치를 찾는다. 그후에  처음으로 만나는 버킷에 도달할때까지 hash ring들 돈다. 각각의 버킷은 그 버킷의 포인트와 이전 버킷의 포인트 사이에 존재하는 모든 리소스를 포함한다.

버킷을 추가할때도 비슷한 과정이 일어난다. 버킷을 추가하면서 그 버킷과 그 옆의 버킷 사이의 모든 리소스는 새로운 버킷에 추가된다. 이 리소스들은 더이상 이전의 버킷과 연관되지 않으며, 데이터 선택 메서드에 의해서 이전의 버킷에서 찾아지지 않는다.

각각의 버킷과 연관된 키의 부분들은 버킷이 매핑된 각들의 개수가 변함에따라 바뀔수있다.