데이터를 어디에 저장해야 하는지 어떻게 알 수 있을까요? 마찬가지로 중요한 것은 스토리지 노드에 장애가 발생하거나 시스템 확장을 위해 새 스토리지 노드를 추가하면 어떻게 될까요? 해시는 이 시나리오에서 데이터를 저장할 위치를 결정하는 일반적이고 효율적인 방법이며, 특히 데이터 스트리밍 애플리케이션을 구현하는 경우 이해해야 할 중요한 요소입니다.

해싱이란 무엇인가요?

해싱은 '해시 테이블'과 '해시 함수' 또는 알고리즘을 사용하여 파일이나 임의의 문자열과 같은 가변 크기 데이터를 일관된 고정 크기 출력으로 변환합니다.

해시 함수(또는 일관된 해시 알고리즘)는 데이터를 받아 해당 데이터를 나타내는 숫자를 출력하는 수학적 연산으로, 그 값은 제공된 데이터의 원래 크기보다 훨씬 작습니다. 해시 함수가 출력하는 숫자를 '해시'라고 하며, 동일한 데이터로 해시 함수를 호출할 때마다 값이 일정하게 유지됩니다. 그런 다음 해시 테이블에서 데이터를 조회할 수 있습니다.

아주 간단한 예로 모듈로 연산자(%)를 해시 함수로 생각해 보겠습니다. 모듈로 연산자에 제공된 숫자의 크기에 관계없이 [데이터] mod n에 대해 지정된 범위 n 내에서 일관된 숫자를 반환합니다:

69855 MOD 10 = 5

63 MOD 10 = 3

916 MOD 10 = 6

26666 MOD 10 = 6

마지막 예시는 서로 다른 입력이 동일한 해시 값인 6을 생성하는 '충돌'을 보여줍니다. 또한 해시 함수를 조정하여 출력 범위를 변경하는 방법(예: x MOD 20 또는 x MOD 30)을 볼 수 있습니다.

실제 해시 구현에서는 예상되는 입력 데이터에 따라 충돌을 처리하고 메모리를 가장 효율적으로 사용하기 위해 더 복잡한 해시 함수가 사용됩니다.

해싱을 사용하는 이유는 무엇인가요?

해싱의 일반적인 예는 데이터 저장 및 검색입니다. 150억 개의 항목으로 구성된 컬렉션이 있는데 특정 항목을 검색해야 한다면 어떻게 해야 할까요? 한 가지 메커니즘 방법은 데이터 집합을 반복하는 것이지만 키-값 저장소의 키 수가 증가하면 비효율적이므로 해시를 사용하는 것이 더 좋습니다.

이 방법은 다음과 같이 작동합니다:

데이터 항목을 저장할 때 먼저 해시 함수를 통해 데이터와 연결된 키를 실행합니다. 결과 해시를 기반으로 해시된 위치의 해시 테이블에 데이터를 저장합니다. 충돌이 발생하는 경우 데이터가 손실되지 않도록 조치를 취해야 합니다. 예를 들어 해시 테이블에 데이터 자체 대신 데이터의 연결된 목록을 저장하거나(체인 해싱), 빈 슬롯을 찾을 때까지 해시 함수가 계속 찾을 수 있습니다(프로빙 또는 이중 해싱 기술 포함).
데이터 항목을 검색할 때는 다시 해시 함수를 통해 데이터와 연결된 키를 실행한 다음 해시 테이블에서 결과 해시 코드를 조회합니다.

데이터에 대한 키가 이미 있다면 그 키를 직접 사용하여 데이터를 저장하지 않을까요? 예를 들어 배열의 인덱스로 사용할 수 있지만(아무것도 하지 않는 해시 함수를 사용하는 것과 같지만) 매우 비효율적입니다. 키가 매우 크고 연속되지 않는 경우에는 어떻게 해야 하나요?

분산 시스템에서의 해싱

이전 예제에서는 해시 테이블을 사용하여 대량의 데이터 항목 목록을 저장하고 검색하는 방법에 대해 설명했지만, 그 목록이 여러 서버에 물리적으로 분산되어 있다면 어떻게 해야 할까요?

해시 함수를 사용하여 분산 시스템에서 데이터를 저장할 위치를 결정할 수 있습니다. 이전 예제에서처럼 해시 테이블의 위치를 가리키는 해시 함수 대신 분산 시스템에서 IP 주소에 매핑할 수 있는 서버 ID를 출력으로 하는 다른 해시 함수를 사용할 수 있습니다.

예를 들어 분산 시스템에 데이터를 저장할 때는 먼저 데이터와 연결된 키를 해시하여 데이터를 저장할 서버 ID를 생성한 다음 해당 서버에 데이터를 저장합니다. 사용 가능한 모든 서버에 출력이 균일하게 분산되는 해시 함수를 선택하면 어떤 서버에도 과부하가 걸리지 않고 데이터를 빠르게 검색할 수 있습니다. 비슷한 방식으로 서버 수를 늘려 서버 부하를 분산하는 로드 밸런싱을 고려할 수도 있습니다.

데이터를 저장할 수 있는 5개의 서버 목록이 있고 각 서버에 1부터 5까지 고유 ID를 할당했다고 가정해 보겠습니다. 이 예에서는 해당 데이터 키의 해시를 기반으로 데이터를 저장할 서버를 결정합니다:

저장하려는 데이터의 키를 나타내는 해시 코드를 생성합니다. 결과 해시 코드는 1에서 5 사이의 범위여야 합니다(서버가 5개이므로).
앞의 예제에서는 해시 함수에 매우 간단한 모듈로를 사용했는데, 여기서 해시 함수는 '[키] MOD 5'라고 생각하면 됩니다.
ID가 계산된 서버에 파일을 저장합니다.

이렇게 하면 작동하지만 서버가 다운되면 어떻게 될까요? 새 서버가 추가되면 어떻게 될까요? 두 경우 모두 모든 데이터는 해시를 다시 계산하고 새 해시 결과에 따라 이동해야 하는데, 이는 비효율적이며 위의 접근 방식은 너무 단순하여 프로덕션 환경에서 사용하기에 부적합합니다.

일관된 해싱이란 무엇인가요?

일관된 해싱은 서버 추가 또는 제거를 허용하면서 분산 시스템에서 데이터를 저장할 위치를 결정하여 인프라 변경 시 이동하거나 재해시해야 하는 데이터의 양을 최소화합니다.

일관 해싱과 해싱의 차이점

해싱은 가변적인 양의 데이터를 가져와서 빠르고 효율적인 검색을 위해 해시 테이블이라는 일관되고 고정된 크기의 저장 구조에 저장되도록 줄이는 일반적인 기술입니다. 선택한 해시 테이블의 크기는 저장되는 데이터의 양과 사용 가능한 시스템 메모리와 같은 기타 실용적인 고려 사항에 따라 달라집니다. 해시 테이블의 크기가 조정되면 일반적으로 해시 함수도 변경되어 새로 조정된 테이블에 데이터가 고르게 분산되므로 모든 데이터를 다시 해싱하고 이동해야 합니다.

일관된 해싱은 해시 테이블의 크기를 조정할 때 데이터의 일부만 이동하면 되는 특별한 종류의 해싱입니다. 구체적으로 이동해야 하는 데이터 항목의 수는 n/m이며, 여기서 n은 데이터 항목의 수, m은 해시 테이블(또는 앞의 분산 시스템 예시에서는 서버)의 행 수입니다.

일관된 해싱은 어떻게 작동하나요?

일관된 해싱을 사용하면 데이터를 보관하는 서버(또는 가상 노드)가 원 안에 시계 방향으로 배열되어 있고 번호가 매겨져 있다고 상상해 보세요. 보다 직관적으로 이해하기 위해 대부분의 그림에서는 노드에 1에서 360(도)까지 번호를 매기지만, 실제 선택된 번호와 연속 여부는 중요하지 않으며, 중요한 것은 한 서버에서 다른 서버로 시계 방향으로 원을 중심으로 경로를 추적할 때 할당된 서버 ID가 올라간다는 점입니다. 다음 노드의 ID는 감싸기 전까지는 항상 이전 노드보다 커집니다.

데이터를 저장할 서버를 결정할 때는 데이터의 해시를 계산한 다음 해당 해시의 계수를 360으로 취합니다. 결과 숫자가 유효한 서버 번호와 정확히 일치하지 않을 수 있으므로 결과 숫자에 가장 가깝고 큰 서버 ID를 선택합니다. 결과 숫자보다 큰 서버가 없으면 다시 0으로 랩어라운드하고 서버 ID를 계속 찾습니다.

예를 들어

해시 함수가 적용된 일부 데이터 키가 존재하며 그 결과는 5562입니다.
5562 MOD 360은 162입니다.
배포에서 ID가 162보다 크지만 162에 가장 가까운 서버(예: 아래 다이어그램의 ID 175)를 찾습니다.

서버가 360개가 없거나 360개보다 많으면 어떻게 하나요? 숫자는 중요하지 않으며 원칙만 중요합니다. 선택한 서버 ID가 오름차순으로 번호가 매겨지고, 합리적으로 균등한 간격으로 배치되어 있으며, 개념적으로 링(해시 링이라고 함)으로 배열되어 있으면 됩니다.

일관된 해싱을 사용하는 이유는 무엇인가요?

데이터가 여러 노드(또는 서버)에 분산되어 있는 경우 시스템에서 노드를 추가하거나 제거하는 것이 훨씬 더 효율적입니다. ID가 90, 180, 270인 3개의 노드 A, B, C가 있는 예를 생각해 보겠습니다. 이 설정에서 각 노드는 데이터의 3분의 1을 담고 있습니다.

새 노드인 D를 추가하려면 360이라는 새 ID를 할당합니다.

이제 D를 비워두고 데이터가 저장되면서 천천히 채워지도록 할 것인지, 아니면 다른 노드의 데이터를 D로 재분배할 것인지 선택할 수 있습니다. 어떤 선택을 할지는 구현되는 솔루션에 따라 다릅니다. 웹 캐싱 및 캐시 서버 구현은 전자를 수행하여 캐시 누락이 D를 천천히 채우도록 하고 다른 솔루션은 A에서 데이터의 절반을 가져와 D로 전송합니다(수학을 너무 깊게 다루지 않고 전송되는 데이터가 새 데이터인 경우 D에 저장될 수 있는 값을 갖는 해시가 있어야 합니다).

일관된 해싱 기반 이름 지정 서비스란 무엇인가요?

이 글의 이전 예제에서는 서버에 데이터나 파일을 저장하는 것을 고려했지만, 이 원리는 모든 데이터를 분산된 방식으로 저장하는 것으로 확장할 수 있습니다. 네이밍 서비스는 가장 규모가 크고 분산된 시스템 중 하나이며 일관된 해싱으로 구현하기에 적합합니다. 구체적이고 다른 구현이 있는 DNS는 잠시 제쳐두고, 다음과 같이 보다 일반적인 네이밍 서비스를 일관된 해싱을 사용해 구현할 수 있습니다:

네임 레코드는 여러 서버에 걸쳐 저장됩니다.
서버에는 ID가 할당되고 개념적 링에서 오름차순으로 배열되어야 합니다.
이름을 확인하려면 이름 레코드가 저장된 서버를 찾아야 합니다.
이름의 해시를 취한 다음 결과의 모듈러스를 360으로 취합니다(서버가 360개 미만이라고 가정).
이전 단계에서 찾은 결과와 가장 가깝지만 더 큰 이름의 서버 ID를 찾습니다. 그러한 서버가 존재하지 않으면 가장 낮은 ID를 가진 링의 첫 번째 서버로 감싸줍니다.
이름 레코드는 식별된 서버에서 찾을 수 있습니다.

비슷한 방식으로 작동하는 콘텐츠 전송 네트워크를 고려하여 핫스팟을 피하기 위해 여러 노드에서 요청의 균형을 맞출 수도 있습니다.

일관된 해싱 구현

여러 노드가 분산 해시 테이블을 포함하는 일관된 해싱 링에 배열되어 있는 Java부터 Python까지 다양한 기존 구현이 Github에 있습니다.

Redis, Akamai 또는 Amazon의 dynamo와 같이 일관된 해싱을 사용하는 프로덕션 스토리지 시스템이 존재하며, 이들 중 다수는 데이터 조회의 최종 단계에서 멤캐시, 이진 검색 또는 랜덤 트리와 같은 더 복잡한 데이터 구조를 사용합니다.

일관된 해싱을 구현하는 단계

기본 기술에 대해 설명했으므로 일관된 해싱 솔루션 구현을 시작할 수 있지만 다음 사항을 고려해야 합니다:

솔루션에 몇 대의 서버를 포함할 것인가? 이 숫자가 늘어날 것으로 예상하는가?
서버 ID는 어떻게 할당할 것인가?
데이터 해시를 생성하는 데 어떤 해싱 함수를 사용할 것인가? 데이터가 단일 서버에 집중되지 않고 모든 서버에 고르게 분산될 수 있도록 균일한 출력을 생성하는 함수를 선택하는 것이 좋습니다.
솔루션에서 서버를 추가하거나 제거할 때 어떤 일이 발생하는지 고려하세요. 데이터가 클러스터링되지 않도록 서버 ID를 가능한 한 균등한 간격으로 유지해야 합니다.

일관된 해싱 구현 예시

파일이 5개의 서버 중 하나에 저장되는 예시를 살펴보겠습니다. 1에서 360 사이의 서버 ID를 할당하겠습니다.

서버는 개념적 링으로 배열되고 74, 139, 220, 310, 340의 ID가 할당됩니다.
새 파일을 저장하고 이 파일의 키를 해시하면 결과는 1551입니다.
1551 MOD 360을 수행하면 111이 됩니다.
따라서 데이터 파일은 ID 139로 서버에 저장됩니다.

다른 예를 생각해 보겠습니다:

서버는 개념적 링으로 배열되고 ID 74, 139, 220, 310 및 340이 할당됩니다.
새 파일을 저장해야 하고, 이 파일의 키를 해시하면 결과는 1075입니다.
1075 MOD 360을 수행하면 355가 됩니다.
355를 초과하는 서버 ID는 없으므로 데이터 파일은 ID 74로 서버에 저장됩니다.

일관된 해싱 최적화

일관된 해싱을 사용하는 시스템에서 노드(서버)가 실패하면 설계상 모든 데이터가 링의 다음 서버로 재할당됩니다. 즉, 서버가 실패하면 다음 서버의 부하가 두 배가 되어 과부하가 걸린 서버의 자원이 낭비되고 최악의 경우 연쇄 장애가 발생할 수 있습니다.각 서버가 링의 여러 위치 또는 복제본에 해시를 저장하면 서버 장애 시 보다 고르게 재분배할 수 있습니다. 예를 들어, 한 서버에 4개의 해시가 있어 링의 4곳에 존재하는 경우, 이 서버에 장애가 발생하면 이 서버에 저장된 데이터가 4곳으로 재분배되므로 다른 서버의 부하가 추가로 1/4을 넘지 않아 관리가 더 쉬워집니다.

PubNub로 일관된 해싱 구현

PubNub은 애플리케이션이 대규모의 글로벌 규모로 메시지를 전송할 수 있도록 지원하는 개발자 API 플랫폼입니다. PubNub은 여러 거점을 통해 메시지를 안전하고 안정적이며 신속하게 전송할 수 있습니다.

고객이 기대하는 규모와 안정성을 제공하기 위해 일관된 해싱을 비롯한 여러 가지 기술을 백엔드에 사용합니다.

클라이언트 간 또는 클라이언트와 서버 간에 대규모로데이터를 교환해야 하는 애플리케이션을 만들고 있다면 어떤 해싱 메커니즘을 사용할지보다 훨씬 더 많은 것을 고려해야 할 것입니다. PubNub이 모든 통신 요구 사항을 처리하도록 맡기면 앱 확장에 따른 낮은 수준의 데이터 전송에 대해 걱정하지 않고 비즈니스 로직에 집중할 수 있습니다.

에지 컴퓨팅을 고려하고 있다면 에지 메시지 버스 솔루션을 확인하거나 PubNub가 통신 및 블록체인 웹3 솔루션을 어떻게 지원하는지 살펴보세요.

PubNub은 무료로 사용해 볼 수 있으며, 로그인하거나 무료 계정에 등록하여 앱을 만들거나 둘러보기를 통해 PubNub의 모든 것을 경험해 보세요.

분산 시스템에서의 일관된 해싱