오늘은 한권더 구매한
대용량 서버 구축을 위한 Memcached와 Redis를 보고 몇자 적어 봅니다.
책을 보다 보니 Memcached와 Redis를 공부 하기 전에 분산 캐시를 구현하는 핵심 기술인
Consistent Hashing에 대해서 알아야 한다는 생각이 들었습니다.
Consitent Hashing은 MIT의 David Karger라는 사람이 웹서버의 수량이 변화하는 상황에서 분산 Request를 처리 하려고 고안한 것이라고 합니다.
---------------------------------------------------------------------------------------
Consistent Hashing
일반적인 hash function을 떠올리자면, ‘key mod N’일 것이다. 이것의 가장 큰 문제점은 Node의 수 N이 변했을 경우이다. Node를 자유롭게 추가/제거할 수 없다면 Scalability보장이 곤란하다. 그래서 새로운 hash function이 필요한데 이를 해결해줄 수 있는 것이 Consistent Hashing이다.
Consistent Hashing의 개념은 매우 단순하다. 다음과 같은 원을 보자.
key와 node를 모두 hash하면 int로 표현할 수 있고 다음과 같이 나타낼 수 있다. 초록색 원은 Node이고, 붉은 색 점은 key를 나타낸다.
위 그림에는 총 3 개의 Node(A~C), 4 개의 key(1~4)가 있다. Consistent Hashing의 중요 포인트는 key와 Node를 모두 hashing한다는 것이고, hash(key)에 인접한 hash(node)값을 가지는 node에 value를 저장한다는 것이다.
즉 hash(key) 값이 1, 2인 key는 Node B에 value가 저장된다. 역시 3은 C에, 4는 A에 저장된다.
만약 Node A와 B가 제거되고, Node E가 추가되었다면 다음과 같을 것이다.
이 때, 4와 1은 E에 2와 3은 C에 저장된다.
Consistent Hashing을 사용하면 replication 또한 쉽다. hash( key + 1), hash(key + 2), hash(key + ...) 하는 식으로 replication 개수만큼 Node에 저장하면 된다. 역시 값을 찾을 때도 hash(key)를 통하여 찾을 수 없다면 hash(key + ...)와 같은 방법으로 값을 읽어올 수 있다.
장점으로는 1. 부하 집중 부분을 피하기 쉽다. 2, 파티셔닝(partitioning)을 가능하게 한다. 슬라이스 피차처럼~ 3. 스케일(scale) up/down이 가능하다. 예측이 가능하다. 4. 복제가 가능하다. 또한 부하 집중 부분의 부하를 경감할 수 있다. * 자료 출처 : NoSQL을 여행하는 히치하이커를 위한 안내서, 송기선|작성자 개발자센터 http://blog.naver.com/naverdev/120116323974 The Simple Magic of Consistent Hashing