Consistent Hashing이란 다수의 노드로 이루어진 클러스터안에 데이터를 저장할때 데이터의 키를 기반으로 하여 어떤 노드에 저장할 것인가 계산하는 로직을 말합니다. Gossip Protocol과 더블어 아마존의 Dynamo의 영향을 받은 부분입니다.

간단하게 표현하여 보자면 위와 같습니다. alice라는 키에 값을 넣을때에는 3대의 노드가 있다면 단순히 이름을 해싱하여 3으로 나누면 됩니다. 위의 그림에서는 두번째 노드에 저장하는것으로 결정 되었네요.

시스템이 확장됨에 따라 노드가 하나 더 추가되었습니다. 단순하게 위의 그림만을 놓고 보자면 alice는 더이상 2에 저장되지 않습니다. 3에 저장되는 군요. 반대로 이미 2에 저장된 데이터는 3으로 옮겨와야 합니다. 데이터의 개편이 필요합니다.

실제로 데이터는 단순하게 나머지연산(%)을 하지는 않습니다. 각각의 노드가  응답가능한 데이터의 범위를 가지고 있고 거기에 맞는 범위안에 데이터가 저장됩니다. 위의 경우에는 키 alice를 해싱한 결과가 23이라면 0과 42사이에 저장하면 되는것이겠죠.

새로운 노드가 추가(또는 삭제)되었습니다. 대부분의 데이터는 여전히 그 자리에 있습니다.

4대의 노드간의 밸런스를 조정한 상태(rebalanced)입니다. 이경우 약간의 데이터가 자기 자리를 찾기위해 옮겨다녀야 합니다. 위의 alice는 23으로 변화가 없지만 35인 데이터가 있다면 노드 위치를 옮겨야 합니다.