[Chapter 05] Q&A

[zziri]

[Chapter 05] 안정 해시 설계

• 궁금한 점 혹은 이야기하고 싶은 주제 코멘트로 정리
• 추가로 같이 보면 좋을 것 같은 기술 블로그, 아티클 등 공유

[zziri]

지훈

• 전통적인 해시 설계 기법을 적용했을 때, 서버가 사용불가한 상태가 된 경우 대규모 캐시 미스가 발생하는 이유?
  • 예를 들어서 같은 key값으로 특정 메타 데이터를 조회하기 위해서 GET 요청을 한다고 할 때, 기존에 요청하던 서버가 아닌 다른 서버로 이관(?)되었다면 기존 서버에서 가지고 있던 로컬 캐시가 유효하지 않아서 발생할 수 있음
  • 그런데 로컬 캐시가 아니라 리모트 캐시(Redis 등)라면 대규모 캐시 미스가 발생할까...?
• 가상 노드의 위치는 어떻게 결정?
  • https://www.joinc.co.kr/w/man/12/hash/consistent
    • 가상 노드들은 랜덤함수, 해시, CRC32와 같은 알고리즘을 이용해서 무작위로 hash ring에 배치를 한다. 무작위로 배치가 된다면 (이론적으로) 현재 노드 N-1다음에 N-2가 올 확률은 1/Node 갯수 이 된다.
  • 딱히 모범답안이 있는 것은 아니고 파티션의 표준 편차를 줄이도록 하면 되는 듯

[travelbeeee]

현석

• 이번 챕터는 지훈님이 질문하신 부분 외에는 다른 궁금증은 없었습니다.
• Java HashMap 원리
  • Java 8 이후부터는 해시함수 + 보조해시함수 + Seperate Chaining 방식 사용
  • Seperate Chaining 방식에서 충돌로 인해 하나의 해시에 데이터가 8개 이상이라면 Linked List 대신에 Red-Black Tree 자료구조를 이용
  • 정리글
  • 이번 챕터에서는 요청 또는 데이터를 균등하게 나누는데 초점을 맞춘 해시 기술이였지만, 알아두면 좋은 지식(?) 느낌으로 추가합니다.

[easyfordev]

이지

• 질문 : 가상 노드를 늘리면 (무조건) 좋은가?에 대해 그렇지 않다. 가상 노드 데이터를 저장할 공간은 더 많이 필요하게 될 것이다. tradeoff가 있다. 라고 했는데... 무슨 말인지 살짝 헷갈려서... 설명해주실 분 있으신가요?

  • 가상 노드가 많아지면, 그만큼 key를 놓을 공간(파티션)의 크기가 작아진다는 의미일까요?
  • 진짜 서버는 1대이니까, 여기에만 공간(스토리지)가 있는 것이라서 가상노드가 많아져도 어차피 공간의 크기는 똑같은 것이 아닌....가요?
  • 가상 노드에 대한 메타정보를 저장할 공간이 필요하다는 의미인듯
  • key들을 결국 가상 노드에서 가지고 있어야 하니까 공간이 필요하다
  • 가상 노드 이미지

• 공유 : 안정 해시 기술 적용 사례로 AWS의 DynamoDB의 파티셔닝 관련 컴포넌트, Apache Cassandra 클러스터에서의 데이터 파티셔닝이 언급되었는데, 둘 다 NoSQL 분산(Distributed) 데이터 베이스이다.

  • 파티셔닝이란? 파티션 키를 기준으로 데이터의 해시 값을 구해서, 이를 기준으로 각 노드에 분산하여 저장하는 것
  • https://goyunji.tistory.com/95

[meloncha]

민석

안정 해시가 최고의 해답일까?

https://dgryski.medium.com/consistent-hashing-algorithmic-tradeoffs-ef6b8e2fcae8

• Jump Hash

• Multi-Probe Consistent Hashing

• Rendezvous Hashing

• Maglev Hashing

• 알고리즘 별로 걸리는 시간

• CHash(Consistent Hashing) 의 경우 시간 복잡도 O(logN) 이다

https://itnext.io/introducing-consistent-hashing-9a289769052e

Rendezvous Hashing

type RendezVous struct {
    nodes []Node
}

type Node struct {
    id string
}

func (r *RendezVous) Get(key string) (*Node, error) {
    length := uint32(len(r.nodes))
    var maxHashValue = hash(key, r.nodes[0].id, length)
    result := 0

    for index, node := range r.nodes[1:] {
        currentHashValue := hash(key, node.id, length)
        if currentHashValue > maxHashValue {
            maxHashValue = currentHashValue
            result = index
        }
    }
    return &r.nodes[result], nil
}

• 각 노드들을 순회하면서 노드와 키를 기반으로 해시 값을 만들어 가장 큰 값에 해당하는 노드를 반환한다
• 가장 높은 무작위 가중치 해시
• 단점 : 시간복잡도 O(N) (N : 노드의 수)
• 제한된 수의 노드를 사용할 경우 안정해시보다 효율적이다 (가상 노드를 사용하지 않아서 메모리 절약)

Jump Consistent Hashing

int32_t JumpConsistentHash(uint64_t key, int32_t num_buckets) { 
  int64_t b = ­1, j = 0;
  while (j < num_buckets) { 
    b=j;
    key = key * 2862933555777941757ULL + 1; // Did you say magic number?
    j = (b + 1) * (double(1LL << 31) / double((key >> 33) + 1));
  }
  return b;
}

• Bucket size는 목적지까지의 거리. Key는 말
• 특수 제작된 주사위를 던져서 말을 앞으로 전진시켜 몇 번만에 목적지를 뛰어 넘는지를 계산
• 멀리 뛸 확률은 점점 줄어든다
• 이 확률이 1/N(거리) 로 맞추면 공정한 게임판이 된다
• 목적지까지의 거리(버킷 크기)가 4이면 1, 1/2, 1/3, 1/4 의 확률을 가진다
• 솔직히 이해 안됨..

장점

• 메모리 오버해드 없이 노드간의 워크로드 분산을 개선
• 가상 노드 개념이 더 이상 필요없다
• 반환되는 값이 0 ~ N-1 사이의 정수이며 임의의 노드 이름을 지원하지 않는다
• 서버 이름이 아닌 샤드 번호를 제공하는 것이 유용하다
• 임의의 노드를 추가하고 삭제할 때는 사이의 노드가 아닌 끝만 가능하므로 임의의 노드를 삭제할 수 없다
• 샤딩 컨텍스트에서는 유용하지만 로드 밸런싱에는 유용하지 않다

[KKambi]

한비

How discord scaled elixir to 5000000 concurrent users

https://discord.com/blog/how-discord-scaled-elixir-to-5-000-000-concurrent-users

elixir : erlang vm이라는 가상머신 위에서 작동하는 언어. 함수형 / 분산처리 / 동시성 / 실시간 등의 특징.

디스코드 pub/sub 기능

• 어떤 유저가 온라인 상태가 되고 특정 채널에 연결되면, 그 채널은 연결된 세션들에게 해당 유저의 존재를 publish
• 매우 큰 채널의 경우 메세지 큐가 감당하지 못하는 문제 ex) 3만명의 동시 사용자가 있는 Overwatch 디스코드 서버

Message Fanout

• Erlang 프로세스의 메세지 통신은 대규모 채널에서 저렴하지 않음
• 병렬 프로세스를 만드는 일은 이벤트의 순서에 의존하는 디스코드 클라이언트에 맞지 않았음
• 원격 노드들의 PID를 모아서 일관되게 해싱
• 특정 파티셔너가 오버로드되지 않고, 선형화 기능을 보장할 수 있다고 함 (erlang의 특정 함수들을 이용해 달성할 수 있다는데 이해 못함)

결론

• 디스코드는 Job을 균등하게 분배하기 위해 안정 해시를 사용

[kihyun-yang]

기현

• 저도 이번 챕터 내에서는 따로 궁금증은 없었고, consistent hashing 개념을 통해 데이터를 분산시키는 memcached나 카산드라와 같은 스토리지도 있다고 해서 관련내용 공유드립니다.
  • https://docs.datastax.com/en/cassandra-oss/3.0/cassandra/architecture/archDataDistributeHashing.html
  • https://meetup.toast.com/posts/58
  • https://charsyam.wordpress.com/2011/11/25/memcached-%EC%97%90%EC%84%9C%EC%9D%98-consistent-hashing/