안정 해시 설계 정보 및 경험 공유

해시 키 재배치(rehash) 문제

• 부하를 균등하게 나누려면 해시 함수를 이용하면 좋음

serverIndex = hash(key) % N (N은 서버의 개수)

 

• 기존 키가 삭제되거나 추가되면 이슈가 발생할 수 있음
  • 삭제 될 경우 엉뚱한 서버에 접속 -> 대규모 캐시 미스 발생 가능

안정 해시

안정 해시는 해시 테이블 크기가 조정될 때 오직 k(키 개수)/n(슬롯 개수)개의 키만 재배치하는 기술

• 서버와 키를 균등 분포(uniform distribution) 해시 함수를 사용 해 해시 링에 배치
• 키의 위치에서 링을 시계 방향으로 탐색하다 만나는 최초의 서버가 키가 저장될 서버다
• 파티션 (해시 공간)의 불균형 문제가 생김 -> 가상 노드가 들어옴

가상 노드

• 하나의 서버가 링 위에 여러 개의 가상 노드를 가지는 것
• 시계방향으로 링을 탐색하다 만나는 최초의 가상 노드가 저장될 서버로 됨
• 가상 노드의 개수를 늘릴 수록 분포가 점점 더 균등해짐

재배치할 키 결정

• 추가 및 삭제 시 고려

---

나의 사용 경험

DynamoDB 에서의 파티셔닝 경험

• DynamoDB의 primary key 를 기준으로 파티셔닝 테이블이 생성된다.
• 각각 테이블이 key-value 기반의 분산 구조로써 작동한다.

DyanmoDB 해시 구조

• 1 partition key 기준 1 partition 에 저장
• 하지만 1 partition 안에 1 partition key 가 저장되는 것은 아니고 n partition key가 저장됨
• partition key는 MD5로 변형되어 해싱되어 분배 저장됨
• partition 개수?
  • 읽기 용량 단위(RCU) 10000 && 쓰기 용량 단위(WCU) 5000
    • 읽기 용량 단위: 10,000
    • 쓰기 용량 단위: 5,000
    • 읽기 용량 기준 파티션 수: 10,000 / 3,000 ≈ 3.33 → 4 (올림)
    • 쓰기 용량 기준 파티션 수: 5,000 / 1,000 = 5
    • 초기 파티션 수: 5 (더 큰 값)
  • 읽기 용량 단위: 6,000 && 쓰기 용량 단위: 2,000
    • 읽기 용량 기준 파티션 수: 6,000 / 3,000 = 2
    • 쓰기 용량 기준 파티션 수: 2,000 / 1,000 = 2
    • 초기 파티션 수: 2 (같은 값)