/
/

Consistent Hash

안정 해시(consistent hash)는 해시 테이블 크기가 조정될 때 평균적으로 오직 k/n개의 키만 재배치하는 해시 기술이다. 여기서 k는 키의 개수이고, n은 슬롯(slot)의 개수이다.
Consistent Hash
avatar
efforthye
in
CS
2025.05.27
·
7 min read

안정 해시(consistent hash)는 해시 테이블 크기가 조정될 때 평균적으로 오직 k/n개의 키만 재배치하는 해시 기술이다. 여기서 k는 키의 개수이고, n은 슬롯(slot)의 개수이다. 이와는 달리 대부분의 전통적 해시 테이블은 슬롯의 수가 바뀌면 거의 대부분 키를 재배치한다.

6460

안정해시의 핵심 동작 원리

해시 링(Hash Ring) 구조

안정해시는 해시 링이라는 원형 공간을 사용한다. 해시 링(hash ring)의 특징은 다음과 같다.

Hash Ring
해시 링(hash ring)은 0부터 최대값까지의 해시값들을 원형으로 연결해서 서버와 데이터를 배치하는 가상의 원형 공간이다.
https://until.blog/@cs/hash-ring
Hash Ring

  • 0부터 2^32-1까지의 해시값을 원형으로 배열한다

  • 서버와 키 모두 이 링 위의 특정 위치에 배치된다

  • 해시 함수(예: SHA-1, MD5)를 사용하여 위치를 결정한다

서버 배치

서버A → hash(서버A IP) → 링 위치 1000
서버B → hash(서버B IP) → 링 위치 5000  
서버C → hash(서버C IP) → 링 위치 8000

키 할당 규칙

핵심: 각 키는 시계방향으로 만나는 첫 번째 서버에 할당된다.

키1 → hash(키1) → 위치 1500 → 서버B (시계방향 첫 서버)
키2 → hash(키2) → 위치 6000 → 서버C
키3 → hash(키3) → 위치 9000 → 서버A (링을 돌아서)

서버 추가/제거 시 재할당 최소화

서버 추가 예시

  • 새 서버D가 위치 3000에 추가된다

  • 기존 서버B(5000)에 있던 키 중 위치 1000~3000 사이의 키들만 서버D로 이동한다

  • 나머지 키들은 그대로 유지된다

서버 제거 예시

  • 서버B(5000)를 제거한다

  • 서버B의 키들만 다음 서버C로 이동한다

  • 다른 서버의 키들은 영향을 받지 않는다

가상 노드(Virtual Nodes)를 통한 부하 분산

실제 구현에서는 각 서버를 여러 개의 가상 노드로 복제하며, 이를 통해 더 균등하게 데이터를 분산시킬 수 있고, 서버 추가/제거 시의 영향도 여러 서버에 분산될 수 있다.

서버A → 가상노드A1(위치 1000), 가상노드A2(위치 4000), 가상노드A3(위치 7000)
서버B → 가상노드B1(위치 2000), 가상노드B2(위치 5000), 가상노드B3(위치 8000)

실제 사용 예시 (Redis 클러스터 / TypeScript)

interface Server {
  id: string;
  position: number;
}

class ConsistentHash {
  private servers: Server[] = [];
  private readonly RING_SIZE = 2**32;

  private hash(key: string): number {
    // 간단한 해시 함수 (실제로는 MD5, SHA-1 등 사용)
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
      const char = key.charCodeAt(i);
      hash = ((hash << 5) - hash) + char;
      hash = hash & hash; // 32bit 정수로 변환
    }
    return Math.abs(hash) % this.RING_SIZE;
  }

  addServer(serverId: string): void {
    const position = this.hash(serverId);
    this.servers.push({ id: serverId, position });
    this.servers.sort((a, b) => a.position - b.position);
  }

  removeServer(serverId: string): void {
    this.servers = this.servers.filter(server => server.id !== serverId);
  }

  getServer(key: string): string | null {
    if (this.servers.length === 0) return null;
    
    const hashValue = this.hash(key);
    
    // 시계방향으로 첫 번째 서버 찾기
    for (const server of this.servers) {
      if (server.position >= hashValue) {
        return server.id;
      }
    }
    
    // 링을 돌아서 첫 번째 서버
    return this.servers[0].id;
  }
}

이러한 방식으로 안정해시는 서버 변경 시 평균적으로 전체 키의 1/n만 재배치하게 되어, 시스템의 안정성과 성능을 크게 향상시킬 수 있다.

안정 해시의 이점

  • 서버가 추가되거나 삭제될 떄 재배치되는 키의 수가 최소화된다.

  • 데이터가 보다 균등하게 분포하게 되므로, 수평적 규모 확장성을 달성하기 쉽다.

  • 핫스팟(hotspot) 키 문제를 줄일 수 있다. 특정한 샤드(shard)에 대한 접근이 지나치게 빈번하면 서버 과부하 문제가 생길 수 있다. 안정 해시는 데이터를 좀 더 균등하게 분배하므로 이런 문제가 생길 가능성을 줄인다.

    • 핫스팟(hotspot) 키 문제: 데이터 상호 작용이 빈번한 유명 유저들이 한 샤드에 몰리는 문제를 일컫는다.

결론

안정 해시는 디스코드의 채팅 어플리케이션, 아파치 카산드라 클러스터에서의 데이터 파티셔닝, 아마존 다이나모 데이터베이스의 파티셔닝 관련 컴포넌트 등에 활용되며 실제로도 널리 쓰이는 기술이다.

- 컬렉션 아티클