brunch

매거진 풀스택 개발자의 웹프로그래밍

라이킷 5 댓글 4

You can make anything
by writing

C.S.Lewis

계정을 잊어버리셨나요?

by 에디의 기술블로그 Sep 08. 2019

Consistent Hashing

분산 캐싱 구현을 위한 Consistent Hashing 알고리즘

오래된 글이라서, 잘못된 내용이 포함되어 있습니다. 읽지 마세요!

~~필자는 지난주에 "if kakao 개발자 컨퍼런스"를 다녀왔다.~~

~~매우 유익한 시간이었는데, 세미나에 대한 후기는 필자의 이전 글을 참고하길 바란다.~~

~~https://brunch.co.kr/@springboot/254~~

if Kakao 개발자 컨퍼런스 1일차 참석 후기

카카오 개발자 컨퍼런스인 "if Kakao developer 2019" 1일 차에 참석하고 작성하는 후기입니다. 공식적인 발표자료가 아직 공개되지 않아서, 부득이하게 제가 직접 찍은 사진으로 설명을 대체합니다. 다른 참석자들에게 방해가 되지 않도록 뒷자리에서 사진을 찍었는데, 그래서인지 사진 품질이 좋지 않습니다. 제 글은 재미 삼아 읽어주시고, 추후에,

brunch.co.kr/@springboot/254

필자는 수많은 세션 중에서, "카카오톡 적용 사례를 통해 살펴보는 카카오 클라우드의 Kubernetes as a Service" 라는 주제의 세션을 참석하였는데, 해당 발표 후반에 레디스 인프라 관련 내용이 있었다. 카카오톡 서비스에서의 레디스 인프라는 쿠버네티스 환경에서 가용성 높게 운영 중이었다. 다수의 레디스 그룹으로 구성되어 있고, 하나의 그룹에는 마스터-슬레이브 구조에 센티널 인스턴스가 별도로 실행 중인 구성이다. 센티널 인스턴스는 기본적인 Auto FailOver 를 담당하지만, 센티널이 할 수 없는 레디스 노드 재시작 등의 기능은 쿠버네티스가 역할을 수행한다. 그런데, 특이한 점은 레디스 클러스터는 퍼포먼스 등의 이유로 사용하지 않는다고 했다. 어쨋든, 필자는 해당 인프라가 너무 궁금해서 연사님께 직접 찾아뵙고 질문했는데 몇가지 추가 정보를 더 알게 되었다. 카카오톡 서비스의 레디스 인프라는, 클라이언트에서 레디스의 타겟 그룹에 Read&Write 커맨드를 수행할지에 대한 판단을, 커스텀하게 구현된 해시룰에 의해서 클라이언트 측에서 결정된다고 한다. 사실, 해시룰이 어떻게 구현이 되었는지 더 상세하게 궁금했지만, 열심히 발표하신 연사님께 추가 질문을 계속하는 건 실례라고 생각이 되어서 소심한 마음에 더이상 질문을 할수가 없었다. 아쉬웠지만, 집에 와서 곰곰히 생각을 해봤는데 아직도 이해가 잘 되지 않는다. 발표 중 연사님께서는, 레디스의 클러스터 기능은 퍼포먼스 때문에 사용하지 않았다고 했는데, 카카오톡 서비스 같은 대용량 트래픽 환경에서는 당연히 레디스 클러스터를 사용할 줄 알았는데,,, 기본적인 레디스 마스터-슬레이브 환경에 센티널 인스턴스와 쿠버네티스로 가용성을 높이고, 레디스를 여러개의 그룹으로 나누어서 클라이언트에서 노드를 선택하는 인프라 환경으로 대용량 트래픽을 안정적으로 받아내고 있다는 사실이 매우 흥미롭다. 물론, 카카오에서 사용하는 레디스 인프라의 역할이 분산캐싱 용도가 아니라 데이터 저장소로서의 역할을 수행할 가능성도 높다. 그래서 사실 이 글에서의 핵심 주제인 분산캐싱과는, 카카오톡 레디스 인프라는 크게 관련이 없을 수도 있다. 어쨋든, 이런저런 이유로 인해서 필자는 분산 캐싱에 대해서 한 주 동안 깊게 생각을 하였고 대표적인 알고리즘인 Consistent Hashing 에 대해서 검토를 하였다. 글 초반부터 주저리주저리 사설이 너무 길어졌는데, 언제나 그렇듯이 필자의 글은 너무 재미없겠지만,우연히 이 글을 읽고 있는 엔지니어 중 분산 환경에서의 분산 캐싱 경험자가 있다면, 이 글을 읽고 꼭 피드백을 해주길 바란다.

이 글은...

시간이 지난 후 다시 읽어보니, 제가 아무생각없이 Consistent Hashing 를 매우 무식한 방법으로 구현한 글이었네요. 소스코드는 참고하지 마시고, 개념만 참고하시길 바랍니다.

분산 캐싱

마이크로 서비스 환경에서는 다양한 목적에 부합하기 위해서 캐시의 사용이 매우 중요하다. 웹 애플리케이션 간의 데이터 일관성 유지, 요청에 대한 응답을 빠른 시간에 제공하기 위한 용도로 보통 분산 캐싱을 사용한다. 그래서, 일반적인 RDMBS 같은 데이터베이스로부터의 데이터 참조보다 훨씬 빠른 속도로 데이터를 제공할 수 있다. 응답이 빠르기 때문에 더 작은 리소스로 많은 요청 처리가 가능하다. 필자는 웹서비스 백엔드 애플리케이션 아키텍처라는 주제로 틈틈히 정리 중인데, 조만간 애플리케이션 캐싱 디자인 패턴 관련해서 글을 작성할 예정이다. 아마도, 캐싱 디자인 패턴이라는 주제의 글을 쓰면서 분산 캐싱에 대해서도 상세하게 다룰 예정이다. 이 글에서는 분산캐싱에 대한 기본적인 개념은 이정도로만 소개하고 넘어갈 예정이다. 이글에서는 Consistent Hashing 에 대해서 집중하겠다. 참고로, 이 글의 주제와는 좀 거리가 있지만, 사전에 읽을만한 글을 먼저 소개하겠다.

~~웹서비스 백엔드 애플리케이션 아키텍처 대한 주제로 작성한 글이다.~~

~~https://brunch.co.kr/@springboot/228~~

~~애플리케이션 데이터를 공용 캐시로 전환했던 경험에 대해서는 예전 글을 읽어보자.~~

~~https://brunch.co.kr/@springboot/173~~

~~Cache-Aside Pattern 을 레디스 환경에서 구현한 사례이다.~~

~~https://brunch.co.kr/@springboot/151~~

~~레디스의 Hash 데이터를 검토했던 글이다.~~

~~https://brunch.co.kr/@springboot/73~~

~~레디스 Sorted Set 검토 글이다.~~

~~https://brunch.co.kr/@springboot/205~~

~~레디스 성능테스트에 대한 글이다.~~

~~https://brunch.co.kr/@springboot/169~~

Consistent Hashing 을 검토하기 전에,

레디스 클러스터에 대해서 가볍게 알아보자.

Consistent Hashing 를 알아보기 전에, 레디스 클러스터 기능에 대해서 간단하게 살펴보겠다. 또한, 필자의 글에서 구축하는 레디스 인프라의 용도에 대해서 소개한다.

오해가 없기를 바라며

필자는 이 글에서 분산캐싱을 검토하기 위해서 레디스를 활용하는데, 레디스에서 제공하는 클러스터 기능을 사용하지 않는다. 대신, 클라이언트에서 직접 분산 캐싱을 구현하는 방법으로, 클라이언트 해싱룰을 구현하였다. 그래서, 이런 분산 캐싱을 구현하기 위한 핵심 기술로 Consistent Hashing 를 활용한다. 사실, 레디스는 훌륭한 클러스터 기능을 제공하며, 많은 기업에서 레디스 클러스터를 잘 활용하고 있다. 필자의 현재 회사, 팀 에서도 사용 중이다.

~~http://redisgate.kr/redis/cluster/cluster_introduction.php~~

CLUSTER Introduction Redis

redisgate.kr

레디스가 훌륭한 클러스터 기능을 제공하지만, 이 글에서의 핵심은 Consistent Hashing 알고리즘이다. 해당 글에서 레디스의 역할은 단순 서버측에서 클러스터, 샤딩 등의 분산 기술이 안되는 단순 싱글노드로서 데이터(캐싱)의 저장소 역할만을 수행한다.

레디스 클러스터에서, 데이터는 어떻게 분산되어 저장되는가?

레디스 클러스터를 이해하기 위해서는 우선 레디스 클러스터의 키-슬롯-노드 할당 방식을 알아야 한다. 레디스 클러스터는 총 16384개의 슬롯을 사용하다. 슬롯 번호는 0~16383 인데, 클러스터가 초기 연동될 때 슬롯을 각 노드에 적절하게 할당한다. 만약 레디스 노드가 3개이면, 1번 노드는 0-5460, 2번 노드는 5461-10922, 3번 노드는 10923-16383 슬롯을 할당받게 된다. 데이터가 어떤 슬롯에 저장되어야 하는지는 아래와 같은 정해진 함수식으로 결정되는데, 각각의 노드는 다른 노드에서 어떤 슬롯을 할당하고 있는지 알고 있다. 그래서, 만약 자신의 노드에서 저장하고 있는 데이터가 아니라면, 해당 데이터를 담당하고 있는 노드로 redirect 해준다. 슬롯을 구하는 함수는 HASH_SLOT = CRC16(key) mod 16384 이다. CRC16 function 를 사용해서 나온 해시코드를 전체 슬롯 크기(16384) 로 나누기했을 때 나머지는 0~16383중에 하나의 값이 나오는데, 그 값이 해당 키가 저장되어야 하는 슬롯 번호이다. 그리고, 그 슬롯을 할당된 노드에 데이터가 저장된다. 예를 들어서, "person:eddy" 라는 키 를 저장한다고 가정하자. CRC16("person:eddy") mod 16384 를 계산해서 나온 값이 "777" 이라고 가정해보자. 클러스터 노드에 슬롯 할당은 A 노드에 0-5460, B 노드에 5461-10922, C 노드에는 10923-16383 할당된 상황에서, 해당 키는 어떤 노드에 저장되는가? 슬롯번호 "777" 은 0~5460 범위에 속하기 때문에, 해당 슬롯을 할당받고 있는 A 노드에 저장될 것이다.

노드가 추가 되거나, 삭제 된다면?

노드가 신규로 추가되거나 또는 기존 노드가 삭제되면 슬롯 재할당 및 데이터를 재할당해야 하는 상황이 발생한다. 레디스에서 제공하는 RESHARD 또는 REBALANCE 기능을 사용하면 된다.

~~http://redisgate.kr/redis/cluster/redis-cli-cluster.php#reshard~~

~~http://redisgate.kr/redis/cluster/redis-cli-cluster.php#rebalance~~

레디스 클러스터

~~간단하게 레디스 클러스터의 슬롯 할당 알고리즘에 대해서 알아봤다. 자세한 내용은 아래 링크를 참고하자.~~

~~http://redisgate.kr/redis/cluster/cluster.php~~

CLUSTER Redis 레디스 클러스터

redisgate.kr

아주 간단하게 레디스 클러스터에 대해서 살펴봤습니다. 레디스 클러스터는 서버측에서 데이터를 분산합니다. 하지만, 필자의 이 글에서는 클라이언트 측에서 데이터를 분산해서 저장하는 방식이며, 핵심 알고리즘으로 Consistent Hashing 를 사용하였습니다. 레디스 클러스터는 매우 훌륭하게 동작합니다. 필자의 방법... 즉, 레디스 클러스터를 사용하지 않고, 클라이언트 측 분산을 구현하는 필자의 방법을 따라할 필요가 전혀 없습니다. 필자는 단지 Consistent Hashing 알고리즘을 공부 중이며, 해당 알고리즘을 검증하기 위한 캐싱 저장소로 레디스를 선택했을 뿐입니다. 이 글에서 사용하는 레디스는 단지 캐시 저장소일 뿐, 그 어떤 중요한 역할도 수행하지 않습니다. 이 글에서는, 어떤 저장소를 사용하는지에 대해서 크게 중요하지 않고, Consistent Hashing 개념을 이해하는 것이 중요합니다.

Consistent Hashing

이제 본격적으로 Consistent Hashing 에 대해서 알아보겠다. 일주일 정도 공부하고 작성하는 글인데, 혹시라도 잘못된 내용이 있다면 댓글을 남겨주길 바란다.

데이터를 분산 저장하는 가장 심플한 방법

데이터를 고르게 분산 저장하는 가장 간단한 방법을 소개하겠다. 해시함수에 의한 해스코드를 전체 데이터 저장소(노드)의 개수로 나누기를 한다. 나누기에 의해서 나온 나머지가 노드의 번호가 되며, 데이터는 해당 노드에 데이터를 저장한다. 데이터 노드가 3개 있다고 가정해보자. 아래와 같이 해시 함수(데이터 키)를 통해서 나온 해시코드를 3으로 나눈다. 이때 나온 나머지는 0, 1, 2 일 것이다. 나머지는 노드의 번호가 되며,

~~노드 번호 0은 Node-A , 1은 Node-B, 2는 Node-C 에 저장하면 된다.~~

~~방식은 매우 간단하다. 근데 이런 방식에는 조금 문제가 있다. 이 글을 읽고 있는 개발자는 1분만 생각해보자.~~

1. 어떤 문제가 발생하는지 잘 알고 있다면, 이 글은 더이상 안 읽어도 된다. 이 글을 읽고 있는 여러분은 필자보다 훨씬 뛰어난 개발자이므로 필자의 허접한 이 글은 더이상 읽지 않는 것을 추천한다. 하지만, 당신이 착한 마음을 가진 개발자라면 한번 읽어보고 꼭 피드백을 남겨주길 바란다.

~~2. 어떤 문제가 있는지 잘 모르겠다면, 이 글을 계속 읽어라.~~

신규 노드가 추가되면 어떤 상황이 발생할까?

위와 같은 방법으로 3대의 노드에 데이터를 분산 저장해서 잘 사용하고 있었다. 시간이 지나면서 데이터의 양이 점점 많아지고, 하드웨어의 메모리 및 디스크로 대응이 안되는 수준이 되었다. 그래서, 우리는 신규 노드를 추가하기로 결정하였다. 이때, 기존에 3개였던 노드에 1대의 신규 노드를 추가해서 총 4대의 노드가 되었다. 이제, 해시함수에 의해서 나온 해시코드를 3으로 나누면 안되고, 4로 나누기를 해야 한다. 아래와 같이 변경되었다.

3으로 나누던 계산식을 4로 나누게 되었기 때문에, 나누기에 의한 나머지는 다르게 나올 수 있다. 결국 많은 데이터를 기존에 저장하던 노드가 아니라, 다른 노드에 새로 저장해야 한다.

데이터의 키 이름이 바뀌지 않는다면, hash_function(키)에 의한 해시코드는 변하지 않는다. 그래서, 노드의 개수가 바뀌지 않는다면 동일한 노드에 저장하게 된다. 하지만, 노드의 개수가 바뀌면 나머지가 바뀌게 되어서, 저장해야 하는 타겟 노드 역시 바뀔 것이다.

어쨋든, 신규 노드가 추가되어서 데이터를 재할당 해야하는 상황이다. 수 많은 데이터를 새로운 서버에 다시 저장해야 한다면, 서버에는 엄청난 과부하가 발생한다. 아마도, 이런 상황에서는 서비스 무중단 상황에서는 재할당 작업이 힘들 것이다. 부득이하게, 서비스 서비스를 중지하고 진행해야 한다. 즉, 유입 트래픽을 막고 데이터를 재할당해야 하는 큰 작업을 수행해야 한다.

Consistent Hashing

~~이 글의 주제인 "Consistent Hashing" 에 대해서 알아보자. 일단, 사전적 의미는 아래와 같다.~~

일관된 해싱(Consistent hashing)은 웹서버의 개수가 변동하는 가운데 요청을 분산하는 방법을 말한다. 해시테이블의 크기가 변할 때, 평균적으로 K/n의 키만 재매핑되면 된다. 즉 노드나 슬롯의 개수가 바뀔 때, 노드의 추가나 삭제를 할 때, 오직 K/n의 아이템만 다시 섞이면 되는 것이다. (n은 전체 노드의 개수, K는 item의 개수) 기존의 해싱에서는 슬록의 개수 변화가 거의 모든 키가 다시 재매핑돼야만 했다. (키와 슬롯간의 매핑이 모듈러 연산에 의해 정의되었기 때문)

일관된 해싱은 분산 캐싱을 위해 나오게 되었다. 이는 변화하는 웹서버들의 수들 사이에서 요청을 분산하는 방법의 하나로 소개되었다. 또한 일관된 해싱은 거대한 웹 애플리케이션에서의 부분적인 장애의 충격을 감소시키는 역할을 하는데, 이는 시스템의 전반적인 장애의 결과를 초래하는 것 없이 강력한 캐시를 사용하기 위해서이다. 일관된 해싱은 또한 분산 해시 테이블(DHT) 디자인에 적용할 수 있다. DHT는 분산된 노드들의 집합사이에서 전체 키공간을 파티셔닝하기 위해서 사용한다. 게다가 노드들을 연결해서 노드가 어떤 키가 효과적으로 위치될 수 있도록 하는 오버레이 네트워크를 제공한다.

~~https://ko.wikipedia.org/wiki/일관된_해싱~~

일관된 해싱 - 위키백과, 우리 모두의 백과사전

ko.wikipedia.org

Consistent Hashing 를 적용하게 되면 노드가 추가되었을 때 재할당되는 데이터를 최소화할 수 있다. 아래와 같이 4개의 노드가 있다고 가정하고, 데이터는 시계방향으로 각각 가장 가까운 노드에 저장된다. data 1 은 노드에, data:2 는 B 노드에 , data : 3 은 C 노드에, data:4 는 D 노드에 저장된다.

만약, 신규 노드가 추가가 된다고 가정하자. E 라는 신규 노드가 추가되었다. 그럼, 모든 데이터가 재할당 될 필요가 없다. 노드 D 와 노드 A 사이의 데이터 중에서 일부만 신규 노드에 할당이 되면 된다. 아래 그림을 보자.

data 1 의 데이터만 New Node E 에 재할당된다. 나머지, 데이터는 기존 그대로 노드에 저장이 될 것이다. 노드가 제거가 되는 경우에도 마찬가지이다. 노드 A 가 죽었다고 가정해보자. 노드 A 에 저장되어야 하는 data 1 은 시계방향에 그다음 노드인 B 노드에 저장이 된다.

~~기존 데이터는 그대로 기존 노드에 저장이 된다. 노드가 추가, 제거 되는 경우 데이터의 재할당은 최소화된다.~~

~~힘들다. 자세한 설명은 생략한다..........~~

아래 내용은 읽지 마세요

Consistent Hashing 구현 (1)

Consistent Hashing 을 구현하겠다. 위에서도 얘기했지만, 레디스는 단지 캐싱 서버로의 역할만을 위해서 사용한다. 레디스 클러스터 기능은 매우 훌륭하게 동작하는데, 필자는 레디스 클러스터 기능을 사용하지 않고, 자체적으로 분산캐싱을 구현하였다. 굳이 필자의 방법을 따라할 필요가 전혀 없다. 이 글은, Consistent Hashing 을 이해하기 위해서 작성한 글이라는 사실을 다시한번 명심하길 바란다.

레디스 인프라 구축, 3대의 마스터 노드

레디스 3대 노드를 준비하자. 각 노드는 모두 마스터 노드이고, 별도로 슬레이브가 연동하지 않았다. 또한, 클러스터 기능 및 센티널 인스턴스를 실행하지 않았다. 별개의 싱글 노드가 3대가 실행 중인 상황이다. 각 노드는 노드-A, 노드-B, 노드-C 라고 부르겠다.

~~필자는 특별하게 다른 설정 값을 바꾼것은 없는데, 외부에서의 커넥션이 가능하도록 redis.conf 에서 bind 0.0.0.0 설정만 수정하였다.~~

스프링 부트 환경에서 레디스 연동하기

이 글에서는 스프링 데이터 레디스 디펜던시를 사용하지만, 레디스 커넥션 연동을 커스텀하게 구현할 것이다. 스프링 부트에서 제공하는 AutoConfiguration 을 사용하지 않는다. 일단, 디펜던시는 아래와 같다.

추가로, 리액티브 프로그래밍을 위해서 spring-boot-starter-data-redis-reactive 를 추가하였다 .또한, 해싱 관련 라이브러리를 사용하기 위해서 guava 디펜던시도 추가했다. 인텔리J 를 사용한다면, 아래와 같이 Lombok 사용을 위한 셋팅을 하자.

Config

RedisConnectionFactory 빈을 정의하는데, 레디스 3대 노드 각각의 Bean 으로 정의한다. 필자의 코드는 아주 지저분한데, 필자처럼 하지 말고 IP 는 프로퍼티로 분리하는 것이 좋다. 커넥션풀 설정도 서비스에 맞게 추가해야 하면 좋다. 하지만, 필자의 코드는 단지 이 글을 설명하기 위한 샘플 코드이기 때문에, 커넥션 풀 설정을 별도로 하지 않았다. 그래서, 기본 디폴트 커넥션 풀을 사용한다.

~~만약, 기본 설정을 변경하고 싶다면 아래와 같이 LettuceClientConfiguration를 추가하면 된다.~~

이제, RedisConnectionFactory 를 사용해서 RedisTemplate 를 정의해야 한다. 마찬가지로 3개의 Bean 을 별도로 정의하자. 이때 중요한 점은, Bean 이름을 정의해야 하는데 reactiveRedisTemplateNode[A-C] 로 정의했다.

~~Bean(빈)의 이름은 나중에 노드의 해시코드를 구하기 위한 키로 사용할 것이다. 레디스 직렬화를 위한 설정도 아래와 같이 추가하였다.~~

~~자세한 내용은 레퍼런스를 참고하자.~~

~~https://docs.spring.io/spring-data/data-redis/docs/current/reference/html/#redis:reactive:connectors:lettuce~~

Spring Data Redis

docs.spring.io

~~자세한 설명은 생략한다.......~~

구현을 위한 준비

~~분산 캐싱 구현을 위한 인터페이스를 정의한다. T 는 데이터 타입이 된다.~~

인터페이스의 구현체로 SimpleCacheTemplate 라는 컴포넌트를 정의한다. reactiveRedisTemplateMap 라는 맵타입의 필드가 중요하다. 해당 Map 에는 ReactiveRedisTemplate<String,Person> 타입의 Bean 이 주입이 될 것이다. 맵의 키는 String 타입의 Bean 이름이다. Value 는 ReactiveRedisTemplate 빈이 참조된다. Lombok의 @RequiredArgsConstructor 어노테이션을 사용해서 주입한다.

~~제대로 주입되는지 확인하기 위해서 디버깅을 해보자.~~

~~아래와 같이 Key 에는 Bean 이름이, Value 에는 Bean 이 참조가 될 것이다.~~

위와 같은 방법으로, Config 에서 정의한 reactiveRedisTemplateNode[A-C] Bean 을 어디서든 주입해서 사용할 수 있다. 필자는 주입받은 Bean 을 필자의 용도에 맞게 선언한 nodeMap 필드에 한번 더 초기화한다.

버킷 번호를 구하는 메서드 구현

(Key가 되는 문자열, 해시함수, 해시코드, 버킷사이즈 를 사용한다.)

Consistent Hashing 을 사용해서 노드를 선택하는 기능을 구현하자. 이 글에서 필자는 버킷이라는 단어를 사용하는데, 버킷은 해시함수에 의해 나온 해시코드가 속하게 되는 범위이다. 필자는 버킷 사이즈를 1024 로 정의하였는데, 일단 버킷 번호를 조회하는 함수는 아래와 같다.

필자는 guava 라이브러리를 사용해서 버킷을 계산한다. Hashing.sha256().hashString(문자열) 메서드를 사용하면 해시코드가 생성되는데, 해당 해시코드와 버킷사이즈를 매개변수로 Hashing.consistentHash 메서드를 사용하면, 버킷 번호가 계산된다. 버킷 번호는, 매개변수의 해시코드와 버킷사이즈가 동일하다면 항상 일관된 값이 반환된다. 예를 들어서, "person:eddy" 라는 key 에 의한 해시코드가 29090809383 라고 가정해보자. 해당 해시코드와 버킷사이즈를 파라미터로, Hashing.consistentHash(29090809383, 1024) 를 실행하면 항상 같은 값이 반환될 것이며, 해당 값이 버킷의 번호가 된다. 물론, 해당 값은 최대 버킷사이즈(1024) 범위인 [0~1023] 사이의 값이 될 것이다.

참고로, 카우치베이스(Couchbase) 에서도 버킷이라는 용어를 사용한다. 그리고, 카우치베이스에서는 CRC32 Hashing Algorithm 을 사용한다. 필자의 이 글와 어느정도 연관은 있지만, 필자가 카우치베이스 를 참고하지는 않았다.

~~구현한 메서드에 의해 계산된 버킷 번호를 사용해보자. reactiveRedisTemplate[A-C] 세 개의 문자열에 대한 버킷 번호를 조회하면 아래와 같다.~~

~~189, 397, 28 이 나왔다. 문자열이 바뀌지 않는다면 항상 일관되고 동일한 숫자가 조회될 것이다.~~

데이터 저장

~~데이터를 저장하는 과정은 아래와 같다.~~

~~1. 데이터가 저장되어야 하는 타겟 노드를 찾는다.~~

~~2. 데이터를 타겟 노드에 저장한다.~~

타겟 노드를 찾는 과정에서 필요한 값은 딱 하나인데, 바로 데이터의 키 이름이다. 우리는 데이터의 키 이름으로 노드를 찾을 것이다. 그리고 여기서 말하는 노드는 RedisTemplate에서 커넥션을 맺고 있는 레디스 마스터 노드이다. 필자는 3개의 RedisTemplate 를 정의하였고, 각각의 RedisTemplate 는 A 노드, B노드, C 노드에 커넥션을 맺고 있다.

~~필자가 구현한 getRedisTempalte(키이름) 메서드를 사용해서 RedisTemplate 노드를 조회하는데, Person 객체의 name 필드 값을 레디스의 키로 사용한다.~~

getRedisTemplate 메서드에서는 Key 를 파라미터로 받는데, 해당 Key 로 노드의 이름을 찾아내서 해당 노드에 커넥션을 맺고 있는 Bean 정보를 리턴한다. 즉, redisTemplateMap에서 Bean을 찾는 과정이다.

~~key 로 노드의 이름을 찾는 getNode 메서드는 아래와 같다.~~

~~데이터가 저장될 수 노드를 찾는 알고리즘은,~~

~~데이터의 버킷 번호보다 큰 노드의 버킷번호를 찾아서 가장 가까운 노드에 저장을 하는 로직이다.~~

필자의 매우 허접한 stream 구문을 천천히 같이보자. 우리는 총 3개의 데이터 노드를 사용하며, 노드 각각의 버킷 번호는 A : 189, B : 397, C : 28 이다. stream을 정렬하면 C : 28 --> A : 189 --> B : 397 의 순서로 스트림을 흘려보낸다. 그리고, filter 를 사용해서 데이터가 저장될 수 있는 노드인지 여부를 검사해서 필터링해서 스트림을 흘려보낸다. 데이터가 저장될 수 있는지 여부는 데이터의 버킷 번호보다 노드의 버킷번호가 크면 저장을 할 수 있다. 즉, 노드의 버킷 번호가 데이터의 버킷 번호보다 크다면 filter 메서드로 흘려보낸다. 데이터의 키(이름) 를 파라미터로 getBucketByHashCode 메서드를 사용하면 버킷번호를 조회할수 있는데, 버킷 사이즈가 1024이므로 0~1023 사이의 값이다. 예를 들어서, getBucketByHashCode(key) 의 값이 200이라 가정하면 해당 버킷번호는 3개의 노드(c:28,a:189,c:397) 중에서, 자신보다 큰 버킷 번호를 갖고 있는 B : 397 노드만 스트림으로 보낸다. 그리고 findFirst 에 의해서 B:397 노드가 선택 될 것이다. 만약 getBucketHashCode(key) 값이 5 라고 가정하면 c,a,b 모든 노드를 흘려보내고 그중에서 가장 앞에 위치한 C 노드가 선택될 것이다. 추가로, 데이터의 버킷 값이 1000 이면 어떻게 될까? filter 조건에서 모든 노드의 버킷 번호가 키의 버킷보다 작기 때문에 그 어떤 데이터도 stream 에서 흘려보내지 않는다. 즉, findFirst 로 조회할 수 있는 데이터는 0이다. 이때는, orElse 구문에 의해서 가장 첫번째 노드의 버킷번호를 임의로 설정하게 된다. 즉, C 노드가 선택이 된다.

~~필자의 글이 이해가 되는가? 다시 읽어보니 필자도 이해가 되지 않는다.~~

1만 건 데이터 저장 테스트

~~1만 건의 데이터를 저장해보자. 아주 무식하게 for문 돌려서 저장한다.~~

~~근데, 노드의 전체 데이터를 확인해보니 조금 이상하다.~~

~~A 노드에는 1631개, B 노드에는 2069개, C 노드에는 6300개의 데이터가 저장되었는데,~~

~~C 노드에 너무 많은 데이터가 저장되었다......~~

Consistent Hash Ring

~~Consistent Hash 를 다시 살펴보자. test:[1~5] 의 데이터를 확인해보면, 아래와 같이 해당 키는 해시함수에 의해서 0~1023 사이의 버킷 번호를 할당받게 된다.~~

Consistent Hash 룰에 의해서, 자신의 버킷번호 보다 큰 노드에 데이터를 저장하는데, test:1~test:5 데이터는 아래 그림과 같이 B 노드와 C 노드 사이에 버킷이 위치한다. 그래서, 해당 데이터는 전부 Node C 에 저장이 될 것이다.

이런 이유는, 3개의 노드가 원에서 고르게 분산되지 않았기 때문이다. 노드의 버킷 번호가 모두 원의 우측에 쏠려 있다. 그래서, 확률적으로 데이터가 고르게 분산되지 않았던 것이다. 이런 경우에는 특정 노드가 제거 되었을 때도 문제가 발생하는데, 예를들어서, Node C 가 죽게되면 그 다음 버킷에 위치하고 있는 Node A 에 데이터가 전부 재할당이 되어야 한다. 아래 그림을 참고하자.

좋지 않은 아키텍처이다. 이런 상황을 개선하기 위해서는, 죽어버린 노드 C 에 저장되었던 데이터를 노드 A 에 모두 저장하지 않고, 노드 A 와 노드 B 에 분산해서 저장하면 더 좋을 것이다. 그래서 이런 상황을 보완하기 위해서, Consistent Hashing 가상 노드 개념을 적용해야 한다.

Consistent Hashing 구현 (2) - 가상노드

위 구현 사례를 보완하기 위해서, 가상노드를 적용한다. 노드를 A, B, C 이렇게 세개만 구성하는 것이 아니라 A-0, A-1, A-2 ... B-0, B-1, B-2... 이렇게 더 많은 노드를 가상 노드로 정의한다. 물론 실제 물리서버는 3대이다.

~~A-[0-...] 의 데이터는 전부 A 노드에 저장이 되고, 마찬가지로 B-[0-...] 노드는 실제로는 B 노드에 저장된다.~~

코드 수정 및 테스트

~~그리고, 실제 노드 정보를 가져오는 로직에서 -0[1-5] 를 제외하는 로직을 추가하였다.~~

~~테스트 코드를 다시 돌려서 1만개의 데이터를 저장해보자. 아래와 같이 나름(?) 분산이 되어 저장이 되는 것을 확인할 수 있다.~~

~~버킷 번호는 아래와 같다.~~

가상노드를 사용하지 않았을 때는 test:1~5 의 모든 데이터가 C 노드에 집중이 되었는데, 이번에는 그렇지 않다. A, B, C 노드에 고르게 분산이 되는 것을 확인할 수 있다.

완벽하지는 않다.

필자가 임의로 만든 해싱룰이기 때문에 빈틈이 존재 한다. 그림을 보면 원의 3시~6시 에는 노드 분산이 잘 안되었다. 즉, 해당 영역에 위치하는 키는 B-02 가상노드에 저장되는데, 즉, 실제 B 노드에 데이터가 더 많이 저장이 될 것이다.

위와 같이 필자의 방법은 빈틈이 있는데, 더 효율적인 분산 방법으로 고도화를 해야한다. 어쨋든, 이 글에서는 Consistent Hashing 구현은 이정도 수준으로만 살펴보겠다. 머리가 아프다. 필자의 허접한 샘플 코드는 github 에서 확인하길 바란다. 코드는 사실 중요하지 않다. Consistent Hashing 개념만 이해하면 된다.

~~https://github.com/sieunkr/consistent-hashing~~

sieunkr/consistent-hashing

Contribute to sieunkr/consistent-hashing development by creating an account on GitHub.

github.com

몇가지 더 검토가 필요한 내용

~~머리가 좀 아프지만, 몇가지 더 검토가 필요한 내용을 간단하게 정리해보겠다.~~

특정 키에 조회가 집중되는 경우가 발생하면?

데이터 노드를 분산했지만, 특정 키에 집중이 될 수 있다. 이런 경우는 어떻게 해야할까? 필자가 해본적은 없어서 잘 모르겠지만, 카카오의 사례를 참고하길 바란다.

~~https://tech.kakao.com/2017/10/23/wcache-1/~~

~~https://tech.kakao.com/2017/10/23/wcache-2/~~

데이터 저장소 VS 분산 캐시

필자의 글은 분산캐싱을 위한 글이다. 만약, 캐시 저장소로서의 인프라가 아니라, 데이터 저장소 인프라로 사용한다면 좀 더 섬세하게 검토가 필요하다. 만약 노드 A 가 죽게 되면, 일시적으로 데이터 조회를 못하는 상황이 발생할 수 있다. 캐시 데이터는 새로 만들어서 신규 노드에 저장 및 조회를 하면 된다. 하지만, 핵심 데이터를 저장하고 있다면 얘기가 많이 달라진다. 그래서, 이런 경우에는 Replication 을 적용해야 할 것이다. 이론적인 방법은 간단하다. Consistent Hash 룰에 의해서 가장 가까운 노드에 먼저 저장하고, 그 다음으로 가까운 노드에 저장을 하는 방식으로 Replication 을 구현할 수 있다. 아래 그림과 같이, data:key 를 A 노드에 먼저 저장하고, 그 다음 데이터를 B 노드에 저장하는 방식이 될 것이다.

이런 경우 A 노드가 죽으면, B 노드에서 데이터를 조회하면 된다. A 노드가 다시 살아나면 A 노드에서 다시 데이터를 조회하면 되는데, A 노드가 죽었던 사이에 변경된 데이터는, B-A 노드 사이에 싱크를 맞춰주는 작업을 해야한다. 조금 많이 복잡해진다.

Read From Slave

항상 그런건 아니지만, 일반적으로 데이터를 Read(조회) 할때보다, Write(저장) 하는 경우에 더 많은 리소스가 필요하다. 레디스 같은 싱글쓰레드 환경에서 동작하는 저장소는 더더욱 그렇다. Redis 를 사용하면서 Write 비율이 Read 비율보다 훨씬 높다면, Redis 인프라 구축에 신경을 많이 써야 하는데, Write 비율이 50%가 넘는다면 Read From Slave 인프라 환경을 구축해야 한다. 데이터를 조회하는 하나의 그룹에 마스터-슬레이브 노드 구성의 인프라 환경으로 구축하고, 고가용성을 위해서 센티널 인스턴스를 별도로 실행하는 것이 좋겠다. 아래와 같이 구성이 가능할 것이다. 참고로... 필자는 이렇게 구축해본적은 없다. 여러가지 추가 문제가 발생할 수도 있다. 필자는 이 구성이 좋다고 말은 못하겠지만, 이런식으로도 구성이 가능할 것이다.

Multi get

레디스는 기본적으로 multi get 커맨드를 지원한다. 10개의 키를 동시에 조회한다고 가정하자. 1번 호출에 10개의 데이터를 한번에 응답받는 방법과 1번 호출에 1개 데이터씩 10번 호출하는 방법 중 어떤 방법이 효율적일까? 필자의 경험에 의하면 1번 호출에 10개의 데이터를 한번에 호출하는 방법이 훨씬 성능이 좋다. 단, 클러스터 환경에서는 데이터가 분산되어 저장되어 있기 때문에 구현하는게 조금 까다롭다. 일단, 어떤 키가 어떤 노드에 저장되어야 하는지 클라이언트 측에서 알수 있어야 한다. 조회하는 데이터 키 리스트가 같은 노드에 저장되어 있는지 확인을 하고, 만약 모든 키가 하나의 노드에 저장되어 있다면 해당 노드에서만 1번에 키 리스트로 조회를 하면 된다. 하지만, 조회하고 싶은 키 리스트가 두 개 이상 노드에 할당되어 있다면 1번의 호출로 데이터 리스트를 전달 받을 수 없는데, 키를 저장하고 있는 모든 노드에 데이터를 조회할 수 밖에 없다.

~~샘플 코드를 심플하게 구현해보자. 일단, 키 리스트를 파라미터로 키에 해당한 노드의 맵 정보를 조회하는 메서드를 구현하자.~~

~~그리고, 해당 맵 정보를 기반으로, 모든 키가 같은 노드에 저장되어 있는지 여부를 확인하는 메서드를 아래와 같이 구현하였다.~~

mGet 명령은 단일 데이터가 아니기 때문에, 리턴 타입은 Mono 가 아니라, Flux 로 정의할 것이다. 아래와 같이 메서드를 작성하였다. Flux<Person> 으로 리턴한다.

해당 메서드의 if 문을 보자. isSameSlot 메서드에 데이터의 키 리스트를 파라미터로 넘기면, 해당 키가 전부 같은 노드에 있는지 확인한다. 만약, 같은 노드라면 키 중 아무 데이터를 사용해서 노드의 RedisTemplate 를 가져온 후, multiGet 메서드를 수행한다. multiGet 메서드에 의해서 리턴되는 값은 Mono<List<Person>>> 인데, Flux<Person> 으로 변환해주기 위해서 flatMapMany 를 마지막으로 적용해준다. 만약, 데이터 키 리스트가 동일 노드에 속하지 않는다면 어떻게 될까? 아래와 같이 키 리스트를 스트림으로 흘려보내면서, 하나하나 데이터를 개별적으로 조회를 한다. 네트워크 비용이 꽤 많이 발생할 것이다.

조금 더 개선한다면, 같은 노드에 해당하는 키만 리스트로 따로 분리해서 호출한다면, 노드 총 개수만큼만 호출하게 개선할 수 있을 것 같다. 귀찮아서 추가 개선은 하지 않았다. 필자의 코드가 아주 그지같으니, 코드리뷰를 잘하는 개발자는 필자의 코드를 한번 보고 개선할 점이 있으면 언제든지 의견을 전달해주길 바란다.

좋은 솔루션을 찾아서 사용하는게 좋을 수도..

복잡한 분산캐싱을 구현하기 위해서 개발일정을 사용하는 것보다는, 좋은 솔루션을 찾아서 사용하는게 좋을수도 있다. 수레바퀴를 재발명할 필요는 없다. 하지만, 너무 많은 대안이 있어서, 좋은 선택을 하는 것은 쉽지 않다. 많은 고민을 하길 바란다. 지금 나열하는 목록은 필자가 생각나는대로 작성을 하였다. 좋고 나쁨에 대해서는 논하지 않았고, 여기서 빠졌다고 해서 나쁜 솔루션이 아니다. 단지, 필자가 생각나는대로 작성했을 뿐이다.

큰 회사라면, 직접 구현하는 방법이 가장 좋을수도 있다.

~~카카오의 사례를 참고하자. 역시 큰회사는 뭔가 클래스가 다르다.~~

~~https://tech.kakao.com/2017/10/23/wcache-1/~~

분산 웹 캐시 (Wcache)의 개선과정 – Part 1

Overview 웹 서비스의 규모가 커지고 이용자의 수가 늘어날수록 서비스 제공자는 scalability 이슈에 직면합니다.그중에서도 실제 ‘로딩 속도’의 차이를 느끼게 해 주고 트래픽의 대부분을 차지하는 정적 컨텐츠의 신속한 제공은 서비스 품질을 좌우하는 중요한 요소가 되곤 합니다. 이런 수많은 컨텐츠들(Javascript, css, image 등)을 빠르게 제공하기 위해 클라이언트와 서버 사이에 위치하며 컨텐츠를 임시로 저장하는 Middlebox를 웹

tech.kakao.com

레디스 클러스터

레디스 클러스터도 좋은 대안이다. 참고로 필자는 레디스 클러스터 인프라로 현재 실무에서 서비스를 운영중이인데, 대용량 트래픽에서 충분히 훌륭한 퍼포먼스를 낼 수 있다.(비록 카카오 세미나에서 카카오톡 서비스에서는 레디스 클러스터가 퍼포먼스가 안나온다고 말했지만...) 필자는 개인적으로 센티널 인스턴스도 구축해본적이 있는데, 레디스 클러스터 와 센티널 두가지 방식 중 어떤 기술이 좋은지 선택하기가 쉽지 않다. 서비스 및 시스템, 개발자의 역량 등 전반적인 상황에 맞게 잘 선택하길 바란다.

넷플릭스 EVCache

~~넷플릭스 공개한 오픈소스를 사용해보는 것도 좋은 선택이 될 수 있다.~~

~~https://www.slideshare.net/PivotalKorea/ss-154455324~~

숨겨진 마이크로서비스: 초고속 응답과 고가용성을 위한 캐시 서비스 디자인

넷플릭스에서는 높은 속도로 데이터를 제공하기 위해서 뿐만 아니라 멀티 리전의 데이터 가용성을 바탕으로한 전체 서비스 가용성 유지를 위해 캐시를 사용하고 있습니다. 이 앞의 세션에서 보았던 마이크로서비스 구조를 염두해 둘때 한가지 가장 간단한 변화는 외부 클라이언트로 부터 유입되는 단 …

www.slideshare.net

Memcached

~~Memcached 는 오래전부터 사용되던 분산캐싱 오픈소스이다. 참고로, 넷플릭스의 EVCache 가 Memcached 기반으로 개발이 된것으로 알고 있다.~~

카산드라

~~필자가 잘 몰라서, 자세한 설명은 생략한다.~~

Ehcache + 기타 솔루션

~~Ehcache 에 기타 솔루션을 연동해서 분산캐시 구현이 가능하다.~~

IMDG 을 활용해도 된다.

~~HazelCast 나 Ignite 같은 인메모리 데이터 그리드를 사용해도 분산캐싱을 구현할 수 있을 것 같다..~~

~~(해보지 않아서 잘 모르겄다)~~

무식하게 구현할 수도 있다.

아주 무식하지만, 애플리케이션에서 메모리를 저장하고 있어도 된다. 근데, 이 경우 동기화의 이슈가 있어서 조금 까다롭다. 그리고, 애플리케이션이 다운되면 캐시 데이터는 휘발성으로 사라질수 있다. 하지만, 이런 단점에도 불구하고 이 방법을 실무에서 꽤 많이 사용한다. 캐시 데이터가 덜 중요하고, 애플리케이션에서 들고 있는는 데이터의 양이 많지 않다면 심플하게 애플리케이션에 캐싱을 저장하는 것도 나쁘지 않은 선택이 될 수 있다. 단, 중요한 데이터는 절대 이렇게 저장하면 안된다.

방법이 너무 많다.

~~전부 나열하기 힘들 정도로 수많은 방법이 있다. 서비스 상황에 맞게 잘 선택하자.~~

글을 마무리하면서

생각의 흐름대로 하루종일 글을 작성했는데 막상 천천히 다시 읽어보니 뭔소리인지 이해가 안되는 구문이 있다. 글이 너무 길어졌는데, 이 글을 힘겹게 읽어준 개발자가 있다면 진심으로 감사하게 생각한다. 이번 기회에 데이터 분산에 대해서 아주 조금은 이해를 하게 되는 계기가 되었는데, 나중에 데이터 분산 관련 프로젝트를 할 기회가 오면 그때 해당 주제로 다시 글을 작성하겠다.

레퍼런스

지난 주말, 이번 주말 포함해서 최근 몇일 동안 봤던 레퍼런스를 정리하였다. 사실, 이 글과 관련 없는 링크도 있는데, 필자가 따로 정리할 시간이 없어서 봤었던 링크 전부를 남기겠다. 백엔드 아키텍처에 관심이 있는 개발자는 링크를 하나하나 읽어보길 바란다. 필자도 나중에(?) 시간이 되면 하나씩 다시 읽어볼 예정이다.

~~(시간이 될지 모르겠지만...핑계)~~

~~https://www.slideshare.net/PivotalKorea/ss-154455324~~

~~https://timewizhan.tistory.com/m/entry/Netflix-Distributed-Inmemory-Datastore~~

~~https://medium.com/netflix-techblog/distributing-content-to-open-connect-3e3e391d4dc9~~

~~https://jistol.github.io/software%20engineering/2018/07/07/consistent-hashing-sample~~

~~https://blog.hltbra.net/2019/02/18/consistent-hashing.html~~

~~https://www.slideshare.net/mobile/quipo/nosql-databases-why-what-and-when/73-Consistent_Hashing_Replication_A_F~~

~~https://www.ably.io/blog/implementing-efficient-consistent-hashing/~~

~~https://highlyscalable.wordpress.com/2012/09/18/distributed-algorithms-in-nosql-databases/~~

~~https://www.ably.io/blog/implementing-efficient-consistent-hashing/~~

~~http://cassandra.apache.org/blog/2018/12/03/introducing-transient-replication.html~~

~~https://docs.microsoft.com/ko-kr/azure/architecture/patterns/sharding~~