[번역] Redis Cluster Specification: (2) Overview of Redis Cluster main components

원문: https://redis.io/topics/cluster-spec

Keys distribution model

키 스페이스는 16384개의 슬롯으로 나누어지며, 실질적으로 16384개의 마스터 노드의 클러스터 사이즈는 실질적인 상한이 설정이다. (그러나 추천하는 최대 노드의 수는 1000개의 노드까지이다.)

클러스터 내의 각 마스터 노드는 16384개의 해시 슬롯에 대한 서브셋을 다룬다. 클러스터는 클러스터 재설정이 진행되고 있지 않을 때 안정적이다. (예를 들어, 해시 슬롯이 한 노드에서도 다른 한 노드로 이동되고 있거나 할 때). 클러스터가 안정적일 때, 단일 해시 슬롯은 하나의 노드에서만 다뤄질 것이다. (그러나 슬롯을 가지는 노드는 하나 이상의 리플리카를 가질 수도 있는데, 네트워크 파티션이나 실패 등의 이유로 마스터 노드를 대체할 수도 있고, 그렇기 때문에 오래된(stale) 데이터를 받아들일 수 있다면, 읽기 오퍼러에이션을 확장시킬 수 있다.)

키를 해시 슬롯에 맵핑하기 위해서 사용되는 기본 알고리즘은 아래와 같다. (이 규칙에 대한 해시 태그의 예외에 대해서는 다음 단락을 참고...)

HASH_SLOT = CRC16(key) mod 16384

The CRC16 is specified as follows:

• Name: XMODEM (also known as ZMODEM or CRC-16/ACORN)
• Width: 16 bit
• Poly: 1021 (That is actually x^16 + x^12 + x^5 + 1)
• Initialization: 0000
• Reflect Input byte: False
• Reflect Output CRC: False
• Xor constant to output CRC: 0000
• Output for "123456789": 31C3

CRC16의 출력 비트 16개 중에서 14개가 사용된다. (이것은 위의 공식에서 모듈러 16384 연산이 있는 이유이다.)

우리의 테스트에서 CRC16은 서로 다른 종류의 키를 16384개의 슬롯들로 고르게 분배하는 것에 아주 잘 작동했다.

Note: CRC16 알고리즘에서 사용된 구현에 대한 레퍼런스 이 문서의 Appendix A에서 확인할 수 있다.

Keys hash tags

해시 슬롯의 계산에는 예외가 있고, 이것은 해시 태그(hash tags)를 구현하기 위해서 사용된다. 해시 태그는 여러 키가 동일한 해시 슬롯에 할당되도록 하는 방법이다. 이것은 레디스 클러스터에서 멀티 키(multi-key) 오퍼레이션을 구현하기 위해서 사용된다.

해시 태그를 구현하기 위해서, 특정 조건에서 키에 대한 해시 슬롯은 약간 다른 방식으로 계산된다. 만약, 키가 "{...}" 패턴을 포함하고 있다면, 해시 슬롯을 얻기 위해서 {와 }사이의 부분 문자열만 해시된다. 그러나 {나 }가 여러번 나타날 수 있기 때문에, 이 알고리즘은 다음과 같은 룰에 의해 지정된다.

• IF 키는 { 문자를 포함한다.
• AND IF {의 오른쪽에 } 문자가 있다.
• AND IF 처음 나타난 {와 처음 나타난 }사이에 하나 이상의 문자가 있다.

그러면 키를 해싱하는 대신, 처음 나타난 {와 다음에 처음 나타난 }사이의 문자만 해시된다.

Examples:

• {user1000}.following 와 {user1000}.followers 2개의 키는 해시 슬롯을 계산하기 위해서 부분 문자열 user1000만 해시되기 때문에, 동일한 해시 슬롯으로 해시된다.
• foo{}{bar}는 처음 나타난 {에 }가 잇따라 나오고 가운데에 문자가 없기 때문에, 보통의 경우와 같이 키 전체가 해시된다.
• foo{{bar}}zap는 부분 문자열 {bar가 해시되는데, 그것이 처음 나타나는 {와 그 오른쪽에 처음 나타나는 }사이의 부분 문자열이기 때문이다.
• foo{bar}{zap}은 부분 문자열 bar가 해시되는데, 알고리즘은 첫번째로 유효하거나 유효하지 않은(내부에 바이트가 없는) {와 }의 일치에서 멈추기 때문이다.
• 알고리즘에 따라서, 만약 키가 {}로 시작하면, 이것은 키 전체가 해시되는 것이 보장된다. 이것은 바이너리 데이터를 키 이름으로 사용할 때 유용하다.

다음은 Ruby와 C로 작성된 HASH_SLOT의 구현이다.

Ruby example code:

def HASH_SLOT(key)
    s = key.index "{"
    if s
        e = key.index "}",s+1
        if e && e != s+1
            key = key[s+1..e-1]
        end
    end
    crc16(key) % 16384
end

C example code:

unsigned int HASH_SLOT(char *key, int keylen) {
    int s, e; /* start-end indexes of { and } */

    /* Search the first occurrence of '{'. */
    for (s = 0; s < keylen; s++)
        if (key[s] == '{') break;

    /* No '{' ? Hash the whole key. This is the base case. */
    if (s == keylen) return crc16(key,keylen) & 16383;

    /* '{' found? Check if we have the corresponding '}'. */
    for (e = s+1; e < keylen; e++)
        if (key[e] == '}') break;

    /* No '}' or nothing between {} ? Hash the whole key. */
    if (e == keylen || e == s+1) return crc16(key,keylen) & 16383;

    /* If we are here there is both a { and a } on its right. Hash
        * what is in the middle between { and }. */
    return crc16(key+s+1,e-s-1) & 16383;
}

Cluster nodes attributes

모든 노드는 클러스터 내에서 유니크한 이름을 가진다. 노드 이름은 160비트 랜덤 숫자의 헥사 표현식이고, 이것은 노드가 처음 시작될 때 획득하게 된다. (보통은 /dev/random을 사용한다.)

노드는 그 ID를 노드 구성 파일에 저장하고, 적어도 시스템 관리자에 의해서 노드 구성 파일이 삭제거나, 또는 CLUSTER RESET 커맨드로 hard reset이 실행되거나 하지 않는 한, 같은 ID를 영원히 사용하게 된다.

노드 ID는 전체 클러스터에서 모든 노드를 식별하기 위해서 사용된다. 주어진 노드ID에 대해서 IP 주소를 바꾸는 것은 노드 ID의 어떤 변경도 필요도 없이 가능하다. 클러스터는 IP/port 변화를 감지하고, 클러스터 버스를 통해 실행되는 가십 프로토콜을 이용해서 노드 정보를 재구성할 수 있다.

노드 ID는 각 노드와 관련된 유일한 정보가 아니라, 전역적으로 항상 일관된 유일한 것이다. 모든 노드는 다음과 같이 연관된 정보의 집합을 가진다. 일부 정보는 특정 노드의 클러스터 구성의 상세한 정보에 관한 것이고, 결국 클러스터 전체에서 일관된다. 일부 다른 정보는 노드가 ping된 마지막 시간과 같은 것으로, 각 노드의 로컬을 대신한다.

모든 노드는 다음과 같이 클러스터 내에서 알고 있는 다른 노드에 관한 정보를 유지한다.

• 노드의 ID
• IP
• Port
• 플래그셋
• 마스터 노드 정보 (플래그가 replica 일때)
• 노드가 마지막으로 ping을 보낸 시간
• 노드가 마지막으로 pong을 받은 시간
• 노드의 현재 configuration epoch (이 문서의 뒷 부분에서 설명)
• 연결 상태
• 서빙하는 슬롯의 집합

모든 노드 필드들에 대한 상세한 설명은 (explanation of all the node fields) CLUSTER NODES 문서에서 설명되어 있다.

CLUSTER NODES 커맨드는 클러스터 내에서 어느 노드에서나 실행될 수 있고, 쿼리된 노드가 가지고 있는 클러스터의 로컬 뷰에 따라서 클러스터의 상태와 각 노드의 정보를 제공한다.

다음은 3개 노드의 작은 클러스터의 한 마스터에서 CLUSTER NODES 커맨드를 실행한 샘플 출력이다.

$ redis-cli cluster nodes
d1861060fe6a534d42d8a19aeb36600e18785e04 127.0.0.1:6379 myself - 0 1318428930 1 connected 0-1364
3886e65cc906bfd9b1f7e7bde468726a052d1dae 127.0.0.1:6380 master - 1318428930 1318428931 2 connected 1365-2729
d289c575dcbc4bdd2931585fd4339089e461a27d 127.0.0.1:6381 master - 1318428931 1318428931 3 connected 2730-4095

위에서 리스팅된 각각 다른 필드는 순서대로 정렬되어 있다: 노드 ID, 주소:포트, 플래그, 마지막으로 ping한 시간, 마지막으로 pong을 받은 시간, 컨피그레이션 에포크, 연결 상태, 슬롯.
위 필드의 상세한 내용은 레디스 클러스터의 특정 부분에 대해서 이야기할 때 바로 설명하게 될 것이다.

The Cluster bus

모든 레디스 클러스터 노드는 다른 클러스터 노드로부터 들어오는(incoming) 커넥션을 받기 위한 추가적인 TCP 포트를 가지고 있다. 이 포트는 데이터 포트에 10000을 더해서 자동으로 만들어지거나, 또는 cluster-port라는 설정으로 지정될 수도 있다.

Example 1:

6379포트에서 클라이언트 커넥션을 수신 중이고, redis.conf에서 cluster-port 파라미터를 추가하지 않았다면, 클러스터 버스 포트는 16379가 사용된다.

Example 2:

6379포트에서 클라이언트 커넥션을 수신 중이고, redis.conf에서 cluster-port를 20000으로 지정했다면, 클러스터 버스 포트는 20000이 사용된다.

노드간(node-to-node)의 통신은 클러스터 버스와 클러스터 버스 프로토콜 (다양한 타입과 크기의 프레임으로 구성되는 바이너리 프로토콜)을 이용해서 독립적으로 이루어진다. 클러스터 버스 바이너리 프로토콜은 공식적으로 문서화되지 않았는데, 이것이 외부 소프트웨어 장치가 이 프로토콜을 이용해서 레디스 클러스터와 통신하기 위한 것이 아니기 때문이다. 그러나 레디스 소스코드 내에서 cluster.h와 cluster.c 파일을 읽음으로써 프로토콜에 관한 상세한 정보를 획득할 수는 있다.

Cluster topology

레디스 클러스터는 모든 노드가 다른 모든 노드와 TCP 커넥션을 사용해서 연결되는 풀 메시(full mesh)의 구성이다.

N개의 클러스터 내에서, 모든 노드는 N-1의 outgoing커넥션과, N-1의 imcoming 커넥션을 가진다.

이 TCP 커넥션들은 항상 keepalive으로 유지되며, 요청이 있을때마다 생성되는 것은 아니다. 노드가 클러스터 버스에서 ping에 대한 응답으로 pong 기다릴 때, 어떤 노드를 접속할 수 없는 상태로 표기할 만큼 충분히 오랜 시간이 지난 것이 아니라면, 처음부터 재연결함으로써 그 노드와의 커넥션을 새로 고치려고 할 것이다.

레디스 클러스터 노드들은 풀 메시를 구성하지만, 노드들은 정상적인 조건에서 노드간의 너무 많은 메시지 교환을 피하기 위해서 가십 프로토콜과 구성 정보 업데이트 메커니즘을 사용한다. 그래서 교환되는 메시지의 수는 기하급수적으로 많지는 않다.

Nodes handshake

노드는 클러스터 버스 포트로부터의 커넥션을 항상 받아들이고, 심지어 ping을 보낸 노드가 신뢰할 수 없더라도, 수신이 된다면 ping을 응답한다. 그러나 만약 보내는 노드가 클러스터의 일부로 간주되지 않는다면, 수신하는 노드에서 다른 모든 패킷들은 삭제될 것이다.

노드는 아래의 두 가지 방식으로만 클러스터의 멤버로서 다른 노드를 받아들인다:

• 만약 노드가 그 자신을 MEET 메시지로 나타낸다면, MEET 메시지는 PING 메시지와 정확히 같지만, 수신하는 노드에게 클러스터의 일부로 받아들이도록 한다. 오직 관리자가 다음의 커맨드로 요청할 때에만, 노드는 MEET 메시지를 다른 노드로 보낸다.

CLUSTER MEET ip port

• 만약, 이미 신뢰한 노드가 다른 노드에 대해서 가십 메시지를 보내면, 수신하는 노드는 다른 노드를 클러스터의 일부로 등록할 것이다. 그래서 만약 A가 B를 알고, B가 C를 안다면, 결국 B는 A에게 C에 관한 가십 메시지를 보낼 것이다. 이것이 일어나면, A는 C를 네트워크의 일부로 등록할 것이고, C와 연결하려고 시도할 것이다.

이것은 연결된 그래프에 노드를 연결하는 한, 결국 자동으로 완전히 연결된 그래프 형태가 된다는 것을 의미한다. 이것은 클러스터가 자동으로 다른 노드를 발견할 수 있지만, 시스템 관리자가 만든 신뢰할 수 있는 관계가 있는 경우에만 가능하다.

이 메커니즘은 클러스터를 더 견고(완고)하게 만들지만, 아이피 주소의 변경이나 네트워크 관련된 이벤트가 발생한 이후에 서로 다른 레디스 클러스터 실수로 섞여버리는 것을 막아준다.