6. 키-값 저장소 설계

키-값 저장소(key-value store)는 키-값 데이터베이스라고 불리는 비 관계형 데이터베이스입니다.
키-값 쌍에서의 키는 유일해야하며 해당 키에 달린 값은 키를 통해서만 접근할 수 있습니다.

문제 이해 및 설계 범위 확정#

완벽한 설계는 없습니다.
다음 특성을 갖는 설계해 볼 수 있습니다.
- 키-값 쌍의 크기는 10KB 이하입니다.
- 큰 데이터를 저장할 수 있어야 합니다.
- 높은 가용성을 제공해야 합니다. 따라서 시스템은 설사 장애가 있더라도 빨리 응답해야 합니다.
- 높은 규모 확장성을 제공해야 합니다. 따라서 트래픽 양에 따라 자동적으로 서버 증설/삭제가 이루어져야 합니다.
- 데이터 일관성 수준은 조정이 가능해야 합니다.
- 응답 지연시간(latency)이 짧아야 합니다.

단일 서버 키-값 저장소#

한 대 서버만 사용하는 키-값 저장소를 설계하는 것은 쉽습니다.
이 방법은 빠른 속도를 보장하지만, 모든 데이터를 메모리 안에 두는 것이 불가능할 수도 있다는 약접이 있습니다. 이를 해결할 해결책은 다음과 같습니다.
- 데이터 압축(compression)
- 자주 쓰이는 데이터만 메모리에 두고 나머지는 디스크에 저장
그러나 한 대 서버로 부족한 때가 곧 찾아옵니다.

분산 키-값 저장소#

분산 키-값 저장소는 분산 해시 테이블이라고도 불립니다.
분산 시스템을 설계할 때는 CAP 정리(Consistency, Availability, Partition Tolerance theorem)를 알고 있어야 합니다.

CAP 정리#

데이터 일관성(consistency), 가용성(availability), 파티션 감내(partition tolerance)라는 세 가지 요구사항을 동시에 만족하는 분산 시스템을 설계하는 것은 불가능하다는 정리입니다.
- 데이터 일관성: 분산 시스템에 접속하는 모든 클라이언트는 어떤 노드에 접속했느냐에 관계없이 언제나 같은 데이터를 봐야 합니다.
- 가용성: 분산 시스템에 접속하는 클라이언트는 일부 노드에 장애가 발생하더라도 항상 응답을 받을 수 있어야 합니다.
- 파티션 감내: 파티션은 두 노드 사이에 통신 장애가 발생하였음을 의미합니다. 파티션 감내는 네트워크에 파티션이 생기더라도 시스템은 계속 동작해야 한다를 의미합니다.
키-값 저장소는 앞서 제시한 세 가지 요구사항 가운데 어느 두 가지를 만족하냐에 따라 아래와 같이 분류됩니다.
- CP 시스템: 일관성과 파티션 감내를 지원하는 키-값 저장소. 가용성을 희생합니다.
- AP 시스템: 가용성과 파티션 감내를 지원하는 키-값 저장소. 데이터 일관성을 희생합니다.
- CA 시스템: 일관성과 가용성을 지원하는 키-값 저장소. 파티션 감내는 지원하지 않습니다. 그러나 통상 네트워크 장애는 없으므로 실세계에서 CA 시스템은 존재하지 않습니다.

Pacelc 이론으로 넘어갔을 텐데.

시스템 컴포넌트#

데이터 파티션#

데이터를 파티션 단위로 나눌 때는 다음 두가지 문제를 주요하게 고려해야합니다.
- 데이터를 여러 서버에 고르게 분산할 수 있는가
- 노드가 추가되거나 삭제될 때 데이터의 이동을 최소화할 수 있는가?
안정 해시를 사용하여 데이터를 파티션하면 좋은 점은 다음과 같습니다.
- 규모 확장 자동화(automatic scaling): 시스템 부하에 따라 서버가 자동으로 추가되거나 삭제되도록 만들 수 있습니다.
- 다양성(hetoerogeneity): 각 서버의 용량에 맞게 가상 노드의 수를 조정할 수 있습니다. 즉, 고성능 서버는 더 많은 가상 노드를 갖도록 설정할 수 있습니다.

데이터 다중화(replication)#

높은 가용성과 안전성을 확보하기 위해서는 데이터를 N개 서버에 비동기적으로 다중화(Replication)할 필요가 있습니다.
같은 데이터 센터에 속한 노드는 정전, 네트워크 이슈, 자연재해 등의 문제를 동시에 겪을 가능성이 있습니다. 따라서, 안정성을 담보하기 위해 데이터의 사본은 다른 센터의 서버에 보관하고, 센터들은 고속 네트워크로 연결합니다.

일관성(consistency)#

정족수 합의 프로토콜을 사용해서 읽기/쓰기 연산 모두에 일관성을 보장할 수 있습니다.
- N : 사본 개수
- W : 쓰기 연산에 대한 정족수
- R : 읽기 연산에 대한 정족수
다음의 구성을 예시로 들 수 있습니다.
- R = 1, W = N: 빠른 읽기 연산에 최적화된 시스템
- W = 1, R = N: 빠른 쓰기 연산에 최적화된 시스템
- W + R > N: 강한 일관성이 보장됨 (보통 N = 3, W = R = 2)
- W + R <= N: 강한 일관성이 보장되지 않음

일관성 모델#

강한 일관성(strong consistency): 모든 읽기 연산은 가장 최근에 갱신된 결과를 반환합니다.
약한 일관성(weak consistency): 읽기 연산은 가장 최근에 갱신된 결과를 반환하지 못할 수 있습니다.
최종 일관성(eventual consistency): 약한 일관성의 한 형태로, 갱신 결과가 결국에는 모든 사본에 반영(즉, 동기화)되는 모델입니다.

비 일관성 해소 기법: 데이터 버저닝#

데이터를 다중호하면 가용성은 높아지지만 사본 간 일관성이 깨질 가능성은 높아집니다.
버저닝은 데이터를 변경할 때마다 해당 데이터의 새로운 버전을 만드는 것을 의미합니다.
백터 시계를 통해 이전 법전인지 여부를 판단할 수 잇습니다.
그러나 벡터 시계를 사용해 충돌 감지는 아래의 문제가 있습니다.
- 첫째, 충돌 감지 및 해소 로직이 클라이언트에 들어가므로, 클라이언트 구현이 복잡해집니다.
- 둘째, [서버, 버전]의 순서쌍 개수가 굉장히 빨리 늘어납니다. -> 해결책은 임계치 이상으로 길어지만 오래된 순서쌍을 벡터 시계에서 제거합니다.

장애 처리#

장애를 처리하는 부분은 중요한 문제입니다.
- 장앤 감지(failure detection) 기법과 장애 해소(failure resolution) 전략이 있습니다.

장애 감지#

멀티 캐스팅 채털을 구축하는 것은 쉬운 방법이나, 서버가 많을 때는 비효율적입니다.
가십 프로토콜(gossip protocol) 같은 분산형 장애 감지(decentralized failure detection) 솔루션을 채택하는 편이 효율적입니다.
- 주기적으로 박동 카운터 목록을 보내는데, 어떤 멤버의 박동 카운터 값이 지정된 시간동안 갱신되지 않으면 장애로 봅니다.

일시적 장애 처리#

엄격한 정족수 접근법이라면 읽기와 연산을 금지해야합니다.
느슨한 정족수 접근법은 건강한 N개에서 건강한 W, 건강한 R개의 서버를 고릅니다.

영구 장애 처리#

머틀(Merkle) 트리 등을 사용해서 일관성이 망가진 상태를 탐지하고 전송 데이터의 양을 줄입니다.

데이터 센터 장애 처리#

데이터를 여러 데이터 센터에 다중화하는 것이 중요합니다.

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

아래 아키텍처를 설계한다면 주된 기능은 다음과 같습니다.
- 클라이언트는 키-값 저장소가 제공하는 두 가지 단순한 API, 즉 get(key) 및 put(key, value)와 통신합니다.
- 중재자/(coordinator)는 클라이언트에게 키-값 저장소에 대한 프락시(proxy) 역할을 하는 노드입니다.
- 노드는 안정 해시(consistent hash)의 해시 링(hash ring) 위에 분포합니다.
- 노드를 자동으로 추가 또는 삭제할 수 있도록, 시스템은 완전히 분산됩니다.(decentralized)
- 데이터는 여러 노드에 다중화됩니다.
- 모든 노드가 같은 책임을 지므로, SPOF(Single Point of Failure)는 존재하지 않습니다.

시스템 아키텍처 요구사항

쓰기 경로(write path)#

쓰기 경로 예시(카산드라)

쓰기 경로

읽기 경로(read path)#

읽기 경로 예시
- 캐시가 있는 경우, 메모리 캐시에서 바로 결과 반환
- 캐시에 없는 경우 아래의 그림

읽기 경로

요약#

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