데이터베이스 - 5부 : 컨시스턴스 해싱

Overview

컨시스턴스 해싱이란 무엇일까? 이를 알기에 앞서, 우선 hashing 이란 말은 다지고 섞다라고 이해할 수 있다. Hash Map은 index에 데이터를 맵핑해둔 자료구조이다. O(1)로써 가장 효율적이라고 말할 수 있다. 대게는 키-값 쌍으로 저장하는게 일반적이다.

해시에 대해서는 이정도로만 얘기를 하고 분산해시에 대해서 얘기해보자.

분산해시

아래의 해시테이블이 있다고 생각해보자. 이제 우리는 이 데이터를 분산된 데이터 저장소로 저장할 것이다.

세대의 서버에 나뉘어 저장을 하면 아래처럼 정리가 된다. 각각 A:0,B:1,C:2 의 인덱스를 갖는다.

이렇게 잘 사용하고 있는 상황에서, 갑자기 장비한대가 고장났다고 생각해보자. 서버 C 가 내려갔다고 가정한다면 다시 아래와 같이 hash 테이블과 서버에 데이터가 할당될 것이다.

이제 A:0, B:1 두 대의 저장소에 데이터가 아래와 같이 저장될 것이다.

이렇게 되면 C 에 존재했던 모든 키위치가 변경되게 되는데, 이떄 원본데이터로부터 re-hashing 작업이 필요하게되고 이는 원본 서버에 부하를 주게된다. 그리고 그 와중에 클라이언트가 요청한 데이터는 유실된다.

이를 해결하고자 나온 해싱 기법이 바로 일관된 해싱 (Consitency Hashing) 이다.

Consitent Hashing

위의 이미지가 이번에 말할 모든 것이다. 위의 이미지를 따라서 해싱을 한다고 생각해보자.

서버도 해싱테이블에 함께 배치해준다.

여기서 각 키가 위치한 서버를 찾는 룰은 하나다.

반시계방향으로 돌때 가장 가까운 서버가 바로 해당 키가 위치한 저장소이다.

위에서 말한 기준으로 키가 저장되어 있는 저장소를 정리하면 다음과 같다.

그럼 도대체 이 기법의 장점은 뭘까?

이제 상상해보자, 만일 C 장비가 제거 되었다고 생각해보자. 기존의 기법은 모든 키들이 rehashing 되야만 했다.

바로 여기서 이 기법을 통해 우리는 C 장비에 할당되어 있는 키들만 rehashing 이 필요하다는 것을 알 수 있다.

A, B 의 서버를 바라보는 키는 이미 가장 가까운 위치 A,B 를 바라보고 있기 때문이다. C 가 없어져도 그 키들은 변경사항이 없다. 오직 C 서버에 할당된 키들만 rehashing 이 필요하다.

반대로 장비가 추가되어도 K/N ( 키의 개수 / 장비수 ) 만큼의 rehashing 이 필요할뿐 모든 키에 대해 rehashing 이 필요하지 않다.

예를들어 키가 3개고, 장비가 두개였을때. 이 사이에 장비가 한개 들어간다고 생각하면. 장비에 키가 골고루 들어가도록 설계했다고 가정한다면, 3/3 = 1개의 키에 대해서 리해싱이 일어날 수 있고, 이는 결국 장비 하나당 하나의 키가 저장되는 균형된 모습을 보일 수 있다.

Consistent Hashing 은 문제를 갖고 있다. 바로 키 쏠림이다. 이를 어떻게 하면 완화시킬 수 있을까?

Ketama Consitent Hashing

우선 가장 쉬운방법은 서버를 여러개의 토큰으로 쪼개서 Consistent Hashing Circle 에 배치하는 것이다. 이것이 바로 Ketema Consistent Hashing 기법이다. A서버를 A0-A10까지 분산시켜 키배치가 최대한 균일하게 되도록 한다.

생각

• 결국, rehashing 은 피할 수 없는 문제이다. 최소한으로 rehashing 이 일어나도록 설계하고 만드는 것이 분산처리의 요구사항이라 생각된다.

예제 프로젝트 ( 위의 이론을 간단히 구현 해보았다 )

• Reduster

Appendix

• Constant Hashing
• hashing, ketama