[Book - 가상 면접 사례로 배우는 대규모 시스템 설계 기초] 6. 키-값 저장소 설계
키-값 쌍에서의 키는 유일해야 하며, 키는 일반 텍스트일 수도 있고 해시 값일 수도 있다.
성능상의 이유로 키는 짧을수록 좋다.
키-값 쌍에서의 값은 문자열일 수도 있고 리스트일 수도 있고 객체일 수도 있다.
값에는 무엇이 오든 상관하지 않는다.
문제 이해 및 설계 범위 확정
완벽한 설계란 없다.
읽기, 쓰기 그리고 메모리 사용량 사이에 어떤 균형을 찾고, 데이터의 일관성과 가용성 사이에서 타협적 결정을 내린 설계를 만들었다면
쓸만한 답안일 것이다.
아래 특성을 값는 키-값 저장소를 설계해 보자.
- 키-값 쌍의 크기는 10KB 이하이다.
- 큰 데이터를 저장할 수 있어야 한다.
- 높은 가용성을 제공해야 한다.
- 따라서 시스템은 설사 장애가 있더라도 빨리 응답해야 한다.
- 높은 규모 확장성을 제공해야 한다.
- 따라서 트래픽 양에 따라 자동적으로 서버 증설/삭제가 이루어져야 한다.
- 데이터 일관성 수준은 조정이 가능해야 한다.
- 응답 지연시간(latency)이 짧아야 한다.
단일 서버 키-값 저장소
서버 한 대만 사용하는 가장 직관적인 방법은 키-값 쌍 전부를 메모리에 해시 테이블로 저장하는 것이다.
그러나 이 접근법은 빠른 속도를 보장하기 하지만 모든 데이터를 메모리 안에 두는 것이 불가능할 수도 있다는 약점을 갖고 있다.
이 문제를 해결하기 위한 개선책으로는 아래와 같은 것이 있다.
- 데이터 압축(compression)
- 자주 쓰이는 데이터만 메모리에 두고 나머지는 디스크에 저장
그러나 이렇게 개선한다고 해도, 한 대 서버로 부족한 때가 곧 찾아온다.
많은 데이터를 저장하려면 분산 키-값 저장소를 만들어야 한다.
분산 키-값 저장소
분산 키-값 저장소는 분산 해시 테이블이라고도 불린다.
분산 시스템을 설계할 때는 CAP 정리(Consistency, Availability, Partition Tolerance theorem)를 이해하고 있어야 한다.
CAP 정리
CAP 정리는 아래 세 가지 요구사항을 동시에 만족하는 분산 시스템을 설계하는 것은 불가능하다는 정리다.
- 데이터 일관성(consistency)
- 분산 시스템에 접속하는 모든 클라이언트는 어떤 노드에 접속했느냐에 관계없이 언제나 같은 데이터를 보게 되어야 한다.
- 가용성(availability)
- 분산 시스템에 접속하는 클라이언트는 일부 노드에 장애가 발생하더라도 항상 응답을 받을 수 있어야 한다.
- 파티션 감내(partition tolerance)
- 파티션은 두 노드 사이에 통신 장애가 발생하였음을 의미한다.
- 파티션 감내는 네트워크에 파티션이 생기더라도 시스템은 계속 동작하여야 한다는 것을 뜻한다.
CAP 정리는 아래 그림과 같이 이들 가운데 어떤 두 가지를 충족하려면 나머지 하나는 반드시 희생되어야 한다는 것을 의미한다.
- CP 시스템
- 일관성과 파티션 감내를 지원하는 키-값 저장소
- 가용성을 희생한다.
- AP 시스템
- 가용성과 파티션 감내를 지원하는 키-값 저장소
- 데이터 일관성을 희생한다.
CA 시스템- 일관성과 가용성을 지원하는 키-값 저장소
- 파티션 감내는 지원하지 않는다.
- 그러나 통상 네트워크 장애는 피할 수 없는 일로 여겨지므로, 분산 시스템은 반드시 파티션 문제를 감내할 수 있도록 설계되어야 한다.
- 그러므로 실세계에 CA 시스템은 존재하지 않는다.
이상적 상태
이상적 환경이라면 네트워크가 파티션되는 상황은 절대로 일어나지 않을 것이다.
n1에 기록된 데이터는 자동적으로 n2와 n3에 복제된다.
데이터 일광성과 가용성도 만족된다.
실세계의 분산 시스템
분산 시스템은 파티션 문제를 피할 수 없다.
그리고 파티션 문제가 발생하면 일관성과 가용성 사이에서 하나를 선택해야 한다.
- 가용성 대신 일관성을 선택한다면(CP 시스템)
- 세 서버 사이에 생길 수 있는 데이터 불일치 문제를 피하기 위해 n1과 n2에 대해 쓰기 연산을 중단시켜야 하는데,
- 그렇게 하면 가용성이 깨진다.
- 은행권 시스템은 보통 데이터 일관성을 양보하지 않는다.
- 예를 들어, 온라인 뱅킹 시스템이 계좌 최신 정보를 출력하지 못한다면 큰 문제일 것이다.
- 네트워크 파티션 때문에 일관성이 깨질 수 있는 상황이 발생하면 이런 시스템은 상황이 해결될 때까지 오류를 반환해야 한다.
- 일관성 대신 가용성을 선택한 시스템(AP 시스템)은
- 낡은 데이터를 반환할 위험이 있더라도 계쏙 읽기 연산을 허용해야 한다.
- n1과 n2는 계속 쓰기 연산을 허용할 것이고,
- 파티션 문제가 해결된 뒤에 새 데이터를 n3에 전송할 것이다.
분산 키-값 저장소를 만들 때는 그 요구사항에 맞도록 CAP 정리를 적용해야 한다.
이 문제에 대해 면접관과 상의하고, 그 결론에 따라 시스템을 설계하도록 하자.
시스템 컴포넌트
1. 데이터 파티션
데이터를 파티션 단위로 나눌 때는 아래 두 가지 문제를 중요하게 따져봐야 한다.
- 데이터를 여러 서버에 고르게 분산할 수 있는가
- 노드가 추가되거나 삭제될 때 데이터의 이동을 최소화할 수 있는가
5장에서 다룬 안정 해시는 이런 문제를 푸는 데 적합한 기술이다.
어떤 키-값 쌍을 어떤 서버에 저장할지 결정하려면 우선 해당 키를 같은 링 위에 배치한다.
그 지점으로부터 링을 시계 방향으로 순회하다 만나는 첫번째 서버가 바로 해당 키-값 쌍을 저장할 서버다.
안정 해시를 사용하여 데이터를 파티션하면 좋은점은 아래와 같다.
- 규모 확장 자동화(automatic scaling)
- 시스템 부하에 따라 서버가 자동으로 추가되거나 삭제되도록 만들 수 있다.
- 다양성(heterogeneity)
- 각 서버의 용량에 맞게 가상 노드의 수를 조정할 수 있따.
2. 데이터 다중화(replication)
높은 가용성과 안정성을 확보하기 위해서는 데이터를 N개 서버에 비동기적으로 다중화(replication)할 필요가 있다.
여기서 N은 튜닝 가능한 값이다.
N개 서버를 선정하는 방법은 어떤 키를 해시 링 위에 배치한 후,
그 지점으로부터 시계 방향으로 링을 순회하면서 만나는 첫 N개 서버에 데이터 사본을 보관하는 것이다.
따라서 N=3으로 설정한 아래 그림에서 key0는 s1, s2, s3에 저장된다.
그런데 가상 노드를 사용한다면 위와 같이 선택한 N개의 노드가 대응될 실제 물리 서버의 개수가 N보다 작아질 수 있다.
이 문제를 피하려면 노드를 선택할 때 같은 물리 서버를 중복 선택하지 않도록 해야 한다.
같은 데이터 센터에 속한 노드는 정전, 네트워크 이슈, 자연재해 등의 문제를 동시에 겪을 가능성이 있다.
따라서 안정성을 담보하기 위해 데이터의 사본은 다른 센터의 서버에 보관하고,
센터들은 고속 네트워크로 연결한다.
3. 데이터 일관성(consistency)
여러 노드에 다중화된 데이터는 적절히 동기화가 되어야 한다.
정족수 합의(Quorum Consensus) 프로토콜을 사용하면 read/write 연산 모두에 일관성을 보장할 수 있다.
아래 그림은 N=3인 경우로 관계된 정의는 아래와 같다.
- N=사본 개수
- W=쓰기 연산에 대한 정족수
- 쓰기 연산이 성공한 것으로 간주되려면 적어도 W개의 서버로부터 쓰기 연산이 성공했따는 응답을 받아야 한다.
- R=읽기 연산에 대한 정족수
- 읽기 연산이 성공한 것으로 간주되려면 적어도 R개의 서버로부터 응답을 받아야 한다.
W=1의 의미는 write 연산이 성공했다고 판단하기 위해 중재자는 최소 한 대 서버로부터 write 성공 응답을 받아야 한다는 뜻이다.
따라서 s1으로부터 성공 응답을 받았다면 s0, s2로부터의 응답은 기다릴 필요가 없다.
중재자는 클라이언트와 노드 사이에서 proxy 역할을 한다.
W, R, N의 값을 정하는 것은 latency와 데이터 일관성 사이의 타협점을 찾는 전형적인 과정인데, 어떻게 정해야 할까?
- R = 1, W = N
- 빠른 read 연산에 최적화된 시스템
- W = 1, R = N
- 빠른 write 연산에 최적화된 시스템
- W + R > N
- 강한 일관성이 보장됨 (보통 N=3, W=R=2)
- W + R <= N
- 강한 일관성이 보장되지 않음
[일관성 모델]
일관성 모델은 일관성의 수준을 결정하는데, 아래와 같이 종류가 다양하다.
- 강한 일관성(strong consistency)
- 모든 read 연산은 가장 최근에 갱신된 결과를 반환한다.
- 즉, 클라이언트는 절대로 낡은(out-of-date) 데이터를 보지 못한다.
- 약한 일관성(weak consistency)
- read 연산은 가장 최근에 갱신된 결과를 받환하지 못할 수 있다.
- 결과적 일관성(eventual consistency)
- 약한 일관성의 한 형태로, 갱신 결과가 결국에는 모든 사본에 반영(동기화)되는 모델이다.
- write 연산이 병렬적으로 발생하면 시스템에 저장된 값의 일관성이 깨어질 수 있는데, 이 문제는 클라이언트가 해결해야 한다.
- 다이나모, 카산드라
클라이언트 측에서 데이터의 버전 정보를 활용해 일관성이 깨진 데이터를 읽지 않도록 하는 기법에 대해서는 아래에서 다룬다.
4. 비 일관성 해소 기법: 데이터 버저닝
데이터를 다중화하면 가용성은 높아지지만 사본 간 일관성이 깨질 가능성은 높아진다.
versioning과 vector clock은 그 문제를 해소하기 위해 등장한 기술이다.
versioning은 데이터를 변경할 때마다 해당 데이터의 새로운 버전을 만드는 것을 의미한다.
따라서 각 버전의 데이터는 변경 불가능(immutable)하다.
versioning 전에 데이터 일관성이 어떻게 깨지는지 보자.
데이터의 사본이 노드 n1, n2에서의 name이 모두 “john”이기 때문에 동시에 조회가 이루어져도 현재는 문제가 없다.
이제 아래 그림과 같이 서버1과 서버2에서 name을 동시에 바꿔보면, 충돌(conflict)하는 두 값을 갖게 되고,
각각을 버전 v1, v2라고 하자.
마지막 두 버전 v1, v2 사아의 충돌은 해소하기 어려워 보인다.
이 문제를 해결하려면, 충돌을 발견하고 자동으로 해결해 낼 versioning 시스템이 필요하며,
vector clock은 이런 문제를 푸는데 보편적으로 사용되는 기술이다.
vector clock은 [서버, 버전]의 순서쌍을 데이터에 매단 것이다.
어떤 버전이 선행 버전인지, 후행 버전인지, 아니면 다른 버전과 충돌이 있는지 판별하는데 쓰인다.
- 충돌X
- D([s0, 1], [s1, 1]) -> D([s0, 1], [s1, 2])
- 충돌O
- D([s0, 1], [s1, 1]) -> D([s0, 1], [s1, 2])
- D([s0, 1], [s1, 1]) -> D([s0, 2], [s1, 1])
- 서로 충돌이 난다.
[vector clock 단점]
- 충돌 감지 및 해소 로직이 클라이언트에 들어가야 하므로, 클라이언트 구현이 복잡해진다.
- [서버:버전]의 순서쌍 개수가 굉장히 빨리 늘어난다.
아마존의 다이나모 데이터베이스는 실제 서비스에서 위와 같은 문제가 벌어지는 것을 발견한 적이 없다고 한다.
5. 장애 처리
[장애 감지]
보통 두 대 이상의 서버가 똑같이 서버 A의 장애를 보고해야 해당 서버에 실제로 장애가 발생했다고 간주하게 된다.
multicasting 채널을 구축하는 것이 서버 장애를 감지하는 가장 손쉬운 방법이다.
하지만 이 방법은 서버가 많을 때는 분명 비효율적이다.
가십 프로토콜 같은 분산형 장애 감지 솔루션을 채택하는 편이 보다 효율적이며, 동작 원리는 아래와 같다.
- 각 노드는 멤버십 목록을 유지한다.
- 멤버십 목록은 각 멤버 ID와 그 박동 카운터 쌍의 목록이다.
- 각 노드는 주기적으로 자신의 박동 카운터를 증가시킨다.
- 각 노드는 무작위로 선정된 노드들에게 주기적으로 자기 박동 카운터 목록을 보낸다.
- 박동 카운터 목록을 받은 노드는 멤버십 목록을 최신 값으로 갱신한다.
- 어떤 멤버의 박동 카운터 값이 지정된 시간 동안 갱신되지 않으면 해당 멤버는 장애(offline) 상태인 것으로 간주한다.
- 노드 s0은 그림 좌측의 테이블과 같은 멤버십 목록을 가진 상태다.
- 노드 s0은 노드 s2의 박동 카운터가 오랫동안 증가되지 않았다는 것을 발견한다.
- 노드 s0은 노드 s2를 포함하는 박동 카운터 목록을 무작위로 선택된 다른 노드에게 전달한다.
- 노드 s2의 박동 카운터가 오랫동안 증가되지 않았음을 발견한 모든 노드는 해당 노드를 장애 노드로 표시한다.
[장애 해소: 일시적 장애 처리]
가십 프로토콜로 장애를 감지한 시스템은 가용성을 보장하기 위해 필요한 조치를 해야 한다.
엄격한 정족수(strict quorum) 접근법을 쓴다면,
앞서 데이터 일관성을 고려하여 read/write 연산을 금지해야 할 것이다.
느슨한 정족수(sloppy quorum) 접근법은 이 조건을 완화하여 가용성을 높인다.
정족수 요구사항을 강제하는 대신, write 연산을 수행할 W개의 건강한 서버와 read 연산을 수행항 R개의 건강한 서버를 해시 링에서 고른다.
이때 장애 상태인 서버는 무시한다.
장애 상태인 노드 s2에 대한 read/write 연산은 일시적으로 노드 s3가 처리하여 그에 관한 단서(hint)를 남겨둔다.
s2가 복구되면 s3는 갱신된 데이터를 s2로 인계한다.
이런 장애 처리 방안을 단서 후 임시 위탁(hinted handoff) 기법이라 부른다.
[장애 해소: 영구 장애 처리]
영구적인 노드의 장애 상태를 처리하기 위해 반-엔트로피(anti-entropy) 프로토콜을 구현하여 사본들을 동기화한다.
또한 사본 간의 일관성이 망가진 상태를 탐지하고 전송 데이터의 양을 줄이기 위해서는 머클(Merkle) 트리를 사용할 것이다.
위키피티아에 따르면 Merkle tree의 정의는 아래와 같다.
hash tree라고도 불리며,
각 노드에 그 자식 노드들에 보관된 값의 해시, 또는 자식 노드들의 레이블로부터 계산된 해시 값을 레이블로 붙여두는 트리다.
해시 트리를 사용하면 대규모 자료 구조의 내용을 효과적이면서도 보안상 안전한 방법으로 검증할 수 있다.
key space가 1부터 12까지일 때 Merkle 트리가 아래와 같은 단계로 만들어진다. (일관성이 망가진 데이터가 위치한 상자는 다른색으로 표시)
- 키 공간을 bucket으로 나눈다.
- bucket에 포함된 각각의 키에 균등 분포 해시 함수를 적용하여 해시 값을 계산한다.
- bucket별로 해시값을 계산한 후, 해당 해시 값을 레이블로 갖는 노드를 만든다.
- 자식 노드의 레이블로부터 새로운 해시 값을 계산하여, 이진 트리를 상향식으로 구성해 나간다.
6. 시스템 아키텍처 다이어그램
아키텍처의 주된 기능은 아래와 같다.
- 클라이언트는 키-값 저장소가 제공하는 두 가지 단순한 API, 즉 get(key) 및 put(key, value)와 통신한다.
- 중재자(coordinator)는 클라이언트에게 키-값 저장소에 대한 proxy 역할을 하는 노드다.
- 노드는 안정 해시의 해시 링 위에 분포한다.
- 노드를 자동으로 추가 또는 삭제할 수 있도록, 시스템은 완전히 분산된다. (decentralized)
- 데이터는 여러 노드에 다중화된다.
- 모든 노드가 같은 책임을 지므로, SPOF(Single Point of Failure)는 존재하지 않는다.
완전히 분산된 설계를 채택했으므로, 모든 노드는 아래 그림에 제시된 기능 전부를 지원해야 한다.
7. 쓰기 경로(write path)
write 요청이 특정 노드에 전달되면 무신 일이 벌어지는지 아래 Cassandra의 사례를 보자.
- write 요청이 commit log 파일에 기록된다.
- 데이터가 메모리 캐시에 기록된다.
- 메모리 캐시가 가득차거나 사전에 정의된 어떤 임계치에 도달하면 데이터는 디스크에 있는 SSTable에 기록된다.
SSTable은 Sorted-String Table의 약어로, <키, 값>의 순서쌍을 정렬된 리스트 형태로 관리하는 테이블이다.
8. 읽기 경로(read path)
read 요청을 받은 노드는 데이터가 메모리 캐시에 있는지부터 살핀다.
있는 경우에는 아래 그림과 같이 해당 데이터를 클라이언트에게 반환한다.
데이터가 메모리에 없는 경우에는 디스크에서 가져와야 한다.
어느 SSTable에 찾는 키가 있는지 알아낼 효율적인 방법으로 Bloom filter가 흔히 사용된다.
데이터가 메모리에 없을 때 read 연산이 처리되는 경로를 보면 아래 그림과 같다.
- 데이터가 메모리에 있는지 검사한다. (없으면 2로)
- 데이터가 메모리에 없으므로 bloom filter를 검사한다.
- bloom filter를 통해 어떤 SSTable에 키가 보관되어 있는지 알아낸다.
- SStable에서 데이터를 가져온다.
- 해당 데이터를 클라이언트에게 반환한다.