Memcached 에서의 Consistent Hashing

------------------------------------------------------------------------------------------------------------------

Memcached 에서의 Consistent Hashing

오늘은 제가 자주 사용하는 Memcached의 Consistent Hashing 에 대해서 알아보려고 합니다.( 자주 쓰기는 하는데, 내부를 잘 알지는 못해서 헛소리를 찍찍 할 수도 있지만, 실력이 모자란거니, 저런 모자란 넘 하시면서 웃으면서 넘어가시면 좋겠습니다. 어차피 욕하셔도, 전 상처받지 아니합니다. 그냥 일기에, 그분 이름 빨간색으로 좀 적어두고, 죽을때까지 기억하기만 할꺼예요. 전 쿨하니깐요. )

제가 가장 좋아하는 기술에 접근 방법은, 왜 이런 기술이 나왔는가? 왜 필요한가? 그래서 어떻게 구현되었는가? 이런순으로 따라가는 겁니다. 왜 필요한지? 문제가 무엇인지? 그래서 어떻게 해결하는지에 알아야만, 저는 그제서야 살짝 이해를 하기 시작합니다.(머리가 나빠서 사실 제대로 이해못하는다는데 제 주둥이를 건다는 쿨럭…)

Why Need Consistent Hashing?

Wikipedia 에서 Consistent Hashing 을 찾아보면 다음과 같은 내용이 나옵니다.

History

Originally devised by Karger et. al. at MIT for use in distributed caching. The idea has now been expanded to other areas also. An academic paper from 1997 introduced the term “consistent hashing” as a way of distributing requests among a changing population of Web servers. Each slot is then represented by a node in a distributed system. The addition (joins) and removal (leaves/failures) of nodes only requires K / n items to be re-shuffled when the number of slots/nodes change.[1]

This same concept, however, appeared in 1996 within the Super Proxy Script technique created by SHARP for optimizing use by web browsers of multiple caching HTTP proxies.[2]

Consistent hashing has also been used to reduce the impact of partial system failures in large Web applications as to allow for robust caches without incurring the system wide fallout of a failure.[3]

The consistent hashing concept also applies to the design of distributed hash tables (DHTs). DHTs use consistent hashing to partition a keyspace among a distributed set of nodes, and additionally provide an overlay network that connects nodes such that the node responsible for any key can be efficiently located.

 

영어가 어렵습니다. 간단하게 바꾸면, MIT의 karger 라는 사람이 웹 서버 수가 변화하는 가운데분산 리퀘스트를 처리하기 위해서 고안했다고 합니다. 이게 무슨 소리일까요? 간단하게 설명하자면 [그림 1]과 같은 상황입니다. K는 요청하는 유저 수, N 은 웹 서버의 수입니다.

[그림 1] User Request 를 Proxy 가 각 서버로 분배하는 상황

그런데, 여기서 [그림 2] 처럼 서버가 몇 대가 장애가 나고 수시로 추가된다고 합시다.

[그림 2] 한대의 서버가 장애로 인해서 서비스 제외된 상황

이렇게 되면 계속 들어오는 리퀘스트 들은 나머지 4대로 분배되게 됩니다. 이걸 보면 이게 무슨 문제가 있냐고 생각을 하게 됩니다. 사실 별 문제 없습니다. 단순히 각각의 리퀘스트 들이 전혀 연관관계가 없다면 말입니다. 이미 세션이 연결되어 있어서 각각의 유저는 기존의 서버로 연결되기를 원하는 상황이 된다면, 조금 문제가 복잡해질 수 있습니다.( 뭐, 해당 유저가 전에 어느 서버로 갔었는지 기억해두고 있다가 매번 그곳으로 보내주는 방식도 있지만, 이건 유저 별로 여분의 추가 작업이 필요합니다. ) 즉, 전체 사용자들이 서버 수에 맞춰서 다시 재분배 된다는 겁니다. 이건 데이터가 추가될 때도 마찬가지 현상이 발생합니다.

그럼 Consistent Hashing이 어떤 기능을 하는지 유추가 되시나요?(오오, 천재시군요. 전 유추 못하는데…) 즉, Consistent Hashing 은 서버의 개수, 즉 슬롯의 개수가 변화하더라도, 전체 데이터에 대한 재분배가 필요 없고, K/N 개의 아이템만 재분배를 하면 되는 방식입니다. 앞에서 서버가 5대 였으니, 한 대당, 20000명을 처리하고 있었는데, 한대가 장애가 나면, 이 20000 명만 서버를 재분배하고 나머지 유저들은 기존 서버에서 그대로 처리가 됩니다.

오오오, 대단히 재미난 기술 인거 같지 않습니까? 그럼 어떤 방식으로 처리가 되는 것일까요? 여기에는 HashRing 이라는 개념이 들어갑니다. Ring 이라는 게, 둥근 것, 즉, 꼬리에 꼬리는 무는 해시라고 해야될까요?

 

Consistent Hasing

먼저 A,B,C,D 서버가 4대가 있다고 가정합니다.( 아, 그림 그리기 힘드네요. 서버 수를 더 줄이줄 좋을 것 같습니다. T.T, 4대도 많아요 )

[그림 3]과 같이 처음에는 서버 한대만 존재한다면, 모든 리퀘스트는 해당 서버로 가게 됩니다.

[그림 3] HashRing 에 A 서버가 등록된 상황

 이 상황에 서버 B, C 가 추가되어서 [그림 4] 처럼 3대가 되었다고 하겠습니다.

[그림 4] HashRing 에 A, B, C 서버가 등록된 상황

 

이제 해당 서버에 들어오는 Key 들이 해시값이 A < Key <= B 라고 한다면,(아, 수식을 다 써보는군요.) 해당 Key는 자기보다 크고, 가장 가까운 서버로 할당이 됩니다. 즉, 여기에 Key 1이 들어왔다면, A < 1 <= B 라면 1은 B 서버에 저장됩니다. [그림 5]와 같습니다.

[그림 5] HashRing 에 A < 1 <= B 인 Key 1이 들어온 상황

자 이제 Key의 해시값이 B < 2 <= C 인 Key 2가 들어왔다고 합시다. 예상대로 [그림 6]과 같습니다.

[그림 6] HashRing 에 B < 2 <= C 인 Key 2이 들어온 상황

 이제 엄청 데이터가 많이 들어와서 [그림 7]과 같은 최종 모습이 되었다고 합시다.

[그림 7] 데이터가 최종적으로 들어 온 모습

이제 여기서 장애로 서버 B가 서비스를 하지 못하는 상태가 되었다고 가정합니다. 서버 B가 장애가 났으므로, Key 1은 유실이 됩니다. [그림 8]의 상황입니다.

[그림 8] 서버 B의 장애로 인해서 HashRing에서 B가 제거된 상황

Consistent Hashing 이 아니라면 [그림 8]의 장애 상황에서 전체 Key가 재조정되어야 할 수도 있습니다. 하지만 Consistent Hashing 방식을 이용하므로 Key 5를 요구하면 5의 해시값이 A < 5 <= C 가 되므로 해당 서버가 그대로 서비스를 하게 됩니다. 그럼 이때 원래 B로 할당되어야 했던 Key 1이 다시 들어오게 되면 어떻게 될까요? 예상하듯, A < 1 <= C 가 되어 버리므로 [그림 9] 와 같이 C로 할당되게 됩니다. (전 솔직히 예상 못했었어요 T.T )

[그림 9] 서버 B의 장애 상황에서 Key 1이 들어온 경우

 

 이런 식으로 Consistent Hashing 은 서버의 추가/장애시 K/N 의 Key만 재 분배 하면 되도록 되어있는 알고리즘입니다. Memcahed 에서 이런 방식을 사용하고 있습니다. 정확하게 하자면, memcached Client Library 에서 이렇게 키를 저장할 서버를 선택합니다. 자, 예제 1의 간단한 파이선 코드를 보시죠. 현재 Local에 20001, 20002, 20003, 20004 포트를 이용하는 memcached 서버 4대를 실행시켜 두었습니다.( python-memcached 모듈이 필요하므로, pip install python-memcached 로 설치하시기 바랍니다. )

 

import memcache    ServerList=[ '127.0.0.1:20001', '127.0.0.1:20002', '127.0.0.1:20003', '127.0.0.1:20004' ]   if __name__==’__main__’:     mc = memcache.Client( ServerList );       for idx in range(1,100):         mc.set( str(idx), str(idx) )

[예제 1] 간단한 1부터 100까지 memcached 에 저장하는 예제

 

 해당 코드를 실행한 후에 각각의 memcached 서버에 붙어서 확인해보면, 1~100 까지의 값들이 서버 4대에 분배되어 있는 것을 볼 수 있습니다.(고르게는 아니더군요 ^^) 확인 하는 방법은 다음과 같습니다.

 

charsyam@ubuntu:~$ telnet 127.0.0.1 20001Trying 127.0.0.1…   Connected to 127.0.0.1. Escape character is ‘^]’. get 1 VALUE 1 0 1 1 END

실제로 memcached 의 c client library인 libmemcached 의 소스를 보면 memcached_send 라는 함수가 있고, 이 안에 memcached_generate_hash_with_redistribution 라는 함수 안에서 key의 해시 값을 구하고, 해당 값이 포함되어야 하는 서버의 해시 값을 알려주게 됩니다.

uint32_t memcached_generate_hash_with_redistribution(memcached_st *ptr, const char *key, size_t key_length)   { uint32_t hash= _generate_hash_wrapper(ptr, key, key_length); _regen_for_auto_eject(ptr); return dispatch_host(ptr, hash); }

 

 

 

Memcached 를 이용할 때의 주의 사항

일반적으로 Consistent Hasing 을 사용하면 큰 문제가 없을 것 같지만, 간혹, 장비의 추가나, 삭제 상황에서, Old Data 가 남아있어서 이 값을 가져가게 되는 이슈가 발생할 수 있습니다. 어떤 상황에서 발생하게 될까요?(똑똑하신 분들은 이미 이해하셨을 테고, 저 같은 사람은 누가 알려주고, 설명을 해줘도 이해가 안가는 경우가 쿨럭…)

이전 [그림 8,9] 에서 한대의 서버가 장애가 나면, B로 들어가야 할 데이터만 다시 C로 들어가게 된다고 했습니다. 그럼 이 상황에는 원래 B일 데이터가 C에 저장됩니다. 그런데 다시 B가 복구가 되어서 HashRing 에 들어왔다고 가정합니다. 그럼 무슨 일이 발생하게 될까요? 끔직한 일? 힘든 일? 상상도 하기 싫은 일?, 정답은 아무 문제 없습니다.(헉, 어디서 돌이!!!) 당연히 뭔가 문제가 있었다면 이거 쓸 수가 없겠죠. 장애는 언제든지 발생하는 데 말입니다.

이 때, 다시 Key 1이 들어온다면 [그림 10]과 같은 상황이 벌어집니다. 그러나 Key 1의 해시는 B에 속하게 되므로, 데이터를 요청해도 C의 1이 응답으로 나가는 문제는 당장 발생하지 않습니다. 그로 인해 서비스는 문제 없이 잘 돌아갑니다. 여기서 문제가 되는 상황은 서버 B가 또 다시 장애가 나는 [그림 11]과 같은 상황입니다. 기존에 C 서버에 Old Key 1이 남아있던 걸 기억해야 합니다.

[그림 10] 서버 B의 복구 후 다시 Key 1이 들어온 경우

[그림 11] 서버 B의 재 장애 케이스

이 경우 Key 1을 요청하면 C 서버의 Old Key 1이 반환되어서 실제로 새로운 값이 아닌 오래된 값이 나갈 수 있습니다. 다만 memcached 를 목적에 맞게 사용하면 Key의 ExpireTime 이 지나서 사라지기 때문에 전혀 문제가 없을 수 있습니다. 위와 같은 문제는 ExpireTime 이내에 같은 서버가 다시 장애가 났을 때만 발생하는 문제입니다. 

(혹시나 해결책을 물어보신다면, 같은 장애가 발생했을 때, memcached의 해시 코드를 가져와서 실제로 남아있어야 하는 서버 이외에는 delete 를 호출하는 방법밖에 없습니다. 아니면 ExpireTime을 짧게 가져가면 쉽게 해결될 수도 있습니다.)

 

--------------------------------------------------------------

출처-http://charsyam.wordpress.com/2011/11/25/memcached-%EC%97%90%EC%84%9C%EC%9D%98-consistent-hashing/