6장. 키-값 저장소 설계
키-값 저장소(key-value store)는 비관계형 데이터베이스이다.
- 일반 텍스트 키: "last_loggred_in_at"
- 해시 키: 253DDEC4
키-값 저장소에서 값은 무엇이 오든 상관하지 않는다.
1. 단일 서버 키-값 저장소
- 가장 직관적인 방법 키-값 쌍 전부를 메모리에 해시 테이블로 저장하는 것
- 모든 데이터를 메모리 안에 두는 것이 불가능할 수도 있다는 약점도 있음.
- 해결 방법
- 데이터 압축
- 자주 사용하는 데이터만 메모리에 두고 나머지는 디스크에 저장
- 이렇게 해도, 한대 서버로 부족한 때가 온다. 분산 시스템으로 가자.
2. 분산 키-값 저장소
분산 키-값 저장소는 분산 해시 테이블이라고 한다.
키-값 쌍을 여러 서버에 분산시키는 탓인데, CAP를 이해해야한다.
CAP 정리
- 일관성(consistency): 모든 클라이언트는 어떤 노드에 접속했느냐에 상관없이 같은 데이터를 보게 되어야 한다.
- 가용성(availability): 일부 노드에 장애가 발생하더라도 항상 응답을 받을 수 있어야 한다.
- 파티션 감내(partition tolerance): 네트워크에 통신 장애가 발생하더라고 시스템은 계속 동작해야한다.
- CP 시스템: 일관성과 파티션 감내를 지원하는 키-값 저장소, 가용성을 희생
- AP 시스템: 가용성과 파티션 감내를 지원하는 키-값 저장소, 데이터 일관성을 희생
- CA 시스템: 일관성과 가용성을 지원하는 키-값 저장소, 파티션 감내는 지원하지 않는다.
- 실세계에 CA 시스템은 존재하지 않는다.
이상 상태
이상적환경은 네트워크 통신이 절대로 일어나지 않는 것이다.
실세계의 분산 시스템
분산 시스템은 네트워크 문제를 피할 수 없다.
만약, 문제가 발생하면 일관성과 가용성 사이에 하나를 선택해야한다.
은행권 시스템은 보통 데이터 일관성을 양보하지 않는다.
시스템 컴포넌트
- 데이터 파티션
- 데이터 다중화
- 일관성
- 일관성 불일치 해소
- 장애 처리
- 시스템 아키텍처 다이어그램
- 쓰기 경로
- 읽기 경로
데이터 파티션
데이터를 파티션 단위로 나눌 때, 두 가지 문제를 중요하게 확인해야 한다.
- 데이터를 여러 서버에 고르게 분산할 수 있는가
- 노드가 추가되거나 삭제될 때 데이터의 이동을 최소화할 수 있는가
5장에서 배운 안정해시를 사용하면 데이터를 파티션하는데 효과적이다.
데이터 다중화
데이터를 N개 서버에 비동기적으로 다중화할 필요가 있다.
N개 서버를 선정하는 방법은 해당 지점부터 시계 방향으로 링을 순화하면서 만나는 첫 N개 서버에 데이터 사본을 보관한다.
데이터 일관성
정족수 합의(Quorum Consensus) 프로토콜을 사용하면 읽기/쓰기 연산에 모두에 일관성을 보장할 수 있다.
- N=사본 개수
- W=쓰기 연산에 대한 정족수, 쓰기 연산이 성공한 것으로 간주되려면 적어도 W개의 서버로부터 쓰기 연산이 성공했다는 응답을 받아야 한다.
- R=읽기 연산에 대한 정족수, 읽기 연산이 성공한 것으로 간주되려면 적어도 R개의 서버로부터 응답을 받아야한다.
면접 시에 N, W, R 값을 어떻게 정해야할까?
- R=1, W=N: 빠른 읽기 연산에 최적화된 시스템
- W=1, R=N: 빠른 쓰기 연산에 최적화된 시스템
- W+R > N: 강한 일관성이 보장됨
- W+R <= N: 강한 일관성이 보장되지 않음
일관성 모델
- 강한 일관성: 모든 읽기 연산은 갖아 최근에 갱신된 결과를 반환한다.
- 약한 일관성: 읽기 연산은 가장 최근에 갱신된 결과를 반환하지 못할 수 있다.
- 결과적 일관성: 약한 일관성의 한 형태로, 갱신 결과가 결국에는 모든 사본에 반영되는 모델이다.
비 일관성 해소 기법: 데이터 버저닝
데이터를 다중화하면 가용성은 높아지지만 사본 간 일관성이 깨질 가능성이 있다.
이를 해결하기 위해 버저닝(versioning)과 벡터 시계(vector clock)이 해결하기 위해 등장했다.
- 버저닝: 데이터를 변경할 때마다 해당 데이터의 새로운 버전을 만드는 것을 의미한다.
- 각 버전의 데이터는 변경 불가능하다.
충돌 예시를 들면, 특정 두 연산이 동시에 이뤄지면 충돌하는 두 값을 가지게 된다.
충돌을 발견하고 자동으로 해결해 낼 버저닝 시스템이 필요로 하는데 백터 시계는 이런 문제를 푸는데 보편적으로 사용되는 기술이다.
- 벡터 시계: [서버, 버전]의 순서쌍을 데이터에 매단 것이다.
- 어떤 버전이 선행 버전인지, 후행 버전인지, 아니면 다른 버전과 충돌이 있는지 판별하는데 쓰인다.
예시)
- 클라이언트가 데이터 D1을 시스템에 기록한다. 쓰기 연산을 처리한 서버는 Sx이다. 따라서 D1[(Sx, 1)]로 변한다,
- 다른 클라이언트가 데이터 D1을 읽고 D2로 업데이트한 다음 기록한다.D2는 D1에 대한 변경이므로 D1을 덮어쓴다. 쓰기 연산은 같은 서버 Sx가 처리한다. 벡터 시계는 D2[(Sx, 2)]로 바뀔 것이다.
- 다른 클라이언트가 D2를 읽어 D3로 갱신한 다음 기록한다. 쓰기 연산은 Sy가 처리한다. 벡터 시계 상태는 D3([Sx,2], [Sy, 1])로 바뀐다.
- 다른 클라이언트가 D2를 읽고 D4로 갱신한 다음 기록한다. 쓰기 연산은 서버 Sz가 처리한다. 벡터 시계는 D4([Sx, 2], [Sz, 1])이다.
- 어떤 클라이언트가 D3와 D4를 읽으면서 데이터 간 충돌이 있다는 것을 알게 된다. D2를 Sy와 Sz가 각각 다른 값으로 바꾸었기 떄문이다. 충돌을 해소하고 서버에 기록한다.
어떤 버전 X가 버전 Y의 이전 버전인지 쉽게 판단할 수 있다.
→ 버전 Y에 포함된 모든 구성요소의 값이 X에 포함된 모든 구성요소 값보다 같거나 큰지만 보면 된다.
어떤 버전 X가 버전 Y 사이에 충돌이 있는지 확인하는 방법
→ Y 의 벡터 시계 구성요소 가운데 X의 벡터 시계 동일 서버 구성요소보다 작은 값을 갖는 것이 있는지 확인하면 된다.
→ 모든 구성요소가 작은 값을 갖는 경우에는 Y는 X의 이전 버전이다.
충돌을 감지하고 해소하는 방법에는 두 가지 단점이 있다.
- 충돌 감지 및 해소 로직이 클라이언트에 들어가야하므로, 클라이언트 구현이 복잡해진다.
- [서버:버전]의 순서쌍 개수가 굉장히 빨리 늘어난다. 임계치 이상으로 길이가 길어지면 오래된 순서쌍을 벡터 시계에서 제거해야한다 그러면 선후 관계가 정확하게 결정될 수 없기 때문에 충돌 해소 과정의 효율성이 낮아진다.
> 장애처리
대다수 시스템에서 흔하게 벌어지는 사건이다.
장애 감지와 장애 해소 전략을 확인해 보자
> 장애 감지
서버 한대가 죽으면 바로 장애처리를 하지 않는다.
보통 두 대 이상의 서버가 똑같이특정 서버 장애 보고해야 실제로 장애가 발생했다고 간주한다.
모든 노드 사이에 멀티 캐스팅 채널을 구추하는 것이 서버 장애 감지에 가장 쉬운 방법이다.
하지만, 서버가 많을 때는 비효율적이다.
가십 프로토콜 같은 분산형 장애 감지 솔루션을 채택하는 편이 효율적이다.
- 각 노드는 멤버십 목록을 유지한다. 멤버십 목록은 각 멤버 ID와 박동 카운터 쌍의 목록이다.
- 각 노드는 주기적으로 자신의 박동 카운터를 증가시킨다.
- 각 노드는 무작위로 선정된 노드들에게 주기적으로 자기 박동 카운터 목록을 보낸다.
- 박동 카운터 목록을 받은 노드는 멤버십 목록을 최신 값으로 갱신한다.
- 어떤 멤버의 박동 카운터 값이 지정된 시간 동안 갱신되지 않으면 해당 멤버는 장애 상태인 것으로 간주한다.
> 일시적 장애 처리
가십 프로토콜로 장애를 감지한 시스템은 가용성을 보장하기 위해 조치를 한다.
엄격한 정족수 접근법을 사용하면 읽기와 스기 연산을 금지한다.
느슨한 정족수 접근법을 사용하면 쓰기 연산을 수행할 W개의 건강한 서버와 읽기 연산을 수행할 R개의 건강한 서버를 해시 링에서 고른다. 장애 상태인 서버는 무시한다.
네트워크나 서버 문제로 장애 산태인 서버로 가는 요청은 다른 서버가 잠시 맡아 처리한다.
그 동안 발생한 변경사항은 해당 서버가 복구되었을 때 일괄 반영하여 데이터 일관성을 보존한다.
> 영구장애처리
영구적으로 노드 장애를 처리하기 위해 반-엔트로피 프로토콜을 구현하여 사본들을 동기화한다.
반-엔트로피 프로토콜은 사본들을 비교하여 최신 버전으로 갱신하는 과정을 포함한다.
사본 간의 일관성이 망가진 상태를 탐지하고 전송 데이터의 양을 줄이기 위해서 머클 트리를 사용한다.
- 키 공간을 버킷으로 나눈다.
- 버킷에 포함된 각각의 균등 분포 해시 함수를 적용하여 해시 값을 계산한다.
- 버킷별로 해시값을 계산한 후, 해당 값을 레이블로 갖는 노드를 만든다.
- 자식 노드의 레이블로부터 새로운 해시 값을 계산하여 이진 트리를 상향식으로 구성해나간다.
루트 노드의 해시 값이 일치한다면 두 서버는 같은 데이터를 갖고 있다.
만약 다른 경우, 왼쪽 자식 노드의 해시값을 비교하고, 그 다음 오른쪽 자식 노드의 해시값을 비교한다.
이와 같이 아래쪽으로 탐색해 나가면 다른 데이터를 갖는 버킷을 찾을 수 있고, 해당 버킷들만 동기화하면 된다.
> 데이터 센터 장애 처리
데이터 센터에 다중화하는 것이 중요하다.
시스템 아키텍처 다이어그램
- 클라이언트는 키-값 저장소가 제공하는 API get 및 put으로 통신한다.
- 중재자는 클라이언트에게 키-값 저장소에 대한 프록시 역할을 하는 노드이다.
- 노드는 안정 해시의 해시 링위에 분포한다.
- 노드를 자동으로 추가 또는 삭제할 수 있도록, 시스템은 완전히 분산된다.
- 데이터는 여러 노드에 다중화된다.
- 많은 노드가 같은 책임을 지므로, SPOF는 존재하지 않는다.
쓰기 경로
쓰기 요청이 특정 노드에 전달되면 무슨 일이 발생하는지 보여준다.
- 쓰기 요청이 커밋 로그 파일에 기록된다.
- 데이터가 메모리 캐시에 기록된다.
- 메모리 캐시가 가득차거나 사전에 정의된 어떤 임계치에 도달하면 데이터는 디스크에 있는 SSTable에 기록된다. SSTable은 Sorted-String Table의 약어로 <키, 값> 의 순서쌍을 정렬된 리스트 형태로 관리하는 테이블이다.
읽기 경로
읽기 요청을 받은 노드는 데이터가 메모리 캐시에 있는지 살펴본다.
데이터가 메모리에 없는 경우에는 디스크에서 가져와야한다. 어느 SSTable에 찾는 키가 있는지 알아낼 효율적이 방법이 필요한데, 블룸 필터(Bloom filter)가 흔히 사용된다.
- 데이터가 메모리에 있는지 검사하고 없으면 2로 간다.
- 데이터가 메모리에 없으므로 블룸 필터를 검사한다.
- 블룸 필터를 통해 어떤 SSTable에 키가 보관되어 있는지 알아낸다.
- SSTable에서 데이터를 가져온다.
- 해당 데이터를 클라이언트에게 반환한다.
요약
| 목표/문제 | 기술 |
| 대규모 데이터 저장 | 안정 해시를 사용해 서버들에 부하 분산 |
| 읽기 연산에 대한 높은 가용성 보장 | 데이터를 여러 데이터센터에 다중화 |
| 쓰기 연산에 대한 높은 가용성 보장 | 버저닝 및 벡터 시계를 사용한 충돌 해소 |
| 데이터 파티션 | 안정해시 |
| 점진적 규모 확장성 | 안정해시 |
| 다양성 | 안정해시 |
| 조절 가능한 데이터 일관성 | 정족수 합의 |
| 일시적 장애처리 | 느슨한 정족수 프로토콜과 단서 후 임시 위착 |
| 영구적 장애 처리 | 머클 트리 |
| 데이터 센터 장애 대응 | 여러 데이터 센터에 걸치 데이터 다중화 |