•
memcahced, redis, amazon dynamo 등
•
문제 이해 및 설계 범위 확정
◦
읽기, 쓰기, 메모리 사용량 사이의 균형을 찾고 데이터 일관성과 가용성 사이에서 타협적 결정을 내린 설계
◦
문제 이해
▪
키-값 쌍의 크기는 10KB 이하
▪
큰 데이터를 저장할 수 있어야 함
▪
높은 가용성을 제공, 설사 장애가 있더라도 빨리 응답
▪
높은 규모 확장성을 제공, 트래픽 양에 따라 자동적으로 서버 증설/삭제
▪
데이터 일관성 수준은 조정이 가능해야 함
▪
응답 지연시간이 짧아야 함
◦
단일 서버 키-값 저장소
▪
키-값 쌍 전부를 메모리에 해시 테이블 형태로 저장
•
빠른 속도를 보장하나 모든 데이터를 메모리 안에 두는 것이 불가능할 수 있음
•
데이터 압축, 자주 쓰이는 데이터만 메모리에 두고 나머지는 디스크에 두는 방법으로 해결 가능
•
하지만 이 방법 또한 결국 단일 서버라는 한계로 인해 분산 서버를 구현해야할 때가 옴
◦
분산 키-값 저장소
▪
분산 해시 테이블이라고도 불림, 키-값 쌍을 여러 서버에 분산시키며 구현을 위해선 CAP 정리를 이해하고 있어야 함
▪
CAP 정리
•
CAP
◦
데이터 일관성 : 분산 시스템에 접속하는 모든 클라이언트는 어떤 노드에 접속하든 언제나 같은 데이터를 보아야 함
◦
가용성 : 분산 시스템에 접속하는 클라이언트는 일부 노드에 장애가 발생하더라도 항상 응답을 받을 수 있어야 함
◦
파티션 감내 : 파티션은 두 노드 사이에 통신 장애가 발생하였음을 의미함, 네트워크에 파티션이 생기더라도 시스템은 계속 작동해야 함
•
데이터 일관성, 가용성, 파티션 감내 즉 세 가지 요구사항을 동시에 만족하는 분산시스템을 구축하는 것은 불가능하다는 정리
•
키-값 저장소는 앞서 제시한 세 가지 요구사항 가운데 어느 두 가지를 만족하느냐에 따라 3개로 분류됨
◦
CP 시스템 : 일관성과 파티션 감내를 지원하는 키-값 저장소
◦
AP 시스템 : 가용성과 파티션 감내를 지원하는 키-값 저장소
◦
CA 시스템 : 일관성과 가용성을 지원하는 키-값 저장소, 네트워크 장애는 피할 수 없는 일로, 반드시 파티션 문제를 감내할 수 있게 설계되어야 하므로 실세계에 존재하지 않는 시스템
•
n1 - n2 - n3 세 개의 노드 중 하나의 노드에 장애가 생겼을 때
◦
장애가 발생한 노드의 데이터들은 다른 노드로 공유되지 않음
◦
CP 시스템 : 데이터 일관성을 유지하기 위해 나머지 2개의 노드에 대하여 쓰기 연산을 중단, 상황이 해결될 때까지 오류를 반환
◦
AP 시스템 : 낡은 데이터를 반환할 위험이 있더라도 계속 읽기 연산을 허용, 나머지 노드들도 쓰기 연산을 허용하며 파티션 문제가 해결된 뒤에 새 데이터를 장애 노드에 전송
▪
시스템 컴포넌트
•
널리 사용되어지고 있는 키-값 저장소 : Dynamo, Cassandra, BigTable
•
데이터 파티션
◦
전체 데이터를 한 개의 서버에 우겨넣는 것이 불가능하기 때문에 필요한 과정
◦
문제
▪
데이터를 여러 서버에 고르게 분산할 수 있는가
▪
노드가 추가되거나 삭제될 때 데이터의 이동을 최소화할 수 있는가
→ 안정 해시를 이용한 해결
⇒ 규모 확장 자동화, 다양성의 이점을 가질 수 있음
•
규모 확장 자동화 : 시스템 부하에 따라 서버가 자동으로 추가되거나 삭제되도록 만들 수 있음
•
다양성 : 각 서버의 용량에 맞게 가상 노드의 수를 조정할 수 있음
•
데이터 다중화
◦
높은 가용성과 안정성을 확보하기 위해서 데이터를 N개 서버에 비동기적으로 다중화해야 함
◦
같은 데이터 센터에 속해있는 노드는 정전, 네트워크 이슈, 자연재해 등의 문제를 동시에 겪을 가능성이 있어 데이터의 사본은 다른 센터의 서버에 보관하고 센터들은 고속 네트워크로 연결
•
데이터 일관성
◦
여러 노드에 다중화된 데이터는 적절히 동기화되어야 함
◦
정족수 합의 프로토콜을 사용하여 읽기/쓰기 연산에 일관성을 보장
▪
N = 사본 개수
▪
W = 쓰기 연산에 대한 정족수
▪
R = 읽기 연산에 대한 정족수
▪
예시
•
N = 3
•
W = 1이란 뜻은 쓰기 연산이 하나의 노드에 대해 성공했다면 응답을 기다릴 필요가 없음, 즉 빠른 쓰기 연산에 최적화된 시스템
•
R = 1도 동일함, 읽기 연산에 대해 최적화된 시스템
•
요구되는 일관성에 수준에 따라 W, R, N의 값을 조정함
•
일관성 모델
◦
강한 일관성 : 모든 읽기 연산은 가장 최근에 갱신된 결과를 반환
▪
달성 방법 : 모든 사본에 현재 쓰기 연산의 결과가 반영될 때까지 해당 데이터에 대한 읽기/쓰기 연산을 금지 ⇒ 고가용성 시스템에는 적합하지 않음
◦
약한 일관성 : 읽기 연산은 가장 최근에 갱신된 결과를 반환하지 못할 수 있음
◦
최종 일관성 : 약한 일관성의 한 형태로 갱신 결과가 결국에는 모든 사본에 반영
◦
비 일관성 해소 기법 : 데이터 버저닝 ⇒ HTTP Cache 방법인 ETag와 비슷
•
장애 처리
◦
장애 감지
▪
두 대 이상의 서버가 똑같이 특정 서버의 장애를 보고했을 때, 해당 서버에 장애가 발생했다고 간주
▪
multicasting의 보고 체계를 구축하면 O(n^2)[: n은 서버의 개수만큼]의 비효율적인 장애 감지 솔루션이 됨
▪
가십 프로토콜과 같은 분산형 장애 감지 솔루션을 채택하는 것이 효율적
•
가십 프로토콜
◦
각 노드는 멤버십 목록을 유지, 멤버십 목록은 각 멤버의 ID와 박동 카운터 쌍의 List 형태
◦
각 노드는 주기적으로 박동 카운터를 증가
◦
각 노드는 무작위로 선정된 노드들에게 주기적으로 자신의 박동 카운터를 보냄
◦
박동 카운터 목록을 받은 노드는 멤버십 목록을 최신 값으로 갱신
◦
어떤 멤버의 박동 카운터 값이 지정된 시간동안 갱신되지 않으면 해당 멤버는 장애 상태인것으로 간주
◦
일시적 장애 처리
▪
느슨한 정족수 접근법 사용
▪
정족수 요구사항을 강제하는 대신, 쓰기 연산을 수행할 W개의 건강한 서버와 읽기 연산을 수행할 R개의 건강한 서버를 해시 링에서 고름
▪
장애 상태인 서버로 가는 요청은 다른 서버가 잠시 맡아 처리
▪
그동안 발생한 변경사항은 해당 장애 서버가 복귀되었을 때 일괄 반영하여 데이터 일관성을 보존
◦
영구적 장애 처리
▪
반-엔트로피 프로토콜을 구현하여 사본들을 동기화
•
반-엔트로피 프로토콜
◦
사본들을 비교하여 최신 버전으로 갱신하는 과정 포함
◦
사본 간의 일관성이 망가진 상태를 탐지하고 전송 데이터의 양을 줄이기 위해서는 머클 트리를 사용
▪
머클 트리
•
정의
◦
해시 트리라고도 불리는 머클 트리는 각 노드에 그 자식 노드들에 보관된 값의 해시값을 함께 저장
•
시스템 아키텍처 다이어그램
•
쓰기 경로
•
읽기 경로
