가상 면접 사례로 배우는 대규모 시스템 설계 기초 - 5장 ) 안정 해시 설계

 

 

안정 해시 설계 

• 수평적 규모 확장성을 달성하기 위해서는 요청 또는 데이터를 서버에 균등하게 전달하는 것이 중요 

 

 

 

해시 키 재배치 문제 

• 해시 함수
  • N개의 서버에 부하를 균등하게 나누는 보편적인 방법
  • ex) serverIndex = hash(key) % N 
    
    • 서버 풀의 크기가 고정되어 있을 때, 그리고 데이터 분포가 균등할 때는 잘 동작 
    • 서버 풀의 수가 변경되면 대부분의 키가 재분배되는 문제발생 
      • 서버 1개가 삭제되면 캐시 클라이언트가 데이터가 없는 엉뚱한 서버에 접속하게 됨 

 

 

 

안정 해시 (consistent hashing)

https://www.geeksforgeeks.org/consistent-hashing/

• 해시 테이블 크기가 조정될 때 평균적으로 k/n개의 키만 재배치하는 해시 기술
  • k = 키의 개수 
  • n = 슬롯의 개수 

 

 

해시 공간과 해시 링 

• 해시링
  • 해시 공간을 동그랗게 접어 만든 것 
  • ex) SHA-1의 해시공간 범위는 0부터 2^160-1 까지

 

 

해시 서버 

• 해시 함수 f를 사용하면 서버 IP나 이름을 해시 링위의 특정 위치에 대응시킬 수 있음 

 

 

해시 키 

• 해시 키 또한 해시링의 어느 지점에 배치될 수 있음 

 

기본 구현 방식 

• 서버와 키를 균등 분포 해시 함수를 사용해 해시 링에 배치 
• 키의 위치에서 링을 시계 방향으로 탐색하다 만나는 최초의 서버가 키가 저장될 서버 
  • 서버 조회 
    • 어떤 키가 저장되는 서버는 해당 키의 위치로부터 시계방향으로 링을 탐색해 나가면서 만나는 첫번째 서버 
  • 서버 추가 
    • 위와 같은 방식이라면 서버를 추가하더라도 키 가운데 일부만 재배치 하면 됨
      • 다른 키들은 재배치 되지 않음 
  • 서버 제거 
    • 하나의 서버가 제거되면 키 가운데 일부만 재배치 됨 
• 기본 구현 방법의 두 가지 문제 
  • 서버가 추가되거나 삭제되는 상황을 감안하면 파티션의 크기를 균등하게 유지하는게 불가능 
    • 파티션 = 인접한 서버 사이의 해시 공간 
  • 키의 균등 분포를 달성하기 어려움 

 

 

 

가상 노드 기법 (복제 노드, virtual node)

https://www.youtube.com/watch?v=sl9pJqIA1hg

• 실제 노드 또는 서버를 가리키는 노드로, 하나의 서버는 링 위에 여러개의 가상노드를 가질 수 있음 
  • 각 서버는 하나가 아닌 여러개 파티션을 관리해야 함 
• 키의 위치로 부터 시계 방향으로 링을 탐색하다 만나는 최초의 가상노드가 해당 키가 저장될 서버가 됨 
  • 가상 노드의 개수를 늘리면 키의 분포는 점점 더 균등해짐 
  • 표준 편차가 작아져서 데이터가 고르게 분포되기 때문 
    • ex) 100 ~ 200 개의 가상노드를 사용했을 경우 표준편차 값은 평균의 5% ~ 10% 사이 
  • 가상 노드 개수를 많이 늘리면 가상노드 데이터를 저장할 공간이 더 많이 필요하게 되므로 타협적 결정이 필요 

 

재배치할 키 결정 

• 서버가 추가되거나 제거되면 데이터 일부는 재배치 되어야 함 
  • 서버가 추가되면 새로추가된 노드 부터 그 반시계 방향에 있는 첫번째 서버까지 영향 받음 
  • 서버가 제거되면 삭제된 노드부터 그 반시계 방향에 있는 첫번째 서버까지 영향 받음 

 

 

 

정리 

• 안정 해시의 장점 
  • 서버가 추가되거나 삭제될 때 재배치 되는 키의 수가 최소화 됨 
  • 데이터가 보다 균등하게 분포하게 되므로 수평적 규모 확장성을 달성하기 쉬움 
  • 핫스팟 키 문제를 줄일 수 있음 
    • 특정 샤드에 대해 부하가 증가하는 것을 방지할 수 있음