Consistent Hashing

Consistent hashing 이란?

각 서버 노드들이 분산된 환경에서는 서버 하나로 이루어진 환경에서 보다 고려해야할 것이 많다. 각 노드들 간의 네트워크는 물론이고, 각 노드들의 동작여부, 각 노드들의 부하 여부 등.. 이 밖에도 많이 존재할 것이다. Consistent hashing은 이런 분산 환경에서 각 노드들로 리퀘스트가 들어올 경우 어떤 서버에 할당을 하는가에 대한 방법 중 하나이다. Consistent hashing은 부하 분산에 효과적이며 서버 failure 시에 효과적인 대응을 가능하게 한다. Consistent hashing은 Karger에 의해 논문[1,2] 으로 발표 되었다. Karger는 Consistent hanshing을 이용하면 웹 서버의 대수가 변화하는 환경에서 효과적인 요청 처리를 할 수 있다고 주장하고 있다. Consistent hashing은 현재 Redis, memcached, cassandra 등에서 많이 이용되고 있는 기술이다.

Conssistent hashing의 동작 방법

Consistent hashing은 해싱 알고리즘을 이용한다. 기본적으로 Consistent hashing의 구조는 Hash ring을 생각하면 이해하기 쉽다. 각 노드들은 각각 해시 범위를 가지고 있다. 사용하는 해시 알고리즘의 범위가 0~99의 범위를 가진다면, 각 노드들은 0~99범위안에서 해시 범위를 나눠 가지게된다. 총 노드가 4개라면 0~24, 25~49, 50~74, 75~99의 범위를 나눠 갖게된다. 만약 데이터가 들어온다면 데이터의 해시 값이 포함되는 범위를 가진 노드에 저장되게 된다.

Fig.1 에서 볼수 있듯이 consistent hashing은 Hash ring구조로 되어있다. Hash ring 상의 사각형은 데이터가 저장될 서버 노드를 나타내고, 원은 데이터를 의미한다. Fig.1 의 왼쪽 그림에서, 1번 데이터는 B노드, 2 번 데이터는 C노드, 3, 4, 5 데이터는 A 노드에 저장되어 있다. 각 노드는 각각 해시 범위를 가지고 있어서, 각 데이터는 데이터의 해시값을 포함하는 서버 노드에 저장되게 된다. 만약 D 노드가 추가 된다면, D 노드는 해시범위를 나눠 가지고 해당 범위에 속하는 3 번 데이터가 D 노드에 속하게 된다.

Consistent hashing의 장점

일반적인 데이터의 부하 분산방법으로는 데이터의 해시값 % server 의 대 수 로 저장될 서버를 결정하는 것이다. 그러나 이 경우 서버가 추가되거나 장애등으로 제외된다면 저장된 모든 데이터를 다시 계산해서 이동시켜야 하는 상황이 발생한다. 이런 연산은 전체 데이터를 대상으로 연산되므로 시스템의 큰 부하를 가져오게 된다.

그렇다면, Consistent hashing 은 어떤가 살펴보도록 하자.

첫번째로, 서버 노드가 삭제 되었을 경우이다. Fig.1 의 오른쪽 Hash ring에서 노드 B 가 장애등의 이유로 제외된다고 가정하자. 데이터 1 은 유실이 되고, 노드 B가 담당하고 있던 해시 범위는 노드 C 가 담당하게 된다. 그 외의 데이터 migration은 발생하지 않는다. 만약, 데이터의 해시값 % server 의 대 수로 저장될 서버를 결정한다면 노드가 제외됬을 경우 전체 데이터에 대한 연산이 발생하게 될 것이다.

두번째로, 서버 노드가 추가 되었을 경우이다. 이 경우에는 앞에서 설명했듯이 Fig.1 의 왼쪽그림에서 노드 D 가 추가되는 상황이랑 같다. 데이터 3 만 노드 D로 할당될 뿐 다른 노드들에 저장된 데이터들은 이동할 필요가 없다.

Consistent hashing의 단점

Consistent hashing의 단점이라고 한다면, 부하 분산을 해시 알고리즘에 의존하게 된다는 점이다. 사용하는 해시 알고리즘의 Uniform distribution 이 좋지 않다면 부하 분산이 잘 되지 않을 것이다. 이를 해결하기 위해 실제 서버 노드 외에 임의 가상노드를 이용하여 문제를 해결 하고 있다. 실제로 Cassandra에서는 virtual node를 이용하고 있다.

Reference

• Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the World Wide Web - http://diyhpl.us/~bryan/papers2/distributed/distributed-systems/consistent-hashing.1996.pdf
• Web caching with consistent hashing - http://diyhpl.us/~bryan/papers2/distributed/distributed-systems/consistent-hashing.1996.pdf
• Amazon’s Dynamo - http://www.allthingsdistributed.com/2007/10/amazons_dynamo.html
• The Simple Magic of Consistent Hashing - http://java.dzone.com/articles/simple-magic-consistent