'virutal node'에 해당되는 글 1건
[번역] Virtual Nodes Strategies[번역] Virtual Nodes Strategies
Posted at 2013. 4. 10. 12:30 | Posted in Articleredis shard를 virtual node를 입혀보려고 연구중.
사례 및 기술연구를 위해 몇몇 문서를 번역해 본다.
※ 오역에 주의하시고, 잘못 번역된 부분은 댓글로 알려주세요.
Virtual Nodes Strategies
consistent hasing 에서 각 호스트에 single "token" in a "hash-space" 를 두는 것은 약간 손해가 있는 모델이다.
데이터 추가가 될 때 1/N로 들어가므로 balanced cluster가 된다.
Fig 1. Partitioning of hash-space between 4 hosts in a cluster
그러나 새로운 호스트가 추가되면 unbalanced cluster가 된다.
이를 해결하기 위해 권장되는 방법은 scaling up시 호스트를 2배로 늘리거나, scaling down시 호스트 수를 반으로 줄이는 방법이 있다. 그리고, 모든 다른 호스트로 token을 이동시켜 균형을 잡게 해야 한다. 이 방법은 소규모 클러스터에서나 실행 가능하고, 큰 큐모에서는 사용하기 어렵다.
Fig 2. Balancing a cluster when adding hosts requires moving tokens (top) or doubling the number of hosts (bottom)
이 문제들은 operation들을 매우 복잡하게 만든다. 카산드라 관리자는 balanced load를 보장하는 token들의 주의 깊은 선택을 해야하고, 호스트가 추가될 때 수작업으로 rebalancing을 해줘야 한다. 이런 문제를 해결하는 한가지 방법은 virtual node를 사용하는 것이다. virtual node를 사용하는 consistent hashing schema는 각 호스트가 인접하지 않은 범위에 데이터를 다중으로 둘 수 있게 한다. virtual node를 사용함으로써 얻는 이득은 다음과 같다:
- 클러스터에 추가된 호스트는 서로 다른 호스트로부터 가져온 데이터로 클러스터를 평탄하게(even portion) 만드는 책임을 맡게된다.
- 하나의 호스트에 장애가 발생하면, 클러스터의 다른 호스트들로 로드가 균등 분배될 것이다.
- Rebuilding a dead host will be faster as it will involve every other host (뭔소린지..)
- 호스트에 할당되는 파티션 수는 자신의 용량(capacity)에 의해 결정될 수 있다. 이것은 각기 다른 하드웨어의 사용도 허용하게 한다.
Virtual nodes schemes
대체로 다음 세가지 형태로 분류 해볼 수 있다.
Random token assignment
각 호스트에 T 개의 random token들을 할당한다. 파티션은 각 호스트의 token들의 각각에 할당되고, 파티션은 ring에서 하나의 token과 그 이전 token의 구간(interval)로 정의된다. 호스트가 ring에 추가됐을 때, T개의 random token들이 할당된다. T random tokens which will result in a portion of an existing partition being assigned to that host.(뭔소린지..)
이 방식은 memcached server사이의 분배/분산(distribution)를 위한 libketama[2] 에서 사용되고, T=1일때 카산드라 분산(distribution)을 위한 일반화 방법이다. (역주: 카산드라는 호스트 하나가 토큰 구간(interval) 하나를 전담하게 된다는 뜻인 듯 - 카산드라쪽을 더 알아보자.)
Fig 3. Partitioning by random token assignment
Fixed partition assignment
해시 공간을 균등한 크기 Q개로 나누고, 각 호스트에는 Q/N 개씩 할당한다(N는 호스트 수). 호스트가 추가될 때 다른 호스트에서 몇개를 가져와서 Q/N 비율을 맞춘다. 호스트를 제거할 때는 제거되는 호스트의 파티션을 다른 호스트로 재분배해서 Q/N 비율을 맞춘다.
이 방식은 Dynamo[3]와 Voldemort[4]에서 사용된다.
Fig 4. Fixed partitioning assignment
Automatic sharding
각 호스트에 하나의 token을 할당하고, 각 호스트는 하나의 파티션(token의 interval로 정의됨)을 갖는다. 하나의 파티션이 한계를 초과하면, 새로운 파티션을 생성할 수 있게 해당 파티션의 구간에 새 token이 추가된다. (역주: 즉, 파티션은 token의 interval(구간)을 의미하고, 용량 초과된 파티션에 새로운 구간(token)을 생성한다는 의미. Partition dividing assignment라고 해야 의미가 더 맞지 않을까?)
이 방식은 BigTable[5] 또는 Mongo auto-sharding[6] 에서 수행되는 sharding 방식과 비슷하다.
Fig 5. Automatic sharding: when a partition contains too much data it is split into smaller partitions
Evaluation(평가)
이 스키마들을 평가하기 위해 구현의 차이에 대한 생각(idea)과 이들이 클러스터의 성능에 어떻게 영향을 미치는지에 대한 것들이 필요하다. 이 스키마들의 주요 차이점은 파티션 size와 파티션들의 수이고, 이 두가지가 어떻게 클러스터 size와 데이터 size를 변하게 하는지 살펴본다.
Number of Partitions(파티션 수)
클러스터 메타데이터의 일부분으로써 그것이 저장된 호스트에 파티션의 할당 매핑을 저장해야 한다(must store the assignment mapping of partition to the host on which it is stored). 카산드라에서 이 매핑의 배치는 호스트간에 gossip을 이용한다. 모든 호스트는 클라이언트의 요청은 정확한 replica로 한 홉에 라우팅할 수 있어야 하고, 모든 데이터 위치를 인지하고 있어야 한다. 만약 파티셔닝 스키마가 더 많은 파티션을 요구하면, 카산드라 gossip 시스템에 더 많은 부하와 더 많은 메모리를 사용하게 될 것이다. (If our partitioning scheme results in more partitions then this placement metadata will be larger, will put more load on Cassandra's gossip system, and will use more memory to store.)
Partition Size(파티션 크기)
카산드라에서는 한 번 실행될 때 전체 파티션으로 수행되는 프로세스들이 있다. 예를 들면, 다른 replica의 데이터와 비교할 수 있도록 저장되는 모든 데이터를 위한 digest를 계산하는 repair 같은 것이다. 클러스터에 참여하는 새로운 호스트의 bootstrapping 같은 스트리밍 operation들도 전체 파티션을 읽을 것이다. 매우 큰 파티션을 가지기에 몇가지 불리함(disadvantages)이 있다: 이런 프로세스들 중 하나가 실패하거나 에러가 발생하게 되면 반드시 재시도해야 한다. 큰 파티션에서, 에러로 인해 더 많은 작업이 낭비되게 된다. 새로운 호스트의 bootstrapping(bootstrapping a new host)이 많은 시간을 소비할 때, 한 파티션의 전송 에러는 매우 높은 비용이 들게한다. 작은 파티션에서는 balancing을 위해 클러스터내 다른 호스트에 영향을 주는 이런 operation들을 늦출 수도 있다.
하지만, 우리는 파티션을 매우 작게 만들 수 없다. 많은 작은 파티션들을 읽는 것은 데이터를 전송하기보다 파티션들을 탐색하느라 디스크에서 대부분의 시간을 소비하는 결과를 만들 수 있다. 우리는 random disk access보다는 sequential disk access로 읽으면서 충분히 큰 파티션이 되기를 원한다.
Comparison
Table1은
<진행중>...
www.deepblue.pe.kr
