devcken.io

Thoughts, stories and ideas.

Consistent Hashing, a guide & Go libarary

본문: https://medium.com/@sent0hil/consistent-hashing-a-guide-go-implementation-fe3421ac3e8f

Consistent Hashing은 믿을 수 없을 만큼 간단하면서도 매우 강력하지만, 앉아서 직접 해보기 전까지는 그것이 무엇인지 잘 이해하지 못했습니다. Consistent Hashing에 대해 이야기하기 전에, 해결하려고 하는 문제가 무엇인지를 이해해야 합니다:

분산 네트워크 내에서 키를 저장하고 조회할 서버가 어떤 것인지 어떻게 결정해야 할까요? 요구사항은 다음과 같습니다. 모든 노드가 상대적으로 동일한 수의 키를 가져오고, 최소한의 키가 움직이도록 노드를 추가하거나 제거할 수 있어야 합니다.

몇 가지를 가정해보죠: 네트워크 내에는 Chico, Harpo, Groucho 그리고 Zeppo라는 네 개의 서버가 존재합니다. 네 개 서버 모두 동일하지만, 서버로에 대해서 알지 못합니다.

이 예제를 간단하게 하기 위해, 키를 증가하는 정수라고 하겠습니다. 보통 여러분은 체크섬에 대해 키를 실행하여 숫자를 반환합니다. 이 숫자를 얻으면, 노드 수에 맞춰 그 숫자의 모듈로를 취할 수 있습니다. 이는 네트워크가 안정적인 경우(즉, 네트워크를 떠나거나 들어오는 노드가 없는 경우) 놀라울 만큼 잘 동작합니다.

하지만, 만약 하나의 노드, 즉 Harpor가 중지되는 일이 발생하면 어떨까요? 그러면 큰 문제가 발생합니다. 동일한 Hash 함수를 사용하는 경우, 동일한 결과를 갖지만, 모듈로 연산을 적용하면 노드의 개수가 한 개 줄어듦으로 이전과 다른 결과를 얻게 됩니다.

모든 노드의 모든 키 역시 대부분 다시 매핑되어야 하는지 확인해야 합니다. 이는 합리적이지 않습니다. 제대로 동작하고 있는 서버의 키를 다시 매핑해야 하나요? 제 의견에 찬성하시나요? 이제 consistent hashing에 대한 요구 사항에 도달했습니다.

Consistent hashing은 해시 테이블의 크기가 변경되고 consistent hasing이 사용되는 경우, 오직 K/n 개의 키만이 평균적으로 다시 매핑되는 특별한 종류의 hashing입니다. 여기서 K란 키의 개수이며 n은 슬롯의 개수입니다.

출처: https://en.wikipedia.org/wiki/Consistent_hashing

위에서 consistent hashing을 사용했더라면, Harpo의 키만 옮겨지면 됐을 겁니다. 보통 대부분의 포스트에서 이를 단위 서클의 그림을 이용해 그점에 대해서 설명합니다. 그렇게 해보죠:

노드가 단위 서클에 배치되는지는 당분간 제쳐두도록 하겠습니다. 키의 해시 상에 모듈로 함수를 적용하는 대신, 해시를 단위 서클 상에 매핑하겠습니다(말 뿐인 것 같지만 곧 구현하게 될 겁니다). 키가 매핑되는 노드를 결정하기 위해, 노드를 찾을 때까지 단순히 시계 방향으로 진행합니다. 그러므로 1번 키는 Harpo에 저장되고 그로부터 조회되어야 합니다.

만약 Harpo가 중지된다면 어떨까요? 다른 노드로부터 1번 키를 얻거나 조회해야 할 겁니다. 하지만 나머지 키의 매핑이 변하지 않았는지를 유의해야 합니다. 변경된 유일한 키는 Harpo 노드에서 사용되던 것들입니다. 이는 새로운 노드를 추가하는 경우에도 동작합니다. 네트워크에 Gummo를 추가했다고 해보죠. 기존 키의 위치를 변경할 필요가 없습니다.

또한 Consistent hashing은 노드의 크기가 다른 상황도 커버합니다. 여러분이 해야할 것은 가상 노드를 단위 서클에 생성하는 것입니다. 여러분이 선택한 해시 함수에 따라, 가상 노드는 단위 서클 상에 무작위로 위치하도록 만들어질 수 있습니다. 노드가 좀 더 많은 용량을 갖도록 하려면, 더 많은 가상 노드들을 추가해야 합니다. 이런 방법으로 노드가 중지된 경우, 키가 단순히 다음 노드가 아닌 다른 노드에 고르게 분산됩니다.

구현

여기서 좀 더 진행해 Go로 consistent hash 라이브러리를 구현해보겠습니다. 좋은 구현을 찾고 모든 곳에 print 구문을 넣고 코드를 변경할 때까지 그것을 이해하지 못했습니다. 이 구현은 stathat의 구현에 상당히 영감을 받았습니다. 원래의 논문은 구현을 위해 트리를 사용해 호출하지만, 저는 stathat이 한 방법을 더 선호합니다.

인터페이스를 정의해보죠:

// Initializes new distribute network of nodes or a ring.
func NewRing() *Ring  
// Adds node to the ring.
func (r *Ring) AddNode(id string)  
// Removes node from the ring if it exists, else returns 
// ErrNodeNotFound.
func (r *Ring) RemoveNode(id string) error  
// Gets node which is mapped to the key. Return value is identifer
// of the node given in `AddNode`.
func (r *Ring) Get(key string) string  

crc32를 사용해 키의 체크섬을 생성할 겁니다. crc32가 하는 일과 그 방법을 설명하는 것은 이 포스트의 범주를 벗어납니다. 입력이 주어지면, 32 uint가 반환된다고 알고 있으면 됩니다. 이 경우에 입력은 노드의 IP 주소입니다.

그것의 요점은 노드 아이디의 체크섬 결과를 배열에 둔다는 것입니다. 각 키에 대해 체크섬을 실행하고 키가 추가되어야 하는 위치를 정하고 그 위치와 가장 가까운 노드를 반환합니다. 배열의 범위를 넘으면, 첫번째 노드를 반환합니다.

먼저, Ring을 정의해보죠. 이는 Node의 컬렉션입니다.

package consistenthash  
// Ring is a network of distributed nodes.
type Ring struct {  
  Nodes Nodes
}
// Nodes is an array of nodes.
type Nodes []Node  
// Node is a single entity in a ring.
type Node struct {  
 Id     string
 HashId uint32
}

다음으로, RingNode를 위한 초기화 함수를 작성해보죠:

package consistenthash  
func NewRing() *Ring {  
  return &Ring{Nodes : Nodes{}}
}
func NewNode(id string) *Node{  
  return &Node{
    Id        : id,
    hashedKey : crc32.Checksum([]byte(id)),
  }
}

이제 드디어 AddNode를 채워넣을 준비가 됐습니다:

func (r *Ring) AddNode(id string) {  
  node := NewNode(id)  
  r.Nodes = append(r.Nodes, node)
  sort.Sort(r.Nodes)
}

sort.Sort를 실행할까요? 단위 서클로 돌아가서 봐야 합니다. 정확하게 단위 서클을 어떻게 구현할까요? 한 가지 방법은 배열의 엔트리 내에 첫번째 아이템을 가리키는 마지막 아이템을 두는 것입니다. 이를 위해 연결 리스트를 사용할 수 있지만, 그것이 불필요한 이유에 대해서 곧 충분히 알게 될 겁니다.

지금까지 한 것을 실행하면, Nodesort.Sort 인터페이스를 구현하지 않았기 때문에 Go 컴파일러가 여러분에게 무언가를 던질 겁니다. 쉽게 해결할 수 있습니다:

package consistenthash  
func (n Nodes) Len() int           { return len(n) }  
func (n Nodes) Less(i, j int) bool { return n[i].HashId < n[j].HashId }  
func (n Nodes) Swap(i, j int)      { n[i], n[j] = n[j], n[i] }  

이 모든 것의 요점인 Get을 구현해보겠습니다:

func (r *Ring) Get(key string) string {  
  searchfn := func(i int) bool {
    return r.Nodes[i].HashId >= crc32.Checksum([]byte(key))
  }
  i := sort.Search(r.Nodes.Len(), searchfn)
  if i >= r.Nodes.Len() {
    i = 0
  }
  return r.Nodes[i].Id
}

sort.Search는 바이너리 검색을 사용해 배열 내에서 기존의 노드를 찾아냅니다. 존재하지 않는 경우 노드가 추가되어야 할 위치를 반환합니다. 노드 체크섬이 마지막 노드보다 크다면, 첫번째 노드에 그것을 추가합니다. 그리고 그게 답니다.

코드의 나머지 부분을 보려면 여기에 약간의 테스트와 함께 오픈 소스화되어 있습니다.

처음에 consistent hashing이 믿을 수 없을 만큼 간단하고도 강력하다고 말한 것을 기억하나요? 아직 저를 믿나요? consistent hashing이 분산 시스템에 관해 좀 아는 Akamai의 논문에서 처음 도입되었다는 것을 알아둬야 합니다. consistent hashing의 향상된 버전은 분산 해시 테이블인 Chord 알고리즘에서 사용됩니다(이전 버전에서는 Chord가 Amazon DynamoDB보다 못하다고 하는데, 이는 잘못된 것입니다).

저는 여전히 chord를 읽고 이해하는 과정에 있으며, 구현하는 것은 말할 것도 없고, 일단 완료되면 포스트할 겁니다. 저는 포스트를 쓰는 것은 물론이거니와, consistent hashing에 대해 배우고, 구현하는 것이 매우 재미있습니다. 여러분은 그것을 배우거나 구현하기를 바랍니다. 오류나 더 좋다고 말할 수 있는 무언가를 찾는다면, @sent-hil로 트윗해주시기 바랍니다.