- 키-값 저장소(key-store store)는 비 관계형(non-relational) 데이터베이스
- 저장되는 값은 고유 식별자(identifier)를 키로 가져야 함
- 키와 값 사이의 연결 관계를 "키-값" 쌍(pair)라고 함
- 키-값 쌍에서 키는 유일해야 함
- 키는 일반 텍스트일 수도 있고 해시일 수도 있음
- 값은 문자열일 수도 있고, 객체일 수도 있음(무엇이든 상관 없다)
가정
- 키-값 쌍의 크기는 10KB 이하
- 큰 데이터 저장 가능
- 높은 가용성 - 장애가 있더라도 빨리 응답
- 높은 규모 확장성 - 트래픽 양에 따라 자동적으로 증설/삭제
- 데이터 일관성 수준은 조정이 가능해야
- 응답 지연시간(latency)이 짧아야
단일 서버 키-값 저장소
- 직관적인 방법: 키-값 쌍 전부를 메모리에 해시 테이블로 저장
- 빠른 접근 속도, 메모리 용량의 한계
- 개선책
- 데이터 압축(compression)
- 자주 쓰이는 데이터만 메모리에 두고 나머지는 디스크에
- 한 대의 서버로는 한계가 명확해, 분산 키-값 저장소(distributed key-value store)를 만들 필요
분산 키-값 저장소
CAP 정리(Consistency, Availability, Partition Tolerance theorem)
- 데이터 일관성(consistency), 가용성(availability), 파티션 감내(Partition Tolerance)라는 세 가지 요구사항을 동시에 만족하는 분산 시스템을 설계하는 것은 불가능
- 데이터 일관성: 모든 클라이언트는 어떤 노드에 접속하더라도 언제나 같은 데이터를 보게 돼야 함
- 가용성: 클라이언트는 일부 노드에 장애가 발생하더라도 항상 응답을 받을 수 있어야 함
- 파티션 감내: 네트워크에 파티션이 생기더라도 시스템은 계속 동작해야 함
- 파티션은 두 노드 사이에 통신 장애가 발생하였음을 의미
- 요구사항 선택에 따른 분류
- CP 시스템: 일관성과 파티션 감내를 지원하고, 가용성을 희생
- AP 시스템: 가용성과 파티션 감내를 지원하고, 데이터 일관성을 희생
- CA 시스템: 일관성과 가용성을 지원하고, 파티션 감내를 희생
- 그러나 네트워크 장애는 피할 수 없는 일이므로, 분산 시스템은 파티션 문제를 감내할 수 있도록 설계돼야 함
- 현실에 존재하지 않음
- 예시
- 가정: 노드 n1 ~ n3에 데이터가 복제돼 보관되는 상황
- 특정 노드에 기록된 데이터는 자동으로 다른 노드로 복제
- 이상적인 상태에서는 일관성, 가용성 보장
- 파티션 문제가 발생한 경우(n3 장애 가정)
- n3에 기록됐으나 n1, n2로 전달되지 못한 데이터가 있을 경우
- 일관성을 선택
- 노드 사이의 데이터 불일치를 피하기 위해 n1, n2에 쓰기 연산 중단
- 가용성 희생
- 가용성을 선택
- 오래된 데이터를 반환할 위험이 있더라도 n1, n2에서 읽기 및 쓰기 연산 허용하고 파티션 문제가 해결된 뒤에 새 데이터를 n3로 전송
시스템 컴포넌트
데이터 파티션
- 전체 데이터를 작은 파티션들로 분할한 다음 여러 대 서버에 저장
- 데이터를 여러 서버에 고르게 분산할 수 있는가
- 노드가 추가/삭제될 때 데이터 이동을 최소화할 수 있는가
- 안정 해시(consistent hash)가 좋은 해결책이 될 수 있음
- 규모 확장 자동화(automatic scaling): 시스템 부하에 따라 추가/삭제되게 할 수 있음
- 다양성(heterogeneity): 서버의 용량에 맞게 가상 노드(virtual node) 수 조절 가능
데이터 다중화
- 가용성과 안정성 확보를 위해 데이터를 N개 서버에 비동기적으로 다중화(replication)
- N개의 서버는 해시 링에서 시계 방향으로 순회하며 만나는 첫 N개의 서버 선택 가능
- 가상 노드를 쓰는 경우, 같은 물리 서버를 중복 선택하지 않도록 처리
- 안정성을 위해 데이터의 사본은 다른 센터의 서버에 보관하고, 센터들을 고속 네트워크로 연결
데이터 일관성
- 정족수 합의(Quorum Consensus) 프로토콜로 읽기/쓰기 연산에서 일관성 보장
- 정의
- N: 사본 개수
- W: 쓰기에 대한 정족수
- R: 읽기에 대한 정족수
- 예시: N = 3, W = 1인 경우
- 중재자(coordinator)가 최소 한 대의 서버로부터 쓰기 성공 응답을 받으면, 나머지 두 대의 서버 성공 응답 상관 없이 쓰기 연산이 성공했다고 판단
- 중재자는 클라이언트와 노드 사이에서 프록시(proxy) 역할
- W, R, N 값은 응답 지연과 데이터 일관성 사이에서 잘 조율해야
- R = 1, W = N: 빠른 읽기에 최적화
- W = 1, R = N: 빠른 쓰기에 최적화
- W + R > N: 강한 일관성 보장(보통 N = 3, W = R = 2)
- W + R <= N: 강한 일관성 보장하지 않음
- 일관성 모델(consistency model)
- 키-값 저장소의 데이터 일관성 수준을 결정하는 요소
- 강한 일관성(strong consistency)
- 모든 읽기는 가장 최근에 갱신된 결과를 반환
- 클라이언트는 절대로 낡은(out-of-date) 데이터를 볼 수 없음
- 약한 일관성(weak consistency)
- 읽기 연산은 가장 최근에 갱신된 결과를 반환하지 못할 수 있음
- 결과적 일관성(eventual consistency)
- 갱신 결과가 결국에는 모든 사본에 반영(동기화)됨
- 모든 사본에 현재 쓰기 연산의 결과가 반영될 때까지 해당 데이터에 대한 읽기/쓰기를 금지하면 강한 일관성 달성
- 새 요청 처리가 중단돼 고가용성 시스템에 부적합
- 결과적 일관성 모델의 경우, 쓰기 연산이 병렬적으로 발생하면 시스템에 저장된 값의 일관성이 깨질 수 있음
비 일관성 해소 기법: 데이터 버저닝
- 버저닝(versioning)과 벡터 시계(vector clock)으로 사본 간 일관성 달성
- 버저닝은 데이터를 변경할 때마다 해당 데이터의 새 버전을 만드는 것
- 즉, 각 버전의 데이터는 변경 불가능(immutable)
- 데이터 일관성이 깨지는 경우
- 어떤 데이터의 사본이 두 노드에 저장된다고 가정
- 각 서버에서 동일한 키에 대한 값을 바꾸는 연산이 동시에 이뤄지는 경우 충돌(conflict)하는 두 값이 생김
- 각각을 버전 v1, v2라고 할 때, 이를 어떻게 해결할 것 인가?
- 백터 시계(vector clock)
- [서버, 버전] 순서쌍을 데이터에 기록하는 것
- 어떤 버전이 선행 버전인지 후행 버전인지, 다른 버전과 충돌이 있는지 판별
- D([S1, v1], ... [Sn, vn])
- D: 데이터
- vi: 버전 카운터
- Si: 서버 번호
- 데이터 D를 서버 Si에 기록하면
- [Si, vi]가 있으면 vi 증가
- 없다면 [Si, v1] 생성
- 백터 시계를 통한 충돌 판별
- 버전 Y에 포함된 모든 구성요소의 값이 X에 포함된 구성요소 값보다 같거나 크다면 Y는 X보다 이후 버전임이 보장
- D([s0, 1], [s1, 1])은 D([s0, 1], [s1, 2])의 이전 버전
- 버전 Y에 포함된 모든 구성요소의 값이 X에 포함된 구성요소 값보다 작은 게 있다면 충돌이 있음
- D([s0, 1], [s1, 2])와 D([s0, 2], [s1, 1])은 충돌
- 단점
- 충돌 감지 및 해소 로직이 클라이언트에 들어가 클라이언트 구현이 복잡해짐
- [서버, 버전] 순서쌍의 개수가 굉장히 빨리 늘어남
- 임계치(threshold)를 설정하고, 오래된 순서쌍을 제거
장애 처리
- 장애 감지(failure detection)
- 두 대 이상의 서버가 똑같은 서버의 장애를 보고해야 해당 서버에 장애가 발생했다고 간주
- 모든 노드 사이에 멀티 캐스팅(multicasting) 채널 구축
- 가십 프로토콜(gossip protocol) 같은 분산형 장애 감지(decentralized failure detection) 솔루션
- 각 노드는 멤버십 목록(membership list) 유지
- 멤버십 목록은 각 멤버 ID와 박동 카운터(heratbeat counter) 쌍의 목록
- 각 노드는 주기적으로 자신의 박동 카운터 증가
- 각 노드는 무작위로 선정된 노드들에 주기적으로 자기 박동 카운터 목록 전송
- 박동 카운터 목록을 받은 노드는 멤버심 목록 갱신
- 어떤 멤버의 박동 카운터 값이 지정된 시간 동안 갱신되지 않으면, 해당 멤버는 장애(offline)으로 간주
- 일시적 장애 처리
- 엄격한 정족수(strict quorum) 접근법을 쓴다면, 읽기와 쓰기 연산을 금지
- 느슨한 정족수(sloppy quorum) 접근법은 가용성을 높이는 방법 적용
- 쓰기를 수행할 W개의 건강한 서버와 읽기를 수행할 R개의 건강한 서버를 해시 링에서 선택
- 장애 상태 서버로 가는 요청은 다른 서버가 잠시 처리
- 발생한 변경사항은 서버가 복구됐을 때 일괄 반영해 데이터 일관성 보존
- 임시로 쓰기 연산을 처리한 서버에는 그에 관한 단서(hint)를 남김
- 단서 후 임시 위탁(hinted handoff) 기법
- 영구 장애 처리
- 반-엔트로피(anti-entropy) 프로토콜 구현해 사본들을 동기화
- 사본 간의 일관성이 망가진 상태를 탐지하고 전송 데이터 양을 줄이기 위해 머클(Merkle) 트리 사용
- 머클 트리(또는 해시 트리)는 각 노드에 그 자식 노드들에 보관된 값의 해시(자식이 leaf인 경우), 또는 자식 노드들의 레이블로부터 계산된 해시 값을 레이블로 붙여두는 트리
- 대규모 자료 구조의 내용을 효과적이면서 보안상 안전한 방법으로 검증(verification)
- 데이터 센터 장애 처리
- 데이터를 여러 데이터 센터에 다중화하는 것이 중요