개요
데이터 분산 시스템(주로 캐시서버) 를 사용할때, 캐시서버가 새로 추가되거나 다운되는 경우가 있다. 일반적인 해시 알고리즘 (ex. mod) 를 사용하게 되면 모든 데이터가 다시 재배치되어야 한다.
이를 방지하고, 일부 데이터들만 재배치하도록 만드는 알고리즘이 Consistent Hashing 이다.
기존 해싱
위와 같이, 3개의 데이터베이스가 있고, 가장 module 계산을 통해 데이터가 저장될 위치를 지정한다고 하면 위와 같은 상태 일 것이다.
그런데, 만약 scale out 을 하게 되어 서버 한개를 추가하게 되면 위와 같은 상태로 변한다.
이와 같이 새로운 서버를 추가하게 되면 rehashing 을 해주어야 하는데, 그렇게 되면 대부분의 데이터 위치들이 변경 될 것이다.
지금은 데이터가 6개 밖에 없지만 실업무 환경에서는 많을경우 수억개의 데이터들이 저장될텐데, 만약 db 서버 한개를 추가할때마다 그 모든 데이터들이 재배치되게 된다면 큰 문제가 발생할 것이다.
안정 해싱
위와 같은 문제를 해결하기 위해 안정해싱이 등장하였다.
안정해싱의 경우 원형으로 된 선위에 노드들이 배치되어 있다. 그리고 각 데이터를 해싱한 값에서 한방향으로 쭉갔을때, 가장 가까운 노드에 저장되는 개념이다.
위 그림은 서버가 3개일때, 각 서버에 저장된 모습입니다.
data 5의 예시를 보시면 오른쪽 방향으로 갔을 때 가장 먼저 만나게 되는 서버 1에 저장되는것을 볼 수 있습니다.
만약 서버가 1개 추가된경우에는 데이터 1001, 1025 만 위치를 재조정하고 나머지 데이터들은 자기자리에 있는 모습을 보실 수 있습니다.
카산드라
카산드라의 경우 node 간 data를 복제해 둔다.
복제되는 노드 수는 replication factor (RF) 에 의해 결정된다.
아래의 그림은 해당 값이 3인 경우이다.
Vnode
이 Consistent Hashing 이 잘 작동하려면, 각 노드별로 담당하는 영역이 균일해야 한다.
그런데, 만약 위와 같이 8개의 노드가 균일하게 배분되어 있는 상황에서 9번째 신규노드를 만든다 가정해보면, 영역별 불균형이 올 수 밖에 없다.
Consistent Hashing 의 균일 분배는 중요한 문제이므로, 이를 해결하기 위해 가상 노드라는 개념을 도입하였다. 한개의 물리적 db가 해시링위에 여러개의 가상노드를 가진다. 해시링 위의 노드들이 많아질수록 분산이 커지기 때문에 더욱더 균일해지는 효과를 지니고 있다.
Reference
https://jiwondev.tistory.com/299
https://cassandra.apache.org/doc/3.11/cassandra/architecture/dynamo.html