1. 상황: 서버 하나로 버틸수가 없다

서비스가 커지면서 트래픽이나 데이터가 너무 많아져 서버 한 대로 버틸 수 없는 상황이 됐다고 해보자.

그래서 서버를 3대로 늘렸다. 그러면 이제 새로운 문제가 생긴다. 어떤 데이터를 어느 서버에 둘 것인가?

"user-1"  -> 어느 서버?
"user-2"  -> 어느 서버?
"user-3"  -> 어느 서버?

이 결정에는 규칙이 필요하다. 그리고 그 규칙은 최소한 아래 두 가지를 만족해야 한다.

같은 key는 항상 같은 서버로 가야 한다. 쓸 때는 A에 쓰고 읽을 때는 B에서 찾으면 안 되니까.
데이터가 서버들에 고르게 퍼져야 한다. 한 서버에만 트래픽이나 데이터가 몰리면 서버를 늘린 의미가 없음.

분산 캐시든, 분산 DB든 "여러 대에 나눠 담기"를 하는 시스템은 전부 이 문제를 풀고 있다.

이번 글에서는 이 문제를 가장 단순한 방법으로 풀기 시작하고 consistent hashing 이라는 개념이 나온 이유와 원리를 설명한다.

2. 첫 번째 시도: hash(key) mod N

2.1 mod 방식은 쉽고, 잘 동작한다

앞선 문제를 풀기 가장 쉬운 방식은 mod를 사용하는 것이다. 데이터에 대한 key 값을 hash해서 숫자로 만들고, 서버 수로 나눈 나머지를 쓰는 방식이다.

int serverIndex = hash(key) % N;  // N = 서버 수

이 방법은 위에서 말한 두 조건을 깔끔하게 만족한다. 같은 key는 항상 같은 hash 값을 가지니 같은 서버로 가고, hash 함수가 균등하다면 데이터도 고르게 퍼진다. 계산도 O(1)이고, 서버들끼리 뭔가를 공유할 필요도 없다.

낯선 방식도 아니다. Spring에서 샤딩된 DB를 쓸 때 AbstractRoutingDataSource 같은 라우팅 계층에서 hash(userNo) % shardCount로 데이터소스를 고르는 코드는 실무에서도 흔하게 볼 수 있다. 이 방식의 장점은 분명하다. 단순하고, 매핑 테이블 같은 상태를 어딘가에 보관할 필요가 없고, 어느 서버에서 계산해도 같은 결과가 나온다.

그래서 샤드 수가 고정이라는 전제가 있다면 굉장히 합리적인 선택이다. 문제는 서버 수가 변할 때 생긴다.