안정 해시(Consistent Hashing)

 

 

 

🍀 해시를 사용해 요청을 분산하는 방법

N개의 캐시 서버가 있을 때 부하를 나누는 보편적인 방법으로는 해시 함수를 많이 사용한다.

MD5 (2^128): 속도가 보안보다 중요한 어플리케이션. SHA-256 에 비해 해시 공간은 작다.
SHA-256 (2^256): 더 긴 해시 크기와 더 강력한 암호화 속성. 속도는 MD5 에 비해 느리다. 매우 큰 해시 공간을 갖기 때문에 충돌이 거의 발생하지 않는다.

 

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

 

위와 같은 방법은 모든 상황에서 잘 동작할 것 같지만 서버 개수 (server pool)이 변경되거나 데이터가 한쪽에 몰리게되었을 때 문제가 발생한다. 키를 적절하게 재배치 하지 않는다면 부하가 몰리게 되고 대규모의 캐시 미스(cache miss)가 발생할 수도 있다.

 

이를 방지하려면 서버가 추가/삭제 되더라도 key 매핑 변경은 최소화 되어야 한다. 이때 사용하는 것이 바로 "안정 해시" 이다.

안정해시(Consistent Hashing)
MIT에서 처음 제안 되었으며 해시 테이블의 크기가 변경될 때, 평균적으로 오직  k(키의개수) / n(slot의 개수)  개의 키만 재배치하는 기술이다. 안정해시로 구현하지 않는 해시함수들은 데이터를 넣는 슬롯의 수가 줄어거나 늘어나면 많은 키가 재배치 되야 한다. 

 

 

 

🍀 안정해시는 어떻게 구현할까

예를 들어 해시 함수로 SHA-1을 사용한다고 가정하면, 해시 공간은 0 <= x < 2^160 까지 사용할 수 있다. 이를 시작과 끝을 붙이게되면 원형 리스트로 사용할 수 있다.

class ConsistentHash<T>(
    private val hashFunction: (String) -> Long, // 사용할 해시 함수
    private val circle: SortedMap<Long, T> = TreeMap() // 해시 값을 키로 하고 노드를 값으로 하는 정렬된 맵
){ 
   /* ... */ 
}
 
// 해시 함수의 예제 구현입니다. Java의 MessageDigest를 사용해 문자열의 SHA-1 해시 값을 생성합니다.
fun hashFunction(key: String): Long {
    val md = MessageDigest.getInstance("SHA-1")
    return md.digest(key.toByteArray())
             .fold(0L, { acc, byte -> (acc shl 8) + (byte and 0xff) })
}
    
fun main() {
    val consistentHash = ConsistentHash(::hashFunction)
}

 

이렇게 구성한 원형 리스트에서 서버(IP나 서버 이름)을 저장하고 사용할 hash key 들을 원하는 어느 지점에나 배치할 수 있게 구성한다.

• 이 때 기존의 해시가 아닌 균등 분포 (uniform distribution) 해시 함수를 사용해서 원형에 골고루 분포시킨다.

 

 

 

이런 식으로 원형으로 구성하게되면 추가/삭제에서 기존의 키 매핑 변경이 최소화 되도록 구현할 수 있다.

• 서버 조회
  해당 hash key로부터 시계방향으로 서버를 탐색하여 만난 첫번째 서버를 조회한다.
• 서버 추가
  서버를 추가하더라도 시계방향으로 hash key를 사용했던 기존 1개의 서버만 키가 변경된다. 다른 키는 재배치 되지 않는다.
• 서버 삭제
  서버 삭제도 마찬가지로 기존 조회 규칙에 따라 가운데 일부만 키만 재배치 되게 된다. 

 

class ConsistentHash<T>(
    private val hashFunction: (String) -> Long, // 해시 함수
    private val circle: SortedMap<Long, T> = TreeMap() // 해시 값을 키로 하고 노드를 값으로 하는 정렬된 맵
) {
    fun addNode(node: T) {
        // 노드를 해시링에 추가합니다.
        val hash = hashFunction(node.toString())
        circle[hash] = node
    }
 
    fun removeNode(node: T) {
        // 노드를 해시링에서 제거합니다.
        val hash = hashFunction(node.toString())
        circle.remove(hash)
    }
 
    fun getNode(key: String): T? {
        // 주어진 키에 대한 노드를 반환합니다.
        if (circle.isEmpty()) return null
        
        val hash = hashFunction(key)
        
        // 주어진 해시 값을 조회하지 못한 경우, 가장 가까운 다음 키를 찾습니다.
        if (!circle.containsKey(hash)) {
            // key 보다 순서가 같거나 큰 서브 맵 생성(tailMap)
            val tailMap = circle.tailMap(hash)
            // 다음 순서가 없다면 한 바퀴 돌아 첫번째 순서(circle.firstKey()) 사용
            hash = tailMap.firstKey() ?: circle.firstKey()
        }
        return circle[hash]
    }
}

 

 

🍀 이렇게 구현한 안정해시는 단점이 없을까?

• 위 그림처럼 각 서버 사이의 빈 공간(partition)을 항상 균등하게 유지하는게 불가능하다.
• 균등 분포 해시함수를 사용하더라도 키 분포 자체가 한쪽 빈 공간(partition)에 몰릴 수도 있다.

 

 

🔑 해결책: 가상 노드(virtual node) 사용

실제 서버(노드)를 1:1로 사용하지 않고, 가상의 노드를 만들어서 사용한다. 서버 1대가 여러개의 가상 노드를 가질 수 있다.

• 가상 노드의 개수를 늘림으로서 키의 분포를 균등하게 만들 수 있다.
• 노드의 개수가 많을 수록 표준편차가 적어져 더 균등해지겠지만 그만큼 메모리가 필요하고 추가/삭제시 가상노드를 많이 정리해야한다. 트레이드 오프를 고려해야한다.
• 참고로 가상 노드의 수는 무한정 늘릴 수 없다. 필요에 따라 전체 노드 수는 줄이고 성능이 좋은 서버가 많은 노드 수를 가져가게끔 구현할 수도 있다.

// 가상 노드를 나타내는 클래스
class VirtualNode<T>(
    private val physicalNode: T,
    private val replicaIndex: Int
) {
    fun getPhysicalNode(): T = physicalNode // 물리 노드 (실제 서버)
 
    fun getKey(): String = "$physicalNode#$replicaIndex" // 가상 노드의 고유 키(해시에 사용)
 
    fun isVirtualOf(node: T): Boolean = this.physicalNode == node
 
    override fun toString(): String = getKey()
}

class ConsistentHash<T>(
    private val hashFunction: (String) -> Long,
    private val numberOfReplicas: Int,
    private val circle: SortedMap<Long, VirtualNode<T>> = TreeMap()
) {
    fun addNode(node: T) {
        for (i in 0 until numberOfReplicas) {
            val virtualNode = VirtualNode(node, i)
            circle[hashFunction(virtualNode.getKey())] = virtualNode
        }
    }
 
    fun removeNode(node: T) {
        circle.entries.removeIf { it.value.isVirtualOf(node) }
    }
 
    fun getNode(key: String): T? {
        if (circle.isEmpty()) return null
 
        var hash = hashFunction(key)
        if (!circle.containsKey(hash)) {
            val tailMap = circle.tailMap(hash)
            hash = tailMap.firstKey() ?: circle.firstKey()
        }
        return circle[hash]?.getPhysicalNode()
    }
}

 

이렇게 구성함으로서 아래와 같은 이점을 챙길 수 있다.

• 서버 추가/삭제에도 키 매핑 변경이 최소화된다. cache miss 비율을 줄일 수 있다.
• 서버 추가/삭제를 굉장히 많이 하더라도 한쪽으로 몰리지 않고 데이터가 균등하게 분포된다.
• 위 장점으로 수평적 규모 확장이 쉬워지고 hot spot key (한쪽으로 키가 몰리는 현상)을 최소화 할 수 있다.

 

 

🍀 수치적으로 안정해시는 얼마나 좋아지는걸까?

라우팅을 만든다고 생각해보자. 여기에서 key 는 request url, ip 등이 될 것이고 키에 따라 적절한 서버를 찾아주어야한다.

• 이 때 key(요청)에 따라 어디로 라우팅 되었는지 캐싱해둔다. 이후 동일 요청은 라우팅 결정과정을 생략하고 바로 조회한다.
• 캐시가 없거나 해당 cache 를 사용했는데 정보가 유효하지 않은 경우 (노드가 변경된 경우) 다시 라우팅 결정과정을 거친다.

 

 

 

# 그냥 해시를 사용해서 구현했을 때

 

 

# 안정해시를 사용했을 때

 

 

# 안정해시를 사용하고, 가상 노드 수를 늘려 표준편차를 줄였을 때

• 가상 노드 수를 늘리면 확실히 더 골고루 분산된다. 다만 가상 노드 개수가 어느정도 차게되면 이후 수십만개를 늘려도 결과는 큰 변화가 없다는걸 인지하자. 이것도 트레이드 오프를 고려해야한다. 

 

 

 

🍀 이러한 기술들은 실제로 어디에 많이 쓰일까?

• 아마존 다이나모 데이터베이스(DynamoDB)의 파티셔닝 관련 컴포넌트
  Dynamo는 리더가 없는 복제시스템으로 모든 노드에서 쓰기 요청처리가 가능하다. 데이터를 여러 파티션에 분배해서 사용할 때 안정 해시를 이용해 데이터 리밸런싱을 최소화한다. (다이나모가 어떻게 구성되었는지 궁금하다면 >  좋은글1 / 좋은글2 )
  
  
• 아파치 카산드라(Apache Cassandra) 클러스터에서의 데이터 파티셔닝
  데이터를 클러스터 내의 여러 노드에 분산시키는데 파티셔닝 키를 해싱할 때 안정 해시를 사용한다.
  
  
• 디스코드(Discord)채팅 어플리케이션 - Elixir를 동시 사용자 오백만명으로 확장한 방법
  새로운 유저가 들어왔을 때, 전 세계에 거친 서버 클러스터 내에서 채널, 사용자 그룹을 특정 노드에 할당하여 사용한다. 이 때 안정 해시를 사용하여 노드의 추가/삭제에 따른 리밸런싱을 최소화한다. 
  
  
• 아카마이(Akamai) CDN
  사용자의 요청을 전 세계에 분산된 캐시(컨텐츠) 서버에 효율적으로 라우팅한다. 서버가 추가/삭제 되더라도 요청 리밸런싱이 최소화 되도록 안정 해시를 사용한다.
  
  
• 매그래프(Meglev) 네트워크 로드 밸런서
  구글이 만든 네트워크 로드밸런서로 트래픽을 균등하게 분산시킨다.

 

Choosing the Right DynamoDB Partition Key | Amazon Web Services

September 2022: This post was reviewed and updated for accuracy. This blog post covers important considerations and strategies for choosing the right partition key for designing a schema that uses Amazon DynamoDB. Choosing the right partition key is an imp

aws.amazon.com

 

 

 

이렇게 대규모 케이스가 아니더라도 당장 사용자수가 많아져 DB 스케일업을 고려해야한다면 파티셔닝을할지, 샤딩을 할지 고민하고 한다면 어떤 key를 기준으로 나눠야할지를 고민해보아야한다. MiRO 엔지니어링 - 데이터 샤딩 문제를 해결하기 위한 적절한 해시함수 선택