[입 개발] Consistent Hashing 과 Replication

그냥 여러가지를 고민하다 보니 번뜩 떠오르는 의문이 생겨서, 이렇게 정리해둡니다. 다들 알다시피, Consitent Hashing 이라는 것이 있습니다. 서버 개수에 맞춰서 Key를 분배하면서도, 서버의 추가나 삭제에 따라서 전체 Key를 재분배 할 필요없이 전체 N 분의 K 서버 즉 N/K 개만 재분배 하면 되는 좋은 방법입니다.

그런데 사실 이 Consistent Hashing에는 여러가지 방법이 있습니다. 그냥 일반적으로 구성되는 형식 [그림 1]과 같습니다.

[그림 1] 일반적인 Consistent Hashing 방법

그런데 위의 방식은 키가 균등하지 못할 가능성이 있어서, 좀 더 개선된 [그림 2]의 방식을 사용합니다. 각 서버의 해쉬값을 더 만들어서 2~300 개 정도의 token 값을 만들어 버리면 거의 균등하게 들어가게 됩니다. 이를 유식하게 ketama consitent hashing 이라고 합니다.

[그림 2] 유식한 Ketama Consistent Hashing

이 방식이 현재 memcached 에서 기본적으로 사용하는 방식입니다. Cassandra 나 다른 여러 가지 분산 DB들은 DHT(distributed Hash Table 이라고 해서 이와 비슷한 방법을 사용합니다.) 그런데, 위의 ketama 방식이 memcached 의 경우에는 아주 적합한데, replication 이 필요한 서버들에게도 적합할까요?

그런데 여기서 제 머리속에 의문이 하나 생겼습니다.  Cassandra의 경우 replication factor 가 3이면 서로 다른 세대의 서버에 값을 저장하게 됩니다. 그런데 위의 Ketama 방식을 사용할 경우, 다음 서버가 자기 자신일 수도 있습니다. 이렇게 되면 3대에 저장한다는 것이 실제로는 한대에만 세번 저장되고 끝날수도 있지 않을까요?. [그림 2]의 A+2, A+3의 경우를 가정해보시면 될듯 합니다. 그래서 일단 대표적으로 유명한 Cassandra를 보았습니다. Cassandra의 경우는 nodetool 을 실행하면 다음과 같은 결과를 얻을 수 있습니다.

bin/nodetool -host 10.176.0.146 ring
Address         Status State   Load            Owns    Token
                                               113427455640312821154458202477256070484
10.176.0.146    Up Normal  459.27 MB   33.33%  0
10.176.1.161    Up Normal  382.53 MB   33.33%  56713727820156410577229101238628035242
10.176.1.162    Up Normal  511.34 MB   33.33%  113427455640312821154458202477256070484

Token이 웬지 위에서 보던 그림 같이 생겼지요? 그리고 Cassandra 종류는 Ketama 방식보다는 일반적인 방식 그러나 변형된 방식을 이용하게 됩니다. 다음 그림은 DataSax에서 무단으로 훔쳐온 그림입니다. 즉 거의 고정 크기를 사용한다고 보시면 될듯 합니다.( 밑에 acunu 자료를 보면 자기들이 수정한 1.2와 1.1을 비교한 PPT가 있습니다.)

../../_images/ring_partitions.png

http://www.datastax.com/docs/1.0/cluster_architecture/partitioning

이까지만 생각해보면, Replication이 필요하면 ketama 방식이 안어울리는구나 라고 생각할 수 있습니다. 그러나 만만의 말씀, 천만의 콩떡입니다. ketama 방식 처럼 실제적으로 물리 노드 보다 많이 보이게 하는 것을 Virtual Node 라고 합니다. Dynamo와 Voldemort 는 이 Virtual Node 방식을 이용하고 있습니다.(어떻게? 라는 의문이 드시겠죠?)

먼저 S개의 서버가 있다고 합니다. ketama 처럼 랜덤한 token을 만들어서 해당 값을 이용하지 않고 Q개의  동일한 파티션을 만듭니다. 그리고각 노드는  Q/S 개 만큼의 token을 가지게 됩니다.  그리고 Ring 안에서 랜덤하게 뿌려줍니다. 자, 이러면, 위의 ketama 방식과 크게 다를 바가 없어보입니다. 그래서 replication을 서버 preference list 라는 것을 만듭니다. 그냥 쭈욱 다음칸으로 이동하면서 -_-, replication factor 만큼의 서로 다른 서버 주소를 저장하는 것입니다. 같은게 나오면 skip, skip 하면서 만들어 내는 거죠.  voldmort 디자인 문서를 보면 다음과 같습니다.

이런 정책이 중요한 이유는 단순히 replication을 하기 위한 목저도 있지만, 이에 따라서, 서버가 장애가 났을 경우, 복구하는 시간이나, 전략 역시 달라지게 됩니다. 예를 들어, 가장 단순한 방식은 장애 났을 때, 바로 다음 서버의 데이터를 읽어오면 되므로 간단합니다. 복구를 위해서도 자신이 main인 모든 key를 한서버로만 넘겨주면 됩니다. 다만, 이러면, 해당 서버들의 부하가 매우 클 가능성이 높습니다. 연쇄 반응이 일어날 가능성이 있는 것이죠. dynamo 와 voldemort 는 이런 이동 부하를 어떻게 줄일것인지에 대한 고민이 조금 더 있습니다. 아까 Q/S 방식에서 전체를 8개의 동일한 파티션을 만들었다고 하고 서버가 4대가 있다고 하겠습니다. 그럼 8개의 파티션에 각각 2개의 토큰 범위를 가지고 있을것입니다. 여기에 서버 E가 추가되었다고 하겠습니다. 8/5가 되므로 해당 서버의 Token은 1~2개가 생기게 됩니다. 2개씩 가지고 있는 녀석들 중에서, 아무 자리나 차지합니다. 그러면 이동시에 해당 파티션 만큼의 부하만 발생하게 됩니다. 다시 4대에서 D서버 한대가 장애가 났다고 한다면, 8/3 이므로 2~3가 됩니다. 남은 A,B,C 중에서 2개가 3개로 하나씩 커버하게 됩니다. 다만 이 방법은 서버 수(S)가 Q보다 같게 될때부터는 조금 문제가 있을듯 합니다. 초반에 Q를 잘 잡는게 필요할 듯 합니다.

갑자기 의문에서 시작된게, 코드보고, 논문보니깐 -_- 몇시간이 훌쩍 지나갔네요. -_- 처음에 간단하게 생각했다가, 점점 아닌듯 해서 판이 커졌습니다. 그 대신, 궁금하던게 해결(?) 이 되어서 다행이라는 생각이 살짝 쿵 듭니다. 쿨럭… 고운하루 되시길…

참고자료

1]  About Data Partitioning in Cassandra http://www.datastax.com/docs/1.0/cluster_architecture/partitioning

2]  Virtual Nodes Strategies http://www.acunu.com/2/post/2012/07/virtual-nodes-strategies.html

3] Voldemort Data partitioning and replication http://www.project-voldemort.com/voldemort/design.html

4] PPT http://www.slideshare.net/jericevans/virtual-nodes-rethinking-topology-in-cassandra

5] dynamo http://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf