가상 면접 사례로 배우는... : 키-값 저장소 설계
- Spring
- 2023. 8. 20.
들어가기 전
이 글은 가상 면접 사례로 배우는 대규모 시스템 설계 기초를 공부하며 작성한 글입니다.
6. 키-값 저장소 설계
Key-Value Store는 비관계형 데이터베이스다. 많이 알려진 녀석들은 아마존의 Dynamo, Memcached, Redis 같은 것들이 존재한다. 데이터는 다음과 같은 형태로 저장된다.
| Key | Value |
| 145 | john |
| 147 | bob |
문제 이해 및 설계 범위 확정
모든 것을 만족할 수는 없고, 요구 사항을 고려해서 트레이드 오프를 결정해야한다. 요구사항은 다음과 같다.
- 높은 가용성을 제공해야 함. 시스템은 장애가 있더라도 빨리 응답해야 함.
- 높은 규모 확장성을 제공해야 함. 트래픽 양에 따라 자동적으로 서버 증설 / 삭제가 가능해야 함.
- 데이터 일관성 수준은 조정 가능해야 함.
- 응답 지연시간(latency)가 짧아야 함.
단일 서버 키-값 저장소
한 대의 서버만 사용하는 키-값 저장소는 해시 테이블을 이용하면 손쉽게 구성할 수 있다. 하지만 치명적인 단점이 있는데, 많은 데이터를 한 대의 서버에 저장할 수 없다는 것이다.
- 메모리에 많은 데이터를 올릴 수 없음.
- 디스크에 저장한다고 하더라도, 디스크 용량이 곧 가득찰 것이고 한계가 있음.
따라서 분산 키-값 저장소(Distributed Key-Value Store)가 필요하다.
분산 키-값 저장소
Key-Value 쌍을 여러 서버에 분산 시킨 것을 분산 키-값 저장소라고 한다. 분산 시스템을 설계할 때는 CAP 정리를 이해하고 있어야 한다.
CAP 정리
CAP 정리는 아래 세 가지를 모두 만족하는 분산 시스템을 설계하는 것은 불가능하다는 정리다. 세 가지 중 두 가지만 만족할 수 있으며, 나머지 한 가지를 희생해야 한다.
- 데이터 일관성 (Consistency) : 분산 시스템에 접속하는 모든 클라이언트는 어떤 노드에서 데이터를 읽어도 같은 데이터를 봐야함.
- 가용성 (Availability) : 일부 노드에 장애가 발생하더라도, 분산 시스템에 접속하는 클라이언트는 항상 응답을 받을 수 있어야 함.
- 파티션 감내 (Partition Tolerance) : 분산 시스템의 노드끼리 네트워크 이슈로 통신할 수 없는 상황을 파티션이라고 한다. 분산 네트워크에 파티션이 발생하더라도 시스템은 계속 동작해야 함.
세 가지 중 두 가지만 만족할 수 있는 트레이드 오프 관계이며, 이를 고려한다면 총 3가지 종류의 시스템이 설계가 가능하다.
- CP : 가용성을 희생함.
- AP : 데이터 일관성을 희생함.
- CA : 파티션 감내를 희생함.
그러나 분산 시스템 내에서 일시적인 네트워크 장애(파티션)는 반드시 발생할 수 있는 것이기 때문에 CA 시스템은 실세계에서 고려되지 않는다. CP, AP 시스템에 대한 간단한 예시를 아래에서 조금 더 살펴보려고 한다.
실생활의 분산 시스템 살펴보기
분산 시스템에서 데이터는 보통 여러 노드에 복제된다. 예를 들어 분산 시스템에서 노드1에 저장된 데이터는 노드2, 노드3에 저장된다.
이상적 상태
이상적 환경이라면 네트워크의 파티션을 절대로 발생하지 않는다. 노드1에 기록된 데이터는 자동적으로 노드2, 노드3에 복제된다.
실세계의 분산 시스템
분산 시스템은 파티션 문제 (네트워크 이슈) 를 피할 수 없다. 파티션 문제가 발생하면 일관성 / 가용성 중에 하나를 희생해야한다. 네트워크 파티션이 발생한 아래 그림에서는 다음 두 가지 문제가 발생할 수 있다.
- 노드1, 노드2에 기록된 데이터가 노드 3에 전달되지 않음. → 노드 3에 데이터 요청 시, 오래된 데이터 봄.
- 노드3에 기록된 데이터가 노드,1 노드2에 전달되지 않음. → 노드1,2에 데이터 요청 시, 오래된 데이터 봄.
여기서 데이터 일관성을 선택한다면, 네트워크 파티션이 해결될 때까지 데이터 쓰기 / 읽기를 금지해야한다. 이렇게 하면 데이터 일관성을 지킬 수 있지만, 가용성은 잃어버린 결과를 초래한다. 가용성을 선택한다면, 네트워크 파티션이 해결될 때까지 임시 노드에서 데이터를 쓰고 읽을 수 있으나, 데이터 일관성을 지킬 수는 없다.
시스템 컴포넌트
키-값 저장소에 구현에 사용될 핵심 컴포넌트들 및 기술들은 다음과 같다. 아래 파트에서 관련된 내용을 하나씩 살펴볼 것이다.
- 데이터 파티션
- 데이터 다중화
- 일관성
- 일관성 불일치 해소
- 장애 처리
- 시스템 아키텍쳐 다이어그램
- 쓰기 경로
- 읽기 경로
데이터 파티션
대규모 트래픽에서 발생하는 전체 트래픽을 하나의 서버에 넣을 수 없다. 따라서 데이터를 작은 파티션으로 분할한 다음 여러 서버에 저장해야한다.
데이터를 파티션으로 나눌 때 고려해야 하는 부분은 다음 두 가지고, 이 부분을 만족할 수 있는 기술은 '안정 해시'다.
- 데이터를 여러 서버에 고르게 분산할 수 있는가.
- 노드 추가 / 삭제될 때 데이터의 이동을 최소화 할 수 있는가
안정 해시를 사용했을 때 좋은 점은 다음과 같다.
- 노드 추가 / 삭제를 하더라도 데이터 이동이 최소화 됨.
- 성능이 좋은 서버에는 가상 노드 개수를 증가시켜 더 많은 데이터를 저장할 수도 있음.
데이터 다중화
안정 해시를 이용해 데이터 파티셔닝을 한 후에 데이터를 저장한다. 여기까지는 하나의 데이터는 하나의 서버에만 저장된다. 데이터의 복제본이 여러 서버에 저장되어야 고가용성을 얻을 수 있다. 안정해시를 이용해 데이터를 다중화 하는 방법은 다음과 같다.
데이터의 해시값을 구한 후, 시계 방향으로 순회하며 처음으로 만나는 N개의 서버에 데이터를 복제한다.
주의해야 하는 부분은 N개의 가상노드가 아닌, N개의 서버에 복제해야한다는 것이다. 특정 서버의 가상 노드만 독보적으로 많다면, N개의 서버에 특정 서버의 가상 노드가 포함될 가능성이 높다. 이런 부분을 주의해서 'N개의 서버'에 데이터가 복제되도록 해야한다.
얼마나 비동기적으로 데이터 다중화(복제)를 처리할지도 중요한 이슈다. 예를 들어 카프카는 ISR을 유지할 때, 몇 가지 옵션이 있다. 당연히 리더 노드에만 저장되는 것이 가장 빠르고, 다른 노드에 저장되는 것을 기다리는 것은 상대적으로 느리다. 왜냐하면 네트워크적으로 가장 느린 노드의 응답에 영향을 받기 때문이다.
- 리더 노드에만 저장되면 완료.
- 모든 ISR 노드에 저장되어야 완료.
- 최소 N개의 ISR 노드에 저장되어야 완료
데이터 일관성
여러 노드에 다중화 된 데이터는 적절히 동기화 되어야 한다. 많은 클라이언트에게 오는 요청이 각각 복제되기 때문에 서로 다른 값을 가질 수 있기 때문이다. 데이터 동기화를 위해 정족수 합의 (Quorom Consensus) 프로토콜이 사용되는데, 이를 통해 읽기 / 쓰기에서 일관성을 가질 수 있다.
쿼럼 컨센서스에서는 다음 세 가지가 사용된다.
- N : 데이터의 사본 개수
- W : 쓰기 연산에 대한 쿼럼. 쓰기 연산이 성공한 것으로 간주되려면, 코디네이터는 적어도 W개의 서버로부터 쓰기 연산 성공 응답을 받아야 함.
- R : 읽기 연산에 대한 쿼럼. 읽기 연산이 성공한 것으로 간주되려면, 코디네이터는 적어도 R개의 서버로부터 읽기 연산 성공 응답을 받아야 함.
여러 노드에서 쓰기를 하다보면, 각 노드마다 가지고 있는 값이 다를 수 있다. 이렇게 상태가 충돌(conflict)하는 경우는 주로 클라이언트가 읽기를 요청했을 때 발견되며, Vector Clock을 이용해서 해결된다. 자세한 것은 다음 단락에서 설명한다.
W = 1의 의미는 쓰기 연산이 성공했다고 판단하기 위해 중재자(Coordinator)는 최소 한 대의 서버로부터 쓰기 성공 응답을 받아야 한다는 것이다. 카프카 브로커의 경우, 각 토픽 파티션마다 리더가 존재하고 리더 파티션을 가진 브로커가 코디네이터 역할을 하기도 한다. 즉, 코디네이터 (중재자)는 외부에 있을 수도 있으나 시스템 내부에 존재할 수도 있다는 것이다.
W + R 과 N의 관계
W + R과 N은 어떤 값이 설정되느냐에 따라 서로 다른 의미를 가진다.
- R = 1, W = N : 빠른 읽기 연산에 최적화 된 시스템
- R = N, W = 1 : 빠른 쓰기 연산에 최적화 된 시스템
- W + R > N and (W, R >= N/2) : 강한 일관성이 보장됨. (보통 W = 2, R = 2)
- W + R <= N : 강한 일관성이 보장되지 않음.
W + R > N 이상일 경우에는 왜 강한 일관성이 보장된다는 것일까? W = 2, R = 2, N = 3을 생각해보자. 두 개의 서버에 '쓰기'가 완료되어야 하고, 클라이언트가 데이터를 요청할 때는 두 개의 서버에서 읽기가 완료되어야 한다는 것을 의미한다.
그림으로 표현해보면 위와 같다. 데이터 1개는 시계 방향으로 돌았을 때 처음으로 만나는 3개의 노드에 저장되어야 한다. 그런데 이 중에서 2개의 노드에만 복제가 완료되면, 코디네이터는 '쓰기'가 완료되었다고 가정한다. 이런 상태를 가정해보자. 두 가지 요청은 각각 다음 서버에 '쓰기 완료'응답을 받았다.
- 1초 : data의 값 10으로 설정 → s1, s2에 저장.
- 1.1초 : data의 값 20으로 설정 → s1, s3에 저장.
클라이언트가 data의 값을 요청하면, 코디네이터는 s1 ~ s3에게 데이터를 요청할 것이다. 그리고 2번의 읽기 응답을 받았을 때, 읽기가 완료되었다고 답변한다. s1에서는 20의 값을, s2에서는 10의 값을 전달할 것이다. 이 때 서로의 값이 충돌하는 부분은 Vector Clock을 이용해서 해결된 다음에 클라이언트에게 전달된다.
만약 이 때 R = 1이라면, 10을 반환할 수도 있고 20을 반환할 수도 있게 된다. 따라서 단순히 W + R > N이라고 강한 일관성을 보장하는 것이 아니라 W, R > N/2라는 조건도 만족해야한다.
일관성 모델
일관성 모델은 데이터의 일관성을 수준하는 모델이다. 아래 모델이 존재한다.
- 강한 일관성 : 모든 읽기 연산은 가장 최근에 갱신된 결과를 반환한다.
- 약한 일관성 : 읽기 연산은 Outdate된 값을 반환할 수도 있다.
- 최종 일관성(Eventually Consistency) : 약한 일관성의 한 형태. 갱신 결과가 결국에는 모든 사본에 반영(즉, 동기화) 되는 모델
강한 일관성을 달성하는 일반적인 방법은 모든 사본에 현재 쓰기 연산의 결과가 반영될 때까지 해당 데이터의 읽기 / 쓰기를 금지하는 것이다. 모든 노드에 분산 처리되어야 하기 때문에 가장 느린 노드의 네트워크만큼 느린 작업이 되므로 고가용성 시스템은 적합하지 않다.
다이나모, 카산드라 같은 저장소는 최종 일관성 모델을 선택하고 있다. Eventually Consistency를 선택하는 경우, 쓰기 연산이 병렬적으로 발생할 경우, 시스템에 저장된 값이 서로 다를 수 있다. 즉, 값의 충돌이 발생할 수 있는데 이런 충돌은 Vector Clock + 버저닝을 이용해서 해결할 수 있다.
비 일관성 해소 기법 : 데이터 버저닝.
데이터를 여러 노드에 복제하면 가용성은 높아지만 데이터 일관성이 희생된다. 버저닝 + 벡터 시계 (Vector Clock)을 이용하면 데이터 충돌을 해소시켜 줄 수 있다.
데이터 충돌은 위 상황에서 볼 수 있다.
- 서버1은 노드1에게 name, 존-샌프란시스코를 저장함.
- 서버2는 노드2에게 name, 존-뉴욕을 저장함.
이 때, R = 2인 상황이고 서버1이 name의 값을 요청하면 코디네이터는 적어도 2개의 서버에게서 값을 읽어와야한다. 이 때, 노드1에서 읽은 값은 존-샌프란시스코, 노드2에서 읽은 값은 존-뉴욕으로 데이터 충돌이 발생한다. 이것을 해결하기 위한 방법 중 하나로 데이터 버저닝 + 벡터 시계(Vector Clock)을 사용한다.
버저닝 + Vector Clock을 이용한 해결
지금부터는 각 데이터에 버전을 매기고, 각 버전을 벡터 시계에 저장한다. 그리고 벡터 시계에 저장된 값을 비교해서 충돌을 해결한다.
위의 그림을 바탕으로 벡터 시계를 한번 고려해보자.
- 서버 Sx에게 데이터 D를 기록해달라는 요청이 옴. 서버 Sx는 쓰기 연산을 처리하고, 벡터 시계는 D1([Sx,1])이 됨.
- 다른 클라이언트가 데이터 D1을 읽고 D2로 업데이트 한 다음 기록한다. D2는 D1에 대한 변경이므로 D1을 덮어쓴다. 이 때 쓰기 연산은 서버 Sx가 처리하고, 따라서 벡터 시계는 D2([Sx, 2])가 된다.
- 다른 클라이언트가 D2를 읽어 D3로 갱신한 다음 기록함. 이 때 서버 Sy가 처리함. D3의 벡터 시계는 D3([Sx,2], [Sy,1])로 바뀜.
- 또 다른 클라이언트가 D2를 읽어 D4로 갱신한 다음 기록함. 이 때 서버 Sz가 처리함. D4의 벡터 시계는 D4([Sx,2], [Sz,1])이 됨.
- 클라이언트가 데이터를 요청함. 이 때 R=2라면 D3, D4의 데이터를 읽어옴. 데이터의 충돌이 발생하는 것을 확인함. 이 충돌은 클라이언트가 해소함. 해소한 값을 서버 Sx를 통해서 쓰고 벡터 시계는 D5([Sx,3], [Sy,1], [Sz,1])로 바뀐다.
벡터 시계를 사용하면 충돌이 발생한 것을 판단할 수 있다. 충돌이 발생하면, 클라이언트는 이 충돌을 적절히 해결해서 값을 일치시킬 수 있다.
벡터 시계를 이용해서 이전 버전인지를 확인하는 방법은 다음과 같다.
- D([s0, 1], [s1,1]) 은 D([s0,2], [s1,1])의 이전 버전이다. 이런 경우 충돌 없음.
- D([s0,1], [s1,2])와 D([s0,2], [s1,1])은 충돌함.
충돌은 클라이언트가 해결하는데, 위에서 볼 수 있듯이 완전히 동시에 일어난 작업이거나, 순서를 유추할 수 없는 데이터 충돌이 발생할 때도 있다. 이럴 때 클라이언트는 몇 가지 방향성을 선택해서 충돌을 해결한다.
- 어플리케이션 수준에서 해결 : 값을 병합하거나 (Concat 처럼), 사용자에게 어떤 값을 사용할지 질의. 혹은 Collection 형태로 병합.
- 마지막 쓰기 : 마지막에 작성된 값을 사용함. (구분이 애매할 수 있음)
벡터 시계 + 버저닝을 이용한 충돌 해결의 단점
벡터 시계 + 버저닝을 이용한 데이터 충돌을 해결하는 방법은 몇 가지 단점이 존재한다.
- 충돌 감지 및 해소 로직을 클라이언트에서 구현해야 함. → 클라이언트의 구현이 복잡해짐.
- 벡터 시계의 [서버:버전]의 순서쌍이 굉장히 빨리 증가함. 특정 사이즈 이상의 경우 몇몇 쌍을 제거하는 방식도 가능하지만, 이 경우 일부 시계 쌍이 없어지므로 선후 관계를 정확하게 결정하는데 어려움이 있음.
아마존 다이나모에서 벡터 시계 + 버저닝으로 데이터 충돌을 해결하는데, 아마존에서는 실제 서비스에서 2번과 관련된 문제가 발생한 적은 없다고 한다.
장애 처리
장애 감지
멀티 캐스팅 / 가십 프로토콜.
가십 프로토콜에서는 맥스값으로 처리해볼 수 있을 듯? 내 상태를 알려주고.
일시적 장애 처리
엄격한 정족수
느슨한 정족수
영구적 장애 처리
머클트리로 처리
데이터 센터 장애 처리
시스템 아키텍처 다이어그램
쓰기 경로
읽기 경로
요약
블룸 필터
가십 프로토콜
- https://jins-dev.tistory.com/244
- https://medium.com/@heonjang.lee96/gossip-%ED%94%84%EB%A1%9C%ED%86%A0%EC%BD%9C%EC%9D%B4%EB%9E%80-906500c3de4b
'Spring' 카테고리의 다른 글
| 가상 면접 사례로 배우는... : 안정 해시 설계 (0) | 2023.08.20 |
|---|