가상 면접 사례로 배우는 대규모 시스템 설계 기초 6장: 키-값 저장소 설계

가상 면접 사례로 배우는 대규모 시스템 설계 기초 6장: 키-값 저장소 설계를 읽고 배운 내용을 정리합니다.

 

key-value 데이터베이스는 비관계형 데이터베이스이다. 여기에 저장되는 값은 고유 식별자(identifier)를 키로 가져야 한다. 키와 값 사이의 연결 관계를 key-value pair 라고 합니다.

 

키는 성능상의 이유로 짧을수록 좋습니다. 

key-value pair에서 값은 문자열, list, object 등 무엇이든 될 수 있습니다.

 

문제 이해 및 설계 범위 확정

해당 글에서는 아래의 조건으로 설계해볼 예정입니다.

• key-value pair의 크기는 10KB 이하이다.
• 큰 데이터를 저장할 수 있어야 한다.
• 높은 가용성을 보장해야 한다.
• 높은 규모 확장성을 보장한다. (오토스케일링이 가능해야 함)
• 데이터 일관성 수준은 조정이 가능해야 한다.
• 짧은 latency를 가져야 한다.

 

단일 서버 key-value store

가장 직관적인 방법은 키-값 쌍 전부를 메모리에 해시 테이블로 저장하는 방법입니다. 이 접근 방법은 빠른 속도를 보장하긴 하지만, 모든 데이터를 메모리 안에 저장하는 것이 불가능할 수 있습니다. 따라서 이에 대한 대안으로 아래의 방향을 제시할 수 있습니다.

• 데이터 압축
• 자주 쓰이는 데이터만 메모리에 두고 나머지는 디스크에 저장

이렇게 개선한다고 해도 단일 서버로는 한계가 있으므로, 분산 키-값 저장소를 만들 필요가 있습니다.

 

분산 key-value store

분산 키-값 저장소는 분산 해시 테이블이라고도 부르며, 키-값 쌍을 여러 서버에 분산시키는 것을 의미합니다. 분산 시스템을 설계할 때는 CAP 정리 (Consistency, Availability, Partition Tolerance theorem)를 이해하고 있어야 합니다.

 

CAP 정리

CAP 정리는 데이터 일관성(Consisntency), 가용성(Availability), 파티션 감내(Partition tolerance)라는 세 가지 요구사항을 동시에 만족하는 분산 시스템을 설계하는 것은 불가능하다는 정리입니다. 

• 데이터 일관성: 분산 시스템에 접속하는 모든 클라이언트는 어떤 노드에 접속했느냐에 관계없이 언제나 같은 데이터를 보게 되어야 합니다.
• 가용성: 분산 시스템에 접속하는 클라이언트는 일부 노드에 장애가 발생하더라도 항상 응답을 받을 수 있어야 합니다.
• 파티션 감내: 파이션은 두 노드 사이에 통신 장애가 발생하였음을 의미합니다. 파티션 감내는 네트워크에 파티션이 생기더라도 시스템은 계속 동작하여야 한다는 것을 의미합니다.

CAP 정리는 세 가지 중 두 가지를 충족하려면 나머지 하나는 반드시 희생되어야 한다는 것을 의미합니다.

키-값 저장소는 앞서 제시한 세 가지 요구사항 가운데 어느 두 가지를 만족하느냐에 따라 다음과 같이 분류할 수 있습니다.

• CP 시스템: 일관성과 파티션 감내를 지원하는 키-값 저장소로, 가용성을 희생합니다.
• AP 시스템: 가용성과 파티션 감내를 지원하는 키-값 저장소로, 데이터 일관성을 희생합니다.
• CA 시스템: 일관성과 가용성을 지원하는 키-값 저장소로, 파티션 감내는 지원하지 않습니다. 그러나 통상 네트워크 장애는 피할 수 없는 일로 여겨지므로, 분산 시스템은 반드시 파티션 문제를 감내할 수 있도록 설계되어야 합니다. 따라서 실세계에 CA 시스템은 존재하지 않습니다.

이상적 상태

세 대의 복제 노드 n1, n2, n3에 데이터를 복제하여 보관하는 상황을 아래의 그림처럼 표현해봅시다.

n1에 기록된 데이터는 자동으로 n2, n3에 복제됩니다. 이 경우 데이터의 일관성과 가용성이 보장됩니다.

 

실세계의 분산 시스템

분산 시스템은 파티션 문제를 피할 수 없습니다. 그리고 파티션 문제가 발생하면 일관성과 가용성 중 하나를 선택해야 합니다. 만약 그림에서 n3에 장애가 나서 n1 및 n2와 통신할 수 없다면 서로의 sync가 끊기게 될겁니다.

 

가용성 대신 일관성을 선택한다면(CP): 세 서버 사이에 생길 수 있는 데이터 불일치 문제를 피하기 위해 n1과 n2에 대해 쓰기 작업을 중단시켜야 하는데, 이는 곧 전체의 중단을 의미하므로 가용성이 깨지게 됩니다. 은행권 시스템의 경우 보통 데이터 일관성을 양보하지 않습니다. 예를 들어, 온라인 뱅킹 시스템이 계좌 최신 정보를 출력하지 못한다면 큰 문제일 겁니다. 네트워크 파티션 때문에 일관성이 깨질 수 있는 상황이라면 뱅킹 시스템같은 경우 상황이 해결될 때까지 오류를 반환해야 합니다.

 

일관성 대신 가용성을 선택한다면(AP): 설사 낡은 데이터를 반환할 위험이 있더라도 계속 읽기 연산을 허용해야 합니다. 따라서 n1, n2는 계속 쓰기 연산을 허용할 것이고, 파티션 문제가 해결된 후 새 데이터를 n3에 전송할 것입니다.

 

분산 키-값 저장소를 만들 때에는 그 요구사항에 맞도록 CAP 정리를 적용해야 합니다. 

 

시스템 컴포넌트

키-값 저장소 구현에 사용될 핵심 컴포넌트들 및 기술들을 살펴봅니다.

• 데이터 파티션
• 데이터 다중화(replication)
• 일관성(consistency)
• 일관성 불일치 해소(inconsistency resolution)
• 장애 처리
• 시스템 아키텍처 다이어그램
• 쓰기 경로 (write path)
• 읽기 경로 (read path)

데이터 파티션

데이터를 파티션 단위로 나눌 때는 다음 두 가지 문제를 중요하게 따져봐야 합니다.

• 데이터를 여러 서버에 고르게 분산할 수 있는가
• 노드에 추가되거나 삭제될 때 데이터의 이동을 최소화할 수 있는가

5장의 안정 해시가 이런 문제를 푸는 데 적합한 기술입니다. 안정 해시를 사용하면 좋은 점은 아래와 같습니다.

• 규모 확장 자동화: 시스템 부하에 따라 오토스케일링이 가능
• 다양성(heterogeneity): 각 서버의 용량에 맞게 가상 노드(virtual node)의 수를 조정할 수 있습니다. 다시 말해, 고성능 서버는 더 많은 가상 노드를 갖도록 설정할 수 있습니다.

데이터 다중화

높은 가용성과 안정성을 확보하기 위해서는 데이터 N개 서버에 비동기적으로 다중화할 필요가 있습니다. 여기서 N은 튜닝 가능한 값입니다. 여기서 N은 튜닝 가능한 값입니다.

N은 해시 링에서 어떤 위치에 존재하는 키가 다음 N개의 서버에 데이터가 복제되어 저장됨을 의미합니다. 

 

가상 노드를 사용한다면 위와 같이 선택한 N개의 노드가 대응될 실제 물리 서버의 개수가 N보다 작아질 수 있습니다. 이 문제를 피하려면 노드를 선택할 때 같은 물리 서버의 중복을 선택하지 않도록 해야 합니다. 

• 애초에 배치할 때 중복되지 않도록 배치할 수는 없을까?

 

데이터 일관성

여러 노드에 다중화된 데이터는 적절히 동기화가 되어야 합니다. 정족수 합의(Quorum Consensus) 프로토콜을 사용하면 읽기/쓰기 연산 모두에 일관성을 보장할 수 있습니다.

• N = 사본 개수
• W = 쓰기 연산에 대한 정족수. 쓰기 연산이 성공한 것으로 간주되려면 적어도 W개의 서버로부터 쓰기 연산이 성공했다는 응답을 받아야 합니다.
• R = 읽기 연산에 대한 정족수. 읽기 연산이 성공한 것으로 간주되려면 적어도 R개의 서버로부터 응답을 받아야 합니다.

 

Coordinator는 클라이언트와 서버 사이의 프록시 역할을 합니다. W = 1이라면, 읽기 연산이 성공하려면 하나의 서버가 요청에 응답해야 함을 의미합니다. 만약 서버 중 하나가 ACK을 보낸다면 다른 서버로부터 ACK을 받을 필요 없이 연산을 수행합니다. W, R, N을 조정하는 것은 응답 지연과 데이터 일관성 사이의 타협점을 찾는 과정입니다. 

 

W = 1 또는 R = 1 인 구성의 경우 coordinator는 한 대의 서버로부터 응답만 받으면 되니 응답 속도가 빠릅니다. 1보다 큰 경우엔 시스템이 보여주는 일관성이 향상되지만 응답 속도는 느려집니다.

 

W + R > N 인 경우, 강한 일관성(strong consistency)가 보장됩니다. 일관성을 보증할 최신 데이터를 가진 노드가 최소 하나는 겹치기 때문입니다.

• R = 1, W = N: 빠른 읽기 연산에 최적화된 시스템
• W = 1, R = N: 빠른 쓰기 연산에 최적화된 시스템
• W + R > N: 강한 일관성이 보장됨(보통 N = 3, W = R = 2) 
• W + R <= N: 강한 일관성이 보장되지 않음

 

일관성 모델

일관성 모델은 키-값 저장소를 설계할 때 고려해야 할 또 하나의 중요한 요소입니다. 일관성 모델은 데이터 일관성의 수준을 결정하며 종류가 다양합니다.

• 강한 일관성(strong consistency): 모든 읽기 연산은 가장 최근에 갱신된 결과를 반환합니다. 다시 말해서 클라이언트는 절대 outdated data를 보지 못합니다.
• 약한 일관성(weak consistency): 읽기 연산은 가장 최근에 갱신된 결과를 반환하지 못할 수 있습니다.
• 최종 일관성(eventual consistency): 약한 일관성의 한 형태로, 갱신 결과가 결국에는 모든 사본에 반영(동기화)되는 모델입니다.

강한 일관성을 달성하는 일반적인 방법은 모든 사본에 현재 쓰기 연산의 결과가 반영될 때까지 해당 데이터에 대한 읽기/쓰기를 금지하는 것입니다. 이 방법은 고가용성 시스템에는 적합하지 않습니다. 다이나모/카산드라같은 경우 최종 일관성을 보장하도록 설계되어 있습니다. 최종 일관성의 경우 연산이 병렬적으로 발생하면 시스템에 저장된 값의 일관성이 깨질 수 있는데, 이는 클라이언트 단에서 해결해야 합니다.

 

Inconsistency 해소 방법: data versioning

데이터를 다중화하면 가용성은 높아지지만 사본 간 일관성이 깨질 가능성이 커집니다. versioning과 vector clock은 그 문제를 해결합니다. versioning은 데이터를 변경할 때마다 해당 데이터의 새로운 버전을 만드는 것을 의미합니다. 따라서 각 버전의 데이터는 변경 불가능합니다.

 

백터 시계는 [서버, 버전]의 순서쌍을 데이터에 붙인 것을 의미합니다. 어떤 버전이 먼저 생성된 것인지 판별할 때 사용할 수 있습니다. 벡터 시계를 D([S1, v1], [S2, v2], ..., [Sn, vn])와 같이 표현한다고 가정합시다. 여기서 D는 데이터이고, vi는 버전 카운터, Si는 서버 번호입니다. 만일 데이터 D를 서버 Si에 기록하면, 시스템은 아래 작업 가운데 하나를 수행합니다.

• [Si, vi]가 있으면 vi를 증가시킵니다.
• 그렇지 않으면 새 항목 [Si, 1]을 만듭니다.

예시:

1. 서버 x가 D1을 시스템에 기록합니다: D1[(Sx, 1)]
2. 서버 x가 D1을 읽고 D2로 업데이트합니다: D2[(Sx, 2)]
3. 서버 y가 D2를 읽고 D3으로 업데이트합니다: D3[(Sx, 2), (Sy, 1)]
4. 서버 z가 D2를 읽고 D4로 업데이트합니다: D4[(Sx, 2), (Sz, 1)]
5. 어떤 클라이언트가 D3과 D4를 읽으면 데이터 간 충돌이 있다는 것을 알게 됩니다. D2를 Sy와 Sz가 각기 다른 값으로 바꾸었기 때문입니다. 이 충돌은 클라이언트가 해소한 후 서버에 기록합니다. 이 연산을 처리한 서버가 x였다면: D5[(Sx, 3), (Sy, 1), (Sz, 1)]가 됩니다. 

벡터 시계를 사용하면 충돌을 감지하는 것이 쉽습니다. 다만 하기 두 가지 문제점이 존재합니다.

• 충돌을 클라이언트가 해소해야 하므로 이에 대한 부담이 존재합니다.
• 서버:버전 순서쌍의 개수가 급격히 증가합니다. 따라서 어떤 threshold를 설정하고, 이 값 이상으로 길이가 길어지면 오래된 순서쌍을 벡터 시계에서 제거하도록 해야 합니다. 하지만 이렇게 구현 시 버전 간 선후 관계가 정확하게 결정될 수 없기 때문에 충돌 해소 과정의 효율성이 낮아지게 됩니다 (다만 다이나모 데이터베이스에 관계된 문헌에서 아마존은 실제 서비스에서 이런 문제가 벌어지는 것을 발견한 적이 없다고 합니다).

장애 처리

장애 감지를 하는 가장 쉬운 방법은 multicasting 채널을 구축하는 것입니다. 

가십 프로토콜같은 분산형 장애 감지 솔루션을 채택하는 편이 보다 효율적입니다. 가십 프로토콜의 동작 원리는 다음과 같습니다:

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

일시적 장애 처리

가십 프로토콜로 장애를 감지한 시스템은 가용성을 보장하기 위해 필요한 조치를 해야 합니다. 엄격한 정족수(strict quorum) 접근법을 쓴다면 읽기/쓰기를 금지해야 합니다.

느슨한 정족수(sloppy quorum) 접근법은 이 조건을 완화하여 가용성을 높입니다. 정족수 요구사항을 강제하는 대신, 쓰기 연산을 수행할 W개 건강한 서버와 읽기 연산을 수행할 R개의 건강한 서버를 해시 링에서 고릅니다. 이 때 장애가 생긴 서버로 가는 요청은 다른 서버가 대신 처리합니다. 그동안 발생한 변경사항은 해당 서버가 복구되었을 때 일괄 반영하여 데이터 일관성을 보존합니다. 이를 위해 임시로 쓰기 연산을 처리한 서버에는 그에 관한 hint를 남긴다고 합니다. 이런 장애 처리 방안을 hinted handoff 기법이라고 합니다. (장애 복구 이후 장애가 난 서버의 데이터는 hint를 남겼던 서버가 인계합니다)

 

영구 장애 처리

Hinted handoff  기법은 일시적 장애를 처리하기 위한 것입니다. 영구적인 장애 처리로 anti-entropy 프로토콜을 사용하여 사본들을 동기화할 수 있습니다.

반-엔트로피 프로토콜은 사본들을 비교하여 최신 버전으로 갱신하는 과정을 포함합니다. 사본 간의 일관성이 망가진 상태를 탐지하고 전송 데이터의 양을 줄이기 위해서는 merkle tree를 사용합니다.

 

해시 트리라고도 불리는 머클 트리는 각 노드에 그 자식 노드들에 보관된 값의 해시, 또는 자식 노드들의 레이블로부터 계산된 해시 값을 레이블로 붙여두는 트리입니다. 해시 트리를 사용하면 대규모 자료 구조의 내용을 효과적이면서도 보안상 안전한 방법으로 검증할 수 있습니다. 

 

머클 트리를 사용하면 동기화해야 하는 데이터의 양은 실제로 존재하는 차이의 크기에 비례할 뿐, 서버에 보관된 데이터의 총량과는 무관해집니다.

 

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

쓰기 경로

쓰기 요청이 특정 노드(서버)에 도달하면 아래의 그림과 같은 플로우가 일어납니다. 아래 예시는 카산드라의 사례를 보여줍니다.

1. 쓰기 요청이 커밋 로그 파일에 기록됩니다.
2. 데이터가 메모리 캐시에 기록됩니다.
3. 메모리 캐시가 가득차거나 사전에 정의된 어떤 임계치에 도달하면 데이터는 디스크에 있는 SSTable에 기록됩니다. SSTable은 Sorted-String Table의 약어로, <키, 값>의 순서쌍을 정렬된 리스트 형태로 관리하는 테이블입니다. 

읽기 경로

읽기 요청을 받았을 때 메모리에 캐시가 있으면 아래와 같이 반환합니다.

데이터가 메모리에 없는 경우에는 디스크에서 가져와야 합니다. 어느 SSTable에 찾는 키가 있는지 알아낼 효율적 방법이 필요할 것입니다. 이럴 때 bloom filter가 흔히 사용됩니다.

1. 데이터가 메모리에 있는지 검사합니다. 없으면 2로 갑니다.
2. 데이터가 메모리에 없으므로 블룸 필터를 검사합니다.
3. 블룸 필터를 통해 어떤 SSTable에 키가 보관되어 있는지 알아냅니다.
4. SSTable에서 데이터를 가져옵니다.
5. 해당 데이터를 클라이언트에게 반환합니다.