분산 키-밸류 저장소 설계

개요

6장의 내용은 put, get 연산을 지원하는 키-값 저장소 설계에 대한 내용입니다.
일반적으로 사용하는 AWS의 DynamoDB, Apache Cassandra와 같은 NoSQL DB를 설계한다고 보면 쉽게 이해가 될 것 입니다.
해당 장에서 중요한 점들은 다음과 같습니다.

• CAP 정리에 의한 분산 시스템 설계
• 단일 서버, 분산 서버 설계 간 장/단점
• 분산 서버 설계 시 발생하는 여러 문제들과 해당 문제를 해결하는 방법
  

단일? 분산?

먼저 put, get 연산을 통해 저장소에 키-값 쌍을 저장하고 해당 키를 기준으로 값을 불러올 수 있는 키-값 저장소를 설계한다고 생각해 봅시다.

단일 서버로 구축하게 된다면, 서버 간 데이터 일관성에 대해 고민할 필요 없이 쉽게 저장소를 구축할 수 있습니다. 다만, 결국 단일 서버의 용량은 정해져 있기 때문에 대용량 데이터 처리를 위해서는 필수적으로 여러개의 를 이용한 분산 저장소를 구축해야 합니다.

분산 서버로 구축하게 되면, 여러개의 서버에 데이터를 분산하는 방식으로 운용되므로 여러 문제를 처리해야 합니다. 분산 서버 설계 시 필수적으로 알고 있어야 하는 CAP 정리에 대해 알아보겠습니다.

CAP 정리
CAP 정리는 데이터 일관성(consistency), 가용성(availability), 파티션 감내(partition tolerance)라는 세 가지 요구사항을 모두 만족하는 분산 시스템 설계는 불가능 하다는 정리입니다.

먼저 여기에서 파티션은 두 서버 간 통신에 장애가 생기는 경우를 말합니다. 서비스 운용 시 네트워크 문제는 무조건 발생하므로, 파티션 감내는 모든 서버가 지원해야 합니다.

일반적인 상황에서는 모든 서버가 제대로 동작하여 일관성과 가용성이 지켜지겠지만, 아래 그림과 같이 한 서버에 문제가 생길 경우 우리는 일관성과 가용성 중 하나를 택해야 합니다.

일관성을 지키기위해 장애가 발생한 서버를 제외한 모든 서버가 읽기/쓰기 작업을 중단할 경우, 가용성이 깨져 한 서버에 문제가 발생하는 순간 해당 저장소를 사용할 수 없게 됩니다.

가용성을 지키기위해 정상 서버들이 읽기/쓰기 작업을 지원할 경우, 장애 서버에서 기록한 정보가 최신 정보라면 모든 서버의 데이터가 일치하지 않으므로 일관성이 깨지게 됩니다.

따라서 우리는 목적에 맞게 일관성/가용성 중 하나를 선택한 후, 파티션 감내를 동시에 지원하는 방식으로 설계해야 합니다.

분산 시스템 설계

데이터 파티션

분산 시스템을 통한 저장소 설계의 경우 모든 데이터를 균등하게 나누어 저장해야하고, 새로운 서버가 추가되거나 삭제될 때에도 데이터의 이동을 최소화해야 합니다.

이를 해결하기 위해서는 5장에서 배운 안정 해시 방식을 이용해 데이터를 저장해야 합니다.

5장_안정해시 정리

이렇듯 안정 해시 방식을 이용해 해시링에 서버를 배치한 후, 데이터를 저장하는 방식을 적용함으로써 균등하게 데이터를 분산시켜 저장할 수 있게 됩니다.

데이터 다중화

하지만 이렇게 분산만 할 경우, 한 서버에 문제가 생길 경우 해당 서버가 가지고 있는 데이터를 조회할 수 없게 됩니다. 이를 해결하기 위해 해시링 방식과 더불어 데이터 다중화가 필요합니다.

키를 해시링에 배치한 후 해당 지점으로부터 시계 방향으로 링을 순회하며 만나는 첫 N개의 서버에 데이터 사본을 보관하는 방식으로 데이터를 다중화 함으로써 다중화가 가능합니다.

다만 가상 노드를 사용하는 해시링의 경우 실제로 N개의 서버를 선택했지만 물리 서버는 N개보다 적을 수 있기 때문에, 동일한 물리 서버를 선택하지 않도록 구현해야 합니다. (ex : 링 상에서는 여러 서버가 선택되었지만 실제로 데이터가 한 물리 서버에만 저장될 수 있음)

데이터 일관성
마지막으로 데이터 일관성입니다. 여러 서버에 데이터를 다중화시켜 저장할 경우, 각 데이터는 적절히 동기화 되어야 합니다. 정족수 합의(Quorum Consensus) 프로토콜을 사용해 읽기/쓰기 연산에 일관성을 보장할 수 있습니다.

다음과 같이 N개의 서버에 같은 PUT 작업을 수행해 다중화시키면서, 일정 개수의 ACK를 받았을 때 연산이 성공되었다고 간주함으로써 정족수 합의 프로토콜을 사용할 수 있습니다.

N = 사본 개수
W = 쓰기 연산에 대한 정족수
R = 읽기 연산에 대한 정족수

W+R > N인 경우에는, 쓰기/읽기 두 연산 모두에 대한 검증이 이루어진 서버가 존재한다는 것이므로 강한 일관성(strong consistency)이 보장됩니다.

이와 더불어 일관성을 보장하는 다른 방법들도 있는데요, 데이터 버저닝과 벡터 시계 방식을 이용해 해결할 수 있습니다.

각 서버에 데이터를 저장할 때, 데이터와 함께 버전을 저장해 일관성을 유지합니다.
벡터 시계는 [서버, 버전]의 순서쌍을 데이터에 매단 것입니다. S1 서버에 데이터를 저장할 경우 [S1, 1]로 저장하고, 이후 수정이 일어날 때 마다 버전을 높여 해당 데이터가 오래 된 데이터인지 다른 서버와의 교차 검증을 통해 검증합니다.

[Si, vi]가 존재 할 경우 vi을 증가시키고, 그렇지 않으면 새로운 벡터 시계인 [Si, 1]을 만듭니다.
이미 저장된 데이터에 대한 벡터 시계가 [S1, 2]가 존재할 때를 가정해 봅시다.
이때, S2와 S3서버가 동시에 해당 데이터를 수정한다면 벡터시계는 어떻게 되어야 할까요?

S2서버는 [S1, 2][S2, 1]와 같이 벡터 시계를 만들고, S3 서버는 [S1, 2][S3, 1]과 같이 벡터 시계를 만듭니다. 다른 클라이언트가 두 데이터를 읽게 된다면, 해당 데이터에 충돌이 발생한다는 것을 깨닫고 벡터 시계를 [S1, 2][S2, 1][S3, 1]과 같이 수정해 주어야 합니다. 이 수정에 대한 부분은 클라이언트 부분에서 처리해야 하므로, 각 서비스 마다 다르게 동작합니다.

구축 후 관리

장애 감지
분산 시스템에서는 한 서버가 A서버와 통신이 안 된다고해서 A서버를 장애 서버로 지정하지 않습니다. 적어도 두 개 이상의 서버가 A서버와 통신이 문제가 발생했을 경우 장애 처리를 하게 됩니다. 각 서버는 장애 감지를 위해 가십 프로토콜과 같은 분산형 장애 감지 솔루션을 채태가는 것이 효율적입니다.

가십 프로토콜
각 서버는 멤버십 목록을 유지합니다. 각 멤버의 ID와 박동 카운터 쌍이 담긴 목록입니다. 주기적으로 각 서버는 자신의 박동 카운터를 증가시키고, 무작위로 선정된 노드들에게 자기 박동 카운터 목록을 보냅니다. 이후 각 노드들은 박동 카운터 목록을 받고, 멤버십 목록을 최신 값으로 갱신합니다. 어떤 멤버의 박동 카운터 값이 지정된 시간 동안 갱신되지 않으면, 해당 멤버는 장애 상태인 것으로 간주하는 방법입니다.

일시적 장애 처리
그렇다면, 이렇게 장애가 발생한 서버가 존재할 경우 어떤 조치를 취해야 할까요? 이전에 언급한 정족수를 이용합니다. 엄격한 정족수 접근법을 쓴다면, 한 서버에서 장애가 발생한 경우 모든 서버에서 읽기와 쓰기 연산을 금지해야 합니다.

이와 다르게 느슨한 정족수 방법은, 가용성을 포기하지 않는 방법입니다. 정족수 요구사항을 강제하는 대신, 쓰기/읽기 연산을 수행할 W,R개의 건강한 서버를 해시 링에서 고릅니다. 이때, 장애가 발생한 서버는 무시합니다.

장애 상태인 서버로 가는 요청은 잠시 다른 서버가 맡아 처리하고, 그동안 발생한 변경사항은 해당 서버가 복구되었을 때 일괄 반영해 데이터 일관성을 보존합니다. 이를 위해 임시로 쓰기 연산을 처리한 서버에는, 해당 장애 후 처리한 데이터들에 단서(hint)를 남겨놓아 이후 복구할 때 사용합니다. 이러한 방안을 단서 후 임시 위탁(hinted handoff) 기법이라 부릅니다.

영구 장애 처리
일시적이지 않은 영구적 노드의 장애의 경우 반-엔트로피 프로토콜을 사용해 데이터 일관성이 깨진 상태를 감지하고 전송 데이터의 양을 줄입니다. 이때에는 머클트리를 사용해 사본들을 동기화합니다.

머클트리를 이용한 데이터 무결성 검증

1. 각 서버에 존재하는 데이터를 일정한 크기의 버킷으로 나누어 저장한 후, 각 데이터들에 균등 분포 해시(uniform hash) 함수를 적용해 해시 값을 저장합니다.
2. 데이터를 포함한 버킷들을 기준으로 해시값을 다시 계산한 후, 해당 해시값을 값으로 갖는 노드를 만든다.
3. 자식 노드의 레이블로부터 새로운 해시 값을 계산하여, 이진 트리를 상향식으로 구해나간다.

-> 이후 일관성이 깨진 데이터를 확인하기 위해서는, 두 서버 간 머클트리를 탐색하며 해시값이 다른 노드를 찾아내면 됩니다.

시스템 아키텍처 다이어그램

위에서 설명한 것들을 구현한 형태의 시스템에 대한 다이어그램과, 이에 대한 설명입니다.

• 클라이언트는 API( get(key), put(key, value) ) 와 통신한다.
• 중재자는 클라이언트에게 키-값 저장소에 대해 proxy 역할을 한다.
• 노드는 안정 해시의 해시 링 위에 분포된다.
• 노드를 자동으로 추가 삭제할 수 있도록 시스템은 분산된다.
• 데이터는 여러 노드에 다중화 된다.
• SPOF(Single Point of Failure)는 존재하지 않는다.(모든 노드가 같은 책임을 지므로)

읽기/쓰기 경로

이렇게 구성된 서버에 읽기/쓰기 요청을 특정 노드에 전달하면 무슨일이 벌어지는지를, 상용 NoSQL DBMS인 카산드라를 기준으로 설명한다.

쓰기경로

1. 쓰기 요청을 커밋 로그 파일에 기록한다.
2. 데이터를 메모리 캐시에 기록한다.
3. 메모리 캐시가 가득찬다면?
4. SSTable(Sorted-String Table)로 구현된 디스크에 저장한다.

읽기 경로

1. 가장 먼저 데이터가 메모리 캐시에 있는지 살핀다.
2. 데이터가 메모리에 없다면? 다른 노드가 가지고 있다는 의미다.
3. 블룸필터(Bloom Filter)를 검사한다.
4. 블룸필터는 어떤 SSTable에 키가 보관됐는지 검사한다.
5. SSTable에서 데이터를 가져와 클라이언트에게 반환한다.

요약

지금까지 알아 본 각 문제와, 이를 해결하는 기술에 대한 표를 보면서 마무리하겠습니다.

목표/문제	기술
대규모 데이터 저장	안정 해시를 사용하여 서버에 부하 분산
읽기 연산에 대한 가용성 보장	여러 데이터센터에 다중화
쓰기 연산에 대한 가용성 보장	버저닝 및 벡터 시계를 사용하여 충돌 해소
데이터 파티션	안정 해시
점진적 규모 확장성	안정 해시
다양성(heterogeneity)	안정 해시
조절 가능한 데이터 일관성	정족수 합의(quorum consensus)
일시적 장애 처리	느슨한 정족수 프로토콜 및 단서 후 임시 위탁
영구적 장애 처리	머클 트리
데이터 센터 장애 대응	여러 데이터센터에 다중화