Consistent Hashing 설계

Consistent Hashing 이란?:

• 분산 시스템에서 데이터를 균형 있게 분산시키고, 노드(서버)의 추가 또는 제거 시 데이터 이동을 최소화하기 위한 해싱 기법

 

 

Consistent Hashing 이 필요한 이유:

• 데이터를 여러개의 분산 시스템에 균등하게 배분하기 위해서.
• 서버의 확장성을 위해서 필요함.
• Rehashing 문제에 대응하기 위해서:
  • 가장 단순하게 데이터를 여러개의 서버로 분산 시키는 방법으로는 Mod(%) 연산이 있음.
  • 서버가 4개라면, % 4 를 해서 데이터를 해당 서버로 분산시키는 것.
  • 이 방법은 서버가 고정되고 정적일 때 잘 작동함. 서버가 추가되거나, 제거되거나 등의 유연하게 대응하기에는 어렵다. Mod 연산의 값이 달라지기 때문에.
  • 그렇다고 서버가 추가/제거 된 이후 모든 데이터를 다시 처음부터 다시 분배하는 것도 말이 안됨. 너무 분배해야 할 데이터가 많기 때문에.
  • 즉 일반적인 해싱 기법에서는 노드 수가 변하면 대부분의 키가 다른 노드로 재배치되지만 Consistent Hashing 은 일부의 데이터만 이동하게 됨.
• 데이터의 수명이 아주 짧거나, 리밸런싱 또는 리해싱이 필요하지 않다면 Mod 연산으로도 충분한(Satitsfy) 방법일듯.

 

 

Consistent Hashing 작동 방식:

• 해시 함수를 사용하여 0부터 최대 값까지의 범위를 가지는 논리적인 원형 해시 공간(해시 링) 을 만듬.
• 각 노드(서버)를 해시 함수를 통해 해시 링의 특정 위치에 매핑
• 저장할 데이터의 키를 동일한 해시 함수를 사용하여 해시 링의 위치에 매핑
• 각 데이터 키는 해시 링에서 시계 방향으로 가장 가까운 노드에 저장
• 새로운 노드가 해시 링에 추가되면, 해당 노드에 영향을 받는 일부 데이터만 재배치
• 노드가 제거되면, 그 노드에 할당된 데이터만 인접한 노드로 이동

 

 

Consistent Hashing 설계 시 고려사항:

• 노드가 골고루 배치되어야 하지 않는가?
  • 노드의 해시 값이 균일하지 않으면 데이터가 특정 노드에 몰릴 수 있음.
  • 이를 해결하기 위해 가상 노드(Virtual Nodes) 를 사용해서 노드마다 여러개의 해시 값을 포함하도록 함.
  • Virtual Node 는 서버 하나만 해쉬 링에 올리는게 아니라, 서버 하나당 여러개의 Virtual Node 를 가지도록 해서 Hash ring 에 올리도록 하는 것. 이렇게 여러개로 올리면 보다 균등하게 배분되게 될거임
• 노드가 사라질 때 해시 키는 어떻게 배분되는가?
• Hashing Function 의 속도도 중요함:
  • SHA 와 같은 cryptographic hash function 은 해쉬 함수의 속도가 느림.
  • Murmur 과 같은 Non-cryptographic hash function 이 속도 측면에서 더 유리함.
• 각 server 가 다른 서버의 replication 도 가지고 있도록 해서 데이터 손실을 없애야함.
• Domino effect 를 고려해야함.
  • Hash Ring 위의 하나의 서버가 crash 가 나면 담당하고 있던 데이터들이 모두 다음 서버에게 전가될 수 있음. 이로 인해서 서버가 연쇄적으로 붕괴될 수 있다.
  • 즉 서버가 하나 제거될 때 그 서버가 담당하고 있는 데이터들은 골고루 전파되어야함.
  • 이것도 Virtual Node 개념으로 해결할 수 있음. 여러개의 Virtual Node 를 통해서 데이터는 보다 균일하게 나눠질거임.

 

 

Consistent Hashing 의 사용 사례:

• Connection 관리 및 로드 밸런싱: 다수의 서버에 부하를 고르게 분산시키고, 서버의 추가 또는 제거 시 데이터의 재분배를 위해서 사용할 수 있음.
• Memcached나 Redis 같은 분산 캐시 시스템에서도 Consistent Hashing을 사용하여 캐시 데이터를 여러 노드에 고르게 분산시킬 수 있음.