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

 

전통적인 해시 테이블

---

• 전통적인 해시 테이블에서 키를 배분할 때는 일반적으로 다음과 같은 방식을 사용합니다.
• ServerIndex = hash(key)%N (N은 서버의 수)
• 이는 서버(또는 데이터)의 개수가 고정되어 있으면 문제가 없습니다. 하지만 서버가 추가되거나 삭제되면, 기존의 대부분 키에 대한 서버 인덱스가 달라져 재해싱해야 하는 문제가 발생합니다.

 

 

안정 해시(Consistent Hashing) 등장 배경

---

• 대규모 트래픽 처리를 위해서는 서버 수를 탄력적으로 조절할 수 있는 ‘수평적 확장성’이 매우 중요합니다.
• 하지만 위와 같은 전통적 방식으로는 서버가 추가/삭제될 때마다 재해싱 부담이 커집니다.
• 이를 해결하기 위해 나온 것이 안정 해시(Consistent Hashing) 기술입니다.

 

안정 해시가 제공하는 이점

---

• 서버 추가/삭제 시 재배치가 최소화: 기존 해시 테이블의 % 연산 방식보다 매우 적은 수의 키만 옮기면 됩니다.
• 데이터 균등 분산: 해시링에서 서버 노드가 고루 분포해 있으면, 자연스럽게 데이터 역시 고르게 분산됩니다.
• 핫스팟(Hotspot) 키 문제 감소: 특정 노드의 트래픽 몰림 현상 가능성이 줄어듭니다.

 

안정 해시(Consistent Hashing) 기법

---

• 안정 해시는 해시 테이블의 크기가 변경될 때 평균적으로 오직 K/N개의 키만 재배치하는 해시 기술입니다.(K는 키 개수, N은 서버 개수)
• 아래 글을 읽고, 제시되는 코드로 이해하는 것이 더 직관적입니다.

1. Hash Ring(해시 링) 구성

• 전통적인 해시 테이블과 다르게 모듈러 연산으로 대상을 탐색하지 않고, 안정 해시는 해시 링을 사용합니다. 해시 함수를 통해 0부터 특정수까지 범위를 갖는 원형 링(자바에서는 treeMap 보통 사용)을 만들어 서버와 데이터를 링 위의 해시 값으로 매핑합니다. 그리고 어떤 키가 어느 서버로 가야 할지는 “시계방향으로 만나는 첫 번째 서버” 방식으로 결정합니다.

2. 첫 번째로 만나는 서버

• 데이터를 통해 만든 키값이 링 위에서 시계방향으로 이동했을 때 가장 먼저 만나는 서버 노드를 해당 데이터의 실제 저장 서버로 결정합니다.
• 가상 노드(Virtual Node) 기법 : 물리 서버 하나를 해시 링에 여러 지점(노드)으로 등록합니다. 이를 통해 특정 구간에 몰리는 문제를 방지하고, 분산을 더 고르게 할 수 있습니다.

3. 재배치 최소화

• 서버가 추가되면, 새로 추가된 서버 위치의 일부 키만 새 서버로 이전됩니다.
• 서버가 삭제되면, 해당 서버에 속했던 키들만 인접한 서버로 이전됩니다.
• 전체 키 중 일부만 움직이므로 재해싱 부담이 최소화됩니다.

4. 자바로 구현한 안정 해시

• 1 ) 초기 서버 정보들을 전달하여 treeMap에 넣습니다. treeMap의 키는 long이고, 저장 value는 서버 정보가 됩니다. 이때 키값은, 초기 전달되는 서버 객체를 잘 가공해서 long으로 만들어낸 다음 저장합니다.
• 2 ) 어떤 데이터를 저장할 건데, 이 데이터를 어느 서버에 접근시켜야 하는지를 가져오는 함수는 get 함수입니다. 저장할 데이터를 잘 가공하여 키값(long 변수)으로 만듭니다. 그 후 treeMap의 ceilingEntry 함수를 이용해, 만들어낸 키값 보다 크거나 같은 가장 작은 키값을 갖는 서버 정보를 가져옵니다. 이때 크거나 같은 게 없다면, 가장 작은 키값을 갖는 서버를 갖고 옵니다. 이렇게 특정 키값보다 큰 키를 갖는 서버가 없을 경우, 첫 번째 키값을 갖는 서버를 가져오기 때문에 “링” 형태라고 부르는 것입니다.

 

class ConsistentHash<V>
{
	 private final TreeMap<Long, V> ring = new TreeMap<>();
	 private final int replicas;// 서버당 가상노드 개수
	 private final MessageDigest md;

	public ConsistentHash(int replicas, Collection<V> servers)throws Exception {
		try {
			
		    this.replicas = replicas;// 가상노드 수 기록
		    this.md =  MessageDigest.getInstance("SHA-256"); //SHA-256 해시 엔진 준비
		    
		    for (V node : servers)
		    {
		    	add(node);// 초기 서버들 링에 삽입
		    }
		    
		}catch(Exception e)
		{
			throw e;
		}

	}
	public void add(V server)
	{	
		// 서버 1대를 링에 등록, 해당 서버를 링에 등록할 때 여러 곳에 등록해 놓는다.(이게 가상 노드 개념)
	    for (int i = 0; i < replicas; i++)// 가상노드 수만큼 반복
	    {
	        String token = server.toString() + "#" + i;// 예: "S1#0", "S1#1"…
	        ring.put(hash(token), server);// 좌표 ↦ 서버 매핑 저장
	    }
	}
	public V get(Object key)
	{
		// 키 값을 통해 해시링 위의 임의의 좌표 h를 구해온다.
	    long h = hash(key.toString());
	    // ceilingEntry를 사용해 키값 h보다 크거나 같은 객체중 가장 키 값이 작은 노드를 구해온다.
	    // 이게 시계방향으로 회전한다는 의미
	    Map.Entry<Long, V> e = ring.ceilingEntry(h);
	
	    if (e == null)// h보다 크거나 같은 키를 갖는 서버 객체가 없다면, ring의 첫번 째 객체 반환
	    	e = ring.firstEntry();
	
	    return e.getValue();
	}
	private long hash(String key) {
	    //  digest() 는 바이트[32] 생성 → 이후 상위 8바이트만 써서 64bit 좌표화
	    byte[] h = md.digest(key.getBytes(StandardCharsets.UTF_8));
	    // digest() : SHA-256(key) 계산해 32바이트 배열 반환
	    // 상위 8바이트만 Long 으로 wrap → 충돌률 극히 낮은 2^64 공간
	    return ByteBuffer.wrap(h).getLong();
	}
}