잘라내다

데이터베이스 중의 분할 방법은 데이터를 여러 노드의 디스크에 분할하여 데이터베이스에 대한 요구를 분산시키고 전체적인 토출량을 높이는 데 쓰인다.
기본적으로 서로의 노드가 공유하는 독립된 데이터가 있기 때문에 모든 노드는 자신이 맡은 데이터에 대해 조회를 실행한다.

구체적으로 말하면 응용 프로그램의 쓰기 요청이 주도적인 위치를 차지하고Primary/Backup 등 처리 시스템의 루트에서 부하가 분산되지 않은 상황에서 사용된다.
e.g)
- 줌 어플리케이션 서버의 동시 접속 수 제한
- 거대한 데이터를 처리할 때 버퍼가 넘쳐나고 디스크/IO가 발생합니다.

(appendix) Primary/Backup (Master/Slave)

응용 프로그램의 처리 시스템에 따라 대상 데이터베이스 노드를 연결하는 분할 방식을 전환합니다.
Leader 노드가 애플리케이션 업데이트를 수신하여 읽기 전용 Follower 노드로 복사할 때
업데이트 시스템은 Leader에 할당되고 시스템은 Follower에 할당된 요청을 참조하여 균형을 맞춥니다.
많은 응용 프로그램 라이브러리에서 환경 변수에서 연결 목표를 추적하여 사용할 수 있기 때문에 읽기 처리가 비례하는 WEB 응용 프로그램에서 이런 방식을 사용할 때가 있다.
그러나 Leader 노드는 여전히 하나의 노드이기 때문에 업데이트 요청이 백분율을 차지하면 이 요청은 이런 방식으로 분포되지 않을 수 있습니다.

분할 단위 식별

실제 데이터를 분할하고 배치할 때 데이터와 그 표지(음영 키)를 어떻게 분할하는지 결정합니다.
표준으로, 사용자 요청에서 얻은 데이터는 특정 노드에서 스캔을 통해 이루어진 분할 단위입니다.잘라낸 후에도 각 노드를 병렬로 조회하면 전체 처리량을 높일 수 없습니다.
이것은 데이터를 배치하는 노드의 분담과도 관계가 있지만 관건은 데이터를 특정 노드에 치우치지 않는 분할 단위로 나누는 것이다.다른 노드에 비해 이런 노드는 더 많은 요청 집중의 위험(이슈)을 초래할 수 있다.
WEB 응용 프로그램의 경우 사용자의 ID가 최대 공약수가 될 수 있고, 시간순으로 배열된 장부표의 경우 타임 스탬프가 분할 단위가 될 수 있지만 이는 응용 프로그램의 성질에 따라 달라지기 때문에 적절한 판단이 필요하다.

대상 노드 식별

데이터의 분할 단위와 커팅 키를 확정한 후 데이터를 배치할 노드를 분배합니다.
노드 수량의 여수에 따라 하데기를 포함하는지 여부를 결정하거나 지정하는 방법도 다양하지만 장단점이 있다.
range
이것은 특정 경계를 축으로 하여 배치 노드를 구분하는 방법이다.
예를 들어 개인을 대상으로 하는 WEB 서비스를 가정하면 회원 로그인 순서에 따라 순서의 사용자 ID를 하데기에게 분배하고 0~19999는 노드에게, 20000~299999는 노드에게 분배하며 정점을 경계점으로 목표 노드를 분배한다.
이 방법은 하데기에서 책임 노드를 쉽게 판단할 수 있지만 방문 모델에 따라 간단하게 핫이슈가 생길 수 있다.
앞의 예에서 시간 서열에 배열된 사용자가 반드시 똑같이 방문하지 않고 휴면 회원과 조치의 활동에 따라 부하가 특정 범위의 노드에 집중될 수 있다.
modulo
이것은 하데기를 노드의 여수로 나누어 노드를 놓는 방법을 계산하는 것이다.

key mod shard_num (+1)

혹은

hash(key) mod shard_num (+1)

import hashlib
from collections import defaultdict


def find_node(key, node_ids):
    """
    :type key: int
    :type node_ids: list of int
    :rtype: int
    """
    return int(hashlib.md5(str(key)).hexdigest(), 16) % len(node_ids)


node_ids = range(0, 10)
keys = [chr(i) for i in range(ord('a'), ord('z') + 1)]  # a..z
node_hash = defaultdict(list)
for key in keys:
    node_id = find_node(key, node_ids)
    node_hash[index].append(key)

제수 범위 내에서 노드를 분배하기 때문에 한편으로는 간단하고 일정량의 분산 설정을 기대할 수 있다
만약 노드 수 자체가 변화한다면 전체 노드에서 데이터를 이동하는 문제가 존재한다.
이 문제를 해결하는 방법은 중간에 설정된 가상 노드를 통해 데이터를 배치하는 노드를 확인하는 것이지 샤드 키에서 노드를 직접 추출하는 것이 아니다.
cookpad가 공개한 mixed_gauge 일 가상 노드의 범위가 한 번에 분배된 나머지를 포함하는지 확인합니다.

ConsistentHash(HashRange)

또는 산열화된 샤드키를 같은 산열화된 노드의 ID와 대조하여 구성을 결정할 수도 있습니다.
이런 상황에서 노드를 추가하거나 삭제할 때 데이터의 이동은 최소한이다.

import hashlib


def find_node(node_tuples, key):
    """
    :type node_tuple: list of tuple
    :type key: int or str
    :rtype: int or str
    """
    node_cnt = len(node_tuples)
    hashed_key = hashlib.md5(str(key)).hexdigest()
    for i in range(1, node_cnt + 1):
        if node_tuples[i-1][0] <= hashed_key and hashed_key < node_tuples[i][0]:
            return node_tuples[i][1]
        return node_tuples[0][1]

from collections import defaultdict


node_ids = range(0, 10)
# list of tuple (hash_slot, node_id)
node_tuples = sorted([(
    hashlib.md5(str(node_id)).hexdigest(), node_id)
    for node_id in node_ids],
    key=lambda n: n[0]
)

node_hash = defaultdict(list)
keys = [chr(i) for i in range(ord('a'), ord('z'))]
for key in keys:
    node_id = find_node(node_tuples, key)
    node_hash[node_id].append(key)

2019/11/04

오식 부분을 수정하다

R/W Splitting -> Primary/Backup

기타 용어의 통일

2019/12/10

분할 항목

modulo 이외의 분할 방식

https://github.com/cookpad/mixed_gauge   ↩