데이터베이스 샤드 개수가 늘어나거나 줄어들 때, 리해시를 해야 하는 총 레코드 개수가 10억 개 정도로 매우 많으면 어떤 일이 발생할까요? 수평 확장된 데이터베이스가 정상 작동하려면 장시간 리해시를 해야 할 것입니다. 즉, 게임 서버 점검 상태가 되어야 할 것입니다. 물론 이 점검 시간은 레코드 개수가 많을수록 길어지겠지요. 여러분 게임 서비스가 장시간 점검 시간을 용납할 수 없다면 이는 심각한 문제가 될 것입니다.

이 문제를 개선하려면 데이터베이스 샤드가 추가되거나 제거될 때 레코드 이동으로 발생한 정지 순간이 최소한이어야 합니다.

이를 위해 크게 다음 세 가지 방법이 있습니다.

1. 이동하는 레코드 개수가 최소가 되는 알고리즘을 사용합니다.

2. 이동할 일이 없게 만듭니다.

3. 이동하더라도 이동하는 레코드 크기를 최소로 만듭니다.

첫 번째 방법은 일관된 해시(consistent hash) 알고리즘으로 해낼 수 있습니다. 두 번째 방법은 매핑 DB를 두어서 해낼 수 있습니다. 세 번째 방법은 두번째 방법의 매핑 DB에서 사용됩니다.

첫 번째 방법인 일관된 해시부터 알아봅시다. 일반적인 해시 테이블에서는 리해시를 할 때 거의 모든 키(각 레코드에 대응)에 대해 재배치 연산을 해야 합니다. 일반적인 해시 테이블을 사용해서 데이터베이스를 샤딩할 때는 샤드가 1개 늘어나더라도 모든 레코드 개수만큼 재배치 연산을 해야 합니다. 모든 샤드가 바빠지죠.

일관된 해시 알고리즘을 사용하면 샤드가 1개 늘어나더라도 다른 샤드 중 하나만 재배치 연산을 하면 됩니다. 이것이 어떻게 가능할까요?