분산 시스템에서 부하 분산을 우아하게: Elixir로 구현하는 HRW 알고리즘

부하 분산, 왜 자꾸 다시 이야기될까

서버를 여러 대 운영하다 보면 꼭 마주치는 문제가 있어요. "이 요청을 어느 서버로 보낼까?"라는 질문이죠. 사용자 1번 요청은 A 서버로, 2번은 B 서버로, 이런 식으로 잘 나눠줘야 한 서버에만 부하가 몰리지 않거든요. 이걸 부하 분산(load balancing)이라고 하는데, 단순히 "돌아가면서 보내자"는 라운드 로빈 방식부터 시작해서 정말 다양한 알고리즘이 있어요.

그런데 캐시 서버처럼 "같은 키는 항상 같은 서버로 가야 하는" 상황에선 라운드 로빈으로는 부족해요. 예를 들어 사용자 ID 12345의 세션 정보가 A 서버 메모리에 저장돼 있는데, 다음 요청이 B 서버로 가버리면 캐시 미스가 나잖아요. 그래서 등장한 게 일관된 해싱(consistent hashing)이라는 기법이고, 이번에 소개할 HRW(Highest Random Weight, 최고 가중치 해싱)도 같은 계열의 알고리즘이에요. 이걸 Elixir라는 함수형 언어로 깔끔하게 구현한 사례를 살펴볼게요.

HRW가 뭐냐면, 이런 원리예요

HRW 알고리즘은 '랑데부 해싱(rendezvous hashing)'이라고도 불려요. 동작 원리가 굉장히 직관적인데요, 어떤 키가 들어오면 그 키와 모든 서버 이름을 한 쌍씩 묶어서 해시값을 계산해요. 그러니까 서버가 5대라면, (키, 서버1), (키, 서버2), ..., (키, 서버5) 이렇게 5개의 해시값이 나오는 거죠. 그중에서 가장 큰 해시값을 가진 서버를 선택하면 끝이에요. 이름 그대로 "가장 높은 가중치"를 가진 서버를 고르는 방식이죠.

뭐가 좋냐면, 서버를 추가하거나 빼도 키의 재배치가 최소화돼요. 일반적인 해시 기반 분산(예: hash(key) % 서버수)에서는 서버 한 대만 빠져도 거의 모든 키가 다른 서버로 옮겨가야 하는데, HRW에서는 떠난 서버에 매핑돼 있던 키들만 새로 분산되거든요. 나머지 키들은 여전히 "두 번째로 큰 해시값을 가진 서버"가 그대로 있으니까 옮길 필요가 없는 거예요. 1996년에 처음 발표된 알고리즘인데, 지금도 CDN이나 분산 캐시 시스템에서 활발하게 쓰이고 있어요.

Elixir로 구현하면 왜 우아할까

Elixir는 함수형 언어이고, Erlang VM(BEAM이라고 불러요) 위에서 돌아가요. 이게 뭐가 특별하냐면, 동시성(여러 일을 동시에 처리하는 것)과 분산 처리에 정말 강해요. WhatsApp이 수억 명의 동시 접속을 Erlang으로 처리한 사례가 유명하죠.

이 글의 저자는 HRW 알고리즘을 Elixir로 구현했는데, 코드가 거의 알고리즘 정의 그대로 나와요. Enum.map으로 모든 서버에 대해 해시값을 계산하고, Enum.max_by로 가장 큰 값을 가진 서버를 골라내는 식이죠. 명령형 언어로 짜면 for 루프 돌면서 최댓값 변수 관리하고 어쩌고 하는데, 함수형으로 짜면 "각 서버에 함수를 적용하고, 최댓값을 고른다"는 한 줄 표현이 가능해요. 알고리즘의 본질이 코드에 그대로 드러나는 거죠.

해시 함수로는 보통 SHA나 MurmurHash 같은 걸 쓰는데, 중요한 건 균일하게 잘 퍼지는 함수면 된다는 거예요. 가중치를 주고 싶으면 (예: 성능 좋은 서버에 더 많은 트래픽 보내기) 해시값에 가중치를 곱해주는 식으로 변형할 수도 있어요. 이걸 가중 HRW(Weighted HRW)라고 하고요.

일관된 해싱과 비교하면

비슷한 문제를 푸는 알고리즘으로 '일관된 해싱(consistent hashing)'이 더 유명해요. Amazon DynamoDB, Apache Cassandra, 그리고 많은 분산 캐시들이 이걸 써요. 일관된 해싱은 서버들을 거대한 원(해시 링) 위에 배치하고, 키도 같은 원 위에 놓은 다음, 시계 방향으로 가장 가까운 서버를 고르는 방식이에요.

HRW와 일관된 해싱은 둘 다 "서버 추가/제거 시 재배치 최소화"라는 목표를 달성하는데요, HRW가 더 단순하고 분포가 더 균일하다는 장점이 있어요. 반면 일관된 해싱은 서버 수가 많을 때 키 검색이 더 빠르고(이진 탐색 가능), 가상 노드 같은 기법으로 부하 균형을 미세 조정하기 쉬워요. 그래서 "적당한 규모에선 HRW, 대규모에선 일관된 해싱"이라는 경험칙도 있어요.

한국 개발자에게 주는 시사점

혹시 사이드 프로젝트나 회사에서 Redis 클러스터, Memcached, 또는 자체 캐시 서버를 운영하고 있다면 HRW를 한 번쯤 검토해볼 만해요. 특히 서버 수가 10~50대 정도의 중간 규모에서는 일관된 해싱보다 구현이 단순하면서도 분포가 더 균일하다는 평가가 있거든요. Elixir를 쓰지 않더라도, Python, Go, Java 어떤 언어로도 50줄 안에 짤 수 있을 만큼 단순한 알고리즘이에요.

그리고 Elixir/Phoenix 생태계에 관심이 있다면 이번 기회에 한 번 들여다봐도 좋아요. 카카오나 우아한형제들 같은 곳에서도 일부 트래픽이 많은 서비스에 Elixir를 검토했다는 이야기가 있고, 토스의 일부 백엔드 팀도 함수형 프로그래밍에 관심이 많은 걸로 알려져 있어요. 분산 시스템과 동시성을 진지하게 다루려면 한 번쯤 만나보게 되는 언어예요.

마무리

부하 분산은 "어떻게 잘 나눌까"라는 단순해 보이는 문제지만, 그 뒤에 30년 가까이 쌓인 알고리즘 역사가 있어요. HRW는 그중에서도 단순하고 강력한 해법이고요. 여러분의 서비스에서는 지금 어떤 방식으로 트래픽을 분산하고 있나요? 그게 정말 최적의 선택인지, 한 번 점검해볼 기회가 될지도 모르겠어요.